Transcript UNIVERSITY OF SOUTHERN CALIFORNIA

UNIVERSITY OF
SOUTHERN CALIFORNIA
PATHS: Analysis of PATH Duration
Statistics and their Impact on Reactive
MANET Routing Protocols
Narayanan Sadagopan*, Fan Bai+,
Bhaskar Krishnamachari*+, Ahmed Helmy+
* Computer Science Department
+ Electrical Engineering Department
University of Southern California
UNIVERSITY OF
SOUTHERN CALIFORNIA
Outline
•
•
•
•
Introduction and Motivation
Background on Mobility Models
Link/Path Duration Metrics
Results & Observations
– Distributions at low and high mobility
– Is it exponential?!
• Models: Path Duration, Throughput & Overhead
• Conclusions and Future Work
UNIVERSITY OF
SOUTHERN CALIFORNIA
Introduction and Motivation
• Mobility affects performance of MANET protocols
significantly [IMPORTANT ‘Infocom BSH03’]
• Mobility affects connectivity, and in turn protocol
mechanisms and performance
Protocol Mechanisms
Performance
Mobility
Connectivity
(Throughput,
• In this study:
Overhead)
– Closer look at the mobility effects on connectivity metrics
(statistics of link duration (LD) and path duration (PD))
– Develop approximate expressions for LD & PD distributions
(Is it really exponential? When is it exponential?)
– Develop first order models for Tput & Overhead as f(PD)
UNIVERSITY OF
SOUTHERN CALIFORNIA
Mobility Models
• Used the IMPORTANT framework and tools[BSH’03]
• Rich set of mobility models that exhibit various spatial
correlation and relative velocities
• Four main models:
–
–
–
–
Random Waypoint (RW) [CMU Monarch, BMJHJ’98]
Reference Point Group Mobility (RPGM) [UCLA, HGPC’99]
Freeway (FW)
Manhattan (MH)
UNIVERSITY OF
SOUTHERN CALIFORNIA
Mobility Models (contd.)
• Random Waypoint Model (RWP)
– A node picks random destination & random velocity [0, Vmax]
– After reaching the destination, it stops for the “pause time”.
– This procedure is repeated until simulation ends
• Reference Point Group Mobility (RPGM)
– A group’s general movement is determined by a logical reference point
– Each node in a group follows the reference point with small deviation:


| Vnode (t ) |  | Vreference (t ) |  random()  SDR Vmax
 node (t )  reference (t )  random()  ADR   max
– Angle Deviation Ratio(ADR) and Speed Deviation Ratio(SDR).
• In our study ADR=SDR=0.1
– Two scenarios: Single Group (SG) and Multiple Group (MG)
UNIVERSITY OF
SOUTHERN CALIFORNIA
Mobility Models (contd.)
• Freeway Model (FW)
– A node is restricted to its lane on the freeway
– Velocity of a node is temporally dependent on
its previous velocity
– If two mobile nodes on the same freeway lane
are within the Safety Distance (SD), the
velocity of the following node cannot exceed
the velocity of preceding node
Map for FW
• Manhattan Model (MH)
– Similar to Freeway model
– Allows nodes to make turns at intersections
Map for MH
UNIVERSITY OF
SOUTHERN CALIFORNIA
Connectivity Metrics
• Link Duration (LD):
– For nodes i,j, the duration of link i-j is the longest interval in
which i & j are directly connected
– LD(i,j,t1)=t2-t1
• iff t, t1  t  t2,   > 0 : X(i,j,t)=1,X(i,j,t1-)=0, X(i,j,t2+)=0
• Path Duration (PD):
– Duration of path P={n1,n2,…,nk} is the longest interval in
which all k-1 links exist
UNIVERSITY OF
SOUTHERN CALIFORNIA
Simulation Scenarios in NS-2
• Path duration computed for the shortest path (at graph
level) until it breaks.Validated later via protocol paths.
• Mobility Models (IMPORTANT tool)
– Vmax = 1,5,10,20,30,40,50,60 m/s,
– RPGM: 4 groups (called RPGM4)
– Speed/Angle Deviation Ratio=0.1
• 40 nodes, in 1000mx1000m area
• Radio range (R)=50,100,150,200,250m
• Simulation time 900sec
UNIVERSITY OF
SOUTHERN CALIFORNIA
Link Duration (LD) PDFs
• At low speeds (Vmax < 10m/s) link duration has
multi-modal distribution for FW and RPGM4
– In FW due to geographic restriction of the map
• Nodes moving in same direction have high link duration
• Nodes moving in opposite directions have low link duration
– In RPGM4 due to correlated node movement
• Nodes in same group have high link duration
• Nodes in different groups have low link duration
• At higher speeds (Vmax > 10m/s) link duration does
not exhibit multi-modal distribution
UNIVERSITY OF
SOUTHERN CALIFORNIA
Nodes moving in opposite directions
FW model
Vmax=5m/s
R=250m
Nodes moving in
the same direction/lane
Multi-modal Distribution of Link Duration for Freeway model at low speeds
UNIVERSITY OF
SOUTHERN CALIFORNIA
Nodes in different groups
RPGM w/ 4 groups
Vmax=5m/s
R=250m
Nodes in the same group
Multi-modal Distribution of Link Duration for RPGM4 model at low speeds
UNIVERSITY OF
RW CALIFORNIA
SOUTHERN
RPGM (4 groups)
FW
Vmax=30m/s
R=250m
UNIVERSITY OF
SOUTHERN CALIFORNIA
Path Duration (PD) PDFs
• At low speeds (Vmax < 10m/s) and for short paths
(h2) path duration has multi-modal for FW and
RPGM4
• At higher speeds (Vmax > 10m/s) and longer path
length (h2) path duration can be reasonably
approximated using exponential distribution for RW,
FW, MH, RPGM4.
UNIVERSITY OF
SOUTHERN CALIFORNIA
Nodes moving in opposite directions
Nodes moving in
the same direction
FW
Vmax=5m/s
h=1 hop
R=250m
Multi-modal Distribution of Path Duration for Freeway model at low speeds, low hops
UNIVERSITY OF
SOUTHERN CALIFORNIA
Nodes in different groups
Nodes in the same group
RPGM4
Vmax=5m/s
h=2 hops
R=250m
Multi-modal Distribution of Path Duration for RPGM4 model at low speeds, low hops
UNIVERSITY OF
SOUTHERN CALIFORNIA
RW
RPGM4
h=2
h=4
100
FW
h=4
Vmax=30m/s
R=250m
UNIVERSITY OF
SOUTHERN CALIFORNIA
Exponential Model for Path Duration (PD)
• Let path be the parameter for the exponential PD
distribution: PD PDF f(x)= path e- path x
– As path increases average PD decreases (and vice versa)
• Intuitive qualitative analysis:
–
–
–
–
PD=f(V,h,R); V is relative velocity, h is path hops & R is radio range
As V increases, average PD decreases, i.e., path increases
As h increases, average PD decreases, i.e., path increases
As R increases, average PD increases, i.e., path decreases
UNIVERSITY OF
SOUTHERN CALIFORNIA
UNIVERSITY OF
SOUTHERN CALIFORNIA
UNIVERSITY OF
SOUTHERN CALIFORNIA
UNIVERSITY OF
SOUTHERN CALIFORNIA
Exponential Model for PD
But, PD PDF f(x)= path e- path x
UNIVERSITY OF
SOUTHERN CALIFORNIA
0.25
RW
h=2
Probability
PD
0.05
RGPM4
h=4
Exponential
0.2
Probability
Exponential
0.1
PD
0.15
0.1
0.05
0
0
0
10
20
30
40
0
50
10
20
30
40
50
Path Duration (sec)
Path Duration (sec)
0.5
FW
FW
h=4
h=4
Exponential
- Correlation: 94.1-99.8%
Probability
0.4
PD
0.3
Vmax=30m/s
R=250m
0.2
0.1
0
0
10
Path Duration (sec)
20
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
Exponential
PD
Probability
D= 0.0477
RW
h=2
0
3
6
9 12 15 18 21 24 27 30 33 36 39 42 45 48 51 54
- Goodness-of-fit Test
RW
FW
RPGM
K-S test
0.04-0.065
0.045-0.085
0.09-0.12
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
Exponential
PD
D= 0.093
RGPM4
h=4
0
3
6
9 12 15 18 21 24 27 30 33 36 39 42 45 48
Cumulative Distribution Function (CDF)
Cumulative Distrbution Function (CDF)
Probability
Probability
UNIVERSITY OF
SOUTHERN CALIFORNIA
Exponential
D= 0.048
PD
FW
h=4
0
2
4
6
8
10 12 14 16 18 20 22 24 26 28 30
Cumulative Distribution Function (CDF)
Vmax=30m/s
R=250m
UNIVERSITY OF
SOUTHERN CALIFORNIA
Effect of Path Duration (PD) on Performance
(in-progress): Case Study for DSR
• PD observed to have significant effect on performance
• (I) Throughput: First order model
– T: simulation time, D: data transferred, Tflow: data transfer time,
Trepair: total path repair time, trepair: av. path repair time, f: path break frequency
Throughput 
D
T
1
T  T flow  Trepair  T flow  t repair. f .T  T flow  t repair.
.T
PD
t repair
t repair
D
Throughput  (1 
)
 (1 
).rate
PD T flow
PD


T
T flow
t
(1  repair )
PD
Throughput (
1
)
PD
UNIVERSITY OF
SOUTHERN CALIFORNIA
Effect of PD on Performance (contd.)
• (II) Overhead: First order model
T
– Number of DSR route requests=
PD
– p: non-propagating cache hit ratio, N: number of nodes

Overhead
1
PD
• Evaluation through NS-2 simulations for DSR
Throughput
Overhead
Random Waypoint (RW) Freeway (FW)
-0.9165
-0.9597
0.9753
0.9812
Manhattan (MH)
-0.9132
0.9978
Pearson coefficient of correlation () with 1
PD
– RPGM exhibits low , due to relatively low path changes/route requests
UNIVERSITY OF
SOUTHERN CALIFORNIA
Conclusions
• Detailed statistical analysis of link and path duration for
multiple mobility models (RW,FW,MH,RPGM4):
– Link Duration: multi-modal FW and RPGM4 at low speeds
– Path Duration PDF:
• Multi-modal FW and RPGM4 at low speeds and hop count
• Exponential-like at high speeds & med/high hop count for all models
• Developed parametrized exponential model for PD PDF, as
function of relative velocity V, hop count h and radio range R
• Proposed simple analytical models for throughput & overhead
that show strong correlation with reciprocal of average PD
UNIVERSITY OF
SOUTHERN CALIFORNIA
Future Work
• Apply path duration analysis to various ad hoc protocols
• Attempt to explain: Why does path duration distribution
become exponential?
• Analyze convergence time and cache performance to
account for varying performance between different
protocols. Use it to extend first order models.
• Analysis of effects of mobility on protocol mechanisms
• Extend and release the IMPORTANT mobility tool:
– URL: http://nile.usc.edu/important
UNIVERSITY OF
SOUTHERN CALIFORNIA
Backup/Extra Slides
UNIVERSITY OF
SOUTHERN CALIFORNIA
Rel vel. (V) prop to max vel (Vmax)
UNIVERSITY OF
SOUTHERN CALIFORNIA
D: total data transferred during simulation
T: simulation time
Tflow: data transfer time
Trepair: total time spent in repairing paths
trepair: time to repair path each time
PD: average path duration
f: frequency of path breakage,
r: is constant data rate=D/Tflow
N: number of of nodes
UNIVERSITY OF
SOUTHERN CALIFORNIA
• Number of path repairs=T/(PD+trepair)
Throughput  (1 
t repair
PD  t repair
)
D
PD
(
).rate
T flow
PD  t repair
UNIVERSITY OF
SOUTHERN CALIFORNIA
• Expression for cache hit ratio (Hit): [FW model]
Hit=
UNIVERSITY OF
SOUTHERN CALIFORNIA
Non-propagating Cache Hit Ratio in DSR (independent of velocity!)