Joint congestion control and distributed scheduling for throughput guarantees in wireless networks

We consider the problem of throughput-optimal cross-layer design of wireless networks. We propose a joint congestion control and scheduling algorithm that achieves a fraction 1/d(I) (G) of the capacity region, where d(I) (G) depends on certain structural properties of the underlying connectivity graph G of the wireless network and also on the type of interference constraints. For a wide range of wireless networks, d(I) (G) can be upper bounded by a constant, independent of the number of nodes in the network. The scheduling element of our algorithm is the maximal scheduling policy. Although maximal scheduling policy has been considered in many of the previous works, the difficulties that arise in implementing it in a distributed fashion in the presence of interference have not been dealt with previously. In this paper, we propose two novel randomized distributed algorithms for implementing the maximal scheduling policy under the 1-hop and 2-hop interference models.