A journal version of this paper exists and is recommended:



Journal Version:
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.


Conference Version:
M. J. Neely, E. Modiano, and C.E. Rohrs, "Dynamic Power Allocation and Routing for Time Varying Wireless Networks," IEEE INFOCOM Proceedings, April 2003. SLIDES

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]).