Distributed relay selection with network coding for data dissemination in vehicular ad hoc networks

Abstract

Data dissemination in vehicular ad hoc networks has been an interesting research topic since rising applications can be run and served based on the success and efficiency of data dissemination in vehicular ad hoc networks. However, the volatile vehicle density, the highly dynamic topologies, and the packet lossy nature of the vehicular wireless communications pose real challenges for vehicular ad hoc networks to achieve high-speed content downloading and efficient resource utilization. In this work, we design a collision-free distributed relay selection method, by jointly considering the geographical locations, channel conditions, moving velocities, and packets receiving statuses of vehicles, to combat the mobility and lossy channel property of vehicular ad hoc networks. Moreover, we adopt the instantly decodable network coding for the selected relay vehicle to retransmit packets which were lost in the original transmission, resulting significant improvements in both network throughput and transmission delay. Simulation results show that the proposed strategy effectively reduces the delay of data dissemination in highway scenarios and improves the downloading rate, as well as the resource utilization of wireless channels.

Keywords

Relay selection network coding data dissemination vehicular ad hoc networks

Introduction

With the remarkable development of modern wireless technologies, researchers and automobile companies have applied vehicular ad hoc networks (VANETs) for inter-vehicle communications (IVC). The nodes in VANETs stand for the vehicles and the communication is done through wireless connections or with infrastructure.¹ For example, vehicles with the purposes of comfort, safety, and entertainment for the drivers and passengers will communicate with each other, using the communication devices installed in the vehicles by the automobile companies or with the access point on the road (i.e. roadside unit (RSU)). Furthermore, numerous attracting applications of vehicular networks are designed and envisioned,^2–5 such as safety warning, intelligent navigation, and mobile infotainment. Data dissemination is a particular promising type of applications which is related to both safety and commercial services. The main goal of data dissemination is to perform efficient data transmission from a source (e.g. access points (APs)) to other vehicles located in the area of interest (AoI). The specific applications of this type include multimedia advertisements, weather report, an update of the global positioning system (GPS) map about a city or a scenic area, and sometimes emergency information and eventual accident. Whereas, data dissemination represents a major challenge in VANETs due to the high node mobility and the lossy wireless medium under vehicular environments. The high node mobility can cause frequent changes in the network topology and constant fragmentation,⁶ while the lossy wireless links cause often packet losses and collisions, leading to prolonged downloading delay and decreased efficiency.⁷

Toward solving these problems, relay-assisted retransmission strategies have been introduced to data dissemination in VANETs. The relay selection is generally divided into two kinds, namely, centralized and distributed relay selection. For the centralized relay selection, relays are selected by a central server (CS) according to various selection criteria. Since the CS needs to collect all the channel information and process the selection criteria, a high complexity burden is posed on it, rendering the centralized method additional overhead.^8,9 Whereas, distributed relay selection does not require unified control center, and without global information gathering system, each node only needs to collect local network information, thus could elect relay by simple calculation.^10,11 Therefore, a distributed selection scheme can alleviate the burden of a control center and improve the system efficiency greatly, as well as reliability. In VANETs, due to the dynamic network topology characteristic, and that each vehicle has the capability of processing information and completing tasks independently, distributed relay selection is preferred.

In this article, we propose the non-collision relay selection with network coding (NCRS-NC), a distributed relay selection strategy with network coding multicast for data dissemination in VANETs. Relay vehicles are selected dispersedly to enhance the reliability of wireless multicast in VANETs and to ensure system scalability. The data dissemination consists of two stages, the relay selection stage and the relay retransmission stage. The novelty of this work lies in the following sides. First, in contrast with existing relay selection algorithms, the proposed NCRS-NC scheme jointly considers the vehicles’ geographical locations and moving velocities, the channels’ conditions and the packets’ reception statuses of vehicles, and combines the multiple parameters into the design of relay selection process. With elaborate study, the NCRS-NC relay selection method can help each unsatisfied vehicles find a suitable vehicle which can relay packets efficiently. Second, in view of the fact that the selected relay vehicles will apply instantly decodable network coding (IDNC) technique¹² for the retransmission stage, the packets’ usability is studied and exploited thoroughly through the relay selection stage, to guarantee the maximization of network coding gain. The packets’ usability is described from two aspects, one is the availability of packets which are lost by the unsatisfied vehicles, and the other is measured by the number of each relay candidate’s targeted vehicles. High packets’ usability indicates that the corresponding vehicle has received a large amount of packets that are lost by other vehicles, and the packets' combination which is constructed on this vehicle's received packets set is thus able to target more vehicles. Therefore, vehicles with high-packet usability are preferred in the relay selection process, under the same channel conditions. Third, different from conventional approaches based on the random-channel-access protocol, the NCRS-NC advocates a relay establishment process for acknowledging the relay relationship among the selected relay vehicle and its serving vehicles. Using an explicit acknowledgement message, the selected vehicle can be informed of the selection result and its serving vehicles, and thus performs the relay retransmission stage without collisions. In this way, the overhead of the proposed approach can be controlled and the waiting time before the selected relay that starts to multicast is minimized accordingly. Finally, the proposed NCRS-NC utilizes the IDNC technique to generate the optimal coded packet for each multicast during the relay retransmission stage. In contrast to classical randomized linear network coding (RLNC), the network coding related decoding delay of NCRS-NC is reduced to zero and the average dissemination delay is minimized.

The main contribution of this work can be summarized as follows:

We design a data dissemination strategy for multicasting packets efficiently in the vehicle-to-vehicle (V2V) communications in VANETs. The V2V communication consists of two phases: (a) relay selection phase, where unsatisfied vehicles select relay vehicles among their neighboring vehicles based on multiple measurements and (b) relay retransmission phase, where each selected relay vehicle retransmit lost packets for unsatisfied vehicles with the assistance of IDNC technique.

We propose a non-collision relay selection algorithm in the relay selection phase, which is distributed and based on multiple parameters such as packets’ reception statuses, vehicles’ positions and speeds, and packet erasure probabilities. Due to specific consideration for the maximization of the serving capability of relay vehicles, the algorithm is guaranteed to find at least one group of optimal relays at each time, with affordable overhead, to retransmit packets for unsatisfied vehicles.

We apply the IDNC coding technique for relay multicast in the relay retransmission phase. Using the IDNC technique, the proposed method is able to reduce the average downloading delay for data retransmission, and lower the encoding/decoding delay in the mean time. We present how to migrate the IDNC method into relay multicast in VANETs, so that the selected relays can help unsatisfied vehicles more effectively.

We implement the proposed strategy and evaluate its performance by extensive simulations. We compare our approach with the representative relay content distribution scheme for VANETs, namely, CodeOn, which is a push-based, network-coding-based data dissemination protocol and represents the current state-of-the-art. We also evaluate the compared algorithms’ performance with and without network coding. Significant improvement in average downloading rate and in average dissemination delay is obtained for highway scenarios with different parameter settings.

The rest of this article is organized as follows: Section “Related works” outlines the related works on data dissemination in VANETs. Section “System model” describes the system model. The proposed relay-assisted data dissemination strategy is provided in detail in section “NCRS-NC.” Section “Performance evaluation” provides the simulation results and discussions. Finally, section “Conclusion” concludes this article.

Related works

Relay selection for data dissemination in VANETs

Nandan et al.¹³ first introduced a swarming protocol, known as “SPAWN,” for VANETs. Using SPAWN, a vehicle requests data from an RSU if it is within the RSU’s range, and it requests data from neighboring vehicles on the contrary. A peer-to-peer protocol was used when the vehicle requests from neighboring nodes. After that, SPAWN was extended to the method AdTorrent.¹⁴ With AdTorrent, RSU continuously multicasts the common information to the vehicles within its coverage. When vehicles move out of the coverage, the provider delivers top-ranked content to the end user using swarming. However, this transmission control protocol can be highly overhead yet poorly performed due to the highly mobile lossy wireless links in VANETs. Various protocols are proposed to improve the transmission reliability by repeatedly multicasting messages or selecting the farthest node to relay messages.^15–17 However, repeated multicast cannot completely guarantee the transmission reliability but degrades the resource utilization.

The relay selection approaches for improving the content dissemination fall into two categorizes. One is the centralized methods and the other is the decentralized approaches. For the centralized methods, it is of great importance to have a control center which is responsible of collecting channel information and processing the relay selection. In VANETs, the control center is represented by the AP/RSU/source and is often inclined to become the system bottleneck. In view of this, the distributed selection schemes have been studied and proposed. Ma et al.,¹⁸ proposed a scheme to enhance the multicast reliability, including the preemptive priority in safety services. The suggested protocol selects the backbone vehicles as relay nodes, considering vehicle movement dynamics and link quality between vehicles. Yoo et al.¹¹ designed an opportunistic relay selection scheme which chooses the candidate relay with high chance to access channel and forward packets for the source vehicle. However, the scheme performance suffers from collisions for that when the network gets densified, the transmission collisions happen with high probability. Given the random-channel-access protocol, the retransmissions which are induced by the collisions further intensifies the collisions. Bi et al.¹⁰ proposed a novel composite relaying metric for relaying node selection by jointly considering the geographical locations, physical layer channel conditions, and moving velocities of vehicles. A distributed relay selection scheme based on these composite metrics was designed to guarantee that a unique relay is selected to reliably forward the emergency message in the desired propagation direction. However, the proposed scheme failed to consider the receiving statuses of vehicles, which is a great impact factor for the efficiency of relay selection and data dissemination.

Network coding for data dissemination in VANETs

Network coding (NC) was first proposed in 2000.¹⁹ It has been proven that a source node can send packets at the theoretical upper bound of transmission rate by employing network coding.^20,21 Therefore, NC has great potential to substantially improve transmission efficiency, throughput, and delay over multicast erasure channels. The traditional RLNC²² allows nodes to combine different data packets together and achieves the maximal network throughput. However, the optimal throughput is often obtained at the price of large decoding delay. Since each encoded packet requires to be decoded before the delivery to higher layers,^23,24 the successful decoding of each encoded packet asks for receiving a certain number of encoded packets. In contrast with RLNC, IDNC^12,25,26 is proposed to reduce the decoding delay by carefully choosing the set of data packets to be coded together in each transmission. By doing so, IDNC guarantees a subset of (or if possible, all) receivers be able to instantly decode one of their wanted packets upon successful reception of the coded packet.^27–29 Moreover, IDNC encoding can be implemented using binary XOR, which eliminates complicated operations over large Galois fields as required by RLNC.

To improve the efficiency of packet delivery to different mobile receivers, network coding has been widely used in VANETs.^7,30–34 Wang and Yin³⁰ studied the network-coding-based retransmission scheme on RSU and proposed an IDNC multicast retransmission algorithm that considers multiple vehicular communication characteristics. Simulation results that approved the algorithm are efficient in improving the data dissemination delay and download rate in VANETs. However, the overall system performance can be degraded since all works need to be done by the RSUs, which is the potential system bottleneck. In Wu et al.,³¹ the random network coding technique is incorporated with the cooperative multicast to address the bottleneck problem. A moving window network coding technique is used to upper bound the average decoding delay of a receiver. The decoding complexity scales as the window size increases. Liu et al.³² analyzed the V2V data dissemination with network coding in two-way road networks, where the vehicles move in opposite directions. The problem of multi-hop data dissemination in VANETs was considered in Wu et al.,³³ where the authors proposed a lightweight protocol which employs dynamically generated backbone vehicles to multicast packets so as to reduce the MAC-layer contention time at each node while maintaining a high packet dissemination ratio. Khlass et al.³⁴ proposed using cooperative relaying of vehicle for the poor channel quality between the nodes and the RSU to improve the connectivity of the network. For the bidirectional communication between the vehicle and RSU, it further uses analog network coding in relay node to improve the communication efficiency. Li et al. designed a method called CodeOn⁷ which is based on RLNC. In CodeOn, each node’s waiting time before data relaying depends on the node’s data remulticasting utility for its neighbors, which can be calculated after each node exchanges the decoding status with their one-hop neighbors. The protocol works well for lossy wireless problems in VANETs. However, frequent collisions may arise since CodeOn assigns each vehicle a back-off duration that is inversely proportional to its utility value, and thus degrade the system performance. Besides, the RLNC used in CodeOn requires complex encoding techniques and results extra decoding delay.

In this article, we propose a collision-free, distributed relay selection algorithm to coordinate the transmissions of vehicles. The proposed algorithm first selects a number of relay nodes among all vehicles based on the vehicular nodes’ speeds, locations, and multicast contents. After the relay selection, the IDNC scheme is applied at each relay node while constructing the NC packets for retransmission. Unlike the RLNC which requires sufficient coded packets to realize the full-rank decoding condition, the IDNC enables the instantly decodable property by including one wanted packet in the coding combination at most, thus minimizing the decoding delay and significantly improving the downloading rate and progress performance.

System model

We consider the general system model of data dissemination in VANETs that have been considered in many related works.^7,9 The APs (or RSUs) are the data sources, and vehicles inside the AoI are the end receivers. Each RSU is connected with the core Internet through the wired backhaul and is deployed in a straight road. Specifically, we consider the highway scenario where vehicles pass through the front of the RSU in lanes of the road at various speeds. Two types of data dissemination involved in the communication process: (1) vehicle-to-infrastructure (V2I) communication, where the roadside infrastructure (APs or RSUs) acts as information source that multicasts the data to the vehicles within its coverage and (2) vehicle-to-vehicle (V2V) communication, where the selected relay vehicle shares data with other vehicular nodes. APs can be placed either deterministically or randomly. The service architecture is illustrated in Figure 1.

Figure 1.

System model.

We make the similar assumptions as those in Li et al.⁷ and Shen et al.⁹ To model the coexistence of safety and commercial applications, we consider two representative channels. One is the control channel and the other is the service channel. Safety messages which may contain information of vehicles’ locations, speeds, and so on are multicasted through the control channel, and common messages are transmitted through the service channel. The interval between two consecutive safety messages should be smaller than 100 ms to guarantee the success transmissions.³⁵ Time is divided into periodical 100 ms/slot, and the transmission of each packet consumes one time slot. Besides, synchronization is required among all vehicles and RSUs to switch simultaneously between the control channel and the service channel. The utilization of time and channels is depicted in Figure 2.

Figure 2.

Time and channel utilization of each vehicle and each AP.

In the control channel, each AP and each vehicle multicast one beacon message in each slot.^7,36 A vehicle will merely listen to an AP’s content multicast in the service channel if it is in the range of the AP. Otherwise, a vehicle may share its received content cooperatively with its neighboring vehicles. Besides, the content distribution process involves only vehicles within the AoI.

Assume that vehicles can obtain their real-time locations and synchronize their clocks through the equipped GPS devices when they are within satellite coverage, and use auxiliary techniques to determine their locations when they are temporarily out of satellite coverage. ⁷ Due to the highly dynamic topology of VANETs and the lossy nature of the vehicular wireless channels, some vehicles may not receive the complete information when APs/sources disseminated the messages.

Further assume the number of packets for transmission is N, denoted as $P = {p_{1}, p_{2}, \dots, p_{N}}$ , the number of vehicles is M, denoted as $V = {v_{1}, v_{2}, \dots, v_{M}}$ . As described above, the data dissemination refers two processes. First, the ith access point AP_i multicasts the packets’ set $P$ sequentially to all vehicles within its coverage area, which is known as the V2I communication process. With perfect channel conditions, vehicles are able to receive all packets in $P$ and get satisfied with the service. However, parts of the vehicles are prone to experience erasure channels and need help with the lost packets. Therefore, the relay selection and retransmission process are required after the first process, and this article focuses on the second process as to improve the retransmission efficiency. In the relay retransmission (V2V communication) process, vehicles exchange local information with each other to perform the relay selection. In each control time slot, each vehicle multicasts its content reception status in the safety message, and the reception status information will be used as an implicit content request for relay selection. Thus, zero overhead is incurred in the service time slots. Furthermore, to limit the overhead impact on control time slots, any vehicle v_i’s reception status after the AP multicast process can be described as follows:

$H_{i}$ : The Has set of vehicle v_i is defined as the set of packets correctly received by v_i in the AP multicast process.

$W_{i}$ : The Wants set of vehicle v_i is defined as the set of packets that are lost by receiver v_i in the AP multicast process. In other words, $W_{i} = P / H_{i}$ .

The relay vehicles are selected based on multiple parameters that are contained in the exchanged messages. Once the relay nodes are determined, they apply the IDNC coding technology on the set of retransmission packets and multicast the coded packet to all the vehicles which have non-empty Wants sets. The coding and retransmission procedure repeats until all vehicles receive their Wants sets successfully.

NCRS-NC

After the AP multicast process, vehicles exchange their local information with each other through the control channel, including the reception statuses $(< H_{i}, W_{i} >)$ , the moving velocity, and the location. Based on the information, a V2V-distributed relay selection algorithm is proposed to select one or multiple suitable relays to retransmit the desired packets for unsatisfied vehicles in a time-efficient way, and the IDNC coding method is applied to further improve the network throughput and reduce the transmission delay. The relay selection algorithm consists of three steps: the construction of relay candidates set, the utility calculation, and the relay establishment.

Construction of relay candidates set

For any vehicle v_i, $W_{i} \neq \emptyset$ , a vehicle v_j(i≠j,1 ≤j≤M) can be considered as its relay candidate shall meet two requirements, one is the information availability, and the other is the channel usability. In specific, the information availability describes v_j’s capability of providing packets that are wanted by v_i, and the channel usability characterizes the channel condition between v_i and v_j.

In order to construct the relay candidates set, v_i executes the following three steps:

Step 1: Upon receiving the exchange information of the neighboring vehicles, v_i records the arrival time of v_j’s safety message as AT_ij, 1 ≤j≠i≤M and sorts AT_ij in ascending order. The order of AT_ij in this ascending sequence is denoted as R_ij.

Step 2: Since the safety messages which piggyback the neighboring vehicles’ packets reception statuses have been received, v_i checks the reception statuses of its neighboring nodes sequentially. If the condition $W_{i} \cap H_{j} = W_{i}$ , i≠j, is satisfied, which equals that v_j has all the desired packets of v_i, thus v_j is selected as a relay candidate for v_i. If more than one vehicles meet the above condition, all of them are selected into the relay candidates set of v_i.

Step 3: In case that none of v_i’s neighboring nodes meet the condition in Step 2, the relay candidate selection criteria relax as to check whether $W_{i} \cap H_{j} \neq \emptyset$ stands. If v_j satisfies the relaxed condition, then

r_{ij} = \frac{| W_{i} |}{| W_{i} \cap H_{j} |} \cdot e_{ij} \cdot R_{ij}

(1)

where e_ij is the packet erasure probability between v_i and v_j, and R_ij is the order of AT_ij in ascending sequence. The vehicle v_j with the minimum value of r_ij is selected into the relay candidates set of v_i. In this way, at least one node is guaranteed to be in the relay candidates set of v_i and each unsatisfied vehicles construct their relay candidates sets similarly.

The vehicle v_i then multicasts a message that contains the information of v_i’s location and speed, CAN_i: 〈location,. speed〉 to all the nodes in its relay candidates set. Also, the information can be piggybacked by the control signalings to minimize the overhead.

Utility calculation

In the construction of relay candidates set, a vehicle can be selected by multiple nodes as their relay candidate, and receives multiple CAN_IDs. Having the knowledge of the location and speed of requesting vehicles, a relay candidate v_j can calculate its capability of serving requesting vehicle v_i as follows

U_{ji} = \frac{n_{j}}{\sqrt{{(x_{i} - x_{j})}^{2} + {(y_{i} - y_{j})}^{2}} + \sqrt{{(s_{i} - s_{j})}^{2}}}

(2)

where n_j is the number of requesting vehicles that choose v_j as a relay candidate, (x_i, y_i) and (x_j, y_j) denote the coordinate of v_i and v_j, respectively. The first arithmetic square root in the denominator thus represents the Euclidean metric between v_i and v_j. Meanwhile, s_i and s_j refer to the speed of v_i and v_j, separately, so the second arithmetic square root in the denominator implies the relative velocity between v_i and v_j. It is reasonable to assume that the packet loss ratio between v_j and v_i is positively correlated with the Euclidean metric between v_j and v_i, as well as the relative velocity between v_j and v_i. The rationale behind equation (2) is that the utility of relay candidate v_j for serving v_i refers to its capability of satisfying v_i as quick as possible, and serving as much as possible vehicles at the same time, which can be further described as to optimize the packet usability and the successful transmission probability of v_j. On one hand, since the selected relay will multicast the needed packets, the packet usability depicts the number of vehicles that are targeted in each multicast. A targeted vehicle refers to the vehicle whose desired packet is scheduled to be multicasted in the current slot. In order to maximize the number of vehicles that are served by v_j in one multicast, the number of targeted vehicles should be maximized first. Thus, n_j is chosen as the measurement to specify the number of targeted vehicles for v_j, as well as the packet usability of v_j. On the other hand, the successful transmission probability decides the retransmission times, which has a strong impact on the relay retransmission efficiency. A high successful transmission probability means that v_i is likely to receive the desired packet from v_j in each multicast, and thus becomes satisfied as fast as possible. The successful transmission probability is relevant to the transmission distance and vehicles’ running speeds. Shorter Euclidean distance and smaller speed difference between v_j and v_i make the channel between them more stable, and thus less packet erasure occurs.

Given n_j fixed, the denominator in equation (2) is expected to be as small as possible, so as to guarantee the successful transmission between v_i and v_j. Whereas, the numerator is hoped to be as large as possible, so as to target and serve more requesting vehicles simultaneously. Therefore, choosing v_j with the greatest utility value as the relay vehicle is more efficient than choosing other vehicles which have smaller utility values, with respect to the fact that v_j has better channel condition and the potential to serve more requesting vehicles.

After the utility calculation, the relay candidate v_j sends the utility value U_ji to the requesting vehicle v_i.

Relay establishment

When the requesting vehicle v_i receives the utility values replied by its relay candidates, it chooses the candidate with the maximum utility value as its relay, and informs the selected vehicle explicitly with an acknowledgement. The relay-service relationship is established once the selected candidate receives the acknowledgement, and both the selected relay and v_i store each other into their relay table. After that, the relay retransmission starts immediately.

Applying IDNC coding method

At each retransmission, the selected relay generates a coded retransmission packet using the IDNC coding method. To achieve the appealing advantage of NC in network throughput without introducing too much decoding delay as the RLNC does, the minimum decoding delay problem for NC is formulated as a maximum weight clique problem over a well-structured graph in the IDNC method.

To minimize the decoding delay in IDNC, all possible packet combinations that are instantly decodable by any subset or all requesting vehicles should be explored. Generally speaking, if two packets in the Wants sets of two receivers are combinable in IDNC, the resulting coded packet can be decoded instantly by these two receivers. This can only happen when these two receivers are requesting the same packet or the packet wanted by each receiver is in the Has set of the other receiver. The combinations between all packets in the Wants sets of all vehicles can be represented as a graph model, denoted as the IDNC graph.^28,37

The IDNC graph $G (N, E)$ is constructed by first generating a vertex $n_{ij} \in N$ for each packet $p_{j} \in W_{i}$ , 1 ≤ i ≤ M. Two vertices n_ij and n_kl are connected by an edge in $E$ if one of the following conditions is true:

j = l: The two vertices are generated by the loss of the same packet j, indicating that the two different receivers i and k request for the same packet j.

$p_{j} \in H_{k}$ and $p_{l} \in H_{i}$ : The requested packet of receiver i is in the Has set of the receiver k, and vice versa.

Here, we give an example to explain the construction of IDNC graph $G$ . After the relay selection phase, assume v₀ has established its relay relationship between v₁, v₂, and v₃. In other words, v₀ has been chosen as the relay vehicle for v₁, v₂ and v₃, and v₀ is about to retransmit the missing packets for v₁, v₂, and v₃. Given the packets set $P = {p_{1}, p_{2}, p_{3}, p_{4}, p_{5}, p_{6}}$ , based on the received control signaling messages, v₀ is aware of the packets’ reception statuses of the requesting vehicles, and the packets’ reception statuses of the three requesting vehicles before the relay retransmission phase are shown in Table 1, where “1” indicates that the corresponding packet is received correctly by the vehicle, and “0” indicates that the corresponding packet is lost.

Table 1.

Packets’ reception status before the relay retransmission phase.

Requesting vehicle	p ₂	p ₃	p ₄	p ₅	p ₆
v ₁	0	1	0	1	0
v ₂	0	0	1	0	0
v ₃	1	0	0	1	1

Applying the vertex generating and edge drawing rules of the IDNC graph construction, we have the IDNC graph of the given example as shown in Figure 3. In this graph, the black dot represents the lost packets of requesting vehicles. For example, vertex n₁₂ is generated according to the observation that vehicle v₁ has lost packet p₂. The rest vertices in $G$ are produced similarly. Two vertices are connected with an edge according to the above-mentioned connecting conditions. It is easily observed that the maximal cliques of this graph are C₁ = {n₁₁, n₂₁, n₃₁} and C₂ = {n₁₄, n₂₅, n₃₄}, respectively. Particularly, clique C₁ = {n₁₁, n₂₁, n₃₁} is induced by the same lost packet p₁ at vehicles v₁, v₂, and v₃, and the transmission of p₁ is instantly decodable by v₁, v₂, and v₃. Clique C₂ = {n₁₄, n₂₅, n₃₄} is induced by two lost packets p₄ at vehicles v₁ and v₃, and p₅ at vehicle v₂. The edge between n₁₄ and n₃₄ is drawn based on the first connecting condition, while the edges between n₁₄ and n₂₅, n₃₄, and n₂₅ are painted according to the second connecting condition. The transmission of combing the two packets identified by the vertices in C₂, namely, p₄⊕p₅ is instantly decodable at all vehicles. When the vehicles receive the XORed packet, v₁ and v₃ can decode out packet p₄ using the cached p₅, and v₂ can decode out packet p₅ with the help of received p₄. In fact, since each requesting vehicle can decode out a lost packet from the retransmission, the multicast of IDNC packet p₄⊕p₅ generated on the maximal clique C₂ of $G$ achieves the maximal transmission rate, and the selected IDNC packet is the optimal packets’ combination for relay retransmission. The conclusion applies equally on clique C₁.

Figure 3.

IDNC graph $G$ constructed on the given example.

Generally speaking, let K be a maximal clique in $G$ . Any packet that is generated by XORing the source packets identified by the vertices of any maximal clique in $G$ is instantly decodable. Consequently, IDNC packets can be generated by maximal clique search over $G$ . The selected relay employs the IDNC algorithm at each retransmission that it randomly selects a maximal clique over $G$ for encoding and multicasting to all requesting vehicles. When vehicles receive the IDNC coded packet, they can decode a wanted packet and update their Has/Wants sets. After each retransmission, vehicles feedback a ACK/NAK of this retransmission to notify the success/failure of the retransmission and their updated packets reception statues. When the feedback is received by the relay, it updates the IDNC graph accordingly and starts the maximal clique search for the next retransmission. The procedure is repeated until all requesting vehicles receive all packets correctly.

The pseudo code of the proposed NCRS-NC data dissemination strategy is presented as in Algorithm 1. The relay selection stage is executed independently by each vehicle. During the process, vehicle v_i calculates the value r_ij (line7) (M − 1) times and calculates its capability of serving other vehicles (line15) (M − 1) times in the worst case to establish a relay-service relationship with other vehicles, the complexity of relay selection is thus the order of O(M). We use the classical priority queue-based branch and bound algorithm to solve the Maximum Clique Problem (MCP) in line 22 and the complexity of the MCP is of the order O(M × N × 2^M×N). However, vehicles usually can receive some data packets in the initial transmission, thus the packets need to be retransmitted are far less than N. Meanwhile, during the relay selection stage, more than one group of vehicles that have established relay relationships, and the vehicle number of one group is far less than M, thus the practical running time of MCP is reduced evidently.

Algorithm 1 Relay retransmission strategy NCRS-NC
Require: Vehicles’ reception statuses after the AP multicast process, the Has sets $H$ , Wants sets $W$ , speed s, locations (x, y), the packet erasure probability e, and the order of the safety message arrival time in ascending sequence R.
Ensure: The IDNC-coded retransmission packets.
//Distributed Non-Collision Relay Selection
//For each unsatisfied vehicle $v_{i} \in V$ , $W_{i} \neq \emptyset$
1: Step 1: Construction of Relay Candidates Set;
2: for each $v_{j} \in V$ , j≠ido
3: if $W_{i} \cap H_{j} = W_{i}$ then
4: put v_j into v_i’s relay candidates set
5: else
6: if $W_{i} \cap H_{j} \neq \emptyset$ then
7: calculate the value r_ij using formula (1)
8: end if
9: put the vehicle v_j with the minimum r_ij into v_i’s relay candidates set
10: end if
11: end for
12: v_i multicasts the CAN_i: 〈location, speed〉 to all the vehicles in it’s relay candidates set
13: Step 2: Utility Calculation;
14: for each requesting vehicle v_ido
15: relay candidate v_j calculates it’s capability of serving v_i using formula (2)
16: v_j sends the utility value U_ji to v_i
17: end for
18: Step 3: Relay Establishment;
19: The requesting vehicle chooses the candidate with the maximum utility value as the relay, and acknowledges the relay service relationship by informing the chosen vehicle with an ACK message.
//Relay Retransmission
20: while there is any unsatisfied vehicle do
21: the selected relay vehicle v_selected generate the IDNC graph $G (N, E)$ according to it’s serving vehicles’ reception statuses.
22: Find and return the maximal clique in $G$ which consists of the packets received by v_selected
23: XOR the packets in the returned maximal clique and multicast the coded packet, update the reception statuses
24: end while

Based on the relay selection strategy and the IDNC network coding method, the overall procedure of the proposed non-collision relay selection with network-coding-based data dissemination approach is shown in Figure 4. The relay selection phase and relay retransmission phase are performed orderly and periodically in the data dissemination procedure. Note that if all vehicles in the AoI have already received the whole packets set $P$ , there is no need to perform the relay selection and retransmission process, and the overall data dissemination process gets to the end.

Figure 4.

Flow chart of the overall proposed data dissemination approach.

Performance evaluation

We evaluate the performance of the proposed data dissemination strategy in this section. Specifically, we compare the proposed strategy with the classical random-access method, CodeOn-Basic,⁷ which is based on the RLNC, and the purely multicasting methods with relay. With the CodeOn-Basic method, the number of right-decoded packets d_k in each vehicle is considered as a metric which reflects the retransmission efficiency. Before each retransmission, each vehicle v_k first exchanges the information of d_k with their one-hop neighbors. Second, v_k calculates its data rebroadcasting utility as $Z_{k} = (1 | N_{v_{k}} |) (\sum_{v_{j \in N_{v_{k}}}} d_{k} - d_{j})$ . Third, each node waits for a random time before relaying the data, and the waiting time for v_k is denoted as $t_{k} = (1 - (Z_{k} / N | N_{v_{k}} |)) Δ t_{max} + rand (0, T_{J})$ , where Δt_max(= 2ms) and T_J ( = 100us). It is shown that the greater the utility, the shorter the average waiting time becomes before accessing the channel. For the purely multicasting methods, data packets are transmitted directly by the relay without NC. Similar to the proposed strategy, we assume that the overhead transmission is error free in CodeOn-Basic. Therefore, the performance of payload is the only concern in the comparisons. For simplicity, we use CodeOn-NC, CodeOn, and NCRS to denote the strategies of CodeOn-Basic with RLNC, CodeOn-Basic without NC, and the Non-Collision Relay Selection without Network Coding, respectively.

Simulation settings

We consider the highway scenarios and simulate the proposed algorithm, as well as the compared algorithms in Java Development Kit. The mobility model we use is similar to the Freeway Mobility Model (FMM) proposed in Mahajan et al.,³⁸ which is well accepted for modeling the traffic in highway scenarios. In FMM, the simulation area includes many multiple lane freeways without any intersections. At the beginning of the simulation, the vehicles are placed uniformly at random in the road area and move at different speeds. The vehicles randomly accelerate or decelerate with security distance between two subsequent vehicles in the same lane, and no change of lanes is allowed. In the highway environment, the map has been simplified to the AoI which consists of a unidirectional four-lane highway, each lane with a length of 6 km, as shown in Figure 5. The channel model is considered as the simple yet effective packet erasure channel with erasure probability generated randomly between [0.3, 0.4].

Figure 5.

Highway scenario.

To evaluate the impact of topology and traffic density, we simulate sparse and dense traffic for the scenario. The simulation parameters’ setting is as follows:

Vehicles’ speeds are randomly drawn from [20, 30] m/s.

The total number of vehicles in sparse highway scenario is 100, and 300 vehicles in the dense traffic scenario.

The number of packets that the AP/source multicasts varies between the range [20, 50].

In the simulations, we evaluate the delay performance of each strategy from two aspects: (1) average downloading progress, which is the average downloading percentage of the packets from the beginning of data dissemination to the end of it and (2) average dissemination delay, which is the average elapsed time from the start of data downloading to full completion.

Sparse versus dense

We evaluate the average downloading progress in Figure 6 and the average dissemination delay in Figure 7 for both sparse and dense traffic scenarios. There are two key observations. First, the average downloading progress of NCRS-NC is the fastest that NCRS-NC always completes its downloading progress first and achieves the shortest average dissemination delay in all shown cases. Second, NCRS-NC maintains high downloading rates with different numbers of packets and for both sparse and dense traffic scenarios. The downloading rate of NCRS-NC is three times quicker than the silver medal winner. Moreover, the NCRS-NC is less affected by the traffic density than the CodeOn-NC does, since the increment in completion times of the NCRS-NC in sparse and dense networks is much smaller than of the CodeOn-NC (with the same number of packets), meaning that NCRS-NC is more robust to variations in topology and vehicle density.

Figure 6.

Average downloading progress in sparse and dense scenarios: (a) sparse highway (20 packets), (b) sparse highway (50 packets), (c) dense highway (20 packets), and (d) dense highway (50 packets).

Figure 7.

Average dissemination delay in sparse and dense scenarios: (a) 20 packets and (b) 50 packets.

Number of packets

We study the effect of packets’ number on the average dissemination delay in Figure 8 with (a) 100 vehicles and (b) 300 vehicles. The dissemination delay of NCRS-NC is much lower than those of the three others with different numbers of packets. Furthermore, the curve of NCRS-NC’s dissemination delay ascends little when the number of packets increases, while the compared strategies’ curves raise rapidly, which indicates that the performance gain of NCRS-NC over the compared algorithms grows gradually with the packets’ number.

Figure 8.

Average dissemination delay with different number of packets: (a) 100 vehicles and (b) 300 vehicles.

Number of vehicles

Figure 9 depicts the average dissemination delay with different numbers of vehicles. It is shown that the number of vehicles affects the dissemination delay of compared strategies little due to the good scalability among the compared distributed strategies. Meanwhile, it is clear that the NCRS-NC has the shortest dissemination delay among all strategies with N = 20 and 50 packets, respectively.

Figure 9.

Average dissemination delay with different number of vehicles: (a) 20 packets and (b) 50 packets.

Comparisons of strategies

To sum up, we can see that the proposed NCRS-NC significantly outperforms the CodeOn, CodeOn-NC, and NCRS strategies. In general, both strategies with network coding (CodeOn-NC and NCRS-NC) outperform the non-coding strategies (CodeOn and NCRS), which proves the advantage of network coding.

The advantage of the proposed NCRS-NC over the CodeOn-NC derives from the non-collision transmissions and the IDNC. On one hand, for the CodeOn-NC, the utility of data relayed by each vehicle is almost the same with that of its neighborhood. It directly results in a negative effect that the waiting time before data relaying at each vehicle and its neighborhood can be very close, which leads to the frequent transmission collisions and thus degrades the performance. On the contrary, the proposed relay selection algorithm avoids the collision issue by computing relaying utility based on multiple parameters and explicitly acknowledge the relay relationships among vehicles. On the other hand, the CodeOn-NC requires the receivers to successfully collect N independent coded packets before decoding the original N packets, which introduces additional decoding delay and thus increases the dissemination delay. While for the IDNC, receivers can perform instant packet recovery upon appropriate receptions such that the successful decoding probability can be enhanced greatly. Therefore, the proposed strategy outperforms the CodeOn-NC.

Conclusion

In this article, we propose a novel data dissemination strategy for VANETs, which combines distributed relay selection and network coding multicast. The relay selection algorithm is designed collision-free, thus decreasing the packet loss ratio and reducing the dissemination delay. A network coding scheme based on IDNC technology is applied during the retransmission process to increase the throughput and to improve the downloading delay. Simulation results show that compared with the CodeOn-NC with RLNC and the non-NC transmission strategies, our proposed strategy performs better in terms of the average downloading progress and the dissemination delay. Moreover, benefitting from the IDNC, the performance advantage of the proposed strategy becomes more distinguishable in the dense traffic scenarios, which indicates the proposed strategy’s good practicability.

Footnotes

Academic Editor: Paolo Bellavista

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This study was supported by the National Natural Science Foundation of China (grant no. 61561029) and funded by the Talent Development Project of Kunming University of Science and Technology (grant no. KKSY201403024).

References

Yousefi

Mousavi

Fathy

. Vehicular ad hoc networks (vanets): challenges and perspectives. In: Proceedings of the 6th international conference on ITS telecommunications, Chengdu, China, 21–23 June 2006, pp.761–766. New York: IEEE.

Delot

Ilarri

Cenerario

. Event sharing in vehicular networks using geographic vectors and maps. Mob Inf Syst 2011; 7(1): 21–44.

Chou

Tseng

. A bipolar traffic density awareness routing protocol for vehicular ad hoc networks. Mob Inf Syst 2015; 2015: 1–12.

Cai

Cheng

. Delay minimization for data dissemination in large-scale vanets with buses and taxis. IEEE T Moblie Comput 2016; 15(8): 1939–1950.

Ahmed

Bouk

Yaqub

. Conet: controlled data packets propagation in vehicular named data networks, In: Proceedings of the 13th IEEE annual consumer communications networking conference (CCNC), Las Vegas, NV, 9–12 January 2016, pp.620–625. IEEE.

Rezende

Mammeri

Boukerche

. A receiver-based video dissemination solution for vehicular networks with content transmissions decoupled from relay node selection. Ad Hoc Netw 2014; 17: 1–17.

Yang

Lou

. Codeon: cooperative popular content distribution for vehicular networks using symbol level network coding. IEEE J Sel Area Comm 2011; 29(1): 223–235.

Xiao

Kui

, Relay schemes for intermittently connected vehicular networks with heterogeneous nodes. In: Proceedings of the 2014 IEEE wireless communications and networking conference (WCNC), Istanbul, Turkey, 6–9 April 2014, pp.2700–2704. New York: IEEE.

Shen

Cheng

Yang

. Data dissemination in vanets: a scheduling approach. IEEE T Intell Transp 2014; 15(5): 2213–2223.

10.

Cai

Shen

. A cross layer broadcast protocol for multihop emergency message dissemination in inter-vehicle communication. In: Proceedings of the 2010 IEEE international conference on communications (ICC), Cape Town, South Africa, 23–27 May 2010, pp.1–5. New York: IEEE.

11.

Yoo

Choi

Gerla

. An opportunistic relay protocol for vehicular road-side access with fading channels. In: Proceedings of the 18th IEEE international conference on network protocols (ICNP), Kyoto, Japan, 5–8 October 2010, pp.233–242. New York: IEEE.

12.

Sorour

Valaee

. Minimum broadcast decoding delay for generalized instantly decodable network coding. In: Proceedings of the 2010 IEEE global telecommunications conference (GLOBECOM 2010), Miami, FL, 6–10 December 2010, pp.1–5. New York: IEEE.

13.

Nandan

Das

Pau

. Co-operative downloading in vehicular ad-hoc wireless networks. In: Proceedings of the second annual conference on wireless on-demand network systems and services (WONS 2005), St. Moritz, 19–21 January 2005, pp.32–41. New York: IEEE.

14.

Nandan

Tewari

Das

. Adtorrent: delivering location cognizant advertisements to car networks. In: Proceedings of the 3rd international conference on wireless on demand network systems and services (WONS 2006), Les Menuires, 18–20 January 2006, pp.203–212. New York: IEEE.

15.

Ren

Chen

Kuo

. Differential successive relaying scheme for fast and reliable data delivery in vehicular ad hoc networks. IET Commun 2015; 9(8): 1088–1095.

16.

Bradai

Ahmed

. Reviv: selective rebroadcast mechanism for video streaming over vanet. In: Proceedings of the IEEE 79th vehicular technology conference (VTC Spring), Seoul, Korea, 18–21 May 2014, pp.1–6. IEEE.

17.

. Scalable opportunistic vanet content routing with encounter information. In: Proceedings of the 21st IEEE international conference on network protocols (ICNP), Goettingen, 7–10 October 2013, pp.1–6. New York: IEEE.

18.

Zhang

Yin

. Design and analysis of a robust broadcast scheme for vanet safety-related services. IEEE T Veh Technol 2012; 61(1): 46–61.

19.

Ahlswede

Cai

. Network information flow. IEEE T Inform Theory 2000; 46(4): 1204–1216.

20.

Yeung

Cai

. Linear network coding. IEEE T Inform Theory 2003; 49(2): 371–381.

21.

Koetter

Medard

. An algebraic approach to network coding. IEEE/ACM T Netw 2003; 11(5): 782–795.

22.

Medard

Koetter

. A random linear network coding approach to multicast. IEEE T Inform Theory 2006; 52(10): 4413–4430.

23.

Ali

Panda

Chahed

. Improving the transport performance in delay tolerant networks by random linear network coding and global acknowledgments. Ad Hoc Netw 2013; 11(8): 2567–2587.

24.

Noura

Martin

Agha

. Erss-rlnc: efficient and robust secure scheme for random linear network coding. Comput Netw 2014; 75(Pt A): 99–112.

25.

Sorour

Valaee

. On minimizing broadcast completion delay for instantly decodable network coding. In: Proceedings of the 2010 IEEE international conference on communications (ICC), Cape Town, South Africa, 23–27 May 2010, pp.1–5. New York: IEEE.

26.

Sorour

Valaee

. On densifying coding opportunities in instantly decodable network coding graphs. In: Proceedings of the 2012 IEEE international symposium on information theory (ISIT), Cambridge, MA, 1–6 July 2012, pp.2456–2460. New York: IEEE.

27.

Sorour

Douik

Valaee

. Partially blind instantly decodable network codes for lossy feedback environment. IEEE T Wirel Commun 2014; 13(9): 4871–4883.

28.

Douik

Sorour

Al-Naffouri

. A lossy graph model for delay reduction in generalized instantly decodable network coding. IEEE Wirel Commun Lett 2014; 3(3): 281–284.

29.

Aboutorab

Sadeghi

Sorour

. Enabling a tradeoff between completion time and decoding delay in instantly decodable network coded systems. IEEE T Commun 2014; 62(4): 1296–1309.

30.

Wang

Yin

. Efficient datadissemination strategy for vanets based on network coding. Comput Eng 2016; 42(5): 118–122, 129.

31.

Hua

Shan

. Cooperative multicast with moving window network coding in wireless networks. Ad Hoc Netw 2015; 25(Pt A): 213–227.

32.

Liu

Chen

Xia

. Data dissemination with network coding in two-way vehicle-to-vehicle networks. IEEE T Veh Technol 2016; 65(4): 2445–2456.

33.

Chen

. Efficient broadcasting in vanets using dynamic backbone and network coding. IEEE T Wirel Commun 2015; 14(11): 6057–6071.

34.

Khlass

Ghamri-Doudane

Gacanin

. Combining cooperative relaying and analog network coding to improve network connectivity and capacity in vehicular networks. In: Proceedings of the IEEE global telecommunications conference (GLOBECOM 2011), Houston, TX, 5–9 Dec 2011, pp.1–5. New York: IEEE.

35.

Mak

Laberteaux

Sengupta

. Multichannel medium access control for dedicated short-range communications. IEEE T Veh Technol 2009; 58(1): 349–366.

36.

Korkmaz

Ekici

Ozguner

. Black-burst-based multihop broadcast protocols for vehicular networks. IEEE T Veh Technol 2007; 56(5): 3159–3167.

37.

Lalos

Antonopoulos

Kartsakli

. RLNC-aided cooperative compressed sensing for energy efficient vital signal telemonitoring. IEEE T Wirel Commun 2015; 14(7): 3685–3699.

38.

Mahajan

Potnis

Gopalan

. Urban mobility models for vanets. In: Proceedings of the 2nd workshop on next generation wireless networks, 2006.