# A Geographical Heuristic Routing Protocol for VANETs
## 3 Background
### Heuristics Adaptations for VANET Routing
#### 3.2.1 Tabu Search  
In [9], the Tabu search implementation was proposed as a list called tabu \(\tau\) of the last \(k\) nodes visited by a packet. The key idea is to keep track of the nodes already visited and forbid forwarding to the nodes included in the tabu list \(\tau\). The tabu list \(\tau\) is updated following the logic of a FIFO list. This means that the oldest visited node in the list is the first to be deleted if the list gets full. Using the tabu technique, we are able to avoid loops. Nodes will be included in the list of forbidden nodes if they are not solutions (destination nodes).  
Contrary to the implementation of [10] that uses one bit for each node of the network in the tabu list, in our tabu search, every packet carries the entire ID of a limited number of nodes in the tabu list \(\tau\) (the last ones, e.g., the last three ones). The number of nodes in a VANET is very dynamic and relatively big, so it is not practical nor possible to use a 0/1 string to encode all of the nodes of a VANET. Moreover, our tabu list implementation of a packet is a dynamic, temporal filter to determine legal nodes in addition to the statical requirements established by the routing protocol. This dynamic filter forbids using a node in the tabu list as a next hop for that packet during a limited number of forwarding operations (the length of the list). For instance, if the length of the tabu list is equal to four, then a node added to the tabu list can be used for routing the packet again only after four routing operations from its addition to the list.  
To show how Tabu could enhance the operation of a routing protocol, we assume in our example, depicted in Figure 1, that nodes employ a basic routing procedure, in which nodes always forward the packet to the closest neighbor to destination, even when the best neighbor is farther than the current forwarding node to the destination.  
On the one hand, our simple routing protocol will fail in the packet delivery between S and AP, as can be seen in Figure 1a, because there is a loop between Nodes A and B. The problem occurs because the closest neighbor to the destination from Node B is the previous hop of the packet (i.e., Node A). Therefore, Node B will return the packet to Node A, and then, Node A will forward the packet to Node B again, and so on. This creates a loop between Nodes A and B because both are the closest nodes to the destination.  
Figure 1: An example that shows how Tabu avoids loops 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.  
On the other hand, if the routing protocol implements a tabu list to record the previous hops, then the packet transmission from S to AP could overcome the loop between A and B in the topology of our example. In this case, depicted in Figure 1b, when Node B receives the packet from Node A, B cannot forward it again to A (its closest neighbor to the destination) because A is contained in the Tabu list of the packet. Therefore, Node B has to forward the packet to C. From Node C, the packet finds a path to reach the destination. In conclusion, Tabu provides memory to the routing decision and helps nodes to deal with complex network topologies in order to find routing paths.