A Contention-Based Routing Protocol for VANET

Headnote

Abstract

In VANETs, vehicles as nodes are self-organized and inter-communicated without centralized authority. The topology formed by vehicles changes quickly, which makes routing become instability. Position-based routing, compared with traditional routing, is more scalable and feasible. Thus it has been proven stabler for VANETs than conventional routing. However, the frequently changed topology and nodes density could break the path a packet is following. Thus designing a robust multi-hop routing in VANET is challenging. This paper proposes an enhanced position-based routing protocol called CBGR, which takes into account the velocity and direction of vehicles in VANET. Simulation results show that CBGR achieves a high level of routing performance in terms of hop counts, network latency and packet delivery ratio both in dense or sparse vehicular ad-hoc networks.

Keywords: VANET, routing protocol, greedy forwarding, local optimal

Copyright © 2016 Universitas Ahmad Dahlan. All rights reserved.

(ProQuest: ... denotes formulae omitted.)

1. Introduction

Vehicular Ad hoc Network (VANETs) [1] is a means of inter-vehicle communication, using for safe driving, driver assistance and traffic management. In VANETs, vehicles as nodes are self-organized, they communication in a distributed fashion with no centralized authority. Moreover, the vehicles are move fast, the topology formed by them changes quickly. Highly dynamic topology makes data transmission less reliable, since the highly dynamic topology may result in network disconnect frequently. So the key problem of design a routing protocol is keeping it as stable as possible, trying to keep the link between two vehicles while they are transmitting information. Beside, nodes in VANETs are not subjected to storage and power limitation as in wireless sensor networks. Vehicles as node in VANET, are supposed to have ample computing power and energy. However, efficient multi-hop routing in VANET is challenging, due to the frequently changed topology. VANET routing protocols must operate reliably in scenarios embracing high speed nodes.

Significant VANET protocols have been proposed, and they're classified as topologybased and position-based[2]. Topology-based routing protocols perform packet forwarding, using links' information they collect from the network. They find out a path to the destination before relay the packet. Position-based (geographic) routings perform packet forwarding, using the position information of the ultimate destination and of the one-hop neighbors. Usually they are stateless, with no need to keep the link information about the whole network. An intermediate node forwards a packet to its neighbor with the closest distance to the position of the destination. These days, it is common that vehicles get a GPS unit on board, from where vehicles can get their location information. It has made position-based routing easy implemented and popular.Literatures have conducted evaluation study of topology-based routing protocols and position-based ones[3, 4]. Unable to cope up with nodes' high mobility and minimum transmission delay, topology-based routing protocols perform unacceptably in VANETs [5, 6].

Position-based routing, as is used by protocols like Greedy Perimeter Stateless Routing (GPSR) [7] and Geographic Routing Protocol(GRP) [8], is well suited for highly dynamic environments such as VANET.

Intermediate node in GPSR forwards a packet to a radio neighbor which is closest to the desination. This approcach is called greedy forwarding. It is assumeed that each node can determine its own position using a GPS. Nodes exchange their locations with neihbors, and obtain the position of destination by a location service. In some cases, there might be no nexthop when greedly forwarding, GPSR introduces a strategy, called perimeter routing. Many research [9-12] have improved GPSR, most of which worked on planarized graphs, which are required in perimeter mode. However these schemes always involve significant overheads, and thus reduce the efficiency of position-based routing.

Node in GRP maintains a neighbor table by periodically broadcasting Hello message. It is assumed that each node can determine its own position using a GPS. The positions of other nodes are determined through flooding [13]. The whole network is divided into quadrants with different levels. They are deployed in a hierarchy manner. Four low levels compose a high level, thus provide a distributed location service. This schedule makes it overcoming GPSR and many other position based protocol. GRP forwards packets in an greedy mode until it gets stuck in a local optimum, where there are no new nodes to forward the packet to. It uses a backtracking mechanism, where the packet is returned to the previous hop and a new next hop selection can be made.

The aforementioned working schedule of GRP makes it a suitable routing protocol for VANET, but there are still some shortcomings. The packet forwarding algorithm is too simple, that it only makes use of the location information to forward the packets. The mobility of packet's source and destination are considered, while the intermediate node's movement isn't well considered when selecting next hop. As the intermediate node moving, the link between them will probably vanish, which result in the routing instability. This generates a routing rebuilt, which bring more network overhead and cost. Thus GRP may not perform as efficient as expected when deployed in VANET, where vehicles are always in a relatively high mobility.

In the next section, a geographic routing protocol called CBRG is proposed, which improve the forwarding decisions through contention among nodes. CBGR is proposed based on GRP to optimize the efficiency, it redesigns the forwarding and backtracking algorithm of GRP, The purpose of CBGR is to improve the packet delivery ratios while reduce the network delay. CBGR keeps the advantages of GRP.Further more, it incorporates geographic location with node's mobile velocity and direction, to be the precondition for choosing the next hop. Simulation results show that CBGR achieves a high level of routing performance in terms of hop counts, network latency and packet delivery ratio both in dense or sparse vehicular ad-hoc networks.

2. Contention-Based Geographic Routing (CBGR)

2.1? Contention-based Forwarding

We notice that, Locations Services and Forwarding algorithm are the two key problems in routing protocols based on geographic location, which would affect the routing performances. The hierarchy location service employed in GRP overcomes many other routing protocols in using the destination zone instead of destination location. This makes GRP be one of the highest efficient position-based routing protocols, as it can decrease the location indeterminacy cause by the mobility of the destination. CBGR keeps this advantage, and redesigns the forwarding algorithm, imposing an additional contention in speed and direction. Meanwhile, CBGR propose a repair strategy when a packet gets stuck in a local optimum, while GRP simply gives the packet back to the previous forwarder.

2.1.1. Contention Based on Speed

Priority is introduced in CBGR. A node calculates the priority of its neighbor before forward it. We use the priority to select the most suitable node to relay, rather than make a pure greedy forwarding selection.

Stability is an important requirement of routing in a wireless network. A high mobility may cause the route failure if we use pure greedy forwarding. To increase reliability, GRP reads the velocity of each node, and select reliable nodes with the lower velocity, abandoning others even if they are closer to the destination. On the other hand, nodes with lower velocity would make a smaller location changes while exchanging Hello message, this will prolong the neighbor table' lifetime.

There are two approaches to get the neighbor's velocity. One can write its own speed in hello message, thereby the speed is known by others along with the broadcasting of hello message. Another way is that, each node can calculate the velocity of its neighbor by the following formula:

... (1)

Where node_lat, node_long and timestampj are the latitude, longitude and time of the neighbor at time j respectively, and nbr_lat, nbr_long and timestampI are the latitude, longitude and time of the neighbor at time i read from neighbor table. We add an additional field named velocity to the neighbor table. To minimize the computing cost when relay a packet, each node does this calculation when receiving the hello message, and updates the neighbor table.

When forwarding packets, we use Pv to decide the priority of the neighbors. Formula 2 define the velocity priority:

... (2)

Thus CBGR selects the next hop based on a contention of speed. The one of the lowest speed will get a highest velocity priority.

2.1.2. Contention Base on Direction

Because of the obstacles, nodes in different roads cannot communicate with each other unless one is an extension of the other. Consider scenario in Figure 1 , Node N1 is at the crossing. At that moment, the current forwarder C will pick N1 as the next hop with a different moving direction. However, since the node is always moving fast in VANET, N1 may be out of C's radio range. In fact it would be better if C chooses N2 at that time. So it's necessary for the neighbour to content base on the moving direction. For a long-lasting link, the one with the same direction as the current forwarder will be a good candidate.

As discussed before, we can use the location at two different moments to calculate the direction of a node.

... (3)

Where node_lat and node_long are the coordinates, and t1 and t2 are two different time points. In order to reduce the impact on relay packet, node calculates Dir when receiving the Hello message, and then updates its neighbor table. Let Pd stand for the priority based on node moving direction, we define Pd as the following formula:

... (4)

Node read Pd from neighbor table to decide a better next-hop before forwarding.

2.2? Deal with Dead-end Problem

Sometimes when greedy forwarding packets, it can lead to blocked routes where there are no next hops to forward the packet to. GRP adopts backtracking, which return the packet to the previous node where a new next hop selection can be made [8]. This mechanism will probably increase the hops to the destination, therefore increase the transmission delay. The long-known dead-end problem is depicted in Figure 2.

The distance between D and x is the radius of the arc around node D. The arc around x stands for its radio range. Although there are two existing paths to D, x-y-z-D and x-w-v-D, x will choose neither of them using greedy forwarding [7]. There needs to be some other mechanism for x to forward packets in this situation.

Classical protocol GPSR uses perimeter forwarding to solve the local optimal. When there is no new node to relay in greedy mode, the long-known right hand rule is introduced to find a path around the void. Perimeter forwarding will come back to greedy forwarding as soon as a new node appears, which is geographically closer to the packet's destination than the node switch to perimeter mode. The shortcoming of perimeter forwarding is planar graphs are required. An algorithm for removing edges from the graph that are not part of the Relative Neighborhood Graph or Gabriel Graph are also required to yield a network with no crossing links [14, 15]. This will definitely increase the routing cost.

GRP, as mentioned before, use a backtracking mechanism to return the packed to the previous node, where a new next hop selection using greedy mode can be made. Thus no new mechanism introduced to solve the problem. A node will eliminate local optimal neighbors one by one until a valid neighbor is found or the packet-life comes to the end. This trial and error method will probably increase the hop counts and the network latency.

The intuition behind CBGR is even if we can't get any closer to the destination, we won't go far away from it. So we go back, but neither returns that much to the previous hop as in GRP, nor follow a fixed counter wise sequence around the void as in GPSR. We let the neighbors of the local optimal node content again. The one closest to the destination got the highest prior. If C get more than one neighbors with the same closest distance to the destination, the one which is furthest to C will win the contention. This is because there is a void ahead; the further the node is away from C, the easier it can bypass the void. See Figure 3 for an example. N1 and N2 lies on the arc with the same distance to node D. Note that in the figure, N2 is more suitable than N1 to be the next hop.

2.3? Combining All Contentions

We now present the full CBGR routing algorithm, which combines all the above mentioned contentions together.

Step 1. When a source node or an intermediate node sends packets, it checks in its neighbor table, to find out the entry of the packet's ultimate destination. If there is an entry, the packet will be delivered directly to the destination successfully, and CBGR ends. If there isn't any entry, the sender will select a node in its single-hop radio neighbor, which is geographic closest to the destination. This step loops and quits when the following two case show up:

Case 1: if there are more than one nodes, which form a set called set_1, satisfy the rule, goes step 2;

Case 2: if there are no nodes satisfy the rule, goes step 4;

Step 2. Contend based on velocities. The sender calculate Pv , using formula 2, for each candidates in set_1, chooses the one with highest Pv as the next hop. The algorithm goes to step 1. If there are two nodes and above, which form a set called set_2, satisfy the rule, goes step 3;

Step 3. Contend based on direction. The sender calculates Pd, using formula 4, for each candidate in set_2, chooses the one with highest Pd as the next hop, and the algorithm goes back to step 1; If there are still more than one nodes satisfy the rule, the sender picks one randomly, and the algorithm goes back to step 1.

Step 4. Break through dead-end. The sender relays the pack, using schedule presented in section 3.3. If there is no neighbor except the one where the packet is from, the sender will carry the packed until there is a fresh hello message or expire TTL, then the algorithm goes back to step1.

By competitions, node can pick up a better next-hop than GRP in vehicle ad hoc network. We must clarify there is rarely possibility for our algorithm degenerated to pure greedy without contention. We define the two nodes with the same distance from sender, if the difference is within 10 meters. So there will always be contentions, especially in crossroad, where the direction contention is highly required.

Recall that all nodes maintain a neighbor table, which stores the locations, velocities and directions of their single-hop radio neighbors. This table provides all information required for CBGR's forwarding decisions, beyond the packets themselves. From this point of view, CBGR make a negligible space cost to improve the routing performance of GRP.

3. Simulation Result

In this section we will compare the performance of CBGR with GRP. The experiments were conducted on OPNet modeler. Medium access control (MAC) is IEEE 802.11g, with a radio range of 250m. The mobility traces were generated on an area of 3000m x1000m using VANetMobiSim [16], a vehicular traffic generator. The micro-mobility is controlled by IDM_IM[17].

For each simulation run, 20% sender-receiver pairs from the network were randomly selected. Each pair exchange 20 packets over 5 seconds. We measured the packet delivery rate (PDR) versus the numbers of vehicles participate in (Figure 4). Each point in the graphs comes out from 10 independent runs. PDR shows good results for our approach compared to GRP. This is because CBGR selects the best suitable node, using the mobility information, to relay the packet to. We can see in the very left part, when network is relatively sparse, CBRG has overwhelming advantage over GRP in PDR, thanks for allowing carrying packet when there is no node to be delivered. The figure illustrates CBGR is stable with a high PDR above 90%, nevertheless the network is dense or sparse.

Figure 5 shows the average number of hops for a packet during routing to its ultimate destination compare with GRP. The reduction in hop count for CBGR is due to not backtracking when come to the dead-end. CBGR keeps the progress the packet has made by last hop, while CBGR obliterate it.

Figure 6 depicts the end-to-end delay. The shorter latency for GRP early in the simulation is the result of small PDR. Packets that do not get delivered to the destination do not contribute to the latency. Thus CBGR gets larger PDR. However it is better to receive something than nothing. When node count reaches more than 100, CBGR gets less latency because of the more reasonable choice of the intermediate nodes under comparable PDR with GRP. Recall that although the choice is based on some extra computing, we arrange the calculating at the time receiving a Hello message rather than the time relaying the packet. Thus the computation cost rarely contributes to the latency.

4. Conclusion

This work aims at improving the route stability in vehicular ad-hoc networks. The simulation results have proved the proposed algorithm adapts itself to VANET in varying node densities. In future, we plan to make the forwarding decision with an overlap of city map. That will make our algorithm perform better in various scenarios.

Acknowledgements

This work was supported by National Natural Science Foundation of China (Grant No. 61309032)Program for Innovation Team Building at Institutions of Higher Education in Chongqing (Grant No. KJTD201310). Scientific and Technological Research Program of Chongqing Municipal Education Commission (KJ1400431)

References

References

[1] Fan Li, Yu Wang. Routing in Vehicular Ad Hoc Networks: A Survey. IEEE Vehicular Technology Magazine. 2007; 2(2): 12-22.

[2] K Katsaros, M Dianati, Z Sun. Survey of Routing Protocols in Vehicular Ad Hoc Networks. Advances in Vehicular Ad-Hoc Networks: Developments and Challenges. 2010: 149-170.

[3] Lochert C, Hartenstein H, Tian J, Fussler H, Hermann, D, Mauve, M. A routing strategy for vehicular ad hoc networks in city environments. 2003. Proceedings of IEEE Intelligent Vehicles Symposium. 2003: 156-161.

[4] Naumov V, Baumann R, Gross T. An evaluation of Inter-Vehicle Ad Hoc Networks Based on Realistic Vehicular Traces. Proc. ACM MobiHoc'06 Conf. 2006: 108-119.

[5] Sanjay K, Dhurandher, Mohammad S Obaidat. GROOV: A Geographic Routing Over VANETs and Its Performance Evaluation. Globecom 2012-Communications QoS, Reliability and Modeling Symposium. 2012: 1670-1675

[6] R Hussey, E Huff, Z Shinwari, V Hnatyshin. A comparative study of proactive and reactive geographical routing protocols for MANET. Proceedings of 12th Int. Conf. on Wireless Netw. 2013: 16.

[7] B Karp, HT Kung. GPSR: greedy perimeter stateless routing for wireless networks. Proc. ACM/IEEE MOBICOM. 2000: 243-254.

[8] Z Li. Geographic routing protocol and simulation. Proceedings of 2nd Int. Workshop on Computer Science and Engineering. 2009: 404-407.

[9] Kim YJ, Govindan R, KARP B, Shenker S. On the Pitfalls of Geographic Routing. Proc. of the 3rd International Workshop on DIALM-POMC. 2005: 34-43.

[10] H Frey, I Stojmenovic. On delivery guarantees of face and combined greedy-face routing in ad hoc and sensor networks. Proceedings of the 12th annual international conference on Mobile computing and networking. 2006: 23-29.

[11] Y Kim, R Govindan, B Karp, S Shenker. Lazy cross-link removal for geographic routing. Proceedings of the 4th international conference on Embedded networked sensor systems. 2006,

[12] Wang Ying, Xu Hui-bin, Cha Dai-feng. A Novel Routing Protocol for VANETS. TELKOMNIKA Indonesian Journal of Electrical Engineering. 2013; 11(4): 2195-2199.

[13] OPNET Modeler. Riverbed Technology, Inc.

[14] Agabriel K, Sokal R. A new statistical approach to geographic variation analysis. Systematic Zoology. 1969; 18: 259-278.

[15] Toussaint G. The relative neighborhood graph of a finiteplanar set. Pattern Recognition. 1980; 12(4): 261-268.

[16] VANetMobisim home. http://VANet.eureeom.fr/.

[17] Vaibhav Godbol. Intelligent Driver Mobility Model and Traffic Pattern Generation based Optimization of Reactive Protocols for Vehicular Adhoc Networks. International Journal of Information and Network Security. 2013; 2(3): 207-215.