# A Geographical Heuristic Routing Protocol for VANETs
## 3 Background
### Heuristics Adaptations for VANET Routing
#### 3.2.2 Simulated Annealing  
The Simulated Annealing (SA) adaptation to VANET routing protocols [9] aims to provide a controlled and decreasing randomness in the forwarding process. The randomness in the forwarding decreases when a packet approaches the destination. To do that, simulated annealing employs Equation (1). If there are closer neighbors to the destination with respect to the current node (forwarding phase), this equation provides the probability of selecting a random legal node as the next forwarding hop. Otherwise, in the recovery phase in which there is not a closer node to the destination, Equation (1) represents the probability of choosing a node farther than the current node. The idea behind selecting a worse node than the current one in terms of distance is to avoid buffering and to consider other alternative forwarding nodes. \[p=e^{-\gamma\frac{|d_{s-s},p^{s}|}{d_{s}}} \tag{1}\]  
The metrics used to compute the probability \(p\) of Equation (1) are:  
* The distance of the current node to destination \(d_{s}\). As a packet jumps, it should be approaching to the destination, and \(d_{s}\) should therefore decrease. This should tend to reduce the probability \(p\). * \(|d_{s^{\prime}-s}|\) is the absolute value of the difference of distances between the best forwarding candidate to the destination (named \(d_{s^{\prime}}\)) and the current node to destination \(d_{s}\). If \(d_{s^{\prime}-s}\) is high, then it will contribute to reducing probability \(p\). The idea of the numerator is that if the next position of the packet by choosing the closest forwarding node is not far from the current position (i.e., the best candidate improves little in distance), then it could be a good option to choose randomly and try other paths that otherwise would not have been explored because of the benefit of using the greedy selection, i.e., choosing the best candidate. * \(\gamma\) is a tuning parameter to balance the deterministic and randomness behavior. If it is close to zero, the probability \(p\) tends to one. Conversely, if \(\gamma\rightarrow\infty\), then \(p\to 0\). The advantage of simulated annealing can be seen in a topology as the one depicted in Figure 2. In that topology, a greedy algorithm that always forwards packets to the closest node to the destination will fail in the delivery of packets from S to AP. Such a kind of protocol will follow the path shown in Figure 2a. That greedy path will end in the node G1 or, if Tabu was used, in the node P5. In any case, the routing algorithm will not find any suitable next hop. On the contrary, if simulated annealing is considered in the strategy of the routing protocols, then other different scenarios are possible. Figure 2b shows one of them. In that scenario, the P1 node decides to forward the packet randomly and chooses the node O1 (red link in the path of Figure 2b). The reason for the random forwarding decision of P1 is the short distance improved by its best neighbor (Node G1) with respect to its distance to destination (P1). This short difference of distance is precisely the numerator of the fraction used by the simulated annealing equation to compute the probability of random forwarding and makes the value of \(p\) high. Once O1 receives the packet, the most likely routing behavior is to forward the packet following the greedy (deterministic) approach. This is because the other nodes (i.e., G2 and Y2) improve the distance to the destination at each hop considerably with respect to the previous node in the path, and the total distance to the destination is reduced, as well. Therefore, the random forwarding probability, which depends on these two factors, becomes smaller at each hop approaching the destination. A second scenario considers the high likelihood of random forwarding at the beginning of the path, as can be seen in Figure 2c. This could happen because the distance to the destination, which is the denominator of Equation (1), is long at that point.