A flexible framework for polynomial-time resource allocation in multiflow wireless networks

We introduce the problem of joint routing, scheduling and power control for multiple information flows in half-duplex, interference limited ad-hoc networks. The joint problem of optimizing for throughput is NP-Hard, and so we present an approximation of the problem and a general framework for solving it in O(N³) time. We attack the problem in two ways, first by presenting a reformulation and decomposition of the joint optimization, and second by providing a framework and data structure to manage the decomposition and its associated complexity. The generality of our approach permits its application to a wide variety of optimality criteria, including delay-constrained routing and minimum-cost routing. Simulation results demonstrate the execution of our algorithms on large networks, where we see significant gains in both throughput and power savings.