Trajectory-Based Optimal Area Forwarding for Infrastructure-to-Vehicle Data Delivery with Partial Deployment of Stationary Nodes

Abstract

This paper proposes a trajectory-based optimal area forwarding (TOAF) algorithm tailored for multihop data delivery from infrastructure nodes (e.g., Internet access points) to moving vehicles (infrastructure-to-vehicle) in vehicular ad hoc networks (VANETs) with partial deployment of stationary nodes. It focuses on reducing the delivery-delay jitter and improving the low reliability of infrastructure-to-vehicle communication. To adapt with the real world, TOAF supposes that stationary nodes are partially installed at intersections in VANETs, and nodes' trajectories can be calculated and predicted, such as using cloud services and GPS, to find the optimal area where the destination vehicle may receive a packet timely. AP selects the optimal area from the trajectory of the destination vehicle and determines the delivery sequence, which includes stationary and mobile nodes from the AP to the optimal area. During delivery, if a new node finds that the delay to the next stationary node is less than that of the current carrier, it can be added to the sequence, reducing the delivery delay. The addition of a new node continues until the packet reaches the optimal area and infrastructure-to-vehicle communication is achieved. The simulation results confirm that TOAF can improve the performance of delivery-delay jitters and reliability of infrastructure-to-vehicle communication with partial deployment of stationary nodes.

1. Introduction

Vehicular ad hoc networks (VANETs) have recently emerged as a promising area of research, since the existing systems cannot always cope with increasing demand in vehicular communication [1–4]. Some new approaches have been developed to lessen packet delay and to efficiently control urban traffic in VANETs. For example, when broadcast communication is not reliable at certain occasions, Access Points (APs) are used to forward a packet to a large number of vehicles. In these cases, each vehicle has a distinctive trajectory and is represented by a mobile sensor node [5]. In addition, with the development of cloud services and dynamic urban technology [6], nodes can compute and process information by working together or individually [7]. Traffic Control Center (TCC) [8] can easily collect road network conditions and maintain vehicle trajectories by using vehicle-to-infrastructure communication [9, 10]. Therefore drivers guided by the data from the TCC can select better driving paths in the VANETs [11]. Drivers can also get the data from the Access Points (APs), which are sparsely deployed in road networks and interconnected with each other to individual vehicles. Generally speaking, all of these applications need to reduce delivery-delay jitter and improve the reliability of infrastructure-to-vehicle system.

Currently, researchers have developed some mechanism to decrease the delivery delay with DSRC (the standardization of IEEE Dedicated Short Range Communications) [12], such as TSF (trajectory-based statistical forwarding) [11] and STDFS (shared trajectory-based data forwarding scheme) [13]. For example, TSF [11] installs stationary nodes at every intersection of road networks to decrease delay of infrastructure-to-vehicle communication. Although the above-mentioned mechanism has achieved great effect, there is still room for improvement. None of them have studied the case with sparse stationary nodes, which are set in the intersections of the road networks.

Due to the good predictability and controllability in the choice of the next forwarding node, stationary nodes are more suitable for data delivery compared with mobile nodes [14]. However, increasing the number of stationary nodes is costly and hard to maintain; so it is not very realistic to install stationary nodes on every intersection in VANETs. In fact, many intersections of real world do not have to contain stationary nodes, and some stationary nodes may be located on roadsides rather than at intersections. The packet forwarding from infrastructure to vehicle under the partial deployment of stationary nodes is more generic and should be paid attention. In this work, we propose a reasonable packet forwarding strategy based on partial coverage of stationary nodes in VANETs. It includes a critical relay node selection method in infrastructure-to-vehicle data delivery.

It is not easy to select a suitable relay node sequence from AP to a mobile vehicle [15], especially when there are sparse stationary nodes with a large number of mobile nodes available in VANETs. A bottleneck in the selection of mobile nodes as relay nodes is the randomness of the position of mobile nodes. However, by means of GPS devices [16], vehicle trajectories are reported to AP via vehicle-to-infrastructure communication timely. So AP can decide which nodes should be set as relay nodes to improve the timeliness and reliability of delivery. In addition, cloud services provide the ability for mobile nodes to calculate delivery delay from their current position to a certain destination position based on their own trajectories. Through comparing with the delay that APs predicted, the mobile node can easily decide whether to add and forward the data packet or not. So, the delivery sequence could be altered by the addition of the new node which can provides less delay according to the actual VANET circumstances at that time.

This paper focuses on two key points during packet delivery: (a) creating a transmission scheme on the basis of vehicle trajectories and (b) adjusting the transmission scheme according to actual circumstance. To create the transmission scheme, we used two kinds of delay distributions in searching for the optimal area: (a) packet delivery-delay distribution from the AP to the optimal area and (b) the vehicle travel-delay distribution from the current position of the destination vehicle to the optimal area. Source nodes (i.e., AP) select the optimal area according to the trajectory of the destination vehicle. An optimal area is identified as a position in VANET, which could get packet from the APs and forward the packet to the destination vehicle, thereby minimizing packet delivery delay while satisfying the required packet delivery probability. Once the optimal area is decided, our TOAF determines the delivery sequence of nodes on the basis of the trajectories data given by TCC, namely, (a) the vehicle trajectories reported to APs and (b) predicted node distribution on the basis of traffic statistics. The system forwards the packet toward the optimal area and constantly adds new nodes with less delay than AP predicted, thus optimizing the delay from the current carrier to the next stationary node in the sequence until the optimal area is reached and infrastructure-to-vehicle communication is achieved. With the application of cloud services and GPS technology, nodes can calculate delivery delay from their current position to a certain position on the basis of its own trajectory and traffic statistics. Using vehicle trajectories instead of traffic statistics improve delay estimates. TOAF ensures effective sequence selection and rearrangement. The intellectual contributions of this study are as follows.

• (1)

An optimal area selection algorithm for infrastructure-to-vehicle data delivery on the basis of partial coverage of stationary nodes.

(2)

An algorithm that determines the delivery sequence of nodes by using vehicle trajectories and traffic statistics.

(3)

A strategy that decreases delivery delay from the AP to the optimal area.

The rest of the paper is organized as follows. Section 2 summarizes related studies regarding VANET communication and generates strategies in relay node selection. Section 3 analyzes the data delivery problem with stationary nodes partially installed in intersections. Section 4 presents the TOAF design. Section 5 shows the effectiveness of TOAF via simulation, and Section 6 concludes the paper.

2. Related Works

Data forwarding in VANET is different from that of traditional mobile ad-hoc networks. Vehicular assisted data dissemination (VADD) [9], static-node assisted adaptive data dissemination (SADV) [5], and trajectory-based data (TBD) [10] schemes process data delivery of vehicle-to-infrastructure communication. VADD utilizes vehicular traffic statistics to achieve data delivery with low delivery delay. SADV proposes a forwarding strategy that leverages stationary nodes in a network for reliable data delivery. TBD utilizes vehicle trajectories and vehicular traffic statistics to decrease communication delay and to increase delivery probability for vehicle-to-infrastructure communication. The above-existing schemes focus on data forwarding from vehicle to a stationary node, such as Access Point (AP).

Trajectory-based forwarding is a hybrid forwarding strategy of the source-based routing and greedy forwarding in ad hoc network [17]. The approximate trajectory is defined by the source node, and each intermediate node makes geographical greedy forwarding along the trajectory, such as DSR and LAR [17]. Unlike these two protocols, DREAM [18] is not an on-demand routing protocol; each node in this proactive location-based protocol maintains a location table for all other nodes in VANET. To maintain the table, each node transmits location packets to other nodes, thus increasing the control overhead. In contrast to DREAM, SIFT [4] proposes a technique where forwarding decisions are shifted from the transmitter to the receiver and are not based on location information but based on timers, which allow network nodes to select themselves in an autonomous fashion as the most appropriate next forwarding node at each intermediate hop without exchanging any type of control messages. It merely uses the trajectory and the location of the last node that forwarded the packet to forward a data packet from a source to a destination. These protocols did not take advantage of the destination vehicles' statistical characteristics.

Trajectory-based statistical forwarding (TSF) [11] presents the first attempt to investigate how to effectively utilize the statistical characteristics of the destination vehicles for infrastructure-to-vehicle data delivery. It uses the stationary node installed in each intersection and on the trajectory of the destination vehicle, which is termed as the target point. This strategy ensures that the packet will arrive earlier at the target point than the destination vehicle. Upon reaching the target point, the destination vehicle receives the packet. However, TSF requires the installation of stationary nodes at all intersections, which is expensive.

Shared trajectory-based data forwarding scheme (STDFS) [13] aims to provide effective vehicle-to-vehicle communication over multihops in VANETs; therefore, STDFS can be used in infrastructure-to-vehicle communication. Shared trajectory information is used to predict encounters between vehicles and to construct a predicted encounter graph. Based on the encounter graph, STDFS optimizes the forwarding sequence to achieve minimal delivery delay given a specific delivery ratio threshold. However, only certain parts of vehicle trajectories can be shared for privacy or other reasons, and obtaining all trajectory information is difficult. The optimization method from the source node to the destination node does not rely on stationary nodes, thereby increasing the complexity of node operation.

Based on the actual construction of the VANET with partial deployment of stationary nodes, we utilize both the stability of the stationary node and the flexibility of the mobile node to achieve optimum delivery performance. The proposed TOAF algorithm selects relay nodes by using trajectory data given by AP and provides nodes with the ability to predict delivery delays. Thus, TOAF provides a reliable and convenient communication strategy for infrastructure-to-vehicle communication.

3. Problem Formulations

This section formulates data forwarding in VANET. This study aims to realize efficient and reliable packet delivery from APs to moving destination vehicles.

3.1. Assumptions

Figure 1 shows that stationary nodes are partially distributed in VANETs, and intersections 2, 5, 7, 8, 10, and 11 do not have stationary nodes. TCC maintains vehicle trajectories without exposing vehicle trajectories to other vehicles. APs are sparsely deployed in VANETs and are interconnected with each other through wired or wireless networks. APs communicate with nodes and provide DSRC devices information regarding these nodes.

Figure 1

Communication mode of nodes in VANET.

APs acquire vehicle trajectories via vehicle-to-infrastructure communication, such as VADD and TBD. TCC shares the traffic graph of the entire VANET with APs. APs can calculate the optimal area where destination vehicles will receive messages and the transfer sequence $V_n=(v_1,v_2,\dots ,v_n)$ , which is selected by APs. Here, $V_n$ is the relay node during data delivery, which includes stationary nodes and mobile nodes from AP to the optimal area. APs select $V_n$ on the basis of vehicle trajectories and predicted traffic statistics. Packets are carried or forwarded by the current relay node in the transfer sequence, or new nodes with shorter delays are added in the sequence until the destination vehicle reaches the optimal area. Delivery ratio relies on stationary nodes, and APs calculate the sequence of stationary node distribution to meet the delivery ratio threshold required by the user.

3.2. Identification of the Optimal Area

Let $f(p)$ be the probability distribution function of the packet delay P, $g(v)$ the probability distribution function of the destination vehicle delay V, TTL the time-to-live (TTL) of the packet, and α the delivery ratio threshold required by the user. In TSF, all the stationary nodes in the intersections are denoted by I, where $i\in I$ is one point in I. The point i should satisfy the following equation to become a target node:

$$\begin{array}{cc}& P\left[p_i\le V_i\right]={\int }_{\mathrm{0}}^{\text{TTL}}‍{\int }_{\mathrm{0}}^{v}f\left(p\right)g\left(v\right)dp\hspace{0.17em}dv\ge \alpha .\end{array}$$

(1)

Optimal target point selection depends on the TTL, the packet delay model P, and the vehicle delay model V, which are described in [11]. Different from TSF, the proposed TOAF is based on partial coverage by stationary nodes. Moreover, the two schemes have different delay distributions. We can decide on the location of the optimal area. However, we cannot choose a target stationary node because stationary nodes may not be present in the trajectories of the destination vehicle. Thus, we need other relay nodes to deliver or forward packets to the optimal area, which is based on the trajectories of the destination vehicle.

3.3. Delay Distribution

3.3.1. Vehicle Delay Distribution

The destination vehicle V travels in the region G with Gamma distribution. Let $E(G)$ be the edge in the VANET. For any edge $e_i\in E(G)$ , the delay $t~\mathrm{\Gamma }({\kappa }_i,{\theta }_i),{\kappa }_i,{\theta }_i$ is computed by using the average vehicle traveling delay ${\mu }_i$ and the travel-delay variance ${\delta }_i^2$ by using equations $E[t_i]={\kappa }_i{\theta }_i$ and $\mathrm{Var}[t_i]={\kappa }_i{\theta }_i^2$ . Thus, the parameters ${\kappa }_i$ , ${\theta }_i$ are computed as follows:

$$\begin{array}{cc}& {\theta }_i=\frac{{\delta }_i^{\mathrm{2}}}{{\mu }_i},\hspace{1em}\hspace{1em}{\kappa }_i=\frac{{\mu }_i^{\mathrm{2}}}{{\delta }_i^{\mathrm{2}}}.\end{array}$$

(2)

The vehicle delay distribution in each edge $e_i$ could be computed according to the average delay $E[t_i]$ and variance $\mathrm{Var}[t_i]$ of the vehicle. Assuming that the destination vehicle has moved from the current position to the optimal area, we need to go through N edges in $E(G)$ because the delay distribution of each road is relatively independent from each other. The total vehicle delivery delay is $E[V]={\sum }_{i=\mathrm{1}}^N{\mu }_i$ , and the variance is $\mathrm{Var}[V]={\sum }_{i=\mathrm{1}}^N{\delta }_i^{\mathrm{2}}$ . Thus, the end-to-end delay distribution of the destination vehicle from the current position to the optimal area can be expressed as follows:

$$\begin{array}{l}V~\mathrm{\Gamma }\left({\kappa }_v,{\theta }_v\right),\hspace{1em}\hspace{1em}E\left[V\right]={\kappa }_v{\theta }_v,\hspace{1em}\hspace{1em}\mathrm{Var}\left[V\right]={\kappa }_v{\theta }_v^{\mathrm{2}},\\ \hfill \hspace{1em}\text{for}\mathrm{\hspace{0.17em}\hspace{0.17em}}V,{\kappa }_v,{\theta }_v>\mathrm{0}.\end{array}$$

(3)

3.3.2. Delay Distribution from AP to the Optimal Area

(I) Delay Distribution between Stationary Nodes. Assume that intersection i is adjacent to intersection j and each intersection has its own stationary node. Let l be the distance between i and j, such that the following two cases exist.

(A) Immediate Forward. In both carry and forward cases, a packet carrier obtains the packet from stationary node i. The packet carrier encounters a vehicle within the DSRC communication range R and forwards the packet to the front node; otherwise, the packet carrier delivers the packet to the communication range of stationary node j. Let the forwarded distance be $l_f$ and the speed of the vehicle v, and the delay for the forwarded distance is only tens of milliseconds, such that we can ignore the delay because it is several orders-of-magnitude less than the carry delay. Set the average rate of the vehicle reaching the intersection i as λ, which obeys the Poisson process. R is the communication range, and v is the vehicle speed. Consider the message forwarding probability $P_f=\beta =\mathrm{1}-e^{-(\lambda R/v)}$ , which denotes that at least one vehicle arrives at the intersection i for the duration $R/v$ ; thus, the delay is $((l-R-E[l_f])/v)\beta$ .

(B) Wait and Carry. Stationary node i waits for a vehicle and forwards the packet to the vehicle. The vehicle then carries the packet to the communication range of the stationary node i. The waiting probability is $P_w=\mathrm{1}-\beta ={e^{-}}^{(\lambda R/v)}$ , and the delay is $(\mathrm{1}/\lambda +(l-R)/v)(\mathrm{1}-\beta )$ .

The node then delays distributions from i to j as $P~\mathrm{\Gamma }({\kappa }_d$ , ${\theta }_d)$ , where

$$\begin{array}{l}\hspace{1em}E\left[d_i\right]=\frac{l-R-E\left[l_f\right]}{v}\beta +\left(\frac{\mathrm{1}}{\lambda }+\frac{l-R}{v}\right)\left(\mathrm{1}-\beta \right),\\ \hspace{0.17em}\mathrm{Var}\left[d_i\right]=E\left[d_i^{\mathrm{2}}\right]-{\left(E\left[d_i\right]\right)}^2\\ \hspace{1em}\hspace{0.17em}\hspace{1em}\hspace{1em}=\frac{{\left(l-R\right)}^2-\mathrm{2}\left(l-R\right)E\left[l_f\right]+E\left[l_f^{\mathrm{2}}\right]}{v^{\mathrm{2}}}\beta \\ \hspace{1em}\hspace{0.17em}\hspace{1em}\hspace{1em}+{\left(\frac{\mathrm{1}}{\lambda }+\frac{l-R}{v}\right)}^2\left(\mathrm{1}-\beta \right)\\ \hspace{1em}\hspace{0.17em}\hspace{1em}\hspace{1em}-{\left(\frac{l-R-E\left[l_f\right]}{v}\beta +\left(\frac{\mathrm{1}}{\lambda }+\frac{l-R}{v}\right)\left(\mathrm{1}-\beta \right)\right)}^2.\end{array}$$

(4)

(II) Delay Distribution from AP to the Optimal Area. Given that the edges with stationary nodes are independent of each other, the average delay from AP to the optimal area with stationary node coverage is $E[P]={\sum }_{i=\mathrm{1}}^{N}E[d_i]$ and the variance is $\mathrm{Var}[P]={\sum }_{i=\mathrm{1}}^N\mathrm{Var}[d_i{]}^{\mathrm{2}}$ . By using $E[P]={\kappa }_p{\theta }_p$ and $\mathrm{Var}[P]={\kappa }_p{\theta }_p^2$ , we can calculate the distribution function of the data delivery delay between AP and the optimal area as follows:

$$\begin{array}{cc}& P~\mathrm{\Gamma }\left({\kappa }_p,{\theta }_p\right),\hspace{1em}\text{for}\hspace{0.17em}P,{\kappa }_p,{\theta }_p>\mathrm{0}.\end{array}$$

(5)

(III) Delay Distribution between Intersections without Stationary Nodes. Figure 1 denotes that regardless of intersections 6-7-8–12 or other delivery paths, each intersection is not guaranteed to have at least one stationary node. Thus, the delay of intersections 6–12 needs to be recalculated.

The delay distribution on each edge is consistent with previous descriptions. However, in this study, messages can only be forwarded to another vehicle or carried by the current vehicle in the intersection. Directly calculating the delay between two stationary nodes is difficult. However, by utilizing the vehicle trajectory, we can obtain the trajectory by using three information: report from the vehicle, vehicle owned, or traffic statistics. Suppose a vehicle will travel along a trajectory denoted by a sequence of intersections $j\in N(n)$ between two stationary nodes; then the last intersection of $N(n)$ is N. We can calculate the delay as follows.

Let D be the expected delivery delay (EDD) of the packet, which is located in the source node and transmitted to the intersection N. The probability that a packet is being carried by a vehicle from intersection 1 to intersection j is $P_c={\prod }_{h=\mathrm{1}}^{j-\mathrm{1}}{P}_{h,h+\mathrm{1}}^c$ , and $P_{h,h+\mathrm{1}}^c=\mathrm{1}-{\prod }_{k\in N(h)}{P}_{hk}$ is the carrying probability from h to $h+1$ , where $N(h)$ is the neighbor intersections of h and $P_{hk}$ is the forwarding probability that the vehicle at intersection h can forward its packets to another vehicle moving toward the neighboring intersection k. The forwarding probability can be obtained by using traffic statistics. The total carried time of the packet from the source node to intersection j along the trajectory is $C_{1j}={\sum }_{k=1}^{j-1}{l}_{k,k+1}/v$ . $E_j$ is the EDD after the packet leaves the current vehicle at j, $D_{jk}$ is the EDD from j to the destination node N when the edge $e_{jk}$ is used as the forwarding edge, and $E_j={\sum }_{k\in N(j)}{P}_{jk}{D}_{jk}$ . Therefore,

$$\begin{array}{l}D=\sum _{j=\mathrm{1}}^N\left(P_c\times \left(C_{\mathrm{1}j}+E_j\right)\right)=\sum _{j=\mathrm{1}}^N(\phantom{\left(C_{\mathrm{1}j}+\sum _{k\in N\left(j\right)}^{}{P}_{jk}{D}_{jk}\right)}\left(\prod _{h=\mathrm{1}}^{j-\mathrm{1}}{P}_{h,h+\mathrm{1}}^c\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.5em}\times \left(C_{\mathrm{1}j}+\sum _{k\in N\left(j\right)}^{}{P}_{jk}{D}_{jk}\right)).\end{array}$$

(6)

For example, from intersection 6 to intersection 12 in Figure 1, the EDD of a vehicle with the trajectories 6-7-8–12, can be calculated as follows:

$$\begin{array}{l}D=P_{\mathrm{6,7}}{D}_{\mathrm{6,7}}+\mathrm{\hspace{0.17em}\hspace{0.17em}}{P}_{\mathrm{6,10}}{D}_{\mathrm{6,10}}\mathrm{\hspace{0.17em}\hspace{0.17em}}+P_{\mathrm{6},\mathrm{7}}^C\mathrm{\hspace{0.17em}\hspace{0.17em}}\\ \hspace{1em}\hspace{1em}\times \left(C_{\mathrm{6,7}}\mathrm{\hspace{0.17em}\hspace{0.17em}}+P_{\mathrm{7,6}}{D}_{\mathrm{7,6}}+\mathrm{\hspace{0.17em}\hspace{0.17em}}{P}_{\mathrm{7,8}}{D}_{\mathrm{7,8}}+\mathrm{\hspace{0.17em}\hspace{0.17em}}{P}_{\mathrm{7,3}}{D}_{\mathrm{7,3}}\right)\\ \hspace{1em}\hspace{1em}+P_{\mathrm{6,7}}^C{P}_{\mathrm{7,8}}^C\mathrm{\hspace{0.17em}\hspace{0.17em}}\left(C_{\mathrm{6,8}}\mathrm{\hspace{0.17em}\hspace{0.17em}}+P_{\mathrm{8,4}}{D}_{\mathrm{8,4}}+\mathrm{\hspace{0.17em}\hspace{0.17em}}{P}_{\mathrm{8,7}}{D}_{\mathrm{8,7}}+\mathrm{\hspace{0.17em}\hspace{0.17em}}{P}_{\mathrm{8,12}}{D}_{\mathrm{8,12}}\right)\\ \hspace{1em}\hspace{1em}+\mathrm{\hspace{0.17em}\hspace{0.17em}}{P}_{\mathrm{6,7}}^C{P}_{\mathrm{7,8}}^C\mathrm{\hspace{0.17em}\hspace{0.17em}}{P}_{\mathrm{8,12}}^C\mathrm{\hspace{0.17em}\hspace{0.17em}}\left(C_{\mathrm{6,12}}\mathrm{\hspace{0.17em}\hspace{0.17em}}+P_{\mathrm{12,8}}{D}_{\mathrm{12,8}}+\mathrm{\hspace{0.17em}\hspace{0.17em}}{P}_{\mathrm{12,11}}{D}_{\mathrm{12,11}}\right).\end{array}$$

(7)

However, if no vehicle contains the trajectories 6-7-8–12, the EDD also can be calculated by the prediction from the traffic statistics given.

We could estimate the delay of the packet along the edges without stationary nodes. Figure 2 shows that paths $T_1$ and $T_2$ can reach the target point, node 4. Moreover, path $T_1$ could not rely on the stationary node in intersections 10 and 5. The delay of the edges of 9-10-11 and 12–5-4 should be re-estimated. When the edges of 8-7-6 and 6-5-4 in path $T_2$ are the same as $T_1$ , we can calculate the EDD of the edges without stationary nodes as follows:

$$\begin{array}{cc}& D_{T\mathrm{1}}=D_{\mathrm{9,11}}+D_{\mathrm{12,4}},\hspace{1em}\hspace{1em}\mathrm{\hspace{0.17em}\hspace{0.17em}}{D}_{T\mathrm{2}}=D_{\mathrm{8,6}}+D_{\mathrm{6,4}}.\end{array}$$

(8)

Figure 2

Multiple paths in VANET with partial coverage by stationary nodes.

3.4. Infrastructure-to-Vehicle Communication Strategy

Given that $D_{T_i}$ is the minimum EDD of the packet transmitted along the certain path $T_i$ in edges without stationary nodes, we can calculate the delay of each path by using (6), which is based on the vehicle trajectories or traffic statistics. Taking for example, $D_{T_1}$ in Figure 2, AP obtains the vehicle distribution of intersections 9–11 according to the average delay of intersections 8-9 and the vehicle trajectories. AP then uses traffic statistics if no vehicle report is available in its trajectory and then calculates the delay of intersections 9–11 and intersections 12–4. AP could set up a new TTL for the packet $\text{TT}{\text{L}}_{\text{new}}=\text{TTL}-D_{T_i}$ . The position of the target point, which is our optimal area, can be obtained using the following equation:

$$\begin{array}{cc}& P_{\mathrm{1}}={\int }_{\mathrm{0}}^{\text{TT}{\text{L}}_{\text{new}}}‍{\int }_{\mathrm{0}}^{v}f\left(p\right)g\left(v\right)dp\hspace{0.17em}dv\ge \alpha .\end{array}$$

(9)

The optimal area is the area where the target point forwards the message to the destination vehicle v. AP selects the target point in the greater range in VANET when no stationary nodes are available on the trajectories of the destination vehicle. Otherwise, AP finds a vehicle traveling the opposite route of the destination vehicle and uses this vehicle as the target vehicle. Thus, the target vehicle receives the packet before encountering the destination vehicle. Let the traveling delay of the destination vehicle be $V~\mathrm{\Gamma }({\kappa }_v,{\theta }_v)$ , and vehicles $v_1,v_2,\dots ,v_m$ have their respective traveling delay distributions of $V_j~\mathrm{\Gamma }({\kappa }_{vj},{\theta }_{vj}),j=\mathrm{1,2},\dots ,m$ . We first determine $v_j$ , which is a vehicle that could encounter the destination vehicle. The stationary nodes in the trajectory of $v_j$ are satisfied by the following equation:

$$\begin{array}{cc}& \left(\mathrm{1}\right)P_{\mathrm{1}}={\int }_{\mathrm{0}}^{\text{TTL}}‍{\int }_{\mathrm{0}}^{v}g\left(v\right)g\left(v_j\right)dp\hspace{0.17em}d{v}_j\ge \alpha ,\hspace{1em}\hspace{1em}\\ \left(\mathrm{2}\right)P_{\mathrm{2}}={\int }_{\mathrm{0}}^{\text{TT}{\text{L}}_{\text{new}}}‍{\int }_{\mathrm{0}}^{v}f\left(p\right)g\left(v_j\right)dp\hspace{0.17em}d{v}_j\ge \alpha .\end{array}$$

(10)

The delivery process is divided into two steps: first, AP delivers the packet to vehicle $v_j$ through the target point discussed above; second, $v_j$ forwards the message to the destination vehicle v. The area where $v_j$ forwards the message to the destination vehicle v is the optimal area.

4. TOAF Algorithm

The AP in our TOAF algorithm could obtain vehicle trajectories and predict the node distribution on the basis of traffic statistics through TCC. The AP first determines the optimal area for delivery according to the partial coverage of stationary nodes in intersections and then creates the transfer sequence $V_n=(v_1,v_2,\dots ,v_n)$ by predicting all mobile nodes that reported their trajectories. AP predicts the delay of each stationary node $S_n=(s_1,s_2,\dots ,s_n)$ , in which $s_n$ is the position of the optimal area. The node $v_i$ in $V_n$ delivers the packet according to $V_n$ . When $v_i$ , which is the node carrying the packet, encounters a new node not in the sequence, the new node calculates the EDD to the next stationary node $s_i$ in $S_n$ by using (6) based on its own trajectory and traffic statistics. The new node is added to the sequence if the calculated EDD is less than $v_i$ , provided that the delivery ended when the packet is forwarded to the optimal area $S_n$ .

The delivery from AP to the optimal area is divided into two cases, which is based on whether stationary nodes exist within the TTL in the trajectory of the destination vehicle.

4.1. Coverage by Stationary Nodes in the Trajectory of the Destination Vehicle in TTL

If the predicted vehicle of AP encounters stationary nodes in its trajectory, select a stationary node as the optimal area. The algorithm strategy is as follows:

• (1)

determine the optimal area $S_n$ in the trajectory of the destination vehicle by using (9),

(2)

AP selects the delivery sequence $V_n$ and sends the packet to the optimal area through the sequence. When the node $v_i$ , which carries the packet, encounters a new node $v_{\text{new}}$ , the new node estimates the $\text{EDD}=D_{\text{new}}$ to the next stationary node according to traffic statistics and its own trajectory by using (6). If $D_{\text{new}}$ has a shorter delay than the node $v_i$ in the sequence, add $v_{\text{new}}$ to $V_n$ until the packet reaches the optimal area $s_n$ . If the destination vehicle arrives at the optimal area when the packet is forwarded to $s_n$ , the destination vehicle gets the packet from $s_n$ , thus completing the delivery process. Node $s_n$ forwards the packet along the reverse trajectory of the destination vehicle when this node has the packet earlier than asked. TOAF adds a new node with less delay to the next stationary node in sequence; therefore the EDD will be lower than predicted. Delivery probability is guaranteed by the stationary nodes because TOAF creates a sequence under the delivery probability α. TOAF does not maintain a backup for each node, thus making sure that the efficiency of frequency resources is maximized.

4.2. No Stationary Node in the Trajectory of the Destination Vehicle in TTL

If AP predicts that selecting a stationary node in the trajectory of the destination vehicle in TTL is impossible, then AP selects a target vehicle $v_j$ as relay node from vehicles that could encounter the destination vehicle. AP determines the sequence $V_n$ , from AP to $v_j$ , as well as sequence $V_m$ from $v_j$ to the optimal area of the destination vehicle.

• (1)

Determine the target vehicle $v_j$ according to  (10).

(2)

Deliver the packet from AP to the target vehicle $v_j$ , as discussed in Section 4.1.

(3)

Deliver the packet from target vehicle $v_j$ to the destination vehicle. $v_j$ delivers the packet to the destination vehicle as sequence $V_m$ and constantly adds a node that has shorter delay from the current position to the optimal area of the destination vehicle. TOAF ensures the timeliness and reliability of delivery by constantly revising the sequence on the basis of the actual traffic.

5. Performance Evaluation

We evaluate the performance of TOAF in this section. The model is based on the description given in [11]; we have built a simulator based on the scheduler provided by SMPL [19] in C with the following settings. A road network with 49 intersections is used in the simulation, and one Access Point is deployed in the center of the network. Each vehicle's movement pattern is determined by a Hybrid Mobility Model of City Section Mobility Model [20] and Manhattan Mobility model [21]. The vehicles are randomly placed at one intersection as a start position among the intersections on the road network, randomly select another intersection as an end position, and wait for a random waiting time (i.e., uniformly distributed from 0 to 10 seconds) at intersections in order to allow the impact of stop sign or traffic signal.

The simulation configuration is shown in Table 1, which has 49 intersections in the range of $\mathrm{8.25}\hspace{0.17em}\text{km}\mathrm{\hspace{0.17em}\hspace{0.17em}}\times \mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{9}\hspace{0.17em}\text{km}$ . The communication range is 200 m, and vehicle speed follows the normal distribution of $N({\mu }_v,{\sigma }_v)$ . The maximum and minimum speeds are, respectively, ${\mu }_v+3{\sigma }_v$ and ${\mu }_v-3{\sigma }_v$ . The default ${\mu }_v$ is 40 MPH, the default ${\sigma }_v$ is 5 MPH, and vehicles can change their speed at each road section. The vehicle travel path length is $l~N({\mu }_l,{\sigma }_l)$ , where ${\mu }_l=d_{i,j}$  km is the shortest path distance from start position i to end position j in VANET, and ${\sigma }_l=3$  km determines a random detour distance. We assume that APs predict the node distribution on the basis of trajectories reported from vehicles and traffic statistics. Packets are dynamically generated randomly from APs to any selected vehicle. The total number of generated packets is 2,000, and the simulation is continued until all of these packets are either delivered or dropped due to TTL expiration. We set the TTL to 2000 s and the delivery probability bound α to 0.9. Considering the randomness of stationary node coverage, we compared TOAF in different stationary node coverage ratios with flooding algorithm (without considering communication conflict and storage limit) and compared with the TSF algorithm and flooding algorithm under different situations in 20% coverage ratio.

Table 1

Simulation configuration.

Parameter	Description
Road network	The number of intersections is 49 The area of the road map is 8.25 km × 9 km
Communication range	R = 200 m
Number of vehicles (N)	The number of vehicles moving within the road network. The default value of N is 250
Time-to-live (TTL)	The expiration time of a packet. The default TTL is the vehicle trajectory's lifetime and it is the vehicle's travel time for the trajectory, that is, 2,086 seconds
Vehicle speed (v)	$v~N({\mu }_v,{\sigma }_v)$ ,  where ${\mu }_v=\left\{\mathit{20,25},\dots ,\mathrm{60}\right\};{\sigma }_v=\{\mathit{1,2},\dots ,\mathrm{10}\}$ , the maximum and minimum speeds are, respectively, ${\mu }_v+3{\sigma }_v$ and ${\mu }_v-3{\sigma }_v$ . The default ${\mu }_v$ is 40 MPH and the default ${\sigma }_v$ is 5 MPH
Vehicle travel path length (l)	$l~N({\mu }_l,\hspace{0.17em}{\sigma }_l)$ , where ${\mu }_l=d_{i,j}$  km is the shortest path distance from start position i to end position j in VANET, and ${\sigma }_l=3$  km determines a random detour distance

5.1. Delivery in Different Coverage Ratios of Stationary Nodes

TOAF mainly predicts the delivery sequence by AP. The stationary nodes in sequence deliver packets with 100% probability. Thus, EDD and delivery ratio are easy to control in stationary nodes. AP creates a reasonable sequence according to the actual situation of the VANET. The current node adjusts the sequence in accordance with the actual situation of the VANET, thus improving the delivery performance under different coverage ratios by stationary nodes. Figure 3 shows that the delivery delay and the delivery ratio have a slight decline with decreased distribution of stationary nodes. Nevertheless, even in the case of 20% coverage, the delivery delay and the delivery ratio are close to full coverage and are close to flooding algorithm. The flooding algorithm is a theoretical algorithm subjected to hardware performance and traffic congestion. AP selects sequences on the basis of the optimal area in the trajectory of the destination vehicle and adjusts the nodes during delivery to satisfy the effectiveness and reliability requirements of the infrastructure-to-vehicle communication.

Figure 3

Performance in different coverage ratios of stationary nodes.

5.2. Influence of Vehicle Number N

Traffic prediction in TOAF may be influenced by the trajectories of moving vehicles. We consider 50 vehicles to 400 vehicles in this study. Figure 4 shows that increasing traffic improves delivery ratio and delay performance. Delivery ratio and delay performance leveled off when more than 150 vehicles were used. The delivery ratio was over 90% when 50 vehicles were used. The delay is slightly lower than the TSF when the number is less than 200, because the sequence is based on the traffic at the beginning of delivery, rather than based on stationary nodes waiting for the arrival of the next vehicle at each intersection. Thus, TOAF can adapt to actual circumstances of VANET by utilizing both stationary nodes and mobile nodes. The flooding delay is significantly lower when a small number of vehicles are involved, which shows that flooding still has a strong competitive advantage in the case of small traffic.

Figure 4

Influence of vehicle number N.

5.3. Influence of Vehicle Speed ${\mu }_v$

Figure 5 shows that for flooding, TSF, and TOAF with 20% coverage, high-speed vehicles result in low delivery delay because high-speed vehicles yield high vehicle arrival rates at each road segment. The delay in TOAF is less than that of TSF when low-speed vehicles are used because TOAF could add new nodes during the process and TOAF has more chances to decrease the delay. At all vehicle speeds, the performance of TOAF is still close to that of TSF. As shown in Figure 5, when the mean speed is very low, the delivery ratio of TOAF is better than that of TSF. Sequence selection in TOAF ensures that the delivery ratio and performance improves with vehicle speed. Thus TOAF can be used in different circumstances in the VANET.

Figure 5

Influence of vehicle speed ${\mu }_v$ .

5.4. Influence of Vehicle Speed Deviation ${\sigma }_v$

We used vehicle speed deviation to reflect the traffic condition. As shown in Figure 6, average delay increased in TOAF with greater speed deviation. TOAF has lower average delay than TSF because the former adds new nodes under actual circumstance to decrease the delay. The packet delivery ratio has no obvious decrease with increasing speed deviation, and the delivery ratio performance of TOAF is nearly the same as that of TSF and flooding algorithm. These data show that utilizing a small number of stationary nodes can ensure stable delivery ratios. The accuracy and effectiveness of packet forwarding by TOAF will improve when stationary and mobile nodes are both utilized.

Figure 6

Influence of vehicle speed deviation ${\sigma }_v$ .

6. Conclusion

TOAF is an algorithm based on the actual construction of the VANET with partial coverage of stationary nodes. TOAF continuously adjusts forwarding node sequences during delivery on the basis of actual VANET by predicting the optimal area to the destination vehicle and by selecting a nodes sequence from the AP to the optimal area. Combining the stability of the stationary node with the flexibility of the mobile node, TOAF reduces the randomness of the delivery process and improves the delivery ratio. TOAF also reduces the delay jitters and improves the reliability of infrastructure-to-vehicle communication. The simulation results further validate the effectiveness of TOAF in practice. For our future work, we will explore infrastructure-to-vehicle data forwarding by using the stationary node installed on roadsides, but not at the intersections (e.g., brand of bus station).