# A Geographical Heuristic Routing Protocol for VANETs
## 4 Geographical Heuristic Routing Protocol
```
1:\(\tau\leftarrow\textsc{GetTabUList}(P,\mathit{state})\) {if \(\mathit{Tabu}=False\) then \(\tau=\varnothing\)}
2:\(v_{\text{nh}}\leftarrow\mathit{v},\ v_{f}\leftarrow\mathit{v},\ v_{r} \leftarrow\mathit{v}\) {Initializing next hop variables}
3:\(s_{\mathit{v}_{f}}\leftarrow-\infty,\ s_{\mathit{v}_{r}}\leftarrow-\infty\)
4:\(\mathrm{d}_{\mathit{v}-v_{f}}\gets 0,\ \mathrm{d}_{\mathit{v}-\mathit{dst}_{f}} \leftarrow 0,\ \mathrm{d}_{\mathit{v}-\mathit{v}_{r}},\leftarrow 0\) {Initializing distance variables for SA procedures}
5:\(\theta\leftarrow\mathrm{U}[0,1]\)
6:\(\mathrm{L}(\mathrm{N}(\mathit{v})\mathit{v})\leftarrow\emptyset\) {Initial empty set of legal neighbors of \(\mathit{v}\) closer to \(\mathit{v}_{\text{dst}}\)}
7:for all\(v_{\text{dst}}\in\mathit{Dst}\)do
8:\(\mathrm{d}_{\mathit{v}}\leftarrow\mathrm{D}(\mathit{v},\mathit{v}_{\text{dst}})\)
9:for all\(n\in\mathrm{N}(\mathit{v})\)do
10:if\(n\
otin\tau\)then
11:if\(\textsc{IsLegal}(n)=True\)then
12:\(\mathrm{d}_{\mathit{v}-n}\leftarrow\mathrm{d}_{\mathit{v}}\) - \(\mathrm{D}(\mathit{n},\ v_{\text{dst}})\)
13:\(s_{n}\leftarrow\textsc{ComputeMetric}(n)\)
14:if\(\mathrm{d}_{\mathit{v}-n}>\)then {Forwarding phase}
15:\(\mathrm{L}(\mathrm{N}(\mathit{v})\mathit{v})\leftarrow\mathrm{L}(\mathrm{N}( \mathit{v})\mathit{v})+n\)
16:if\(s_{n}>s_{\mathit{v}_{f}}\)then
17:\(v_{f}\gets n,\ s_{\mathit{v}_{f}}\gets s_{n},\ \mathrm{d}_{\mathit{v}-\mathit{v}_{f}} \leftarrow\mathrm{d}_{\mathit{v}-n}\ \mathrm{d}_{\mathit{v}-\mathit{dst}_{f}} \leftarrow\mathrm{d}_{\mathit{v}}\) {Set the current best vehicle as forwarding vehicle}
18:if First=\(True\)then
19:\(v_{\text{nh}}\leftarrow\mathit{v}_{f}\)
20:goto End
21:else [Recovery phase: To use a farther vehicle to dest. \(v_{dst}\) than \(\mathit{v}\): \(\mathrm{d}_{\mathit{v}-n}\leq\)0]
22:if\(s_{n}>s_{\mathit{v}_{r}}\)then
23:\(v_{b}\gets n,\ s_{\mathit{v}_{r}}\leftarrow s_{n},\ \mathrm{d}_{\mathit{v}- \mathit{v}_{f}}\leftarrow\mathrm{d}_{\mathit{v}-n}\ \mathrm{d}_{\mathit{v}- \mathit{dst}_{r}}\leftarrow\mathrm{d}_{\mathit{v}}\) {Set the best legal vehicle is not closer to \(\mathit{v}_{\text{dst}}\) as recovery vehicle}
24:endfor
25:endfor
26:if\(\mathrm{L}(\mathrm{N}(\mathit{v})\mathit{v})\mathit{\
eq}\emptyset\)then {Forwarding phase: \(\mathrm{d}_{\mathit{v}-n}>\)0}
27:\(p=e^{-a\mathrm{d}_{\mathit{v}-\mathit{v}_{f}}/\mathrm{d}_{\mathit{v}-dst_{f}}}\)
28:if\(\mathrm{p}>\theta\)then
29:\(v_{f}:=\textsc{S}_{\text{Random}}(\mathrm{L}(\mathrm{N}(\mathit{v})\mathit{v}))\) [Set a random legal neighbor as forwarding vehicle]
30:\(v_{\text{nh}}\)=\(v_{f}\)
31:else [Recovery phase: \(\mathrm{d}_{\mathit{v}-\mathit{v}_{b}}\leq 0\)]
32:if\(v_{r}\
eq v\)then
33:\(p=e^{\beta\mathrm{d}_{\mathit{v}-\mathit{v}_{b}}/\mathrm{d}_{\mathit{v}-dst_{r}}}\)
34:if\(\mathrm{p}>\theta\)then
35:\(v_{\text{nh}}\)=\(v_{r}\)
36:End:
37:if\(v_{\text{nh}}\
eq\mathit{v}\wedge\mathit{Tabu}=True\)then {The packet will be forwarded}
38: UpdateTabUList (\(\tau,\mathit{v},\mathit{P}\))
39:return\(v_{\text{nh}}\)
```  
**Algorithm 2** Our proposed Geographical Heuristic Routing (GHR) protocol. The Tabu list will be empty if the _Tabu_ option is not enabled, and therefore, there will not be any forbidden neighbor as the next hop. Regarding \(v_{\text{nh}}\), it stores the next forwarding node. It can be equal to the selected node \(v_{f}\) of the forwarding phase, to the selected backup node \(v_{r}\) in the recovery phase or it can store the initial value \(v\) because no neighbor was chosen to forward the packet \(P\). Secondly, GHR initializes to a very low value the best scores \(s_{v_{f}}\) and \(s_{v_{r}}\) of the selected node in the forwarding and recovery phases, respectively (line 3). Then, the variables \(d_{v\text{-}dst_{f}}\), \(d_{v\text{-}dst_{f}}\), \(d_{v\text{-}v_{f}}\) and \(d_{v\text{-}v_{r}}\) are initialized to zero (Line 4 of Algorithm 2).