# A Geographical Heuristic Routing Protocol for VANETs
## 4 Geographical Heuristic Routing Protocol
The two former variables, i.e., \(d_{v\text{-}dst_{f}}\), \(d_{v\text{-}dst_{f}}\), store the difference of distances to destination from the current node \(v\) and the best forwarding \(v_{f}\) and recovery \(v_{r}\) candidate neighbors, respectively. The distance of the current node to the destination member for which the best forwarding and candidate nodes got their score are kept in \(d_{v\text{-}dst_{f}}\) and \(d_{v\text{-}dst_{f}}\), respectively. These four variables related to distances or the difference of distance to the destination are used in the computation of a probability \(p\) of using a random forwarding node or a recovery node, depending on the operation phase of GHR. After that, a random uniform value between zero and one is stored in the variable \(\theta\) (Line 5). The probability of random or recovery forwarding is compared to the value \(\theta\) to decide if any of these options is performed. Next, in Line 6 of Algorithm 2, the set of legal neighbors L(N(\(v\)), \(v\)) is initialized as an empty set. L(N(\(v\)), \(v\)) stores the legal neighbors \(n\), which are closer to some destination member \(v_{\text{dst}}\in Dst\) than the current node \(v\). GHR searches the best forwarding \(v_{f}\) and recovery \(v_{r}\) nodes considering all of the members of the destination set \(Dst\). The GHR algorithm goes through the list of destination members (see the \"for\" loop from Lines 7 to 25 of Algorithm 2), seeking the forwarding and recovery nodes with the highest scores among legal neighbors. Hence, GHR makes an exhaustive search and chooses the neighbor with the best metric over all of the other neighbors and members of the destination set. More specifically, for each destination member \(v_{\text{dst}}\), GHR searches among the neighbors of current node \(N(v)\) (see the \"for\" loop from Lines 9 to 24) if any of them improves the current scores \(s_{v_{f}}\) and \(s_{v_{r}}\) of \(v_{f}\) and \(v_{r}\), respectively. In the selection process, the first step is to obtain the distance from the current node to the destination member \(v_{\text{dst}}\), which will be stored in \(\text{d}_{v}\) (Line 8). Then, GHR checks if the neighbor \(n\) under evaluation is not in the Tabu list \(\tau\) (Line 10) and that it is legal (Line 11). Only if node \(n\) is not in the Tabu list and it is legal, the algorithm considers neighbor \(n\) as a possible next forwarding node. Otherwise, the node is discarded by the selection process. After verifying the eligibility of a neighbor \(n\), the GHR protocol calculates the difference of distances, called \(\text{d}_{v\text{-}n}\), between the current node \(v\) to the destination member \(v_{\text{dst}}\) (i.e., \(d_{v}\)) and the candidate node \(n\) to the destination member \(v_{\text{dst}}\), i.e., \(D(n,v_{\text{dst}})\) (see Line 12). In addition, the algorithm computes the routing metric score of the neighbor \(n\) (Line 13). If \(\text{d}_{v\text{-}n}\geq 0\) in Line 14, this means that \(n\) is closer to \(v_{\text{dst}}\) than the current node \(v\); therefore, \(n\) is a candidate to be the next forwarding node \(v_{f}\), and the neighbor \(n\) is added to the set of legal neighbors L(N(\(v\)), \(v\)) (Line 15). Otherwise (i.e., \(\text{d}_{v\text{-}n}<0\) in Line 21), the neighbor \(n\) is considered as a possible recovery node. We would like to highlight that, if a neighbor \(n\) is a legal forwarding node for more than one destination member, then that neighbor \(n\) will be included in the set of legal neighbors as many times as it was considered legal in the selection process. Hence, the probability of that node \(n\) being chosen in a random selection (Line 29) will be higher than for a node that is legal only for one destination member. If the neighbor is closer to the destination (\(\text{d}_{v\text{-}n}\geq 0\)), the score of neighbor \(n\) is compared with the current best forwarding score \(s_{v_{f}}\) (Line 16).