Distributed algorithms for maximum throughput in wireless networks

The optimal control of multi-hop wireless networks is a major research and design challenge due, in part, to the interference between nodes, the time-varying nature of the communication channels, the energy limitation of mobile nodes, and the lack of centralized coordination. This problem is further complicated by the randomness of data traffic arrivals. Although a complete solution to the problem is still elusive, a major advance is made in the seminal work of Tassiulas and Ephremides [1992], which obtains a throughput optimal routing and link activation policy without a priori knowledge of arrival statistics. The policy operates on the Maximum Differential Backlog (MDB) principle, which essentially seeks to achieve load-balancing in the network. The MDB policy has been extended to multi-hop networks with general capacity constraints in Neely et al. [2003]. There remains, however, a significant difficulty in applying the MDB policy to practical wireless networks. The mutual interference between wireless links implies that the evaluation of the MDB policy involves a centralized optimization. On the other hand, effective control strategies for large-scale wireless networks require distributed implementations with low control messaging overhead. Motivated by this concern, we investigate the distributed implementation of the MDB algorithm within interference-limited CDMA wireless networks, where transmission on any given link potentially interferes with transmissions on all other active links.