International Journal of Scientific & Engineering Research Volume 4, Issue3, March-2013 1
ISSN 2229-5518
Study of Efficient Routing Protocols for VANET
Vimmi A Gajbhiye, Ratnaprabha W. Jasutkar
Abstract: Vehicular Ad hoc Networks is a kind of special wireless ad hoc network, which has the characteristics of high node mobility and fast topology changes. VANET provides a distinguished approach for Intelligent Transport System (ITS).The Vehicular Networks can provide wide variety of services, range from safety-related warning systems to improved navigation mechanisms as well as information and entertainment applications. These additional features make the routing and other services more challenging and cause vulnerability in network services. These problems include network architecture, vanet protocols, routing algorithms, as well as security issues. In this paper, we provide a review for the researches related to existing and emerging routing protocols in VANET. This paper discusses the following types of protocols for VANET; Topology Based, Positioned Based, Geo Cast, Broad Cast, Cluster Based Protocols ,Swarm Intelligence based and Delay tolerant based protocols.
Keywords—, VANET , Routing protocols Swarm intelligence, DTN
—————————— ——————————
1. INTRODUCTION
A Mobile Ad-hoc Network (MANET) is comprised of a group of mobile nodes which have the capability of self organization in a decentralized fashion and without fixed infrastructure [1]. A Vehicular Ad hoc Network (VANET) is an example of a MANET where the mobile nodes are the vehicles themselves. Communication is possible between vehicles within each other’s radio range as well as with fixed road side infrastructure components. The VANET concept is an integral part of the intelligent transportation system (ITS) architecture [2], which aims to improve road safety, optimize traffic flow, reduce congestion, and so on. VANETs are special case of MANETs [3].
————————————————
2. Routing Protocol
In VANET, the routing protocols are classified into five categories: Topology based routing protocol, Position based routing protocol, Cluster based routing protocol,
Geo cast routing protocol and Broadcast routing protocol. These protocols are characterized on the basis of area / application where they are most suitable.
Topology based routing protocols use link’s information within the network to send the data packets from source to destination. These routing protocols use links information that exist in the network to perform packet forwarding. Topology based routing approach can be further categorized into proactive (table-driven) and reactive (on- demand) routing.
On-demand routing protocols are designed to reduce the overheads in Table-Driven protocols by maintaining information for active routes only as and when required.
IJSER © 2013 http://www.ijser.org
International Journal of Scientific & Engineering Research Volume 4, Issue3, March-2013 2
ISSN 2229-5518
Figure 1. Classification of routing protocols for VANET including Swarm Intelligence based routing protocol
(1)Ad-hoc On-demand Distance Vector Routing
AODV is a reactive protocol in which the routes are created only when they are needed. It uses traditional routing tables.In AODV, when a source node send data trafic to a destination node, firstly it initiates a a route discovery process. In AODV, when a source node send data trafic to a destination node, firstly it initiates a a route discovery process. In this process, the source node broadcasts a Route Request (RREQ) packet. Neighbor nodes which do not know an active route for the requested destination node forward the packet to their neighbors until an active route is found or the maximum number of hops is reached. When an intermediate node get the active route to the requested destination node, it sends a Route Reply (RREP) packet back to source node in unicast mode. Eventually, the source node receives the RREP packet and opens the route.
Ad-hoc On-demand Multipath Distance Vector Routing (AOMDV) protocol is an extension to AODV protocol for computing multiple loop-free and link disjoint paths [6]. AOMDV protocol is useful for VANET with high performance. However, the performance of AOMDV is much better than AODV [5], [6]. AOMDV can find node-disjoint paths and link disjoint paths when discovering routes. Because the conditions of node-disjoint paths are much stricter than that of link-disjoint paths, the number of node- disjoint paths is less than that a link-disjoint paths. Thus link-
disjoint policy is used more popular. AOMDV is a good
routing protocol for scenarios with high mobility and the performance of AOMDV is much better than AODV [5].
SD-AOMDV is a VANET routing protocol . SD-AOMD improves the most important on demand multipath routing protocol AOMDV to suit VANET characteristics. SD-AOMDV add the mobility parameters: speed and direction to hop count as new AOMDV routing metric to select next hop during the rout discovery phase. SD-AOMDV has outperformed AOMDV in city and highway with different traffic scenarios.
HAODV routing protocol inherits the advanced properties of table-driven routing protocol and on-demand routing protocol. So that, it meet the communication requirements as fast setting up connection link, reliable link, reducing broken link, and increasing network throughput.
QoSBeeVanet is a reactive, distributed and topology-based protocol focuses on a quality of service routing protocol suitable to the VANET. QoSBeeVanet outperforms the standard proactive and reactive routing protocols DSDV and AODV in terms of end-to-end delay and packet delivery ratio[10].In addition, it provides an acceptable normalized overhead load measure . QoSBeeVanet protocol is more
adequate to the transmissions in realistic vehicular networks
IJSER © 2013 http://www.ijser.org
International Journal of Scientific & Engineering Research Volume 4, Issue3, March-2013 3
ISSN 2229-5518
which require the QoS guarantees compared to DSDV and
AODV.
Pro-active or Table-Driven routing protocols require each node to maintain up-to-date routing information to every other node (or nodes located within a specific region) in the network
The Optimized Link State Routing Protocol (OLSR) [3,4] is a proactive routing protocol. It is introduced by the IETF MANET working group for mobile ad-hoc networks for accuracy and stability. OLSR protocol is the enhanced version of pure link state routing protocol that chooses the optimal path during a flooding process for route setup and route maintenance. In OLSR, only symmetric links are used for route setup process. The key concept here is the selection of Multipoint Relays (MPR) among one-hop neighbors such that they cover all two-hop neighbors.
Stable Routing Protocol (SRP) for highway scenario uses segment-by-segment way. Each node in the SRP protocol
maintains a k-hop vicinity routing table. When a source node
and a destination node are in the same vicinity, it adopts proactive routing. Otherwise, the route is carried according to location-based way. SRP protocol outperforms Greedy Perimeter Stateless Routing (GPSR) in terms of average path length and average packet delivery ratio. When node density is moderate, the SRP protocol consumes some acceptable routing overhead to achieve good performance.
This protocol is for having bandwidth aggregation in the hybrid VANET environment such that a better collaborate video streaming service in the ”fleet scenario” can be achieved. PMCS maintains the topology among fleet member nodes proactively. By giving member nodes higher priority to forward the data, the special driving pattern exists in fleet members is going to benefit the routing because the links between member nodes are more stable than others; by maintaining member nodes and suitable nonmember nodes, PMCS can reduce some control overhead.
The hybrid protocols are introduced to reduce the control overhead of proactive routing protocols and decrease the initial route discovery delay in reactive routing protocols.
In ZRP the network is divided into overlapping zones. The zone is defined as a collection of nodes which are in a zone radius. The size of a zone is determined by a radius of length α where α is the number of hops to the perimeter of the zone. In ZRP, a proactive routing protocol (IARP) is used in intra- zone communication and an inner-zone reactive routing protocol (IARP) is used in intra-zone communication. Source sends data directly to the destination if both are in same routing zone otherwise IERP reactively initiates a route discovery.
Cluster based routing is preferred in clusters. A group of nodes identifies themselves to be a part of cluster and a node is designated as cluster head will broadcast the packet to cluster. Good scalability can be provided for large networks but network delays and overhead are incurred when forming clusters in highly mobile VANET. The various Clusters based routing protocols are COIN, LORA-CBF, TIBCRPH, CBDRP[4,15].
(1)CBDRP: Cluster-Based Directional Routing Protocol [15]
It divides the vehicles into clusters and vehicles which are moving in same direction form a cluster. The source sends the
IJSER © 2013 http://www.ijser.org
International Journal of Scientific & Engineering Research Volume 4, Issue3, March-2013 4
ISSN 2229-5518
message to its cluster header and then it forwards the message to header which is in the same cluster with the destination. At last the destination header sends the message to the destination. The cluster header selection and maintenance is same like CBR but it considers velocity and direction of a vehicle.
Special environments and applications cause that VANET can not use the exiting protocols well. In [24] the author utilize the exiting traffic infrastructures to cluster the network effectively and make use of the handoff idea of cellular networks to propose a new protocol dubbed TIBCRPH which is special for VANET. TIBCRPH always performs well no matter how node density and speed change which is better than some traditional routing protocols.
Epidemic routing has been proposed as a routing protocol based on Store-Carry-Forward mechanism for VANET environment. However, in epidemic routing, network resources such as packet buffer of a node are significantly consumed because data packets are spread across the network. Therefore, Yasuharu OHTA, Tomoyuki OHTA, and Yoshiaki KAKUDA proposed a new autonomous clustering- based data transfer scheme using positions and moving direction of vehicles for VANETs. The autonomous clustering configures multiple clusters in the network and then only the cluster head that manages the cluster stores data packets. Whenever the cluster meets a new cluster, the cluster head of the cluster decides whether it should forward data packets to the new cluster based on Vehicle Information consisting of its own position, the destination node’s position, and moving direction of the cluster.
Position based routing consists of class of routing algorithm. They share the property of using geographic positioning information in order to select the next forwarding hops. Position based greedy V2V protocols, Delay Tolerant Protocols are two types of it.
In greedy strategy and intermediate node in the route forward message to the farthest neighbor in the direction of the next destination. Greedy approach requires that intermediate node should possessed position of itself, position of its neighbor and destination position. The goal of
these protocols is to transmit data packets to destination as
soon as possible that is why these are also known as min delay routing protocols. Various types of position based greedy V2V protocols are GSR, GPSR, SAR, GPCR, CAR, ASTAR, STBR, CBF, DIR and ROMSGP.
EBGR (Edge Node Based Greedy Routing) is a greedy position based routing approach to forward packet to the node present in the edge of the limited transmission range of forwarding node as most suitable next hop, with consideration of nodes moving in the direction of the destination.
.
Geo cast routing is basically a location based multicast routing. Its objective is to deliver the packet from source node to all other nodes within a specified geographical region (Zone of Relevance ZOR). The various Geo cast routing protocols are IVG, DG-CASTOR and DRG
It is a reliable geographical multicast protocol where only control packets are broadcasted in the network and the data packets are unicasted. The objective of the protocol is to send a message to all other vehicles within a specified Zone of Relevance (ZOR). The ZOR is defined as a rectangle specified by its corner coordinates. A message is defined by the triplet [A,M, Z] it indicates specified application, message and identity of a zone respectively. When a vehicle receives a message, it accepts the message if it is within the ZOR. It also defines a Zone of Forwarding (ZOF) which includes the source and the ZOR.
within the region.
Broadcast routing is frequently used in VANET for sharing, traffic, weather and emergency, road conditions among vehicles and delivering advertisements and announcements. The various Broadcast routing protocols are BROADCOMM, UMB, V-TRADE, and DV-CAST,EAEP.
IJSER © 2013 http://www.ijser.org
International Journal of Scientific & Engineering Research Volume 4, Issue3, March-2013 5
ISSN 2229-5518
(1)DV-CAST: Distributed vehicular broadcast protocol[4]
It uses variable to check whether the packet is redundant or not. This protocol divides the vehicles into three types depending on the local connectivity as well connected, sparsely connected, totally disconnected neighborhood local topology information by using the periodic hello messages for broadcasting the information.
DECA is a reliable and efficient broadcast protocol for data dissemination. The protocol does not require GPS but uses store-and-forward technique and employs local density information (number of neighbors) to make decision on forwarding. A source node or a precursor selects a neighbor with the highest density to be the next rebroadcasting node. This neighbor is responsible for rebroadcasting the message immediately without waiting time. By this mechanism, number of nodes that receive the message in one transmission can be maximized. This is because cars on the real traffic always form groups. DCA can outperform other protocols.
It uses adaptive beacon[18] to get neighbors' position and velocity. When nodes want to broadcast messages, they will select the neighbors in preferred distance to rebroadcast the message. The preferred distance is based on the distance between nodes and selector nodes. The selected node will rebroadcast the message immediately. In case the selected nodes do not rebroadcast the message, other nodes which have set waiting timeout since they received message will do this task instead. The waiting timeout is calculated depend on the distance between node and precursor node. So a node that is closest to selected node will rebroadcast the messages. POCA also piggybacks the message identifier to beacon to handle intermittent connectivity. Nodes can know if the neighbors miss some messages and rebroadcast the message to them by set waiting timeout. So a node in the same road section will rebroadcast the messages to neighbors.
The DADCQ protocol utilizes the distance method to select forwarding nodes. This protocol helps in achieving high reach-ability and low bandwidth consumption in urban and highway scenarios with varying node density and fading intensity.
Routing in delay-tolerant networking concerns itself with the ability to transport, or route, data from a source to a destination, which is a fundamental ability all communication networks must have. Delay and disruption-tolerant networks (DTNs) are characterized by their lack of connectivity, resulting in a lack of instantaneous end-to-end paths. In these challenging environments, popular ad hoc routing protocols such as AODV and DSR fail to establish routes. This is due to these protocols trying to first establish a complete route and then, after the route has been established, forward the actual data. However, when instantaneous end-to-end paths are difficult or impossible to establish, routing protocols must take to a "store and forward" approach, where data is incrementally moved and stored throughout the network in hopes that it will eventually reach its destination. Epidemic Routing and Spray and Wait do not need any information about the network state. In Prophet and Mobyspace, nodes can memorize contact history and use it to make more informed forwarding decisions.
Epidemic Routing protocol is basically a flooding mechanism for message delivery in a mostly disconnected network with mobile nodes. It relies on exchanges of messages between nodes whenever they get in contact with each other to deliver the messages to their destinations. Each node have a buffer containing messages that have been generated at the current node as well as messages that has been generated by other nodes and relayed to this node. When two nodes initiate a contact, they exchange their summary vectors in the anti- entropy session. [26].
Spray and Wait is a zero-know-ledge routing protocol to reduce the wasteful flooding of redundant messages in a DTN [6]. Spray and wait like epidemic routing, forwards copy of messages to other nodes met randomly during connection in a mobile network. Spray and Wait disseminates a number of copies of the packet to other nodes in the network, and then waits until one of these copies meets the destination [9].
In PROPHET (Probabilistic Routing Protocol using History of Encounters and Transitivity), a single copy history-based routing algorithm for DTNs is introduced. Each node in PROPHET estimates a delivery predictability vector containing an entry for each other node. A probabilistic
metric called delivery predictability estimates the probability
IJSER © 2013 http://www.ijser.org
International Journal of Scientific & Engineering Research Volume 4, Issue3, March-2013 6
ISSN 2229-5518
that node A will be able to deliver a message to node B. The delivery predictability vectors are maintained at each node A for every possible destination B. Predictability vectors will be used to decide on packet forwarding. When two nodes
contact each other, node if the delivery predictability for the destination of the message is higher at the other node, a message is forwarded to the other. In addition to the predictability vector, a summary vector of stored packets will be also exchanged upon contact. The information in the summary vector is used to decide on which messages to request from the other node. The entry updates process whenever each contact and works as follows. Nodes that are often within mutual ranges have high delivery predictability for each other, and as they increase their corresponding delivery predictability entries. Nodes that rarely connect are less likely to be good forwarders of messages to each other, therefore they will reduce their corresponding delivery predictability entries [27].
A virtual Euclidean space named MobySpace in which two nodes with a small distance between them are more likelyto have a contact than two nodes that are further apart[24].Therefore the forwarding algorithm makes decision to forward a message during a contact to a node that has a shorter distance to the message destination. Messages take paths through the MobySpace to bring become to near to the destination. Different distance functions have been proposed to measure node’s mobility. The MobyPoint of a node is not related to its physical GPS coordinate[30].
Here the comparison of these protocols is shown in given table 1 which compares the protocols on basis of following terms, Scenario, Routing maintenance, Routing type, simulator. Among this scenario the proactive routing protocol works best in highway scenario and reactive in urban scenario.
Routing is an important issue in Vehicular Adhoc network.. Designing an efficient routing protocol for all VANET applications is very difficult. Hence a survey of different VANET protocols essential to come up with new proposals for VANET. Thus this paper has come up with an exhaustive survey and comparative study on recent trends in routing protocol of different classes of VANET routing protocols. We also discussed Delay tolerant, greedy position and the Swarm Intelligence based routing protocols. The chapter discusses the newly proposed approaches for routing in VANET. From the survey it is clear that Delay Tolerant Routing and swarm
intelligence are also reliable for most of the applications in
VANET.
REFERENCES
[1] M. Rydstrom, A. Toyserkani, E. Strom, A. vensson, “Towards a Wireless Network for Traffic Safety Applications”, Proc. Radio and Communication, pp. 375-380, Linkoping, Sweden, 2005.
[2] Jun Luo and J.-P. Hubaux, “A Survey of Inter-Vehicle Communication”, Proc. Embedded security in Cars-Securing current and Future Automotive IT applications, pp. 164-179, Springer- Verlag, October 2005.
[3] Wischhof, L. and H. Rohling 2005, Congestion control in vehicular ad
hoc networks, IEEE International Conference on Vehicular Electronics and
Safety, 2005.5
[4] Maowad, H. Shaaban, “ Efficient routing protocol for Vehicular A d hoc networks” [IEEE ICNSC 2012, Cairo, Egypt]
[5] C. Perkins,S. DasnRFC Ad hoc On-Demand Distance Vector (AODV) Routing, July 2003,7
[6] Mahesh K. Marina, Samir R. Das. “ Ad hoc on-demand multipath
distance vector routing”, Wirel. Commun. Mob. Comput. 2006
[7] Hafez Maowad, Eman Shaaban,”Enhancing AOMDV Routing Protocol for V2V Communication” Recent Researches in Communications, Information Science and Education,Egypt,2012
[8]Salim Bitam and Abdelhamid Melloukr,” QoS Swarm Bee Routing
Protocol for –hoc network “,[IEEE ICC 2011]
[9]K.Chauhan1 , Arzoo Dahiya ,”AODV Extension using Ant Colony
Optim zation for Scalable Routing in VANETs”, VOL. 3, NO. 2, February
2012 ISSN 2079-8407 Journal of Emerging Trends in Computing and
Information Sciences.
[10] Suman Banik, Bibhash Roy, Biswajit Saha and Nabendu Chaki,
“Design of QoS Routing Framework based on OLSR Protocol,” ARTCOM
2010, Kochin, Kottyam Kerala, IEEE Explorer, pp-171-73, 2010.
[11] Yun Ge, Xin Fan, Xing Wang, “A stable Routing Protocol using
Segment-by-Segment way in VANET”, School Of Software, Nanchang
330063, China, 2012, International conference on Computer Science & IT.
[12] Chung-Ming Huang ,Tzu-Hua Lin,Cheng-Hsiu Chang ,”The Proactive Member-Centric Routing Protocol Using the Several Strategy (PMCS) for the Fleet Scenario in the Hybrid VANET”,2012 Fukuoka-shi, Japan, IEEE 26th International Conference on Advanced Information
Networking and Applications (AINA), 2012.
[13]Kevin,Uichin Lee, Mario Gerla, “Survey of Routing Protocols in Vehicular Ad Hoc Networks in Car 2 Car communication consortium” USA,2011
[14] Le Van Minh, Guo Qing, Yang Ming Chuan, “Novel Hybrid Routing
Protocol for Vehicular Ad-hoc Network”, 2011( ICST CHINA)
[15] Tao Song,” A Cluster-Based Directional Routing Protocol in
VANET”, IEEE Trans, China k, 2010(ICCT)
[16] Tiecheng Wang, Gang Wang,”TIBCRPH: Traffic Infrastructure Based
Cluster Routing Protocol with Handoff in VANET” ©2010 IEEE
[17] Yasuharu OHTA, Tomoyuki OHTA, and Yoshiaki KAKUDA,” An Autonomous Clustering-based Data Transfer Scheme Using Positions and Moving Direction of Vehicles for VANETs”, IEEE Trans. 2010
[18] K. Prasanth, Dr. K. Duraiswamy, K. Jayasudha, Dr.C.Chandrasekar,
”Edge Node Based Greedy Routing for VANET with Constant Bit Rate Packet Transmission” ,International Journal of Recent Trends in Engineering, Vol 2, No. 4, November 2009
[19]M. Kihl, ”Reliable Geographical Multicast Routing inVehicular Adhoc
Networks”, 2007.
[20] M. Slavik, and I.Mahgoub, ”Spatial disribution and channel quality adaptive protocol for multi-hop wireless broadcast routing in vanet,” IEEE Transactions on Mobile Computing, 2010
IJSER © 2013 http://www.ijser.org
International Journal of Scientific & Engineering Research Volume 4, Issue3, March-2013 7
ISSN 2229-5518
[21] N. Na Nakom, and K. Rojviboonchai, "DECA: Density-Aware Reliable Broadcasting in Vehicular Ad-Hoc Networks," IEEE the 7th ECTICON20IO, Chiang Mai, Thailand, May 19-21,2010.
[22]K. Na Nakom and K. Rojviboonchai, "POCA : Position-Aware Reliable Broadcasting in VANET," to be appear in Proc. the 2nd Asia- Pacific Conference of Information Processing APCIP20IO, Nanchang, China, September ,2010
[23] Michael Slavik,Imad Mahgoub,”Spatial Distribution and Channel Quality Adaptive Protocol for Multi-Hop Wireless Broadcast Routing in VANET”,IEEE Trans,2012
[24] Ramin Karimi, Norafida Ithnin ,Shukor Abd Razak , Sara
Najafzadeh,” DTN Routing Protocols for VANETs: Issues and Approaches” , IJCSI International Journal of Computer Science Issues, Vol. 8, Issue 6, No 1, November 2011
[25] Vahdat, A. and Becker, D., Epidemic Routing for Partially Connected
Ad Hoc Networks, in Technical Report, April 2000.
[27] Anders Lindgreny Avri Doria,”Probabilistic Routing in
Intermittently Connected Networks, 2003
[28] S. S. Manvi, M. S. Kakkasageri “Performance Analysis of AODV, DSR, and Swarm Intelligence Routing Protocols In Vehicular Ad hoc Network Environment “, ICFCC 2009
[29]George Adam, Patras, Greece “Performance Evaluation of Routing
Protocols for multimedia transmission over Mobile Ad hoc Networks”
IFIP 2011
[30]Jérémie,” Evaluating MobySpace-based routing strategies in delay- tolerant networks: Research Articles”, December 2007
Protocol | Scenario | Routing maintenance | Routing type | Strategy | Mobility Model | Simulator |
AODV | urban | Reactive | Unicast | Wireless multihop | IDM on Manhattan grid | Ns2 |
AOMDV | urban | Reactive | Unicast | Wireless multihop | Random Waypoint mobility model | Ns2 |
SD-AOMDV | Highway | Reactive | Unicast | Wireless multihop | VanetMobisim | Ns2 |
QoSBeeVanet | urban | Reactive | multipath | Wireless multihop | realistic propagation model | Ns2 |
OLSR | urban | Proactive | Unicast | Wireless multihop | Two Ray Ground | Ns2 |
SRP | Highway, urban | Proactive | Store & forward | location-based | Two Ray Ground, VanetMobisim | Ns2 |
PMCS | Highway | Proactive | Broadcast | Wireless multihop | Fleet Mobility model | Ns2 |
ZRP | urban | Hybrid | Broadcast | Wireless multihop | --------- | -------- |
HAODV | Highway/urban - | Reactive | Unicast | homogeneous hops | ------------- | Simulator in JAVA |
DV-CAST | Highway | Proactive | Broadcast | Store-carry - forwarding | Ricean fading propagation model | NS2 |
VLSI, Embedded system and wireless Network.
IJSER © 2013 http://www.ijser.org
International Journal of Scientific & Engineering Research Volume 4, Issue3, March-2013 8
ISSN 2229-5518
IJSER © 2013