A Delay-Based Optimum Routing Protocol Scheme for Collision Avoidance Applications in Vanets
In:
Submitted By neethus Words 4169 Pages 17
A Delay-based Optimum Routing Protocol Scheme for
Collision Avoidance Applications in VANETs
Gayathri Narayanan1,a, Neethu Sathianadhan2,b and Sruthi Sanjiv Gangadharan3,c
1,2,3 Department of Electronics and Communication Engineering
Amrita School of Engineering, Amritapuri Campus
Kollam – Kerala, India agayathrin@am.amrita.edu, bneethu91ammu@gmail.com, csruti.sanjiv_g@ymail.com
Abstract — Broadcast transmissions are currently finding extensive applications in vehicular ad-hoc networks, albeit primarily in the research phase. Given the importance of knowing the updated network details of each node in the network, and also considering the fact that the delay in transmission of messages is a crucial factor in collision avoidance, it is imperative to implement a broadcast network which will ensure minimum delay in transmission of messages between the nodes. In this paper, we primarily implement a multi-hop broadcast vehicular network for collision avoidance. We consider the mobility and traffic density of vehicles and simulate the end-to-end delay in message transmission for a sparse and dense network scenario. In order to ensure high reliability and get the optimum delay, we extend the scenario to include three different routing protocols – AODV, Cluster-based routing and OSPF – and perform a comparison based on the end-to-end transmission delay to determine the optimum routing algorithm. In order to account for all possibilities, the case of link failure as a consequence of sparse network scenario is also considered.
Introduction
Broadcasting is an integral communication technique that can be widely implemented in vehicular ad hoc networks. In particular, ad-hoc networks depend largely on the MAC layer’s broadcast for routing, neighbor discovery and data dissemination. Broadcasting of messages can be considered to be an integral component of VANETs, particularly for the requirement of avoiding possible collision between nodes, by the exchange of safety related alarm and beacon messages [1]. The increasing rates of motor vehicle crashes demand improvements in the transportation systems to provide higher road safety. With the advent of express highways, the occurrence of chain collision is ever increasing and therefore there is a need for effective collision avoidance/warning techniques.
Vehicles enabled with communication capability can send warning messages to other nodes in its proximity and thereby avoid the occurrence of accidents or other emergency incidents. The prompt availability of these messages ahead of time will give the driver sufficient time to react and avoid pile-up accidents. For this, two types of transmission mechanisms can be used among the nodes in the network – single hop and multi-hop transmission. In a single hop transmission scheme, only two nodes are involved at a time contrary to which a multi hop network considers the message being transmitted from the source to the destination through a sequence of intermediary nodes. Much of the literature focuses on modeling the VANET as a single hop network. Although the analytical modeling of a single hop network is easier, a single hop network will not suffice to model a realistic vehicular ad hoc network. VANETs are basically networks where the density of nodes varies largely with respect to time. Over a particular stretch of the highway, daytime and peak hours may experience dense traffic whereas at other times the nodes form a sparse network. This offers one limitation of considering a multi-hop network scenario in that a reliable multi hop communication scenario can be considered only at a particular density of nodes, where there are enough nodes in each other’s proximity to form a multi-hop network [10]. Taking all these factors into consideration, in this work, we implement the network as a multi hop broadcast network modeling both the dense and the sparse scenario separately.
The primary focus of this work is to compare the performance of the routing protocols that are used in VANETs with respect to the end-to-end delay obtained between the source and destination node. We consider the following routing protocols – AODV, Cluster-based routing and OSPF - and choose the optimum routing protocol that can be implemented to achieve minimum delay and maximum reliability for vehicular networks catering to collision avoidance applications. Most of the early analytical studies focused on the performance analysis of unicast transmissions. The two-dimensional Markov chain model developed by Bianchi [2] is the pioneering work in this direction. [3] carries out a survey of the routing protocols and discusses its issues with respect to VANETs. [4] deals with the performance analysis of AODV routing protocol alone. The authors of [5] models emergency messages in a cluster-based network. There are numerous papers that have addresses delay issues in a vehicular network [6]. Several research works also deal with the comparison of various routing protocols used in vehicular networks [7], [10]. [7] implements the comparison for the specific case of city traffic scenarios. [10] also addresses the comparison including the delay optimization for urban environments. Both these works are carried out using NS2 simulation environment. Even though many of the works compare various routing protocols and evaluate the delay as a performance measure, the cluster based routing has not been incorporated in any of the performance comparisons while incorporating the network constraints for both the dense as well as sparse network scenarios.
In this paper, we implement a multi-hop broadcast network where nodes have the capability to communicate with each other using broadcast messages. The transmission of messages in the network is achieved using three routing protocols- AODV, Cluster-based and OSPF – and the end-to-end delay incorporating many network constraints is obtained. The simulation is carried out using Matlab. This work also addresses and implements some of the obstacles to reliable reception of messages, like the hidden terminal problem, the problem of link failure in case of sparse networks etc. Rest of the paper is organized as follows: The system model is presented in Section II. In Section III, we present the comparison of the routing protocols and the simulation results. The paper is concluded in Section IV. System Model
System Implementation Scenario: A 3-lane bidirectional highway of length 2 km is modeled using Matlab. It is assumed that the vehicles (nodes) are arriving at a specified traffic rate. The vehicles, which are travelling at different velocities, are randomly placed on each lane. The velocities of vehicles follow Poisson distribution, with an average velocity of 60 km/hr. The highway is modeled as being monitored every 10 seconds. The vehicles are assumed to arrive with an average inter-arrival time of ‘L’ seconds. The network is modeled as a sparse or a dense network by suitably varying the inter-arrival rate. A dense network is modeled with an inter-arrival rate of L=0.3 seconds and a sparse network is modeled with a value as large as 0.9 seconds. Assuming that the network will have an average of ‘n’ vehicles in the highway at any instant, mobility is incorporated by locating the position of the nodes every 10 seconds. For low traffic densities, the distance headway implies exponential distribution for inter-vehicle spacing, while for a dense highway the distance headway implies normal distribution.
The network so modeled conforms to the Dedicated Short Range Communications to transmit safety messages. DSRC is allocated 75 MHz of spectrum at 5.9 GHz to support safety-critical communication applications [1]. Since safety messages have a greater precedence compared to messages transmitted for comfort and gaming applications, it will be transmitted with higher priority. DSRC channel supports a data rate of 6 to 54 Mbps with a transmission range up to 300 m. Typically, safety messages require only a low bandwidth and have a size of a few hundreds of bytes (about 200-500 bytes).
When on-board sensors detect an accident or a sudden deceleration/break, the information is carried via an emergency message to all vehicles in the area exposed to potential danger, i.e., to the Zone of Relevance (ZOR). The ZOR extends on either side of the source vehicle along the highway. Initially, to calculate the total broadcasting delay, we assume that the network is static. Under this assumption, the total delay incurred in broadcasting a message from a source node to a destination node is calculated. However, it is imperative to consider mobility and random behaviors of vehicles on the highway in order to model a realistic VANET. Taking into account the randomness in the mobility and the realistic movement of vehicles, the total broadcasting delay is calculated by summing up the delays caused by all intermediate transmissions.
Hidden Terminals and DCF: The hidden terminal issue is a common phenomenon due to the multi-hop nature of ad-hoc networks [9]. Interference is caused by nodes that do not fall in the range of the transmitting node. The hidden terminal problem can be best illustrated using Fig. 1. Here, when node A is transmitting data to node B, the hidden terminal problem occurs when a third node C, which is unaware of the ongoing transmission, attempts to transmit, thereby causing packet collision.
Fig. 1 Hidden Terminal Scenario
The IEEE 802.11 standard DCF/MAC protocol uses the RTS/CTS mechanism to tackle this issue [2]. The primary medium access control technique used in IEEE 802.11 is called Distributed Co-ordination Function (DCF) [1]. Retransmission of collided packets is managed according to binary exponential back-off rules. The default scheme is a two-way handshaking technique called basic access mechanism which is characterized by data and acknowledgement transmissions. Some broadcast schemes use only the basic access mechanism [2]. But in order to ensure reliability, this work implements the four way handshaking scheme, the RTS/CTS mechanism. Before transmitting a packet, a station reserves the channel by sending a Request-to-Send frame. The destination acknowledges the receipt of the RTS frame by sending back a Clear-to-Send (CTS) frame. The RTS/CTS scheme is designed in the 802.11 protocol to combat the so-called problem of Hidden Terminals, which occurs when pairs of mobile stations are unable to hear each other.
Routing Protocols: In this work, we choose three routing protocols – AODV, Cluster-based routing and OSPF - and compute the end-to-end delay for each of the three cases with respect to the system model and network scenario mentioned above. AODV is one of the most commonly used routing protocols in VANETs. The cluster-based routing protocol divides the highway into a groups or clusters of vehicles. In this protocol, all vehicles need not be involved in broadcast transmissions depending upon their location at that instant. Only nodes at the center and the perimeter of the cluster are involved in transmissions [5]. OSPF protocol is based on the shortest path (Dijkstra) algorithm with neighbor discovery. Literature finds comparisons between various other routing protocols but this work particularly chooses the Cluster-based routing protocol and OSPF to be compared with AODV since the primary focus is on optimizing delay for collision avoidance.
Simulation results
Network Model and Implementation of Routing Protocols: In this section, we simulate the 3-lane bidirectional highway scenario as mentioned in the previous section. The simulations are carried out in Matlab. The highway is modeled with an average of 50 vehicles at a given instant. The transmission of emergency messages are considered in both forward as well as reverse direction with respect to the direction of motion of the vehicle depending upon where it finds its immediate neighbor.
The maximum transmission range of the vehicles is taken to be 300 m. The packet size is taken as 200 bytes and the delay is computed for data rates of 6, 9, 24, 36 and 54 Mbps. Fig. 2 shows the mobility of nodes in a sparse network. The nodes are represented using numbers and the node number shows the location of the node on the stretch of highway.
####################### First set of figures with larger size #######################
Fig. 2 Mobility in a Sparse Network
Fig. 3 Mobility in a Dense Network
##################### 2nd set of figures with reduced size ##########################
Fig. 2 Mobility in a Sparse Network
Fig. 3 Mobility in a Dense Network
Fig. 3 represents the mobility model for a dense network scenario. Here also, the vehicles are denoted by numbers and their positions on the highway are indicated using the node number.
Fig. 4 shows the specific case of routing using AODV protocol for a dense network scenario. The AODV routing protocol is made reliable by including acknowledgement from the destination node to the source once the message packet is received by the last node. The size of the acknowledgement packet is 10 bytes, very less compared to the size of the safety message. The total delay for successful transmission includes the delay for the transmission of the warning messages as well as the acknowledgement. In Fig. 4, we also observe that the route is established between node 50 on lane 4 with node 1 on lane 1. This particular simulation corresponds to the worst case scenario where the source and destination nodes are maximally separated for a given number of ‘n’ vehicles.
Fig. 4 AODV routing for a dense network
Fig. 5 Cluster-based routing in a dense network
In cluster based routing, the entire length of the highway is divided into small clusters. A cluster head is chosen for each cluster. As far as possible, the node chosen as the cluster head should be at the geographic centre of the cluster and the clusters are formed such that the adjacent cluster heads are separated by a distance equal to maximum transmission range of vehicles. Only the cluster heads are allowed to retransmit the message [5],[8]. In case the clusters alone cannot carry out successful transmission, nodes located close to the perimeter of the clusters (gateways) are used for transmitting the message to the nearest cluster head. Fig. 5 shows the bi-directional highway divided into clusters and a route being established between a source and destination node at a specific instant of time. It is observed that the route is established between node 45 on lane 4 and node 7 on lane 1. It can also be seen that the transmissions are in the hands of the cluster heads, which are nodes located at the center of each cluster, and gateways, which are nodes at the edge of each cluster on the same lane as the cluster head.
OSPF routing protocols makes use of Dijkstra’s algorithm to find the shortest available path from source to destination. The connections between all nodes are plotted using this algorithm, with the weights of each link representing the number of hops. The shortest distance path is found for end-to-end transmission and the delay is calculated. Fig. 6 shows the interconnectivity between all the nodes in the network for the specific case of a sparse network. The simulation for OSPF in Fig. 6 is carried out using NS2 simulations since the interconnectivity can be represented better. However, for the purpose of numerical delay computation, OSPF simulations were carried out in Matlab also.
Fig.6 Dijkstra’s graph for a sparse network showing node locations and interconnections between the nodes
Delay Computation and Comparison of Routing Protocols: This section presents the results for the delay computation corresponding to the implementation of the three routing protocol algorithms. The end-to-end delay has been computed and simulated for each of the three routing protocols for the standard DSRC data rates. Fig. 7 shows the behavior of the delay with increasing number of vehicles for data rates of 6 Mbps, 9 Mbps and 24 Mbps. The blue curve corresponds to the delay for AODV routing protocol, the green curve corresponds to OSPF and the red curve indicates the delay obtained for Cluster-based routing.
Fig. 7 Comparison of delay at data rates 6 Mbps, 9 Mbps and 24 Mbps.
Fig. 8 Comparison of delay at data rates 36 Mbps and 54 Mbps
Fig. 8 plots the delay computed corresponding to the three routing protocols for data rates of 36 Mbps and 54 Mbps. From Fig. 7 and Fig. 8, it is evident that (1) the end-to-end transmission delay decreases as the data rate increases and (2) the transmission delay increases with increase in the number of vehicles in the highway. Table I shows the numerical values of delay obtained corresponding to the implementation of the three routing protocols for different data rates considering the mobility model, network scenario and system limiting factors as explained in the previous section. From Table I, Fig. 7 and Fig. 8, it is evident that the AODV protocol, though widely used in ad hoc networks, yields the maximum delay as compared to the Cluster-based routing and OSPF. Cluster-based routing protocol incurs minimum delay. This can be attributed to the fact that in Cluster-based routing all the nodes are not involved in the transmission of the message.
TABLE I
DELAY COMPUTATION FOR AODV, CLUSTER-BASED AND OSPF ROUTING PROTOCOL FOR DIFFERENT DATA RATES
Fig. 8 plots the delay computed corresponding to the three routing protocols for data rates of 36 Mbps and 54 Mbps. From Fig. 7 and Fig. 8, it is evident that (1) the end-to-end transmission delay decreases as the data rate increases and (2) the transmission delay increases with increase in the number of vehicles in the highway. Table I shows the numerical values of delay obtained corresponding to the implementation of the three routing protocols for different data rates considering the mobility model, network scenario and system limiting factors as explained in the previous section. From Table I, Fig. 7 and Fig. 8, it is evident that the AODV protocol, though widely used in ad hoc networks, yields the maximum delay as compared to the Cluster-based routing and OSPF. Cluster-based routing protocol incurs minimum delay. This can be attributed to the fact that in Cluster-based routing all the nodes are not involved in the transmission of the message.
The sparse network scenario was also simulated and the obtained results are presented in the following figures. The sparse network is associated with the occurrence of the ‘link failure’ condition where, due to non-availability of nodes, a reliable link cannot be established between the source and the destination. The smooth transmission of the emergency message packets are hindered due to link failures. Link failures are identified when the source node or an intermediate transmitting node doesn’t receive back an acknowledgement within a specified waiting time. In such cases, the message has to be retransmitted by the source node. The node which has not received the acknowledgement generates a notification and sends it to the source node to inform that a link has failed. On the reception of such a notification, the source node retransmits the message. The time taken to send the notification and the time for retransmitting the message is added to the total delay. Retransmission continues till the acknowledgement is received by the source.
The sparse network scenario is implemented for the AODV routing protocol. The AODV protocol is chosen since, in this protocol, acknowledgements are expected by the transmitting node in order to ensure reliability and hence is more suitable for a sparse network. Fig. 9 shows the implementation of a sparse network and link failure as explained above, where the message packet needs to be transmitted by node 5 on lane 2 to node 20 on lane 1. But for this node configuration on the highway, the transmission stops at node 9 since it does not detect a neighbor in its vicinity. Fig. 10 shows how the route is re-established once node 9 detects node 10 in its neighborhood and then continues the packet transmission.
Fig. 9 Case of Link Failure in a Sparse Network
Fig. 10 Route is re-established when a neighbor is detected in a Sparse Network
Summary
In this paper, we considered a multi hop broadcast network and evaluated the end-to-end delay in packet transmission between source and destination nodes by implementing the AODV, Cluster-based routing and OSPF protocol. It was observed that as the number of nodes increases, the network becomes denser and hence, the end-to-end transmission delay increases. Although the AODV protocol is more reliable, it incurs a higher transmission delay. Cluster-based routing exhibits minimum delay but yields poor performance in sparse network as it is was not possible to locate cluster heads and gateway nodes to establish a complete link between the source and destination. The OSPF routing has an initial delay for route discovery and therefore the total delay is less than that in AODV but more than that of Cluster-based routing. In view of our findings, we emphasize that there needs to be a trade-off between obtaining minimum delay and high reliability. So, for a given vehicular network scenario, it is optimum to employ a switched routing scheme which implements Cluster-based routing for dense networks and AODV routing protocol for sparse networks.
References
[1] Q. Xu, R. Sengupta, T. Mak and J. Ko, “Vehicle-to-vehicle safety messaging in DSRC”, Proceedings of the 1st ACM International Workshop on Vehicular Ad-hoc Networks , pp. 19-28, 2004 [2] G. Bianchi, “Performance analysis of the IEEE 802.11 distributed coordination function,” IEEE Journal on Selected Areas in Communications, vol 18, no. 3, pp.535-547, March 2000. [3] J. Kakarla, S.S. Sathya, B. Govinda Laxmi and B. Ramesh Babu, ”A Survey of Routing Protocols and its Issues in VANETs”, International Journal of Computer Applications, vol. 28, no. 4, August 2011 [4] B. Ramakrishnan, “Performance Analysis of AODV Routing Protocol in Vehicular ad hoc network Service Discovery Architecture”, ARPN Journal of Systems and Software, vol. 2, no. 2, February 2012. [5] K. Abboud and W. Zhang, “Modeling and Analysis for Emergency Messaging Delay in Vehicular Ad hoc Networks,” Global Telecommunications Conference, pp 1 - 6, December 2009. [6] A. Skordylis and N. Trigoni, “Delay bounded routing in Vehicular Ad hoc networks”, Proceedings of the 9th ACM International Symposium on Mobile Ad hoc Networking and Computing, pp. 341 -350, 2008. [7] S. Jaap, M. Bechler and L. Wolf, “Evaluation of Routing Protocols for VANETs in City Traffic Scenarios”, Proceedings of the 11th EUNICE Open European Summer School on Networked Applications, pp 584–602, 2005. [8] R. Lakshmi Devi, C.Maheswari, L. Maria, “A Cluster-based Authentic Vehicular Environment for Simple Highway Communication”, International Conference on Information and Network Technology, ICINT 2012, vol.37 [9] J.Yoo and C. Kim, “On the Hidden Terminal Problem in Multi-rate Ad hoc Networks”, Information Networking, Convergence in Broadband and Mobile Networking, Lecture Notes in Computer Science, vol. 3391, pp. 479-488, 2005. [10] J. Haerri, F. Filali and C. Bonnet, ”Performance Comparison of AODV and OLSR in VANETs Urban Environments under Realistic Mobility Patterns”, Proceedings of 5th IFIP Mediterranean Ad-hoc Networking Workshop, Med-Hoc-Net, 2006.
