A Reliable Routing Algorithm with Network Coding in Internet of Vehicles

，Manlin Fang, Yang Li, Botao Feng

1 Faculty of Information Technology, Macau University of Science and Technology, Avenida Wai Long, Taipa, Macau, China

2 College of Electronic Science and Technology, Shenzhen University, Shenzhen 518060, China

* The corresponding author, email: jqli@must.edu.mo

I. INTRODUCTION

Traffic congestion, pollution, and traffic safety are three major problems in international transportation fields. Intelligent Transportation System (ITS) provides potential schemes,which could effectively establish a wide range,real-time, reliable, and efficient integrated intelligent transport communication system.

The rapid increase of traffic data sources(base station, mobile, portable terminal, intelligent vehicle terminal, and so on), allows the collection and dissemination of transportation information without creating a bottleneck in the ITS.

This traffic information can be quickly shared among traffic participants (including cars, buses, taxis, etc.) and the Traffic Control Center, as shown in Figure 1, through sensors in vehicles, transfer stations, parking lots and intelligent transmission equipment, etc.According to the aggregated data, the Traffic Control Center could carry out real-time scheduling, according to various measures,such as closing signal lights, issued guidance information, accident treatment and rescue. To achieve intelligent vehicle communication, acquisition and dissemination of real-time traffic information between vehicles is the key point[1].

Internet of Vehicle is operated with a high bit error rate and interference [2]. At the same time, rain and the large scale of building may block the transmission of radio waves, which are apt to cause interruption of the wireless link between vehicles. All of this makes it a challenge to provide reliable communication service in the city environment. This has become a hotspot in vehicular network research[3].

In order to improve the reliability of packet delivery, a novel routing algorithm is introduced in this paper.

Due to a large number of vehicle nodes in the urban traffic environment, multiple communication paths are present. In multi-hop vehicle sensor networks, traditional routing protocols choose a sequence of nodes between the source and the destination and then forward packets along the path. In order to overcome the shortcomings of the traditional single path routing, the vehicle network usually uses multi-path routing technology to achieve reliable communication, which makes the multipath routing algorithm a research hotspot.However, there are some unsolved problems in the application of the traditional multipath routing technology in the multi-hop network[4].

First, due to the difference of data transmission over the multiple paths in node cache capacity in traditional multi-path routing algorithm, the packets arrive at the destination prone to disorder. In addition, due to the rapid changes of vehicle network topology, the wireless link is unstable. Therefore, it always retransmits the data in the link layer level to reduce packet loss. However, in the case of heavy traffic in the vehicle network, frequent transmission can cause a huge waste of network overhead, so as to increase the end to end delay.

Fig. 1 Urban intelligent traffic management scenario

In order to increase link duration and throughput, TALEBet al.[5] present a stable routing algorithm by using vehicles’ movement information (e.g., position, direction,speed, etc.) to predict a possible link-breakage event. In this scheme, the link expiration time(LET) of each link in the group is calculated,and then the most stable communication link is searched according to LET. This method could effectively reduce the overall traffic in the network. SAKHAEEet al.[6] presents a Doppler aware clustering algorithm for highly mobile ad hoc networks and aims to establish stable clusters, which can provide help for establishing reliable mobile routing algorithms based on clusters.

In order to enhance the reliability of data dissemination when vehicular density occurs,Static node assisted adaptive data dissemination (SADV) protocol is introduced in [7],which attempts to increase the delivery ratio for medium and low vehicular densities at the road junctions. This moving cluster assisted routing could improve the connection time and thereby improve packet delivery ratio. In recent years, when network encoding began to apply, practice shows that it can significantly improve the capacity and reliability of vehicle networks [7]. But in IoV, the related research has just begun [9,10,11].

Based on the above analysis, this paper proposes a reliable routing algorithm with network encoding for IoV. By addition linear code in transmission, the proposed algorithm can recover original data packets under poor urban traffic environments. The paper is organized as follows. In section 2, a system model is displayed. In section 3 the proposed reliable routing algorithm protocol is depicted in detail. Section 4 discusses performance evaluation, and the results are compared with other routing algorithms. Conclusions are given in Section 5.

II. SYSTEM MODEL

In this section, ITS network architecture is given, and then the cooperative communication system with network coding is discussed in the urban environment.

In Figure 2, the perception layer is responsible for real-time data acquisition from vehicles, including weather conditions, location,traffic congestion, emergencies, etc. The transport layer delivers the data between vehicles and ground stations. Upon receiving various information, the application layer starts to process and analyze this information, and then decision-making information is fed back to each vehicle.

2.1 Cooperative communication in IoV

In urban traffic, there are some characteristics of the vehicle network. Firstly, mass vehicles along the road show strong obvious group mobility [3]. Secondly, due to the speed limit and the traffic light control, vehicles with the same destination and similar speed easily form a unified cluster. All these cases provide a typical scenario for the Internet of Vehicle with network coding.

Figure 3 illustrates the application of the network in vehicular networking encoding. In the traditional method of data transmission,each hop is composed of a single link, and in the cooperative coding transmission system,each hop is multi-point to multi-link instead.Network encoding technology can receive packet combinations randomly, and through the cooperation of different nodes in the same cluster, then forward the encoded data packets.This kind of cooperative transmission mechanism increases the likelihood of packet arrival to end point.

2.2 Cooperative communication with network coding

Network coding presented by AHLSWEDEet al. [12] put forward a new point of view that intermediate nodes could intelligently mix the received packets, and the resulting transmitted packets could contain information of multiple messages. Based on the analysis capacity bound networks, network coding allows intermediate nodes to implement encoding to packets.

Network coding was proposed to improve the performance of multicast [13] and broadcast [14] in the context of wireless networks,with throughput gain. By using randomized network coding, the destination node can still recover the message from source data, even if some links have failed. The experiments were conducted to demonstrate that network coding enhances the network fault tolerance,resilience and stability, and reduces the energy consumption, which has great application value in vehicle networking communication technology.

Fig. 2 ITS network architecture

Fig. 3 Cooperative communication in IoV

III. RELIABLE ROUTING WITH NETWORK CODING

A Reliable Routing Algorithm with Network Coding (RR_NC) is presented in this section.Through integration of network coding into multicast between vehicles clusters, the algorithm can effectively improve the reliability of data transmission in the Internet of Vehicles.The algorithm is given as below.

3.1 Initial route discovery

In RR_NC, a “one-node-width” path is first discovered between source and destination,by using MACO [16] routing protocol. To determine the optimal routing path, a few attributes are abstracted from road. Suppose each intersection hasmroads and each road containsnattributes,means the value ofattribute ofroad. Then get the attribute weights as formula (1) as follows:

Fig. 4 Packet format with network coding

3.2 Clustering

As initial vehicle node sequence has formed with MACO previously, and then each vehicle node can recruit other vehicles as a cluster within transmission range. RR_NC is designed to transmit packets from one cluster to another cluster. Recruiting of cluster nodes is done per hop. Recruiting of nodes of the next cluster commences once all the packets are received by the previous cluster.

3.3 Encoding

Once the cluster is formed, the RR_NC routing algorithm can transfer data from one cluster to another in a group of encoding data packets. First, the source divides original data packets into several groups, each group hasmelements. Then, these groups are converted into new data packets of the same size by using network coding. Finally, these new packets will be sent out in a parallel manner.

The source node partitions the data into groups ofmpackets, according to the sequence of them. A packet is denoted byRandom linear code is used in the routing algorithm. A coded packetis a linear combination of the native packets, generated as formula (3):

3.4 Recoding and Forwarding

Once the immediate relay node receives the coded packets, it will invoke recoding of the previous coded packets belonging to the same group with network coding, and then forwards them to next cluster.

In order to further reduce the linear correlation of encoding messages, and improve the success rate of decoding at destination, as the encoded packets from the same group of the sending cluster have arrived, they will first be cached, and then forwarded to next cluster. At the same time, the packets with the same ID will be re-encoded.

The node will embed a new encoding vectorinto the header ofas the source node while forwarding the encoded packets.

3.5 Decoding

When the destination node receives enough data packets from the intermediate node, the decoding algorithm can be used to recover the original data.

Receiving a coded packet, the destination will first check whether the packet is linearly independent from the previous ones of the same group. The packet will be discarded if it is not independent. The coding coefficient is known by using the embedded code vector and each coded packet represents a linear equation ofmelements. Thus, as long as the destination has obtainedmpackets, it could recover the original packets by solving the following set of linear equations. The equations can be uniquely solved, if the rank of the matrix ism.

IV. SIMULATION

In order to evaluate the performance of the proposed routing algorithm, this section gives a detailed performance evaluation. Firstly,the key parameters are analyzed, then the simulation setup and related experiments are designed, and the experimental results are compared with the existing algorithms.

4.1 Parameters

Assuming that the nodes in the same cluster are within the transmission range of each other, the key parameters are given as Table I.

In practice, the linear independence of the received data packets at destination is determined by the range ofOn the one hand, if the value ofqis too large, the memory space occupied by the coded coefficient is too large, which produces pressure on the limited storage ability of vehicles. On the other hand,if the value of theqis too small, the linear correlation of the received data is higher,which make it is unable to recover the original messages correctly. Table II gives the linear independent probability (p) of the coded coefficient with differentq.

Fig. 5 Urban road network of Macau

Table I Network Paramters

Table II Linear independent probability of coefficient vector in different finite fields

As can be seen from Table II, whenqequals 8, thepof the two coded coefficient vectors is as high as 99.96%. Meanwhile, the size of the coded coefficient is only 1 byte, and the original packets can be recovered with a very high probability. Based on the above analysis, the value ofqis set to 8 in the simulation.

Whether the destination is able to obtain more linear independent encoding packets with the least number of packets, is decided bynandp, wherenis the number of nodes in a cluster andpis the linear independent probability. The greater ofnand the smaller ofp,the probability of recovering the original data packet is greater. This is because more packets are successfully forwarded to the next cluster,and more linear independent packets can be generated.

4.2 Simulation environments

Firstly, the dynamic simulation environment of vehicle network is built by using QualNet simulation software [22], and the simulation model is built for each vehicle node [19]. In the physical layer, the actual communication environment factors, such as the free space propagation model and transmission power are considered [20]. The Application layer uses constant bit rate (CBR) to simulate the vehicle communication message. Assuming all services are distributed evenly, all the vehicle terminals produce new messages at the same probability, and the packet length is satisfied with Poisson distribution.

A real-world urban road networks from Macau as shown in Figure 5 is employed in the simulations. Bold lines show two-way fourlane roads, other roads show two-way twolane roads. The unidirectional road segments are omitted for simplicity. The simulation is taken from the road between point A and point B or point A and point C. The Channel bandwidth is 1 Mb/s, the antenna radius is 500 m, and the transmission power of the node is 1.25W. Every time, 5 original packets in each group are routed from the source node to the destination. Simulations are taken in the scenario that the data is transmitted from point A to point B and point C to point D in Figure 5. All simulation data is obtained with the average of 10 runs and the results are compared with the SADV [7] routing algorithm and Cluster-based Dynamic Routing Approach(CDRA) [21].

The following three performance evaluation metrics are mainly considered in simulation experiments.

1) Throughput: this represents the number of 10 original packets that the source node has initially transmitted to the destination.

2) Packet Loss Rate: the ratio of the number of lost packets to the total of the transmitted data set, which is related to the packet length and the packet transmission frequency.

3) Total delay: the time used to transmit the packet from source to destination.

4.3 Simulation I

The first simulation tests the impact of different routing algorithms on the entire network throughput with the same link packet loss rate(p=0.05), and the average packet size of 256 Kbytes.

As can be seen from Figure 6, the throughputs of the three algorithms increase with the increment of nodes. This is because each packet has a greater possibility to be transmitted to the destination when the cluster has more nodes. However, when the number of nodes in the cluster is less than 5, the performance of RR_NC is a little worse. This is mainly due to the fact that the destination node must wait to get at least 5 data packets to start decoding in RR_NC. When the number of received data packets at destination is less than 5, it is difficult to recover the data packets. When the number of nodes in the cluster is more than 5(that isthe destination could receive enough packets to recover the original data packets, so the throughput of RR_NC is greater than other algorithms. When the number of nodes is beyond 5, the performance of SADV is better, but the throughput is not up to 5.CDRA obtained the lowest throughput without the use of clustering and network encoding.These results show that the proposed RR_NC effectively improves the throughput of the entire network.

4.4 Simulation II

In the second simulation, the average size packet is 256 Kbytes，the link packet loss rate varies from 0.01 to 0.3.

Figure 7 describes the changing of three different routing algorithms in packet loss rate.Whenpis relatively small, the whole network packet loss rate of these algorithms remains low. With the increase ofp, the overall packet loss rate of the other two algorithms, CDRA and SADV, increases. This is due to the fact that the network communication interrupt is more frequent, and, the error correction capability of the link layer is limited. On the contrary, RR_NC shows comparatively good performance. This is because the use of network coding introduces more control and correction for transmission in application layers between clusters. Therefore, even if some nodes or links in the network fail, the destination can still recover the original message data from the source. It is obvious that network coding enhances the fault tolerance and the stability of entire network. In contrast, because there is no recovery mechanism, the other two algorithms are more likely to have some packet loss in each hop. Ifpis greater, more packet loss rate occurs in transmissions of CDRA and SADV.

Fig. 6 The influence of the number of nodes on the throughput.

Fig. 7 The influence of network performance on Packet Loss Rate

Fig. 8 The influence of vehicle speeds on Packet Loss Rate

Table III Statistics of total delay of three algorithms in simulation

4.5 Simulation III

In order to simulate and investigate the effect of mobility, vehicle speeds are varied. The result is shown in Figure 8, which illustrates packet loss rate with a period of 5 minutes. On average, the speed of a vehicle ranges from 20 to 80 km/h (depending on road speed restrictions and vehicle types).

From the results, it can be seen that the proposed RR_NC can form stable clusters containing packets in the associated clusters for a longer period of time, with the vehicle speeds from 20 to 60km/h. The packet loss rates of RR_NC shows almost no change with vehicle speeds varying from 20 to 60 km/h while those packet loss rates of CDRA and SADV increase quickly. This shows that our RR_NC routing algorithm is suitable for urban scenarios, depending on the amount of reliable mobility information available in the targeted system.

4.6 Simulation IV

The fourth simulation demonstrates the timeliness of three routing algorithms under different traffic flow, wherep=0.05 andn=5. As can be seen from Table III, when the size of the data packet is small (64k), the network traffic is small, and the total delay (the time used to transmit the packet from source to destination)of the three algorithms are similar to each other. When the size of the packet is large (512k),the network traffic becomes large, and it is prone to packet loss because of network congestion. In this case, the sender and the relay nodes in CDRA and SADV will launch more retransmission, resulting in large time consumption. By using network encoding, RR_NC could reduce unnecessary retransmission via a cooperative communication mechanism.At the same time, the amount of control overhead and bandwidth resource occupancy remains low, and this is conducive to being able to guarantee applicable end to end delay.

V. CONCLUSION

In the ITS, the Internet of Vehicles connects the communication terminals and provides real-time traffic information to drivers and traffic managerial staff at the fastest speed possible. This achieves a reduction of traffic load, ensuring traffic safety and improving the efficiency of traffic control. As one of the key technologies, mobile routing technology largely determines the performance of the entire vehicle network. In order to improve the reliability of packet delivery, a novel routing algorithm is introduced in this paper. The basic idea of the algorithm is to integrate network encoding into packet transmission between clusters by using the cooperative communication mechanism of the vehicle nodes.

Simulation experiments are designed for several scenarios and the performance of the proposed algorithms are compared with the traditional encoding routing algorithms which do not use network coding. Results show that the novel algorithm with network coding has obvious improvement in throughput and packet loss rates, under the circumstance of increasing network nodes and relatively poor network communication environments. At the same time, the total delay of packet transmission is effectively guaranteed, in the event of large network traffic flow. All of the above shows that the proposed algorithm can solve the low reliability problem of current network communication in urban traffic environments,by introducing cooperative communication and network coding between the nodes in the cluster. The routing algorithm can be realized in the intelligent electronic terminal of vehicles and it is convenient to operate in this application. From the experimental results, the algorithm presented in this paper is more suitable for the scenario of heavy vehicle traffic and heavy communication interference.

Although the advantage of network coding is outstanding, it raises the complexity of the calculations needed to cache enough information. The novel routing algorithm enhances the capabilities of the performance and cost investment of vehicle electronic equipment. In the future, our work can focus on researching the impact of network coding in energy saving.

ACKNOWLEDGEMENTS

This work is supported by the Science and Technology Development Fund (No.037/2015/A1), Macao SAR, China.

[1] Y.S Chen, Y.W Lin, C.Y Pan, “DIR: diagonal-intersection-based routing protocol for vehicular ad hoc networks”[J], Telecommunication systems,vol.46, no.4, pp 299-316, April, 2011.

[2] S.G Wang, C.Q Fan, C.H Hsu, “A Vertical Handoff Method via Self-Selection Decision Tree for Internet of Vehicles”[J], IEEE Systems Journal,vol.10, no.3, pp 1183-1192, September, 2016.

[3] K Naveen, K Karuppanan, “Mobile cluster assisted routing for urban VANET”[C], International Conference on Recent Trends in Information Technology (ICRTIT 2011), IEEE, pp 296–300,June, 2011.

[4] G Kim, Y.S Ong, K.H Chen, “City Vehicle Routing Problem (City VRP): A Review”[J], IEEE Transactions on Intelligent Transportation Systems,vol.16, no.4, pp 1654-1666, August, 2015.

[5] T Taleb, E Sakhaee, A Jamalipour, “A stable routing protocol to support ITS services in VANET networks”[J], IEEE Transactions on Vehicular Technology, vol.56, no.6, pp 3337-3347, November, 2007.

[6] E Sakhaee, A Jamalipour,“Stable clustering and communications in pseudolinear highly mobile Ad Hoc networks”[J], IEEE Transactions on Vehicular Technology, vol.57, no.6, pp 3769-3777,November, 2008.

[7] Y Ding, L Xiao, “SADV: static-node-assisted adaptive data dissemination in vehicular networks”[J], IEEE Transactions on Vehicular Technology, vol.59, no.5, pp 2445-2455, June, 2010.

[8] Z.N Feng, Y.M Zhu, Q Zhang, “Exploiting Network Coding for Data Availability in Vehicular Networks: Issues and Opportunities”[C], 2012 Eighth International Conference on Mobile Adhoc and Sensor Networks, pp 24-30, December,2012.

[9] L Zhang, B Hassanabadi, S Valaee, “Cooperative Positive Orthogonal Code-Based Forwarding for Multi-Hop Vehicular Networks”[J], IEEE Transactions on Wireless Communications, vol.13, no. 7, pp 3914-3925, July, 2014.

[10] I Achour, T Bejaoui, S Tabbane, “Network coding approach for vehicle-to-vehicle communication:Principles, protocols and benefits”[C], 2014 22nd International Conference on Software,Telecommunications and Computer Networks,IEEE, pp 154-159, September, 2014.

[11] A Arsie, K Savla, E Frazzoli, “Efficient Routing Algorithms for Multiple Vehicles With no Explicit Communications”[J], IEEE Transactions on Automatic Control, vol.54, no.10, pp 2302-2317,October, 2009.

[12] R Ahlswede, N Cai, S Li, R.W Yeung, “Network information flow”[J], IEEE Transactions on Information Theory, vol. 72, no. 4, pp. 167–180, July,2000.

[13] D.S Lun, N Ratnakar, R Koetter, “Achieving minimum-cost multicast: a decentralized approach based on network coding”[C], 24th Annual Joint Conference of the IEEE Computer and Communications Societies, Miami, FL, USA, pp 1607–1617, March, 2005.

[14] C Fragouli, J Widmer, J.Y.L Boudec, “A network coding approach to energy efficient broadcasting: from theory to practice”[C], 25th IEEE International Conference on Computer Communications, Barcelona, Spain, pp 1–11, April, 2006.

[15] Y Jo, J Choi, I Jung, “Traffic Information Acquisition System with Ultrasonic Sensors in Wireless Sensor Networks”[J], International Journal of Distributed Sensor Networks, vol.2014, no.1804,pp 1-12, May, 2014.

[16] Z Wang，J.Q Li，M.L Fang，Y Li,“A Multimetric Ant Colony Optimization Algorithm for Dynamic Path Planning in Vehicular Networks”[J],International Journal of Distributed Sensor Networks, vol. 2015, pp 1-10, January, 2015.

[17] H.M Zhang, L.Y Yu, “MADM method based on cross-entropy and extended TOPSIS with interval-valued intuitionistic fuzzy sets”[J], Knowledge-Based Systems, vol. 30, no.2, pp 115-120,June, 2012.

[18] D.F Li, “TOPSIS-based nonlinear-programming methodology for multiattribute decision making with interval-valued intuitionistic fuzzy sets”[J], IEEE Transactions on Fuzzy Systems, vol.18, no.2, pp 299-311, January, 2010.

[19] Z Li, F Bai, J.A Fernandez, B. V. K. Vijaya Kumar,“Tentpoles Scheme: A Data-Aided Channel Estimation Mechanism for Achieving Reliable Vehicle-to-Vehicle Communications”[J], IEEE Transactions on Wireless Communications,vol.14, no.5, pp 2487-2499, January, 2015.

[20] C Ren, J Chen, Y.H Kuo, “Differential successive relaying scheme for fast and reliable data delivery in vehicular ad hoc networks”[J], IET Communications, vol.9, no.8, pp 1088-1095, May,2015.

[21] R.C Poonia, D Bhargava, B.S Kumar, “CDRA:Cluster-based dynamic routing approach as a development of the AODV in vehicular ad-hoc networks”[C], 2015 International Conference on Signal Processing and Communication Engineering Systems (SPACES), pp.397-401, March,2015.

[22] Scalable Network Technologies. QualNet 5.0.2,Programmers Guide. March, 2010.