# A Routing Algorithm Based on Real-Time Information Traffic in Sparse Environment for VANETs
## 4 Routing Algorithm
### Routing Process  
The real-time effective information traffic routing(RTEIT) is a new vehicle-to-vehicle routing protocol we proposed, which aims to improve communication performance in a sparse urban routing environment. To achieve this goal, we propose a new method to evaluate relay nodes, which has been discussed in other parts of Section 4. In this subsection, we will describe the implementation process of this scheme.  
All vehicles broadcast hello massage periodically to neighbor nodes. The receiving node will update the neighbor table according to the information in the hello packet. Each neighbor node has an entry in the neighbor table. Each entry consists of node IP address, speed vector, location coordinates, the value of \(I(t)\), and the last update time. This information is directly obtained from the hello package.  
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline  & **Node 1** & **Node 2** & **Node 3** & **Node 4** & **Variance** \\ \hline \(I(t)\) & 0.4 & 0.56 & 0.86 & 1 & 0.075 \\ \(E(l)\) & 1 & 0.81 & 0.75 & 0.93 & 0.012 \\ \hline \hline \end{tabular}
\end{table}
Table 1: Parameters with different variances.  
Figure 7: Two parameters of neighbors.  
Our new routing scheme is divided into two parts: greedy forwarding and recovery forwarding. Figure 8 shows the whole process of the routing. In greedy forwarding, the source node sends the data packet to the node with the largest vehicle utility from the one-hop neighbor table. In recovery mode, nodes forward packet based on right-hand rule. When the sender wants to send packets, it determines the forwarding mode first according to the location information of the destination node. If there is a neighbor node closer to the destination node, the sender enters a greedy forwarding mode. In another case: the sender has the shortest distance to the destination among neighbors. Generally, there are two kinds of strategies for this condition: one is to carry the packet until it meets the appropriate neighbor which is closer to the destination; the other is to use left or right-hand rule to find nodes that can enter greedy mode. We use the second strategy as the recovery forwarding mode. This is because our protocol is mainly for sparse scenes. In such a scenario, it may take a long time for a node to encounter the next vehicle, which makes the end-to-end delay increase. Another reason is that our defined real-time effective information traffic will reduce the forwarding priority of nodes near the topology hole. In addition, the peripheral forwarding will have a negative impact on the real-time effective information traffic, further reducing the priority of nodes near the road with holes. The details of the algorithm are described in Algorithm 1.  
Figure 8: Routing process.  
```
1:\(CN\): Current node. \(DN\): Destination node. \(P\): Packet. \(N_{T}\): Neighbor table. \(d_{n}eighbor\): Distance between neighbor and destination. \(d_{c}\): Distance between current node and destination.
2:while (\(CN\) receive \(P\)) do
3:if\(P\) is hello packet then
4:\(n_{p}\)=get position from hello packet;
5:\(n_{p}\)=get speed from hello packet;
6:\(n_{i}\)=get \(I(t)\)from hello packet;
7: add \(n_{p}\),\(n_{v}\),\(n_{i}\) to \(N_{T}\) or refresh it;
8:endif
9:if\(P\) is data packet then
10:if in greedy mode then
11: calculate \(d_{c}\);
12:for (each \(neighbor\in N_{T}\)) do
13: calculate \(d_{n}eighbor\);
14:if\(d_{neighbor}>d_{\min}\) then
15:\(d_{neighbor}\gets d_{\min}\);
16:endif
17:endfor
18:if\(d_{c}<d_{\min}\)then
19: enter to recovery mode;
20:else
21:for (each \(neighbor\in N_{T}\)) do
22: calculate \(E(l)\) for neighbor;
23:endfor
24: calculate \(U_{neighbor}\)for each neihgbor;
25:for (each \(neighbor\in N_{T}\)) do
26:if\(U_{max}<U_{neighbor}\)then
27:\(U_{max}\gets U_{neighbor}\)
28:\(bestnode\)=neighbor;
29:endif
30:endfor
31: forward to \(bestnode\) in greedy mode;
32:endif
33:else
34: forward in recovery mode;
35:endif
36:endif
37:endwhile
```  
**Algorithm 1** Real-time effective information traffic routing (RTEIT) algorithm