This work considers efficient transmission scheduling in a multi-hop wireless network with unreliable channels. The broadcast nature of the wireless channel enables a single transmission to be overheard by a subset of potential receivers, increasing the probability of successful reception. This multi-receiver diversity can lead to significant gains in throughput and energy efficiency, although it creates an exponentially growing set of decision options.

We present a simple and optimal algorithm that overcomes the exponential system complexity via a queue backpressure principle. This is the Diversity Backpressure Routing algorithm (DIVBAR). The DIVBAR algorithm compares favorably (in metrics of throughput and power) to alternative approaches that use heuristics such as Geographic Random Forwarding (GeRaF) and Extremely Opportunistic Routing (ExOR), although delay may be worse in a low-rate regime. An "enhanced" E-DIVBAR algorithm that combines backpressure with a shortest path metric is also developed and shown to provably provide throughput and energy optimality, and simulations show that E-DIVBAR is also very delay efficient.

In the figure shown, we illustrate the shortcomings of alternative approaches. Suppose the algorithm simply routes packets to the successful receiver that is closest to the destination. In this case, a packet may go from node 1 to 2 to 3, and then be deadlocked because there are no other nodes in transmission range that are closest to the destination. In this case, it is best to temporarily move in directions that are further from the destination to achieve an optimal path. Backpressure techniques can learn optimal routing and scheduling decisions, often even when mobility patterns and channel statistics are unknown. In the graph shown, a delay comparison of ExOR, DIVBAR, and E-DIVBAR is given for a particular network. Note the vertical asymptote of DIVBAR and E-DIVBAR are at network capacity, whereas ExOR is not throughput optimal and hence has a vertical asymptote that is less than capacity.

Learn More:

M. J. Neely and R. Urgaonkar, "Optimal Backpressure Routing in Wireless Networks with Multi-Receiver Diversity," Ad Hoc Networks (Elsevier), vol. 7, no. 5, pp. 862-881, July 2009. [Slides from CISS 2006].
M. J. Neely and R. Urgaonkar, Opportunism, Backpressure, and Stochastic Optimization with the Wireless Broadcast Advantage," Asilomar Conference on Signals, Systems, and Computers, Pacific Grove, CA, Oct. 2008 (invited paper).
L. Georgiadis, M. J. Neely, L. Tassiulas, "Resource Allocation and Cross-Layer Control in Wireless Networks," Foundations and Trends in Networking, Vol. 1, no. 1, pp. 1-144, 2006.
M. J. Neely, "Energy Optimal Control for Time Varying Wireless Networks", IEEE Transactions on Information Theory, vol. 52, no. 7, pp. 2915-2934, July 2006. [Slides from Infocom 2005]