Keywords
|
| VANET, ITS, dynamic topology, mobility, routing protoco |
INTRODUCTION
|
| Recently, it has been widely accepted by the academic society and industry that the cooperation between vehicles and road transportation systems can significantly improve driver's safety road efficiency and reduce environmental impact. The development of vehicular ad hoc networks (VANETs) has received more attention and research efforts. Much work has been conducted to provide a common platform to facilitate inter-vehicle communications (IVCs).IVC is necessary to realize traffic condition monitoring, dynamic route scheduling, emergency-message dissemination and, most importantly, safe driving [1]. It is supposed that each vehicle has a wireless communication equipment to provide ad hoc network connectivity. VANETs are a subset of MANETs (Mobile Ad-hoc Networks) in which communication nodes are mainly vehicles. As it is involved with vehicles, its arrangement is mobile and eventually dispersed in different roads. |
| In VANETs, vehicles can communicate each other (V2V, Vehicle-to-Vehicle communications) also they can connect to an infrastructure (V2I, Vehicle-to-Infrastructure) to get some service. This infrastructure is located along the roads. Network nodes in VANETs are highly mobile, thus the network topology is ever-changing. Accordingly, the communication link condition between two vehicles suffers from fast variation, and it is prone to disconnection due to the vehicular movements. Fortunately, their mobility can be predictable along the road because it is subjected to the traffic networks and its regulations. VANETs have normally higher computational capability and higher transmission power than MANETs. |
| VANETs applications types are classified into safety and efficiency [2].There are many difficulties in VANETs systems design and implementation, including: security, privacy, routing, connectivity, and quality of services. This paper will focus on routing problem in vehicle to vehicle communication (V2V); discusses some proposed routing solutions, routing protocols classifications, and illustrates some challenges and open issues in VANET routing. The main goal for routing protocols is to provide optimal paths between network nodes via minimum overhead. Many routing protocols have been developed for VANETs environment, which can be classified in many ways, according to different aspects such as: protocols characteristics, techniques used, routing information, quality of services, network structures, routing algorithms, and so on.The rest of the paper is organized as follows: Section 2 presents an overview of VANET, Section 3 presents about the related work, and section 4 provides the comparison of routing protocols and finally section 5 concludes the paper. |
OVERVIEW OF VANET
|
A. Intelligent Transportation System (ITSs)
|
| In intelligent transportation systems, each vehicle takes on the role of sender, receiver, and router to broadcast information to the vehicular network. For communication to occur between vehicles and Road Side Units (RSUs) vehicles must be equipped with some sort of radio interface or On Board Unit (OBU) that enables short range wireless ad hoc networks to be formed [3].In ITS vehicles are provided with Global Positioning System (GPS) or a Differential Global Positioning System (DGPS) receiver for location prediction. Fixed RSUs, which are connected to the backbone network, must be in place to facilitate communication. For example, some protocols require road side units to be distributed evenly throughout the whole road network; some require road side units only at intersections, while others require road side units only at region borders. Though it is safe to assume that infrastructure exists to some extent and vehicles have access to it intermittently, it is unrealistic to require that vehicles always have wireless access to roadside units. Inter-vehicle, vehicle-to-roadside, and routing-based communications rely on very accurate and up-to-date information about the surrounding environment which in turn, requires the use of accurate positioning systems and smart communication protocols for exchanging information. |
B. Architecture of the Vehicular Network
|
| As shown in Figure 1, the architecture of VANETs falls in three main categories: |
| Inter-vehicle communication: This is also known as vehicle-to-vehicle (V2V) communication or pure ad hoc networking. In this category, the vehicles communicate among each other with no infrastructure support. Any valuable information collected from sensors on a vehicle can be sent to neighbouring vehicles. |
| Vehicle-to-road side communication: This is also known as vehicle-to-infrastructure (V2I) communication. In this category, the vehicles can use cellular gate ways and wireless local area network access points to connect to the Internet and facilitate vehicular applications. |
| Inter-road side communication: This is also known as hybrid vehicles-to-roadside communication. Vehicles can use infrastructure to communicate with each other and share the information received from infrastructure with other vehicles in a peer-to-peer mode through ad hoc communication. This architecture includes V2V communication and provides greater flexibility in content sharing. |
C. Special Characteristics of Vanet
|
| The feature of VANET mostly resembles the operation technology of MANET in the sense that the process of self-organization, self-management, low bandwidth and shared radio transmission criteria remain same. But the key hindrance in operation of VANET comes from the high speed and uncertain mobility of the mobile nodes (vehicles) along the paths [1]. Moreover, VANETs have unique attractive features over MANETs as follows: |
| Higher transmission power and storage: The network nodes (vehicles) in VANETs are usually equipped with higher power and storage than those in MANETs. |
| Higher computational capability: Operating vehicles can afford higher computing, communication and sensing capabilities than MANETs. |
| Predictable Mobility: Unlike MANETs, the movement of the network nodes in a VANET can be predicted because they move on a road network. If the current velocity and road trajectory information are known, then the future position of the vehicle can be predicted. |
D. Challenges in VANET
|
| VANET supports diverse range of on road applications and hence requires efficient and effective radio resource management strategies. [4] This includes QOS control, capacity enhancement, interference control, call admission control (CAC), bandwidth reservation, packet loss reduction, packet scheduling and fairness assurance. Theexisting approaches designed for MANETs are ineffective and/or inefficient and cannot be directly applied in VANET. To accomplish various applications in a vehicular environment, new and effective strategies are required to be tailored specifically meant for VANET. Following are the key research challenges in VANET: - |
| Frequent Link Disconnections: As discussed in the previous section that unlike nodes in MANETs, vehicles are highly mobile and generally travel at higher speeds, especially on highways (i.e., over 100 km/hr) and thus changes the topology of a network which causes intermittent communication links between a source and a destination. Moreover, the network resources allocated to vehicles go in vain due to frequent link disconnections. |
| Node Distribution: In the real world, vehicles are not uniformly distributed in the given region [5]. Hot spots like commercial district and shopping centres can attract more people, which results in higher node densities in these areas. The heterogeneous distributions of vehicles raise a great challenge for design of routing algorithms. |
| Inter-contact time and duration time: Inter-contact time [5] characterizes the distribution of the interval between two inter-vehicle contacts. The network connectivity is better if the inter-contact time is smaller. The duration time of a contact decides the amount of data can be transmitted within a contact, which is typically small, in the scale of seconds. |
RELATED WORK
|
A. Routing Protocols of VANET
|
| VANETs are a specific class of ad hoc networks; the commonly used ad hoc routing protocols initially implemented for MANETs have been tested and evaluated for use in a VANET environment. Use of these address-based and topologybased routing protocols requires that each of the participating nodes be assigned aunique address. This implies that we need a mechanism that can be used to assign unique addresses to vehicles but these protocols do not guarantee the avoidance of allocation of duplicate addresses in the network. Thus, existing distributed addressing algorithms used in mobile ad hoc networks are much less suitable in a VANET environment. Specific VANET related issues such as network topology, mobility patterns, density of vehicles at different times of the day, rapid changes in vehicles arriving and leaving the VANET and the fact that the width of the road is often smaller than the transmission range all make the use of these conventional ad hoc routing protocols inadequate. The routing protocol of VANET can be classified into two categories such as Topology based routing protocols & Position based routing protocols. Topology based routing is further classified into Proactive and Reactive Protocols [1]. |
B. Proactive Routing Protocols
|
| Proactive protocols allow a network node to use the routing table to store routes information for all other nodes, each entry in the table contains the next hop node used in the path to the destination, regardless of whether the route is actually needed or not. The table must be updated frequently to reflect the network topology changes, and should be broadcast periodically to the neighbours. This scheme may cause more overhead especially in the high mobility network. However, routes to destinations will always be available when needed. Proactive protocols usually depend on shortest path algorithms to determine which route will be chosen; they generally use two routing strategies: Link state strategy and distance vector strategy. |
| Destination Sequenced Distance Vector(DSDV):Destination Sequenced Distance Vector is a Proactive routing protocol that solves the major problem associated with the Distance Vector routing of wired networks i.e., Count to-infinity, by using Destination sequence numbers[6]. Destination sequence number is the sequence number as originally stamped by the destination. The DSDV protocol requires each mobile station to advertise, to each of its current neighbours, its own routing table (for instance, by broadcasting its entries).The entries in this list may change fairly dynamically over time, so the advertisement must be made often enough to ensure that every mobile node can almost always locate every other mobile node. In addition, each mobile node agrees to relay data packets to other nodes upon request. At all instants, the DSDV protocol guarantees loop free paths to each destination. Routes with more recent sequence numbers are always preferred as the basis for making forwarding decisions, but not necessarily advertised. Of the paths with the same sequence number, those with the smallest metric will be used. The routing updates are sent in two ways: a “full dump” or incremental update. A full dump sends the full routing table to the neighbours and could span many packets whereas, in an incremental update only those entries from the routing table are sent that has a metric change since the last update and it must fit in a packet. When the network is relatively stable, incremental updates are sent to avoid extra traffic and full dump are relatively infrequent. The update can be time periodic or event periodic. |
| Optimized Link State Routing Protocol (OLSR): OLSR protocol implement the link state strategy; it keeps a routing table contains information about all possible routes to network nodes. Once the network topology is changed each node must send its updated information to some selective nodes, which retransmit this information to its other selective nodes. The nodes which are not in the selected list can just read and process the packet. Some researchers thought that OLSR has easy procedure which allows it to built-in different operating systems, besides it works well in the dynamic topology, also it is generally suitable for applications that required low latency in the data transmission (like warning applications). |
| However, OLSR may cause network congestion; because of frequent control packets which sent to handle topology changes, moreover OLSR ignore the high resources capabilities of nodes (like transmission range, bandwidth, directional antenna and so on). Therefore, some researchers propose Hierarchical Optimized Link State Routing (HOLSR) protocol as enhancement of the OLSR protocol, which decreases routing control overhead in the large size networks, also maximizes the routing performance; by the defining network hierarchy architecture with multiple networks [7]. Also some researchers propose QOLSR as a solution of providing a path such that the available bandwidth at each node on the path is not less than the required bandwidth. QOLSR considers delay as a second for path selection .These protocols usually provide average enhancement for the QOS of packets. However, they cause more complexity, increasing packet overhead, and only suitable for some limited applications. |
| Fisheye State Routing (FSR): It is a proactive or table driven routing protocol where the information of every node collects from the neighbouring nodes. Then calculate the routing table. It is based on the link state routing & an improvement of Global State Routing [8].FSR is similar to LSR, in FSR node maintains a topology table (TT) based upon the latest information received from neighbouring and periodically exchange it with local neighbours. For large networks to reduce the size of message the FSR uses the different exchange period for different entries in routing tables. Routing table entries for a given destination are updated preferably with the neighbours having low frequency, as the distance to destination increases.The problem with the FSR routing is that with the increase in network size the routing table also increases. As the mobility increases route to remote destination become less accurate. If the target node lies out of scope of source node then route discovery fails [9]. |
C. Reactive (On Demand) Routing Protocols
|
| Reactive routing protocols such as Dynamic Source Routing (DSR), and Ad hoc On-demand Distance Vector (AODV) routing implement route determination on a demand or need basis and maintain only the routes that are currently in use, thereby reducing the burden on the network when only a subset of available routes is in use at any time. Communication among vehicles will only use a very limited number of routes, and therefore reactive routing is particularly suitable for this application scenario. |
| Ad Hoc on Demand Distance Vector (AODV): In AODV routing, upon receipt of a broadcast query (RREQ), nodes record the address of the node sending the query in their routing table. This procedure of recording its previous hop is called backward learning. Upon arriving at the destination, a reply packet (RREP) is then sent through the complete path obtained from backward learning to the source. At each stop of the path, the node would record its previous hop, thus establishing the forward path from the source. The flooding of query and sending of reply establish a full duplex path. After the path has been established, it is maintained as long as the source uses it [10]. A link failure will be reported recursively to the source and will in turn trigger another query-response procedure to find a new route. |
| Temporally Ordered Routing Algorithm (TORA):TORA belongs to the family of link reversal routing in which directed a cyclic graph is built which directs the flow of packets and ensures its reachability to all nodes. A node would construct the directed graph by broadcasting query packets. On receiving a query packet, if node has a downward link to destination it will broadcast a reply packet; otherwise it simply drops the packet. A node on receiving a reply packet will update its height only if the height of replied packet is minimum of other reply packets. The advantages of TORA is that the execution of the algorithm gives a route to all the nodes in the network and that it has reduced far reaching control messages to a set of neighbouring nodes. However, because it provides a route to all the nodes in the network, maintenance of these routes can be overwhelmingly heavy, especially in highly dynamic VANETs [9]. |
| Dynamic Source Routing (DSR): It uses source routing, that is, the source indicates in a data packet’s the sequence of intermediate nodes on the routing path. In DSR, the query packet copies in its header the IDs of the intermediate nodes that it has traversed. The destination then retrieves the entire path from the query packet (source routing), and uses it to respond to the source. As a result, the source can establish a path to the destination. If we allow the destination to send multiple route replies, the source node may receive and store multiple routes from the destination. An alternative route can be used when some link in the current route breaks. In a network with low mobility, this is advantageous over AODV since the alternative route can be tried before DSR initiates another flood for route discovery. There are two major differences between AODV and DSR.The first is that in AODV data packets carry the destination address, whereas in DSR, data packets carry the full routing information. This means that DSR has potentially more routing overheads than AODV.Furthermore, as the network diameter increases, the amount of overhead in the data packet will continue to increase. The second difference is that in AODV, route reply packets carry the destination address and the sequence number, whereas, in DSR, route reply packets carry the address of each node along the route. |
D. Position Based Routing Protocols
|
| Position or geographic routing protocol is based on the positional information in routing process; where the source sends a packet to the destination using its geographic position rather than using the network address. This protocol required each node is able to decide its location and the location of its neighbours through the Geographic Position System (GPS) assistance. The node identifies its neighbour as a node that located inside the node’s radio range. When the source need to send a packet, it usually stores the position of the destination in the packet header which will help in forwarding the packet to the estimation without need to route discovery, route maintenance, or even awareness of the network topology . Thus the position routing protocols are considered to be more stable and suitable for VANET with a high mobility environment, compared to topology-based routing protocols. |
| Motion Vector Routing Algorithm (MOVE): MOVE algorithm is designed for light networks, especially for road side vehicle communication. This protocol assumes that eachnode has global locations information, that's beside the knowledge of a mobile router speed and its neighbouring nodes velocity. From this information the node can estimate the nodes which are the closest distance to the destination. In this protocol each node regularly broadcasts a HELLO message; and its neighbour replays by a RESPONSE message; by this replayed message the node will know its neighbours and their locations. Given this information, the node can estimate the shortest distance to destination, in that case the node decides how to forward the message according to the information about nodes which are currently located nearby the destination. MOVE protocol uses less memory size compared with Non DTN positionbased routing; it also has a higher data transmission rate in light environments [2]. However, Non DTN position-based routing could have better performance only if the routes are stable and consistent. |
| Geographic Source Routing (GSR): Earlier GSR was used in MANET. Then it was improved to use in VANET scenario by incorporating into it greedy forwarding of messages toward the destination. If at any hop there are no nodes in the direction of destination then GPSR utilizes a recovery strategy known as perimeter mode. The perimeter mode has two components one is distributed planarization algorithm that makes local conversion of connectivity graph into planar graph by removing redundant edges. Second component is online routing algorithm that operates on planer graphs. So in VANET perimeter mode of GPSR is used. In GPSR if any obstruction occurs then algorithm enter into perimeter mode and planner graph routing algorithm start operations, it involves sending the message to intermediate neighbour instead of sending to farthest node, but this method introduces long delays due to greater no. of hop counts. Due to rapid movement of vehicles, routing loops are introduced which causes dissemination of messages to long path. |
COMPARSION OF ROUTING PROTOCOLS
|
| The various protocols are compared based on important parameters and tabulated below |
 |
CONCLUSION
|
| Routing is one of the most important parameter in inter-vehicle communication (IVC) and vehicles to infrastructure communications (V2I). Thus this paper has presented an overview about the various routing protocols of VANET.The paper also characterizes the advantages and limitations of the protocols by comparing the different parameters. Through this study we have represented about the open issues and challenges involved in various VANET protocols. We hope that this paper will be an instrument for the students and researchers to address the challenges involved in VANET protocols. |
Figures at a glance
|
 |
| Figure 1 |
|
| |
References
|
- Mahmoud HashemEiza, Qiang Ni, Thomas Owens and Geyong Min “Investigation of routing reliability of vehicular ad hoc networks”EURASIP Journal on Wireless Communications and Networking 2013, pp.179 , 1 July 2013
- MarwaAltayeb and ImadMahgoub “A Survey of Vehicular Ad hoc Networks Routing Protocols” International Journal of Innovation andApplied Studies, Vol. 3 No. 3, pp. 829-846, July 2013
- SheraliZeadally, Ray Hunt, Yuh-Shyan Chen Angela Irwin, Aamir Hassan “Vehicular ad hoc networks (VANETS): status, results,and challenges”Telecommunation System, EURASIP Journal on Wireless Communications and Networking.
- Rakesh Kumar and Mayank Dave “A Review of Various VANET Data Dissemination Protocols” International Journal of u- and e- Service,Science and Technology, Vol. 5, No. 3, September, 2012
- Yanmin Zhu1, Chao Chen1 and Min Gao“An evaluation of vehicular networks with real vehicular GPS traces”EURASIP Journal onWirelessCommunications and Networking 2013,pp.190, 13 July 2013
- Avdhesh Kumar Sharma “Ad-Hoc Network” International Journal of Engineering Research & Technology (IJERT) Vol. 2 Issue 7, July – 2013.
- Yun-Wei Lin, Yuh-Shyan Chen And Sing-Ling Lee “Routing Protocols in Vehicular Ad Hoc Networks:A Survey and Future Perspectives”Journal Of Information Science and Engineering 26,pp 913-932 (2010)
- Bijan Paul, Md. Ibrahim, Md. Abu NaserBikas“VANET Routing Protocols: Pros and Cons”International Journal of Computer Applications,Volume 20– No.3, April 2011
- V. Namboodiri and L. Gao, “Prediction-based routing for vehicular ad hoc networks,” IEEE Trans. Veh. Technol., vol. 56, no. 4, pp. 2332–2345,Jul. 2007
- T. Taleb, M. Ochi, A. Jamalipour, N. Kato, and Y. Nemoto, “An efficient vehicle-heading based routing protocol for VANET networks,” inProc.IEEE Wireless Commun. Netw. Conf., 2006, pp. 2199–2204.
|
Menu