Transcript Qos-Aware Data Dissemination in V2V Networks

An Architecture Study of AdHoc Vehicle Networks
Richard Fujimoto
Randall Guensler
Hao Wu
Michael Hunter
Computational Science & Engineering
Civil and Environmental Engineering
College of Computing
College of Engineering
Georgia Institute of Technology
The Costs of Mobility



Safety: 6 Million crashes, 41,000 fatalities in U.S.
per year ($150 Billion)
Congestion: 3.5 B hours delay, 5.7 B gal. wasted
fuel per year in U.S. ($65 Billion)
Pollution: > 50% hazardous air pollutants in U.S.,
up to 90% of the carbon monoxide in urban air
> 3M
1M - 3M
0.5 - 1M
< 0.5 Million

Disproportionate increase
in car ownership relative
to population growth in
China, India
Source: 2005 Annual Urban Mobility Report
(http://mobility.tamu.edu)
Texas Natural Resource Conservation Commission
(http://www.tnrcc.state.tx.us/air)
Intelligent Transportation Systems
www.georgia-navigator.com

ITS deployments: Traffic Management Centers (TMC)
–
–

Roadside cameras, sensors, communicate to TMC via private network
Disseminate information (web, road signs), dispatch emergency vehicles
Infrastructure heavy
–
–
–
Expensive to deploy and maintain; limited coverage area
Limited traveler information
Limited ability to customize services for individual travelers
Current Trends
Smart Vehicles




On-board GPS, digital maps
Vehicle, environment sensors
Significant computation,
storage, communication
capability
Not power constrained
Dedicated Short Range
Communications (DSRC)






5.850-5.925 GHz
V2V, V2R communication
802.11p protocol
7 channels, dedicated safety channel
6- 27 Mbps
Up to 1000 m range
U.S. DOT Vehicle Infrastructure
Integration (VII) Initiative



Public/private partnership
“Establishment of vehicle-to-vehicle and
vehicle-to-roadside communication
capability nationwide”
Improve safety, reduce congestion
Mobile Distributed Computing
Systems on the Road
Roadside
BaseStation
Vehicle-to-vehicle
communication
Roadside-to-vehicle
communication
Applications

Collision
warning/avoidance
–
–





Unseen vehicles
Approaching
congestions/hazards
Traffic/road monitoring
Emergency vehicle
warning, signal
warning
Internet Access
Traveler & Tourist
Assistance
Entertainment
Objectives
Motivating question: Can networks composed of smart
vehicles be used to collect and disseminate information
in urban / rural transportation systems?
• Augment or replace infrastructure deployments
Challenges
• Create realistic models for mobility by developing,
populating, and calibrate simulations specific to data
for the Atlanta metropolitan area
• Develop simulation modeling tools for traffic, vehicleto-vehicle, and vehicle-to-roadside communications to
support the development and evaluation of future
generation intelligent transportation systems
• Evaluate the performance limits of multi-hop vehicleto-vehicle communication for realistic test conditions
Spatial Propagation Problem
Message
Spatial Propagation Problem:
How fast can information propagate with vehicle
forwarding?
Focus on V2V ad hoc networks (802.11) in order to
understand the limitations of message forwarding
Observations
 One dimensional partitioned network
 Vehicle movement helps propagate information
Vehicle Ad Hoc Networks
H
Time t0
Time t1
Time t2
Informed Vehicle
Uninformed Vehicle
Partition


Partitioned Network
Forward mode


Message forwarding within a
partition
Catch-up mode

Distance
Time t3
Vehicle movement allows
message propagation
between partitions
Cyclic Process
Forward Mode
Catch-up Mode
Time
Time-space Trajectory
Analytic Models
H. Wu, R. M. Fujimoto, G. Riley, “Analytical Models for Information Propagation in Vehicle-to-Vehicle
Networks,” IEEE Vehicular Technology Conference, September 2004.


A single road with one way traffic
Vehicle movement follows undisturbed traffic model
Distance for 100s (m)
16000
Sparse Netow ork Model
Dense Netw ork Model
Simulation
14000
12000
10000
8000
6000
4000
2000
1.25
1.1
0.95
0.8
0.65
0.5
0.35
0.2
0.05
0
Flow Rate (vehicles/s)

Sparse network model -- Small partition size
–
–

Information propagation principally relies on vehicle movement.
Message propagation speed approaches maximum vehicle speed.
Dense network model -- Large partition size
–
–
Independent cycles
Renewal reward process
 Reward: message propagation distance during each cycle
Integrated Distributed Simulations
CORSIM



Microscopic
traffic
simulation
Vehicle-tovehicle and
vehicle-toinfrastructure
wireless
communication
Distributed
simulation over
LANs and
WANs
QualNet
Traffic Simulator
Comm. Simulator
Run Time Infrastructure Software
Federation
management
Pub/Sub
Communication
LAN/Internet
Synchronization
(Time Management)
Traffic Simulation Model
(Guensler, Hunter, et al.)
• One-foot resolution United States Geological Survey
(USGS) orthoimagery aerial photos used to code lanes,
turn bay configurations, and turn bay lengths for each
intersection
• Traffic volumes, signal control plans, geometric data,
speed limits, etc., obtained from local transportation
agencies
Traffic Corridor Study Area






I-75 and surrounding
arterials in NW Atlanta
189 nodes (117 arterial,
72 freeway)
45 signalized nodes
365 one-way links (295
arterial, 70 freeway)
101.4 arterial miles
16.3 freeway miles (13.6
mainline, 2.7 ramp)
Model Calibration & Validation
H. Wu, J. Lee, M. Hunter, R. M. Fujimoto, R. L. Guensler, J. Ko, “Simulated Vehicle-to-Vehicle Message
Propagation Efficiency on Atlanta’s I-75 Corridor,” Journal of the Transportation Research Board, 2005.
Speed(MPH)
Comparison of Measured and Simulated Vehicle Speeds
70
Measured
60
Simulated
50
40
30
20
10

R
os
ew
ry
el
lR
R
d.
d.
r.
Fe
r
Pa
ce
s
or
th
sid
e
ar
a
t.
P
M
D
n
d.
R
M
il l
Bl
vd
.
oo
re
N
W
Arterials
Anomalous (simulated) delays observed at some locations
–

M
d.
ar
ie
t ta
R
M
Fe
rry
ef
oo
rs
ol
l ie
rR
d.
D
C
I-7
5
So
ha
t ta
ut
h
ch
oo
ch
ee
Av
e
C
I-7
5
N
or
th
0
Field surveys completed at six intersections to calibrate model
Validation using instrumented vehicle fleet collecting second-bysecond speed and acceleration data
–
–
–
GPS data from 7 AM to 8 AM peak used
591 weekday highway trips (Feb.-May 2003)
601 weekday highway trips (July-Sept. 2003)
Mobility-Centric Data Dissemination
for Vehicle Networks (MDDV)
H. Wu, R. M. Fujimoto, R. Guensler, M. Hunter, “MDDV: Mobility-Centric Data Dissemination Algorithm for
Vehicular Networks,” ACM Workshop on Vehicular Ad Hoc Networks (VANET), October 2004.

No end-to-end connection assumption
–
–
–



Opportunistic forwarding [Fall, SIGCOMM 2003]
Trajectory-based forwarding [Niculescu & Nath, Mobicom’03]
Geographic forwarding [Mauve, IEEE Networks 15 (6)]
Compute trajectory to destination region
Group forwarding: Set of vehicles holding message “closest” to
destination region actively forward message toward destination
Group membership
–
–
–
Vehicle stores last known location/time of message head candidate;
forwards information with message
Join group if (1) moving toward destination along trajectory and (2) reach
estimated head location (or closer) less than Tl time units after head
Leave group if (1) leave trajectory or (2) receives same message
indicating head is closer to the destination
Propagation Delay (simulation)
Delay (s)
H. Wu, J. Lee, M. Hunter, R. M. Fujimoto, R. L. Guensler, J. Ko, “Simulated Vehicle-to-Vehicle Message
Propagation Efficiency on Atlanta’s I-75 Corridor,” Journal of the Transportation Research Board, 2005.
End-to-End Propagation Delay
120
EVENING PEAK
100
80
60
40
20
0
0.05



0.1
0.15
0.2
0.25
Penetration
Ratio
Penet r at i o n R at i o
Delay to propagate message 6 miles southbound on I-75
Relatively heavy traffic conditions
Penetration ratio: fraction of instrumented vehicles
End-to-End Delay Distribution




Delay to propagate
message 6 miles along
I-75 (southbound)
Heavy (evening peak)
and light (nighttime)
traffic
Penetration ratio:
fraction of instrumented
vehicles
Significant fraction of
messages experience a
large delay
Delivery Ratio
Mobility-centric Data Dissemintation for
Vehicle Networks (MDDV)

Delivery Rat io
1.2

1
0.8
0.6
0.4

0.2
0
0.1
0.2
0.3
0.4
0.5
Delay (s)
P e ne t r a t i on Ra t i o
500
Avg Delay
M ax Delay
M in Delay

0. 5

400
300
200
100
0
0. 1
0. 2
0. 3
0. 4
Penetration Ratio
P e ne t r a t i on R a t i o
MDDV: opportunistic
forwarding algorithm
Morning rush hour
traffic
Propagate
information to
destination 4 miles
away
Delivery ratio: fraction
delivered before
expiration time (480
seconds)
Large variation in
delay observed
Field Experiments: Goals




Characterize communication performance in
a realistic vehicular environment
Identify factors affecting communication
Lay the groundwork of realizing
communication services
Demonstrate and assess the benefits of
multi-hop forwarding
When the Rubber Meets the Road
H. Wu, M. Palekar, R. M. Fujimoto, R. Guensler, M. Hunter, J. Lee, J. Ko, “An Empirical Study of Short Range
Communications for Vehicles,” ACM Workshop on Vehicular Ad Hoc Networks (VANET), September 2005.

In-vehicle systems
–
–
–
–


Roadside station using the
same equipment
Software
–
–


Iperf w/ GPS readings
Data forwarding module
Location
–

Laptop
GPS receiver
802.11b wireless card
External antenna
I-75 in northwest Atlanta,
between exits 250 and 255
Un-congested traffic
Clear weather
Vehicle-to-Roadside (V2R)
Communication
Exit 255
-2440m
-2270m
-1400m
Exit 254
-700m
Peachtree Battle Bridge
0
600m
Trees
Exit 252B
N
S
Exit 252A
1000m
2500m
3000m
3370m
Exit 250
4250m
4700m
4570m
V2R Performance
Success Ratio
-
Percentage of packet transmissions received by the receiver
North
South
Northbound
Southbound
Success Ratio
View facing north
Bridge
100%
90%
80%
70%
60%
50%
40%
30%
20%
10%
0%
-500
0
-1500
-1000
View facing south
500
1000
Trees
Peachtree Battle
Trees
Exit 254
north
1500
2000
Distance (m)
Vehicle-to-Vehicle (V2V)
Communication
Exit 255
-2440m
-2270m
-1400m
Exit 254
-700m
Peachtree Battle Bridge
0
600m
Trees
Exit 252B
N
S
Exit 252A
1000m
2500m
3000m
3370m
Exit 250
4250m
4700m
4570m
V2V Performance (Southbound)
North
v2v Distance = 150m
v2v Distance = 300m
Bridge South
100%
80%
Success Ratio
Exit 255
-2440m
-2270m
60%
-1400m
40%
20%
-700m
0%
-3000
-2000
-1000
0
1000
2000
3000
4000
0
5000
Exit 254
Peachtree Battle Bridge
Sender Location (m )
600m
Trees
v2v Distance = 400m
v2v Distance = 700m
Success Ration
North
-3000
-2000
Bridge
100%
90%
80%
70%
60%
50%
40%
30%
20%
10%
0%
-1000
0
South
Exit 252B
N
S
1000m
Exit 252A
2500m
3000m
Exit 250
3370m
4250m 4700m
4570m
1000
2000
3000
4000
5000
Sender Location (m)
Multi-hop Communication
Exit 255
-2440m
-2270m
-1400m
Exit 254
-700m
Peachtree Battle Bridge
0
600m
Trees
Exit 252B
N
S
Exit 252A
1000m
2500m
3000m
3370m
Exit 250
4250m
4700m
4570m
Performance Comparison
Single hop, northbound
Single hop, southbound
Tw o hops, southbound, v2v distance = 340m
Tw o hops, southbound, v2v distance = 180m
Tw o hops, northbound, v2v distance = 320m
Tw o hops, northbound, v2v distance = 460m
80%
60%
40%
20%
-1200
-700
0%
-200
Success Ratio
100%
300
800
1300
1800
Distance (m )
Summary

Mobile distributed computing systems on the road are coming
–
–
–

Simulation methodology is essential to design vehicle networks,
e.g., to determine a necessary penetration ratio for effective
communication
–
–

Safety likely to be the initial primary application
System monitoring also early application
Enable wide variety of commercial applications
Realistic evaluation of vehicular networks requires careful
consideration of mobility
Federating simulation models can play a key role
Vehicle-to-vehicle communication can be used to propagate
information for applications that can tolerate some data loss
and/or unpredictable delays
–
–
V2V communication provides a means to supplement infrastructurebased communications
Must weigh benefits against implementation complexity
Future Directions

Architectures of the future will likely include a mix
of technologies
–
–

WWAN, WLAN (e.g., DSRC), V2V
Roadside computing stations, Internet gateways
Transition from data draught to data flood will
create new technical challenges
–
–
–
Management of bandwidth
Management of computing resources; vehicle grids
Data challenges: cleaning, aggregating, mining
Wireless Infrastructure
Technologies

Wireless Technologies (in order of decreasing coverage)
–
Wireless Wide Area Networks (WWAN)



–
Wireless Metro Area Networks (WMAN)

–


IEEE802.11x (T-mobile hop spots)
High bandwidth: 802.11b provides 11 Mbps, 802.11 a/g offers 54 Mbps
Low coverage (250m)
Wireless Personal Area Networks (WPAN)


Fixed broadband wireless link (WiMAX -- IEEE 802.16)
Wireless Local Area Networks (WLAN)

–
Cellular networks (2nd Generation, 2.5G, 3G, 4G)
High coverage (up to 20 km)
Low bandwidth: Verizon BroadbandAccess provides up to 2 Mbps
upstream, the Cingular Edge provides up to 170 Kbps upstream
Bluetooth
Larger coverage -> Increased cost, low bandwidth
Network Architecture Options
Backbone
WWAN BS
WLAN AP


WWAN last hop: broad coverage, limited capacity
WLAN access points to improve capacity
–
–

WLAN AP
In addition to, or rather than WWAN
Many access points vs. coverage tradeoff
Add WLAN multihop (vehicle-to-vehicle) communication
–
–
Extend WLAN coverage, reduce number of access points
Requires presence of vehicles
Required WWAN Capacity
vehicle data rate = 16Kbps (a modest value)
7 WLAN access points (for hybrid architectures)
(Kbps)
Required WWAN Capacity
WWAN
WWAN
WWAN
WWAN
35000
30000
25000
last-hop
last-hop + WLAN last-hop
last-hop + 2-hop WLAN
last-hop + 3-hop WLAN
28.8 Mbps
20000
15000
10000
5.6 Mbps
5000
0
0
Not Linear


0.2
0.4
0.6
0.8
1
Penetration Ratio
WWAN does not scale well.
A hybrid architecture can increase the system capacity
and reduce the WWAN data traffic load.
Required WLAN Access Points
to Provide Sufficient Capacity
vehicle data rate = 16 Kbps, road length = 11,000 m, number of
instrumented vehicles = 1800 * penetration ratio, aggregated
WWAN data rate = 6 Mbps
WLAN last-hop
WWAN last-hop + WLAN last-hop
WWAN last-hop + 2-hop WLAN
WWAN last-hop + 3-hop WLAN
# of Access Points
25
20
15
10
5
0
0
0.2
0.4
0.6
0.8
1
Penetration Ratio



Fixed number required for WLAN last-hop architecture
Hybrid architecture can greatly reduce the number
Multi-hop forwarding can reduce number further
WLAN Coverage Range
Coverage range: expected length of road segment within which
vehicles can access a WLAN access point using at most m hops
hops = 1
analysis, hop limit = 2
analysis, hop limit = 3
simulation, hop limit = 2
simulation, hop limit = 3
Normalized WLAN Coverage
3.5
3
2.5
2
1.5
1
0.5
0
0
0.025


0.2
0.4
0.6
0.8
1
Penetration Ratio
Instrumented vehicles will likely be sufficiently dense
Further coverage increase minor when instrumented vehicle
density reaches a saturation value (penetration ratio 0.3 above)
Design Implication

Vehicular network design requires:
–
–

Careful assessment of cost / performance tradeoffs
Addressing changing vehicle traffic conditions
Multi-hop forwarding
–
–
–
–
Pro: extend coverage -> reduce number of access points > reduce cost
Con: reduced channel capacity, additional system
complexity (routing, billing & security)
Questionable except in places with cost or other
constrains
Voluntary cooperation is beneficial in improving
communication performance
Design Implication (Cont.)

Continuous connectivity
–
–
–

Intermittent connectivity
–
–
–

WWAN: does not scale well.
WLAN last-hop: simple, easy deployment, provide high
throughput, require a large number of access points
WWAN + WLAN: increase system capacity
WLAN-based solution
Whether to allow multi-hop forwarding is governed by a
tradeoff between cost and system complexity.
Connectivity probability in every location can be estimated
using our models.
Deal with vehicle traffic dynamics
–
–
Overprovision (for hard-to-predict variations)
Adaptation (for predictable variations)
References
H. Wu, J. Lee, M. Hunter, R. M. Fujimoto, R. L. Guensler, J. Ko, “Simulated Vehicle-to-Vehicle Message
Propagation Efficiency on Atlanta’s I-75 Corridor,” Journal of the Transportation Research Board, 2005.
H. Wu, R. M. Fujimoto, R. Guensler, M. Hunter, “An Architecture Study of Infrastructure-Based Vehicular
Networks,” Eighth ACM/IEEE International Symposium on Modeling, Analysis, and Simulation of Wireless
and Mobile Systems,” October 2005.
R. M. Fujimoto, H. Wu, R. Guensler, M. Hunter, “Evaluating Vehicular Networks: Analysis, Simulation, and
Field Experiments,” Cooperative Research in Science and Technology (COST) Symposium on Modeling and
Simulation in Telecommunications, September 2005.
H. Wu, M. Palekar, R. M. Fujimoto, R. Guensler, M. Hunter, J. Lee, J. Ko, “An Empirical Study of Short Range
Communications for Vehicles,” ACM Workshop on Vehicular Ad Hoc Networks (VANET), September 2005.
Lee, J., M. Hunter, J. Ko, R. Guensler, and H.K. Kim, "Large-Scale Microscopic Simulation Model Development
Utilizing Macroscopic Travel Demand Model Data", Proceedings of the 6th Annual Conference of the
Canadian Society of Civil Engineers, Toronto, Ontario, Canada, June 2005.
H. Wu, M. Palekar, R. M. Fujimoto, J. Lee, J. Ko, R. Guensler, M. Hunter, “Vehicular Networks in Urban
Transportation Systems,” National Conference on Digital Government Research, May 2005
H. Wu, R. M. Fujimoto, R. Guensler, M. Hunter, “MDDV: Mobility-Centric Data Dissemination Algorithm for
Vehicular Networks,” ACM Workshop on Vehicular Ad Hoc Networks (VANET), October 2004.
H. Wu, R. M. Fujimoto, G. Riley, “Analytical Models for Information Propagation in Vehicle-to-Vehicle
Networks,” IEEE Vehicular Technology Conference, September 2004.
B. Fitzgibbons, R. M. Fujimoto, R. Guensler, M. Hunter, A. Park, H. Wu, “Simulation-Based Operations Planning
for Regional Transportation Systems,” National Conference on Digital Government Research, pp. 175-176,
May 2004.
B. Fitzgibbons, R. M. Fujimoto, R. Guensler, M. Hunter, A. Park, H. Wu, “Distributed Simulation Testbed for
Intelligent Transportation System Design and Analysis,” National Conference on Digital Government
Research, pp. 308-309, May 2004.