Characterizing Achievable Rates in Multihop Networks: The Joint Routing and Scheduling Problem

This paper considers the problem of determining the achievable rates in multihop wireless networks. We consider the problem of jointly routing the flows and scheduling transmissions to achieve a given rate vector. We develop tight necessary and sufficient conditions for the achievability of the rate vector. We develop efficient and easy to implement Fully Polynomial Time Approximation Schemes for solving the routing problem. The scheduling problem is solved as a coloring problem. We show that this approach guarantees that the solution obtained is within 67% of the optimal solution in the worst case and in practice is typically within about 80% of the optimal solution. The approach that we use is quite flexible and seems like a promising approach to handle more sophisticated interference conditions, multiple antennas and routing with diversity requirements.