论文部分内容阅读
Providing efficient packet delivery in vehicular ad hoc networks （VANETs） is particularly challenging due to the vehicle movement and lossy wireless channels. A data packet can be lost at a forwarding node even when a proper node is selected as the forwarding node. In this paper， we propose a loss?tolerant scheme for unicast routing protocols in VANETs. The proposed scheme employs multiple forwarding nodes to improve the packet reception ratio at the forwarding nodes. The scheme uses network coding to reduce the number of required transmissions， resulting in a significant improvement in end?to?end packet delivery ratio with low message overhead. The effectiveness of the proposed scheme is evaluated by using both theoretical analysis and computer simulations.
vehicular ad hoc networks； routing protocol； network coding； cooperative forwarding scheme
1 Introduction
Vehicular ad hoc networks （VANETs） have been attracting interest in recent years for their potential role in intelligent transport systems. Due to node movement and the lossy wireless channels， providing efficient multi?hop communication between a source node and a destination node is a well?known challenging problem. In order to provide an efficient communication， the following issues should be considered： 1） the selection of an efficient multi?hop route， 2） providing reliable transmission to the next forwarding node. Many protocols have been proposed to handle the first issue [1]-[8]. However， the second issue has not been discussed seriously. In this paper， we focus on the problem of how to provide efficient packet delivery to the selected forwarding node.
Since vehicle movement could directly affect the performance of data transmission， many protocols have been proposed to take into account vehicle mobility in the forwarding node selection. Shafiee and Leung [1] have proposed a protocol which takes the connectivity of routes into consideration for its route selection logic to maximize the chance of packet reception. Yang et al. [2] have proposed an approach which takes into account vehicle densities and traffic light periods to estimate the probability of network connectivity and data delivery ratio for transmitting packets. Goonewardene et al. [3] have proposed a clustering scheme named robust mobility adaptive clustering （RMAC） to strategically partition the network into smaller segments. RMAC selects optimal cluster heads by considering vehicle speed， locations and direction of travel. In our previous work， we have proposed QLAODV [4]， an extension of Ad Hoc On?Demand Distance Vector （AODV） Protocol [5]. QLAODV learns the best route by using a Q?learning algorithm and dynamically switches to a new route before the breakage of the current route. By taking account of vehicle movement and available channel bandwidth in the route selection， QLAODV can attain a high packet delivery ratio. There also have been some protocols [6]， [7] utilizing position information for the route selection. In a lossy environment， a packet can be lost at a forwarding node， resulting in the failure of packet delivery. The easiest way to recover from the packet loss is retransmitting the packet [8]. However， the retransmission increases the end?to?end delay， and also affects upper layer protocol （such as TCP） behaviors. Another alternative is to use multi?path routing [9]. Although the multi?path routing approach can improve the packet delivery ratio， it also increases the message overhead due to the maintenance of the redundant paths， resulting in an increase of MAC layer contention time in the neighborhood. Another approach utilizes an auxiliary node to transmit a packet when a packet loss occurs at the forwarding node [10]. However， the message overhead is large when the packet loss ratio is high.
In this paper， we propose a cooperative forwarding scheme which can be used for unicast routing protocols. The scheme uses linear network coding [11] to improve the packet forwarding ratio without increasing the message overhead. Network coding can utilize the broadcast nature of the wireless channel and therefore it has attracted much attention recently. There have been many protocols applying the ideas from network coding [10]-[15].
Lee et al. [12] have proposed a network coding?based file swarming protocol for VANETs. There have been some protocols utilizing network coding for content distribution in VANETs [13]， [14]. Ye et al. [15] have proposed a direct peer?to?peer data sharing scheme based on network coding. Hassanabadi and Valaee [16] have employed a random network coding approach to provide reliability for safety messages. Wang et al. [17] have considered seamless information spread in joint vehicle to infrastructure （V2I） and vehicle to vehicle （V2V） communication networks using a network coding?based technique. However， these previous works do not consider the issue of how to improve the reception reliability in a unicast protocol.
The proposed scheme employs a cooperative forwarding approach with multiple forwarder selection based on network coding. The scheme uses a slave forwarding node for each master forwarding node to improve the packet forwarding probability. Benefited from the cooperation between the master forwarding node and slave forwarding node， the proposed scheme is resistant to packet losses without increasing the total number of transmissions. The proposed scheme can be applied in any unicast routing protocol. We apply the scheme to AODV， QLAODV， and Optimized Link State Routing （OLSR） Protocol [18]， and evaluate the performance of the proposed scheme using both theoretical analysis and network simulations. The remainder of the paper is organized as follows. In section 2， we give a detailed description of the proposed scheme. In section 3， we give a theoretical analysis of the proposed scheme. Next， we present simulation results in section 4. Finally， we present our conclusions in Section 5.
2 Proposed Scheme
2.1 Design Overview
The aim of this approach is not to provide a completely new routing protocol. In contrast， we propose a scheme which can be incorporated into routing protocols. The proposed scheme is a general solution which does not assume any specific VANET scenario. In the proposed scheme， the data packets are transmitted in pairs. The source node encodes two consecutive packets （using linear network coding） to get two encoded packets and transmits the encoded packets. By using network coding， the proposed scheme can improve the packet delivery ratio without increasing message overhead. Without loss of generality， we use network coding only for the packets that belong to the same flow （since different flows could use different forwarding nodes， the problem would be more complicated）.
2.2 Selection of and Routes for Slave Forwarding Nodes
In typical routing protocols， each sender node specifies a forwarding node （next hop） for data transmissions. The proposed scheme specifies a slave forwarding node for each master forwarding node （the forwarding node specified by the corresponding routing protocol） to improve the packet reception probability. The slave node is selected by the master node. The selection of the slave node could have a significant impact on the packet forwarding probability. In the proposed protocol， the master node selects the most stable and nearest neighbor to be its slave node. For the slave node selection， a vehicle driving in the same direction is preferred. Since the distance and driving directions are taken into account for the slave node selection， the scheme is scalable with the size of road （including the number of lanes）. We assume each node transmits hello messages periodically （1 packet per second）. Each node knows its position information and attaches the position information and velocity information to the hello messages. Stability is estimated by calculating the hello message reception ratio. In the case where the position information is not available， each master node selects its slave node by only considering the hello message reception ratio. More specifically， each vehicle selects the neighbor node which has the highest hello message reception ratio. If multiple nodes have the same ratio， the inter?vehicle distance and driving directions are considered. Note that the slave node is recalculated for each pair of original packets. In a reactive routing protocol such as AODV， the slave node address is attached with the route reply messages. In a proactive routing protocol， the slave node is attached to the periodical messages which are used for the route table update. In this way， the sender node knows the master forwarding node and the slave forwarding node. The sender node then specifies the master node and slave node for the data forwarding. The slave forwarding node overhears the messages which are used for route table updates （route reply in AODV） in order to know the next hop nodes for the corresponding traffic flows. If a packet loss occurs at the master node ， the slave node forwards the packet on behalf of the master node.
This paper does not address the master forwarding node selection problem. The master forwarding nodes can be determined by any routing protocol. The proposed scheme does not change the basic forwarding procedure of the selected routing protocol. Instead， the proposed scheme improves the packet reception probability of the specified （master） forwarding nodes. Therefore， the proposed scheme is able to provide multi?hop packet delivery based on the route selected by the corresponding routing protocol.
2.3 Packet Encoding at the Source Node and Forwarding
Nodes
The proposed scheme uses linear network coding [11] with fixed coding vectors. The coding coefficients are selected from
[C=c1c2c3c4=1 11 22 33 5] （1）
Therefore， when the native packets are a and b， the possible encoded packets are
[Y=y1y2y3y4=1 11 22 33 5ab=a+ba+2b2a+3b3a+5b]. （2）
Since the number of packets for each generation is 2， any two coding vectors of C = （c1， c2， c3， c4）T could be used for encoding the packets. The source node encodes the packets using any two coding vectors. We can transform from any two encoded packets to other two encoded packets. For example， we can get [y3， y4] from [y1， y2]. This is very useful for improving the packet forwarding ratio by cooperation among the master forwarder and slave forwarder （because each node can decode the packets as long as the node receives any two packets）.
In order to make the decoding at the receiver node possible， each sender node has to add the generation information （unique number for each generation） and the coefficient information to each encoded packet. After receiving a packet， the receiver can know the linear combination used by the sender from the coefficient information， and know the generation information to which the current packet belongs to. In the random network coding， the sender node at least has to add the number for the generation information， the coefficient for a and the coefficient for b. In the proposed scheme， by using the fixed coefficients， we only need to transmit the generation information and the index of the combination used （the index is from 0 to 3 in our case； a+b has the index of 0， and so on）. Therefore， the proposed scheme can reduce the size of coefficient overhead because the scheme only requires two bits to carry the coefficient information （there are only four combinations as shown in （2））. In the proposed scheme， the coefficients are selected from GF（23）. Note that there are many possible combinations which can satisfy the requirement of the proposed scheme （the only requirement is that the four combinations are independent of each other）. Therefore， （2） is not the only option. 2.4 Network Coding Assisted Cooperative Forwarding
Scheme
In the proposed scheme， the source node specifies a slave forwarder for a master forwarding node. The source node processes network coding based on packets in pairs. The source node uses the network coding algorithm to encode two consecutive packets， and transmits the encoded packets. Upon receiving a packet， the master forwarding node transmits the packet immediately. In contrast， the slave forwarding node may re?encode the received packet depending on the reception status. As shown in Algorithm 1， upon receiving an encoded packet， the slave node first checks whether the received packet is the first packet of the corresponding generation or not by using the generation information attached in the packet. If the packet is the first one， the node waits for a short period of time （T） to check whether it could receive the second encoded packet or not （T is set to 50 ms based on our experience [19]）. If the master node has transmitted two packets （for the same generation） already， the slave node does nothing. If the slave node has received only one packet and the master node has not transmitted this packet before， the node transmits the packet immediately. If the node received two packets， the node transmits a new encoded packet （with a different linear combination）. We use the next combination （in terms of combination index） of the combination with higher index （between two packets in the same generation）. For example， if the received packets are a+b and a+2b， the next combination is 2a+3b； if the received packets are 2a+3b and 3a+5b， the next combination is a+b. Note that， the proposed scheme works on the top of IP layer. This means that the procedure defined in Algorithm 1 is independent of MAC layer specifically IEEE 802.11p [20].
As shown in Fig. 1， the source node Src1 encodes the packets [a， b] to get the linear combinations [a+b， a+2b]. The source node specifies the master forwarding node M1 and slave forwarding node S1. The nodes M1 and S1 receive the packet a+b and a+2b respectively. After that， M1 and S1 forward the packets they received. In this way， the nodes M1 and S1 can successfully receive two encoded packets （receive from each other one packet）. Although M1 is not the final destination node， it is important to receive the packets in order to retransmit the packets when needed.
When the slave node S2 receives both two encoded packets， the node uses a linear transformation of the two encoded packets to get 2a+3b and transmits 2a+3b. This is to improve the packet reception probability at the next hop forwarders. For example， a node can retrieve the original packets as far as any two of {a+b， a+2b， 2a+3b， 3a+5b} are received. As shown in Fig. 1， upon receiving 2a+3b， node M3 can decode the packets as far as the node receives a+b. If the packet transmitted at node S2 was a+b， node M3 would fail to decode the packets even if the node received a+b from node M2. The forwarding node waits for a short period of time （T） to check whether the master node transmitted the packet or not. For example， node S3 does not forward any packets because node M3 already has forwarded two packets. 2.5 Advantage of the Proposed Scheme
The advantage of the proposed scheme over the existing approaches comes from two main elements： the use of slave forwarding node and the use of network coding.
By overhearing the transmissions happening at the master forwarding node， the slave forwarding node can forward a packet when a packet loss occurs at the master node. This is more efficient than retransmitting the packet at the upstream sender node.
Now we explain why we use network coding. As shown in Fig. 2， the master forwarding node （M） does not receive the first packet （a for the left figure； a+b for the right figure） while the slave forwarding node （S） receives both packets. Let’s assume node S fails to detect the transmission from node M. This can happen frequently because of the following two reasons： 1） node M has failed to get the transmission opportunity （MAC layer） （although node M is supposed to transmit before node S， the transmission order can be changed due to MAC layer contention， 2） node M has transmitted the packet， but the node S has failed to detect this transmission due to overhearing failure （but it is possible to detect this after node T1 forwarding the packet）. Without network coding， node S sends packet a first. After node S knows that node M does not receive packet b， it will send packet b. This requires 3 transmissions to forward the packet a and b to the node T1. However， with network coding， we can do it by using only 2 transmissions. As shown in Fig. 2 （right）， node Src1 transmits 2 encoded packets a+b and a+2b. Upon receiving the packets， node S transmits 2a+3b which is a linear combination of a+b and a+2b. Node T1 can successfully retrieve the original packets （a and b） after the reception of a+b and 2a+3b. Therefore， the proposed scheme can significantly reduce the number of transmissions.
In this paper， we use deterministic coefficients. Note that the random network coding cannot achieve this result. In the random network coding， the coefficients are chosen independently and randomly. A node can decode the original packets if the node receives 2 encoded packets from the same generation （generated at the same node）. However， when the node receives 1 packet from the master node and 1 packet from the slave node， the node may fail to decode the packet. In the proposed scheme， when both packets of the same generation are received by the slave forwarding node， the node re?encodes the received packets and then transmits. Since the master node does not re?encode the packets， the encoded packet sent by the master node and the encoded packet sent by the slave node are linearly independent. This ensures a node can decode the original packets upon its reception of two encoded packets regardless of the upstream sender node （whether the master forwarding node or slave forwarding node）. This can significantly increase the packet forwarding probability. Since the proposed scheme transmits 2 encoded packets for a pair of original packets， the total number of transmissions remains the same. By using this network coding assisted cooperative forwarding scheme， the proposed scheme can improve packet forwarding ratio without extra transmissions. 2.6 Important Considerations
The proposed scheme sends encoded data packets in pairs. This incurs a concern of the possible delay to the first packet. However， in real?world scenarios， one packet is always impossible to contain all necessary information that should be delivered. This means that there are always more than two packets consecutively arriving in the send queue. This means that the delay between two consecutive packets is negligible. Moreover， by using the proposed scheme， the forwarding probability at forwarding nodes can be improved and therefore the number of route breaks decreases. As a result， many unnecessary control messages （such as route request messages due to the frequent route discoveries） can be avoided， which reduces contention delays at the MAC layer.
In the proposed scheme， each master forwarding node selects the most stable and nearest neighbor as the corresponding slave forwarding node. The packet loss probability at the slave node can be different from the master node. However， the proposed scheme can considerably improve the packet forwarding probability even when the packet loss probability at the slave node is higher （see section 3）. The proposed scheme does not increase the congestion level at the slave node and the neighborhood because the number of transmissions remains the same. In vehicular networks， road width is always much smaller than the transmission range. As a result， the neighbors of the master node （including the slave node） experience similar MAC layer contentions regardless of the sender （is whether the master node or not）.
3 Theoretical Analysis
For a fair comparison， we only consider protocols in which only one next hop node is selected for a particular route （in the proposed scheme， the average number of forwarding nodes for each packet is the same）. We assume independent packet losses for different packets. In vehicular networks， the packet loss correlation could be totally different for different scenarios. For simplicity， we first analyze the performance with the assumption that the quality of the link which connects the master forwarding node and a node x is the same with the link which connects the slave forwarding node and the node x. Then， we conduct analysis for the case where the slave node experiences a different packet loss probability. A slave forwarding node can successfully overhear all packets transmitted from the master forwarding node. This assumption is reasonable because the slave forwarding node is located very near from the master forwarding node. 3.1 Successful Forwarding Probability
We first analyze the case of typical unicast routing approach. The next hop node is specified by the upstream sender node. If the packet loss probability of the link （which connects the sender node and the next forwarding node） is [pl] （for simplicity， we assume this probability is constant）， the probability that both data packets （two consecutive data packets） being successfully received by the next hop forwarding node is [FP=（1-pl）2].
In the proposed scheme， the slave forwarding node forwards a packet when the master forwarding node fails to receive the packet. A node can retrieve the corresponding native packets when the node receives two linearly independent encoded packets. We can easily know that two encoded packets generated at the same node are linearly independent. As mentioned before， the encoded packet sent by the master node and the encoded packet sent by the slave node are also linearly independent.
Therefore， for the proposed scheme， the forwarding only fails when 1） the total number of received packets at two forwarding nodes （the master forwarding node and the slave forwarding node） is smaller than 2； or 2） both forwarding nodes receive only one packet and the packet received at two forwarding nodes are the same. Therefore， the successful forwarding probability is
When [pl] is 0.1， this probability is 0.9801. However， without the proposed scheme we get only 0.81. This shows the network coding assisted cooperative forwarding scheme can significantly improve the successful forwarding probability.
3.2 Number of Transmissions for Each Hop
Here we analyze the distribution of possible numbers of transmissions for the two consecutive packets. We assume the packet is retransmitted until the packet is successfully received by the next hop forwarding node（s）. For the original unicast routing approach， each packet is transmitted to the next hop node. Therefore， for two consecutive packets， we can calculate the probability that the number of transmissions is equal or lower than K as
The number of transmissions is equal or lower than 2 （K=2） means that both packets are successfully delivered to the next hop node. Therefore， the probability that the number of transmissions is equal or lower than 2 is [（1-pl）2]. When K is 3， we can first calculate the probability that the number of transmissions is larger than 3 （[PNT>3]）. The number of transmissions is larger than 3 only when 1） first 3 packets are all lost； or 2） the only one packet of the first 3 packets is received. Based on this we can calculate the probability that the number of transmissions is equal or lower than 3 as[ 1- p3l- 311-plp2l]. Similarly， we can calculate the probability for different values of K as in （4）. For the proposed scheme， we can calculate the probability that the number of transmissions is equal or lower than K as
Based on （4） and （5）， we draw the cumulative distribution functions for various numbers of possible transmissions in Fig. 3. In the figure， the line “Proposed （[pl]=0.1）” shows the cumulative probability for the proposed approach when [pl] （the packet loss probability of the link） is 0.1. When [pl] is 0.3， for the proposed scheme， the probability that the number of transmissions is equal or lower than 3 is 0.981127. This means that the proposed approach can deliver almost all packets with 3 transmissions. However， for the original approach， in order to provide 0.97% reception probability， the number of transmissions should be at least 5. We can observe that the expected number of transmissions for the proposed scheme is much smaller than the original method.
3.3 Analysis for Different Packet Loss Probabilities at the
Slave Node
Now we analyze the performance of the proposed scheme in the case where the master node and slave node have different packet loss probabilities. We use [pl] and [pl ]to denote the packet loss probability for the master node and slave node respectively. We can calculate the successful forwarding probability by extending （3） as
The average number of transmissions per hop by extending （5） can be calculated as
Based on （7）， Fig. 4 shows the cumulative distribution function for different packet loss probabilities at the slave node. The proposed scheme can significantly reduce the number of transmissions even when the packet loss probability at the slave node is higher than the master node.
4 Simulation Results
We used network simulator ns?2 （version 2.34） [21] to conduct simulations in Street scenario [22]， [23]. Simulation parameters are shown in Table 1. Simulation parameters were defined according to IEEE 802.11p [20]. We simulated IEEE WAVE multi?channel operation [24] by dividing each 100 ms channel time into two equal parts， a CCH interval and an SCH interval. All traffics generated by the simulation were transmitted in SCH intervals. We used the tiger line map file [22] and real street map based model [23] to generate realistic vehicle movement scenarios. We used a 2500 m × 2500 m square area in Midtown Manhattan in New York City （Fig. 5）. The Nakagami model was used to simulate the channel fading. The parameters of the Nakagami model are shown in Table 2. We used these parameter values because they model a realistic wireless channel of vehicular ad hoc networks [25]. Other simulation parameters were the default settings of ns?2.34. The proposed scheme was implemented with AODV [5] （we call AODV with the proposed scheme as AODV?proposed）， QLAODV [4] （QLAODV?proposed） and OLSR [18] （OLSR?proposed）. QLAODV takes into account the vehicle movement for the route selection. OLSR is a well?known proactive routing protocol. The proposed scheme was also compared with AODV?XOR （AODV with traditional network coding）， QLAODV?XOR （QLAODV with traditional network coding） and OLSR?XOR （OLSR with traditional network coding）. Here， we use “traditional network coding” to denote the approach in which XOR coding is used to forward packets for bi?directional unicast flows [26]. In the simulation， traffic flows were selected randomly. For AODV?proposed， QLAODV?proposed and OLSR?proposed， each slave node was selected by taking into account the hello reception ratios at the corresponding master node. The hello reception ratio was updated for each hello interval based on the number of received hello messages in the last 10 seconds. In order to clearly show the performance of the proposed scheme， we use the same access category Access Category Best Effort （AC_BE ） for all packets （since the proposed scheme is an enhancement to the routing protocol， the MAC layer issues （packet prioritization etc.） are outside the scope of this paper）. In the following simulation results， the error bars indicate the 95% confidence intervals.
4.1 Packet Delivery Ratio
Fig. 6 shows the packet delivery ratio for various numbers of nodes in Street scenario. From the results， we observe that the proposed scheme significantly improves the packet delivery ratio of all protocols （AODV， QLAODV， and OLSR）. By incorporating with QLAODV， the proposed scheme can provide the highest packet delivery ratio. These results show that the proposed scheme is necessary in a lossy environment. This is because in many cases， it is very difficult to select a very reliable next hop node. Traditional network coding?based approach is unable to improve AODV and QLAODV notably. This is because different traffics could use different forwarding nodes， resulting in a very small chance of network coding at the forwarding nodes. OLSR intends to use multipoint relay （MPR） nodes for routing， which improves the chance of network coding. However， the improvement is still very limited because different nodes could select different MPRs. The proposed scheme can significantly improve the packet delivery ratio in various node densities. This is because the proposed scheme does not incur extra overhead as compared with the original routing protocol. 4.2 EndtoEnd Delay
Fig. 7 shows the end?to?end delay. AODV?proposed and QLAODV?proposed show small improvements over AODV and QLAODV respectively. The proposed scheme can reduce the number of route discoveries （due to route errors） by providing a higher reliability at the forwarding nodes， which results in a lower channel contention time at each node. QLAODV and QLAODV?proposed show a low end?to?end delay due to the dynamic route change mechanism which uses shorter routes for data transmissions. Note that the delay of OLSR is dependent on the number of nodes which determines the overhead of control messages. Since the overhead of the proposed scheme does not increase with the node density， the proposed scheme can reduce the end?to?end delay of AODV and QLAODV in various node densities.
4.3 Normalized Control Overhead
A comparison of the normalized control overhead is shown in Fig. 8. The normalized control overhead is defined as the size （in bytes） of control packets generated divided by the size of data packets that arrive at receivers. We observe that the proposed scheme can reduce the normalized control overhead significantly by improving packet delivery ratio （for all protocols） and reducing the number of route discoveries （for AODV and QLAODV）. AODV?proposed shows a significantly lower overhead than AODV. This shows that the proposed scheme is efficient especially when the packet loss probability at the forwarding node is high.
5 Conclusions
We proposed a network coding?based cooperative forwarding scheme for unicast routing protocols in vehicular ad hoc networks. The proposed scheme can be easily applied to typical routing protocols. The proposed scheme can significantly improve the packet reception ratio at the forwarding nodes by employing network coding to utilize the broadcast nature of wireless communications. The theoretical analysis and simulation results showed the proposed scheme can considerably improve the packet delivery ratio without increasing message overhead.
References
[1] K. Shafiee and V. C.M. Leung， “Connectivity?aware minimum?delay geographic routing with vehicle tracking in VANETs，” Ad Hoc Networks， vol. 9， no. 2， pp. 131-141， Mar. 2011. doi： 10.1016/j.adhoc.2010.06.003.
[2] Q. Yang， A. Lim， S. Li， J. Fang， and P. Agrawal， “ACAR： adaptive connectivity aware routing for vehicular ad hoc networks in city scenarios，” Mobile Networks and Applications， vol. 15， no. 1， pp. 36-60， Feb. 2010. doi： 10.1007/s11036?009?0169?2. [3] R. T. Goonewardene， F. H. Ali， and E. Stipidis， “Robust mobility adaptive clustering scheme with support for geographic routing for vehicular ad hoc networks，” IET Intelligent Transport Systems， vol.3， no.2， pp.148-158， 2009.
[4] C. Wu， K. Kumekawa， and T. Kato， “Distributed reinforcement learning approach for vehicular ad hoc networks，” IEICE Transactions on Communications， vol.E93?B， no.6， pp.1431-1442， 2010. doi： 10.1587/transcom.E93.B.1431.
[5] Ad hoc On?Demand Distance Vector （AODV） Routing， RFC 3561， Jul. 2003.
[6] R. Jiang， Y. Zhu， T. He， Y. Liu， and L.M. Ni， “Exploiting trajectory?based coverage for geocast in vehicular networks，” IEEE Transactions on Parallel and Distributed Systems， vol. 25， no. 12， pp.3177-3189， 2014. doi： 10.1109/TPDS.2013.2295808.
[7] C.?M. Huang and S.?Y. Lin， “Timer?based greedy forwarding algorithm in vehicular ad hoc networks，” IET Intelligent Transport Systems， vol.8， no.4， pp.333-344， 2014.
[8] J. Cheng， J. Cheng， M. Zhou， et al.， “Routing in internet of vehicles： a review，” IEEE Transactions on Intelligent Transport Systems.， vol.16， no.5， pp. 2339-2352， 2015.
[9] X. Huang and Y. Fang， “Performance study of node?disjoint multipath routing in vehicular ad hoc networks，” IEEE Transactions on Vehicular Technology.， vol.58， no.4， pp.1942-1950， 2009. doi： 10.1109/TVT.2008.2008094.
[10] C. Wu， S. Ohzahata， T. Kato and Y. Fang， “A low latency path diversity mechanism for sender?oriented broadcast protocols in VANETs，” Ad Hoc Networks， vol.11， no.7， pp. 2059-2068， 2013. doi：10.1016/j.adhoc.2012.02.007.
[11] S. Li， R. Yeung， and N. Cai， “Linear Network Coding，” IEEE Transactions on Information Theory， vol. 49， no. 2， pp. 371-381， 2003. doi： 10.1109/TIT.2002.807285.
[12] U. Lee， J.?S. Park， J. Yeh， G. Pau， and M. Gerla， “CodeTorrent： content distribution using network coding in VANET，” in Proc. ACM MobiShare， Los Angeles， USA， 2006， pp.1-5. DOI： 10.1145/1161252.1161254.
[13] M. Li， Z. Yang， and W. Lou， “CodeOn： cooperative popular content distribution for vehicular networks using symbol level network coding，” IEEE Journal on Selected Areas in Communications， vol. 29， No. 1， pp. 223-235， 2011. doi：10.1109/JSAC.2011.110121.
[14] T.?X. Yu， C.?W. Yi， and S.?L. Tsao， “Rank?based network coding for content distribution in vehicular networks，” IEEE Wireless Communication Letters， vol. 1， no. 4， pp. 368-371， 2012.
[15] F. Ye， S. Roy， and H. Wang， “Efficient data dissemination in vehicular ad hoc networks，” Journal of Systems and Software， vol. 30， no. 4， pp. 769-779， 2012. doi：10.1016/j.jss.2016.04.005. [16] B. Hassanabadi and S. Valaee， “Reliable periodic safety message broadcasting in VANETs using network coding，” IEEE Transactions on Wireless Communications， vol. 13， no. 3， pp. 1284-1297， 2014. doi： 10.1109/TWC.2014.010214. 122008.
[17] Q. Wang， P. Fan， and K.B. Letaief， “On the joint V2I and V2V scheduling for cooperative VANETs with network coding，” IEEE Transactions on Vehicular Technology， vol.61， no.1， pp.62-73， 2012. doi： 10.1109/TVT.2011.2167249.
[18] P. Jacquet， P. Muhlethaler， T. Clausen， et al.， “Optimized link state routing protocol for Ad Hoc Networks，” in Proc. IEEE International Multitopic Conference， Pakistan， 2001， pp.62-68.
[19] C. Wu， S. Ohzahata， and T. Kato， “VANET broadcast protocol based on fuzzy logic and lightweight retransmission mechanism，” IEICE Transactions on Communications， vol. E95?B， no.2， pp.415-425， Feb. 2012. doi： 10.1587/transcom.E95.B.415.
[20] IEEE Std 802.11 Amendment 7： Wireless Access in Vehicular Environments， 802.11p ?2010， 2010.
[21] ISI. （2015， Jun. 25）. The Network Simulator ? ns?2 [Online]. Available： http：//www.isi.edu/nsnam/ns
[22] U.S. Census Bureau. （2012， Jun. 23）. TIGER/Line [Online]. Available： http：//www.census.gov/geo/www/tiger
[23] A.K. Saha， and D.B. Johnson. “Modeling mobility for vehicular ad hoc networks”， in Proc. First ACM Workshop on Vehicular Ad Hoc Networks， Philadelphia， USA， Oct. 2004， pp.91-92. doi： 10.1145/1023875.1023892.
[24] IEEE Standard for Wireless Access in Vehicular Environments （WAVE）?Multi?channel Operation， IEEE Std 1609.4?2010， Sept. 2010.
[25] A. Khan， S. Sadhu， and M. Yeleswarapu， “A comparative analysis of DSRC and 802.11 over vehicular ad hoc networks，” Project Report， University of Californai， Santa Barbara， USA， pp.1-8， 2009.
[26] Z. Xiang and X. Fang， “An improved AODV routing protocol with network coding in wireless ad hoc network，” in Proc. IET Conference on Wireless， Mobile and Sensor Networks， Shanghai， China， 2007， pp.84-87.
Manuscript received： 2015?12?25
vehicular ad hoc networks； routing protocol； network coding； cooperative forwarding scheme
1 Introduction
Vehicular ad hoc networks （VANETs） have been attracting interest in recent years for their potential role in intelligent transport systems. Due to node movement and the lossy wireless channels， providing efficient multi?hop communication between a source node and a destination node is a well?known challenging problem. In order to provide an efficient communication， the following issues should be considered： 1） the selection of an efficient multi?hop route， 2） providing reliable transmission to the next forwarding node. Many protocols have been proposed to handle the first issue [1]-[8]. However， the second issue has not been discussed seriously. In this paper， we focus on the problem of how to provide efficient packet delivery to the selected forwarding node.
Since vehicle movement could directly affect the performance of data transmission， many protocols have been proposed to take into account vehicle mobility in the forwarding node selection. Shafiee and Leung [1] have proposed a protocol which takes the connectivity of routes into consideration for its route selection logic to maximize the chance of packet reception. Yang et al. [2] have proposed an approach which takes into account vehicle densities and traffic light periods to estimate the probability of network connectivity and data delivery ratio for transmitting packets. Goonewardene et al. [3] have proposed a clustering scheme named robust mobility adaptive clustering （RMAC） to strategically partition the network into smaller segments. RMAC selects optimal cluster heads by considering vehicle speed， locations and direction of travel. In our previous work， we have proposed QLAODV [4]， an extension of Ad Hoc On?Demand Distance Vector （AODV） Protocol [5]. QLAODV learns the best route by using a Q?learning algorithm and dynamically switches to a new route before the breakage of the current route. By taking account of vehicle movement and available channel bandwidth in the route selection， QLAODV can attain a high packet delivery ratio. There also have been some protocols [6]， [7] utilizing position information for the route selection. In a lossy environment， a packet can be lost at a forwarding node， resulting in the failure of packet delivery. The easiest way to recover from the packet loss is retransmitting the packet [8]. However， the retransmission increases the end?to?end delay， and also affects upper layer protocol （such as TCP） behaviors. Another alternative is to use multi?path routing [9]. Although the multi?path routing approach can improve the packet delivery ratio， it also increases the message overhead due to the maintenance of the redundant paths， resulting in an increase of MAC layer contention time in the neighborhood. Another approach utilizes an auxiliary node to transmit a packet when a packet loss occurs at the forwarding node [10]. However， the message overhead is large when the packet loss ratio is high.
In this paper， we propose a cooperative forwarding scheme which can be used for unicast routing protocols. The scheme uses linear network coding [11] to improve the packet forwarding ratio without increasing the message overhead. Network coding can utilize the broadcast nature of the wireless channel and therefore it has attracted much attention recently. There have been many protocols applying the ideas from network coding [10]-[15].
Lee et al. [12] have proposed a network coding?based file swarming protocol for VANETs. There have been some protocols utilizing network coding for content distribution in VANETs [13]， [14]. Ye et al. [15] have proposed a direct peer?to?peer data sharing scheme based on network coding. Hassanabadi and Valaee [16] have employed a random network coding approach to provide reliability for safety messages. Wang et al. [17] have considered seamless information spread in joint vehicle to infrastructure （V2I） and vehicle to vehicle （V2V） communication networks using a network coding?based technique. However， these previous works do not consider the issue of how to improve the reception reliability in a unicast protocol.
The proposed scheme employs a cooperative forwarding approach with multiple forwarder selection based on network coding. The scheme uses a slave forwarding node for each master forwarding node to improve the packet forwarding probability. Benefited from the cooperation between the master forwarding node and slave forwarding node， the proposed scheme is resistant to packet losses without increasing the total number of transmissions. The proposed scheme can be applied in any unicast routing protocol. We apply the scheme to AODV， QLAODV， and Optimized Link State Routing （OLSR） Protocol [18]， and evaluate the performance of the proposed scheme using both theoretical analysis and network simulations. The remainder of the paper is organized as follows. In section 2， we give a detailed description of the proposed scheme. In section 3， we give a theoretical analysis of the proposed scheme. Next， we present simulation results in section 4. Finally， we present our conclusions in Section 5.
2 Proposed Scheme
2.1 Design Overview
The aim of this approach is not to provide a completely new routing protocol. In contrast， we propose a scheme which can be incorporated into routing protocols. The proposed scheme is a general solution which does not assume any specific VANET scenario. In the proposed scheme， the data packets are transmitted in pairs. The source node encodes two consecutive packets （using linear network coding） to get two encoded packets and transmits the encoded packets. By using network coding， the proposed scheme can improve the packet delivery ratio without increasing message overhead. Without loss of generality， we use network coding only for the packets that belong to the same flow （since different flows could use different forwarding nodes， the problem would be more complicated）.
2.2 Selection of and Routes for Slave Forwarding Nodes
In typical routing protocols， each sender node specifies a forwarding node （next hop） for data transmissions. The proposed scheme specifies a slave forwarding node for each master forwarding node （the forwarding node specified by the corresponding routing protocol） to improve the packet reception probability. The slave node is selected by the master node. The selection of the slave node could have a significant impact on the packet forwarding probability. In the proposed protocol， the master node selects the most stable and nearest neighbor to be its slave node. For the slave node selection， a vehicle driving in the same direction is preferred. Since the distance and driving directions are taken into account for the slave node selection， the scheme is scalable with the size of road （including the number of lanes）. We assume each node transmits hello messages periodically （1 packet per second）. Each node knows its position information and attaches the position information and velocity information to the hello messages. Stability is estimated by calculating the hello message reception ratio. In the case where the position information is not available， each master node selects its slave node by only considering the hello message reception ratio. More specifically， each vehicle selects the neighbor node which has the highest hello message reception ratio. If multiple nodes have the same ratio， the inter?vehicle distance and driving directions are considered. Note that the slave node is recalculated for each pair of original packets. In a reactive routing protocol such as AODV， the slave node address is attached with the route reply messages. In a proactive routing protocol， the slave node is attached to the periodical messages which are used for the route table update. In this way， the sender node knows the master forwarding node and the slave forwarding node. The sender node then specifies the master node and slave node for the data forwarding. The slave forwarding node overhears the messages which are used for route table updates （route reply in AODV） in order to know the next hop nodes for the corresponding traffic flows. If a packet loss occurs at the master node ， the slave node forwards the packet on behalf of the master node.
This paper does not address the master forwarding node selection problem. The master forwarding nodes can be determined by any routing protocol. The proposed scheme does not change the basic forwarding procedure of the selected routing protocol. Instead， the proposed scheme improves the packet reception probability of the specified （master） forwarding nodes. Therefore， the proposed scheme is able to provide multi?hop packet delivery based on the route selected by the corresponding routing protocol.
2.3 Packet Encoding at the Source Node and Forwarding
Nodes
The proposed scheme uses linear network coding [11] with fixed coding vectors. The coding coefficients are selected from
[C=c1c2c3c4=1 11 22 33 5] （1）
Therefore， when the native packets are a and b， the possible encoded packets are
[Y=y1y2y3y4=1 11 22 33 5ab=a+ba+2b2a+3b3a+5b]. （2）
Since the number of packets for each generation is 2， any two coding vectors of C = （c1， c2， c3， c4）T could be used for encoding the packets. The source node encodes the packets using any two coding vectors. We can transform from any two encoded packets to other two encoded packets. For example， we can get [y3， y4] from [y1， y2]. This is very useful for improving the packet forwarding ratio by cooperation among the master forwarder and slave forwarder （because each node can decode the packets as long as the node receives any two packets）.
In order to make the decoding at the receiver node possible， each sender node has to add the generation information （unique number for each generation） and the coefficient information to each encoded packet. After receiving a packet， the receiver can know the linear combination used by the sender from the coefficient information， and know the generation information to which the current packet belongs to. In the random network coding， the sender node at least has to add the number for the generation information， the coefficient for a and the coefficient for b. In the proposed scheme， by using the fixed coefficients， we only need to transmit the generation information and the index of the combination used （the index is from 0 to 3 in our case； a+b has the index of 0， and so on）. Therefore， the proposed scheme can reduce the size of coefficient overhead because the scheme only requires two bits to carry the coefficient information （there are only four combinations as shown in （2））. In the proposed scheme， the coefficients are selected from GF（23）. Note that there are many possible combinations which can satisfy the requirement of the proposed scheme （the only requirement is that the four combinations are independent of each other）. Therefore， （2） is not the only option. 2.4 Network Coding Assisted Cooperative Forwarding
Scheme
In the proposed scheme， the source node specifies a slave forwarder for a master forwarding node. The source node processes network coding based on packets in pairs. The source node uses the network coding algorithm to encode two consecutive packets， and transmits the encoded packets. Upon receiving a packet， the master forwarding node transmits the packet immediately. In contrast， the slave forwarding node may re?encode the received packet depending on the reception status. As shown in Algorithm 1， upon receiving an encoded packet， the slave node first checks whether the received packet is the first packet of the corresponding generation or not by using the generation information attached in the packet. If the packet is the first one， the node waits for a short period of time （T） to check whether it could receive the second encoded packet or not （T is set to 50 ms based on our experience [19]）. If the master node has transmitted two packets （for the same generation） already， the slave node does nothing. If the slave node has received only one packet and the master node has not transmitted this packet before， the node transmits the packet immediately. If the node received two packets， the node transmits a new encoded packet （with a different linear combination）. We use the next combination （in terms of combination index） of the combination with higher index （between two packets in the same generation）. For example， if the received packets are a+b and a+2b， the next combination is 2a+3b； if the received packets are 2a+3b and 3a+5b， the next combination is a+b. Note that， the proposed scheme works on the top of IP layer. This means that the procedure defined in Algorithm 1 is independent of MAC layer specifically IEEE 802.11p [20].
As shown in Fig. 1， the source node Src1 encodes the packets [a， b] to get the linear combinations [a+b， a+2b]. The source node specifies the master forwarding node M1 and slave forwarding node S1. The nodes M1 and S1 receive the packet a+b and a+2b respectively. After that， M1 and S1 forward the packets they received. In this way， the nodes M1 and S1 can successfully receive two encoded packets （receive from each other one packet）. Although M1 is not the final destination node， it is important to receive the packets in order to retransmit the packets when needed.
When the slave node S2 receives both two encoded packets， the node uses a linear transformation of the two encoded packets to get 2a+3b and transmits 2a+3b. This is to improve the packet reception probability at the next hop forwarders. For example， a node can retrieve the original packets as far as any two of {a+b， a+2b， 2a+3b， 3a+5b} are received. As shown in Fig. 1， upon receiving 2a+3b， node M3 can decode the packets as far as the node receives a+b. If the packet transmitted at node S2 was a+b， node M3 would fail to decode the packets even if the node received a+b from node M2. The forwarding node waits for a short period of time （T） to check whether the master node transmitted the packet or not. For example， node S3 does not forward any packets because node M3 already has forwarded two packets. 2.5 Advantage of the Proposed Scheme
The advantage of the proposed scheme over the existing approaches comes from two main elements： the use of slave forwarding node and the use of network coding.
By overhearing the transmissions happening at the master forwarding node， the slave forwarding node can forward a packet when a packet loss occurs at the master node. This is more efficient than retransmitting the packet at the upstream sender node.
Now we explain why we use network coding. As shown in Fig. 2， the master forwarding node （M） does not receive the first packet （a for the left figure； a+b for the right figure） while the slave forwarding node （S） receives both packets. Let’s assume node S fails to detect the transmission from node M. This can happen frequently because of the following two reasons： 1） node M has failed to get the transmission opportunity （MAC layer） （although node M is supposed to transmit before node S， the transmission order can be changed due to MAC layer contention， 2） node M has transmitted the packet， but the node S has failed to detect this transmission due to overhearing failure （but it is possible to detect this after node T1 forwarding the packet）. Without network coding， node S sends packet a first. After node S knows that node M does not receive packet b， it will send packet b. This requires 3 transmissions to forward the packet a and b to the node T1. However， with network coding， we can do it by using only 2 transmissions. As shown in Fig. 2 （right）， node Src1 transmits 2 encoded packets a+b and a+2b. Upon receiving the packets， node S transmits 2a+3b which is a linear combination of a+b and a+2b. Node T1 can successfully retrieve the original packets （a and b） after the reception of a+b and 2a+3b. Therefore， the proposed scheme can significantly reduce the number of transmissions.
In this paper， we use deterministic coefficients. Note that the random network coding cannot achieve this result. In the random network coding， the coefficients are chosen independently and randomly. A node can decode the original packets if the node receives 2 encoded packets from the same generation （generated at the same node）. However， when the node receives 1 packet from the master node and 1 packet from the slave node， the node may fail to decode the packet. In the proposed scheme， when both packets of the same generation are received by the slave forwarding node， the node re?encodes the received packets and then transmits. Since the master node does not re?encode the packets， the encoded packet sent by the master node and the encoded packet sent by the slave node are linearly independent. This ensures a node can decode the original packets upon its reception of two encoded packets regardless of the upstream sender node （whether the master forwarding node or slave forwarding node）. This can significantly increase the packet forwarding probability. Since the proposed scheme transmits 2 encoded packets for a pair of original packets， the total number of transmissions remains the same. By using this network coding assisted cooperative forwarding scheme， the proposed scheme can improve packet forwarding ratio without extra transmissions. 2.6 Important Considerations
The proposed scheme sends encoded data packets in pairs. This incurs a concern of the possible delay to the first packet. However， in real?world scenarios， one packet is always impossible to contain all necessary information that should be delivered. This means that there are always more than two packets consecutively arriving in the send queue. This means that the delay between two consecutive packets is negligible. Moreover， by using the proposed scheme， the forwarding probability at forwarding nodes can be improved and therefore the number of route breaks decreases. As a result， many unnecessary control messages （such as route request messages due to the frequent route discoveries） can be avoided， which reduces contention delays at the MAC layer.
In the proposed scheme， each master forwarding node selects the most stable and nearest neighbor as the corresponding slave forwarding node. The packet loss probability at the slave node can be different from the master node. However， the proposed scheme can considerably improve the packet forwarding probability even when the packet loss probability at the slave node is higher （see section 3）. The proposed scheme does not increase the congestion level at the slave node and the neighborhood because the number of transmissions remains the same. In vehicular networks， road width is always much smaller than the transmission range. As a result， the neighbors of the master node （including the slave node） experience similar MAC layer contentions regardless of the sender （is whether the master node or not）.
3 Theoretical Analysis
For a fair comparison， we only consider protocols in which only one next hop node is selected for a particular route （in the proposed scheme， the average number of forwarding nodes for each packet is the same）. We assume independent packet losses for different packets. In vehicular networks， the packet loss correlation could be totally different for different scenarios. For simplicity， we first analyze the performance with the assumption that the quality of the link which connects the master forwarding node and a node x is the same with the link which connects the slave forwarding node and the node x. Then， we conduct analysis for the case where the slave node experiences a different packet loss probability. A slave forwarding node can successfully overhear all packets transmitted from the master forwarding node. This assumption is reasonable because the slave forwarding node is located very near from the master forwarding node. 3.1 Successful Forwarding Probability
We first analyze the case of typical unicast routing approach. The next hop node is specified by the upstream sender node. If the packet loss probability of the link （which connects the sender node and the next forwarding node） is [pl] （for simplicity， we assume this probability is constant）， the probability that both data packets （two consecutive data packets） being successfully received by the next hop forwarding node is [FP=（1-pl）2].
In the proposed scheme， the slave forwarding node forwards a packet when the master forwarding node fails to receive the packet. A node can retrieve the corresponding native packets when the node receives two linearly independent encoded packets. We can easily know that two encoded packets generated at the same node are linearly independent. As mentioned before， the encoded packet sent by the master node and the encoded packet sent by the slave node are also linearly independent.
Therefore， for the proposed scheme， the forwarding only fails when 1） the total number of received packets at two forwarding nodes （the master forwarding node and the slave forwarding node） is smaller than 2； or 2） both forwarding nodes receive only one packet and the packet received at two forwarding nodes are the same. Therefore， the successful forwarding probability is
When [pl] is 0.1， this probability is 0.9801. However， without the proposed scheme we get only 0.81. This shows the network coding assisted cooperative forwarding scheme can significantly improve the successful forwarding probability.
3.2 Number of Transmissions for Each Hop
Here we analyze the distribution of possible numbers of transmissions for the two consecutive packets. We assume the packet is retransmitted until the packet is successfully received by the next hop forwarding node（s）. For the original unicast routing approach， each packet is transmitted to the next hop node. Therefore， for two consecutive packets， we can calculate the probability that the number of transmissions is equal or lower than K as
The number of transmissions is equal or lower than 2 （K=2） means that both packets are successfully delivered to the next hop node. Therefore， the probability that the number of transmissions is equal or lower than 2 is [（1-pl）2]. When K is 3， we can first calculate the probability that the number of transmissions is larger than 3 （[PNT>3]）. The number of transmissions is larger than 3 only when 1） first 3 packets are all lost； or 2） the only one packet of the first 3 packets is received. Based on this we can calculate the probability that the number of transmissions is equal or lower than 3 as[ 1- p3l- 311-plp2l]. Similarly， we can calculate the probability for different values of K as in （4）. For the proposed scheme， we can calculate the probability that the number of transmissions is equal or lower than K as
Based on （4） and （5）， we draw the cumulative distribution functions for various numbers of possible transmissions in Fig. 3. In the figure， the line “Proposed （[pl]=0.1）” shows the cumulative probability for the proposed approach when [pl] （the packet loss probability of the link） is 0.1. When [pl] is 0.3， for the proposed scheme， the probability that the number of transmissions is equal or lower than 3 is 0.981127. This means that the proposed approach can deliver almost all packets with 3 transmissions. However， for the original approach， in order to provide 0.97% reception probability， the number of transmissions should be at least 5. We can observe that the expected number of transmissions for the proposed scheme is much smaller than the original method.
3.3 Analysis for Different Packet Loss Probabilities at the
Slave Node
Now we analyze the performance of the proposed scheme in the case where the master node and slave node have different packet loss probabilities. We use [pl] and [pl ]to denote the packet loss probability for the master node and slave node respectively. We can calculate the successful forwarding probability by extending （3） as
The average number of transmissions per hop by extending （5） can be calculated as
Based on （7）， Fig. 4 shows the cumulative distribution function for different packet loss probabilities at the slave node. The proposed scheme can significantly reduce the number of transmissions even when the packet loss probability at the slave node is higher than the master node.
4 Simulation Results
We used network simulator ns?2 （version 2.34） [21] to conduct simulations in Street scenario [22]， [23]. Simulation parameters are shown in Table 1. Simulation parameters were defined according to IEEE 802.11p [20]. We simulated IEEE WAVE multi?channel operation [24] by dividing each 100 ms channel time into two equal parts， a CCH interval and an SCH interval. All traffics generated by the simulation were transmitted in SCH intervals. We used the tiger line map file [22] and real street map based model [23] to generate realistic vehicle movement scenarios. We used a 2500 m × 2500 m square area in Midtown Manhattan in New York City （Fig. 5）. The Nakagami model was used to simulate the channel fading. The parameters of the Nakagami model are shown in Table 2. We used these parameter values because they model a realistic wireless channel of vehicular ad hoc networks [25]. Other simulation parameters were the default settings of ns?2.34. The proposed scheme was implemented with AODV [5] （we call AODV with the proposed scheme as AODV?proposed）， QLAODV [4] （QLAODV?proposed） and OLSR [18] （OLSR?proposed）. QLAODV takes into account the vehicle movement for the route selection. OLSR is a well?known proactive routing protocol. The proposed scheme was also compared with AODV?XOR （AODV with traditional network coding）， QLAODV?XOR （QLAODV with traditional network coding） and OLSR?XOR （OLSR with traditional network coding）. Here， we use “traditional network coding” to denote the approach in which XOR coding is used to forward packets for bi?directional unicast flows [26]. In the simulation， traffic flows were selected randomly. For AODV?proposed， QLAODV?proposed and OLSR?proposed， each slave node was selected by taking into account the hello reception ratios at the corresponding master node. The hello reception ratio was updated for each hello interval based on the number of received hello messages in the last 10 seconds. In order to clearly show the performance of the proposed scheme， we use the same access category Access Category Best Effort （AC_BE ） for all packets （since the proposed scheme is an enhancement to the routing protocol， the MAC layer issues （packet prioritization etc.） are outside the scope of this paper）. In the following simulation results， the error bars indicate the 95% confidence intervals.
4.1 Packet Delivery Ratio
Fig. 6 shows the packet delivery ratio for various numbers of nodes in Street scenario. From the results， we observe that the proposed scheme significantly improves the packet delivery ratio of all protocols （AODV， QLAODV， and OLSR）. By incorporating with QLAODV， the proposed scheme can provide the highest packet delivery ratio. These results show that the proposed scheme is necessary in a lossy environment. This is because in many cases， it is very difficult to select a very reliable next hop node. Traditional network coding?based approach is unable to improve AODV and QLAODV notably. This is because different traffics could use different forwarding nodes， resulting in a very small chance of network coding at the forwarding nodes. OLSR intends to use multipoint relay （MPR） nodes for routing， which improves the chance of network coding. However， the improvement is still very limited because different nodes could select different MPRs. The proposed scheme can significantly improve the packet delivery ratio in various node densities. This is because the proposed scheme does not incur extra overhead as compared with the original routing protocol. 4.2 EndtoEnd Delay
Fig. 7 shows the end?to?end delay. AODV?proposed and QLAODV?proposed show small improvements over AODV and QLAODV respectively. The proposed scheme can reduce the number of route discoveries （due to route errors） by providing a higher reliability at the forwarding nodes， which results in a lower channel contention time at each node. QLAODV and QLAODV?proposed show a low end?to?end delay due to the dynamic route change mechanism which uses shorter routes for data transmissions. Note that the delay of OLSR is dependent on the number of nodes which determines the overhead of control messages. Since the overhead of the proposed scheme does not increase with the node density， the proposed scheme can reduce the end?to?end delay of AODV and QLAODV in various node densities.
4.3 Normalized Control Overhead
A comparison of the normalized control overhead is shown in Fig. 8. The normalized control overhead is defined as the size （in bytes） of control packets generated divided by the size of data packets that arrive at receivers. We observe that the proposed scheme can reduce the normalized control overhead significantly by improving packet delivery ratio （for all protocols） and reducing the number of route discoveries （for AODV and QLAODV）. AODV?proposed shows a significantly lower overhead than AODV. This shows that the proposed scheme is efficient especially when the packet loss probability at the forwarding node is high.
5 Conclusions
We proposed a network coding?based cooperative forwarding scheme for unicast routing protocols in vehicular ad hoc networks. The proposed scheme can be easily applied to typical routing protocols. The proposed scheme can significantly improve the packet reception ratio at the forwarding nodes by employing network coding to utilize the broadcast nature of wireless communications. The theoretical analysis and simulation results showed the proposed scheme can considerably improve the packet delivery ratio without increasing message overhead.
References
[1] K. Shafiee and V. C.M. Leung， “Connectivity?aware minimum?delay geographic routing with vehicle tracking in VANETs，” Ad Hoc Networks， vol. 9， no. 2， pp. 131-141， Mar. 2011. doi： 10.1016/j.adhoc.2010.06.003.
[2] Q. Yang， A. Lim， S. Li， J. Fang， and P. Agrawal， “ACAR： adaptive connectivity aware routing for vehicular ad hoc networks in city scenarios，” Mobile Networks and Applications， vol. 15， no. 1， pp. 36-60， Feb. 2010. doi： 10.1007/s11036?009?0169?2. [3] R. T. Goonewardene， F. H. Ali， and E. Stipidis， “Robust mobility adaptive clustering scheme with support for geographic routing for vehicular ad hoc networks，” IET Intelligent Transport Systems， vol.3， no.2， pp.148-158， 2009.
[4] C. Wu， K. Kumekawa， and T. Kato， “Distributed reinforcement learning approach for vehicular ad hoc networks，” IEICE Transactions on Communications， vol.E93?B， no.6， pp.1431-1442， 2010. doi： 10.1587/transcom.E93.B.1431.
[5] Ad hoc On?Demand Distance Vector （AODV） Routing， RFC 3561， Jul. 2003.
[6] R. Jiang， Y. Zhu， T. He， Y. Liu， and L.M. Ni， “Exploiting trajectory?based coverage for geocast in vehicular networks，” IEEE Transactions on Parallel and Distributed Systems， vol. 25， no. 12， pp.3177-3189， 2014. doi： 10.1109/TPDS.2013.2295808.
[7] C.?M. Huang and S.?Y. Lin， “Timer?based greedy forwarding algorithm in vehicular ad hoc networks，” IET Intelligent Transport Systems， vol.8， no.4， pp.333-344， 2014.
[8] J. Cheng， J. Cheng， M. Zhou， et al.， “Routing in internet of vehicles： a review，” IEEE Transactions on Intelligent Transport Systems.， vol.16， no.5， pp. 2339-2352， 2015.
[9] X. Huang and Y. Fang， “Performance study of node?disjoint multipath routing in vehicular ad hoc networks，” IEEE Transactions on Vehicular Technology.， vol.58， no.4， pp.1942-1950， 2009. doi： 10.1109/TVT.2008.2008094.
[10] C. Wu， S. Ohzahata， T. Kato and Y. Fang， “A low latency path diversity mechanism for sender?oriented broadcast protocols in VANETs，” Ad Hoc Networks， vol.11， no.7， pp. 2059-2068， 2013. doi：10.1016/j.adhoc.2012.02.007.
[11] S. Li， R. Yeung， and N. Cai， “Linear Network Coding，” IEEE Transactions on Information Theory， vol. 49， no. 2， pp. 371-381， 2003. doi： 10.1109/TIT.2002.807285.
[12] U. Lee， J.?S. Park， J. Yeh， G. Pau， and M. Gerla， “CodeTorrent： content distribution using network coding in VANET，” in Proc. ACM MobiShare， Los Angeles， USA， 2006， pp.1-5. DOI： 10.1145/1161252.1161254.
[13] M. Li， Z. Yang， and W. Lou， “CodeOn： cooperative popular content distribution for vehicular networks using symbol level network coding，” IEEE Journal on Selected Areas in Communications， vol. 29， No. 1， pp. 223-235， 2011. doi：10.1109/JSAC.2011.110121.
[14] T.?X. Yu， C.?W. Yi， and S.?L. Tsao， “Rank?based network coding for content distribution in vehicular networks，” IEEE Wireless Communication Letters， vol. 1， no. 4， pp. 368-371， 2012.
[15] F. Ye， S. Roy， and H. Wang， “Efficient data dissemination in vehicular ad hoc networks，” Journal of Systems and Software， vol. 30， no. 4， pp. 769-779， 2012. doi：10.1016/j.jss.2016.04.005. [16] B. Hassanabadi and S. Valaee， “Reliable periodic safety message broadcasting in VANETs using network coding，” IEEE Transactions on Wireless Communications， vol. 13， no. 3， pp. 1284-1297， 2014. doi： 10.1109/TWC.2014.010214. 122008.
[17] Q. Wang， P. Fan， and K.B. Letaief， “On the joint V2I and V2V scheduling for cooperative VANETs with network coding，” IEEE Transactions on Vehicular Technology， vol.61， no.1， pp.62-73， 2012. doi： 10.1109/TVT.2011.2167249.
[18] P. Jacquet， P. Muhlethaler， T. Clausen， et al.， “Optimized link state routing protocol for Ad Hoc Networks，” in Proc. IEEE International Multitopic Conference， Pakistan， 2001， pp.62-68.
[19] C. Wu， S. Ohzahata， and T. Kato， “VANET broadcast protocol based on fuzzy logic and lightweight retransmission mechanism，” IEICE Transactions on Communications， vol. E95?B， no.2， pp.415-425， Feb. 2012. doi： 10.1587/transcom.E95.B.415.
[20] IEEE Std 802.11 Amendment 7： Wireless Access in Vehicular Environments， 802.11p ?2010， 2010.
[21] ISI. （2015， Jun. 25）. The Network Simulator ? ns?2 [Online]. Available： http：//www.isi.edu/nsnam/ns
[22] U.S. Census Bureau. （2012， Jun. 23）. TIGER/Line [Online]. Available： http：//www.census.gov/geo/www/tiger
[23] A.K. Saha， and D.B. Johnson. “Modeling mobility for vehicular ad hoc networks”， in Proc. First ACM Workshop on Vehicular Ad Hoc Networks， Philadelphia， USA， Oct. 2004， pp.91-92. doi： 10.1145/1023875.1023892.
[24] IEEE Standard for Wireless Access in Vehicular Environments （WAVE）?Multi?channel Operation， IEEE Std 1609.4?2010， Sept. 2010.
[25] A. Khan， S. Sadhu， and M. Yeleswarapu， “A comparative analysis of DSRC and 802.11 over vehicular ad hoc networks，” Project Report， University of Californai， Santa Barbara， USA， pp.1-8， 2009.
[26] Z. Xiang and X. Fang， “An improved AODV routing protocol with network coding in wireless ad hoc network，” in Proc. IET Conference on Wireless， Mobile and Sensor Networks， Shanghai， China， 2007， pp.84-87.
Manuscript received： 2015?12?25