- Open Access
- Total Downloads : 33
- Authors : Manish Kumar , Shubham Pathak , Neha Singh , Mansi Kasera
- Paper ID : IJERTV7IS040358
- Volume & Issue : Volume 07, Issue 04 (April 2018)
- Published (First Online): 27-04-2018
- ISSN (Online) : 2278-0181
- Publisher Name : IJERT
- License: This work is licensed under a Creative Commons Attribution 4.0 International License
A Distributed Approach to Adhoc on Demand Vector Link Routing Protocol for Vanet
Department of Computer Science and Engineering. Galgotias College of Engineering and Technology Greater Noida, Uttar Pradesh, India
Department of Computer Science and Engineering. Galgotias College of Engineering and Technology Greater Noida, Uttar Pradesh, India
Department of Computer Science and Engineering. Galgotias College of Engineering and Technology Greater Noida, Uttar Pradesh, India
Abstract – In several papers, analytical calculations of the mean value of the end-to-end delay in highway vehicular
ad-hoc networks (VANETs) have been presented. Unfortunately, none of these papers presented calculations of the probability stribution of this delay, which is necessary to give probabilistically guaranteed upper bounds on the end-to-end delay in such VANETs. In a previous work , we scovered the first analytical framework for the calculation of the probability stribution, and not only the mean, of the end-to-end delay in multi-lane one-way highway vehicular ad-hoc networks (VANETs). This made it possible to provide guarantees of transmission in a given time frame with known confidence. In this paper, that previous work is extended to two-way multi-lane highways by taking into consideration vehicles travelling in both rections.
The probability stribution of the end-to-end delay is calculated herein and its dependence on system parameters such as speed stributions in the two rections, communication range, and vehicle densities, are analyzed. Computer simulations are used to verify the analytical model. The good agreement between simulation results and the analytical calculations demonstrates the correctness and accuracy of the proposed analytical model.
Vehicle networks have very unique characteristics due to the nature of the vehicles, namely, the mobility, storage capacity, and battery life. However, there are many challenges in the reliability of such networks due to the highly rapid topology change. This paper proposes Connecting Autonomous Vehicles (CAV), which is a new decentralized approach for routing autonomous vehicles in order to enhance network coverage. Routes for vehicles are decided based on a cooperative game theoretic problem. We show that allowing the autonomous vehicles to cooperate in a game theory approach enhances the overall network connectivity in a geographical area. We evaluate and validate our design using simulations. The results show that CAV enhances the network connectivity, as it improves it up to 140% compared to regular VANET, while minimally compromising the average travel stance for vehicles.
Index Terms Vehicular Network, VANET, Probability Density Function, End-To-End Delay, Two-Way, Analytical
Vehicular ad-hoc networks have witnessed great advancements over the past decade, and an extensive amount of research has been de cated to improve the performance of these networks. In VANETs, the connectivity is categorized to be either between vehicles (i.e. V2V) or between vehicles and infrastructure (i.e. V2I). The main objective of VANETs, the connectivity is categorized to be either between vehicles (i.e. V2V) or between vehicles and infrastructure (i.e. V2I). The main objective of VANET is the vehicle. In literature, the vehicle is considered to be an or nary vehicle with fferent sensors and connectivity devices. However, over the past few years, vehicles have witnessed great advancements in their electronic hardware and capabilities, which led to the introduction of autonomous vehicles. Autonomous vehicles are becoming a reality in the recent years. For example, BMW has started testing autonomous vehicles since 2005 . Tesla has its new models completely equipped with autonomous vehicle hardware . In these types of vehicles, the path is decided based on the best available routes that minimizes the travel stance and time.
In this paper, we aim to manipulate the route selection in order to provide a reliable VANET in geographical areas such as cities and highways. This is achieved through a stributed game theoretic approach named CAV. The premise of CAV is that it allows the autonomous vehicle to change its route slightly and decide on what is the best possible street to select to the destination based on the objective of enhancing the connectivity of the whole VANET. This can be demonstrated through figure 1. The dotted circles around the (a) (b) (c)
Fig. 1: Possible choices for vehicles arriving at intersections, which can lead to the vehicle stribution in (b) or (c). vehicle represent the communication range of the vehicles. If two vehicles are approaching an intersection as in figure 1a, in normal circumstances, they will take the routes that lead to their destination faster, as in figure 1b, however, in CAV, they will take the route that lead to maximizing the network coverage as in figure 1c.
Fig. 1: Possible choices for vehicles arriving at intersections, which can lead to the vehicle stribution in (b) or (c).
This paper is organized as follows: we start by scussing the motivation to solve this problem, followed by the related work regar ng vehicular network performance optimization and the game theory techniques. Following that, we scuss CAV in details, and present the simulation results to validate it. We conclude the paper with a scussion and conclusion.
Routing Protocols Classification
First, In  the authors classify VANET routing protocols into three principal groups: Position-based greedy V2V protocols, this approaches use information about the geographic coor nates nodes to generate an efficient route through the network. In the greedy forwar ng strategy, an interme ate node forwards messages to the farthest neighbor in the rection of the next destination. Delay tolerant protocols, in delay tolerant networks DTN, router are replaced with DTN nodes, that can store and later forward packets, if a link is down a DTN node will hold the packet until the link comes back up, this store and forward mechanism may handle sruptions in the end-to-end path, so all packets can get through. Delay Tolerant Networking is an emerging field that attempts to develop a networking philosophy revolving around asynchronous message delivery with custody transfer for networks that are subject to long delays and frequent sconnections. Motion Vector routing algorithm MOVE  and Vehicle Assisted Data Delivery VADD  are delay tolerant routing protocols. Quality of service protocols, this category attempt to provide a robust route among vehicles. Factors such as link delay, node velocity and trajectory, node position, the stance between nodes, and reliability of links, all contribute to the stability of a particular route. The MultiHop Routing Protocol for Urban VANET, MURU  and Pre ction-Based Routing algorithm PBR  is most aptly described as a set of Â«Best effortÂ» routing protocols.
The main motivation behind CAV is that fixed communication infrastructure and cellular networks have been suffering from two main serious problems, which caused many researchers to investigate the possibility of fin ng other alternatives.
The first issue isthe cost of installation and maintenance of the infrastructure unit, and the second is the usage overload of pre- existing communication infrastructure due to the advancements in current smart phones and mobile data usage, and the influx of new customers. Amongst many proposed solutions, some researchers have suggested using a device- todevice architecture , while others have suggested offloa ng the cellular data onto the pre-existent wi-fi network .
VANET is a new technology that has, recently, been utilized to carry the burden off the cellular network. However, it suffers from instability in the communication links between vehicles due to the rapid vehicle topology changes. Extensive research has been conducted to enhance the connectivity in vehicular networks. However, much of the existing research utilize infrastructure for V2I communication to provide reliable network connectivity. Although Road Side Units (RSUs) are deployed for VANETs connectivity, they utilize existing infrastructure such as cellular networks being their backbone. However, this is not practical for the existing overloaded cellular network. Hence, although dependence on RSU has been suggested in literature , , this approach is not practical or easily scalable.
Hence, in CAV, we approach the VANET connectivity problem through controlling autonomous vehicles, to improve the overall connectivity of the vehicular network by bridging the gaps between travelling vehicles. If this is proved to be possible, and the VANET could provide reliable and stable connectivity, then it can provide an effective solution to carry the burden off the cellular network, similar to the proposal in . To achieve this, a decentralized game theory approach has to be devised that can manage to re- stribute autonomous vehicles over a certain geographical area to provide better connectivity, which is what we propose in CAV.
K.Tanjida authors have proposed Pro-AODV (Proactive AODV), which is a routing protocol that uses information from the AODV routing table to minimize congestion in VANET. In Pro-AODV, the routes scover process is done proactively. Each vehicle checks the number of entries in its routing table before broadcasting an RREQ packet. If the number of entries in the routing table is max, then, the vehicle drops the message with a certain probability p otherwise, the vehicle broadcast the message.
DongjieZhu DT-AODV (DTN-based on-demand routing protocol) is proposed and which is based on AODV routing protocol, taking into account the store-carry-forward strategy. The author has also developed a mobility model for vehicular network. DT-AODV allows the scovery and construction of roads only on demand, which avoids unnecessary information exchange and reducing the overhead of perio c control messages. Experimental comparisons show that, DT-AODV is more suitable for VANET than other reactive classical routing protocol.
A.Chinnasamy  authors have scussed the dynamic trust based approach, in which, association between nodes used to resist sinkhole attacks connected to ad hoc networks. The trust model is integrated on AODV routing protocol. Simulation results prove that the proposed scheme increases the routing security and encourages the nodes to cooperate in the ad hoc structure and isolate the malicious nodes from the active data forwar ng and routing.
The performance of vehicular networks has been the focus of literature for many years. However, in reserach, the improvement of VANET coverage was proposed to be achieved through the control of the location of the road side units (RSUs). In , the authors present a framework to optimize the locations of the RSUs and minimize the total cost to deploy and maintain them. However, they do not consider the maximum transmission delay. This was stu ed in , where the authors considered the movement of the vehicles in order to study the spatial propagation of information in VANET, and proposed a placement strategy for RSUs. Other authors presented similar ideas , , .
In the scope of controlling robots or authonomous vehicles, many algorithms and approaches have been presented in literature in order to plan the path or the trajectory of robots in dynamic environments. Some of these approaches utilized game theory. In , the authors scuss a multi-target searching scenario using a multi-robot system in a dynamic environment. However, this proposed algorithm is restricted only to the searching environment it was experimented on, it does not apply to the highly dynamic environment of vehicles.
On further exploration of the effect of nodes behavior on the network overall performance, the authors in  presented a stributed game that can be an effective mechanism for solving fferent stributed tasks, with the goal of achieving a uniform node stribution among the Mobile Ad-Hoc Networks (MANET) nodes over a given geographical space.
In this paper, we present an approach that improves the vehicular network coverage that is based on game theory, and unlike any previous work, provides a solution to the networkcoverage problem that is low cost.
CONNECTING AUTONOMOUS VEHICLES (CAV)
CAV is a game theoretic approach in which vehicles work cooperatively in order to improve the overall network connectivity; instead of each vehicle considering only its own interest which is to take the shortest possible path from its initial location to reach its destination.
Fig. 1: Example of right-connected (gray) vehicle
Fig. 2: Example of (gray) vehicle which is not right-connected
Fig. 3: Example of right-traveling right-connected (gray) vehicle
Fig. 4: Example of (gray) vehicle which is right-traveling, but not right connected to the next right-traveling vehicle
Vehicle routes environments are either a highway scenario or a city scenario. In the highway scenario, the vehicle travels in an almost straight path on the highway, and only makes a decision of whether to exit the highway or not. The highway scenario will utilize the control of the inter-vehicle stance in CAV. However, in a city scenario, the setting is more complicated.
Inter-vehicle stance (IVD): In IVD, the autonomous vehicles maintain the maximum inter-vehicle stance allowed that does not srupt the connectivity between the adjacent vehicles. The vehicles will self-organize based on their communication range in order to provide the maximum possible covered geographical stance on a street. This is demonstrated in figures 2a and 2b. In figure 2a, the vehicles do not self organize, which limits the stance covered by their connectivity, contrary to figure 2b.
City environment: In the city environment, the vehicles utilize the game theory approach, presented in the next section, to make a decision on which route to select at every intersection.
This decision is based on three factors or objectives:
Which selection increases the overall network coverage.
The impact of that selection on the travel stance.
What other decisions will be made by other vehicles at the same intersection.
Game Theory Approach
When a vehicle starts its trip, with a specific destination, it initially starts its route by computing the shortest path to the destination. The vehicle traverses this route till it reaches an intersection, at which, it has a set of options (i.e. streets) to select from. In CAV, the vehicle makes the decision of which street to select by following a game theoretic algorithm to compute a utility matrix for all its optional routes and then picks the route with the highest utility.
However, due to the fact that the vehicle is accompanied with other vehicles approaching the same intersection, these vehicles have to cooperate with each other. This cooperation is important in order to prevent the vehicles from selecting the same route simltaneously and waste any of the vehicles connectivity range that could have contributed to the overall network connectivity.
This scenario can be modeled as a multi-player cooperative non zero-sum game . The overall game is considered a sequence of static games at each screte time; where players (i.e. vehicles) are required to solve this static game based on their stinct observations, each considering its destination. Each static game starts on the event of the arrival of a vehicle at an intersection, at which it will be presented with multiple streets to select from. The decision making process in this cooperative game is achieved through several steps, which can be explained as follows:
Pre ctive Network Coverage Map: Firstly, each vehicle needs to retrieve information about the stribution of vehicles on fferent streets originating from that intersection. This is provided by Smart Traffic Lights at each intersection as will be explained later. Afterwards, each vehicle will compute the estimated network coverage in each of its optional routes in case it joins it. This can be calculated based on its latest former coverage percentage at time step k and the current measurement observed by the vehicle at time step k+1 which is represented as follows:
where z(k) represents the vector of vehicle observations at time step k; f represents the update function and p(kjk) denotes the vector of coverage percentage at time step k which is estimated based on former percentage (most recent previous information). In the previous equation, the vehicle adds the range of network coverage that it can add to that route in case it joins to its observation vector.
Now, each vehicle computes a vector of utilities for all of its optional routes and then picks the route with the highest utility; that is the one that provides the highest possible network coverage, to be its next decision.
Utility Function: Each vehicle calculates the utility valuefor each of its optional routes, which is based on the following:
_ Travel Time Cost, denoted by Tn i : which is equal to the length of this optional route i + Actual Shortest stance ( jkstra shortest path length from the end point of this optional route i to the destination of this vehicle n) * k factor (in cating environmental con tions i.e. speed of the car due to traffic).
_ Time taken after reaching that route i for vehicles to re stribute to maximize the coverage (i.e. achieving the inter- vehicle stance to improve the network connectivity), denoted by Tc(i). This is computed based on the number of vehicles in the street and their speed.
_ New network coverage percentage pre cted by vehicle n in that route i at time step k as mentioned in equation(1); denoted by pni (k + 1jk).
Therefore, the payoff value of vehicle n deci ng on some route i at time step k can be represented as follows, where D(k) is the decision at time step k:
Moreover, for the vehicles utility value to be more accurate in representing a certain route, we perform a look ahead in which the vehicle considers the maximum expected utility that it can get from the sub routes originating from route i at the next intersection. Therefore, the vehicle also computes:
where: route j ,route j route i. Here, every route j is a subset of the route i (representing the current vehicles decision). Then, the utility value of a vehicle n deci ng on a route i will now be represented as follows:
where: route j ,route j route i. Using this previous equation, each vehicle n can now calculate its utility vector with the set of utility values correspon ng to N options of routes that it may choose from, represented as follows:
Reaching this point, the vehicle can now pick the route with the maximum utility value in its vector to be its next decision.
Cooperation Scenario: In CAV, the cooperating vehicles consider each others decisions to avoid choosing the same route simultaneously. For this purpose, we define the coor nation factor h(D), which can be calculated as follows:
where Sn (k) is the shortest path from vehicle n s current location to its final destination. This shortest path is computed accor ng to jkstras algorithm. Therefore, for each of the cooperating vehicles, the utility function for each of its optional routes, after multiplying by exponential to the power of that cooperation factor, becomes as follows:
where: route j ,route j route i. However, the allowance for extra travel by the vehicle in order to increase the coverage cannot be unbounded as that will cause large degradation in the trip duration and travel stance. In order to ensure this bound, CAV utilizes a tolerated capacity that can vary based on the network con tions.
Fig. 5: Smart Traffic Lights are used to provide feedback and pre ction to incoming vehicles.
Trade off between network coverage and vehicle travel stance
In order to avoid a significant increase in the vehicle travel stance, CAV provides a threshold that the travel stance for a vehicle will not exceed. This threshold is calculated as a factor of the original projected travel stance from the initial point to the destination. If the threshold is set to be 1.5, this means that the vehicle is willing to travel 50% more than its original travel stance. In CAV, this threshold is set at the start of the vehicle trip, and computed as follows:
where cap is the capacity factor which can range anywhere between 0 and 1 (i.e. 0 means that the vehicle doesnt tolerate to travel more than its jkstra shortest path length, and 1 means that it can travel up to double the shortest path length).
Information from Smart Traffic Lights (SMLs)
In CAV, Smart Traffic Lights (SMLs) play an instrumental role where they function in a stributed stand-alone manner, to provide information on existing vehicle densities on the roads at the moment, and the expected vehicle density. The first role achieved by the SMLs is to monitor how many vehicles went on each road. This information is then relied to vehicles arriving at this intersection and lack connectivity with other vehicles on the roads as demonstrated in figure 5.
The other role for the SMLs is to pre ct the expected vehicle density. This information helps the vehicle make an informed decision based on the expected vehicle density that will arrive at this intersection in the future. If it is expected to be a high density, then the vehicle taking the decision would be free to make any choice that satisfies its trip stance. In CAV, this information is provided through the SMLs which use machine learning techniques (the technique is beyond the scope of this paper) to witness and extract traffic patterns, and then rely this information, to the vehicles taking a decision.
We used simulation to validate the performance of CAV.
In this section, we present the results and scuss them. The results reveal that CAV can provide an improvement up to 140% of network coverage compared to regular VANET.
TABLE I: Simulation Parameters.
Fig. 6: Network coverage performance of CAV compared to regular VANET and IVD
To test CAV, we developed a Java based simulator of a simple Manhattan model, in which roads are perpin cular to each other. The simulation, whose parameters are presented in TABLE I, tests for fferent vehicle introduction rates, which is the number of vehicles being introduced per second into the system. The scenarios used in the simulation are: VANET, IVD and CAV. VANET represents a regular vehicular network without any manipulation of vehicles, while IVD and CAV are what we propose in this paper.
The results of the simulation are as follows:
Network Coverage in CAV: Figure 4 presents the average network coverage performance of CAV compared to VANET, and IVD. At a vehicle introduction rate of 1 vehicle/sec, CAVprovides between 80 to 140 % improvement in network coverage when compared to VANETs and between 10 to 30% when compared to IVD. The dependence of the average coverage on the capacity in CAV is presented in figure 5. As shown, increasing the allowed travel stance for the vehicle allows more flexibility in improving the network connectivity.
Average Vehicle Travel stance: The average travel stance in cates how much extra travel stance will vehicles have to sacrifice in order to provide the improvement in network coverage. We compare the performance of CAV versus
VANET and IVD in figure 6. It is worth mentioning that the vehicles travel stance in VANET is identical to that of IVD because in IVD, the route of the vehicle to the destination is not changed, which is not the case in CAV. In figure 6, although the capacity allows for an increase of up to 20%, the increase is between 3 and 8.5% for the vehicle introduction rates of 0.2 and 1.5. This screpancy between the improvements is due to the fact that at lower vehicle densities,
the vehicle does not need to change its route in order to provide added network coverage because it is already doing so in its shortest path route due to the lack of other vehicles in it.
Moreover, we compare the performance of CAV in the case of fferent capacities, which is shown in figure 7. In ad tion, as in figure 6, the travel stance increases with the increase of the vehicle density. However, after a certain point in vehicle density, the routes become full with other vehicles, and hence, when the vehicle computes its utilities, the incentive to change its shortest path route begins to become smaller, which results in the vehicle not deviating much from its original route.
Fig. 7: Network coverage for fferent capacities in CAV
Fig. 8: Average vehicle travel stance in CAV compared to VANET and IVD
Fig. 9: Average vehicle travel stance for fferent capacities in CAV
We presented CAV, a stributed game theoretic approach to improve the network connectivity through optimizing the routes of autonomous vehicles. As shown in the simulation results, the network coverage improves up to 140% from the regular vehicular networks, while the cost of this improvement is in the range of 10%. Besides the benefit of network coverage improvement, we believe that this re stribution of vehicles in a geographical area helps avoid traffic congestion, which helps improve the travel duration despite the increase in travel stance. CAV provides a cheap, and realistic approach to provide a reliable vehicular network that can be used as a backbone and infrastructure for other types of networks. We believe that CAV is an important step forward in the realization of the potential of vehicular networks.
K.Tanjida Â«Pro-AODV (Proactive AODV): Simple Mo fications to AODV for Proactively Minimizing Congestion inVANETsÂ» IEEE Xplore, Networking Systems and Security (NSysS), International Conference in Dhaka 5-7 Jan. 2015.
DongjieZhu and all Â«DT-AODV: An On-Demand Routing Protocol based DTNin VANETÂ» international journal, NSP , Applied Mathematics & Information Sciences, volume 8, pages 2955-2963, china 2014.
A.Chinnasamy and all, Â«Enhance Trust based Routing Techniques against Sinkhole Attack in AODV based VANET
Â»International Journal of Computer Applications (0975 8887) Volume 65 No.15, IN A 2013.
X. Ma, J. Zhang, X. Yin and K. S. Trive , Design and Analysis of a Robust Broadcast Scheme for VANET Safety- Related Services", IEEE Trans. Veh. Tech., vol. 61, no. 1, Jan. 2012  S. Mehar, S. M. Senouci, A. Kies and M. M. Zoulikha, An Optimized Roadside Units (RSU) placement for delay-sensitive applications in vehicular networks", Proc. Consumer Communications and Networking Conference (CCNC), 2015 12th Annual IEEE, pp. 121-127, 2015.
Z. Mo, H. Zhu, K. Makki and N. Pissinou, MURU: A multi-hop routing protocol for urban vehicular ad hoc networks", Mobile and Ubiquitous Systems: Networking & Services, 2006 3rd Annual Int. Conf. on, pp. 1-8, 2006.
C. Campolo, A. Molinaro, A. Vinel and Y. Zhang, Modeling Prioritized Broadcasting in Multichannel Vehicular Networks", IEEE Trans. Veh. Tech., vol. 61, no. 2, Feb. 2012.
S. Dulman, M. Rossi, P. Havinga and M. Zorzi, On the hop count statistics for randomly deployed wireless sensor networks", Intl. Jnl. Sensor Networks, vol. 11, no. 1-2, pp. 89-102, 2006.
V. Kumar, S. Mishra, and N. Chand, Applications of Vanets: present & future, Communications and Network, vol. 5, no. 01, p. 12, 2013.
An Automated Adventure at the Wheel of a driverless BMW, http: //www.thenational.ae/, 2011.
T. Team, All Tesla Cars Being Produced Now Have Full Self-Driving Hardware, https://www.tesla.com/blog/ all-tesla-cars-being-produced-now-have-full-self-driving- hardware, October 2016.
M. J. Yang, S. Y. Lim, H. J. Park, and N. H. Park, Solving the Data Overload: Device-to-device bearer control architecture for cellular data offloa ng, IEEE Vehicular Technology Magazine, vol. 8, no. 1, pp. 31 39, March 2013.
A. Pyattaev, K. Johnsson, S. Andreev, and Y. Koucheryavy, 3GPP Lte Traffic Offloa ng onto WiFi Driect, in 2013 IEEE Wireless Communications and Networking Conference Workshops (WCNCW), April 2013.
H. Wu, R. M. Fujimoto, G. F. Riley, and M. Hunter, Spatial Propagation of Information in Vehicular Networks, IEEE Transactions on Vehicular Technology, vol. 58, no. 1, pp. 420431, Jan 2009.
Y. Liang, H. Liu, and D. Rajan, Optimal Placement and Configuration of Roadside Units in Vehicular Networks, in 2012 IEEE 75th Vehicular Technology Conference (VTC Spring), May 2012.
H. Cheng, X. Fei, A. Boukerche, A. Mammeri, and M. Almulla, A Geometry-based Coverage Strategy Over Urban Vanets, in Procee ngs of the 10th ACM Symposium on Performance Evaluation of Wireless Ad Hoc, Sensor, & Ubiquitous Networks, ser. PE- WASUN 13. New York, NY, USA: ACM, 2013, pp. 121128. [Online]. Available: http://doi.acm.org/10.1145/2507248.2507250
O. Trullols, M. Fiore, C. E. Casetti, C. C.-F, and J. Barcelo, A Max Coverage Formulation for Information ssemination in Vehicular Networks, in IEEE International Conference on Wireless and Mobile Computing, Networking and Communications (WIMOB 2009). IEEE, 2009, pp. 154160. [Online]. Available: http://porto.polito.it/2354904/
O. Trullols, M. Fiore, C. Casetti, C.-F. Chiasserini, and
J. B. Or nas, Planning Roadside Infrastructure for Information ssemination in Intelligent Transportation Systems, Computer Communications, vol. 33, no. 4, pp. 432442, 2010.