Efficient Data Dissemination in Urban VANETs: Parked Vehicles Are Natural Infrastructures

Abstract

Data dissemination is the fundamental operation in vehicular ad hoc networks (VANETs); for example, after an accident or congestion is detected by the corresponding sensors mounted on the vehicles, an alert message should be swiftly disseminated to the vehicles moving towards the affected areas. However, the unique characteristics of VANETs, such as high mobility of vehicle nodes, intermittent connectivity, and rapidly dynamic topology, make data dissemination over them extremely challenging. Motivated by the fact that there are large amounts of roadside parked vehicles in urban areas, this paper proposes a parking-based data dissemination scheme for VANETs. Data to be disseminated are buffered at the roadside parked vehicle, which continuously provides data dissemination services for the vehicles passing by. We analyze the challenging issues in achieving parking-based data dissemination and provide possible solution for each issue. Theoretical results illustrate the effectiveness of our approach, and simulation results based on a real city map and realistic traffic situations show that the proposed data dissemination paradigm achieves a higher delivery ratio with lower network load and reasonable delivery delay.

1. Introduction

Nowadays, to facilitate better road safety and comfort driving, more and more vehicles are equipped with wireless devices and different types of sensors. Consequently, large-scale vehicular networks are expected to be available in the near future. With its popularity, VANETs are envisioned to provide us with numerous useful applications. One typical application is intelligent transportation system; for example, after an accident or congestion is detected by the corresponding sensors mounted on the vehicles, an alert message would be swiftly disseminated to the vehicles moving towards the affected areas via vehicular communication. Taking advantage of this application, incoming vehicles will be informed in advance of these accidents/congestions and the drivers may take another route/appropriate actions. Other applications also include available parking spaces notification and commercial ads dissemination. Undoubtedly, these applications would improve our driving experience greatly.

The basic operation in the aforementioned applications is data dissemination. Unfortunately, VANETs are characterized by rapidly dynamic topology, intermittent connectivity, and high mobility of vehicle nodes, which make data dissemination over it a challenging issue. Most of the existing works take advantage of the inter-vehicle communication to achieve data dissemination [1–4]. The weakness of the inter-vehicle scheme is that data to be disseminated can hardly be kept within a target area in highly mobile environments. Towards solving the problem, two abiding geocast techniques [5] could be adopted. One is periodically broadcasting each data at the deployed server. Another is maintaining each data at selected moving vehicles within the target area. For the first approach, when tens of thousands of messages are routed over a long distance to the target areas, excessive transmissions and severe congestion are inevitable. For the second approach, continuous node selection and message handover are required due to the high mobility of vehicle nodes, which incurs great overheads.

In view of the insufficiency of inter-vehicle data dissemination, some researches put forward the infrastructure-based data dissemination. In [6], Zhao et al. propose to deploy roadside units to assist data dissemination. Data to be disseminated are stored temporarily at roadside units in the target area and broadcasted periodically to the vehicles passing by. This scheme is proved to be effective. However, the deployment of roadside units at the city scale also requires a large amount of investment.

In this paper, we propose a parking-based data dissemination scheme, which harnesses the free resource offered by roadside parking for data dissemination in urban areas. Our proposal is inspired by a real world urban parking report [7], 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 accounts for 69.2% of total parking, 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. The basic idea of our parking-based data dissemination scheme is simple: if a vehicle often drives through extensive vehicles parked at roadside, why not let these parked vehicles support data dissemination as roadside infrastructure?

We organize the parked vehicles into different clusters, propose an effective routing scheme to distribute each data message to appropriate roadside parking, and adopt the pub/sub scheme to perform data dissemination. Moreover, we investigate our scheme through theoretic analysis, realistic survey, and simulation. The results prove that our scheme achieves a higher delivery ratio with lower network load and reasonable delivery delay.

The original contributions that we have made in the paper are highlighted as follows. (i)

We exploit the roadside parked vehicles to achieve data dissemination in urban VANETs. Our scheme aims at reducing the overhead brought by inter-vehicle scheme and avoiding the costs brought by constructing roadside infrastructure.

(ii)

We tackle the main challenges in realizing parking-based data dissemination, for example, how to manage the roadside parked vehicles and how to route a data message to the targeted parking efficiently.

(iii)

We evaluate our parking-based data dissemination scheme through theoretical analysis, realistic survey, and simulation. The numeric results show that our scheme is effective.

The remainder of this paper is structured as follows. Section 2 makes a brief overview of related work. Section 3 presents the system model. In Section 4, we explain our parking-based data dissemination scheme in detail. Section 5 proves the effectiveness of our scheme through theoretical analysis, while Section 6 evaluates our scheme through realistic survey and simulation. Finally, Section 7 summarizes the paper.

2. Related Work

Data dissemination over VANETs is extremely challenging due to the unique characteristics of VANETs. In the last decade, many research effects have been devoted to addressing the data dissemination issues in VANETs. Xu et al. propose an opportunistic dissemination (OD) scheme [8]. In this scheme, the data center periodically broadcasts some data, which will be received and stored by passing vehicles. Whenever two vehicles move into the transmission range of each other, they exchange data. This scheme does not rely on any infrastructure. However, the performance of the OD scheme is poor in areas with high vehicle density due to media access control (MAC) layer collisions. This can easily lead to severe congestion and significantly reduce the data delivery ratio. To mitigate the excessive transmissions and congestion, Korkmaz et al. [9] propose a link-layer broadcast protocol to help disseminate the data. The protocol relies on link-layer acknowledge mechanisms to improve the reliability of the multihop broadcast. However, in the case of network congestion, the link-layer solution is not enough. Furthermore, since many information sources may exist in a given urban area, the amount of broadcasted data from these sources can easily consume the limited bandwidth. In [1], Nekovee M proposes an improved Epidemic scheme, which takes advantage of the clustering characteristics of vehicle flow and broadcasts message at the edge of each cluster. This scheme reduces the communication overhead at some extent. In [2], the notification area is divided into several subareas, and message is disseminated based on each subarea, which effectively limits the broadcast range of each message. In [3], the authors put forward MDDV scheme, which exploits the vehicles called message holder to carry the message to the notification area and broadcast it in this area. In [4], Wu et al. propose a mobile distribution-aware data dissemination scheme MDA for VANETS. In MDA, the subscribers' distribution is predicted, and the forwarding of the notification token is controlled to achieve effective distribution of notification brokers (notification-token holder). Although [1–4] cut down the network overhead to some extent. The data to be disseminated can hardly be kept in the target area owing to the intermittent connectivity of VANETs.

Recently, many approaches have been proposed to realize persistent data availability in VANETs. A basic approach is the server approach in [5], in which the server periodically delivers the message to the destination region using a geocast routing protocol. The deficiency of this approach is that frequent broadcasting at the server would consume a large amount of bandwidth. An alternative approach is the Election approach in [5]. It stores the messages at elected mobile nodes inside the geocast destination region. Due to the high mobility of vehicle nodes, continuous node selection and message handover are required in this case.

To reduce the amount of data poured from the server, Zhao et al. [6] propose the idea of intersection buffering, in which the relay and broadcast station (IBer) is used to buffer data copies at the intersection. The IBer broadcasts each message periodically. As a result, the server does not have to frequently broadcast data to guarantee that each vehicle receives the data. In [10], the authors also propose to use stationary roadside units to improve data dissemination performance. In [11], they further discuss the strategic placement of roadside units. Although the deployment of roadside units could improve the dissemination performance dramatically, the widely deployed roadside units will lead to great investments.

3. System Model

3.1. Assumptions

First, we assume that vehicles are equipped with various types of sensors, GPS, and preloaded electric maps, which are already popular in new cars and will be common in the future. Second, we assume that some vehicle users will share their devices during parking. This could be motivated by effective incentives, as indicated in [12, 13]. Finally, we assume that each data message is attached with the following two attributes: (1) target areas, which are the areas where the data is most likely to be interested, and (2) survival time, which indicates the survival time of the data. This assumption is based on the following observation: the disseminated data are often spatial or/and temporal sensitive; for example, for an accident notification message, it is most likely to be the interest of drivers moving towards the affected area, and this message will be invalid after the traffic accident is properly treated.

3.2. Scenario

As shown in Figure 1, the parked vehicles are widely distributed at the roadside in urban area. At a certain moment, a traffic accident happens in one road segment. Assume that the vehicles are equipped with accident detection sensors and the sensor output is monitored and processed by a microcontroller. After the microcontroller detects this traffic accident based on the input from the sensors, it would broadcast an emergency notification message. To lower the impact of this accident on the traffic condition, the emergency notification message should be forwarded to the vehicles moving towards the affected area, so that the drivers could choose to take another route. Similar applications also include parking statistics dissemination. In [14], it is reported that cruising for parking wastes 47,000 gallons of gasoline and produces 730 tons of CO₂ emissions per year in a small business district of Los Angeles. If drivers are provided with parking data dissemination services, the parking space searching costs would be greatly reduced. With the popularity of VANETs, more and more applications would be emerging in VANETs. While tens of thousands of data messages are flooded into the VANETs, an efficient data dissemination scheme is indispensable. Therefore, it is of great significance to develop highly efficient data dissemination scheme for urban VANETs.

Figure 1

A sample scenario.

In our parking-based data dissemination scheme, data to be disseminated are buffered at the roadside parked vehicle, which continuously provides services for the vehicles passing by. Overall, our parking-based scheme involves the following four components. (1)

Data source could be a computer with a wireless interface, a wireless access point, or an infostation [15].

(2)

Data forwarders are the vehicles which help to forward a data item from the data source to the targeted parking clusters.

(3)

Roadside parking cluster is composed of a group of vehicles which are parked along the same road segment and belong to the same partially connected network.

(4)

End users are the vehicle users who have interests in a certain set of data messages while driving.

4. The Proposed Parking-Based Scheme

To facilitate data dissemination, we organize the roadside parked vehicles into clusters. Generally, our proposed parking-based data dissemination scheme is divided into two phases: data forwarding from the data source to appropriate parking clusters within the target area and data dissemination from the parking cluster to vehicles passing by.

4.1. Parking Cluster

A realistic survey [16] provides a quantitative understanding of roadside parking in cities, in which the on-street parking meters in the Ann Arbor city are continuously monitored during six midweek days. It shows that the parking time is 41.40 minutes in average, with a standard deviation of 27.17. The occupancy ratio, defined as occupied space-hour/available space-hour, 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 is feasible in urban areas. In our parking-based scheme, we group the vehicles which are parked along the same road segment and are mutually reachable into a cluster and take it as data buffering unit at street level. Considering the fact that vehicle mobility is strictly constrained by traffic rules and street layout, buffering each data at some clusters in the target area is enough. Therefore, we will first introduce how to elect data buffering units from the existing clusters and then give our cluster management scheme.

In some road segments, the parked vehicles form one cluster, as shown in Figure 2(a). In other road segments, the parked vehicles are isolated from each other and form different partially distributed groups, as shown in Figure 2(b). To determine whether it should act as data buffering unit, we let each cluster periodically report its distribution to other clusters along the same road (with the help of vehicles traveling across the road). After obtaining the distribution of other clusters along the same road, a cluster decides whether it would work as buffering unit according to following rule: if there is only one cluster along the road, this cluster is undoubtedly elected as data buffering unit; if there are two or more than two clusters along the road, the two clusters located at the two ends of the road are elected as data buffering units. After elected as data buffering unit, a cluster needs to be responsible for the cluster management, including head election and membership management.

Figure 2

Data buffering unit.

In our scheme, we specify the following head selection mechanism. In a scenario in Figure 2(a), the two vehicles located at the two ends of the cluster are elected as cluster head. In a two-way road, the two cluster heads, respectively, provide services for the vehicles coming from the nearest intersection. In a scenario in Figure 2(b), the vehicle which locates at the end of the road segment is elected as cluster head in each cluster; this is also to ensure that a vehicle moving into the road could encounter the cluster head in a short time. After the cluster head is determined, the cluster members periodically report their position to the cluster head. Thus, the cluster head is able to manage all parked vehicles, act as local service access points, and perform the data dissemination operation. Considering the fact that the vehicle works as cluster head might leave at any time, we specify the following rule: while the cluster head is leaving (the engine is started), a new round of head selection is triggered, and the data to be disseminated as well as the cluster state are transferred from the old cluster head to the new one.

4.2. Data Forwarding from Data Source to Roadside Parking

In our parking-based scheme, the parking clusters help to buffer the data messages in their target area and provide data dissemination service for the vehicles passing by. To realize this one-hop data dissemination, the data source should first distribute each data to the selected parking clusters within the target area. According to the strategy used, this process could be further divided into two phases: routing from data source to one parking cluster (step 1 in Figure 3) and routing from one parking cluster to other parking clusters (step 2 in Figure 3). We will describe them in detail in the following part.

Figure 3

Data forwarding process.

4.2.1. Routing from Data Source to One Parking Cluster

While investigating the routing from the data source to one parking cluster in the target area, we first focus on the most common scenario, in which the location of the data source is out of the target area of the data message. In our scheme, apart from taking advantage of the mobile vehicles, we also exploit the parked vehicles for data forwarding. To be specific, in the straightway mode, the geographically greedy forwarding is used to forward the data message to the intersection ahead. Here, specially, the parked vehicles are deemed as special mobile vehicles (velocity = 0) and involved in the process of geographically greedy forwarding. In the intersection mode, a vehicle finds the next road to forward the packet according to the utility function of each available road, which is determined by the vehicle density (including both the moving vehicles and parked vehicles) in this road and the distance from the next intersection to the target area.

The utility function of a road segment is defined as follows:

\begin{matrix} U = \frac{ρ_{m} + ρ_{p}}{d}, \end{matrix}

(1)

where

ρ_{m}

represents the density of mobile vehicles,

ρ_{p}

represents the density of parked vehicles, and d is the shortest distance form the next intersection to the target area. If we assume

N_{m}

to be the number of parked vehicles in a road segment,

N_{p}

to be the number of parked vehicles, L to be the length of this road segment, and

r_{pva}

to be the ratio of parked vehicles which are willing to provide parking assistance service, we have

\begin{matrix} ρ_{m} = \frac{N_{m}}{L}, \end{matrix}

(2)

\begin{matrix} ρ_{p} = \frac{r_{pva} N_{p}}{L} . \end{matrix}

(3)

For $N_{p}$ , it could be easily obtained, and for $N_{m}$ , it could be estimated as follows: the cluster head first estimates the driving time within this segment based on the average velocity as $T = L / v$ and then counts the number of vehicles passing by within time period of T.

Using the above data forwarding strategy, a message could be routed to its target area efficiently. After arriving at a road in the target area, the data is propagated along this road. While its carrier encounters the first parking cluster, it forwards the data to this parking cluster. This parking cluster is then responsible for sending the data to the other parking clusters in the same target area. To indicate whether a parking cluster is the first one obtaining the data in the target area, we adopt an additional bit in the head of each message, where 0 represents it has not traversed any parking cluster until now, while 1 represents it has traversed at least one parking cluster.

If the data source is within the target area of a data, the routing process becomes much simpler. Data is sent to a vehicle that moves into its communication range, which works as mobile helper and forward this data along this road, until the carrier encounters a parking cluster.

4.2.2. Routing from One Parking Cluster to Other Parking Clusters

To effectively route a data to all parking clusters in the target area, we propose a tree-based data forwarding scheme, which forwards each data message from one parking cluster to the other parking clusters in the same target area over a tree structure. We assume that one parking cluster knows the location of other parking clusters within the same target area. This could be realized through a simple mechanism with the help of moving vehicles. For example, each parking cluster periodically broadcasts its location (the location of cluster head) to the parking clusters within two hops (the TTL is set as 2), and adjacent parking clusters exchange the information (similar like <cluster ID, location>) they obtain with each other. This process is similar to Link-State Broadcast [17]. Due to the high occupancy of parking lots, a long broadcast cycle is enough. As some vehicles may move away while others may move in, the location reported from the same cluster at different time might be slightly different. We abstract the parking clusters and the roads in a target area as a weighted connected graph $G (V, E)$ , where V is the set of parking clusters and E is the set of roads between two adjacent parking clusters (might be more than one segment). Weight $d_{i j}$ on E is the estimated transmission delay between adjacent parking clusters. Figure 4 shows one such weighted connected graph. We let adjacent parking lot clusters periodically send a delay probe packet to each other and estimate the transmission delay according to the history record. As the transmission delay between two parking lot clusters is affected by their mutual distance, the traffic density, and other factors that change slowly, this approximation is reasonable.

Figure 4

One minimum spanning tree.

The transmission delay between each pair of parking clusters forms a delay matrix, which is updated periodically. With this delay matrix, each parking vehicle could derive a minimum spanning tree, such that the total estimated transmission delay is minimized while routing over this tree. The minimum spanning tree could be easily acquired at each parking cluster through the classic Kruskal's algorithm or Prim's algorithm, both of which are of polynomial complexity. As these two algorithms are all very simple, we will not elaborate them here. If the minimum spanning tree is not unique, the one covers that the shortest road length is chosen as data forwarding tree. Through this way, we could make sure that each parking cluster in a target area maintains the same MST at the same time point. With this tree obtained in each cluster, each data message records its previous hop and is forwarded along this tree. Here, the data forwarding from one cluster to a next-hop cluster uses the routing approach presented in the previous section.

Although routing a packet along any one spanning tree could make sure that the packet could be received by every parking cluster, routing along the minimum spanning tree could realize the same goal in a shorter time. With this routing scheme, each packet only needs to be replicated while new tree branch appears, which greatly decreases the transmission overhead. Moreover, the consistency among packets buffered at different parking clusters could also be maintained.

4.3. Demand-Driven Data Dissemination

VANETs are characterized by limited bandwidth. To make full use of this scarce resource, blind data dissemination should be avoided. We observe that the vehicle users usually only have interests in certain types of data items. Thus, we adopt a demand-driven data dissemination scheme. The vehicles users express their interests in certain types of data messages, while the parking cluster delivers the matched ones to them. In this sense, our system is a pub/sub system. The data source acts as publisher, the mobile vehicle acts as subscriber, while the parking cluster acts as a broker, which is used to ensure that the data from the data source could be delivered to the subscribers.

To achieve the demand-driven data dissemination, the format of a data message is defined as <MsgID, AOI, topic, TTL>, among which the MsgID represents the ID of this data message, AOI represents the target areas, topic indicates the type, and TTL is the survival time of this data message. For the topic, it is represented by a tree as follows in Figure 5.

Figure 5

Topic representation.

The data dissemination at the parking cluster includes the following three phases. (1)

Subscribe: an end user customizes a subscription according to his/her requirements, and this subscription is periodically broadcasted in the control channel.

(2)

Match: once receiving a subscription, the parking cluster compares it against the stored data messages. This could be realized using the existing matching algorithm [18, 19].

(3)

Data dissemination: if there is any data messages which match the subscription, the parking clusters broadcast it in the service channel, which is then received by the subscribers.

Due to the fact that each data item is buffered at multiple parking clusters in the same target area, a vehicle may receive replicas of the same data message while driving in this area. To avoid this problem, we let the subscriber piggyback the IDs of the last n data messages received while broadcasting the subscription. Through this way, we could guarantee that the vehicle users will not be disturbed by replicas of the same data message.

5. Theoretical Analysis

We consider a road segment S with length L. Assume that the number of vehicles moving on this road is $K_{m}$ , among which the number of vehicles that carry the desired message is $K_{c}$ . The communication range of each vehicle is R, and there are $K_{P}$ vehicles parked uniformly along one side of this road. Imagine that a vehicle moves into road S at time 0. We will investigate the probability of getting the desired message through the inter-vehicle-based scheme and the parking-based scheme, respectively, on this road segment.

5.1. Parking-Based Scheme

As the vehicles are uniformly parked along road S, we have the number of vehicles parked within a distance of R of the intersection is

\begin{matrix} N_{e} = K_{p} \cdot \frac{R}{L} . \end{matrix}

(4)

Here, the width of the road is neglected. Among the $N_{e}$ vehicles, the probability of at least one vehicle willing to provide PVA services is

\begin{matrix} p = 1 - {(1 - {pva}_{ratio})}^{N_{e}} . \end{matrix}

(5)

Substituting $N_{e}$ with (3), we have the probability for a vehicle getting a data from the parking cluster at the intersection is:

\begin{matrix} p = 1 - {(1 - {pva}_{ratio})}^{K_{p} R / L} . \end{matrix}

(6)

Now we assume $L = 1000 m, R = 200 m$ , ${pva}_{ratio} = 30 %$ , and study how the probability p varies with the number of parked vehicles, with the results shown in Figure 6.

Figure 6

Impact of $K_{p}$ on the probability p.

We observe that with 40 vehicles parked along a road with a length of 1 km, the probability for the vehicle getting the data at the intersection is higher than 94%. From the parking report [16], we learn that the average number of parked vehicles along a road (in one side) with 1 km is much higher than 40 in urban areas. Thus, while taking advantage of the parking cluster, the probability of getting the desired data at the intersection is greater than 94%.

5.2. Inter-Vehicle Scheme

We assume $N (t); t \geq 0$ denotes the number of encountered mobile vehicles in the time of $(0, t]$ . Notice that the $N (t), t \geq 0$ satisfies the conditions of the Poisson process [20]. Therefore, $N (t), t \geq 0$ is a Poisson process. We define $W_{n}$ as a random variable and have the sequence of $W_{0} = 0, \dots, W_{i} = t_{i}, \dots$ , where $t_{i}$ stands for the beginning until encountering the number i mobile vehicle. According to the properties of Poisson process, we can derive that $W_{n}, n = 1,2, \dots$ is an Erlang distribution, with the probability density function expressed as

\begin{matrix} f_{w_{n}} (t) = {\begin{cases} \frac{λ^{n}}{Γ (n)} t^{n - 1} e^{- λ t}, & if t \geq 0, \\ 0, & otherwise . \end{cases} \end{matrix}

(7)

Then, we have the probability of encountering the number n mobile vehicle in the time of $(0, t]$ is

\begin{matrix} F (t) = \int_{0}^{t} \frac{λ^{n}}{Γ (n)} t^{n - 1} e^{- λ t} d t = \sum_{k = n}^{\infty} \frac{λ t^{k}}{k!} e^{- λ t} . \end{matrix}

(8)

As the possibility for a moving vehicle carrying the desired data item, represented by P, is $K_{c} / K_{m}$ , the possibility of obtaining the desired data item from the number n encountered vehicle is

\begin{matrix} p_{n} = \sum_{k = n}^{\infty} \frac{λ t^{k}}{k!} e^{- λ t} {(1 - P)}^{n - 1} P . \end{matrix}

(9)

Considering the fact that a moving vehicle might obtain the desired data item from the number $1, 2, \dots, N (t)$ encountered vehicle, we have

\begin{matrix} p = \sum_{n = 1}^{N (t)} \sum_{k = n}^{\infty} \frac{λ t^{k}}{k!} e^{- λ t} {(1 - P)}^{n - 1} P . \end{matrix}

(10)

This can be further represented by

\begin{matrix} p = \sum_{n = 1}^{N (t)} (1 - \sum_{k = 0}^{n - 1} \frac{λ t^{k}}{k!} e^{- λ t}) {(1 - P)}^{n - 1} P . \end{matrix}

(11)

Now we assume $L = 1000 m$ , set $λ = 2, K_{m} = 100, t = 20$ , $N (t) = 60$ (as the average value obtained in our survey), and study the probability p. According to formula (11), if $K_{c} = 2$ , p equals 69%. That is to say, if there are only 2 copies of the same message kept within a road segment, the possibility for a moving vehicle getting the desired message within 20 s is only 69%. Obviously, the parking-based data dissemination scheme outperforms the inter-vehicle-based scheme.

6. Performance Evaluation

In this section, we investigate realistic parking and traffic profile in real urban environments and evaluate the performance of parking-based scheme and other two alternative data dissemination schemes in NS-2.33.

6.1. Survey

We performed a six-week survey on an urban area of Chengdu, a city in China, for collecting realistic parking and traffic profile. 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 7, we extract a real street map with the range of 1600 m × 1400 m, which contains 10 intersections and 14 bidirectional roads totaled up to 7,860 meters. Each intersection is marked by a number from 0 to 9.

Figure 7

Road topology in survey and simulations.

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 counted the vehicles parked along each street within 5 meters and skipped those parked in the middle of obstacles or too far from the roads. To on-street parking lots, only fringed vehicles along road direction were calculated. As shown in Table 1, there are three classes of streets with different parking limits. The first class permits free parking at roadside, as $R_{04}, R_{15}$ , and $R_{26}$ , which results in a very high node density. The second one, as $R_{37}$ and $R_{79}$ , lacks public parking spaces. These streets have a very low vehicle density that comes from some reserved parking spaces and illegal parking. The rest of the streets belong to the third one, which has a moderate vehicle density. Generally, the parked vehicle numbers are stable in different hours of a day. During the survey, we also calculated daily traffic by counting the passing vehicles within fifteen minutes at random positions and found traffic fluctuating from 300 veh/h (vehicle per hour) to 2200 veh/h at different time of one day. If the road width is 20 m, the corresponding moving vehicles within the area range from 60 to 400, with the average speed ranges of 40 km/h to 80 km/h.

Table 1

Roadside parking in survey.

Street	Policy	Density	Average
$R_{04}$ , $R_{15}$ , $R_{26}$	No limits	280–320 veh/km	308 veh/km

$R_{37}$ , $R_{79}$	Strict limits	15–25 veh/km	21 veh/km

$R_{01}$ , $R_{12}$ , $R_{23}$ , $R_{45}$ , $R_{56}$ , $R_{67}$ , $R_{48}$ , $R_{68}$ , $R_{89}$	Moderate limits	72–180 veh/km	95 veh/km

6.2. Simulations

Since accurately modeling node movement is very important for simulation, we use the open source software, VanetMobiSim-1.1 [21], to generate realistic urban mobility traces. The generated traffic file can be directly utilized by NS-2.33. To produce sparse traffic and traffic changes, we deploy different vehicle numbers, that is, 50, 100, 150, 200, 250, and 300, to the map. The radio 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 density collected in Table 1. The average parking time is 41.40 minutes with a standard deviation of 27.17, which is provided in [18]. Since not all parked vehicles are willing to share their wireless devices, a participating ratio of 30% is deployed in default. We assume that the parking clusters are established at the beginning of simulation and are maintained at a cycle of 60 seconds.

To simulate data dissemination, a data source is deployed at the center area of the simulated area, which generates new message with a given time interval. For each message, its target area is specified as a rectangle area which includes four intersections and the roads among them (e.g., the area composed of $R_{01}$ , $R_{04}$ , $R_{45}$ , and $R_{15}$ in Figure 5.), and we assume that 20% of vehicles moving in the target area are interested in it. The default parameters are shown in Table 2.

Table 2

Performance under default parameters.

Parameter	Default value
Number of vehicle	200
Vehicle velocity	40∼80 kph
Size of data message	10 kb
Interval of beacon message	1 second
Data generation rate	0.1/second
Data survival time	30 minutes

We mainly discuss three data dissemination mechanisms: our parking-based data dissemination, inter-vehicle-based data dissemination, and OD [8]. For the inter-vehicle based scheme, data messages to be disseminated are routed to the target area using GPSR [22] routing protocol and are maintained within each road segment by the mobile vehicles. While the carrier is leaving a road segment, the maintained data would be transmitted to the furthest vehicle that located within its communication range and drives on the same road segment. Here, similar to our parking-based scheme, we let the message carrier respond to the message subscription within one hop.

The performance of the three mechanisms is measured by the following three metrics.

Data Delivery Ratio

For each message, the delivery ratio is defined as the fraction of subscribers that successfully received this message.

Data Delivery Delay

For each message, the delivery delay is defined as the time spent for a subscriber obtaining this message after entering the target area of this message.

Network Traffic Overhead

The network traffic overhead is defined as the total amount of data generated during the simulation.

The average delivery ratio is the mean value of delivery ratio of all the disseminated messages, and the average delivery delay is the mean value of the delivery delay of all the disseminated messages. For each measurement, 30 simulation runs are used, and each simulation lasts for 60 minutes.

We first test the performance of the above three schemes under the default parameters. The results are shown as Table 3. We notice that compared to the inter-vehicle scheme and OD, parking-based scheme shows better performance. It achieves a higher delivery ratio with less delivery delay at lower overhead. For parking-based scheme, replicas of the same message are maintained at many parking clusters in the target area. Once a vehicle comes to a road with parking cluster, it will get the desired message in short time. Thus, the average delivery ratio is higher and the average delivery delay is lower. In addition, as each message only needs to be broadcasted within one hop of the parking cluster, the overhead is very low. For the inter-vehicle scheme, data to be disseminated are maintained at the mobile vehicles. Owing to the high mobility of vehicles, frequent handovers among the mobile vehicles are needed to maintain a data message within a road segment. Hence, the network overhead is high. Moreover, there might exist some special cases, in which the vehicle which carries a message leaves a road segment, and it has no chance to perform data handover (there are not any other vehicles within its communication range), and the new coming vehicles have no way to acquire this data. Thus, the delivery ratio is lower and the data delivery delay is higher. For OD, the overhead is much higher than the other two schemes. However, the data delivery ratio is not as high as it should be. In OD, whenever two vehicles move into the transmission range of each other, they will exchange data, which leads to severe congestion and significantly reduces the data delivery ratio.

Table 3

Performance under default parameters.

Scheme	Parking-based	Inter-vehicle	OD
Average delivery ratio (%)	93.2	85.4	80.6
Average delivery delay (s)	3.5	18.2	7.6
Network traffic overhead	1.53 × 10⁴	2.4 × 10⁵	0.7 × 10⁶

6.2.1. Impact of Vehicle Density

This group of experiments illustrates the impact of vehicle density on the performance of three data dissemination schemes. Form Figure 8, we observe that the parking-based scheme works well under different road traffic, while the inter-vehicle scheme shows bad performance under sparse traffic. The parking based scheme relies on the roadside parking. As long as there are a certain amount of parked vehicles, the message availability within the target area could be guaranteed. However, the inter-vehicle scheme relies on the moving vehicle, which can hardly ensure the message availability in sparse traffic and thus lead to low delivery ratio. For OD, while the vehicles density increases, the possibility of collisions in media access control (MAC) layer is increased. Thus, the delivery ratio decreases while the delivery delay reduces.

Figure 8

Impact of vehicle density.

6.2.2. Impact of Data Publication Rate

The data publication rate determines the number of messages to be disseminated over VANETs. Higher data publication rate means larger network load. Through this group of experiments, we will see how the data publication rate affects the performance of the three data dissemination schemes. As shown in Figure 9, while the data publication rate varies from 1 message/10 s to 1 message/1 s, the delivery ratio of parking based scheme decreases slightly, while the delivery ratio of inter-vehicle scheme drops obviously. This is because parking-based scheme buffers data at roadside parking and performs data dissemination within one hop, which greatly reduces the possibility of transmission collision. The inter-vehicle scheme maintains data at mobile vehicles, which causes frequent handover and excessive transmission while the publication rate is high. With the increase of the publication rate, the overheads of the three schemes are all increased, and that of OD scheme is more obvious. Here, we also observe that the parking based scheme outperforms the other two schemes.

Figure 9

Impact of data publication rate.

6.2.3. Impact of Data Packet Size

This group of experiments investigates the impact of data packet size on the performance of three data dissemination schemes. As shown in Figures 10(a) and 10(b), the data delivery ratio and delivery delay of parking-based scheme are superior to that of the other two schemes under different data packet size. For the parking-based scheme, data messages are maintained at the roadside parked vehicles, which thus could provide stable data dissemination services for the vehicles passing by. However, for the inter-vehicle scheme, data messages need to be frequently handed over to the vehicles still moving within the road segment. With the increasing data packet size, the handover suffers from more losses; thus, the data delivery ratio is decreased and the data delivery delay is increased. For OD, larger data packet size means much more serious collision. Hence, the performance becomes worse.

Figure 10

Impact of data packet size.

7. Conclusion

Data dissemination over VANETs is challenging due to the fact that data messages can hardly be kept in a specified target area. In this paper, we propose the idea of parking-based data dissemination, which leverages the roadside parking to buffer the data to be disseminated and performs data dissemination. We organize the parked vehicles into clusters, offer a routing scheme to distribute each data message to appropriate roadside parking, and introduce the pub/sub scheme into the last stage of data dissemination. Our parking-based data dissemination scheme exhibits a low capital overhead by exploiting the free resources offered by parked vehicles and a low operational overhead via efficient operations. The theoretical analysis demonstrates the superiority of our scheme. At last, the numerical results also show that our scheme achieves a higher data delivery ratio at lower network traffic overhead and reasonable delay.

Footnotes

Acknowledgments

This work is supported by National Science Foundation of China under Grant nos. 61170256, 61103226, 61103227, 61173172, and 61272526 and the Fundamental Research Funds for the Central Universities under Grant nos. ZYGX2011J060, ZYGX2010J074, and ZYGX2011J073.

References

Nekovee

Epidemic algorithms for reliable and efficient information dissemination in vehicular Ad Hoc networks

IET Intelligent Transport Systems 2009 3 2 104 110

2-s2.0-67249099900

10.1049/iet-its:20070061

Caliskan

Graupner

Mauve

Decentralized discovery of free parking places

Proceedings of the 3rd ACM International Workshop on Vehicular Ad Hoc Networks (VANET'06)

September 2006

New York, NY, USA

30 39

2-s2.0-34247386346

10.1145/1161064.1161070

Fujimoto

Guensler

Hunter

MDDV: a mobility-centric data dissemination algorithm for vehicular networks

Proceedings of the 1st ACM International Workshop on Vehicular Ad Hoc Networks (VANET'04)

October 2004

New York, NY, USA

47 56

2-s2.0-14944351780

Liu

Wang

Chen

Gong

Mobile distributionaware data dissemination for vehicular Ad Hoc Networks

Software Journal 2011 22 7 1580 1596

10.3724/SP.J.1001.2011.03871

Maihöfer

Leinmüller

Schoch

Abiding geocast: time-stable geocast for Ad Hoc networks

Proceedings of the 2nd ACM International Workshop on Vehicular Ad Hoc Networks (VANET'05)

2005

ACM

20 29

10.1145/1080754.1080758

Zhao

Zhang

Cao

Data pouring and buffering on the road: a new data dissemination paradigm for vehicular Ad Hoc networks

IEEE Transactions on Vehicular Technology 2007 56 6 I 3266 3277

2-s2.0-36749002651

10.1109/TVT.2007.906412

Morency

Trépanier

Characterizing parking spaces using travel survey data

CIRRELT, 2006

Ouksel

Wolfson

Opportunistic resource exchange in inter-vehicle Ad Hoc networks

Proceedings of the IEEE International Conference on Mobile Data Management (MDM)

2004

4 12

Korkmaz

Ekici

Ozguner

Urban multi-hop broadcast protocol for inter-vehicle communication systems

Proceedings of the 1st ACM International Workshop on Vehicular Ad Hoc Networks (VANET'04)

2004

76 85

10.1145/1023875.1023887

10.

Ding

Wang

Xiao

A static-node assisted adaptive routing protocol in vehicular networks

Proceedings of the 4th ACM International Workshop on Vehicular Ad Hoc Networks (VANET'07)

September 2007

59 68

2-s2.0-37849007552

10.1145/1287748.1287758

11.

Lochert

Scheuermann

Wewetzer

Luebke

Mauve

Data aggregation and roadside unit placement for a vanet traffic information system

Proceedings of the 5th ACM International Workshop on VehiculAr Inter-NETworking (VANET'08)

September 2008

New York, NY, USA

58 65

2-s2.0-59249090296

10.1145/1410043.1410054

12.

Eltoweissy

Olariu

Younis

Towards autonomous vehicular clouds

Ad Hoc Networks 2010 49 1 16 Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering

13.

Olariu

Khalil

Abuelela

Taking VANET to the clouds

International Journal of Pervasive Computing and Communications 2011 7 1 7 21

10.1108/17427371111123577

14.

Shoup

Cruising for parking

Access 2007 30 16 22

15.

Frenkiel

R. H.

Badrinath

B. R.

Borràs

Yates

R. D.

Infostations challenge: balancing cost and ubiquity in delivering wireless data

IEEE Personal Communications 2000 7 2 66 71

2-s2.0-0033692686

10.1109/98.839333

16.

Adiv

Wang

On-street parking meter behavior

Transportation Quarterly 1987 41 281 307

17.

Kurose

J. F.

Ross

K. W.

A top-down approach featuring the internet

18.

Meier

Cahill

STEAM: event-based middleware for wireless Ad Hoc networks

Proceedings of the 1st International Workshop on Distributed Event-Based Systems (DEBS'02)

2002

639 644

10.1109/ICDCSW.2002.1030841

19.

Fiege

Gärtner

Kasten

Zeidler

Supporting mobility in content-based publish/subscribe middleware

Proceedings of the ACM/IFIP/USENIX International Conference on Middleware (Middleware'03)

2003

103 122

20.

Feller

An Introduction to Probability Theory and Its Applications 2008

New York, NY, USA

John Wiley & Sons

21.

Härri

Filali

Bonnet

Fiore

VanetMobiSim: generating realistic mobility patterns for VANETs

Proceedings of the 3rd International Workshop on Vehicular Ad Hoc Networks (VANET'06)

2006

New York, NY, USA

ACM

96 97

10.1145/1161064.1161084

22.

Karp

Kung

GPSR: greedy perimeter stateless routing for wireless networks

Proceedings of the 6th Annual International Conference on Mobile Computing and Networking (MobiCom'00)

2000

ACM

243 254

10.1145/345910.345953