Dubhe: A Reliable and Low-Latency Data Dissemination Mechanism for VANETs

Abstract

Many attractive applications over vehicular ad hoc networks (VANETs) need data to be transmitted to the remote destinations through multihop data forwarding, but some unique characteristics of VANETs (i.e., high node mobility, dynamic topology changes with frequent link breakage, and unstable quality of wireless transmission) incur unstable data delivery performance. In order to reliably and quickly disseminate the data, we present Dubhe which includes a delay model and an improved greedy broadcast algorithm embedded with a coverage elimination rule. The former is used for making decisions for path selection with the aim of minimizing the transmission latency, while the latter focuses on boosting the reliability of one-hop data transmission. We also analyze the necessity and effectiveness of Dubhe and the retransmission overheads theoretically. It is shown from the experiments that Dubhe can achieve high-reliability and low-latency data delivery in comparison with the epidemic-based protocol and the static-node-assisted adaptive data delivery protocol.

1. Introduction

As a mobile and self-organizing network, a VANET is built over two types of nodes on an as-needed basis, that is, the mobile nodes equipped with on-board units (OBUs) and the stationary wireless stations deployed along the roads known as roadside units (RSUs). Both OBUs and RSUs have wireless interfaces to connect together or to the other equipment such as traffic lights. The communication over a VANET can be done by means of vehicle-to-vehicle (V2V) and Vehicle-to-Infrastructure (V2I) communications. Based on these communications, many promising applications over VANETs can be envisioned in the future with the help of enabling technologies (e.g., vehicular positioning, digital maps, and sensors), such as active safety applications, intelligent transportation applications, and various convenience applications for drivers and passengers. More specially, VANETs are also underlying networks to provide access to the Internet, as well as data transmission in case of emergency (earthquakes, traffic jams, etc.) [1].

In this paper, we focus on the reliable and low-latency long distance data transmission in urban scenarios, which is indispensable to many applications. For example, a moving vehicle may initiate an inquiry for available parking lots of a business center several miles away to decide the next travel destination; the hazardous traffic situations collected by vehicles cooperatively need to be diffused timely to the infostations deployed at adjacent blocks so as to remind the driver of rerouting. Although RSUs connected to the backbone networks can provide a stable link for the data transmission, the high expenses impose restriction on the deployment of RSUs on a large scale, especially in the initial phase of deploying a VANET. A common idea is to place RSUs at intersections firstly in urban areas, where the RSUs can take on multiple roles: storing the received data temporally, making the decisions on the data routing, and forwarding the data to the passing vehicles if necessary. Meanwhile, vehicles have to cooperate with each other to deliver the data. That is, a vehicle will forward the data in case that there is a chance to establish a wireless link with other vehicles; otherwise, it will carry the data by itself.

The wireless connections among vehicles are extremely uncertain owing to the rapid movements of vehicles. When vehicles are sparse, the VANET falls into a disruptive network [2]. However, a dense vehicle flow may lead to severe channel contentions due to the broadcast nature of the VANETs. Therefore, the key issue of the data delivery over a VANET is how a vehicle node on a road segment determines its action: carrying on or forwarding or dropping the received packets, and how a node (a vehicle or an RSU) at an intersection chooses the optimal paths for the packets to be delivered.

As far as the selection of relay nodes is concerned, some algorithms including the broadcast suppression techniques [3] have been developed to assist in the selection of rebroadcasting nodes, but they lack the theoretical analysis on the reliability of data delivery. On the other hand, as for the routing path selection, a variety of data delivery protocols have been proposed. Typically, while a data packet is transmitted to a node at an intersection, the optimal path aiming at minimizing the transmission delay is expected. Some protocols require nodes to maintain the routing information [4, 5], as thus, considerable packets have to be exchanged to keep routing tables up to date. However, some other protocols (e.g., VADD [6]) exploit the historical traffic data to decide the path for packet forwarding. Obviously, the historical data are almost certainly inconsistent with the constantly changing traffic situations. So far, lacking an accurate model of reflecting the time-varying connectivity of a VANET has become the biggest obstacle to improving the performance of data delivery, where the connectivity refers to the probability that a node (i.e., a vehicle or an RSU) can communicate with any other nodes through wireless communication.

Motivated by the limitations of the existing protocols and noting that the vehicles in a typical city scenario are restricted in grid roads, we present Dubhe, a reliable and low-latency data delivery mechanism for transmitting data to stationary roadside infrastructures several miles away from source vehicles by unicast communication. Dubhe comprises a delay model, a path choosing algorithm, and an improved greedy broadcast algorithm. The delay model is responsible for estimating the transmitting delay between the adjacent intersections with RSUs deployed, the path choosing algorithm is used for determining the optimal path for the packet arriving at RSUs, and the broadcast algorithm concentrates on improving the reliability of one-hop data transmission. The contributions of this paper include the following aspects.

• (1)

We propose a delay model which takes account of the road topology and the interference of the traffic signals in an urban scenario. We also give our path choosing algorithm on the basis of the delay model.

(2)

We present an improved greedy broadcast algorithm merged with a coverage elimination rule. The multi-candidate strategy in algorithm can enhance the reliability of one-hop data transmission.

(3)

We analyze the necessity and feasibility of the multicandidate strategy for 1-hop data transmission and the corresponding retransmission ratio theoretically.

(4)

We evaluate the performance of Dubhe by conducting extensive experiments to examine the performance and cost metrics (i.e., delivery ratio, transmission delay, and message overhead) over three independent factors (i.e., vehicle density, traffic signal cycle, and connectivity estimation period).

The rest of this paper is organized as follows. In Section 2, we introduce the existing researches related to data delivery mechanisms over VANETs. In Section 3, we describe our delay model and path choosing algorithm. And then, we present our greedy broadcast algorithm and analyze the reliability and the retransmission ratio in Section 4. In Section 5, we conduct the performance evaluation. Finally, we summarize our work in Section 6.

2. Related Work

Rapid changes of network topology, lack of central coordination, and limited bandwidth are stumbling blocks to efficient data delivery over VANETs [7]. Besides, radio channels are error-prone. The wireless signals interfere with vehicles in unpredictable ways, and the fading phenomenon (the multipart of the same wireless signal traveling along different paths that interfere with each other) deteriorates the channel quality even in the case of no neighbor trying to transmit simultaneously. All lead to apparently nondeterministic packet reception.

As is known, the best-effort manner is commonly used for data delivery over a MANET. For example, following the epidemic based data delivery (EBDD) protocol [8], a node exchanges digests of all data packets with other nodes as long as they can communicate with each other. Then they transmit the data packets that do not appear in the packet lists of counterparts in turn. However, the performance degrades quickly while facing a high vehicle density owing to the excessive repeated packet exchanging.

Due to the broadcast nature of wireless signals, a wireless transmission with the target to a particular destination vehicle can be overheard by all neighboring vehicles; how to choose an appropriate relay vehicle from multiple candidates is a tough task. In [9], a decentralized broadcast algorithm is presented to achieve a good broadcast coverage in a VANET. Beside the broadcast suppression techniques introduced in [3], a connected dominating set (CDS) on the basis of local beacon messages is proposed in [10] with the expectation of repressing the overhead of broadcast. As thus, only the nodes within a CDS have a chance to transmit the received packets. Although broadcast messages are partially diminished, the CDS suffers from the overheads for constant CDS construction owing to the fast movements of nodes. Obviously, their goal is different from ours.

Further, in order to find an efficient path for forwarding the packet, some studies propose to propagate the vehicle density of roads among vehicles to acquire the route decision-making information, for example, periodical probing packets are used [4] to collect the vehicle density proactively and then are exchanged among neighbors. Obviously, packets for probing and propagating route information induce massive overheads. By contrast, [5, 11] employ a reactive route discovery approach with the help of the relay nodes. However, the routing tables are out of date quickly because of the mobility of the relay nodes. Since the historical data of traffic flow are an important basis for deciding the optimal path, vehicle-assisted data delivery (VADD) [6] exploits the historical records of the vehicle density marked on a digital map so that a node can decide the minimum delay paths for the arriving packets. But the time-varying vehicle density may deviate far from the one marked on the map. To remedy the weakness, [12] presents a static-node-Assisted adaptive Data delivery protocol for Vehicular networks (SADV), which suggests to place static nodes at intersections to assist packet forwarding. Each static node has the capability of storing the received packets until they can be forwarded to a vehicle travelling toward the optimal forwarding road. Meanwhile, transmission delay is piggybacked in data packets to help forwarding decisions. Nevertheless, SADV is designed entirely without consideration for the impact of the spatial distribution of vehicles on the connectivity of VANETs. Similarly, [13] suggests buffering data in the parked vehicles along the roads if no appropriate route path for data forwarding is available in urban areas. But the efficiency of data delivery is unstable, depending on the number of vehicles which are willing to relay messages as volunteers.

To enhance the adaptation and scalability of routing protocols, [14] proposes to select the intermediate nodes according to the group mobility patterns, importance of the messages, destination, current location, and speed of the vehicles. Reference [15] periodically evaluates the SIR (signal-to-interference ratio) values on the available transmission channels and chooses the channel with the best perceived SIR to deliver the data. Reference [16] presents a hierarchical routing scheme for data forwarding decisions, which makes use of peer servers to discover the trajectory from a source to a destination. However, the overhead of electing peer servers and maintaining the information on the peer servers is not ignorable. On the behalf of enhancing the reliability of data transmission over VANETs, [17] proposes to utilize black-burst signals to prevent the receivers from concurrent rebroadcasting. At the same time, [17] employs acknowledgement packets to improve the reliability and a mechanism similar to the RTS/CTS handshake to decrease the effects of the hidden nodes. But the overheads incurred by the black-burst and the acknowledgement messages restrict its scalability.

The network connectivity is crucial to efficiently deliver data over VANETs. Usually, one-hop connectivity between node i and node j can be specified as $P_r(d(i,j)<R)$ , where $d(i,j)$ is the Euclidean distance between two nodes, and R denotes the radius of wireless transmission (Table 2). Reference [18] examines the connectivity of VANETs in an urban scenario by experiments, and the results show that the probability of an uninterrupted multi-hop link decreases exponentially with the increasing length of the road. More concretely, when the vehicle density is 4 vehicles/250 m, the probability of the formation of a 1000 m wireless communication is just 68%, and 42% as the road length is increased to 2000 m. While the vehicle density reduces to 2 vehicles/250 m, the corresponding probabilities decline to 21% and 7%, respectively. Hence, some studies believe that it is unfeasible to achieve reliable and efficient data delivery without the support of RSUs [18]. Further, the experimental results in [19] also indicate that once the vehicle density is below a specified threshold (e.g., 60 vehicles/km²), the quality of service of data transmission cannot be satisfied if it relies solely on the V2V communications.

Although the connectivity models are of great importance to measure the data transmission delay in VANETs, the most existing studies only focus on the highway scenarios [20]. Reference [21] employs discrete-time and discrete-space Markov chains to estimate the changing of vehicle velocities so as to infer whether the network partition would occur. Unfortunately, the computational complexities of the estimation methods refrain them from putting into practice for routing decisions. Considering the significant impact from the traffic signals on the speeds and spacing distribution of the vehicles, [22] derives the connectivity model of a single road segment in urban environments. However, [22] needs traffic flow data of all entrances of the road segments to calculate the connectivity, so it is improper to be directly used for routing decision.

In summary, the frequent disruptions of traffic flow in urban roads seriously affect the connectivity of VANETs. But the existing data delivery protocols still fail to adapt to the time-varying vehicle density resulting from the stochastic vehicle mobility and periodic interference of the traffic signals [23].

3. Connectivity-Aware Data Delivery

We propose deploying RSUs at major intersections to collect data for calculating the vehicle arrival ratios and then exchanging them with the neighboring RSUs periodically through connectivity messages. Next, the RSUs can employ the arrival ratios to estimate the real-time connectivity and exchange the transmitting delay with the adjacent RSUs by connectivity messages. Then, the RSUs can choose a forwarding path for the arriving packets in terms of the minimum delay.

On the other hand, each vehicle and each RSU are equipped with a GPS device and a digital map on which the positions of RSUs are marked.

3.1. Estimating Arrival Ratios of Vehicles

The vehicles are required to broadcast beacon messages periodically, so an RSU can be aware of the approaching vehicles, and then estimate the arrival ratios of different directions of an intersection for every time interval τ. The arrival ratios calculated by an RSU (denoted as $R_i$ ; see Table 1) are sent to the neighboring k-hop RSUs (here, 1-hop RSU is defined as an RSU immediate adjacent to the RSU $R_i$ ) with the assistance of the passing vehicles. If a neighboring RSU (denoted as $R_j$ ) does not receive the reports from $R_i$ within a given interval, then $R_j$ forecasts it based on the historical arrival ratios of $R_i$ recorded in the local storage by applying the regression technique (see the following paragraph). If the delayed arrival ratios of $R_i$ reach later, then $R_j$ replaces the estimated ones with the incoming arrival ratios.

Table 1

The notations used in the delay model.

τ	Time interval for estimating the transmission delay
λ	Arrival ratio during τ
β	The average vehicle density
A	The number of arrival vehicles during $[t-\tau ,t]$
D	The number of vehicles departing in one direction
ω	Time slices of τ
$L_{ij}$	The road length from RSU i to j
$v_{ij}$	The average vehicle velocity of the road $ij$
R	The transmission range of wireless signals
$d_{\mathrm{0}}$	Average one-hop wireless transmission delay
${\rho }_{ij}(t)$	The vehicle density of road $ij$ at time t
$d_{ij}(t)$	The transmission delay of road $ij$ at time t
$E(N_{ij}(t))$	The expected number of vehicles of road $ij$ at time t
$V_s(ij)$	The vehicles that go straight through the intersection i into the road $ij$
$V_t(ij)$	The vehicles that enter road $ij$ from the perpendicular direction during the green phase

Table 2

Notations list of reliability analysis.

S	The sender node
R	The transmission radius
$t_b$	The period of beacon messages
$v_x$	The velocity of the vehicles
$C_0$	The furthest vehicle from S in the direction of packet transmission
L	The distance from S to $C_0$
$B_0$	The region without vehicle marked with red lines
m	The distance from $C_0$ to the horizontal transmission boundary of S
θ	The horizontal angle

In order to predict the missing arrival ratios of vehicles at neighboring intersections that should have been reported, the k-nearest neighbor (kNN) algorithm [24] is used to capture the traffic patterns from a time series of data, given that the traffic flow has periodical patterns [25]. As thus, a historical arrival ratio record turns into a state vector in kNN which contains several attributes depicting the arrival ratios, that is, the time and the date attributes (e.g., hour of the day, the day of the week), and then it is stored locally in RSUs.

The estimation process is activated when the missing of current arrival ratio is detected. To simplify the calculation, the historical records are stored in a KD-tree and the records retrieved from the local storage are restricted to latest four items represented by ${\lambda }_{h1},{\lambda }_{h2},{\lambda }_{h3}$ , and ${\lambda }_{h0}$ . Then, the missing arrival ratio of vehicles at a neighboring intersection can be estimated as $\lambda ={\sum }_{i=\mathrm{0}}^H{\mu }_i{\lambda }_{hi}$ , where $H=4$ and ${\mu }_i={d_i}^{-\mathrm{1}}/{\sum }_{i=\mathrm{0}}^K{d_i}^{-\mathrm{1}}$ . $d_i$ denotes the dissimilarity distance between the subvector from the historical record and the current state and is measured by the Euclidean distance; that is, $d_i=\sqrt{{\sum }_{j=\mathrm{1}}^K{(p_j-q_j)}^{\mathrm{2}}}$ , where K is the dimension of the state vector, $p_j$ is the jth element of the historical record under consideration, and $q_j$ is the jth element of the current state.

3.2. Delay Model

All RSUs are assumed to be standalone, they determine the forwarding paths for the arriving packets with the goal of minimizing the transmission delay. Note that the transmission delay depends heavily on the wireless connectivity of the VANETs on the roads, so the delay model is derived through the real-time estimation of the expected number of vehicles and vehicle distribution between adjacent RSUs.

An RSU works as follows to decide the optimal paths for the arriving packets.

• (1)

The RSU builds a Markov model for vehicle queue length at intersections. At time $t_0$ , the RSU $R_i$ estimates the queue length of the neighboring intersections of time $t_0+\tau$ in the light of the current arrival ratios of neighbor RSUs.

(2)

The RSU estimates the transmission delays in terms of the real-time varying vehicle number and distribution between the adjacent RSUs.

(3)

The RSU calculates a minimum-delay forwarding path to a virtual destination $v_d$ for a packet with an improved Dijkstra algorithm, where $v_d$ refers to the RSU nearest to the original destination of the packet and can exchange arrival ratios with the intended forwarding RSU $R_i$ . All the destinations refer to $v_d$ in the rest of the paper.

In the following, we elaborate the vehicle queue length prediction, delay estimation, and path choosing, respectively.

3.2.1. Vehicle Queue Length Prediction

The arrival of vehicles at an intersection can be viewed as a stochastic process following the Poisson distribution [26, 27]. As a result, the queue length of vehicles at an intersection at time t can be modelled with a random variable $L(t)$ :

$$\begin{array}{cc}& L\left(t\right)=\max \left\{L\left(t-\tau \right)+A-D,\mathrm{0}\right\},\end{array}$$

(1) where τ is a small time interval by which a green phase of traffic signal is divided into n equal episodes and A is a random variable standing for the number of arrival vehicles during [ $t-\tau ,t$ ]. Meantime, D represents the number of vehicles departing from the intersection in one direction; we assume that the departure ratio G is a constant during the green phase. Equation (1) points out that the queue length at time t depends only on the queue length at time $t-\tau$ , the arrival and departed vehicles during τ; therefore, it is a renewal process. So the RSU can predict the queue length at $(k+1)\tau$ with the arrival ratios at time $k\tau$ (k and n are positive integers, $0<k<n$ ) in an iterative manner. Note that τ is also the period of connectivity messages.

The prediction is based on the transition probability $q_{ij}$ , which is the probability that the queue length changes from i to j in a small interval ω ( $\tau =u\times \omega$ , u is a positive integer):

$$\begin{array}{cc}& q_{ij}\left(\omega \right)=\{\begin{array}{cc}{P}_r\left(A\left(\omega \right)=j-i+\omega D\right)\hfill & j>i-\omega D\hfill \\ \mathrm{0}\hfill & \text{otherwise},\hfill \end{array}\mathrm{\hspace{0.17em}\hspace{0.17em}}\end{array}$$

(2) where i, $j>0$ . Consequently, the probability that the queue length changes from i to 0 can be calculated by the following equation:

$$\begin{array}{cc}& q_{i\mathrm{0}}\left(\omega \right)=\{\begin{array}{cc}{\displaystyle \sum }_{k=\mathrm{0}}^{\omega D-i}{P}_r\left(A\left(\omega \right)=k\right)\hfill & \mathrm{\hspace{0.17em}\hspace{0.17em}}i\le \omega D\hfill \\ \mathrm{0}\hfill & \phantom{l}i>\omega D.\hfill \end{array}\mathrm{\hspace{0.17em}\hspace{0.17em}}\end{array}$$

(3)

At any interval ω, the probability of finding i vehicles arriving is written as

$$\begin{array}{cc}& P\left(A=i\right)=e^{-\lambda \tau }\frac{{\left(\lambda \omega \right)}^i}{i!},\end{array}$$

(4) where λ is the arrival ratio during τ.

Note that the probability distribution of a queue length at time $k\tau$   during a green phase can be denoted as $P^{(0)}=[P_0^{(0)},P_1^{(0)},P_2^{(0)},\dots ,P_m^{(0)}]$ (where $P_l^{(\mathrm{0})}$ denotes the probability that the queue length equals l and $P^{(0)}$ is randomly initialized) [26]; then probability distribution at $k\tau +\omega$   can be estimated by $P^{(1)}=P^{(0)}{q}_{ij}$ (ω). Then after u iterations, the probability distribution about the queue length is

$$\begin{array}{cc}& P^{\left(u\right)}=P^{\left(u-\mathrm{1}\right)}{q}_{ij}\left(\omega \right).\end{array}$$

(5)

With the queue length at time $k\tau$ , the expected queue length at time $(k+1)\tau$   is calculated with

$$\begin{array}{cc}& E\left(L\left(\left(k+\mathrm{1}\right)\tau \right)\right)={\displaystyle \sum }_{j=\mathrm{0}}^{m}j{P}^{\left(u\right)},\end{array}$$

(6) where m is the dimension of the transition probability matrix. During the red phase of traffic signal, (6) is still valid as long as the parameter D in (2) is set to 0.

3.2.2. Delay Estimation

With the prediction of the changes of the queue length, we then estimate the transmission delay of a specific road segment. To simplify the derivation, we suppose that all roads are of two lanes and the traffic signals are synchronized.

The beginning time of the green phase of the traffic signal is denoted as time 0. So the shortest time to form the wireless links from RSU i to j is $M{T}_{ij}=(L_{ij}-R)/(2\times v_{ij})$   after the green phase has started; it is reasonable that we suppose that the spacing of vehicles on the road $ij$ follows the Poisson distribution [26] after $M{T}_{ij}$ . Then, the one-hop connectivity probability between vehicles at time t can be specified as

$$\begin{array}{cc}& p_r\left(x<R\right)=\mathrm{1}-e^{-{\rho }_{ij}\left(t\right)R},\end{array}$$

(7) where x represents the spacing between vehicles and ${\rho }_{ij}(t)$ is the vehicle density. Notice that $t\ge M{T}_{ij}$ and $t=m\tau$ ; that is, the estimation of transmission delay is only executed at an integral multiple of time interval τ.

Since $V_s(ij)$ during the interval τ can be estimated by

$$\begin{array}{cc}& V_s^{\tau }\left(ij\right)=\alpha \max \left\{E\left(N_i\left(\tau \right)\right)+E\left(L_i\left(t-\tau \right)\right),\tau D\right\},\end{array}$$

(8) where $E(N_i(\tau ))$ denotes the number of the vehicles arriving intersection i during τ and α  is the ratio of the vehicles going straight through intersection i into the road $ij$ , apparently, the number of vehicles on the road $ij$ at time t can be given by

$$\begin{array}{cc}& E\left(N_{ij}\left(t\right)\right)=E\left(N_{ij}\left(t-\tau \right)\right)+V_s^{\tau }\left(ij\right)-E\left(A_j\left(\tau \right)\right).\end{array}$$

(9)

Equation (9) implies that the number of vehicles of road $ij$ at time t depends only on the number of vehicles at time $t-\tau$ , the number of vehicles going straight through the intersection, i toward intersection j and the number of arriving vehicles at intersection j. Note that $E(A_j(\tau ))$ needs to be calculated only after $t>L_{ij}/v_{ij}$   in that no vehicle in   $V_s(ij)$ could arrive at intersection j before $L_{ij}$ / $v_{ij}$ .

Thus, the vehicle density during the green phase is given by

$$\begin{array}{cc}& {\rho }_{ij}\left(t\right)=\frac{\left(E\left(N_{ij}\left(t\right)\right)+E\left(N_{ji}\left(t\right)\right)\right)}{L_{ij}}.\end{array}$$

(10)

During the red phase of the traffic signal, since the wireless links may still be connected before time elapsed $M{T}_{ij}$ . Considering that some vehicles (denoted by $E(T_i(t))$ ) on the road $ij$ are entered from the perpendicular direction during green phase, $E(T_i(t))$ is proportional to the vehicles passed in the perpendicular direction of the intersection (the ratio is $1-\alpha$ ). So the number of vehicles on the road $ij$ can be estimated as

$$\begin{array}{cc}& E\left(N_{ij}\left(t\right)\right)=E\left(N_{ij}\left(\mathrm{0}\right)\right)-E\left(A_j\left(t\right)\right)+E\left(T_i\left(t\right)\right).\end{array}$$

(11)

From (11) we can observe that the expected number of vehicles on the road $ij$ at time t equals the number of vehicles at the beginning of the red phase subtracting the number of vehicles arriving at intersection j after the beginning of the red phase and adding the vehicles entering the road from the perpendicular direction. Specially, the wireless link of $V_s(ij)$ could be possible only after $M{T}_{ij}$ passes in the green phase; meanwhile, $V_t(ij)$ contributes to the connectivity of the road at a red phase. Therefore, the vehicles on the road $ij$ can be regarded as the $V_s(ij)$ superimposed with $V_t(ij)$ . Thus, the transmission delay of road $ij$ at time t of a green phase can be written as follows:

$$\begin{array}{cc}& d_{ij}\left(t\right)=\{\begin{array}{cc}{\sigma }_{ij}\left(t\right)+D_{ij}^{\left(\mathrm{1}\right)}\left(t\right)\hfill & t\le M{T}_{ij}\hfill \\ D_{ij}\left(t\right)\hfill & t>M{T}_{ij}.\hfill \end{array}\end{array}$$

(12)

Equation (12) indicates that before a wireless link is formed, the packets are carried or transmitted by $V_s(ij)$ and entered during the green phase together with the vehicles turned into the road $ij$ during last red phase. ${\sigma }_{ij}(t)$ is the resulting delay of $V_t(ij)$ , the vehicle density of $V_t(ij)$ is estimated by the numbers of vehicles passing in the perpendicular direction during the green phase of intersection i and j, that is,   ${\rho }_{ij}^{(2)}(t)=(E(T_i(t))+E(T_j(t)))/(L_{ij}-2v_{ij}t)$ , so

$$\begin{array}{cc}& {\sigma }_{ij}\left(t\right)=\left(\mathrm{1}-e^{-R{\rho }_{ij}^{\left(\mathrm{2}\right)}\left(t\right)}\right)\frac{L_{ij}-\mathrm{2}{v}_{ij}t}{R}{d}_{\mathrm{0}}+e^{-R{\rho }_{ij}^{\left(\mathrm{2}\right)}\left(t\right)}\frac{L_{ij}-\mathrm{2}{v}_{ij}t}{v_{ij}},\end{array}$$

(13) where $e^{-R{\rho }_{ij}^{(\mathrm{2})}(t)}$ is the probability that the spacing of vehicles is larger than R. If so, the packets have to be carried by the vehicles. As suggested in (13), the transmission delay relies on the vehicle density heavily; a high vehicle density makes for a small portion of data packets completed by the vehicle movements; $D_{ij}^{(1)}(t)$ is the delay caused by the $V_s(ij)$ :

$$\begin{array}{cc}& D_{ij}^{\left(\mathrm{1}\right)}\left(t\right)=\left(\mathrm{1}-e^{-R{\rho }_{ij}^{\left(\mathrm{1}\right)}\left(t\right)}\right)\frac{\mathrm{2}{v}_{ij}t}{R}{d}_{\mathrm{0}}+\mathrm{2}{e}^{-R{\rho }_{ij}^{\left(\mathrm{1}\right)}\left(t\right)}t.\end{array}$$

(14)

Similar to (10), the vehicle density of $V_s(ij)$ is ${\rho }_{ij}^{(\mathrm{1})}(t)=(E(N_{ij}(t))+E(N_{ji}(t)))/(2v_{ij}t)$ , when the spacing of vehicles satisfies the exponential distribution after time elapsed $M{T}_{ij}$ ; the data delivery is performed mainly by $V_s(ij)$ and the transmission delay is given by

$$\begin{array}{cc}& D_{ij}\left(t\right)=\left(\mathrm{1}-e^{-R{\rho }_{ij}\left(t\right)}\right)\frac{L_{ij}}{R}{d}_{\mathrm{0}}+e^{-R{\rho }_{ij}\left(t\right)}\frac{L_{ij}}{v_{ij}}.\end{array}$$

(15)

$D_{ij}(t)$ indicates that the total delay is composed of the delay caused by vehicles carrying on with proportion of $e^{-R{\rho }_{ij}(t)}$ and the delay incurred by wireless transmission when the intervehicles distances are smaller than R. It must be emphasized that on the calculation of the expected transmitting delay between adjacent RSUs, the impacts of the traffic signal cycle and the reasonable conditions of the exponential spacing distribution to be fulfilled are considered.

3.3. Path Choosing

When the RSU at an intersection i receives a packet with $v_d$ as its destination, it calculates the minimum delay from intersection i to $v_d$ through an improved Dijkstra algorithm. Considering that the traffic flow is uneven, we need to scale up the weight of delay $d_{k,k+1}$ on the roads nearer to the intersection i so as to avoid being deceived by the short latencies of the roads far away from the intersection i. Therefore, on the basis of the original Dijkstra algorithm, we introduce (16) to calculate the minimum forwarding delay $D_{i,vd}$ , of which ${\beta }_{k,k+1}\in (\mathrm{0,1})$ is the weight of delay $d_{k,k+1}$ and l is the searching depth from i to $v_d$ in the algorithm

$$\begin{array}{cc}& D_{i,vd}={\displaystyle \sum }_{k=\mathrm{0}}^{k=l}{\left({\beta }_{k,k+\mathrm{1}}\right)}^k{d}_{k,k+\mathrm{1}}.\end{array}$$

(16)

The parameter ${\beta }_{k,k+1}$ depends on the average vehicle density on the road $(k,k+1)$ . The higher the vehicle density is, the greater the value of ${\beta }_{k,k+1}$ is assigned. On that account, ${\beta }_{k,k+1}$ is decided by (17), in which the offset θ represents the least number of vehicles in the transmission range R to form a successive wireless connection [18]; θ is set to 6 in experiments:

$$\begin{array}{cc}& {\beta }_{k,k+\mathrm{1}}=\frac{\mathrm{1}}{\mathrm{1}+e^{-({\rho }_{k,k+\mathrm{1}}R-\theta )}}.\end{array}$$

(17)

4. Reliable Data Delivery

The propagation of wireless signals in urban environments is interfered by the buildings, facilities along the roads, and the rapid vehicle movements in different directions, which may give rise to the loss of data transmitted Therefore, improving reliability is an imperative requirement for the data delivery. Due to the broadcast nature of the wireless medium in VANETs, a single packet often evokes multiple receptions. Thus, it is crucial in determining the appropriate neighboring vehicles to rebroadcast the data in a distributed way with the promise of guaranteeing the reliability.

4.1. Improved Greedy Broadcast Algorithm

Dubhe provides an improved greedy broadcast algorithm to choose the proper relay vehicles. In detail, the sending vehicle broadcasts a packet which contains the payload to be sent, the packet ID, the list of 1-hop neighboring IDs acquired by beacon messages, the location of the last RSU passed by, and the distance from the sending vehicle to the passed RSU. If the vehicle finds that there is no neighbor in the direction of next RSU within the transmission range, it carries the packet. However, on receiving a packet, the vehicle applies the coverage elimination rule; that is, it checks whether all its neighbors are covered by the neighbor list of the packet or not, if covered, then the recipient discards the packet, otherwise it becomes a forwarding candidate. Such a coverage elimination rule can effectively reduce the candidate number.

Being a candidate implies that the vehicle needs to start a timer according to the distance from the sending node in preparation for the packet rebroadcasting. The longer the distance is, the shorter the timer is set. In this way, the vehicle furthest away from the sender has the highest priority to rebroadcast the packet. On condition that the furthest one fails, the secondary vehicles can rebroadcast the packet after a little while. Therefore, a multicandidate situation is formed.

In Dubhe, the packet may be rebroadcast by the vehicles moving in the opposite direction, which can improve the connectivity and increase the efficiency of packet forwarding. But in order to prevent the packet from being propagated in the inverse direction, the vehicle updates the distance from the last passed RSU in the packet before it rebroadcasts the packet. The improved greedy broadcast algorithm deployed on vehicles is shown in Algorithm 1.

Algorithm 1: An improved greedy broadcast algorithm with coverage elimination.

$(1$ )  //Definition: u denotes a vehicle in a VANET, $N(u)$

    denotes a neighbor list of u;

(2)  //O denotes the last intersection passed by; dist

    (O,  u) denotes the length from O to u;

(3)  //R denotes wireless transmission radius;

(4)  //M denotes the data packet which needs to be

    delivered, and consists of ID, data, sender node s, a

    neighbor list of s   $N(s)$ , the coordinates of O, and the

    distance between O and s

(5)  On receiving a data packet M at node u

(6)     Extract dist(O,  s), coordinates of O and $N(s)$

    from M;

(7)     If  M has been received before or $u\notin N(s)$ then

(8)     Drop data packet M;

(9)     If exists any defer timer on M then

(10)     Cancel all the timers;

(11)      return;

(12)   If $\mathrm{dist}(O,\hspace{0.17em}\hspace{0.17em}u)\le \mathrm{dist}(O,\hspace{0.17em}\hspace{0.17em}s)$ then

(13)     Drop data packet M;

(14)   If $N(u)\subseteq N(s)$ then

(15)     Drop data packet M;

(16)   Set defer timer $d_1$ time to T;

(17)   On expiration of deferred timer $d_1$

(18)     Broadcast data packet M;

(19)   Set t equals to $(R-(\mathrm{dist}(O,\hspace{0.17em}\hspace{0.17em}u)\mathrm{mod}R))*T/R$ ;

(20)   Set defer timer $d_2$ with t;

(21)   On expiration of deferred timer $d_2$

(22)     Update M: replace $N(s)$ with $N(u)$ ,dist(O,  s)

     with dist(O,  u)

(23)     Broadcast data packet M

It is clear that the maximum waiting time T is a critical parameter to Algorithm 1, which closely relies on the one-hop wireless transmitting time, vehicle density, and wireless communication range and queue length of the packet in the MAC layer. The similar deferring policy is utilized in [3], which advises to set no less than 5 ms when the vehicle density is 100 vehicles/km/lane. Taking all factors into consideration, T is set to 20 ms in our experiments. Additionally, in order to avoid the expanding of the neighbor list in the packet when the vehicle density is high, the probabilistic data structure (e.g., bloom filter) can be used. Meanwhile, the interval of beacon messages can be dynamically adjusted according to the vehicle density to reduce the communication overheads [11].

4.2. Algorithm Analysis

Algorithm 1 attempts to choose the furthest vehicle to forward the packets and meanwhile lets multiple neighboring vehicles be the alternatives in case of the failure of the furthest node. Such a design aims to provide the robust packet transmission.

The following subsections will check the reliability of our algorithm by theoretically analyzing the effects of rapid moving of vehicles on the reliability of one-hop packet transmission and discussing the treatment of the failures of RSUs.

4.2.1. Reliability of One-Hop Data Transmission

As we know, the vehicles at the edge of the transmission range of the message sender may get away in a very short time due to the fast movement of the vehicles. When the above situation occurs in Dubhe, the furthest one-hop neighboring vehicle of the sender may not receive the message because the neighboring vehicle is no longer within the transmission range of the sender when the sender broadcasts the message. This subsection examines the possibility of such situation caused by the rapid vehicle mobility, given the ideal wireless signal model (i.e., the unit disk model).

Figure 1 illustrates the distribution of vehicles on a 4-lane road; the packets are propagated from right to left by vehicle S. Note that whether the rebroadcasting vehicles could run away from the sender or not is decided by the location of the candidates when they send beacon to S, the relative velocity between the sender and receivers, and packet sending time elapsed from the time of receiving beacons.

Figure 1

Vehicle distribution on the road.

Supposing that the vehicle $C_0$ reports its position by a beacon message at time 0 and the time that S sends a packet is $T_0$ , therefore, the condition that vehicle $C_0$ can run away from S at $T_0$ is defined as

$$\begin{array}{cc}& {{\displaystyle \int }}_0^{T_0}\left(v_{c_0}+v_s\right)t\hspace{0.17em}dt>m.\end{array}$$

(18)

Since the relative velocity between the vehicles in the opposite directions is more likely to be greater than that of the same direction and such situation has more chances to flee from each other, so we focus on the case of the opposite directions.

To begin with, we specify the probability that a candidate vehicle $C_i$ can escape from S at time instant t:

$$\begin{array}{cc}& p_i\left(t,v,l\right)={{\displaystyle \int }}_{\mathrm{0}}^{R}f\left(l\right){{\displaystyle \int }}_{\mathrm{0}}^{t_b}f\left(t\right){{\displaystyle \int }}_{\mathrm{0}}^{\mathrm{2}{v}_{\max }}{f}_r\left(v\right)vtdl\hspace{0.17em}dt\hspace{0.17em}dv,\end{array}$$

(19) where $f_r(v)$ is the probability density function (pdf) of the relative velocity, $f(l)$ is the pdf of the distance between the candidates and S and $f(t)$ is the pdf of packet transmission time of S.

$(1)$   Pdf of the relative velocity is as follows. We combine the fluid model with the stochastic model to characterize the average vehicle density and the random behavior of individual vehicle [22]. In light of the Greenshield model in traffic flow theory, as for a node at location l at time t, the relationship between the velocity $v(l,t)$ of the node and the vehicle density is depicted as

$$\begin{array}{cc}& v\left(l,t\right)=v_f\left(\mathrm{1}-\frac{n\left(l,t\right)}{k_j}\right),\end{array}$$

(20) where $v_f$ denotes the vehicle velocity of free flow, $k_j$ represents the jamming vehicle density and $k_j=1/l_c$ , in which $l_c$ is the vehicle length, and $n(l,t)$ is the vehicle density of location l at time t. Taking the random behavior of vehicles into account, the vehicle velocity can be redefined as $f(v)=v(l,t)+\mu$ , in which μ is a random variable following normal distribution $N(0,{\sigma }^2)$ . Since the maximum relative velocity of the moving vehicles in the opposite directions is $2v_{\max }$ and the additive of two hormal distributions follows $N(\mathrm{0,2}{\sigma }^2)$ , hence, $f_r(v)$ is

$$\begin{array}{l}{f}_r\left(v\right)=f\left(v_c\right)+f\left(v_s\right)\\ \phantom{f_r\left(v\right)}=v_c\left(l,t\right)+v_s\left(l,t\right)+\frac{\mathrm{1}}{\sqrt{\mathrm{4}\pi {\sigma }^{\mathrm{2}}}}\exp \left(-\frac{v^{\mathrm{2}}}{\mathrm{4}{\sigma }^{\mathrm{2}}}\right).\end{array}$$

(21)

(2) Pdf of vehicle distances is as follows. The exponential distribution is turned out to be appropriate for describing the distances between the vehicles travelling along a 1-lane road; therefore, the number of vehicles in the 1-lane road can be estimated by a Poisson distribution. However, vehicles in Figure 1 are located in an approximate rectangle region formed by the 4-lane road intersecting with the wireless coverage area of S. In view of this, we consider that the vehicles may be located randomly in the rectangle region which is  modelled by a 2-dimension Poisson distribution. To simplify the analysis, we turn to the distance distribution of the furthest vehicles $C_0$ and S in that $C_0$ has maximum opportunity to escape from S. So the cumulative distribution function (cdf) of distance distribution between $C_0$ and S can be specified in the form

$$\begin{array}{cc}& F_{c_{\mathrm{0}}}\left(L\right)={{\displaystyle \int }}_{\mathrm{0}}^{\pi /\mathrm{2}}P\left\{N\left(B_{\mathrm{0}}\right)=\mathrm{0}\hspace{0.17em}|\hspace{0.17em}\mathrm{\Theta }=\theta \right\}{f}_{\mathrm{\Theta }}\left(\theta \right)d\theta ,\end{array}$$

(22) where $B_0$ is the region without a vehicle, as marked with red dotted lines in Figure 1. The angle  θ  is uniformly distributed in $[0,\pi /2]$ ; that is, $f_{\mathrm{\Theta }}(\theta )=2/\pi$ . Generally, the conditional probability that i vehicles locate in region $B_0$ conditioned on a specific angle  θ  is

$$\begin{array}{cc}& P\left(N\left(B_0\right)=i\hspace{0.17em}|\hspace{0.17em}\mathrm{\Theta }=\theta \right)=\frac{{\left(\lambda B_{\mathrm{0}}\right)}^i}{i!}{e}^{-\lambda B_{\mathrm{0}}}.\end{array}$$

(23)

Particularly, the area of $B_0$ can be calculated approximately with

$$\begin{array}{cc}& B_{\mathrm{0}}\approx w\left(R-L\cos \theta \right),\end{array}$$

(24) where w is the width of the road; hence (22) is rewritten as

$$\begin{array}{cc}& F_{c_{\mathrm{0}}}\left(l\right)=\frac{\mathrm{2}}{\pi }{{\displaystyle \int }}_{\mathrm{0}}^{\pi /\mathrm{2}}{e}^{-\lambda w\left(R-L\cos \theta \right)}d\theta .\end{array}$$

(25)

By differentiating (25), we obtain the pdf of distance between $C_0$ and S:

$$\begin{array}{cc}& f_{c_{\mathrm{0}}}\left(l\right)=\frac{d}{F}{F}_{c_{\mathrm{0}}}\left(l\right)=-\frac{\mathrm{2}\lambda }{\pi }{{\displaystyle \int }}_{\mathrm{0}}^{\frac{\pi }{\mathrm{2}}}{e}^{-\lambda B_{\mathrm{0}}}\frac{\partial B_{\mathrm{0}}}{\partial l}d\theta .\end{array}$$

(26)

(3) It is a reasonable assumption that the time S sends packets follows uniform distribution; thus,

$$\begin{array}{cc}& f\left(t\right)=\frac{\mathrm{1}}{t_b}.\end{array}$$

(27)

Substituting (21) and (26)-(27) into (19), then the theoretical probability that the vehicle $C_0$ can escape from S (i.e., packet loss probability $p_i(t,v,l))$ can be calculated easily. Figures 2 and 3 show the results under different conditions. It is observed that the packet loss ratio goes up with an increase in beacon period, which is the direct result of the integral of (27), (19). Moreover, note that increasing the vehicle density also incurs an increase in the packet loss ratio slightly, which is due to the fact that the more vehicles locate in the forwarding area of S, the smaller the area of $B_0$ would be, which results in an increase in the integral of (26).

Figure 2

Packet loss ratio of 10 vehicles.

Figure 3

Packet loss ratio of 40 vehicles.

Next, we derive the success broadcast probability (P _succ) [28] to justify the function of the multi-candidate strategy to meet the challenge of the rapid movements of vehicles. First of all, recall that the vehicle number in the forwarding area of S follows Poisson distribution. Therefore, the probability that there are j potential vehicles that can take part in rebroadcasting the received packet can be given by

$$\begin{array}{cc}& P\left\{N_C=j\right\}=\frac{{\left(\lambda Rw\right)}^j}{j!}{e}^{-\lambda Rw}.\end{array}$$

(28)

Further, assuming that at most M candidates participate in forwarding a packet, the success probability can be found from

$$\begin{array}{l}{p}_{\text{succ}}^{\left(M\right)}={\displaystyle \sum }_{j=\mathrm{0}}^{M-\mathrm{1}}P\left\{N_C=j\right\}\left(\mathrm{1}-{\displaystyle \prod }_{i=\mathrm{0}}^j{p}_i\left(t,v,l\right)\right)\\ \phantom{p_{succ}^{\left(M\right)}=}+P\left\{N_C\ge M\right\}\left(\mathrm{1}-{\displaystyle \prod }_{i=\mathrm{0}}^M{p}_i\left(t,v,l\right)\right).\end{array}$$

(29)

The former part corresponds to the case that the number of potential candidate vehicles is less than M, while the latter part reveals that the number of available forwarding vehicles is more than M. However, only M vehicles are involved in rebroadcasting the packet. By employing the complementary relationship, the probability that there is more than M potential candidate vehicles can be easily given:

$$\begin{array}{cc}& P\left\{N_C\ge M\right\}=\mathrm{1}-{\displaystyle \sum }_{i=\mathrm{0}}^{M-\mathrm{1}}\frac{{\left(\lambda Rw\right)}^i}{i!}{e}^{-\lambda Rw}.\end{array}$$

(30)

Finally, the success broadcast probability can be expressed in two different forms as

$$\begin{array}{cc}& P_{\text{succ}}^{}=\{\begin{array}{cc}P\left\{N_c\ge \mathrm{1}\right\}\left(\mathrm{1}-p_i\left(t,v,l\right)\right)\hfill & M=\mathrm{0}\hfill \\ P\left\{N_c\ge \mathrm{1}\right\}{p}_{\text{succ}}^{\left(M\right)}\hfill & M\ge \mathrm{1},\hfill \end{array}\end{array}$$

(31) where $M=0$   implies that the packet is successfully transmitted without the help of the candidates, while $M\ge 1$ means that multiple candidate vehicles participate in forwarding the packet. Obviously, the probability that at least one vehicle in the forwarding area of S is

$$\begin{array}{cc}& p\left\{N_c\ge \mathrm{1}\right\}=\mathrm{1}-p\left\{N_c=\mathrm{0}\right\}=\mathrm{1}-e^{-\lambda wR}.\end{array}$$

(32)

Combining (28)–(30) and (32) with (31), we can obtain the success transmission probability easily. Given the parameter values in Table 3, the analytical results are shown in Figures 4 and 5. As can be seen, the success transmission probability without the auxiliary vehicle decreases as the vehicle velocity arises. In comparison, the success probability increases significantly while one auxiliary vehicle is involved in the packet relay, which exactly justifies the necessity and effectiveness of our strategy. In particular, with an increase in the vehicle density, the success transmission probability declines slightly for the same reason as the packet loss ratio.

Table 3

Parameter values used in analysis.

Parameter	Value
R	200 m
Road width	40 m
Vehicle length	5 m
T	20 ms
Max velocity	25 m/s
Maximum process time	60 ms

Figure 4

Delivery ratio of 10 vehicles.

Figure 5

Delivery ratio of 40 vehicles.

4.3. Retransmission Ratio

Due to the relative movements of vehicles, the vehicle S may not receive the message broadcasted by $C_0$ (S takes this message as an acknowledgment message) and it will regard that message transmitting fails and then rebroadcast the packet, which leads to the result that S retransmits the packet. However, the theoretical analysis result (Figure 6) shows that retransmission probability is acceptable under different vehicle densities. Apparently, the analysis procedure is similar to that in Section 4.2.1 except the integral upper limit of $f(t)$ in (19) is replaced with Ψ, and Ψ is defined as

$$\begin{array}{cc}& \mathrm{\Psi }=t_s+{\tau }_c+{\delta }_t,\end{array}$$

(33)

$$\begin{array}{cc}& t_s=\left(R-l\cos \theta \right)*\frac{T}{R},\end{array}$$

(34) where $t_s$ denotes the wait time before the packet is rebroadcasted by $C_0$ ,   ${\tau }_c$   represents the maximum process time in $C_0$ and ${\delta }_t$ is the one-hop wireless signal transmission time. Equation (34) comes from line 19 of Algorithm 1; therefore, the retransmission probability can be obtained by rewriting (19) as follows:

$$\begin{array}{l}{p}_{rt}\left(t,v,l\right)\\ \hspace{1em}\hspace{1em}={{\displaystyle \int }}_{\mathrm{0}}^R{f}_{L_i}\left(l\right){{\displaystyle \int }}_{\mathrm{0}}^{{\tau }_c+{\delta }_t}f\left(t\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\times {{\displaystyle \int }}_{\mathrm{0}}^{\mathrm{2}{v}_{\max }}{f}_{v_r}\left(v\right)\frac{v_{r}t}{R-l\cos \theta }dl\hspace{0.17em}dt\hspace{0.17em}dv\\ \hspace{1em}\hspace{1em}\hspace{1em}+{{\displaystyle \int }}_{\mathrm{0}}^R{f}_{L_i}\left(l\right){{\displaystyle \int }}_{\mathrm{0}}^{\mathrm{2}{v}_{\max }}{f}_{v_r}\left(v\right)\frac{v_r{t}_s}{R-l\cos \theta }dl\hspace{0.17em}dv,\end{array}$$

(35) where the former integral indicates that the retransmission probability is mainly result of process time and the wireless signal transmission time given that the other parts of integral are known. The $f(t)$ can be depicted with a random variable with uniform distribution; thus,

$$\begin{array}{cc}& f\left(t\right)=\frac{\mathrm{1}}{{\delta }_t+{\tau }_c}.\end{array}$$

(36)

Figure 6

Theoretical retransmission ratio.

According to (34), the defer time of timer in $C_0$ ( $t_s$ ) is an implicit random variable determined by the distance distribution $f(l)$ .

As can be seen from Figure 6, the retransmission probability caused by vehicle movements is less than 1.2%, so the message overheads incurred are very limited. Meanwhile, our theoretical results are expected to provide upper bound in that the parameter values configured correspond to the relative extreme case.

4.4. Failures of RSUs

The RSUs play important roles in pinpointing the forwarding paths, so it is a necessary capability for Dubhe to tolerate the failures of the RSUs. In Dubhe, the messages of arrival ratios from adjacent RSUs act as the heart beating to maintain the neighboring relationship between RSUs. If the messages of arrival rates of a neighboring RSU have not been received within a specified interval (in units of an exchanging cycle) on condition that there are vehicles coming from the RSU, then the RSU is regarded as failed. When a vehicle finds that the approaching RSU is failed, it tries to forward the packet to the vehicle travelling in the same direction. Otherwise, it selects a random path and tries to forward the packet.

5. Evaluation

We conduct simulation experiments to investigate the data delivery performance and message overheads over three independent factors (i.e., the vehicle density, the traffic signal cycle and the connectivity estimation period). The experimental results show that our mechanism can achieve reliable and low-latency data delivery in comparison with the epidemic-based data dissemination protocol (EBDD) [8] and the static-node-assisted adaptive data delivery protocol (SADV) [12].

5.1. Experimental Setup

The experiments are performed on a 6000 × 4000 m area, where the street layout is derived and normalized from a real map in Google Maps. In the experiments, roads are two-lane and 35 RSUs are deployed at major intersections. Figure 7 shows the road topology, where the black dots indicate the deployed RSUs.

Figure 7

Road topology used in the experiments.

We use NCTUns 6.0 [29] to conduct experiments, and the MAC protocol follows IEEE 802.11b. In order to simulate roadside buildings in urban environments, barrier walls are set along the roadsides. The Intelligent Driver Model (IDM) is chosen for vehicles as their mobility model to reflect the features of vehicle movements in urban scenarios.

In the experiments, the initial positions of all vehicles (100–1035 vehicles) are randomly placed, and vehicles make turns at the intersections with a certain probability (probabilities of going  straight, turning left and turning right are 0.6, 0.2, and 0.2, resp.). The green phase of traffic signal equals the red phase, with 50 s as default. Each simulation lasts for one hour.

Data are generated as follows: 10 percent of vehicles generate a data request with a random destination (SADV and Dubhe use RSUs as destinations while EBDD uses vehicles as destinations) per second. Table 4 outlines the experimental parameters.

Table 4

Experimental parameters.

Parameter	Value
Propagation model	Two-ray ground refection model
Expected transmission radius	200 m
Vehicle velocity	0~72 KM/h
Average length of road segments	1 Km
Number of vehicle	100–1035
Traffic signal period	40–120 s
Connectivity estimation period	5–20 s
Beacon message interval	1 s
TTL (time to live) of a packet	1200 s
Length of beacon messages	76 bytes
Length of data packets	68–418 bytes

5.2. Results and Analyses

We conduct three groups of experiments to evaluate the influence of the traffic densities, the traffic signal cycle and the connectivity estimation period/delay update period on the performance and overheads.

(1) Vehicle Density. The vehicle density is one of the most important factors affecting the connectivity of a VANET. The first group of experiments examines the performance and overheads under different traffic densities. Here, the number of vehicles is employed to represent the vehicle density, which is increased from 100 to 1035 in experiments. As shown in Figure 8, the delivery ratios grow substantially as the number of vehicles increases. Note that EBDD is more sensitive to the vehicle density than Dubhe and SADV. The packet delivery ratio of EBDD reaches its peak at 635 vehicles and then declines as the vehicle density further increases. The behaviors of EBDD are rooted in the fact that it works in a manner of best effort, that is, the packets are exchanged when the vehicles enter the transmission range of each other, which leads to severe channel conflicts under heavy traffic. In contrast, the delivery ratios of SADV and Dubhe show steady improvement as the vehicle density increases. Furthermore, Dubhe shows a significant advantage over SADV in terms of transmission delay and delivery ratio. It is worth mentioning that the packet loss in Dubhe is mainly due to expiration of TTL values of packets.

Figure 8

Data delivery ratio.

Figure 9 indicates that the delay of EBDD is lower than that of SADV and Dubhe when the vehicle density is relatively low (less than 635 vehicles) but grows gradually as the vehicle number continues to increase. Benefiting from exchanging the transmitting delay between adjacent intersections, the transmission delay of SADV and Dubhe cuts down rapidly with the increase of the vehicle density. But the delay of Dubhe is shorter than that of SADV in that Dubhe employs a more accurate delay model than SADV for packet forwarding decisions.

Figure 9

Transmission delay.

Figure 10 shows the experimental results of message overheads. Here, as for a vehicle, its message overhead is defined as the message traffic that is received and sent except payload of data packets. It can be observed that SADV consumes fewer messages than Dubhe and EBDD because no beacon messages are sent in SADV. The message overheads of EBDD increase dramatically as the growth of vehicle number, which results from the exchanging of packet digest lists when the vehicles can communicate with each other, and the lengths of the lists rise sharply as the vehicle density increases. However, the overheads of Dubhe remain relatively stable, and the majority of messages of Dubhe come from the beacon messages. Considering that the beacon is an essential mechanism for safety-related applications, we claim that Dubhe does not increase substantial message overheads in comparison with SADV.

Figure 10

Message overhead.

(2) Traffic Signal Cycle Length. The traffic signals at intersections interrupt the traffic flow and affect the VANET connectivity significantly. Therefore, the second group of experiments investigates the influence of traffic signal cycle length on the performance of data delivery. Figures 11–16 show the results of the delivery ratios, the transmission delay, and the overheads under distinct traffic signal cycle lengths for the scenarios of different vehicle number, (200 vehicles and 1000 vehicles, resp.).

Figure 11

Delivery ratio of 200 vehicles.

Figure 12

Delivery ratio of 1000 vehicles.

Figure 13

Transmission delay of 200 vehicles.

Figure 14

Transmission delay of 1000 vehicles.

Figure 15

Overhead of 200 vehicles.

Figure 16

Overhead of 1000 vehicles.

As shown in Figure 11, the delivery ratio of SADV and Dubhe decreases about 5% and the delay rises about 10% as the length of the traffic signal cycle increases from 40 s to 120 s in the 200-vehicle scenario, while the delivery ratio of EBDD boosts about 10%, which may arise from the fact that in EBDD the long traffic signal cycle provides more chances for vehicles queuing at intersections to infect mutually.

From Figures 12 and 14, in the 1000-vehicle scenario, EBDD is significantly inferior to SADV and Dubhe in terms of the packet delivery ratio and the transmission delay. Meanwhile, the transmission delay of Dubhe is minimum when the traffic signal cycle lasts 80 seconds, which is 8% higher than the delay with 40 seconds as the cycle length. Moreover, the transmission delay of SADV is 20% longer than that of Dubhe as a whole. The reason behind this is that the estimation of transmitting delay in SADV is concerned little about the interference of traffic signals while the delay model of Dubhe distinguishes between the required time for establishing a wireless link during the red phase and the green phase, together with the consideration of the changing vehicle density.

What is worth noting is that short traffic signal cycles correspond to high transmission delay when the vehicle density is high. This phenomenon can be interpreted as the multi-hop wireless link between adjacent intersections cannot be established during the short green phase, which increases the proportion of the transmission time of the packet carried by vehicles.

In addition, the data in Figures 15 and 16 imply that the traffic signal cycles have little impact on the message overheads of SADV and Dubhe. However, the messages consumed by EBDD are more sensitive to the length of the traffic signal cycle especially in the 1000-vehicle scenario where the number of messages rises about 10% at most with the increase of the length of the traffic signal cycle.

(3) Connectivity Estimation Period/Delay Update Period. The RSUs deployed at intersections contribute to store the packets when no suitable vehicles can relay the packets. In Dubhe, an RSU estimates the change of queue lengths of vehicles at intersections with the period τ, here τ; is called a connectivity estimation period. In SADV, the static nodes at adjacent intersections periodically exchange the data transmitting delay on roads, which is utilized to decide the packet forwarding paths. Because connectivity estimation period τ and delay update period η of static nodes have similar function, we design a group of experiments to examine their effects on the data delivery performance.

As shown in Figures 17 and 18, with the increase of τ and η, both delivery ratios decrease slightly, that is, 1% for Dubhe and 2% for SADV. Meanwhile, we find that the parameter τ in Dubhe shows more impact on the transmission delay than on the delivery ratio. That is, from Figures 19 and 20, the transmission delay increases as τ gets longer. In detail, when τ changes from 5 s to 20 s, the transmission delay grows about 5.6% in the 1000-vehicle scenario while being 2% or so in the 200-vehicle scenario. The increased delay is due to the deteriorated accuracy of connectivity estimation.

Figure 17

Delivery ratio of 200 vehicles.

Figure 18

Delivery ratio of 1000 vehicles.

Figure 19

Transmission delay of 200 vehicles.

Figure 20

Transmission delay of 1000 vehicles.

Similar to τ, as η   becomes longer, the transmission delay of SADV goes up about 9% in the 1000-vehicle scenario while being  4% in the low-density case. In comparison with Dubhe, the parameter η has more effect on performance of SADV than τ on Dubhe. The reasons are twofold: on the one hand, the error rates of the actual delay information go up as η   increases. On the other hand, Dubhe can forecast the lost arrival ratios of vehicles at neighboring intersections from historical data while SADV has no such remedy strategy.

No significant changes in the message overheads are observed in the experiments of different traffic densities, as shown in Figures 21 and 22. Since the examined parameters τ and η are only related to the frequency of exchanging the arrival ratios and exchanging the actual delay information, the messages incurred are negligible to the total overheads.

Figure 21

Overhead of 200 vehicles.

Figure 22

Overhead of 1000 vehicles.

6. Conclusions

The efficient and reliable data delivery lays a foundation for many VANET applications. We present Dubhe, which reduces the data transmission delay and improves the data delivery reliability of long-distance data transmission in urban scenarios. In Dubhe, the RSUs deployed at main intersections are exploited to collect the traffic densities and estimate the real-time transmitting delay between the RSUs and then choose a minimum delay path for the packets. Meanwhile, an improved greedy broadcast algorithm is proposed to enhance the reliability of one-hop data transmission; then we theoretically analyze the reliability and the retransmission ratio. The experimental results show that the packet delivery ratio of Dubhe is 10% higher than of SADV and transmitting delay is 5–12% lower than that of SADV. Moreover, in comparison with EBDD, our mechanism exhibits stable performance, low message overheads, and high scalability.