# A Geographical Heuristic Routing Protocol for VANETs
## 4 Geographical Heuristic Routing Protocol
If it is higher than the current best score, then the neighbor \(n\) becomes the best forwarding node \(v_{f}\) and the best forwarding score \(s_{v_{f}}\), and the difference of distance \(\text{d}_{v\text{-}v_{f}}\) between current node \(v\) and best candidate \(v_{f}\) to the destination is updated to \(\text{d}_{v\text{-}n}\) and \(s_{n}\), respectively (Line 16). When the \(first\) option is set to true, the first legal forwarding node \(v_{f}\) is selected as the next forwarding node \(v_{\text{nh}}\) (Lines 18 and 19), and the searching stops and goes to the final step of the algorithm. When the neighbor \(n\) is considered to be in the recovery phase (Line 21 of Algorithm 2), if the neighbor score \(s_{n}\) is higher than the current best recovery score \(s_{v_{r}}\) (Line 22), then \(n\) is the new best recovery node \(v_{r}\), and the corresponding score and distance variables are updated (Line 23). After that, the GHR protocol searches for the best forwarding node considering all of the members of the destination set; it checks whether the set L(N(\(v\)), \(v\)) is empty or not (Line 26 of Algorithm 2). If it is not empty, which means that there are neighbors closer to the destination, then a probability \(p\) is obtained as a function of the forwarding factor \(\alpha\), the difference of distances \(d_{v-v_{f}}\) and the distance from the current node to destination \(d_{v-dst_{f}}\) following Equation (1). The purpose of these factors was explained in the simulated annealing of Section 3.2. If \(p>\theta\), then the next forwarding node is chosen randomly from the set of legal neighbors (Line 29); otherwise, the next forwarding node is the best neighbor previously stored in \(v_{f}\). When there is no legal neighbor closer to the destination (i.e., L(N(\(v\)),\(v\)) = \(\emptyset\)), the algorithm checks if there is a legal recovery node \(v_{r}\) different from the initial value of it, which was set to node \(v\) (\(v_{r}\
eq v\) in Line 32). If there is some recovery node \(v_{r}\), then it will be farther from the destination (i.e., \(d_{v-v_{b}}\leq 0\)). A probability \(p\), computed as in the forwarding case (Line 33), decides if the packet \(P\) is forwarded to \(v_{r}\) (\(p>\theta\) in Line 34) or if on the contrary, the packet is stored in a buffer. Notice that there is no negative sign in the equation of Line 33 because \(d_{v-v_{b}}\leq 0\). It is worth pointing out that we employ the random uniform number \(\theta\) to decide if the probability computed with Equation (1) becomes true in the routing process. Since \(\theta\) changes its value at each forwarding operation, the routing decision depends on the probability of randomness \(p\) and on the current value of _theta_. This makes random the decision of selecting a random node or a recovery node, which is the idea of simulated annealing. For instance, in the forwarding phase, even for high values of \(p\), there is a chance of not randomly routing a packet because the current value of \(\theta\) is higher than \(p\). If _theta_ were a fixed value, then the algorithm would use random routing or a recovery node only depending on the value of \(p\) computed through Equation (1). This would make decisions not random at all, contrary to the simulated annealing principle. Finally, if _Tabu_ routing is being used (i.e., \(Tabu=True\)) and the packet will be forwarded to some neighbor (i.e., \(v_{\text{nh}}\
eq v\)), then the current node \(v\) is added to the top of the Tabu list \(\tau\) according to the procedure described in Section 3.2.1.