Communications of the ACM

Contributed articles

Data Acquisition in Vehicular Ad Hoc Networks

By Xiaonan Wang
Communications of the ACM, May 2018, Vol. 61 No. 5, Pages 83-88
10.1145/3197544
Comments

With the amount of multimedia data large and growing larger, low-latency data acquisition represents an important practical goal for emerging Internet of Vehicles applications. Multihoming could help reduce such latency because it could let a single node use multiple addresses to acquire data in parallel. Network researchers are thus trying to extend multihoming to vehicular ad hoc networks (VANETs), aiming to reduce latency in the Internet of Vehicles. But in VANETs with multihoming, a vehicle must be able to perform n addressing processes to be configured with addresses with n global network prefixes (GNPs). And getting a vehicle to use addresses with different GNPs to acquire data in parallel through the standard communication models is a significant engineering challenge. Here, I propose an address-separation mechanism so vehicles can be configured with addresses with different GNPs in a single addressing process, extending the k-anycast model to help acquire data in parallel.

Back to Top

Key Insights

Vehicles on the road today include abundant computer processing and storage, producing demand for connecting VANETs to the Internet so they can acquire a variety of multimedia data.^1,6,12 In multihoming, one IP domain is identified by n (n ≥ 2) GNPs, and a node can be configured with n addresses with different GNPs.⁷ A node would use these addresses to acquire data in parallel, thus reducing data-acquisition latency.^{3, 4, 5} However, network researchers trying to extend multihoming to VANETs must first address two main technical challenges:³

Addressing. A node usually performs an addressing process with addresses including one GNP;² that is, a node must perform n addressing processes to be configured with addresses with n GNPs, leading to considerable addressing latency; and

Data acquisition. In unicast and any-cast models, a node acquires data from a single provider. In multicasting, a multicast address works only as a destination address. Each destination multicast member receives a copy of data from a particular source, so a multicast member actually acquires data from a single provider. A node cannot use addresses with different GNPs to acquire data from providers in parallel via uni-cast, anycast, or multicast.

Wang⁹ proposed a k-anycast communication model in the IPv6 network with one GNP. In the k-anycast model,⁹ one k-anycast group consists of k-anycast members that cooperate to provide data in parallel; that is, a user can acquire data from more than one member in parallel, greatly reducing data-acquisition latency. Due to the efficiency of the k-anycast model, vehicle-network researchers are looking to take advantage of the k-anycast idea. Addressing and data-acquisition latency can thus be reduced through multihoming and the k-anycast model. Based on my proposed architecture for VANET with multihoming, a vehicle can be configured with addresses with different GNPs through a single addressing process, substantially reducing addressing latency. Also based on my proposed architecture, the k-anycast model can be extended through a single GNP⁹ to VANET with multiple GNPs so the vehicle would use addresses with multiple GNPs to acquire data from different k-anycast members in parallel, thus reducing data-acquisition latency.

There are two main differences between the data-acquisition mechanism I propose and the one suggested by the k-anycast mechanism:⁹

Multiple GNPs. The data-acquisition mechanism based on the i-anycast model⁹ works in the IPv6 network with a single GNP, whereas the one I propose works in VANETs with multiple GNPs; and

A single GNP. In Wang,⁹ the optimal k-anycast members that cooperate to provide data are selected based on one GNP, whereas the optimal k-anycast members are chosen based on multiple GNPs.

Anycast is different from k-anycast. In anycast, a node acquires data from one anycast member, whereas in k-anycast, a node acquires data from more than one k-anycast member in parallel.

Back to Top

Architecture

In DAVM, a VANET consists of access points (APs) and vehicles and is connected to the Internet through access routers (ARs). The lanes enclosed by p_x (p_x ≥ 2) APs construct a vehicular multihoming domain (VMD) M_x, and each AP is denoted by AP_x−y (1 ≤ y ≤ p_x). AP_x−y links with r_x−y (1 ≤ r_x−y) AR(s) denoted by AR_x−y−z (1 ≤ z ≤ r_x−y) that identifies one GNP denoted by GNP_x−y−z. M_x can thus be defined by GNP set G_x, as shown in Equation (1). One vehicle in M_x can use each GNP in G_x to construct an IPv6 address and utilize the addresses with different GNPs to acquire data from providers in parallel. As shown in Figure 1, two VMDs, M₁ and M₂, are included. The lanes enclosed by AP_x−y (x = 1, 1 ≤ y ≤ 4) form VMD M₁, which is defined by GNP set G₁, and the lanes enclosed by AP_x−y (x = 2, 1 ≤ y ≤ 4) construct VMD M₂, which is defined by GNP set G₂.

Figure 1. Architecture.

In DAVM, one VMD is defined by a GNP set and the VMD-based architecture yields two main benefits:

Address separation. A single VMD can help achieve the proposed address-separation mechanism in VANET through multihoming to help reduce addressing latency. In the address-separation mechanism, a vehicle in one VMD is configured with a globally unique node ID through a single addressing process, then combines the node ID with each GNP in the GNP set defining the VMD to construct globally unique addresses with different GNPs. A vehicle can thus be configured with addresses with different GNPs through a single addressing process; and

In parallel. A VMD can help achieve the k-anycast model in the VANET with multiple GNPs to reduce data-acquisition latency; that is, a vehicle in one VMD can use the addresses with different GNPs to acquire data from different optimal k-anycast members in parallel.

Back to Top

Addressing

In order to reduce the address-configuration latency in VANET with multiple GNPs, I propose address separation as a way to achieve the addressing, whereby a vehicle in M_x performs only one addressing process to be configured with a globally unique node ID and is uniquely identified through this node ID during its lifetime. The vehicle then combines its node ID with each GNP in G_x to construct globally unique addresses with different GNPs. A vehicle can thus be configured with addresses with different GNPs through a single addressing process.

Node ID space. If a node ID is w-bits long (w is a positive integer) and the number of APs is 2^a (1 ≤ a <w−1, a is a positive integer), then the node ID space [1, 2^w−2] is divided into 2^a parts, with each part for one AP. The m^th (1 ≤ m ≤ 2^a) AP's node ID A(m) is shown in Equation (2), and the m^th AP's node ID space [L(m), U(m)] is shown in Equation (3) and Equation (4). Each AP thus has a unique node ID and maintains its globally unique node ID space.

GNP set. In DAVM, an AP stores the GNP sets defining the VMDs it belongs to. In M_x, AP_x−y can acquire GNP_x−y−z by receiving a router advertisement from AR_x−y−z. When AP_x−y acquires the GNP set x−y, as shown in Equation (5), it then performs the three operations to acquire G_x:

Broadcasts. AP_x−y sets G_x to G_x−y and broadcasts one Neig-AP message where the payload is G_x−y−z.

Performs operations. Following receipt of the Neig-AP, a vehicle or AP performs acquisition operations based on three cases:

Case 1. A vehicle outside an AP's communication range receives the Neig-AP, and the vehicle forwards the Neig-AP and repeats the operation;

Case 2. A vehicle within an AP's communication range receives the Neig-AP, then updates the destination address in the Neig-AP with the address of the AP, forwards the Neig-AP, and repeats the operation; and

Case 3. An AP receives the Neig-AP, then updates G_x by performing the union operation, as shown in Equation (6).

Ends. The process ends, as shown in Figure 2.

Figure 2. Addressing.

In this data-acquisition process, AP_x−y might employ a positioning method¹⁰ to determine the VMD one Neig-AP comes from. As shown in Figure 2, AP₁₋₁ in VMD M1 receives one Neig-AP from AP_x−y (x=1, 2 ≤ y ≤ 4) and establishes GNP set G₁ defining M₁. Likewise, AP_x−y (x = 1, 2 ≤ y ≤ 4) also acquires G₁ by receiving one Neig-AP. In this way, AP_x−y (x = 1, 1 ≤ y ≤ 4) acquires G₁.

Address construction. A vehicle V₁ in M_x that begins to move uses a hardware ID (such as a media-access control, or MAC, address) as a temporary address and acquires a node ID from the nearest AP AP_x−y based on the following three-step process:

Sends. V₁ sends one N-Req message to AP_x−y;

Marks the node. The AP_x−y receiving the N-Req returns one N-Rep message where the payload includes the assigned node ID and GNP set G_x defining M_x, then marks the node ID as "assigned"; and

Sets its node. The V₁ receiving the N-Rep sets its node ID to the node ID in the N-Rep and stores G_x, as shown in Figure 2.

Since AP_x−y's node ID space is globally unique, the node ID that AP_x−y assigns to V₁ is also unique. A V₁ configured with a globally unique node ID then combines its node ID with each GNP in G_x to acquire a globally unique IPv6 address. In Figure 2, V₁ is located in M₁, which is defined by G₁. When V₁ acquires a unique node ID from AP₁₋₁, it then combines the node ID with each GNP in G₁ to acquire seven unique IPv6 addresses.

Back to Top

Data Acquisition

In the k-anycast model with a single GNP,⁹ one k-anycast group consists of k-anycast members that cooperatively provide data in parallel. A user can thus acquire data from different k-anycast members in parallel, greatly reducing acquisition latency. In order to achieve the main DAVM objective of reduced data-acquisition latency, network researchers are trying to extend the k-anycast idea with one GNP⁹ to VANET with multihoming so vehicles are able to use addresses with different GNPs to acquire data from different optimal providers in parallel.

In DAVM, a single k-anycast address defines one type of content, and all providers able to provide that content construct a k-anycast group uniquely specified by the k-anycast address. The k-anycast address structure consists of w-bit k-anycast ID field and reserved field whose value is zero (see Table 1). In DAVM, a particular content C is divided into q (q ≥ 2) parts, with each part c_u (q ≥ u ≥ 1) uniquely identified by part ID d_u, as shown in Equation (7). A vehicle would use a content address to achieve k-anycast communications, with a content address consisting of the k-anycast ID and part ID set (see Table 2). The k-anycast ID specifies the type of desired content, and the part ID set indicates the specific parts of the content.

Table 1. k-anycast address.

Table 2. Content address.

Vehicle V₁ is located in M_x, as defined by GNP set G_x, and acquires content C₁ identified by k-anycast address K₁ through the following five-step process:

Selects. V₁ selects g (2 ≤ g ≤ |G_x|) GNPs from G_x to construct g addresses denoted by S_i (1 ≤ i ≤ g) where the node ID is V₁'s node ID and then constructs g content addresses denoted by D_i. In D_i, the k-anycast ID is the same as the ID in K₁, and the part ID set is P_i that defines the data parts B_i, as shown in Equation (8), where c_i−j (1 ≤ j ≤ |P_i|) is the data part identified by element d_i−j in P_i. This way, B_i satisfies Equation (9);

Sends. V₁ sends g data-request messages denoted by R_i in which the destination address is D_i and the source address is S_i;

Routs. Based on S_i, R_i is routed to AR_i, which specifies the GNP in S_i. Based on D_i, AR_i routes R_i to the optimal k-anycast member A_i with k-anycast address K₁. Based on P_i in D_i, A_i returns a data-response message E_i whereby the destination address is S_i and the payload is B_i;

Further routs. Based on the GNP in S_i, E_i is routed to AR_i and then, based on the node ID in S_i, E_i is routed to V₁; and

Receives data. V₁ can thus receive g data-response messages from different k-anycast members in parallel, as shown in Figure 3.

Figure 3. Data acquisition.

In Figure 3a, V₁ is located in M₁, which is defined by G₁ and connects with R_i (1 ≤ i ≤ 4), and the k-anycast group includes four members, A_i, that provide content C₁, as defined by k-anycast address K₁. C₁ is divided into fours parts, with each part defined by part ID d_i. V₁ constructs four content addresses D_i whereby the k-anycast ID is the same as the ID in K₁, and the part ID set is P_i. V₁ selects four GNPs, GNP_i, to construct four addresses, S_i. V₁ then sends four data-request messages R_i in which the source address is S_i and the destination address is D_i. Based on S_i, R_i reaches AR_i, which routes R_i to the optimal k-anycast member A_i. Based on P_i in D_i, A_i returns a data-response message E_i whereby the destination address is S_i and the payload is the content parts, B_i, as defined by P_i. Based on the GNP in S_i, E_i is routed to AR_i. Based on the node ID in S_i, E_i is routed to V₁, which receives different parts of C₁ from different k-anycast members in parallel.

Back to Top

Performance Evaluation

Following the earlier description of data acquisition, the addressing latency TA consists of the node ID request latency T_A-Req and the node ID response latency T_A-Rep, as shown in Equations (10), (11), and (12), in which b is the data rate, t is the delay in transmitting a bit between neighbors, t_Max is the delay in transmitting a message with maximum size s_Max between neighbors, l is the distance between a vehicle and the nearest AP, and s_ID-Req/s_ID-Rep is the size of an N-Req/N-Rep. Following the description of performance evaluation, the data-acquisition latency T_C consists of the data-request latency T_Req and data-response latency T_Rep, as shown in Equations (13), (14), and (15), in which l_i is the distance between AR_i and the nearest k-anycast member, l_i is the distance between AR_i and a particular vehicle, and s_Req/s_Rep is the size of a data request/response message. The notations used in DAVM are listed in Table 3.

Table 3. Notation.

DAVM is evaluated in ns-2 using the simulation parameters in Table 4 in which the number of k-anycast members is equal to g. DAVM is compared withaddressing standard² and the data-acquisition scheme with a single GNP⁹ called Data Acquisition One GNP, or DAOGNP, as shown in Figure 4 and Figure 5.

Table 4. Simulation parameters.

Figure 4. Addressing latency.

Figure 5. Data-acquisition latency.

As in Figure 4, with the increase in the number of addresses, the addressing latency in the standard increases, whereas the addressing latency in DAVM tends to be stable. Such stability follows from DAVM including an address-separation mechanism and a vehicle using a single addressing process configured with multiple addresses with different GNPs. As a result, addressing latency is only minimally affected by the number of addresses. In the standard, only a single addressing process is performed for each GNP, so the addressing latency grows with the number of addresses. As shown in Figure 5, with the increase in GNPs, the data-acquisition latency in both DAVM and DAOGNP decreases, but DAVM involves less data acquisition latency for two main reasons:

Based on multiple GNPs. In DAVM, the optimal k-anycast members that provide the data are selected based on multiple GNPs, whereas in DAOGNP, the optimal k-anycast member are selected based on a single GNP; and

Single address. In DAVM, a vehicle uses addresses with different GNPs to acquire data from optimal k-anycast members through different routing paths in parallel, whereas in DAOG-NP, a node uses a single address with a single GNP to acquire data from relatively optimal k-anycast members.

Back to Top

Conclusion

My observation that multihoming and k-anycast can help lower data-acquisition latency to extend multihoming and k-anycast to VANET is what led me to propose DAVM as a way to reduce data-acquisition latency. My results show DAVM works for three main reasons:

• Extends multihoming to VANET;
• Extends the k-anycast idea with one GNP to VANET with multihoming so vehicles can use addresses with different GNPs to acquire data from multiple k-anycast members in parallel; and
• Provides the address-separation mechanism so vehicles can obtain multiple addresses with different GNPs through a single addressing process.

My future work will aim to take advantage of the powerful computing capabilities and abundant storage resources of APs to help improve addressing and data acquisition in VANET with multihoming.

Back to Top

Acknowledgment

This work is supported by the 333 Project Foundation (grant number BRA2016438), CERNET Innovation Project (grant number NGII20170106), and National Natural Science Foundation of China (grant number 61202440).

Back to Top

Back to Top

The Digital Library is published by the Association for Computing Machinery. Copyright © 2018 ACM, Inc.

---

No entries found