Geographic Routing in Vehicular
Ad Hoc Urban Networks
Kevin C. Lee
Computer Science Department
University of California, Los Angeles
Advisor: Dr. Mario Gerla
1
Motivation for VANET
Safety/Traffic applications
Accident notification
Road hazard alert
Wide range of possible applications:
Content applications (CarTorrent)
Weather info, restaurant locations
Ad download, music download, Infotainment
Peer-to-peer citizen surveillance
Forensic accident or crime site investigations
Terrorist alert
Multi-hop routing scheme necessary
2
Possible Routing Solutions VANET
Characteristics
• Rapidly and
Take care of
dynamically
complete
changing network
disconnectivity
topologies
• Confined
mobility by roads
Not too scalable • Disconnectivity
typical
Long route establishment;
susceptible to route breaks Take care of
intermittent
disconnectivity
Take care of
low S/N ratio
Routing inefficiency; low PDR
Can’t avoid void; 3
open path all the time!
Anatomy of GPSR
Greedy mode
Nodes learn 1-hop
neighbors’ positions
from beaconing
A node forwards packets
to its neighbor closest to
D
Greedy traversal not
always possible!
x is a local maximum to
D; 4
w and y are far from D
Anatomy of GPSR (2)
Recovery mode y z
Face traversal
By right-hand rule
Face change x
D
F4
F3
F2
F1
Walking sequence:
F1 -> F2 -> F3 -> F4
X
5
Planarization
Face traversal requires
planar graph: cross edges
result in routing loops
GG and RNG
planarization algorithms
Their faults
Unit-disk assumption
High hop count
Accurate localization
6
Limitations of Geographic Routing in VANET
Planarization overhead
Routing inefficiency due to
Planarization
New paradigm still generates inefficiency
Missing junctions cause routing loops!
Low throughput due to
Signal interference in urban environments
Routing without regard of context information
7
My Contributions
No planarization
Roads naturally formed a “planar” graph
No routing inefficiency
Junction look-ahead
Remove routing loops from missing junction
Improve route throughput
Opportunistic forwarding due to channel fading from
interference
Density helps route away the void to minimize recovery
Combine delay tolerant network (DTN) to handle
end-to-end disconnectivity
8
Outline of My Talk
TO-GO: Route on planar graph formed by roads
Eliminate inefficiency by junction-lookahead
Opportunistic forwarding to improve packet delivery
GeoCross: Route in spite of routing loops
LOUVRE: Peer-to-peer density estimation to avoid void
and backtracking
GeoDTN+Nav: Context info to provide threshold to
switch to DTN
Ongoing and Future work:
Vehicular-Airborne network for emergency
responses to handle complete ground disconnectivity
VANET applications
9
State of the Art in VANET Georouting: GPCR
Eliminate planarization by routing
along roads
Roads naturally formed a “planar”
graph
Greedily forward until
junctions so as not to miss
best route to the destination
Drawback: Inefficiency in
routing as packets always
stop @ junction nodes
10
GPCR Inefficiency
GPCR Routing Bypass Junction
Bypass Junction
Greedy Mode Perimeter Mode Greedy Mode
Perimeter Mode
Total Hops: 16 Total Hops: 12
11
(+25%)
My Solution: Junction Look-ahead
Recovery mode
DB > AD => S to J
DB < AD => S to B
Greedy mode
If B exists, Forward directly
forward to J to A
Road 1 12
instead
Opportunistic Forwarding Motivation
Forward to node making biggest progress
Drawback: Furthest node often fails to
receive because of high error rate
Low signal. Packet drop!
13
TO-GO Set Construction
Node forwards to a set of nodes
Construct a set between the current node
and the target node
Nodes in a set can hear each other and
contend the channel
Node closest to the destination wins the
contention and is chosen to be the next
forwarding node (priority scheduling)
Equivalent to finding a clique, NP-hard!
14
Heuristic for TO-GO Set Construction
Requires two-hop neighbors and Bloom filter (ref.
paper)
O(n2), where n is number of C’s neighbors
From remaining, C picks its neighbor M that has most
Pick C’s neighbors that can hear C
neighbors; add to the set if the rest of neighbors in C are
& the target node
neighbors with M
TO-GO Priority Scheduling
Nodes contend based on timer,
dist (receiving node, target node)
T =C×
dist (sending node, target node)
Packet duplication possible because of
Nodes’ proximity => Similar T, AND
Time to suppress > Time T goes off
Impose further constraint in set selection:
T N − T N < δ δ is the minimum time interval
k i
for suppression, for all nodes Ni
in FS 16
TO-GO Evaluation: Set up
Qualnet 3.95
1800m x 300m
CBR rate: 1460 bytes/sec
VanetMobisim, vehicular traffic generator
Avg. vehicle speed, 25 miles/hour
Inter-road blocking model
TX range 250m
Number of nodes 75 to 150
20 runs, 95% confidence interval
17
TO-GO Evaluation: Error-Free vs. Error-Prone
1 1
0.8 0.8
PDR (%)
0.6 0.6
PDR (%)
GPSR
GpsrJ+
0.4 GPCR 0.4
TO-GO
GpsrJ+
0.2 0.2
TO-GO
0
0
0 1 2 4 6 8 10
50 75 100 125 150
Standard Deviation
Node Density
GPCR, GpsrJ+, TO-GO similar in PDR, GPSR always falls
behind
@ σ = 10, TO-GO’s PDR remains @ 98% but GpsrJ+ @ 58%
18
Outline of My Talk
TO-GO: Route on planar graph formed by roads
Eliminate inefficiency by junction-lookahead
Opportunistic forwarding to improve packet delivery
GeoCross: Route in spite of routing loops
LOUVRE: Peer-to-peer density estimation to avoid void
and backtracking
GeoDTN+Nav: Context info to provide threshold to
switch to DTN
Ongoing and Future work:
Vehicular-Airborne network for emergency reponses
to handle complete ground disconnectivity
VANET applications
19
GeoCross Overview
Problem of cross links still exist without
planarization! => mainly empty junctions!
Cross links cause routing loops
20
Routing loop!!
Cross Link Detection Protocol
(CLDP) to Cross Link Problem
Algorithm:
Probe
Record
Analyze
Notify
Disadvantages: Notify A
Extra control message
Proactive scheme not suitable for high mobility
Not necessary to remove all such links
Long convergence time
21
GeoCross Approach
Removes cross links only when necessary
Basic operations:
Piggyback roads and junctions as packet loops
back
Determine the presence of cross links
Continue forwarding in existing loop
Route around the offending cross link
No additional control messages
Dynamic loop detection suitable to VANET
22
GeoCross Example
S, R1, [R1R2], R2, B, R3, C, R4, D, R5, [R5R6], R6, E,
R7, F, R8, B => No cross link, continue forwarding
Can’t forward
b/c UR: [R5R6]
S, R1, [R1R2], R2, B, R3, C, R4,
D, R5, [R5R6],
UR: R6, E, R7,
[R5R6], F, R8,
continue
B, R2, [R2R1], R1, Sloop
existing
23
Packet reaches destination
GeoCross Evaluation
Compare GPSR, GPCR, GeoCross, Optimal Flooding
Optimal flooding provides benchmark
Snapshot of the trace of 100 nodes
100 runs
10 random src-dest pairs/run
GPCR and GeoCross
PDR minimal diff =>
No cross links GeoCross
Cross links removed GPCR/GPSR
improve PDR
24
GeoCross Summary
Non-planarity still exists with graph formed
by roads because of missing junction nodes
GeoCross, a lightweight, event-driven
geographic routing protocol that removes
cross links dynamically on a need basis to
avoid loops
25
Outline of My Talk
TO-GO: Route on planar graph formed by roads
Eliminate inefficiency by junction-lookahead
Opportunistic forwarding to improve packet delivery
GeoCross: Route in spite of routing loops
LOUVRE: Peer-to-peer density estimation to avoid void
and backtracking
GeoDTN+Nav: Context info to provide threshold to
switch to DTN
Ongoing and Future work:
Vehicular-Airborne network for emergency
responses to handle complete ground disconnectivity
VANET applications
26
LOUVRE Motivation
Recovery mode often expensive;
backtracking takes too many steps, but
Low communication density on D
road segments not detectable!
?
End-to-End route optimization Road 1
impossible! S
Two challenges for urban geo-routing
1. Intra-road communication density estimation
2. Global junction routing
27
LOUVRE Routing
Density Estimation Accuracy
decreases
Peer to Peer Computes
and TX
density
Finite number of road densities
(scalability) density
Density gets more accurate Records
expires
with proximity to the road Road A # unique
Neighbors
(freshness)
Global-junction routing
Overlay nodes: Road junctions
Overlay links: Road segment
between junctions
Proactive Dijkstra shortest path
on the overlay
Geographic routing on the
underlay
28
LOUVRE Operation
Proactive overlay routes creation
Avoids road element with local maxima!
Grid-limited overlay topology
Optimal route for src-dest on the same grid
Optimal overlay gateway node to reach nodes
on neighboring grids
3 3 3
0 3
0 0
0 5 5
3
Density Overlay
> Thresh = 3 routes
s 2
s 3 3
s
29
LOUVRE Example
For S to reach D, roads 5, 2, 3, 8, and 11 are followed
Conventional geographic routing fails when greedily delivering
through road 4 due to the lack of relays after road 4
The dotted arrows show LOUVRE routing from S in grid 1 to D’ in
grid 2 30
LOUVRE Evaluation
1000m x 1000m
Washington D.C. map
100 nodes, 20% to 50%
mobility
10 simulation runs of
1460-byte CBR traffic
from 50s to 300s
Measurement of PDR & Hop Count with
95% conf. int.
31
LOUVRE
PDR
Evaluation Hop Count
1.2 30
1 25
0.8 20
GPSR GPSR
0.6 15
GPCR GPCR
0.4 10
LOUVRE LOUVRE
0.2 5
0 0
20% 30% 40% 50% 20% 30% 40% 50%
LOUVRE has global vision of density
distribution and local maxima => highest PDR
Hop count a bit higher than GPCR due to
delivery of unsuccessful packets by LOUVRE
32
LOUVRE Future Work
Current P2P density estimation scheme too
expensive! 1 … … …
9 … … …
… 4 … …
… 3 … … 4 1
… …… …
… …
… …
3 … … …
… … 6 … … …… …. …
… 9 … … 4 … …
… … ….5 7
… … 6 … 2 … … 11 4
…
5 2
… … …. 7 … … …. …
Current P2P density estimate scheme does not
take non-uniform road density into account in
inferring connectivity
33
LOUVRE Future Work (contd.)
Histogram-based scheme: each car has a
histogram of cars in each segment
What is the appropriate segment size (SS) for
accuracy and fast convergence?
How frequent is false negative due to no cars in
the last segment < SS?
1 2 0 0
1 0 0 0 0 2 0 0
Cars on each seg. 1 2 1 0
34
Outline of My Talk
TO-GO: Route on planar graph formed by roads
Eliminate inefficiency by junction-lookahead
Opportunistic forwarding to improve packet delivery
GeoCross: Route in spite of routing loops
LOUVRE: Peer-to-peer density estimation to avoid void
and backtracking
GeoDTN+Nav: Context info to provide threshold to
switch to DTN
Ongoing and Future work:
Vehicular-Airborne network for emergency
responses to handle complete ground disconnectivity
VANET applications
35
GeoDTN+Nav Goal
Aim to improve packet delivery in a disconnected
VANET
Inspired by:
DTN
Not all applications require real-time delivery
LER (Last Encounter Routing), 7DS, ZebraNet, …
Mobility helps data dissemination
Basic idea:
Exploit vehicles’ mobility
Use DTN mechanism to store, carry and forward
Deliver packets between disconnected networks
36
GeoDTN+Nav Contributions
Virtual Navigation Interface
(VNI) is installed on every
vehicle
A lightweight wrapper interface
interacts with data sources
Provide Nav Info (Dest, Path,
Direction) and Confidence
3 modes of operations: Greedy, Recovery, and
DTN
Use VNI to determine when to switch and who to
forward in DTN mode
Use context information along with hop count to
determine whether to switch to DTN
37
GeoDTN+Nav Evaluation
1500m x
Normalized PDR (w/ Optimal)
Optimal
1.4 GPSR/GPCR(RAND)
GeoDTN+NAV(RAND) 4000m
1.2 GPSR/GPCR(UNIM)
GeoDTN+NAV(UNIM) 50 randomly
1
moving nodes
0.8
Additional 40
0.6
GeoDTN ‘bus’ nodes
0.4
GPSR/GPCR 20 random src
0.2 nodes to a
0
fixed dest
5 10 15 20 25 30 35 40
Number of ’Bus’ Nodes
GeoDTN+Nav performs at least 12%+
over GPSR/GPCR
38
Ongoing and Future Work
LOUVRE: Histogram-based scheme of density
information to minimize storage overhead
Vehicular-Airborne network to handle ground
disconnectivity due to
Emergency such as Katrina-type of event
Ground APs are completely destroyed
Exploiting planned trajectories of airborne network
Exploiting satellite links to minimize end-to-end
delay
Multicast + DTN for military applications
39
Scientific Contributions
In the new paradigm of planar graph by roads,
We improve routing efficiency (TO-GO)
We perform cross link removal to eliminate routing
loops (GeoCross)
We avoid voids and backtracking by peer-to-peer
density estimation scheme (LOUVRE)
We handle end-to-end intermittent disconnetivity
by using contextual information (GeoDTN+Nav)
Combine Airborne and Vehicular network to
handle broken communication arise from
natural disaster or terrorist attacks
40
Publications
“GeoCross: A Geographic Routing Protocol in the Presence of Loops in Urban Scenarios,” Kevin C.
Lee, Payne Cheng, Jerome Haerri, Mario Gerla, submitted
"TO-GO: TOpology-assist Geo-Oppertunistic Routing in Urban Vehicular Grids", Kevin C. Lee,
Uichin Lee, Mario Gerla, WONS 2009 , Snowbird, Utah, February. 2009
"LOUVRE: Landmark Overlays for Urban Vehicular Routing Environments", Kevin C. Lee, Michael
Le, Jerome Haerri, Mario Gerla, WiVeC 2008, Calgary, Canada, March. 2008
"GeoDTN+Nav: A Hybrid Geographic and DTN Routing with Navigation Assistance in Urban
Vehicular Network", Pei-Chun Cheng, Kevin C. Lee, Mario Gerla, Jerome Haerri,
MobiQuitous/ISVCS 2008, best paper award, Trinity College Dublin, Ireland, July. 2008
"GeoDTN+Nav: A Hybrid Geographic and DTN Routing with Navigation Assistance in Urban
Vehicular Network", Pei-Chun Cheng, Kevin C. Lee, Mario Gerla, Jerome Haerri, JNC submission
"Enhanced Perimeter Routing for Geographic Forwarding Protocols in Urban Vehicular Scenarios",
Kevin C. Lee, Jerome Haerri, Uichin Lee, Mario Gerla, Autonet'07, Washington, D.C., November.
2007
"First Experience with CarTorrent in a Real Vehicular Ad Hoc Network Testbed", Kevin C. Lee,
SeungHoon Lee, Ryan Cheung, Uichin Lee, Mario Gerla, VANET MOVE ’07, Anchorage, Alaska,
May. 2007
41