Title :
A general class of throughput optimal routing policies in multi-hop wireless networks
Author :
Naghshvar, M. ; Zhuang, H. ; Javidi, T.
Author_Institution :
Dept. of Electr. & Comput. Eng., Univ. of California San Diego, La Jolla, CA, USA
fDate :
Sept. 30 2009-Oct. 2 2009
Abstract :
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.
Keywords :
Lyapunov methods; ad hoc networks; delays; diversity reception; telecommunication congestion control; telecommunication network routing; telecommunication network topology; congestion diversity; delay; multihop wireless networks; network topology; piecewise quadratic Lyapunov functions; routing packets problem; throughput optimal routing policy; traffic control; Cost function; Delay; Lyapunov method; Network topology; Relays; Routing; Spread spectrum communication; Throughput; Traffic control; Wireless networks;
Conference_Titel :
Communication, Control, and Computing, 2009. Allerton 2009. 47th Annual Allerton Conference on
Conference_Location :
Monticello, IL
Print_ISBN :
978-1-4244-5870-7
DOI :
10.1109/ALLERTON.2009.5394513