A general class of throughput optimal routing policies in multi-hop wireless networks

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 appropriate and universal Lyapunov functions with negative expected drift. The few well-known throughput optimal routing policies in the literature are constructed using simple quadratic or exponential Lyapunov functions of the queue backlogs and as such they do not use any metric of closeness to the destination. Consequently, these routing policies exhibit poor delay performance under many network topologies and traffic conditions. By considering a class of continuous, differentiable, and piece-wise quadratic Lyapunov functions, this paper provides a large class of throughput optimal routing policies. The proposed class of Lyapunov functions allow for the routing policies to control the traffic along short paths for a large portion of state-space while ensuring a negative expected drift, hence, enabling the design of routing policies with much improved delay performance. In particular, an opportunistic routing policy with congestion diversity is proved to be throughput optimal.