Date Added: Oct 2009
This paper considers the problem of routing packets across a multi-hop wireless network while ensuring throughput optimality. One of the main challenges in the design of throughput optimal routing policies is identifying an appropriate Lyapunov function with negative expected drift. The only known throughput optimal routing policies in the literature, most notably backpressure routing, are constructed using simple node-based quadratic or exponential Lyapunov functions of the queue backlogs and as such exhibit poor delay performance under many network topologies and traffic conditions. By constructing a class of continuous, differentiable, and piece-wise quadratic Lyapunov functions, this paper provides a large class of throughput optimal routing policies.