Connectivity Aware Routing for Vehicular Ad Hoc Networks

Don’t hesitate to comment below if you have any questions or additional phrases
Connectivity Aware Routing for Vehicular Ad Hoc Networks Qing Yang, Alvin Lim, Prathima Agrawal Auburn University IEEE Wireless Communications & Networking Conference March 31 – April 3, 2008, Las Vegas
,Outline Goals
Basic concepts Related works Assumptions Model of the connectivity Validation with VanetMobiSim
Routing strategy Simulations and result analysis Conclusions IEEE Wireless Communications & Networking Conference (WCNC), Las Vegas, 2008
,Goals Achieves routing between two ends
IEEE Wireless Communications & Networking Conference (WCNC), Las Vegas, 2008
,Basic concepts Model the probability of connectivity of each road segment
Find the route with the highest probability of connectivity Carry-and-forward the packet while facing network partitions IEEE Wireless Communications & Networking Conference (WCNC), Las Vegas, 2008
,Related Works VADD (’06Infocom)
Vehicle-Assisted Data Delivery
MURU (’06MobiQuitous) Multi-Hop Routing for Urban Vanet
GSR (’05MC2R) Geographic source routing
GPSR (’00MobiCom) IEEE Wireless Communications & Networking Conference (WCNC), Las Vegas, 2008
,Assumption GPS on each vehicle
Standard component
Digital maps [1,2] Vehicle density
Vehicle speed Traffic light period 1. https://www.mapmechanics/ 2. https://www.yahoo.com/ IEEE Wireless Communications & Networking Conference (WCNC), Las Vegas, 2008
,…. n cars n0 cells m cells Model of connectivity One lane road segment
road segment (length is L) is equally divided into m cells
each cell can contain only one node communication range is size of n0 cells IEEE Wireless Communications & Networking Conference (WCNC), Las Vegas, 2008
,…. …. Multiple lanes case One lane road segment
Number of empty cells is m-n
Multiple lanes road segment Number of lanes is n’
Number of empty cells ranges [m-n, m-n/n’] IEEE Wireless Communications & Networking Conference (WCNC), Las Vegas, 2008
,…. Problem formulation Problem formulation
What is the probability that network is connected
The probability that no gap in networks is larger than the communication range Random Allocation (RA) theory 1 0 0 1 1 0 1 2 0 1 1 1 1 IEEE Wireless Communications & Networking Conference (WCNC), Las Vegas, 2008
,Probability of connectivity P1 (exists exactly k empty cells)
P2 (exists more than n0continuous empty cells) Pcon (Probability of connectivity) IEEE Wireless Communications & Networking Conference (WCNC), Las Vegas, 2008
,VanetMobiSim Feature
multi-lane roads
separate directional flows traffic signs at intersections Intersection management Lane changing VanetMobiSim[3] mobility patterns have been validated against TSIS-CORSIM a well known and validated traffic generator
3. https://vanet.eurecom.fr IEEE Wireless Communications & Networking Conference (WCNC), Las Vegas, 2008
,Validation of connectivity model Length of road
1000m, 1800m
Traffic light period 60sec., 120sec.
Average velocity 7.5m/s, 10m/s
IEEE Wireless Communications & Networking Conference (WCNC), Las Vegas, 2008
,Result of validation 1000m, 7.5m/s and 60sec
IEEE Wireless Communications & Networking Conference (WCNC), Las Vegas, 2008
,Result of validation (cont’) 1800m, 10m/s and 120sec
IEEE Wireless Communications & Networking Conference (WCNC), Las Vegas, 2008
,Probability of connectivity of route p3 p8 Pi: probability of connectivity of road segment i
Pcon: probability of connectivity of selected route (path) Defined as ∏Pi
p1 p11 p6 p4 p9 p1*p4*p7*p12=Max? p2 p7 p12 p5 p10 IEEE Wireless Communications & Networking Conference (WCNC), Las Vegas, 2008
,Computation of Pr Define of Pr:
sequence of road segments from source to destination
Modified Dijkstra Algorithm Final goal: maximize the probability of whole path
Each step: add one more edge, the probability of new path decrease Can be computed Centralized
Distributed IEEE