Transcript phoebus

Congestion Control to
Reduce Latency in
Sensor Networks for
Real-Time Applications
Presented by
Phoebus Chen
5/4/2006
EE228A – Communication Networks
1
Outline
Motivation: Sensor Network Surveillance
 Background: Congestion Control
 Difficulties with Addressing Latency
 Design Guidelines for Latency Congestion
Control Policies

5/4/2006
EE228A – Communication Networks
2
Sensor Networks for Real-Time
Surveillance

Event Detection
 bursty
traffic
 varying importance
of data for estimation
 can operate with
incomplete data

Low Latency
 routing
 selective
packet
delivery
 congestion control
5/4/2006
EE228A – Communication Networks
3
Sample Surveillance Scenario


Multiple targets on
linear trajectories
One centralized
estimator per cell
Ultimate scenario:
Pursuit-Evasion Games with mobile robots
5/4/2006
EE228A – Communication Networks
4
Study focused on design of
network congestion control
Wireless, multi-hop channel
 Fixed routing
Sensing and
 Multiple sources, one sink
Data

Aggregation
(source)
(network)
Sensing and
Data
Aggregation
5/4/2006
(source)
Estimation
EE228A – Communication Networks
(sink)
5
Performance Metric: Estimator

Linear System Dynamics
 driven
by a white noise process
 Simple linear measurement model

Estimation via Kalman Filter
 Check
5/4/2006
performance under different traffic patterns
EE228A – Communication Networks
6
Background on Congestion Control [1] [2]
Flow model
 Network Optimization Problem

[1] R. Srikant, The Mathematics of Internet Congestion Control, ser.
Systems & Control: Foundations & Applications. Birkhauser Boston, 2004.
[2] F. P. Kelly, A. K. Maulloo, and D. K. H. Tan, “Rate control for communication
networks: shadow prices, proportional fairness and stability,” Journal of the
Operational Research Society, vol. 49, no. 3, pp. 237–252, March 1998.
5/4/2006
EE228A – Communication Networks
7
Various User Utility Functions

Weighted Proportional Fairness

Minimum Potential Delay
Max-Min Fair
General Utility Function [3]


 For
max-min fairness
[3] J. Mo and J. Walrand, “Fair end-to-end window-based congestion control,”
IEEE/ACM Transactions on Networking, vol. 8, no. 5, pp. 556–
567, Oct 2000.
5/4/2006
EE228A – Communication Networks
8
Primal Algorithm and Controller

Primal Algorithm (Lyapunov Function)

Flow Controller
 kr(xr)

> 0 is a non-decreasing, continuous function
Assume prices react instantaneously
5/4/2006
EE228A – Communication Networks
9
Dual Algorithm and Controller

Dual Algorithm

Price Controller
 hl(pl)

> 0 is a non-decreasing continuous function
Assume flows react instantaneously
5/4/2006
EE228A – Communication Networks
10
Primal-Dual Algorithms and other
variants

Can combine primal and dual controllers, and
prove via a Lyapunov function that the algorithm
is globally, asymptotically stable

Other variants exist
 Calculate
prices using a weighted average of the flow
at a link over time
 Setting prices based on fullness of a virtual queue
(Adaptive Virtual Queue, or AVQ)
 Prices are marking probabilities of packets
5/4/2006
EE228A – Communication Networks
11
Examples of Congestion Control
Analysis

Convergence Rate



Time-delay Stability Analysis



Linearize about equilibrium
Look at smallest eigenvalue of dynamics matrix
Linearize about equilibrium
Look at transfer function in the frequency domain and apply
Nyquist stability criterion
Stochastic Stability


5/4/2006
Linearize about equilibrium
Look at Brownian motion perturbations, check induced
covariance of fluctuations
EE228A – Communication Networks
12
Applying TCP/IP congestion control
to wireless sensor networks

Does not account for
wireless networks with:
 interference
from
neighboring paths
 physical channel errors
 Hard to address both, first
pass is to treat as constant
error disturbance like [4]
[5]
[4] M. Chen, A. Abate, and S. Sastry, “New congestion control schemes over
wireless networks: stability analysis,” in Proceedings of the 16th IFAC
World Congress, 2005.
[5] A. Abate, M. Chen, and S. Sastry, “New congestion control schemes
over wireless networks: delay sensitivity analysis and simulations,” in
Proceedings of the 16th IFAC World Congress, 2005.
5/4/2006
EE228A – Communication Networks
13
Properties of Utility and Pricing
Functions

Assumptions on Ur(xr),  r
 is
a non-decreasing, continuously
differentiable, strictly concave function
 Ur(xr)  - as xr  0

Assumptions on prices pl()  l
 is
a non-decreasing, continuous function such
that
5/4/2006
EE228A – Communication Networks
14
Incorporating Latency into Utility

Assign a utility to each packet
 Sigmoidal
5/4/2006
function for differentiability
EE228A – Communication Networks
15
Incorporating Latency into Utility (2)

Integrate delay utility of each packet with
flow
 non-decreasing,
continuously differentiable,
strictly concave (assuming additional flow only
come with greater delay)
 May not be able to meet constraint
Ur(xr)  - as xr  0
5/4/2006
EE228A – Communication Networks
16
Flow Rate vs. Delay and Packet Drop Rate

Delay is a function of
 queuing



delay
Congestion
Errors from wireless channel
CSMA contention
 transmission

Congestion at
merge points
In routing tree
delay (number of hops)
Do not have a good/simple model of CSMA
contention at the MAC layer
 Without
knowing
we have a hard time knowing
for our optimization problem
5/4/2006
EE228A – Communication Networks
17
Hope? Congestion control policies as
an optimization solver with a black box




Some optimization solvers only needs a black box
Make delay part of objective function
Know general trend D = g(x), delay increases with more flow
Treat channel contention, lossy wireless link, inteference, as noise
Congestion Black Box
D = g({xr})
{xr}
Source
Nodes
5/4/2006
D
D
Delay Noise
pl
Lossy
Communication
Channel
EE228A – Communication Networks
pl
Relay
Nodes
18
Design Guidelines for Packet Drop
Policy


May want to use a LIFO queue on a node, to get
latest packets delivered (least delay)
Fairness for packets from different merging
routes suggests round robin service over many
queues
 May
want to prioritize based on time to last delivered
packet

Need to design policy on when to purge LIFO
queues, and how many LIFO queues
 Parameters of policy set by messages from sink
 Given vehicle dynamics, sink can determine how
many targets it can track well
5/4/2006
EE228A – Communication Networks
19
Design Guidelines for Congestion
Feedback Policy

Since low network bandwidth, may not want
end-to-end acknowledgement
 Sparse
end-to-end acknowledgement means cannot
adapt to network changes as quickly

Types of Information
 Queue lengths
 Number of hops to congestion
 Delay on packets delivered

point
Interfering nodes may want to share information
about their respective flow rates and packet
delays
5/4/2006
EE228A – Communication Networks
20
Design Guidelines for Rate
Adaptation Policy
Slow start phase?
 May want evenly spaced samples for
Kalman Filter

 If
within delay constraints, may want to queue
packets to accommodate channel fluctuations

How to decode multiple congestion
indicators from relay nodes (queue length,
delay, number of hops)?
5/4/2006
EE228A – Communication Networks
21
Future Work
Fix a model for simulating the network
 Design a congestion control scheme via
heuristics, and simulate
 If I can get a mathematical model, analyze
its stability and convergence

5/4/2006
EE228A – Communication Networks
22
Extra Slides
5/4/2006
EE228A – Communication Networks
23
Definition of Max-Min Fair
5/4/2006
EE228A – Communication Networks
24
What pursuers really see
5/4/2006
EE228A – Communication Networks
25
Sensor net increases visibility
5/4/2006
EE228A – Communication Networks
26