Transcript Source - 國立政治大學資訊科學系

國立政治大學資訊科學系演講
Open Your Driving Vision
BPAB: Binary Partition Assisted Emergency Broadcast
Protocol for Vehicular Ad Hoc Networks
國立中央大學資訊工程所 吳曉光 教授
March 11, 2013
ABC News 2008: Social Networking for Cars Can Help You Avoid Traffic Jams
~ We are having cars talk to each other about traffic data.
Outline
Introduction
 Multihop Broadcast Protocols in VANET
 Binary Partition Assisted Broadcast
 Performance Evaluation
 Conclusion and Future work

New usage
IP cars
IP everywhere
IP fridge
Wireless & Multimedia Network Laboratory
異質無線多網多媒體分享與推薦平台場景圖
電信國家型計畫建置案
metadata 1
搜尋
metadata 2
….
推薦
metadata n
傳送
Alice
人際網路
WiFi
Bluetooth
Internet
WiMax
搜尋
推薦
傳送
Wireless & Multimedia Network Laboratory
Bob
Scenario of VANET safety applications
Multicasting warning messages
WLAN AP
Emergency
Event !!
WLAN AP
Car accident happen in the left
lane.
You can take exit to avoid traffic
jam.
Wireless & Multimedia Network Laboratory
Multicast the warning
message
Car accident happen !!
About 100 meters from the me.
Please prepare to change into the
right lane.
The Enabling Standard: DSRC / IEEE 802.11p
• Car-Car communications at
5.9Ghz
• Derived from 802.11a
Event data recorder (EDR)
Forward radar
• three types of channels:
Vehicle-Vehicle service,
a Vehicle-Roadside
service and a control
broadcast channel .
• Ad hoc mode; and
infrastructure mode
• 802.11p: IEEE Task Group for
Car-Car communications
Positioning system
Communication
facility
Rear radar
Display
Computing platform
CR (Cognitive Radio)

The CR idea was initially introduced by Joseph
Mitola. On average, only 2% of allocated
spectrum in the U.S. is actually in use
Wireless & Multimedia Network Laboratory
Introduction
Traffic jam
Road Accident
Car to Car communications for Safe
Driving
Vehicle type: Cadillac XLR
Curb weight: 3,547 lbs
Speed: 75 mph
Acceleration: + 20m/sec^2
Coefficient of friction: .65
Driver Attention: Yes
Etc.
Vehicle type: Cadillac XLR
Curb weight: 3,547 lbs
Speed: 65 mph
Acceleration: - 5m/sec^2
Coefficient of friction: .65
Driver Attention: Yes
Etc.
Alert Status: None
Alert Status: None
Alert Status: Inattentive Driver on Right
Alert Status: Slowing vehicle ahead
Alert Status: Passing vehicle on left
Vehicle type: Cadillac XLR
Curb weight: 3,547 lbs
Speed: 75 mph
Acceleration: + 10m/sec^2
Coefficient of friction: .65
Driver Attention: Yes
Etc.
Alert Status: Passing Vehicle on left
Vehicle type: Cadillac XLR
Curb weight: 3,547 lbs
Speed: 45 mph
Acceleration: - 20m/sec^2
Coefficient of friction: .65
Driver Attention: No
Etc.
V2V Applications (cont)
Efficient Navigation
GPS Based Navigators
Dash Express (just came to
market):
ITS (Intelligent Transportation System) Applications
 Electronic Toll Collection
 Traffic Congestion Notification
 Collision Avoidance Systems
 Driver Assistance Systems
 Freeway Management
 Parking Lot Management
Benefits of ITS
Time savings
Cost Avoidance
Enhanced Customer satisfaction
Reduced number of accidents
and fatalities
ITS Communication Paradigm
Vehicle-to-vehicle
Communication
Vehicle-to-Infrastructure
Communication
VANET (Vehicular Ad Hoc Networks)
No Infrastructure
 Self-organizing
Ad Hoc Network
 High Mobility
 Restricted movement patterns
 Predictable speed,
Predictable movement.
Video Advertisement
You are driving to Vegas
You hear of this new show on the radio
Video preview on the web (10MB)
CarTorrent: Basic Idea
Internet
Download a piece
Outside Range of Gateway
Transferring Piece of File from Gateway
Co-operative Download: Car
Torrent
Internet
Vehicle-Vehicle Communication
Exchanging Pieces of File Later
Vehicular Sensor Network
Roadside base station
Inter-vehicle
communications
Vehicle-to-roadside
communications
VSN-enabled vehicle
Sensors
Video
Chem.
Systems
Storage Proc.
Accident Scenario: storage and retrieval
•
•
Public/Private Cars (eg, busses, taxicabs, police, commuters, etc):
– Continuously collect images on the street (store data locally)
– Process the data and detect an event
– Classify the event as Meta-data (Type, Option, Loc, time,Vehicle ID)
– Distribute Metadata to neighbors probabilistically (ie, “gossip”)
Police retrieve data from public/private cars
- Sensing
- Processing
Summary
Harvesting
CRASH
Crash Summary
Reporting
Meta-data : Img, -. (10,10), V10
Why VANET
No deployment cost.
Easy introduction of technology.
Availability of cost-effective GPS and other location
services.
Government
VANET Projects
SeVeCom
Academia
PATH
Fleetnet
Network on Wheels
DRIVE-IN
CAR TALK 2000
PreDRIVE C2X
PReVENT
Automotive
industries
Safety Message in VANET
Periodic Message
 Vehicles exchange position, velocity with neighbors.
 Single-hop broadcast
Beacon
Beacon
Drivers are aware of the
potential danger (e.g.
intersection collision,
accidents ahead) before it
occurs.
Event-driven Message
 Dissemination of warning message to the following vehicles.
 Multihop Broadcast
Emergency Event
Allow drivers to react in time
Emergency
Message
(Accident, unsafe road
surface, obstacle, etc.)
Emergency
Message
Specific area-of- interest
Emergency
Message
Outline
Introduction
 Multihop Broadcast Protocols in VANET
 Binary Partition Assisted Broadcast
 Performance Evaluation
 Conclusion and Future work

Multihop Broadcast Protocols in VANET
Requirements for Safety Message Dissemination
 Low communication delay
 High Message Dissemination Speed
 Reliable Packet Delivery
 Bandwidth Efficiency
Challenges
 Choosing the right forwarder
Allocate minimum waiting time
Hidden Terminal Problem
Urban Multihop Broadcast (UMB)
S0
S1
RTB DATA
RTB
Select the furthest node
as the forwarder.
0
9
CTB
S9
Black burst
duration
(time slots)
40m
…………
Source
CTB
CTB
ACK
4m CTB
Black burst
duration
(time slots)
0
1
9
Drawbacks
RTB/CTB handshake is
used to avoid hidden
terminal problem.
 Relay node is assigned the longest waiting time.
 Wastage of time in collision resolution phase.
Control Packet Overhead.
Nodes randomly select waiting
time from a back off window
allocated to their segment.
Smart Broadcast (SB)
CTB
40m
RTB
…………
DATA
Source
S10
W10= {45,46,47,48,49}
RTB/CTB handshake is used to avoid
hidden terminal problem.
S2
W2= {5,6,7,8,9}
S1
W1= {0,1,2,3,4}
Back off times increases
towards the sender
Smart Broadcast
Source
Relay Node
C
A
D
E
Range of C
Range of D
F
B
Range of A
Range of B
Drawback
Longer waiting time at irregular topologies.
Range of E
Outline
Introduction
 Multihop Broadcast Protocols in VANET
 Binary Partition Assisted Broadcast
 Performance Evaluation
 Conclusion and Future work

Binary Partition Assisted Broadcast
Objective
 Reduce Broadcast latency.
 Maximize message progress
 Efficient usage of network bandwidth.
Features
 Binary partitions are applied iteratively.
A segment is divided into two equal sub segments.
Potential segment is selected by black-burst approach.
It becomes the input segment for next iteration.
 N binary partitions yields a furthest segment.
The width of furthest segment is R/2N.
Finally, back off time is chosen from {0,1,…cw-1} .
The parameter ‘cw’ is a small value.
Binary Partition Assisted Broadcast
Two nodes contend using
back off window {0,1, 2..cw}
CTB
RTB
…....
DATA
Source
Transmission range
Iteration
Segment Width
1
2
3
R/2
N
R/2N
R/4
R/8
Elected relay node
Forward Node selection
procedure
Black Burst
Detection
R: Transmission Range
Contention
Winner
Black Burst
Detection
Black Burst
Black Burst
Transmission Black Burst
Detection
Random
Transmission
Contention
Exit
Contention
Source
Exit
Contention
Exit
Black Burst
Contention
Transmission
Exit
Contention
R/2
Iteration 1 : Time Slot 1
Iteration 2 : Time Slot 2
Iteration 3 : Time Slot 3
Black burst is transmitted
for one time slot duration
R/4
R/8
Time slots spent per hop= N + t
3
cw=6
Slot chosen from {1,2,..5}
Source might lose CTB packet
due to varying wireless
channel conditions.
Reliability Measures
RTB
lost
CTB
Relay node
selection ends
Source
Solution
Source waits a time period (slots) = N + cw,
Where N + cw -1 = Maximum possible waiting time, before a CTB
could be sent.
One extra time slot to determine the start of CTB reception.
Reliability Measures
Implicit Acknowledgement
Source overhears RTB,
thus DATA delivery is
guaranteed.
RTB
DATA
Relay node
selection ends
CTB
RTB
Source
PROBLEMS
Relay node
selection ends
RTB
DATA
Relay node
selection ends
CTB
RTB
RTB
DATA
Source
CTB
lost
Source
Case 1
Case 2
Solution
Source waits for a certain time
period and then retransmits RTB to
select a potential relay node.
Outline
Introduction
 Multihop Broadcast Protocols in VANET
 Binary Partition Assisted Broadcast
 Performance Evaluation
 Conclusion and Future work

Performance Evaluation
Simulation Set up
 Vehicle Density : 150-650
 Vehicle Speed : 20m/s – 40m/s
 Transmission Range : 400m
 Packet Size :100 bytes
 MAC Protocol : IEEE 802.11b
 Protocols compared : SB and UMB
NS-2 simulator.
Modeled Scenario
Straight Highway
Regular Topology
Irregular Topology
Normal flow of traffic
Occurs when nodes move in close proximity of each
other due to fog or ongoing road work at some intervals.
Performance Metrics
 MAC Layer slots
 Total number of slots expended for the message
dissemination.
 One hop message progress
 Additional coverage provided by the relay node.
 Control Overhead
Total number of RTB/CTB handshakes required during
the message dissemination.
Total number of MAC layer Slots
500
No. of Slots
400
BPAB
SB
UMB
300
200
100
0
150
250
350
450
Node Density
Regular Topology
550
650
One Hop Message Progress
Message Progress (%)
100
BPAB
SB
95
UMB
90
85
80
150
250
350
450
Node Density
Regular Topology
550
650
Control Overhead
No. of RTB/CTB Exchange
40
BPAB
SB
35
UMB
30
25
20
15
150
250
350
450
Node Density
Regular Topology
550
650
Total number of MAC layer Slots
BPAB
SB
UMB
1000
No of slots
800
600
400
200
0
150
250
350
450
Node Density
Irregular Topology
550
650
One Hop Message Progress
Msg Progress
90
BPAB
SB
UMB
80
70
60
50
150
250
350
450
Node Density
Irregular Topology
550
650
Control Overhead
No. of RTB/CTB Exchange
50
40
30
20
BPAB
SB
UMB
10
150
250
350
450
Node Density
Irregular Topology
550
650
Conclusion
Improves broadcast efficiency by reducing delay.
Exhibits constant behavior in varying node densities.
 Minimizes bandwidth consumption by using few
number of control messages.
 Offers high message progress.
Future Work
 Inclusion of multiple emergency message
sources.
 Adaptation of existing scheme to more complex
road scenarios such as City environments.
 Analytical determination of optimal value of N.
Thanks a lot…