A journal version of this paper exists and is recommended:
M. J. Neely, E. Modiano, and C. E. Rohrs,
"Dynamic Power Allocation and Routing for Time Varying Wireless Networks,"
IEEE Journal on Selected Areas in Communications, Special Issue on
Wireless Ad-Hoc Networks, vol. 23, no. 1, pp. 89-103, Jan. 2005.
M. J. Neely, E. Modiano, and C.E. Rohrs, "Dynamic Power
Allocation and Routing for Time Varying Wireless Networks,"
IEEE INFOCOM Proceedings, April 2003.
Back to M. J. Neely homepage
Comments: This paper develops an on-line crosslayer control algorithm
for stabilizing a general network with time
varying channels and user mobility. Note that this includes networks
with random disconnections or link outages.
We first describe the
network layer capacity region (characterizing all rate matrices
that the network can stably support). Then, assuming the incoming traffic
rates are within the capacity region, we construct an algorithm
that yields optimal
throughput without requiring knowledge of channel statistics or
user mobility patterns. The algorithm makes use of Lyapunov drift
theory, and generalizes the Tassiulas-Ephremides backpressure policy
developed in their seminal 1992 paper that introduced Lyapunov drift
as a tool for stability analysis of queueing networks:
"Stability properties of constrained
queueing systems and scheduling policies for maximum throughput in
multihop radio networks" [IEEE Trans. Autom. Control, 1992].
Specifically, we show that throughput optimal networking can be reduced to
solving a particular wireless MAC problem every timeslot (involving
maximizing a weighted sum of link transmission rates and differential
backlog). This problem may or may not be difficult to solve every
timeslot, depending on the physical interference properties of the
network. However, the policy
has a simple distributed
implementation in the case when data channels of the network are independent. Also, a
(sub-optimal) distributed implementation is provided for a wireless
network with full user interference. The sub-optimal scheme achieves
a scaled version of the capacity region, and is evaluated for
a mobile network and compared to the Grossglauser-Tse
2-hop relay algorithm.
Further, "approximately" solving the max-differential backlog MAC metric
every slot to within a constant factor gamma yields throughput
that is within gamma of the capacity
region (see Neely Ph.d. thesis 2003, Chapter 4.3.6). A related idea
is the "imperfect scheduling" results developed recently
from a convex
optimization perspective in Li, Shroff Infocom 2005.
Note 1: In this paper we also define a general notion of queue stability, and
provide a framework for delay analysis of networks with bursty traffic
and non-iid channel states. The journal version treats the general
ergodic channel and arrival case, such as Markov modulated arrivals
and channel states (see also my thesis, chapter 4).
Further, this work reveals a fundamental relationship between
Lyaupunov drift, stable
queueing policies, and convex optimization for multi-commodity flow problems
(see Section VII of the
journal paper, and/or Chapter 4 of
my Ph.D. thesis (MIT LIDS 2003).
Note 2: Implementations of the algorithm for power allocation in
satellite downlinks and
satellite constellation networks are described
in my Ph.D. thesis, and
the satellite downlink problem for independent downlinks
is described in
our earlier work [Infocom 2002, TON 2003].
Note 3: Extensions that treat optimal fairness for general wireless, wireline,
or packet switch networks in the case when traffic is either inside
or outside of the capacity region, and algorithms that yield minimum
average energy expenditure or that maximize throughput subject to
strict average energy constraints, are given in [Infocom fairness] and [Infocom energy]. This work develops two new Lyapunov drift theorems
(the first in terms of a "reward" function, the second in terms of a "cost"
function) that allow stability and
performance optimization to be achieved simultaneously (see also Chapter 5
of my Ph.D. thesis [MIT LIDS 2003]).