Transcript Slide - Victoria Manfredi

Sensor Control and Scheduling
Strategies for Sensor Networks
Victoria Manfredi
Thesis Defense
August 13, 2009
Advisor: Jim Kurose
Committee: Andrew Barto
Deepak Ganesan
Weibo Gong
Don Towsley
Motivation
Cameras, radars: cannot
collect data simultaneously
from all environment locations
Where to focus sensing?
Wireless, Closed-Loop
Sensor Network
Data
Sensor Controls
Changing network topology
Multiple users making
conflicting sensor requests
How to make routing robust
to network changes?
How to accommodate
multiple users?
Bursty, high-bandwidth data, many-to-one data routing to sink: congestion
How to make sensing robust to delayed and dropped packets?
2
Contributions
 Adaptive sensors
– where to focus sensing in adaptive meteorological radar network?
• show lookahead strategies useful when multiple small phenomena,
trade-off between scan quality and re-scan interval
– accommodating multiple users?
• identify call admission control problem, give complexity results
 How to make sensing robust to delayed, dropped packets?
– show good application-level performance possible in closed-loop
sensor network when congestion if sensor control prioritized
 How to make routing robust to network changes?
– propose routing algorithm, show can significantly  control
overhead while minimally degrading % of packets delivered
3
Outline
Adaptive sensors
– where to focus sensing?
– multiple users
Prioritizing sensor control traffic
Robust routing in dynamic networks
Conclusions
4
Where to focus sensing?
CASA: Adaptive Meteorological Radar Network
small scan sectors
high quality, but
may miss storm
large scan sectors
low quality, but
miss fewer storms
5
Sensing Strategies
What are ``good” sensing strategies?
 sit-and-spin
– all radars always scan 360
 myopic
– consider only current environmental state
 limited lookahead
– Kalman filters to predict storm cell attributes k time-steps ahead
 full lookahead
– formulate as Markov decision process
– reinforcement learning to obtain policy: Sarsa()
6
Storm Tracking Application
 Radar network
30km
30
km
max storm radius: 4km
 Storm model
– storms arrive according to spatio-temporal Poisson process
– storm dynamics from Kalman filters
 Radar sensing model
– observed attribute value = true attribute value + Gaussian noise
Depends on scan
quality
7
Performance Metrics
 Re-scan interval 30 km
– how long before storm first observed or rescanned
 Scan quality
– how well storm observed
– function of
• scan sector size
• distance from radar
• % of storm scanned
– value between 0 and 1
 Cost
– function of re-scan interval, quality, penalty for missing storms
– 2-step and full lookahead have similar cost for 2 radars
8
Optimize over all radars?
Average Quality
1-Step Lookahead
Myopic
1-Step Lookahead
Myopic
Sit-and-Spin
Max 1 Storm
No gains in quality as optimize
over more radars
Sit-and-Spin
Max 8 Storms
Decreasing gains as optimize
over more radars
9
Summary
Where to focus sensing?
Showed lookahead strategies useful when multiple
storms, storm radius (much) smaller than radar radius
 trade-off scan quality and frequency storm scanned
 may not need to optimize over all radars in network
 Related work
– track ground targets from airplanes [Kreucher, Hero, 2005]
– our focus: track meteorological phenomena using ground radars
10
Outline
Adaptive sensors
– where to focus sensing?
– multiple users
Prioritizing sensor control traffic
Robust routing in dynamic networks
Conclusions
11
How to accommodate multiple users?
 Virtualize sensing resources
Mt. Toby
– virtualized private sensor network
Quick Time™a nd a
dec ompr esso r
ar e nee ded to see this pictur e.
 To each user
– looks like own private network
– but user only has virtual slice
MA1
Tower
 Users request resources
– possibly conflicting requests
– which requests to satisfy?
Quick Time™a nd a
dec ompr esso r
ar e nee ded to see this pictur e.
QuickTime™ and a
decompressor
are needed to see this picture.
CS
Building
Call admission control problem
12
Call Admission Control Problem
 Sensor request
Scan 360°
– use sensor in particular way possibly during particular time
 Sensing strategy
Scan 360° every 2 min
– sequence of requests over time
Strategy for User 1
Strategy for User 2
 Utility of request j
i
– to requesting user i: uij
– to each other user i: uiji
Combine into single utility
i
uij = uij +  uij
i
i
Select set of non-interfering requests that maximizes utility
13
Space of Problems
Divisible requests?
 Utility received if only part
of request satisfied?
 Yes
– scan x of y elevations
 No
Shifting permitted?
 Utility received if request
executed at different time?
 Yes
– perform surveillance scan
 No
– obtain full scan of storm
– sense storm expected at
location (x,y) at time t
User 1 Request
User 1 Request
User 2 Request
Shifted Request
Interleaved Requests
Time
Time
14
Complexity
Divisible requests?
Yes
Shifting permitted?
Yes
Polynomial
Same as fractional
knapsack problem
No
Polynomial
Interleave sensor
requests
No
Shifting permitted?
Yes
NP-Complete
No
Polynomial
Interval scheduling
[Arkin, Silverberg, 1987]
15
Indivisible, Shifting
 NP-complete
– assume utility independent of when request executed
– In NP: can check whether solution correct in polynomial time
Reduction
Capacity
W
w1
v1

wN
vN
Sensing Strategy
for User N
w1
v1


Knapsack Problem
Sensing Strategy
for User 1
wN
vN
Time T=W
Utility for satisfying user i’s request
– to user i: vi
– to each other user: 0
16
Summary
How to accommodate multiple users?
Requests divisible or fixed in time  polynomial-time algorithms
Requests indivisible but may be shifted  NP-complete
 Related work
– adaptively select set of sensors for task [Jayasumana et al, 2007]
– our focus: virtualizing sensing resources within a sensor
 Future work
– online, decentralized algorithms
– trade-off between maximizing utility and user fairness
– implement proposed algorithms in deployed network
17
Outline
Adaptive sensors
– where to focus sensing?
– multiple users
Prioritizing sensor control traffic
Robust routing in dynamic networks
Conclusions
18
Why prioritize sensor control traffic?
 Sensor network
Bursty, highbandwidth data
Many-to-one
routing to sink
Congestion
Wireless links
 Closed-loop sensor network
Data
Sensor
Controls
Data spatially,
temporally
redundant
Data >> control
Prefer to delay,
drop data rather
than control
How does prioritizing sensor control traffic over data traffic
impact application-level performance?
19
Closed-loop Sensor Networks
 Prioritizing sensor control
– impact on packet delays?
– impact on data collected?
 Control loop delay
Control, data share queues
e.g., wireless links
Priority control
delay
Data delay
FIFO control delay
Data
Data from
control k
Data from
control k-1
Control
k-1
k
k+1
Update interval
Small  data delay, large  control delay  more data
collected in time to compute next sensor control
20
Better Quality Data
 More data samples
Cramer-Rao bound:
SD(W) ≥ 1 / n I
Std Dev of W
from 
Fisher
information
# of iid samples
Radars, Sonars,
Cameras, …
Quick Time™a nd a
dec ompr esso r
ar e nee ded to see this pictur e.
Lower bound on std dev of unbiased estimator W
(sample mean) from parameter  (population mean)
– accuracy  sub-linearly with  n
 Effect of data packet drops?
– accuracy  sub-linearly with  n
Sensing accuracy changes slowly with # of samples
21
Storm Tracking Application
 Network model
– obtain sensor control and data packet delays
– CASA network is closed-loop sensor network
Delays at bottleneck
link dominate,
assume wireless links
Deterministic
arrivals
control
data
Bursty arrivals

other
 Sensing model
– convert packet delays into sensing error
 Tracking model
– convert sensing error into storm location error
– tracking: compute next scan for radar from 99% confidence ellipse
22
Tracking Error
+
+
RMSE =
# intervals
√
(true -obs )

t=1
t
t
2
# intervals
+
+
idx = 1
idx = 25
idx = 55
Per-interval performance gains/losses may accumulate
across multiple update intervals
23
Summary
How to make sensing robust to delayed and dropped packets?
When network congestion, prioritizing sensor control
in closed-loop sensor network  quantity, quality of
data, and gives better application-level performance
 Related work
– SS7, ATM, [Fredj et al, 2001] [Kyasanur et al, 2005]
– our focus: prioritizing sensor control (not network control)
24
Outline
Adaptive sensors
– where to focus sensing?
– multiple users
Prioritizing sensor control traffic
Robust routing in dynamic networks
Conclusions
25
What do we mean by robust?
network structure
changing over time
protocols
must adapt
But if frequent changes, adapting is costly: e.g., in MANET
may have as much routing control traffic as data
Adapt to every change?
 yes: potentially perform optimally, but more overhead
 no: likely perform sub-optimally, but less overhead
Robust: solution performs well over many
scenarios, solution is not fragile
26
Robust Routing
Robust routing: routing subgraph has path from
src to dest, as links up/down
 src-dest reliability
– prob instantaneous path in stochastic graph
– want max reliability sub-graph for overhead
But, reliability #P-complete
to compute, can’t search
over all sub-graphs
Identify structural properties that make graph reliable,
efficiently find subgraph with such properties
 Effect of graph structure on src-dest reliability?
– show reliability (in limits) dominated by shortest paths, smallest cuts
Most robust routing subgraph should contain
shortest path and have large min cut
27
Braid
(shortest)
k-hop braid: most reliable path + all nodes within k-hops
Most Reliable Path
1-Hop Braid
s
s
2-Hop Braid
s
d
d
d
Given fixed amount of overhead, is braid most reliable sub-graph?
 reliability simulations + theoretical analysis
28
Theoretical Analysis
Lemma: Suppose subgraph contains shortest
path and 0<n<N 1-hop
nodes. Given 1 or 2 extra
nodes, to max reliability,
use all 1-hop nodes before
any 2-hop nodes
Add black node rather
than
blue nodes?
How Reliable is
Braid?
s
d
N
Note: lemma does not hold when adding links
s
Partial Braid
d
s
d
2-Disjoint Paths
Partial braid less reliable
than 2-disjoint paths for
1p√2/3
29
Braid Routing
If no path from src to dest:
Use dynamic source
routing (DSR)
Step 1: Identify shortest path in network
Step 2: Build braid around shortest path
Step 3: Perform local forwarding within braid

e.g., flooding, opportunistic routing,
backpressure
Overheard RREQ and RREP
contain 1-hop braid info
When link breaks, use braid
path back to DSR path
DSR vs Braid
– path breaks
• use new DSR path or existing 1-hop braid path
– primary difference
• control overhead incurred to find this new path
30
Simulation Set-up
 QualNet
 Gauss-Markov mobility
– BonnMotion to generate traces
– min 0.5 m/s, max 2 m/s
– speed, angle updates every 100s
 20-80 nodes
– 400m transmission radius
– 2km x 2km area
 1 constant bit-rate flow
– 4 pkts/s, 1 million seconds
 10 runs, each lasting life of flow
31
# of Control Packets
Control Overhead
DS
R
Braid
# of Nodes
As node density increases, braid incurs fewer
control packets than DSR
32
Control Overhead
# of Control Packets
Route Requests
Route
Replies
Route Errors
DS
R
Braid
DS
R
Braid
DS
R
Braid
# of Nodes
# of Nodes
# of Nodes
Up to ~30%
fewer requests
Up to ~40%
fewer replies
Up to ~25%
fewer errors
Braid incurs fewer route requests, replies, errors than DSR
33
DS
R
Braid
(4 million packets)
Delay (seconds)
% of Packets Delivered
Packets Delivered and Delay
Braid
DS
R
# of Nodes
# of Nodes
Braid delivers slightly fewer packets, incurs
higher delay than DSR
34
Summary
How to make routing robust to network changes?
Proposed routing algorithm that  control overhead by
(1) updating routes less frequently
(2) performing local forwarding within routing sub-graph
 gains depend on network characteristics
 Related work
– [Shacham et al 1983] [Lee, Gerla, 2000] [Ganesan et al, 2001] [Ghosh et al, 2007]
– our work: differs in structure and/or usage of routing subgraph
 Future work
– which network characteristics most impact performance?
– joint rate control and routing
– what should be braid width (trade-off with interference)?
35
Outline
Adaptive sensors
– where to focus sensing?
– multiple users
Prioritizing sensor control traffic
Robust routing in dynamic networks
Conclusions
36
Conclusions
 Adaptive sensors
– where to focus sensing in adaptive meteorological radar network?
• show lookahead strategies useful when multiple small phenomena,
trade-off between scan quality and re-scan interval
– accommodating multiple users?
• identify call admission control problem, give complexity results
 How to make sensing robust to delayed, dropped packets?
– show good application-level performance possible in closed-loop
sensor network when congestion if sensor control prioritized
 How to make routing robust to network changes?
– propose routing algorithm, show can significantly  control
overhead while minimally degrading % of packets delivered
37
Thanks!
 Jim
 Don, Deepak, Andy, Weibo
 Networks Lab
– Bruno, Mike, Yung-Chih, Daniel2, Majid, Yu, Bo, Patrick, Junning,
Giovanni, Guto, Elisha, Suddu, Bing, Sookhyun, Chun …
 ALL Lab
– Sridhar, Mohammad, George, Sarah, Khash, Ash, Ozgur, Pippin …
 Laurie, Tyler, ….
Questions?
38
Adaptive Sensing
39
Performance Metrics
 Re-scan interval
sr : radar configuration, start,
end angles of scan sector
Sr: set of radar configurations
– # of decision epochs before storm cell first observed or rescanned
 Quality
– how well storm cell p observed
distance to storm cell
Up(p, Sr) = max [ Fc(c(p, sr ))  [  Fd(d(r,p)) + (1-) Fw(w(sr ) / 360)]
s r Sr
% covered
]
radar rotation speed
– how well sector ri scanned
Us(ri, sr) = Fw(w(sr ) / 360)]
40
Performance Metrics
Pm := penalty for never
scanning storm
Pr := penalty for not
rescanning storm
 Cost
– Re-scan time and quality + penalty for never scanning storm cell
Difference between true and
observed # of storm cells
o
Np
Nd
i=1
j=1
o
C =   |dij - dij| +
o
(Np -Np)
Difference between observed
and true storm attribute
Np
Pm + I(tk)Pr
k=1
Storm scanned within Tr
decision epochs?
Goal: maximize quality, minimize re-scan time
41
Limited Look-ahead Strategy
Use Kalman filters to predict storm cell attributes
1 and 2 decision epochs ahead
 State


True state:
true = [ x, y, x, y ]T
Observed state: obs = [ x, y ]T
y

(x,y) x
Assume:
truet = A truet-1 + N[0, Q]
obst = B truet + N[0,R]
A, B, Q, R
initialized using
prior knowledge
 Actions
– select scan action that minimizes cost
– additionally scan any sector not scanned in last T=4 decision epochs
42
Full Look-ahead Strategy
Markov Decision Process Formulation
 State

Storm radius
y

(x,y)
x
+
# of storm cells,
Up quality of storm cells,
Us quality of sectors
 Actions
 Transition function
– encodes observed environment dynamics, obtained from simulator
 Cost function
– obtained from performance metrics
 Sarsa()
– linear combination of basis functions to approximate value function
– tile coding to obtain basis functions, one tiling for each state variable
43
Simulation Set-up
 True state
– storms arrivals: spatio-temporal
process
– storm attributes from distributions
derived from real data
– max storm radius: 4km
– max number of storms
Poisson
10 km or
30 km
 Observed state
– observed attribute value = true attribute value plus noise ~ N[0, 2]
Largest positive value of attribute
 = (1-u) Vmax / 
Us(ri,sr) quality
scaling term
44
Avg Difference in Quality (250,000 steps)
Scan Quality
Max 1 storm
2Step - Sarsa
SitandSpin - Sarsa
Max 4 storms
1/
2-Step scans have higher quality than Sarsa(), especially
when little noise in environment (when 1/ is small)
45
Cost
2 radars
Average
Difference in Cost
# timesteps

t=1
SitandSpin Full Lookahead
2step
Ct
- CFull
t
# timesteps
2StepLookahead - FullLookahead
1/
Full lookahead and 2-step look-ahead have similar costs
46
Re-scan Interval
Sit-and-Spin
1-Step
P[X≤ x]
2-Step
Sarsa() more likely than 2-step
look-ahead to scan storm within
Tr=4 decision epochs
Sarsa()
x = # of decision epochs between storm scans
47
Related Work
Radar Control
 2005: Kreucher, Hero
– look-ahead scheduling of radars on
airplanes for detecting and tracking
ground targets
– information-theoretic reward, Qlearning
Large State-space
Reinforcement Learning
 2005: Stone, Sutton, Kuhlmann
– robot soccer
 2004: Ng, Coates, Diel, Ganapathi,
Schulte, Tse, Berger, Liang
– helicopter control
 2002: Zilberstein, Washington,
Bernstein, Mouaddib
– planetary rovers
We consider tracking meteorological
phenomena using ground radars
 2005: Suvorova, Musicki, Moran,
Howard, Scala
– target radar beams, select waveform
for electronically steered phased
array radars
– show 2-step lookahead outperforms
one-step look-ahead for tracking
multiple targets
Do not consider infinite-horizon case
Sensor Networks
 2005: Mainland, Parkes, Welsh
– game theory + reinforcement
learning to allocate resources
– learn profit associated with
different actions, rather than profit
associated with different stateaction pairs
48
Call Admission Control Problem
49
Divisible, No Shifting
 Polynomial-time
– assume utility depends on how much of request executed
– select max utility sensor request during each conflicting interval
Sensing Strategy for User 1
Sensing Strategy for User 2
Interleaved Sensor Requests
50
Separation of Control/Data
51
Storm Tracking Application: 3 Coupled
Models
Network model: control, data delays,
depend on scheduling (FIFO, priority)

d
Timeliness of control, data affects
amount of sensed data gathered
d


d

c
Sensing model: given scan, quantity and
quality of data, estimated storm location
Quality of estimated storm location
affects tracking
Tracking model: predict storm location
based on current, past estimates and
observations using Kalman filters
Quality of tracking affects scan angle,
quality of estimates
(xk,yk)
(xk-1,yk-1)
52
Network Model

d
Obtain sensor control and
data packet delays
d


d

c
 Wireless network
– radar data sent to control center, sensor control back to radars
– much more data traffic than sensor control traffic
 Delays at bottleneck link dominate control-loop delay
Deterministic
arrivals
control

data
Bursty arrivals
other
Obtain delays for FIFO, priority queuing using simulation
53
Sensing Model
Convert packet delays into
sensing error
 Radar
– transmits pulses to estimate reflectivity at point in space
 Reflectivity
– # of particles in volume of atmosphere
– standard deviation,
=
where N = c (D - (a+)) / 
sensing time
radar SNR
scan angle width
Smaller angle, longer time sensing  lower sensing error
54
Tracking Model
Convert sensing error into location
(xk,yk)
error, perform tracking
(xk-1,yk-1)
 Location of storm centroid
– equals location of peak reflectivity
– standard deviation,
z =
r d
30 dBz
distance from radar
mid-range reflectivity value
 Kalman filters
– generate trajectory of storm centroid
– track storm centroid
z used in measurement
covariance matrix
Goal: track storm centroid with highest possible accuracy
55
Kalman filter
xk := estimated (location, velocity)
yk := measured (location, velocity)
noisy, with std deviation r(,a+)
(xk-1,yk-1)
(xk,yk)
Measure: radar data
received, measured
position yk, with r(,a+)
Filter: estimate xk
based on yk, predicted x-k
x-
Predict: next (k+1) 99%
confidence region, gives k+1
to scan next time step
Estimated state error
covariance matrix, depends
on velocity noise model,
r(,a+)
56
Simulation Set-up
 Network parameters
Vary burstiness of ``other” traffic,
r1 = 1s
control= 1/D pkts/s
data= 2000/30

pkts/s
1= po
on
off
2= (1-p)o
r2 = 1s
other= 2000/30
pkts/s
Index of dispersion
control+ data+other  133.37 pkts/s
 = 148.5 pkts/s
idx =
avg load  0.90
 Kalman filter parameters
– initialize based on storm data
 10 NS-2 simulation runs, 100,000 sec each
57
Data Quantity
idx = 55
Number of times more
voxels scanned under
priority than under FIFO
idx = 25
idx = 1
D (seconds)
As D  and burstiness , gains from prioritizing increase
58
Data Quality
Number of Pulses
Reflectivity Standard
Deviation
D = 30sec
D = 30sec
D = 5sec
idx55
idx1
idx55
idx1
x = NFIFO / NPriority
Small decision epoch, bursty traffic:
FIFO achieves ~80% as many pulses
as priority ~80% of time
F(x)
F(x)
Assuming  = 360
D = 5sec
idx55
idx1
idx55
idx1
x = r,Priority / r,FIFO
Small decision epoch, bursty traffic:
priority has at least 90% as much
uncertainty as FIFO ~90% of the time
59
Number of Pulses
FIFO and Priority each achieve about 6x as many
pulses per voxel for D = 30 sec vs D = 5 sec, and total
# of pulses is independent of D
60
Data Quantity vs Quality
CDF
360 scans, D = 5sec,
very bursty traffic
FIFO achieves at least
80% as many samples as
priority ~80% of time
NFIFO / Npriority
**
Priority has at least
90% as much
uncertainty as FIFO
~90% of the time
r,Priority / r,FIFO
During times of congestion, prioritizing sensor
control  quantity, quality of data
61
r (with loss) / r (no loss)
Effect of Packet Loss
FIFO: sensor control
packets dropped
Capacity: when >1000,
data dropped
Priority: no sensor control
packets dropped
 = pkts / second
As system goes into overload sensing accuracy degrades
(more) gracefully when sensor control is prioritized
62
Related Work
Service Differentiation for
Different Classes of Traffic
 2001: Bhatnager, Deb, Nath
–
assign priorities to packets, forwarding
higher-priority packets more frequently
over more paths to achieve higher
delivery prob
 2005: Karenos, Kalogeraki,
Krishnamurthy
–
bandwidth reservation for high-priority
flows in wireless sensor networks
 2008: Kumar, Crepadir, Rowaihy, Cao,
Harris, Zorzi, La Porta
–
 SS7 telephone signaling system
 ATM networks, IP networks
 1998: Kalampoukas, Varma, Ramakrishan,
2002: Balakrishnan et al,
–
differential service for high priority data
traffic versus low-priority data traffic in
congested areas of sensor network
Do not consider effects of
prioritizing only sensor control
in a sensor network
priority handling of TCP acks
 2005: Kyasanur, Padhye, Bahl
–
separate control channel for controlling
access to shared medium in wireless
Our focus: prioritize sensor control
allocate rates to flows based on class of
traffic and estimated network load
 2006: Tan, Yue, Lau
–
Prioritize Network Control
Networked Control Systems
 data, sensor control sent over network
–
–
constrained to be feedback and
measurements of classical control system
ratio of data to control much smaller than that
of closed-loop sensor network
 2001: Walsh, Ye
–
put error from network delays in control eqns
 2003: Lemmon, Ling, Sun
–
drop selected data during overload by
analyzing effect on control equations
We assume amount of
data  sensor control
63
Robust Routing
64
What do we mean by robust?
Robust routing: routing subgraph has path from
src to dest, as links up/down
T=1






T=2


2/4


3/4

4/4

T=3
T=4
65
Some Intuition
What is effect of graph structure on src-dest reliability?
Given graph G, src, dest, assume links iid and up with prob p
Paths
Small p limit:
reliability
dominated by
shortest paths
Cuts
Small q=1-p limit:
un-reliability
dominated by
smallest cuts
Most robust routing subgraph should contain shortest/most
reliable path and have large min cut
66
Theoretical Analysis
Proof:
s
s1
s1
q1
q1
d1
d1
s0
s0
q0
q0
d0
d0
d
P(d|s) = P(d | s0 s1) P(s0 s1|s)
+ P(d | s0 s-1) P(s0 s-1|s)
+ P(d | s-0 s1) P(s-0 s1|s)
Recursively iterate:
get eqn with 27 terms
P({q0,q1} | {s0,s1}) P(d | {d0,d1})
Product always  for
adding black node
67
Conjectures
Conjecture 1: N extra nodes: 1-hop braid most reliable
 From lemma: true for N ≤ 5
Conjecture 2: 2N extra nodes: 2-hop braid most reliable
 Experimentally: for
N=6, 2-hop braid more
reliable than pyramid
d
s
N=6
s
d
N=6
Generally: conjecture no “holes” in most reliable graph
68
Conjectures
Conjecture 2: 2N extra nodes: 2-hop braid most reliable
reliability
 experimentally: for N=6, 2-hop braid more reliable than pyramid
p
69
Adding edges rather than nodes
Conjecture 3: N+1 extra edges: partial 1-hop braid most reliable
 not true, see counterexamples
Partial Braid
2-Disjoint Paths
Partial braid less
reliable than 2-disjoint
paths for 1p0
N=3
s
s
d
d
N=4
s
d
s
d
Partial braid less
reliable than 2-disjoint
paths for 1p√2/3
70
Adding edges rather than nodes
Conjecture 3: N+1 extra edges: partial 1-hop braid most reliable
 not true, see counterexamples
Scaling behavior
link up prob above which
2-disjoint paths more
reliable than partial braid
N
As N increases, partial braid more reliable
for more values of p
71
Reliability Experiments
Have intuition that braids have good reliability properties
 But,
– how does reliability of braid compare with other routing subgraphs?
– what is impact of time between braid re-computations T on reliability?
 Experiment set-up
– model
Link model
1-p
• 100 nodes, random graph
• links iid, 2-state link model
• src, dest randomly chosen
– Monte Carlo simulation
• 500 runs, each lasting 100 time-steps
p
up
down
q
1-q
72
full graph
Reliability
1-hop braid
2-shortest disjoint paths
shortest path
T = length of routing update interval
p=0.85, q=0.5
Gain in Reliability over Shortest Path
Link Failures
2-shortest
disjoint paths
full graph
1-hop braid
# of Nodes Used in Addition to Shortest Path
p=0.85, q=0.5, T=5
Braid reliability close to full graph, braid overhead
significantly less than full graph
73
Node vs Link Failures
1-hop braid
full graph
2-shortest
disjoint paths
shortest path
T = length of routing update interval
p=0.85, q=0.5
Gain in Reliability over Shortest Path
Reliability
Node failures imply correlated link failures, as in mobility
2-shortest
disjoint paths
full graph
1-hop braid
# of Nodes Used in Addition to Shortest Path
p=0.85, q=0.5, T=5
All algorithms have lower reliability, braid overhead
still less than full graph
74
Routing Experiments
 GloMoSim
–
–
–
–
60 nodes, 250m transmission radius
1km x 1km area
1 cbr flow: 5 million pkts (~29 days)
random waypoint, Gauss Markov mobility
 Compare throughput, overhead
– AODV
– 1-hop braid
 built around AODV path
 choose next hop based on last successful use
 10 runs, each lasting life of flow
75
Random Waypoint Mobility
T = routing update interval (seconds)
Packets delivered: braid
delivers up to 5% more
packets than AODV
T = routing update interval (seconds)
Braid overhead: ~25% more
control overhead than AODV
76
Gauss-Markov Mobility
Insights: braids work well when
 links can reappear in T
 Independent link failure
T = routing update interval (seconds)
Packets delivered: braid
delivers up to 5% more
packets than AODV
T = routing update interval (seconds)
Braid overhead: ~40% more
control overhead than AODV
77
Reliability vs Routing
Reliability gains  Throughput gains
Reliability experiments
 iid links
 shortest path = most reliable path
Routing experiments
 non-iid links
 shortest path ≠ most reliable path
Braid construction independent of “best” path algorithm
 don’t use AODV, instead estimate link reliability
78
Reliability vs Routing
Reliability gains  Throughput gains
Reliability experiments
 iid links
 rate at which down links re-appear is “high”
 prob down link reappears = 0.5
 broken link likely re-appears during T
Routing experiments
 non-iid links
 rate at which down links re-appear is “low”
 2 nodes meet on avg once every 22.7 min
 broken link likely does not re-appear during T
 Consider link correlations, mobility characteristics
79
Link Failures and Braid Attempts
80