Delay Efficient Backpressure Routing in Wireless Ad Hoc Networks

Packet scheduling/routing in wireless ad hoc networks is a fundamental problem for ad hoc networking. Backpressure routing is a solid and throughput optimal policy for such networks, but suffers from increased delays. In this article, we present two holistic approaches to improve upon the delay problems of backpressuretype algorithms. We develop two scheduling algorithms, namely Voting backpressure and Layered backpressure routing, which are throughput optimal. We experimentally compare the proposed algorithms against state-of-the-art delay-aware backpressure algorithms, which provide optimal throughput, for different payloads and network topologies, both for static and mobile networks. The experimental evaluation of the proposed delay reduction algorithms attest their superiority in terms of QoS, robustness, low computational complexity and simplicity.