Polynomial Complexity Algorithms for Full Utilization of Multi-Hop Wireless Networks

In this paper, we provide and study a general framework that allows the development of distributed mechanisms to achieve full utilization of multi-hop wireless networks. In particular, we describe a generic randomized routing, scheduling and flow control scheme that is applicable to a large class of interference models, and that allows for the development of distributed algorithms which maximize network throughput and utilization. In particular, we focus on a specific interference model, namely the secondary interference model, and develop distributed algorithms with polynomial communication and computation complexity in the network size. This is an important result given that earlier throughput-optimal algorithms developed for such a model relies on the solution to an NP-hard problem. This results in a polynomial complexity cross-layer algorithm that achieves throughput optimality and fair allocation of network resources amongst the users. We further show that our algorithmic approach enables us to efficiently approximate the capacity region of a multi-hop wireless network.