# A Routing Algorithm Based on Real-Time Information Traffic in Sparse Environment for VANETs
## 4 Routing Algorithm
### Link Utility  
Vehicle movement model can be described by the following variables: current position at \(t_{0}\) in Cartesian coordinates: \(X(t_{0})\) and \(Y(t_{0})\); velocity vector: \(\left(V_{ix}\left(t_{0}\right),V_{iy}\left(t_{0}\right)\right)\)(Figure 4). The euclidean distance between node \(i\) and \(j\) at \(t_{0}\): \(d_{ij,t_{0}}\) is written as (5). \(x_{i,t_{0}}\) and \(x_{j,t_{0}}\) are the coordinates of the x-axis of node \(i\) and \(j\) at \(t_{0}\), \(y_{i,t_{0}}\) and \(y_{j,t_{0}}\) are the coordinates of the y-axis of node \(i\) and \(j\) at \(t_{0}\). At \(t_{1}\) the distance between \(i\) and \(j\): \(d_{ij,t_{1}}\) is given by (2) and (3). \(\Delta_{d}ij,t_{1}-t_{0}\) is distance changing of \(i\),\(j\) during \([t_{0}-t_{1}]\), \(v_{j}(t)\), \(v_{i}(t)\) is the function of velocity. \[d_{ij,t_{0}}=\sqrt[2]{\left(x_{i,t0}-x_{j,t0}\right)^{2}+\left(y_{i,t_{0}}-y_{ j,t0}\right)^{2}} \tag{5}\]  
\[d_{ij,t_{1}}=d_{ij,t_{0}}+\Delta d_{ij,t_{1}-t_{0}} \tag{6}\]  
\[\Delta d_{ij,t_{1}-t_{0}}=\int_{t_{0}}^{t_{1}}\left[v_{j}(t)-v_{i}(t)\right]dt. \tag{7}\]  
In this vehicle movement model, the link lifetime is defined as the time that the vehicle can maintain communication [30]. Ref. [31] proposes link reliability, which is the probability that a direct communication link between two vehicles will stay continuously available over a specified time period. Link reliability can be derived as:  
\[r(l)=P\{\text{to continue be available }t+\Delta\text{t }|\text{ \ available at t}\}. \tag{8}\]  
Next, the vehicle movement will be discussed in several situations in Figure 5:  
Figure 4: Node movement model. Scenario 1: \(Vi\) and \(Vj\) have the same direction, and \(v_{i}\geq or\geq v_{j}\). \(\Delta d_{ij,t1-t0}\) is the changing distance between node \(i\) and \(j\) in the period of \([t_{0}-t_{1}]\). \(\Delta x\) is the distance on the x-axis, \(\Delta y\) is the distance on the y-axis. \(R\) is the range of vehicle wireless communication. In this scenario, \(r(l)\) can be formulated as:  
\[r(l)=P\left\{\Delta d_{ij,t1-t0}<\sqrt{R^{2}-\Delta y^{2}}+\Delta x\right\} \tag{9}\]  
Scenario 2: \(v_{i}\) and \(v_{j}\) have the same direction, and \(v_{i}\leq\leq v_{j}\). \[r(l)=P\left\{\Delta d_{ij,t1-t0}<\sqrt{R^{2}-\Delta y^{2}}-\Delta x\right\}. \tag{10}\]  
Scenario 3: \(v_{i}\) and \(v_{j}\) have the opposite direction,and move towards each other, \(r(l)\) can be formulated as:  
\[r(l)=P\left\{\Delta d_{ij,t1-t0}<\sqrt{R^{2}-\Delta y^{2}}+\Delta x\right\}. \tag{11}\]  
Scenario 4: \(v_{i}\) and \(v_{j}\) have the opposite direction, move away from each other, \(r(l)\) can be formulated as:  
\[r(l)=P\left\{\Delta d_{ij,t1-t0}<\sqrt{R^{2}-\Delta y^{2}}-\Delta x\right\}. \tag{12}\]  
The speed and direction of the vehicle can be periodically broadcast to neighbor nodes using hello packets. However, the vehicle speeds \(v_{i}\) and \(v_{j}\) of the vehicle in \([t_{0}-t_{1}]\) time can also change. Therefore, the distance changing of \(i,j\) during \([t_{0}-t_{1}]\)\(\Delta d_{(}ij,t1-t0)\) can be expressed as:  
\[d_{ij,t_{1}}=d_{ij,t_{0}}+\Delta d_{ij,t_{1}-t_{0}} \tag{6}\]0  
\[d_{ij,t_{1}}=d_{ij,t_{0}}+\Delta d_{ij,t_{1}-t_{0}} \tag{6}\]1  
\[d_{ij,t_{1}}=d_{ij,t_{0}}+\Delta d_{ij,t_{1}-t_{0}} \tag{6}\]2 Link stability scenarios. In (14), \(\Delta v_{ij}(t)\) is a function of the speed changing between two vehicles with time \(t\). The previous study [31], have proved that \(\Delta v_{ij}(t),\Delta v_{i}(t)\) and \(\Delta v_{ij}(t)\) are all independent variables and follow zero-mean Gaussian distribution. Moreover, the link reliability can be calculated as:  
\[d_{ij,t_{1}}=d_{ij,t_{0}}+\Delta d_{ij,t_{1}-t_{0}} \tag{6}\]3  
where \(\Delta v_{j}\sim N\left(0,\sigma_{j}^{2}\Delta t\right),\Delta v_{i}\sim N \left(0,\sigma_{i}^{2}\Delta t\right)\), and \(\Delta v_{j}-\Delta v_{i}\sim N\left(0,\sigma_{i}^{2}\Delta t+\sigma_{j}^{2} \Delta t\right)\), so \(f\left(\Delta v_{j}-\Delta v_{i}\right)\) is the probability density function (PDF) of Gaussian distribution.