Sage Journals: Discover world-class research

Abstract

Data delivery is the most compelling issue for the applications in vehicular ad hoc networks. The characteristics of VAENTs such as highly dynamic topology and the road-constrained mobility pose great challenges for data delivery in vehicular ad hoc networks. In this paper, a latency estimation-based data delivery (LED) scheme is presented. According to the current location and the moving direction of the vehicles, LED calculates the expected delivery latency (EDL) of each vehicle and chooses the vehicle with the shortest EDL as the next hop to forward data. Simulation results show that LED performs better than VADD.

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]. Besides, 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) [2–6], VANETs usually cannot establish a stable end-to-end path to transmit data packets due to the intermittent connectivity [7–9]. (2) The mobility of vehicle nodes in VANETs is constrained by predefined roads. Due to the buildings and other obstacles, the data delivery based on the V2V communications over VANETs is also constrained by the roads.

Efficient data delivery based on infrastructure-less V2V communications is the most compelling issue for the mentioned applications in VANETs. However, the characteristics of VAENTs such as highly dynamic topology and the road-constrained mobility pose great challenges for data delivery in vehicular ad hoc networks. Some researches have been proposed to resolve data forwarding for vehicular networks. GPSR [4] is a geographical forwarding approach which always chooses the next hop closer to the destination. It is a classic and very efficient data delivery scheme in ad hoc networks, but it may not be suitable for sparsely connected vehicular networks and it cannot select a path with lower latency. Zhao and Cao present VADD [7], which utilizes the predictable mobility in VANET for data delivery. VADD regards each road as a link whose delay is the time consumed to deliver a packet through the corresponding road by the multihop communication and the carrying of moving vehicles on this road. Therefore, packets will be delivered along the shortest-delay trajectory. In cases when no vehicles are available in the next road for data delivery along the optimal trajectory, VADD improves packet delivery reliability by making a routing decision at each intersection to select the best currently available trajectory. Though VADD performs better than GPSR, it neglects the performance difference of individual vehicle while forwarding data.

In this paper, a latency estimation-based data delivery (LED) scheme is presented. According to the current location and the moving direction of the vehicles, LED calculates the expected latency of the individual vehicles and chooses the best vehicle as the next hop to forward data.

The paper is organized as follows: Section 2 discusses some related works. Section 3 states the problems. Section 4 presents the detailed design of LED, followed by the evaluation of LED in Section 5. 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.

Ding et al. [10] 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. Sormani et al. [11] take an accident happening on the highway as an example. In order to prevent dangerous situations, the crashed cars and possibly other cars in the vicinity immediately generate a message that is delivered to the nearest ambulance and police stations, the vehicles within one-mile approaching the accident area and the closest highway entrances.

Most protocols assume that intermediate nodes can be found to set up an end-to-end connection; otherwise, the packet will be dropped [3, 5]. Naumov and Gross [2] 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, its scheme is 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 auto-adjusted on the fly to account for changes, without another discovery process.

Wisitpongphan et al. [12] indicate that although the average recovery time for I-80 type of freeways is, on average, less than 30 seconds, such long network disconnection time could be a major problem for conventional ad hoc routing protocols [3, 5], which just tolerates a network disconnection time of up to 2-3 seconds. In addition, some time-critical applications may not be able to function properly in disconnected VANET as the end-to-end delay could be on the order of several minutes. Vahdat and Becker in [13] 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 [7], 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.

Some protocols add controlled nodes to help message forwarding. Li and Rus [14] proposed to have mobile nodes proactively modifing their trajectories to transmit messages. Zhao et al. [15] proposed to utilize special mobile nodes called message ferries, which move nonrandomly in the deployed area, to help data delivery in a sparse network. However, in vehicular networks, it is impossible to modify the trajectories of the moving vehicles or finding such ferries.

3. Problem Statement

3.1. VADD Analysis

VADD is based on the idea of carry and forward. The most important issue is to select a forwarding path with the smallest packet delivery delay. As shown in Figure 1, VADD has three packet modes: Intersection, StraightWay, and Destination based on the location of the vehicle that carries the packet. In StraightWay mode, the geographically greedy forwarding is applied to deliver the packet to the intersection, entering into Intersection mode. In Intersection mode, packet is determined to be delivered to one of the road segments connected with the intersection. Among the three modes, the Intersection mode is the most critical and complicated one, since vehicles have more choices at the intersection.

Figure 1

The transition mode in VADD.

Before making a forwarding decision, VADD estimates the data delivery delay of different paths to the destination.

As shown in Figure 2, for a packet at the intersection $I_{m}$ , the expected delay of delivering the packet through road segment $r_{m n}$ is as follows:

\begin{matrix} D_{m n} = d_{m n} + \sum_{j \in N (n)} (P_{n j} \times D_{n j}), \end{matrix}

(1)

where

D_{m n}

is the expected data delivery delay from

I_{m}

to the destination if the packet carrier at

I_{m}

chooses to deliver the packet following road segment

r_{m n}

;

d_{m n}

is the delivery delay between

I_{m}

and

I_{n}

;

P_{n j}

is the probability that the packet is forwarded through road

r_{n j}

at the intersection

I_{n}

;

N (n)

is the set of neighboring intersections of

I_{n}

Figure 2

Delay model in VADD.

To shorten the delivery delay, VADD sorts $D_{m n}$ for each neighboring intersections of $I_{m}$ and chooses the road with the smallest expected delay.

3.2. Problem Description

VADD has some disadvantages as follows. (1) In StraightWay mode, packet could be determined to deliver to which direction according to the expected delivery delay. However, it takes some time to deliver the packet to the intersection, which was influenced by the location of the packet carrier, the moving speed, and the traffic flow of the vehicles. (2) Though the geographically greedy forwarding method achieves shorter delivery delay in the StraightWay mode, the packet may be delivered to a road with high latency because the moving direction of the vehicle ahead is uncertain and it may not contact the neighboring vehicle in the optimal road. The wrong choice of the road with high latency leads to more end-to-end delivery delay. In fact, when encountering a vehicle driving to the road with lower delivery delay, packet can be delivered to the vehicle and carried by it to the road with shorter delay, which may achieve shorter data delivery delay than the geographically greedy forwarding approach. Unlike VADD that estimates the expected data delivery delay based on the road, our proposed LED calculates the latency of the individual vehicle and chooses the optimal vehicle as the packet carrier according to the current location and turning direction of the vehicle to achieve the lowest transmission latency.

4. The Design of LED

4.1. The Expected Delivery Latency

LED scheme calculated the expected delivery latency (EDL) of the vehicles based on their current location and moving direction. Assuming that the vehicle $V_{1}$ moves in the road $r_{i j}$ at the speed of v and the distance to the intersection $I_{j}$ is l, the EDL of $V_{1}$ includes two parts. (1) The time carried by $V_{1}$ to the intersection $I_{j}$ , denoted by $t_{carry}$ . (2) The expected end to end delay to the destination from the intersection $I_{j}$ , denoted by $t_{e 2 e}$ . $t_{carry}$ can be calculated by $t_{carry} = l / v$ .

As in VADD, LED selects the next road with the shortest expected delivery delay in the intersection. Assuming that the intersection $I_{j}$ connects n road such as $r_{j 1}, r_{j 2}, \dots, r_{j n}$ sorted by the nondecreasing order of $D_{j 1}, D_{j 2}, \dots, D_{j n}$ calculated by (1). If the vehicle $V_{1}$ carries the data to the intersection $I_{j}$ and will move into road $r_{j a} (1 \leq a \leq n)$ , the data will be carried by $V_{1}$ and delivered to road $r_{j a}$ in the worst case. Obviously, the probability that data delivered to the road whose expected delivery delay is higher than road $r_{j a}$ is zero. The probability that data delivered to road $r_{j m}$ $(1 \leq m \leq a)$ is defined as (2)

\begin{matrix} p_{j m} = {\begin{cases} {C P}_{j 1} & m = 1, \\ [\prod_{s = 1}^{m - 1} (1 - {C P}_{j s})] {C P}_{j m} & 2 \leq m \leq a - 1, \\ 1 - \sum_{s = 1}^{a - 1} p_{j s} & m = a, \end{cases} \end{matrix}

(2)

where

{C P}_{j m}

is the probability of meeting at least one neighboring vehicle towards road

r_{j m}

So, if the vehicle $V_{1}$ carries the data to the intersection $I_{j}$ , the end-to-end delivery delay $t_{e 2 e}$ from the intersection $I_{j}$ to the destination is as follows:

\begin{matrix} \begin{matrix} t_{e 2 e} = \sum_{m = 1}^{a} p_{j m} D_{j m} . \end{matrix} \end{matrix}

(3)

And then, the expected delivery latency of the vehicle $V_{1}$ could be calculated by the equation (4) at the current moment:

\begin{matrix} EDL = t_{carry} + t_{e 2 e} = \frac{l}{v} + \sum_{m = 1}^{a} p_{j m} D_{j m} . \end{matrix}

(4)

As seen from (4), LED computes EDL of the individual vehicle more accurate than VADD while it considers the moving direction of the vehicle in the next intersection and the transmission direction of the data in the worst case.

4.2. Data Delivery

According to (4), each vehicle calculates its EDL and broadcasts a beacon message containing EDL periodically. While receiving beacon message, the vehicle could find its neighboring vehicles and the EDL of the neighbors. When making a forwarding decision, data is always delivered to the vehicle with the shortest EDL until it arrives at the destination.

LED can be used to select an optimal driving route because (4) considers four factors: the current location of the vehicle, the moving direction of the vehicle, the expected delivery latency of the road connected with the intersection ahead, and the probability that data will be delivered to the road connected with the intersection ahead. For example, as in Figure 3, the vehicles $V_{1}$ and $V_{2}$ move to the intersection $I_{j}$ and the vehicle $V_{3}$ moves to the intersection $I_{i}$ . The transmission direction of data is determined by the EDL of the three vehicles. If $V_{3}$ has the shortest EDL, data will be delivered to the intersection $I_{i}$ . Otherwise, data will be transmitted to the intersection $I_{j}$ . Compared with LED, VADD cannot choose the transmission direction of data according to the current traffic, which may incur longer delivery delay. In addition, if $V_{3}$ has the largest EDL, data will be delivered to the intersection $I_{j}$ . Assume that the intersection $I_{j}$ connects the road $r_{j 1}$ and $r_{j 2}$ , and the end-to-end delay of $r_{j 1}$ is far less than $r_{j 2}$ . In the intersection $I_{j}$ , the vehicle $V_{1}$ will enter into the road $r_{j 1}$ and $V_{2}$ will enter into the road $r_{j 2}$ . If the probability that $V_{2}$ meets a vehicle moves to the road $r_{j 1}$ in the intersection $I_{j}$ is too small, data will be carried by $V_{1}$ and delivered to the road $r_{j 1}$ in spite of the fact that $V_{2}$ is closer to the intersection $I_{j}$ than $V_{1}$ . On the contrary, if $V_{2}$ has a high probability to contact a vehicle that moves to the road $r_{j 1}$ in the intersection $I_{j}$ , data will be transmitted to $V_{2}$ and delivered to the vehicle that moves to the road $r_{j 1}$ by $V_{2}$ quickly.

Figure 3

Data delivery of LED.

5. Performance Evaluation

We choose VanetMobiSim+NS2 to evaluate the performance of the LED, in which VanetMobiSim is used to produce the motion model of the vehicles. VADD is also simulated to compare with the LED.

The experiment is based on a 5400 m × 4800 m map, including 36 intersections and the destination is set to the central point of the map. The speed of vehicle is differentiated from 40 km/h∼80 km/h and is set before the vehicle enters into the road segment, which is restricted by the speed limit of the road segment. MAC protocol of the vehicles uses 802.11 and the transmission radius is set to 200 m. TTL is an upper bound on the time that a packet is valid or not. If the TTL of packet expires, packet will be dropped. The simulation parameters are listed in Table 1.

Table 1

Default simulation parameters.

Parameters	Value
Simulation area	5400 m × 4800 m
Intersections	36
Number of vehicles	100
Transmission radius	200 m
Speed of vehicles	40 km/h–80 km/h
MAC protocol	802.11
Time-to-live (TTL)	600 seconds
Packet generation rate	1 packet/second

We evaluate the performance of the two schemes on data delivery ratio and average delivery delay. Firstly, we observe the performance of the two schemes when the packet is without TTL constrains. Then TTL is set to 600 seconds, the performance of the two schemes under different scenarios is discussed.

5.1. Without TTL Constrains

In this section, we set TTL to infinite. That is to say, packet will not be dropped forever and all packets will be delivered to the destination. The average delivery delay of the two schemes is listed in Table 2.

Table 2

Performance of the two schemes without TTL constrains.

	LED	VADD
Average delivery delay(s)	323.6	347.1

As seen from Table 2, LED has less delivery delay than VADD. The reason is that VADD computes the expected delivery delay based on the statistics of traffic flow, which is used to assist in packet forwarding, without any consideration of the current delivery capability of the individual vehicle. In contrast, LED takes the current state of the individual vehicle and calculates the EDL of the individual vehicle more accurately based on the current location and moving direction of the vehicle, which packet is delivered to the vehicle with the lowest EDL.

5.2. Impact of Density

Figure 4 shows the impact of the number of vehicles on the performance of the two schemes in terms of the data delivery ratio and the average delivery delay, respectively.

Figure 4

Performance under different densities of the vehicles.

Figure 4(a) depicts the impact of the number of vehicles on the data delivery ratio. As seen from Figure 4(a), the data delivery ratio increases quickly with the increase of the number of vehicles. 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. But when the number of vehicles is high, the data delivery ratio increases slowly and there is no much difference between the two schemes. The reason is that when the density of the vehicles is high, there are more chances to meet an optimal vehicle in the intersection and the packet will be delivered to the vehicle closer to the intersection, in which LED performs like VADD. Figure 4(b) shows the average delivery delay of the two schemes. The higher the density of the vehicles, the higher probability the packet is delivered to the road with the shorter expected delivery delay to the destination, which reduces the average delivery delay.

5.3. Impact of Communication Radius

Figure 5 shows the performance of the two schemes under different communication radii. Figure 5(a) compares the two schemes on data delivery ratio and Figure 5(b) describes the average delivery delay of the two schemes. When the communication radius is small, the network connectivity is poor and there are little chances to communicate with each other, leading to poor performance. With the enlargement of the communication radius, the data delivery ratio of the two schemes increases and the average delivery delay decreases. The enlargement of the communication radius improves the network connectivity, introducing more chances to meet the next hop. Moreover, there is less time to carry the packet if the communication radius is large and the packet will be delivered to the destination rapidly by multihop.

Figure 5

Performance under different communication radii.

6. Conclusions

In this paper, we proposed a latency estimation-based data delivery scheme. Based on the current location and the moving direction of the vehicles, LED calculates the expected delivery latency of the individual vehicles and chooses the vehicle with the shortest EDL as the next hop to forward data. Simulation results show that LED performs better than VADD.

Footnotes

Acknowledgments

This work is supported by the National Science Foundation under Grants no. 61003229, 61170256, 61173172, and 61103226 and the Fundamental Research Funds for the Central Universities under Grants no. ZYGX2010J074, ZYGX2011J073, and ZYGX2011J060.

References

Fracchia

Meo

Rossi

Knowing vehicles location HELPS avoiding broadcast packets storm

Proceedings of the 4th Annual IEEE International Conference on Pervasive Computing and Communications Workshops (PerCom Workshops'06)

March 2006

Pisa, Italy

118 123

2-s2.0-33750323388

10.1109/PERCOMW.2006.71

Naumov

Gross

T. R.

Connectivity-aware routing (CAR) in vehicular Ad Hoc networks

Proceedings of the 26th IEEE International Conference on Computer Communications (IEEE INFOCOM'07)

May 2007

Anchorage, Alaska, USA

1919 1927

2-s2.0-34548321656

10.1109/INFCOM.2007.223

Johnson

Maltz

Dynamic source routing in Ad Hoc wireless networks

Mobile Computing 1996

New York, NY, USA

Kluwer Academic

153 181

Karp

Kung

H. T.

GPSR: greedy perimeter stateless routing for wireless networks

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

August 2000

243 254

2-s2.0-0034547115

Perkins

C. E.

Royer

E. M.

Ad-hoc on-demand distance vector routing

Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications (WMCSA'99)

February 1999

New Orleans, La, USA

90 100

2-s2.0-34347349933

10.1109/MCSA.1999.749281

Royer

E. M.

Toh

C. K.

A review of current routing protocols for Ad Hoc mobile wireless networks

IEEE Personal Communications 1999 6 2 46 55

2-s2.0-0032621035

Zhao

Cao

VADD: vehicle-assisted data delivery in vehicular Ad Hoc networks

Proceedings of the 25th IEEE International Conference on Computer Communications (INFOCOM'06)

April 2006

Barcelona, Spain

1 12

2-s2.0-34248646800

10.1109/INFOCOM.2006.298

Lee

K. C.

Härri

Gerla

LOUVRE: landmark overlays for urban vehicular routing environments

Proceedings of the 68th Semi-Annual IEEE Vehicular Technology Conference (VTC'08-Fall)

September 2008

Calgary, Canada

1 5

2-s2.0-58149122598

10.1109/VETECF.2008.447

Wisitpongphan

Bai

Mudalige

Tonguz

O. K.

On the routing problem in disconnected vehicular Ad Hoc networks

Proceedings of the 26th IEEE International Conference on Computer Communications (IEEE INFOCOM'07)

May 2007

Anchorage, Alaska, USA

2291 2295

2-s2.0-34548305165

10.1109/INFCOM.2007.267

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.

Sormani

Turconi

Costa

Frey

Migliavacca

Mottola

Towards lightweight information dissemination in inter-vehicular networks

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

September 2006

New York, NY, USA

20 29

2-s2.0-34247363689

10.1145/1161064.1161069

12.

Wisitpongphan

Bai

Mudalige

Tonguz

O. K.

On the routing problem in disconnected vehicular Ad Hoc networks

Proceedings of the 26th IEEE International Conference on Computer Communications (IEEE INFOCOM'07)

May 2007

Anchorage, Alaska, USA

2291 2295

2-s2.0-34548305165

10.1109/INFCOM.2007.267

13.

Vahdat

Becker

Epidemic routing for partially connected ad hoc networks

2000 CS-200006

14.

Rus

Sending messages to mobile users in disconnected ad-hoc wireless networks

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

August 2000

44 55

2-s2.0-0034545825

15.

Zhao

Ammar

Zegura

A message ferrying approach for data delivery in sparse mobile Ad Hoc Networks

Proceedings of the 5th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MoBiHoc'04)

May 2004

United States Department of Transportation

187 198

2-s2.0-4444277059

Latency Estimation-Based Data Delivery Scheme for Vehicular Ad Hoc Networks

Abstract

1. Introduction

2. Related Works

3. Problem Statement

3.1. VADD Analysis

3.2. Problem Description

4. The Design of LED

4.1. The Expected Delivery Latency

4.2. Data Delivery

5. Performance Evaluation

5.1. Without TTL Constrains

5.2. Impact of Density

5.3. Impact of Communication Radius

6. Conclusions

Footnotes

Acknowledgments

References