Survey on Various Position Based Routing Protocols in Vehicular Ad-Hoc Network

Survey on Various Position Based Routing Protocols in Vehicular Ad-Hoc Network

Annu Kurien, A. Diana

Department of Computer Science and Engineering, Karunya University, Coimbatore, India

Abstract

Vehicular ad hoc network is an evolving technology that would allow vehicles on roads to form an organized network without the aid of a permanent infrastructure. VANET provides the capability for vehicles to wirelessly network with other vehicles nearby on an as-needed basis. With this rapidly changing topology of vehicles there should be an efficient routing protocol to route packets within the network. In this paper, a survey on various position based routing protocols such as CAR, VADD, ACAR, SADV, RIVER in VANET has done. A routing protocol helps to exchange information between nodes in the network. The different methods used by each of the position based routing protocols has discussed here. The goal of the paper is to provide an overview of the existing position based routing protocols in VANET.

Keywords – VANET, position based routing protocol, path discovery, nodes, data delivery delay

1. INTRODUCTION

   The vehicular ad hoc network (VANET) [1] is a novel class of wireless network. This network provides the ability for vehicles to wirelessly network with other vehicles nearby so that new features and applications could be provided to travelers. One of the important characteristic of VANET is that an infrastructure is absent. Intermediate nodes are used to exchange messages between source node and destination node. In vehicular environment, the IEEE 802.11p [2] is the standard for wireless access. The interaction between the nodes takes place through the on-board sensors that are equipped in vehicles which are participating in the network. It employs a dynamically varying network. There should be an efficient routing protocol to route packets within the VANET environment.

   A routing protocol makes the mode for exchanging information between the nodes in the network. It also involves course of actions for establishing a route, forwarding decisions and actions for maintaining routes. It specifies how routers communicate with each other. They spread this information widely to select routes between any two nodes in the network. The routing protocols in VANET could be categorized as topology based routing, cluster based routing, geocast routing, broadcast routing and position based routing.

   The topology based routing protocols [3] use linked information to discover the route and for forwarding packet. They are further classified in to proactive and reactive routing protocols. The proactive routing protocol maintains the next forwarding hop in the background in spite of communication request. The paths between any pair of nodes are maintained by broadcasting the control packets. Each node maintains a table in which the entry indicates the next hop node. Hence there is no route discovery. The reactive routing protocol maintains only the routes that are presently in use. When there is some data to send, they periodically update the routing table. For route discovery they use flooding process which results in more routing overhead.

   In cluster based routing [4], the cluster refers to a group of nodes. Within that cluster a node would be designated as the cluster head and it will broadcast the packet to the cluster. In order to provide scalability in cluster based routing, virtual network infrastructure must be shaped through the clustering of nodes. Network delays and overhead occurs when forming clusters in highly mobile VANET.

   The broadcast based routing protocols [5] are used to communicate the safety related messages. This method is carried out by flooding in which each node rebroadcast the message to other nodes. This makes sure of the arrival of all messages to destination. But it incurs high overhead cost. It performs well when the number of nodes in the network is lesser. When there is

   larger number of nodes in the network, the increased message transmission causes collision and the overall performance degrades.

   The geocast based routing [6] is a location based routing protocol. Each node delivers the packet to all other nodes that are within a specified geographical region which is said to be as zone of relevance. The sender node would not deliver packets to the nodes that are beyond the zone of relevance. It employs multicast routing. In the forwarding zone, it directs the flooding of packet in turn to reduce message overhead and network congestion. The unicast routing could be used to forward the packet in the destination zone.

   The position based routing protocol [7] knows about the position of each and every vehicles in the network. They utilize geographic positioning information [8] in order to select the next forwarding hop. Since they do not exchange link state information and do not maintain established routes, they are robust and promising to VANET. They are classified in to non-delay tolerant network, delay tolerant network and hybrid. The routing protocols that come under non- delay tolerant network do not consider discontinuous connectivity. The delay tolerant network types of routing protocols do consider discontinuous connectivity. The hybrid types of routing protocol consider partial connectivity by combining both non- delay tolerant network and delay tolerant network routing protocols.

   In this paper, the survey focuses on position based routing protocols in VANET.

2. CONNECTIVITY AWARE ROUTING

   Valery Naumov and Thomas R.Gross proposed connectivity aware routing protocol (CAR) [9]. The CAR is based on PGB [10] and AGF [11], intended to provide low overhead routing for inter-vehicle communication in a city and highway environment. This protocol comes under the category of non-delay tolerant network. It has the capability to find associated paths between the source and destination nodes. During the path discovery, it is auto-adjusted on the fly to account for changes. The protocol involves actions such as destination location and path discovery, data packet forwarding along the discovered path, path maintenance with the help of guards, error recovery. Nodes in the network send periodic Hello beacons which maintain their velocity vector information. While receiving Hello beacons, each node makes an entry in its neighbor table. The node records the sender

   of the beacon and set the entry expiration time by estimating its velocity vector and that for its neighbor also. To find a destination and the respective path to it the source node initiates preferred group broadcasting. The destination node could reply or wait for other path discoveries to choose the appropriate path in terms of connectivity and delay. If it is an invalid path, maintenance of the path is handled by means of guards. The guard message includes an id, TTL (time to live), guarded position and radius. On receiving the guard, the node makes entry about the temporary status in its guard table and decrements the TTL whenever the guard is retransmitting. When the target node changes the position, standing guard would be activated. When the target node changes the direction of communication, travelling guard would be activated. Routing errors may occur when there is a communication gap between the intermediate nodes. The protocol manages the routing errors with the aid of timeout algorithm with active waiting cycle and walk around error recovery. The former strategy uses timeout while storing packets and an active waiting cycle. If the location discovery is ineffective, then the walk around error recovery forwards this information to the source node and it starts a new path discovery from its present position. The temporally stored packets would be dropped or send back to the source.

   The advantages of the protocol are that it provides a scalable low overhead routing algorithm for inter- vehicular communication and is able to locate destinations without using any idealized location service. The disadvantages of the protocol are that it could not adjust with different sub-path when traffic environment changes and sometimes unnecessary nodes could be selected as anchor points.

3. VEHICLE ASSISTED DATA DELIVERY

   Jing Zhao and Guohong Cao proposed vehicle assisted data delivery in VANET. Vehicle assisted data delivery protocol (VADD) [12] could forward the packet to the best road with minimum delay in data delivery. This protocol comes under delay tolerant network routing protocol. The protocol employs carry and forward mechanism. The protocol provides a delay model to evaluate the data delivery delay in roads by denoting the vehicle as a node and road as an edge. The vehicles direction represents the traffic direction and the weight of the edge indicates the delay in forwarding packet. Due to the rapidly changing topology, sometimes the packet could not be routed

   along the pre-computed path. Hence dynamic path selection should be executed throughout the packet forwarding process. In order to choose the next hop node for forwarding packet, the VADD protocol has several alternatives. The first one is the Location First Probe (L-VADD) which selects the closest node to the target intersection without considering the travelling direction. This strategy suffers from the loop effect which will have a negative impact on the delivery ratio. The second one is the Direction First Probe (D- VADD) which works by selecting the node that has the same direction. This strategy eliminates the loop effect. Another approach is the Multi-Path Direction First Probe (MD-VADD) which selects multiple nodes going towards the forwarding path. Hence not to miss forwarding to a node that offers a shorter time to the destination. Finally a Hybrid Probe (H-VADD) has been introduced which combines the positive impact of both L-VADD and D-VADD. It uses the L-VADD during the first stage. Later on when a loop is detected, it switches to D-VADD.

   The advantages of the protocol are that it is suitable for multi-hop data delivery and has high packet delivery ratio. The disadvantage is that due to the change of topology and traffic density it might cause large delay.

4. ADAPTIVE CONNECTIVITY AWARE ROUTING

   Q.Yang and etal proposed an adaptive connectivity aware routing protocol (ACAR) [13]. The ACAR consists of selecting an optimal route with the best transmission quality based on statistical and real- time density data. The protocol consists of two essential elements; 1) selecting an optimal route that consists of road segments with best transmission quality and 2) efficiently forwarding packets through the multi-hop path that would perk up the delivery ratio and throughput. Routes are selected based on the statistical information on the road and thereafter a connectivity model is built. Then a transmission quality model is built based on the network connectivity probability and data delivery ratio of packets. In order to avoid statistical density data, on- the-fly information collection algorithm is developed to select the best route. The protocol first computes the data based on the statistical density data from the pre- loaded map. The computed information is added to the packet headers and transmits packets along the selected route. During the packet forwarding to the destination, the network densities of all road segments along the

   path are collected. After collecting the on-the-fly density, the destination node needs to alert the source if there is any difference between the statistical and real- time density data. If so, the source node recalculates the route with the aid of newly collected density information. The packets would be forwarded through multiple hops along the selected route. The next hop will be selected using a metric that reduces the packet error rate by counting the number of successfully delivered packets and the packets that are dropped. This does not incur additional network overhead.

   The advantages of the routing protocol are that it provides higher data delivery ratio and reduced networking overhead. The disadvantage of the routing protocol is that it requires digital map which is comprised of historical data.

5. A STATIC NODE ASSISTED ADAPTIVE ROUTING

   Yong Ding and etal proposed static node assisted adaptive routing protocol (SADV) [14]. The SADV is used to eliminate the delay of message delivery in sparse environment. The protocol utilizes some static nodes at road intersections in a completely mobile vehicular network to help relay data. The protocol allowed each node to calculate the time needed to deliver a message with the aid of GPS system and digital map. The SADV introduced three modules: Static Node Assisted Routing (SNAR), Link Delay Update (LDU), and Multi-Path Data Dissemination (MPDD). SNAR utilized static nodes at intersections to store and forward data through optimal paths. It has chosen the path with the shortest delay to make a message delivery operation, with the aid of static and dynamic nodes. This could be accomplished in two modes; one is an in-road mode which was activated while a message was carried by a dynamic node in the road. A greedy protocol was used to deliver the message to a static node at an intersection. At this stage the intersection mode would be activated. In this mode, the next hop intersection for the message is computed by the static node based on its delay matrix. This could be achieved by saving the packet at a static node and forwarding it when a vehicle that is travelling towards the next hop intersection is found. If there are more than one vehicle is found then the one that is closest to the target will be selected. In order to eliminate the stored messages, the stored packets in a static node are forwarded to a suitable available path. This strategy tries to determine which message needs to be forwarded in favor of minimizing the delivery delay.

   An abstracted graph from the road map in which the delays of expected forwarding path has weighted could be used to determine the optimal path. LDU is to let static nodes obtain a more accurate packet forwarding delay assessment for each link. When a static node receives a message, the entry of a timestamp is made to the message header and the elapsed time is measured. When the message reaches the next static node, the timestamp will be updated. From this the delay for the messages could be determined by maintaining the elapsed time in its buffer. This information could be spread periodically to all other neighboring static nodes.

   The advantage of the protocol is that the data delivery delay is reduced. The disadvantages were that location service devices and digital map were required.

6. A RELIABLE INTER-VEHICULAR ROUTING PROTOCOL

   James Bernsen and D. Manivannan proposed a reliable inter-vehicular routing protocol for vehicular ad hoc networks (RIVER) [15]. The RIVER protocol transmits messages via routes that are considered to be reliable through its traffic monitoring components. In the network, each node maintains a copy of the nearby street layout in its street graph. It is an undirected graph in which vertices of the graph are the points at which street curve or intersect and the graph edges are the street segments between those vertices. The protocol performs real-time traffic monitoring using both active and passive mechanisms. The primary mechanism for active monitoring is probe message. Probe message is a packet that is periodically sent by each node in the network. A node can discover neighboring nodes and their locations via probe messages. The routing is aided by gathering and distributing kowledge regarding the connectivity of edges in the street graph. This could be done with the aid of passive monitoring. The gathered reliability information is shared within the network. This enables to learn about edges of the street graph that are far away from the node. The vital part of the protocol is its ability to calculate approximately the reliability of a particular street edge. This helps to determine the most suitable path from a sender node to a receiver node. Each node assigns a weight to every known edge in its street graph. In this protocol, the edges are weighted with their reliability rating. Dijkstras least weight path algorithm [16] is used to calculate the reliable routing path. The smaller weight indicates greater reliability and a larger weight indicates unreliability. If the next-

   hop recipient could not be found while routing the packet then the route recovery mechanism would be engaged. The failed street edge could be determined by its vertices which consist of the preceding anchor point that was successfully reached and the present anchor point in the route. This edge is marked with maximum weight possible to show it as a disconnected edge. In order to recalculate the route the forwarding node employs Dijkstras algorithm. If the newly recognized anchor paths mean weight is less than the current paths mean weight then the current path is overwritten with the newly recognized anchor path.

   The advantage of the protocol provides highest throughput in most of the traffic densities. The disadvantage of the protocol is that the routing packets header size might grow excessively.

   The table 1 shows the comparison of various position-based routing protocols in VANET.

   Table1: Comparison of various position based routing protocols in vehicular ad-hoc network

   Routing protocol	Methods used	Strength	Limitation
   CAR	Beaconing	Low overhead	When the traffic topology changes could not adjust with different sub-paths
   VADD	Carry and forward	Multi-hop data delivery	Change of topology and traffic density causes large delay
   A-CAR	Vehicle position information	Stable in high mobility environment	Requires digital map consisting of historical data
   SADV	Global positioning service	Minimizing delivery delay	Position services may fail
   RIVER	Real-time traffic Monitoring	Highest throughput	Routing packets header size may grow

7. CONCLUSION

   The purpose of this paper is to compare the various position-based routing protocols in VANET. The survey focuses on the position based routing protocols such as CAR, VADD, ACAR, SADV and RIVER. These protocols involve different methods for real-time traffic density detection. The RIVER protocol employs real-time traffic monitoring using active and passive mechanisms. This provides highest throughput in the network. The survey shows that RIVER protocol has better performance over the other protocols. But more researches have to be conducted in the area of network densities and congestion control.

8. REFERENCES

1. Saif Al-Sultan, Moath M. Al-Doori, Ali H. Al-Bayatti, Hussein Zedan, A comprehensive survey on vehicular ad hoc network, Journal of Network and Computer Applications, vol. 37, 2014, pp. 380-392.

2. Veronica Shivaldova, Georg Maier, Dieter Smely, Nicolai Czink, Arrate Alonso, Andreas Winkelbauer, Alexander Paier, Christoph F. Mecklenbrauker, Performance Evaluation of IEEE802.11p infrastructure to vehicle tunnel measurements, in Proceedings of IWCMC, 2011, pp. 1-5.

3. Mehran Abolhasan, Tadeusz Wysocki, Eryk Dutkiewicz, A review of routing protocols for mobile ad hoc networks, AdHoc Networks, vol.2(1), 2004, pp. 1-22.

4. Sharnjeet Kaur, Dr.Gurpreet Singh Josan, Performance Evaluation of Topology Based Routing Protocols In Vanet, International Journal of Engineering Research and Application, vol.2(5), 2012, pp. 1646-1655.

5. Kapil Baghchandani, Yatendra Mohan Sharma, Exploration of Vanet Mobility models with new Cluster Based Routing Protocol, International Journal of Soft Computing and Engineering, vol.2(6), 2013, pp. 224-227.

6. Uma Nagaraj, Poonam Dhamal, Broadcasting routing Protocols in Vanet, Network and Complex system, vol.1(2), 2011, pp. 13-19.

7. Salim Allal, Saadi Boudjit, Geocast Routing Protocol for Vanet:Survey and Geometry Driven Scheme Proposal, Journal of Internet Services and Information Security, vol.3, 2013, pp. 20-36.

8. James Bernsen, D.Manivannan, Unicast routing protocols for vehicular ad hoc networks: A critical comparison and classification, Pervasive and Mobile Computing, vol.5(1), 2009, pp. 1-18.

9. Vivek Pathak, Danfeng Yao, Liviu Iftode, Securing Location Aware Services Over Vanet Using Geographical Secure Path Routing, Vehicular Electronics and Safety, 2008, pp. 1-8.

10. Valery Naumov, Thomas R.Gross, Connectivity Aware Routing In Vehicular ad hoc network, in Proceedings of INFOCOM, 2007, pp.1-9.

11. Valery Naumov, Rainer Baumann, Thomas Gross, An Evaluation of Inter-Vehicle Ad Hoc Networks Based on Realistic Vehicular Traces, in Proceedings of MobiHoc06, 2006, pp. 108-119.

12. J.Zhao, G.Cao, VADD: vehicle-assisted data delivery in vehicular ad hoc networks, in Proceedings of INFOCOM, 2006, pp.1-12.

13. Q.Yang, A.Lim, S.Li, J.Fang, P.Agrawal, ACAR: adaptive connectivity aware routing for vehicular ad hoc networks in city scenarios, Mobile Networks and Applications, vol.15(1), 2010, pp.36-60.

14. Y.Ding, C.Wang, L.Xiao, A static node assisted adaptive routing protocol in vehicular networks, in Proceedings of the Fourth ACM International Workshop on Vehicular ad hoc networks, 2007, pp.1-9.

15. J.Bernsen and D.Manivannan, RIVER: A reliable inter- vehicular routing protocol for vehicular ad hoc networks, Computer Networks, 2012, pp.3795-3807.

16. E.W.Dijkstra, A note on two problems in connexion with graphs, Numerische mathematik, 1959, pp.269-271.