# A Geographical Heuristic Routing Protocol for VANETs
## 3 Background
### Generic Geographical Routing Process  
Algorithm 1 shows the generic routing process of a packet in a node that employs a geographical routing protocol with carry and forwarding as the recovery strategy. The algorithm is written for an anycast routing protocol. Nonetheless, the algorithm works exactly the same for a unicast routing. In that particular case, the destination set \(Dst\) used as the input of the algorithm will have a single element that is the destination node of the packet.  
```
1:route(\(P\))
2:a packet \(P\), Destination set \(Dst\), current vehicle \(v\)
3:Forward \(P\) to a vehicle neighbor \(v_{\text{nh}}\) to reach a member \(Dst\) or save \(P\) in buffer.
4:\(Dst\leftarrow\textsc{GetDestinationSet}(P)\)
5:if\(v\in Dest\)then
6:GotoUpperLayer(\(P\))
7:return
8:if\(\exists\ n\in\)N(\(v\)) \(\wedge\ n\in Dest\)\(\wedge\)IsLegal(\(n\)) = True then
9:\(v_{\text{nh}}\gets n\)
10:else
11:\(v_{\text{nh}}\leftarrow\textsc{DoRouting}(P,v,Dst)\)
12:if\(v_{\text{nh}}\
eq v\)then
13:Forward(\(P,v_{\text{nh}}\))
14:else
15:Buffering(P)
16:return
```  
**Algorithm 1** General routing process of a DTN geographical protocol.  
When a packet arrives to a node, the first step is to determine the destination set of that packet (Line 1 in Algorithm 1). The information of the destination set can be retrieved from the anycast IP address of the packet. A list of destination nodes is associated with each anycast IP address. Every node carries this mapping table with it. Therefore, the look-up task of the destination set does not need any on-line search. Moreover, since the typical destination set will be fixed network points like RSUs, then their positions also can be a priori known. The associations anycast IP address-destination and RSU position do not need to be constantly updated. A vehicle can refresh this information where there are available Internet connections, for instance when the vehicles are parked at home or at the office.  
If the current node \(v\) is a member of the destination set \(Dst\), then the packet is processed by the upper layer (Line 3 in Algorithm 1), and the routing process ends. When the current node is not a destination member, it searches if it has a member \(n\) of the destination set among its neighbors N(\(v\)), which in addition is considered a legal node (see Line 5). A \"legal node\" refers to a neighbor that meets a certain list of characteristics that depend on the routing protocol. For instance, in the case of our MMMR [20] protocol used in this paper, a legal neighbor has to be in LOS, and the estimated power reception has to be higher than its antenna sensibility plus an extra margin of 1 dB. If the current node \(v\) finds such a neighbor, then it chooses as the next forwarding node that neighbor \(n\) (Line 6). Otherwise, a selection of the next forwarding hop \(v_{\text{nh}}\) is performed (Line 8). Next, if the selected node \(v_{\text{nh}}\) is not the current node \(v\) (Line 9 in Algorithm 1), then the routing protocol forwards the packet to \(v_{\text{nh}}\). Else, the packet is stored in the buffer until a suitable node appears. The next sections explain in detail two routing proposals for the function DoRouting, which is in charge of selecting the next forwarding node.