ABSTRACT
Vehicular adhoc networks (VANETs) leverage the communication system of Intelligent Transportation Systems (ITS). Recently, Delay-Tolerant Network (DTN) routing protocols have increased their popularity among the research community for being used in non-safety VANET applications and services like traffic reporting.
Vehicular DTN protocols use geographical and local information to make forwarding decisions. However, current proposals only consider the selection of the best candidate based on a local-search. In this paper,we propose a generic Geographical Heuristic Routing (GHR) protocol that can be applied to any DTN geographical routing protocol that makes forwarding decisions hop by hop. GHR includes in its operation adaptations simulated annealing and Tabu-search meta-heuristics, which have largely been used to improve local-search results in discrete optimization.
We include a complete performance evaluation of GHR in a multi-hop VANET simulation scenario for a reporting service. Our study analyzes all of the meaningful configurations of GHR and offers a statistical analysis of our findings by means of MANOVA tests. Our results indicate that the use of a Tabu list contributes to improving the packet delivery ratio by around 5% to 10%. Moreover, if Tabu is used, then the simulated annealing routing strategy gets a better performance than the selection of the best node used with carry and forwarding (default operation).
RELATED WORK
Heuristic optimization techniques have been used in some works to improve the operation of routing protocols. In the authors propose a new routing protocol called the Tabu Search-based Routing Protocol (TSRP), which introduces an implementation of the Tabu search meta-heuristic to avoid nodes previously selected in the routing process of the data from the sensor (that has previously sensed the event) to the sink. TSRP is based on maximizing the cost function, which considers the energy and the visibility of that sensor compared to the sink. TSRP keeps a 0/1 string that indicates whether a node forwarded a packet or not. Simulation results show that TSRP extends the network lifetime compared to the protocols Gossiping and MFR.
BACKGROUND
Tabu Search
Figure1. An example that shows Tabu avoid sloops and improves the operation of a basic routing protocol
Figure1. An example that shows Tabu avoid sloops and improves the operation of a basic routing protocol based on forwarding the packet to the closest neighbor to destination. (a) Forwarding to the closest neighbor fails when two nodes are both the closest neighbors to destination, as Nodes A and B in this topology; (b) Tabu breaks the loop between Nodes A and B. Tabu list prevents B from returning the packet to A. Node C receives the packet from B.
GEOGRAPHICAL HEURISTIC ROUTING PROTOCOL
In this section, we present our proposal of the geographical routing protocol named the Geographical Heuristic Routing (GHR) protocol. GHR follows the DTN approach of carrying the packet when there is not a suitable next forwarding node. Moreover, our routing protocol can use any routing criteria to select the next forwarding node to make forwarding decisions at each hop.
The GHR protocol combines Tabu search and the Simulated Annealing (SA) adaptation summarized in the previous Section 3 to avoid loops and select the next node with a certain degree of randomness, respectively. GHR does not need to add any information to the hello messages. Algorithm 2 shows the procedure of our proposed GHR.
PERFORMANCE EVALUATION
Figure 3. Simulation scenario. Eixample district of Barcelona, Spain, with an Access Point (AP). Buildings (orange lines) from Open Street Map are included
There was one fixed destination, the Access Point (AP) in Figure 3, that receives the vehicles traffic information (e.g., traffic reports, infraction notifications, event of an accident, etc.). We used a single AP in the scenario because in this way, we obtained along range of route lengths, which depend on the position of the source vehicles in the scenario.
All nodes sent 1000-byte packets every T seconds to the unique destination during 300 s. T follows a uniform distribution from 2 to 6 s. We point out that these two settings (i.e., a single AP and all vehicles generating traffic) are adverse for successful multi-hop transmissions because they make medium access contention very challenging, and therefore, collisions and the associated packet losses are more likely to happen.
Figure 4. Performance evaluation of the forwarding techniques
Figure 4. Performance evaluation of the forwarding techniques (FT) included in our proposed GHR. T = 1 means that our Tabu routing is used. The four FT are: best node selection (α → ∞), simulated annealing (α = 3), random forwarding (α = 0) and first legal node (First). (a) Percentage of packet losses; (b) average end-to-end packet delay; (c) average number of hops; (d) percentage of idle time.
CONCLUSIONS AND FUTURE WORK
In this paper, we have proposed a generic Geographical Heuristic Routing (GHR) protocol. GHR is inspired by simulated annealing and Tabu search meta-heuristics. We divide the GHR operation according to the operation in forwarding and recovery. The forwarding heuristics are used when an improvement to reach the destination is feasible. The recovery heuristics are thought to be used with the carry and forwarding approach. GHR can adapt its forwarding criterion depending on the application requirements.We use the traffic-aware MMMR protocol in the core of our proposed GHR to validate and score the neighbors of the current node in the forwarding process.
None the less, GHR could use any other routing protocol for the validation and scoring tasks. An extensive performance evaluation of our proposed GHR indicates that the use of a Tabu list contributes to improving the packet delivery ratio by around 5% to 10%. However, this better performance comes at the price of an additional delay (2 s) because of the more restrictive selection process of the next forwarding node. None the less, the non-real-time applications, which are objective of our work (e.g., report of traffic notifications), could cope with this delay. On the other hand, we show that the classical selection of the best node to forward a packet (i.e., the node with the best metric) and the carry and forwarding recovery are only adequate when the use of Tabu is not possible. On the contrary, if the routing process enables a Tabu list, then a forwarding strategy selection based on simulated annealing and a recovery procedure that does not use the buffer frequently are preferred. There are some interesting variants of the heuristics presented in this work that we believe are worth testing.
Among these variants we highlight the possibility to re-define the numerator of the simulated annealing probability function by considering some function of the distances among candidate nodes. In this way, when candidates are close to each other, random selection would be preferred. Another variant in simulated annealing is not to select, with probability p, a random node to forward the packet. Instead, a node will prefer, with probability p, a backup node (chosen by some function) rather than the best candidate in the forwarding process.
Source: Universitat Politecnica De Catalunya
Authors: Luis Urquiza-aguiar | Carolina Tripp-barba | Mónica Aguilar Igartua