An Efficient Data Dissemination Protocol with Roadside Parked Vehicles' Assistance in Vehicular Networks

Abstract

Data dissemination is a challenging problem in vehicular ad hoc networks (VANETs) due to the characteristics of VANETs such as highly dynamic topology, intermittent connectivity, and the road-constrained mobility. Observed from the fact that on-street parking is a common phenomenon in the city, the parked vehicles at roadside can also contribute their resources to the communications in network. In this paper, an efficient data dissemination protocol (EDP) for VANETS is proposed. Different from the existing works which consider mainly mobile vehicles or some expensive roadside infrastructure, EDP leverages the resources of parked vehicles at roadside to help in forwarding data. EDP groups the parked vehicles at roadside into a cluster, which buffers and relays data from mobile vehicles and manages the duplicates of data. Simulation results based on a real city map show that EDP achieves a higher delivery ratio and lower delivery delay.

1. Introduction

Vehicular ad hoc networks have been envisioned to be promising in road safety and many other commercial applications, such as the intelligent transportation system (ITS), one of the most important applications of VANET, which have been deployed in USA, Europe, and Asia. For example, with the ITS, an emergency warning can help drivers behind a crashed vehicle (or incident) to avoid multicar collisions [1]. Moreover, a vehicular network can be used to alert drivers to potential traffic jams, providing more convenience and efficiency. Vehicular ad hoc networks have some characteristics as follows (1) The topology of VANETs changes rapidly due to the high mobility of the vehicles. Different from the traditional node-to-node pattern of routing which is based on the mobile node topology in mobile ad hoc networks (MANETs), VANETs usually cannot establish a stable end-to-end path to transmit data packets due to the intermittent connectivity. (2) The mobility of vehicles in VANETs is constrained by predefined roads. Due to the buildings and other obstacles, the data delivery based on the vehicle to vehicle (V2V) communications over VANETs is also constrained by the roads.

Efficient data dissemination based on infrastructure-less V2V communications is the most compelling issue for the mentioned applications in VANETs. However, the major communication challenge lies in the intermittent connectivity in VANETs. Consequently, VANETs are regarded as extreme environments or challenged networks that are opportunistically connected.

Connectivity is crucial and significantly affects the underlying routing and the overall performance of applications. Many schemes are proposed to exploit the opportunistic connectivity, including the broadcast techniques and the delay-tolerant ones. Obviously, infrastructures built in VANETs can improve the connectivity and improve the network performance. Recent efforts [2–4] show that proper access points APs deployment techniques could dramatically improve connectivity. A viable alternative is to install some roadside units to relay packets. In [5–7], relay units for packet forwarding and their strategic placement are discussed. However, the wide deployment of infrastructures is very expensive. For example, internet APs need costly installation of power and wired network connectivity. These costs can be as high as 5,000 US dollars per unit [8]. Relay nodes are cheaper, but more units are needed for the same performance. Furthermore, static roadside infrastructure is hardly adaptive to rapid-changing traffic. It seems all but impossible to build a single strategy that represents all aspects of optimal deployment, such as budget limits, street layout, traffic changes, and transmission delay. Generally, the introduction of supporting infrastructures does improve connectivity, but it often requires a large amount of investment and elaborate design, especially at the city scale.

As we all know, vehicles in the city include mobile vehicles and parked ones. However, most of the existing researches just focus on the mobile vehicles and data is delivered among the mobile vehicles or between mobile vehicles and RSUs. In our opinion, the parked vehicles also could be utilized to assist in forwarding data or storing information, especially the on-street parked vehicles. In fact, on-street parking is a common phenomenon in most of the cities in our daily life. With the assistance of roadside parked vehicles, we propose an efficient data dissemination protocol (EDP) in this paper. EDP leverages the resource of the parked vehicles at roadside to help deliver data. EDP organizes the parked vehicles at roadside into a cluster, which buffers and relays data from mobile vehicles. Moreover, the cluster on each road manages the duplicates of data to improve the probability to the destination.

The remainder of the paper is organized as follows. Section 2 makes a brief overview of related works in VANETs. Section 3 presents the background of on-street parking. The design of EDP protocol is given in Section 4 in details. Section 5 gives the simulation results and Section 6 concludes the paper.

2. Related Works

There have been a lot of research works on vehicular ad hoc networks. In this section, we just discuss some related works about the data delivery scheme.

Naumov and Gross [9] present a position-based routing scheme called CAR designed specifically for intervehicle communication in a city and highway environment. CAR integrates locating destinations with finding connected paths between source and destination. Once a path is found, it is autoadjusted on the fly to account for changes, without another discovery process.

Vahdat and Becker in [10] use Epidemic routing. Whenever two nodes meet, they exchange the data that they do not possess. The random pairwise exchanges of messages among mobile hosts ensure eventual message delivery. In [11], Zhao and Cao make use of the predicable vehicle mobility, which is limited by the road traffic pattern and road layout. Based on the existing road traffic pattern, a vehicle can find the next road to forward the packet to reduce the delay. The estimation of packet forwarding delay through each road is based on some statistical data such as the average vehicle density. As the vehicle density on each road may vary with time, which greatly influences the packet forwarding delay, the shortest-delay path calculated based on the statistical data may not reflect the real optimal one.

Song et al. [12] think it is better to construct routing based on the road-to-road pattern than the traditional node-to-node routing pattern in MANETs, due to the road-constrained data delivery and highly dynamic topology of vehicle nodes. However, the challenging issue for the road-to-road routing in VANETs is the opportunistic forwarding at intersections. Therefore, they propose a novel routing scheme, (buffer and switch) BAS. In BAS, each road buffers the data packets with multiple duplicates propagation in order to provide more opportunities for packet switching at intersections. Different from conventional protocols in VANETs, the propagation of duplicates in BAS is bidirectional along the routing path.

Chume and Liu [13] propose a traffic-aware data delivery scheme (TADS) to choose intersections to forward packets dynamically based on link quality and remaining Euclidean distance to destination. A traffic condition prediction model is built to estimate the link quality. TADS also improves geographically greedy routing algorithm for packet forwarding in straightway.

Roadside units are also introduced into VANETs to improve the communication efficiency. Ding et al. [5] introduce that the sensing data from a vehicle may need to be sent to a sink that is deployed miles away, or a vehicle may want to send queries to a remote site such as gas station, restaurant, or parking area. Thus, a multihop routing algorithm is needed in a large vehicular network for these applications. Then authors propose a static node-assisted adaptive data dissemination protocol (SADV) for vehicular networks. They suggest employing mechanisms that enable the packet to wait at an intersection until the best path is available. To achieve this, they add static nodes at intersections that store and forward the packet when appropriate. A few protocols such as TBD [14] and TSF [15] are designed to utilize available vehicle trajectories to improve the data delivery performance. TBD utilizes the vehicle trajectory information along with vehicular traffic statistics in order to compute the accurate expected delivery delay for better forwarding decision-making. However, to disseminate vehicle trajectory information, these protocols assume that numerous wireless access points (APs) need to be deployed along roads. That will undoubtedly request a large amount of investment.

In [16], the idea of (parked vehicle assistance) PVA is first proposed and the network connectivity in PVA is investigated through theoretic analysis and realistic survey and simulations. The results prove that even a small proportion of PVA vehicles could overcome sparse or unbalanced traffic and promote network connectivity greatly.

Utilizing parked vehicles as relay nodes in order to connect two vehicles is presented in [17] by Eckhoff et al. However, the authors just use the parked vehicle located at the corner of the street to connect two vehicles that are located at two sides of an obstacle or a building. And they do not propose any specific relay strategy. In [18], Malandrino et al. present a content downloading system in vehicular networks using parked vehicles. The goal is to share big pieces of data between vehicles and maximize content freshness and utilize the radio resources. But data exchange only involves one-hop communication. Balen et al. also discuss that parked vehicles could assist multi-hop communication in vehicular networks and analyze the energy consumption of the battery of the parked vehicle [19]. They demonstrate that the owner of the vehicle does not need to worry about the depletion of the battery if the car is just parked for 80 hours or less. However, they provide no specific data delivery strategy.

3. Backgrounds of Parked Vehicles

At first, we build our research on a real world urban parking report [20], which provides the parking statistics of two surveys in a central area of Montreal City in Canada. It investigated the 61,000 daily parking events in an area of 5,500 square kilometers. According to the report, street parking, outside parking (mainly off-street parking on the ground), and interior parking (garages or underground parking lots) account for 69.2%, 27.1%, and 3.7% of total, respectively, and the average duration of street parking lasts 6.64 hours. It generates many roadside vehicle nodes easy to communicate and enables them to support long-time communication.

Compared to their moving counterparts, parked vehicles show great advantages in communication. Traffic changes acutely and sometimes makes vehicles very sparse or unbalanced, whereas parked vehicles remain constant in large number all day. Moving vehicles have rapid-changing positions every second, but parked ones stay static for hours. Large ratio of street parking and widespread parking distribution make parked vehicles easy to be exploited in communication, where message delivery often follows road directions. Since parked vehicles are abundant, credible, and convenient node sources, leveraging the resources of the parked vehicles is feasible and has a solid basis in urban areas.

Individual parked vehicle nodes are far from stable roadside units, due to uncertain parking location and duration. But aggregated urban parking behaviors often show a high degree of temporal and spatial regularity. In order to balance supply and demand, city planners often enforce local restrictions and Set up specific locations for parking on every block, such as on-street parking spaces and parking lots.

A survey [21] explores on-street parking in Ann Arbor, the US State of Michigan. The research team selected three sites of on-street parking meters in the city, and continuously monitored their usage during six mid-week days. The selected sites (A/B) represent different downtown shopping areas, and the periods (peak/off-peak/day) point out the survey time (Peak: 12:30–2:30 pm and Off-peak: 8:30–10:30 am). It carried out an all-day observation and some short ones within 2 hours. Although each parking is short and undulated, the utilization of the parking spaces is quite stable. Occupancy ratio, defined as occupied space-hour/available space-hour, averages 93.0% on Site A throughout one day, and nearly 100% around Sites A and B during the peak. Even off-peak occupancy ratio averages almost 80%. For all practical purposes, the on-street parking spaces are used all of the time, for high parking demand.

Similarly, another survey [22] provides the utilization of parking lots in Hattiesburg, the US State of Mississippi. It investigated eight parking lots of the city in November and December, 1996 and in March and April, 1997. The utilization and standard deviation of the parking lots demonstrate that these facilities often have considerable vehicle numbers (above 129 averagely) and small parking fluctuations (less than 13.7%). It proves that the possibility of being completely empty is very slim.

Consequently, we can assume such frequently occupied on-street parking spaces and parking lots have some “fixed” vehicles, as stable roadside units in communication, for the positions and occupancy ratios can be marked and maintained in an electric map.

4. Design of EDP

4.1. Assumptions

We assume that each vehicle knows its location by triangulation or through the GPS service, which is already available in most new cars and will be common in the future. In addition, each vehicle has a digital city map. Vehicles communicate with each other through short range wireless channel. Let R denote the transmission range, and let $r_{ij}$ denote the road from the intersection $I_i$ to $I_j$ ; $l_{ij}$ is the length of $r_{ij}$ . Moreover, let ${\rho }_{ij}$ denote the vehicle density on road $r_{ij}$ , and let $v_{ij}$ denote the average vehicle velocity on road $r_{ij}$ . Moreover, define $R_{\text{INT}}$ as the radius of the intersection area, which is a circle area with the intersection point as the center, as shown in Figure 1. Vehicles should not be parked in the intersection area.

Figure 1

The intersection area.

Data delivery is based on infrastructure-less V2V communications, and the destination for each packet is stationary such as a shop, and a park.

Finally, we assume that some vehicle users will share their devices and contents during parking. Obviously, it can be motivated by some appropriate incentives like in [23]. In fact, even if there are no any incentives, there are still 30% users who are found cooperative and willing to share their resources, according to the running experience of P2P file systems [24]. It proves that at least some users are willing to contribute resources, even if they cannot benefit from the sharing. Moreover, the owner of the vehicle will not worry about the depletion of the power of the battery based on the demonstration discussed in [19]. Define ${\rho }_{\text{PV}}$ as the proportion of parked vehicles which are willing to provide assistance service.

4.2. Overview of EDP

The basic idea of EDP is to utilize the idle resources of on-street parked vehicles to assist in forwarding packet for the vehicular network. Figure 2 shows the overview of EDP. In Figure 2, there are 6 intersections ( $I_i$ , $I_j$ , $I_k$ , $I_l$ , $I_m$ , and $I_n$ ) and several road segments in the map. Blue vehicles are parked at the roadside and green vehicles move along the road. The yellow car wants to send its packet to the destination D. Firstly, EDP organizes the parked vehicles at roadside into clusters (cluster 1~cluster 7 in Figure 2).

Figure 2

The overview of EDP.

Each cluster has one or two cluster heads to manage the cluster and to maintain some routing information such as packet delivery delay of the road segments. To improve the packet delivery ratio, cluster head also manages the replications of the packet. The packets from mobile vehicles are delivered by the intracluster communication and intercluster communication, while mobile vehicles still relay packets if intercluster communication is impossible. The cluster head decides how to deliver the packet within the cluster and between clusters. For example, when yellow car enters into the road $r_{ij}$ , it sends the packet to the head of cluster 1. The head of cluster 1 computes an optimal route for the packet to the destination D (red line in Figure 2) according to the packet delivery delay of other road. Then, the packet is relayed in cluster 1 and delivered to cluster 5. However, cluster 5 and cluster 6 could not connect with each other, and the packet would be sent to the moving vehicle A, which will carry the packet into the road $r_{mn}$ and send it to the head of cluster 6. Finally, the packet is transmitted from cluster 6 to cluster 7 and to the destination.

In the following, we will introduce the clustering of parked vehicles at roadside, which is important to the EDP protocol. Then, other issues such as estimation of packet delivery delay, packet transmission, and replication management are also presented in detail.

4.3. Clustering of Roadside Parked Vehicles

As mentioned before, the survey [21] shows that the occupancy ratio averages 93.0% throughout one day. Even the occupancy ratio during off-peak time reaches almost 80%. Due to the high stability and utilization of roadside parking, clustering parked vehicles on roadside is feasible in the city. We try to organize all parked vehicles ( $\text{PV}$ ) on one road into a virtual cluster, even if some of them can not communicate with each other directly. This is viable, for the moving vehicles ( $\text{MV}$ ) will travel across the road and help to maintain the whole virtual cluster. For the support of data dissemination, the virtual cluster needs to handle the following three tasks: (a) cluster management, including cluster head election and membership management; (b) data delivery on the local road and the adjacent roads; and (c) estimation of packet delivery delay of the road. Cluster must calculate the packet delivery delay of the local road and spread the packet delivery delay to other clusters.

The election of cluster head ( $\text{CH}$ ) is simple. The parked vehicle closest to the intersection could be the cluster head. As in Figure 3, there are 3 scenarios of parked vehicles clustering. If $l_{ij}$ is less than the communication radius of the vehicles, R, just one cluster head is needed to manage the cluster, as shown in Figure 3(a). In Figure 3(b), if $l_{ij}$ is greater than R, but it is less than $2R$ , there may be two cluster heads (i.e., ${\text{CH}}_i$ and ${\text{CH}}_j$ ) at the two ends of road $r_{ij}$ , so that moving vehicles could get the information of the virtual cluster as soon as possible once they enter into the road from $I_i$ or $I_j$ . When $l_{ij}$ is greater than $2R$ , there might be some isolated parked vehicle ( $\text{IPV}$ ) that can't communicate any cluster members directly. As in Figure 3(c), the moving vehicle ${\text{MV}}_1$ would help the $\text{IPV}$ communicated with the ${\text{CH}}_i$ or ${\text{CH}}_j$ and maintain the virtual cluster.

Figure 3

Different scenarios of clustering.

We use the finite state machine, as shown in Figure 4, to describe the principle and operating process of our proposed clustering scheme. Each vehicle operates under one and only one of 4 states at any given time, under the control of seven statetransition conditions.

Figure 4

The state transition of vehicles.

To explain the state transition more clearly, we take the yellow car as an example shown in Figure 5. Once the yellow vehicle parked, it sends QUERY message to its neighbors and transits from $\text{MV}$ to $\text{IPV}$ state (Figure 5(a)). If it receives ECHO message or it receives BEACON message while parking, then it becomes a cluster member and send a JOIN message to the cluster head (Figure 5(b)). If it receives no any ECHO message or BEACON message after it enters the local road, it will be the cluster head near the intersection $I_i$ (Figure 5(b)). As a cluster head, it will periodically broadcast BEACON message to its members and moving vehicles driving through the local road.

Figure 5

Illustration of state transition.

As in Figure 5(d), the cluster head (the green car) drives away it will send LEAVE message and the cluster member who is closest to it (the yellow car) would be the new cluster head. The yellow car will send BEACON message to notify its members and its state will change from $\text{PV}$ to $\text{CH}$ . In Figure 5(e), the blue car will be parked at the location closer to the intersection than the current cluster head (the yellow car) then it claims to be the new cluster head and the yellow car becomes a cluster member. If a cluster member does not receive any BEACON or other information about the cluster head, it will be the isolated parked vehicle (the yellow car as in Figure 5(f)) and vehicles moving across the road will help it communicate with the cluster.

4.4. Estimation of Packet Delivery Delay

For the routing path determination, some studies [11] have shown that after a period of time, some states of a road, such as the average vehicle speed or traffic density, will also be stabilized. The studies have proposed various packet delivery delay estimation schemes for the roads in VANETs, which is based on the traffic density information obtained from the preloaded statistics or P2P protocol for discovering and distributing density information. Therefore, the vehicles can find a better routing path based on these schemes. For effectively evaluating the packet delivery delay along each road, we employ a real-time delay estimation scheme in our previous work [12]. In this scheme, the cluster head calculates the real-time packet delivery delay of each road and then propagates it to their neighboring cluster in order to make all parking cluster in VANETs obtain the real-time information and estimate the packet delivery delay of each road.

When a vehicle storing a packet moves into the road $r_{ij}$ , it will record the current time as $t_i$ in a field of the packet, as in Figure 6. When the packet is transmitted out of the road $r_{ij}$ successfully (Figure 6(a)) or the vehicles storing the packet moves cross the intersection $I_j$ (Figure 6(b)), it will record the current time as $t_j$ . Therefore, the real-time delay of the packet delivery in road $r_{ij}$ is as follows:

$$\begin{array}{cc}& d_{ij}\mathrm{\hspace{0.17em}\hspace{0.17em}}=\mathrm{\hspace{0.17em}\hspace{0.17em}}{t}_j-t_i.\end{array}$$

(1)

Figure 6

Obtain real-time delay record.

Keeping a timestamp (denoted by $t_s$ ) of the packet when the delivery delay of a road is computed can be used to maintain freshness. When a node updates the delay of a road, it keeps a timestamp along with the delay. The vehicle stores the delay time as the delay record of this road, and let $t_j$ be the timestamp of this record in the following form:

$$\begin{array}{cc}& 〈r_{ij},d_{ij},t_j〉.\end{array}$$

(2)

When a packet is sent out of the road $r_{ij}$ or the vehicles carrying the packet moves across the exit intersection $I_j$ , it broadcasts its record of real-time delivery delay. The record should be spread over the whole networks. Mobile node can carry the record and distribute it to other vehicles in epidemic way. However, there would be more redundancy of the record. To be more efficiently, the record of real-time delivery delay of the road could be spread over the network by intercluster communication. The record is only delivered by the cluster in each road unless there is no any cluster in one road. When a cluster head received n delay records from other clusters, it will refresh the mean delivery delay of the road. Let $D_{ij}^n$ denote the mean packet delivery delay, and then it can be calculated by:

$$\begin{array}{cc}& D_{ij}^n=\frac{D_{ij}^{n-1}·t_j^{n-\mathrm{1}}+d_{ij}^{}·t_j^{}}{t_j^{n-\mathrm{1}}+t_j^{}},\\ t_{ij}^n=t_j^{n-\mathrm{1}}+t_j^{}.\end{array}$$

(3)

Each cluster head maintains the mean delivery delay of each road. Then, a weighted graph $G(V,E)$ could be built, where V is the set of intersections and E is the set of roads. The mean delivery delay $D_{ij}$ is the weight on E. Then, a vehicle can compute an optimal route according to the weighted graph.

4.5. Data Dissemination

In a road topology, the data forwarding in the road delivery is much simpler than the intersection delivery, since the traffic is at most bidirectional. Due to the road-constrained data delivery in VANETs, data dissemination of EDP includes three modes, which are the entrance mode, straightway mode, and exit mode.

4.5.1. Entrance Mode

When a packet is delivered into a new road segment, it will operate into entrance mode. The packet sent to the road segment came from two sources. One is the mobile vehicle moving into the road segment, while carrying the packet or generating a new packet (Figure 7(a)). The other is the cluster head in other road which delivers the packet to the cluster head of local road segment directly, as in Figure 7(b). In the header of packet, there is an ID flag that is used to identify whether the packet is a new packet or a duplicate of a packet. When mobile vehicle generates a new packet, the ID flag of the packet is set to 1 and the packet is sent to the cluster head of local road, that is, CH ₁ in Figure 7(a). CH ₁ calculates the number of duplicates of the packet, n, which is inserted to a TTL field of the packet. Intuitively, more copies of the packet can increase the probability of forwarding them to the destination. Only the first cluster that received the new packet will manage the duplicates of the packet. When the packet is sent to other mobile vehicles or cluster heads in other road, the TTL of the packet decreases by 1 and the ID flag is set to 0, which denotes that the packet is a duplicate. However, when the packet is relayed by the cluster members, the TTL remains unchanged. Once the TTL is equal 0, the cluster drops the packet.

Figure 7

Data delivered to road $r_{ij}$ .

If the cluster head of local road receives a packet whose ID flag is equal 0, it only delivers the packet without managing of duplicates of the packet. Unfortunately, if there is no cluster in the local road, the mobile vehicle generated the packet will carry the packet and do the same things as the cluster head.

4.5.2. Straightway Mode

In straightway mode, the packet is delivered in the road. If there are no parked vehicles at roadside, the packet will be carried by the vehicle till the vehicle moves into the area of the exit intersection. Otherwise, the vehicle will send the packet to the cluster head it encountered first. The cluster head knows the location of parked vehicles via the JOIN message sent by the cluster members. If the road is covered by a sequence of connected PV, the packet will be delivered by the cluster members, as shown in Figure 8(a). However, if there are disconnected parts in the virtual cluster, mobile vehicles will help to deliver the packet and connect the separated parts of the virtual cluster (Figure 8(b)). As described before, if the packet is sent to mobile vehicle, the TTL value of the packet will decrease by 1.

Figure 8

Data delivery in the road.

4.5.3. Exit Mode

When data packet is transmitted to the area of intersection, it enters into exit mode. Obviously, if there is no cluster in the local road or the cluster head can't communicate with the vehicle in the intersection area, the packet would be carried by the mobile vehicle which will enter into other road for dissemination. If the packet is relayed by the cluster members, the cluster head of the local road near the intersection would decide how to forward the data packet to the expected routing path (the red line in Figure 9). The cluster head of local road should deliver the packet to the mobile vehicle that is going through the intersection and moving forward to the expected routing path in priority, as in Figure 9(a). If there are no moving vehicles within the field of intersection, the cluster head knows whether there are clusters on other road via BEACON message and the cluster head of local road sends the packet to the cluster heads of other road adjacent to the intersection. As in Figure 9(b), cluster head CH ₁ sends packet to the CH ₂ and CH ₃ , and the TTL value of the packet decrease by 1, respectively. And then, CH ₂ and CH ₃ deliver the packet to mobile vehicles (MV ₂ and MV ₃ , resp.) that will drive through the expected routing path of the packet.

Figure 9

Data delivery at intersection.

4.6. The Number of Duplicates

Compared with routing protocols without duplicates, the protocols with duplicates (such as epidemic routing [10]) can increase the probability of meeting vehicles moving into expected next road at intersections. Authors in [11] assume that the vehicle arrivals at the intersections follow the Poisson distribution, and the probability of meeting k vehicles at the intersection $I_i$ towards the expected next road $r_{ij}$ is

$$\begin{array}{cc}& P\left(x_m=k\right)=e^{-{\lambda }_{ij}{T}_{ij}}\frac{{\left({\lambda }_{ij}{T}_{ij}\right)}^k}{k!},\end{array}$$

(4)

where $x_m$ is the number of meeting other vehicles towards the expected next road $r_{ij}$ , at the intersection $I_i$ for the vehicle m driving through the intersection. ${\lambda }_{ij}$ denotes the average rate of contacts leaving $I_i$ and moving toward road $r_{ij}$ , which can be computed as

$$\begin{array}{cc}& {\lambda }_{ij}={\rho }_{ij}·v_{ij}.\end{array}$$

(5)

And $T_{ij}$ denotes the contacting time for packet carriers which enter intersection $I_i$ and move toward neighbor intersection $I_j$ . The contacting time at a signalized intersection $I_i$ , which is denoted as ${\tau }_i$ , is only related to the length of the signal interval at $I_i$ . In an isolated intersection, vehicles in all directions can smoothly go through without being stopped. For a vehicle at $I_i$ , authors in [11] assume that the average vehicle speed in going through the intersection is the same as the average vehicle speed at the outgoing road. Therefore,

$$\begin{array}{cc}& T_{ij}=\{\begin{array}{cc}{\tau }_i\hfill & I_i\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{is}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{signalized}\mathrm{\hspace{0.17em}\hspace{0.17em}}\hfill \\ \frac{\mathrm{2}{R}_{\text{INT}}}{v_{ij}}\hfill & I_i\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{is}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{isolated}.\hfill \end{array}\end{array}$$

(6)

So, if there is only one vehicle carrying the packet, the probability of meeting at least one vehicle towards expected next road is

$$\begin{array}{cc}& P_{\mathrm{1}}\left(x\ge \mathrm{1}\right)=\mathrm{1}-P\left(x_{\mathrm{1}}=\mathrm{0}\right)=\mathrm{1}-e^{-{\lambda }_{ij}{T}_{ij}}.\end{array}$$

(7)

If there are two vehicles carrying the duplicates of the packet on the road, their travels are independent. Therefore, the probability is

$$\begin{array}{l}{P}_{\mathrm{2}}\left(x\ge \mathrm{1}\right)=\mathrm{1}-P\left(x_{\mathrm{1}}=\mathrm{0}\right)·P\left(x_{\mathrm{2}}=\mathrm{0}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}=\mathrm{1}-e^{-{\lambda }_{ij}{T}_{ij}}-e^{-\mathrm{2}{\lambda }_{ij}{T}_{ij}}.\end{array}$$

(8)

So, if there are n vehicles carrying the duplicates of the packet on the road, their travels are also independent. Therefore, the probability is

$$\begin{array}{l}{P}_n\left(x\ge \mathrm{1}\right)=\mathrm{1}-P\left(x_{\mathrm{1}}=\mathrm{0}\right)·P\left(x_{\mathrm{2}}=\mathrm{0}\right)···P\left(x_n=\mathrm{0}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}=\mathrm{1}-e^{-n{\lambda }_{ij}{T}_{ij}}.\end{array}$$

(9)

We notice that while increasing the number of duplicates (n) in a road, the probability of forwarding them to the expected next road is increasing. In order to provide more opportunities for effective packet switching at an intersection, we propose the scheme of packet buffering in roads with the multiple duplicates propagation. Cluster head will observe the traffic flow and estimate ${\lambda }_{ij}$ and $T_{ij}$ . Then, given an expected $P_n$ , n could be calculated according to (9). Cluster head will manage the duplicates of the packet and n is the TTL value of a new packet.

5. Performance Evaluations

5.1. Survey

We firstly performed a 15 day's survey on an urban area of Chengdu, a City in China. Since choosing target area is crucial in performance evaluation, we prefer ordinary urban region with typical parking distribution to downtown areas where the parking is above average. As shown in Figure 10, we extract a real street map with the range of 3600 m × 2500 m, which contains 24 intersections and 35 bidirectional roads. Each intersection is marked by a number from 1 to 24. During the survey, we investigated the traffic and roadside parking statistics at 16:00, 18:00, and 22:00 of every Tuesday, Thursday, and Saturday. We just counted the vehicles parked along each street within 5 meters. To on-street parking lots, only fringed vehicles along road direction were calculated. We found three kinds of streets with different parking limits (Table 1). The first kind permits free parking at roadside, $R_{\mathrm{1,2}}$ , $R_{\mathrm{2,3}}$ , and so forth, which results in a very high node density 300 veh/km on average. The second one, as $R_{\mathrm{1,4}}$ and $R_{4,9}$ , lacks public parking spaces. These streets have a very low vehicle density, 20 veh/km, which comes from some reserved parking spaces and illegal parking. The rest of streets belong to the third one, a moderate vehicle density with 98 veh/km. During the survey, we also calculated daily traffic by counting the passing vehicles within fifteen minutes at random positions of and found traffic fluctuating from 300 veh/h to 2200 veh/h at different times of one day.

Table 1

On-street parking survey.

Road	Policy	Average density
$R_{\mathrm{1,2}}$ , $R_{\mathrm{2,3}}$ , $R_{\mathrm{5,6}}$ , $R_{\mathrm{7,8}}$ , $R_{\mathrm{15,16}}$ , $R_{\mathrm{16,20}}$ , $R_{\mathrm{17,21}}$ , $R_{\mathrm{18,22}}$ , $R_{\mathrm{13,23}}$	No limits	300 veh/km
$R_{\mathrm{1,4}}$ , $R_{\mathrm{4,9}}$ , $R_{\mathrm{9,15}}$ , $R_{\mathrm{15,19}}$ , $R_{\mathrm{10,11}}$ , $R_{\mathrm{12,18}}$	Strict limits	20 veh/km
Others	Moderate limits	98 veh/km

Figure 10

Road topology in survey and simulation.

5.2. Simulation Setup

We use the open source software, VanetMobiSim-1.1 [25], to generate realistic urban mobility traces, for the generated traffic file can be directly utilized by NS-2.33. The number of simulated vehicles is from 50 to 500. The average speed ranges from 40 to 80 kilometers per hour, depending on the speed limit of the specific road it travels on. The default ratio range is set at 250 m, and the MAC protocol is 2 Mbps 802.11. In the simulation, parked vehicle nodes are located on random positions of each street, following the densities collected in survey. The average parking time of them is 41.40 minutes with a standard deviation of 27.17, which is provided in [21]. The intersections in the map cover a 20 m × 20 m segment without parking. Since free-riding is inevitable, the ratio of the parked vehicles that are willing to share their resources is set to 10% and 30%.

Among mobile vehicles, 10 of them are randomly chosen to send CBR data packet to random roads. The data sending rate (CBR rate) is 1 packet per second. Simulation parameters are shown in Table 2.

Table 2

Simulation parameters.

Parameter	Value
Area	3600 m × 2500 m
Number of intersections	24
Number of mobile vehicles	50~500
Velocity of vehicles	40~80 km/h
Communication radius	100~400 m
Data generation rate	1 packet/s
BEACON interval of cluster	1 s
$P_n$	0.9
$R_{\text{INT}}$	20 m
${\rho }_{\text{pv}}$	10%, 30%

We evaluate the performance of EDP compared with BAS [12], TADS [13], and epidemic routing [10]. Comparing the protocols, we evaluate them according to the following two metrics.

• (1)

Data delivery ratio. The ratio between the number of packets originated by the CBR sources and the number of packets received by the CBR sink at the final destination.

(2)

Data delivery delay. The earliest arrival time of the packet at the destination.

5.3. Simulation Results

Firstly, we compare the performance of EDP with other schemes in terms of data delivery ratio and delay under different densities of mobile vehicles and the results are shown in Figure 11.

Figure 11

Impact of the density of mobile vehicles.

Figure 11 shows the impact of the number of vehicles on the performance of the different schemes in terms of the data delivery ratio and the data delivery delay, respectively. Figure 11(a) depicts the impact of the number of vehicles on the data delivery ratio. As seen from Figure 11(a), the data delivery ratio increases with the increase of the number of vehicles of all schemes. This is because the growth of the density of the vehicles improves the connectivity of the networks and there are more chances to deliver the packet to meet an appropriate next hop. However, when the density of mobile vehicles is low, the two EDP schemes achieve better delivery ratio than BAS and TADS. The reason is that parked vehicles help to increase the connectivity of the network and packets could be delivered by the parked vehicles. TADS has the lowest data delivery ratio when the density of the vehicles is very low because it is hard to predict the traffic precisely. As the number of vehicles increases, due to MAC layer collisions, the number of data requests increases. Therefore, the network traffic dramatically increases in Epidemic, increasing the number of collisions and reducing the data delivery ratio. The delivery ratio of Epidemic drops faster, so Epidemic is very sensitive to the number of vehicles.

Figure 11(b) shows the change of data delivery delay with the increase of the number of vehicles. Compared with Epidemic routing, the other three protocols show much lower delivery delay, since they consider the vehicle traffic pattern when constructing routing path, and can increase the forwarding opportunities along the expected routing paths to route packets efficiently, especially at each intersection. When the density of mobile vehicles is low, the average delivery delay of EDP with 10% PV is about 10% lower than that of BAS and the delivery delay of EDP with 30% PV is about 18% lower than BAS. And TADS behaves like BAS. For Epidemic, as the number of vehicles increases, the delay of Epidemic is decreases first when the number of nodes is low, since more nodes can provide more opportunities for packet forwarding and the redundant duplicates can help the packet be eventually delivered. However, when the number of mobile vehicles is high, the delay of Epidemic is increasing, because Epidemic generates much more redundant duplicates, many of which may be dropped.

Figures 12 and 13 show the impact of communication radius on the performance of the protocols under heavy and light traffic, respectively. Figure 12 plots the results of 400 vehicles moving on the roads. The increasing of communication radius improves the connectivity of the network, so that the delivery ratio increases with the increase of communication radius. When the communication radius is too large, the delivery ratio will decrease because more collisions would be introduced by larger communication radius. As seen from Figure 12(a), when the radius is small, BAS achieves higher data delivery ratio than other schemes. For EDP, it is because there are more overheads for EDP such as cluster management under higher density of mobile nodes. For TADS, the reason is that traffic information is not easy to collect when the radius is small. As in Figure 12(b), though BAS has higher delivery ratio than EDP, it has longer delivery delay than EDP. Likewise, when the radius is short, TADS takes more time to get the traffic to predict the traffic condition, introducing more delay. With the enlargement of communication radius, the delivery ratio of EDP decreases more quickly than BAS because the clusters on road improve the connectivity of the network. However, if communication radius is too large, the delivery delay would decrease due to more collisions.

Figure 12

Impact of communication radius under higher density of mobile vehicles.

Figure 13

Impact of communication radius under lower density of mobile vehicles.

Figure 13 shows how the communication radius influences the performance under light traffic, where there are only 100 mobile vehicles moving on the roads. Obviously, it is not easy to encounter a vehicle and the probability of collisions is small when communication radius is small under light traffic, so the delivery ratio increases with the enlargement of communication radius. As in Figure 13(a), that EDP with 30% PV achieves much higher delivery ratio (about 83%) than other schemes with the assistance of parked vehicles at roadside. It shows EDP achieves much better performance under light traffic than that under heavy traffic, comparing with other schemes. Also, EDP has shorter delivery delay under light traffic, as shown in Figure 13(b).

6. Conclusions

Due to high mobility, the topology of nodes in VANETs changes rapidly. To deal with opportunistic forwarding in VANETs, we propose an efficient data dissemination protocol for multihop data delivery in VANETs. Different from the other works, EDP leverages the parked vehicles at roadside to help forwarding data. The parked vehicles are grouped into a cluster to assist in delivering data and manage the duplicates of data packets. Simulation results show that EDP performs better than other three protocols, especially while the density of mobile vehicles is low.

In our future work, we plan to build a parking model for on-street parking and integrate it into mobile model and then evaluate the performance of EDP in a more realistic environment.