SADV:Static-Node-Assisted Adaptive Data Dismination in Vehicular Networks
Yong Ding and Li Xiao,Senior Member,IEEE
Abstract—Vehicular networks have recently attracted great in-terest in the rearch community,and multihop data dismination has become an important issue.To improve data-delivery perfor-mance,we propo deploying static nodes at road interctions to help relay data.In this paper,we prent SADV,which is a static-node assisted adaptive data-dismination protocol for vehicular networks.With the assistance of static nodes at interctions,a packet is forwarded to the static node when there are no vehicles available to deliver the packets along the optimal path.The static node is able to store the packet and transmit it when the optimal delivery path becomes available.In addition,we let adjacent static nodes measure the delay of forwarding data between each other in real time so that the routing decision that is made at static nodes can adapt to the changing vehicle densities.Moreover,a multipath routing mechanism is also adopted in SADV,which is effective in reducing the data-delivery delay.Our simulation results show that SADV outperforms other multihop data dismination protocols, particularly under median or low vehicle density where the net-work is frequently partitioned.In this paper,we also prent some heuristic deployment strategies to maximize SADV performance under partial deployment of static nodes and analyze them by simulations.
勾魂面
Index Terms—Geographic routing,mobile ad hoc networks (MANETs),multihop routing,vehicular networks.
I.I NTRODUCTION
V EHICULAR networks have recently attracted great in-terest in the rearch community.Many potentially u-ful applications have been envisioned in vehicular networks [1]–[3].The range from safety applications,such as vehicle collision avoidance,to other valuable applications,such as real-time traffic estimation for trip planning,information retrieval, and media content sharing.Moreover,by embedding nsors in vehicles,a mobile nsor network can be established to mon-itor roads and other environmental conditions.The vehicular networks can act as“delivery networks”to transfer data from remote nsor nets to Internet rvers.
Most of the previous rearch on intervehicle communication is limited to vehicles within one hop or a few hops away[1],[2] [4]–[6],such as communicating with nearby upstream traffic
Manuscript received June7,2009;revid November12,2009and January31,2010;accepted February9,2010.Date of publication March15, 2010;date of current version June16,2010.This work was supported in part by the U.S.National Science Foundation under Grant CCF-0514078,Grant CN
S-0551464,and Grant CNS-0721441.The review of this paper was coordinated by Dr.L.Cai.
The authors are with the Department of Computer Science and Engineer-ing,Michigan State University,East Lansing,MI48824-1226USA(e-mail: dingyong@c.msu.edu;lxiao@c.msu.edu).
Color versions of one or more of thefigures in this paper are available online at ieeexplore.ieee.
Digital Object Identifier10.1109/TVT.2010.2045234vehicles to avoid collisions.However,it is also important to nd data from a vehicle to a destination that is veral miles away through multihop relay by a number of intermediate vehicles.For example,the nsing data from a vehicle may need to be nt to a sink that is deployed miles away,or a vehicle may want to nd queries to a remote site such as a gas station.Thus,a multihop routing algorithm is needed in a large vehicular network for the applications.
A vehicular network can be regarded as a special type of mobile ad hoc networks(MANETs)with some unique features. First,as vehicles move at high speed,the topology of the vehicular network changes rapidly.Second,unlike MANETs where an end-to-end connection is usually assumed,vehicular networks are frequently disconnected,depending on the vehicle density.In additio
n,the movement of vehicles is constrained by the roads,which renders many topology holes in the network. The characteristics make the classical MANET routing algo-rithms such as Ad Hoc On-Demand Distance Vector[7]and Greedy Perimeter Stateless Routing[8]inefficient in vehicular network,and significantly influence the design of alternative routing protocols.
Due to the rapidly changing topology in vehicular networks, geographic routing mechanisms become more preferable than topology-bad routing mechanisms becau of the latter’s high maintenance overhead of routing tables.“Opportunistic for-warding”[9]–[11]has been propod,targeting networks where the existence of an end-to-end path cannot be assumed.Specif-ically,a vehicle will carry the packet and forward it to a new vehicle when they meet.“Trajectory-bad forwarding”[12], [13]is an extension to geographic routing mechanism,which tries to deliver packets along a quence of predefined roads or a trajectory.It is particularly suitable for vehicular networks where vehicles are restricted on roads with static structures. Mobility-centric data dismination(MDDV)[14]and vehicle-assisted data delivery(V ADD)[15]are two multihop routing protocols in vehicular networks,which combine geo-graphic forwarding,opportunistic forwarding,and trajectory-bad forwarding to deliver data from a mobile vehicle to a static position beside the road.They abstract each road as a link where the packet-delivery delay depends on the vehicle density on the road.Therefore,a packet will
be delivered along the shortest delay trajectory to the destination.However,as a vehic-ular network consists of highly mobile nodes,it is possible that when a packet reaches an interction,it cannot be delivered along the shortest delay trajectory becau there is no vehicle within the wireless communication range in the next road along the trajectory to relay the packet at that moment.V ADD copes with this problem by lecting the best currently available path,
0018-9545/$26.00©2010IEEE
where an available path means that there are vehicles within the communication range on that path to continue delivering the packet.
There are two problems in the current routing protocols for vehicular networks.1)The performance of V ADD is quite nsitive to the vehicle density.Under high vehicle density, there is a high probability that the next path along the shortest delay trajectory toward the destination is available when the packet reaches an interction.However,when the vehicle density is median or low,the cond best,the third best,or even the worst path may be taken at an interction becau they are the only available paths at the moment.This makes the actual packet-delivery route deviate far from the optimal one,leading to a dramatic increa in the packet-delivery delay.
2)The real shortest delay trajectory may not be taken under inaccurate delay estimation of each road.Both MDDV and V ADD estimate the packet-delivery delay along each road bad on some offline statistical parameters,such as the average vehicle velocity and vehicle density on the road at different times of a day.Nevertheless,as the parameters vary with time, the statistical result is not an accurate estimation of the current packet-delivery delay along each road.
In this paper,we propo SADV,which is a static-node assisted adaptive data dismination protocol for vehicular net-works.Different from MDDV and V ADD,this paper focus on data delivery in large-scale and dynamic V ANETs under low vehicle densities,where V ADD experiences dramatic per-formance degradation in the packet-delivery delay,and MDDV even renders poor reliability.The contributions of this paper are in the following aspects.
•We propo deploying static nodes at interctions,which enables packets to be stored at an interction until the optimal path(the path with the minimum expected data delivery delay to the destination)is available.Our simu-lation shows that the propod static-node assisted routing protocol can dramatically improve the packet-delivery per-formance compared with the previous work.
•To better estimate the delay of forwarding packets along each road,the static nodes are designed to be able to measure the packet-forwarding delay and propagate the link delay information.Therefore,the routing decision in each static node can adapt to the changing vehicle densities.We analyze the converging speed of the link-delay update(LDU)by simulations.
•We also propo a multipath routing algorithm,which can further decrea the packet-delivery delay without an exponential increa in the protocol overhead.•Furthermore,we study intelligent partial deployment strategies of static nodes when it is not possible to deploy
a static node at each interction.
The rest of this paper is organized as follows.Previous studies are summarized in Section II.The motivation of this paper is introduced in Section III.The detailed description of our routing protocol SADV is in Section IV.SADV under partial deployment of static nodes is discusd in Section V.In Section VI,we evaluate our propod approach by comparing it with V ADD.We conclude this paper in Section VII.
II.R ELATED W ORK
There have been many studies on delivering messages in spar MANETs with sporadic connectivity and ever-prent network partitions.In the networks with extreme conditions, traditional routing algorithms that assume the fully connected path between hosts become inefficient.In ca of the ran-dom movement of mobile nodes,“opportunistic forwarding”has been propod in[10],[16],and[17].Some other stud-ies employed controlled mobility to help message delivery
[18]–[20].
A vehicular ad hoc network(V ANET)is a special type of MANETs.Several studies have focud on multihop routing in V ANETs in addition to the work we have discusd in Section I. Greedy perimeter coordinator routing[21]is a position-bad routing protocol,which us the knowledge of the street map structure.Once the packet reaches the interction,the routing decision is made to forward the packet to the neighboring vehicle with the largest progress toward the destination.Greedy traffic aware routing[22]us the vehicle density as well as the distance from the destination for route decision at interc-tions.When a packet reaches the interction,it will lect the neighboring interction,which is geographically clost to the destination and has the highest vehicle traffic.
Louvre[23]abstracts the street map into an overlay network bad on the vehicles at interctions and the vehicle density in each road.There exists a link if and only if the vehicle density on the road is higher than the predefined threshold.A routing protocol that us the similar idea of overlay routing has been propod in[24].However,they are not suitable for scenarios of low vehicle densities becau the overlay network may be disconnected most of the time.In contrast,this paper deals with the V ANET under low vehicle densities as well.Throwbox [25],which is a device that can store and forward data,has been designed to improve the network throughput and reduce the packet delay in delay-tolerant networks.The placement of throwboxes and the determination of packet forwarding trajectory are bad on the contact opportunities between each pair of mobile nodes,which can be effective in small-scale networks.However,the assumption of known contact opportunities limits its extensibility to larger scale networks. The static node in this paper takes the similar idea with throwbox in that it can store and forward data when necessary. Different from throwbox,our solution does not require the node contact opportunities.Instead,both the deployment of static nodes and the routing algorithm utilize the street map structure and vehicle densities of each road in vehicular networks.The SADV routing protocol is a geographic-bad routing protocol, where the routing decision at each vehicle or static node is bad on the knowledge of its position on the street map and its communication with neighbors.As a result,the propod SADV is a practical solution for large-scale networks.
To evaluate routing protocols in V ANETs by simulation, various traffic mobility models have been studied.Some stud-ies ud vehicle movement models to simulate traffic[24], [26]–[28],while Naumov et al.[29]evaluated routing protocols bad on realistic public and private traffic over the real regional road maps of Switzerland.We u the model in[26]to evaluate
DING AND XIAO:SADV:STATIC-NODE-ASSISTED ADAPTIVE DATA DISSEMINATION IN VEHICULAR NETWORKS
2447 Fig.1.Packet delivery delay of V ADD.(a)Mean packet-delivery delay.(b)Packet-delivery delay(100
vehicles).
Fig.2.Static-node assisted routing in a V ANET.
our protocol becau we believe that it can capture the dynamics of the problem that we want to address in this paper.
III.D ATA D ISSEMINATION U NDER
D IFFERENT V EHICL
E D ENSITIES
To evaluate the performance of V ADD with regard to the packet-delivery delay,we u the delay of e
pidemicflooding [16]as a baline.In epidemicflooding,two vehicles exchange the packets that they do not have in common whenever they can communicate with each other.Assume that there is no packet loss due to transmission collision;epidemicflooding is the quickest way to deliver a packet to its destination.Therefore, we u this value as the lower bound in our analysis.In the following,we refer to this method as“flooding.”
Fig.1illustrates our experiment to evaluate the performance of V ADD under different vehicle densities.We extract a re-gional road map from Tiger[30],which is shown in Fig.6.The simulation is performed on this road topology with different numbers of vehicles(the detailed experiment tting is ex-plained in Section VI).As shown in Fig.1(a),when the vehicle density is high,the mean packet-delivery delay of V ADD is clo to that offlooding.However,the gap increas with the decrea in the vehicle density.Moreover,V ADD becomes unstable under low vehicle densities.Fig.1(b)shows the com-parison of the delivery delay of individual packets between V ADD andflooding when100vehicles are simulated in the area.We can obrve that the packet-delivery delay of some packets is much larger than that offlooding,while the delay of some other packets is clo or even equal to the optimal value. There are two reasons for this performance degradation.妇炎洁使用方法
1)V ADD choos the best currently available path at each interction.However,when the vehicle de
nsity is low,the optimal path may not always be available at the moment.Thus, V ADD has to deliver packets via detoured paths.In the worst ca,the packet may go through a much longer path as indicated by the peaks in Fig.1(b).2)The estimation of the packet forwarding delay through each road is bad on some offline statistical data such as the average vehicle density becau it is expensive to have each vehicle get up-to-date vehicle densities from some infrastructures.As the vehicle density on each road may vary with time,which greatly influences the packet-forwarding delay,the shortest delay path that is calculated bad on the statistical data may not reflect the real optimal one. Due to the reasons,we propo SADV in this paper,which can improve the performance of data dismination under low vehicle densities in V ANETs.
IV.SADV D ESIGN
As the shortest delay path is not always available at the moment when a packet reaches an interction,we can deploy a static node at each interction to assist packet delivery. The static node can store the packet for some time until the shortest delay path becomes available.As illustrated in Fig.2, a packet is nt from A to a remote location.Once the packet is relayed from A to B,B needs to determine the next vehicle to forward.Assume that the shortest delay path to deliver the packet is northward.However,there is no vehicle within the communication range of B that can de
liver the packet along the direction.Thus,B relays the packet to the static node.The static node stores the packet for a while and forwards it to C when it pass the interction and goes toward the northward road.From thefigure,we can e that without the help of the
2448IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY,VOL.59,NO.5,JUNE 2010
奢侈的幸福
static node,the packet will be carried by B to the eastward road最好的孩子
if B does not meet C at the interction,which may lead to a much longer packet-delivery path.
We assume that each vehicle knows its location through the Global Positioning System rvice,which is already available in most new cars and will be common in the future.Each vehicle or static node is equipped with a radio that is capable of short-range wireless communication (100–250m).All vehicles and static nodes broadcast beacon messages periodically,so that they can know their neighboring vehicles and static nodes.In addition,each static node knows its own position and has a digital street map,bad on which the packet-forwarding trajectory is determined.Here,we focus on the critical issue of how to reduce the packet-delivery delay by the assistance of static nodes.Efficient routing algorithms need to be designed for both vehicles and static nodes,while care must be taken to alleviate the loads in static nodes.In the following,we prent the design of SADV ,which is a static-node-assisted adaptive data-dismination protocol for vehicular networks.It consists of three modules:static-node assisted routing (SNAR),LDU,and multipath data dismination (MPDD).A.SNAR
System Model:Given the road map of the region,we can abstract it as a directed graph G (V,E ),where V is the t of interctions,and E is the t of directed roads.Assume that each interction v i is deployed with a static node s i .Let s i and s j be the static nodes at two adjacent interctions v
i and v j .Then,the expected delay of delivering a packet from s i to s j through the vehicles on road v i v j ,which is denoted as d (s i s j ),can be calculated as
d (s i s j )=w (s i s j )+t (v i v j )
(1)
where w (s i s j )denotes the expected waiting time of a packet at s i for vehicles coming into the communication range to deliver the packet toward s j along road v i v j ,and t (v i v j )denotes the expected time taken to deliver a packet through road v i v j given that vehicles are currently available for transmitting the packet at s i along v i v j .
Suppo that vehicles enter road v i v j from v i with an average rate of λij .Then,λij =v ij ×ρij ,where v ij and ρij reprent the average vehicle velocity and the average vehicle density on the road,respectively.Therefore,the expected waiting time can be calculated as
w (s i s j )=
1λi j =1v ij ×ρij
.(2)
On the other hand,t (v i v j )is dependent on the vehicle den-sity,the vehicle velocity,the length of road,and the maximum
wireless transmission range.We u the following formula in [15]to calculate this value,where l ij denotes the length of road v i v j ,and R reprents the maximum wireless transmission ,
t (v i v j )=
α·l ij ,if 1ρij
≤R l ij v ij −β·ρij if 1
ρij
>R.(3)怠工
DING AND XIAO:SADV:STATIC-NODE-ASSISTED ADAPTIVE DATA DISSEMINATION IN VEHICULAR NETWORKS2449 within R of the static node),let s
be the nearest static node
of the packet’s destination.Then,s i can calculate the optimal
path from s i to s t bad on delay matrix d.Thus,SNAR should
deliver the packet toward the next static node along the optimal
path.This way,the packet can be delivered along the minimum
expected delay path.More protocol details are discusd in the
following.
Data Forwarding in Vehicles:SNAR operates in two modes,
that is,in-road mode and interction mode,when a packet is in
a vehicle.
Upon reaching the interction(or the vehicle is in the radio
communication range of the static node in the interction),the
SNAR stack on the vehicle works in the interction mode.As-
校园秋色
sume that the vehicle has packets with destination dst.Denote
the static node at the interction by s i.The vehiclefirst nds
a routing query to s i for destination dst.Node s i calculates
the optimal next interction,which is denoted by s j,that the
packet should be delivered to and replies to the vehicle.(As the
calculation of the optimal path in static nodes is by the shortest
path algorithm,it only takes veral milliconds tofinish the
query.)The vehicle then determines the next vehicle to deliver
好运来歌词the packet to.It will forward the packet to the vehicle that is
both moving toward s j and clost to s j.If such a vehicle exists,
四时之景不同
the packet will be delivered to the next hop.A special ca is
that the vehicle itlf is the best vehicle to further deliver the
packet;therefore,the vehicle will continue to carry the packet.
If there are no such vehicles,when the vehicle starts to leave the
interction,it will deliver the packet to s i so that the static node
can deliver the packet along the best direction when there are
vehicles available.The algorithm is illustrated in Algorithm1.
When a packet is carried by a vehicle in a road,which has not
entered the communication range of static nodes yet,the SNAR
stack on the vehicle operates in the in-road mode.Assume that
the next adjacent interction to deliver the packet is s i.We then
u geographic forwarding to greedily deliver the packet to s i,
that is,if the vehiclefinds another neighboring vehicle,which
is clor to s i,it will deliver the packet to that vehicle.
Algorithm1Packet Delivery for Vehicle Interction Mode
1:Denote the vehicle by c and the static node by s i.
2:Assume that c has packets that are destined for dst.
3:Query s i for the next interction for dst,which is denoted
by s j.
4:while c has not pasd the interction do
5:Let N(c)denote the neighbors of c that are going toward
direction s i s j(c∈N(c)).The can be vehicles already in
road s i s j,or vehicles that will turn into s i s j after passing s i.
6:if N(c)is not empty then
7:For c k∈N(c),calculate d k=(−1)p·
distance(c k,s i),where p=0if c k is in road s i s j now,
or p=1otherwi(c k has not entered the road yet).
8:Let k∗=arg min({d k}).
9:if c k∗=c then
10:Deliver the packets to c k∗.
11:return
12:end if
13:end if
14:end while
