Randomized Algorithms for Cross-Layer Network Control

We study the problem of joint congestion control and scheduling in wireless networks. We model the wireless network as a directed graph G=(V, E), where V denotes the set of nodes and E denotes the set of wireless links between the nodes. We propose a joint congestion control and scheduling scheme that achieves a fraction d₁(G) of the capacity region, where d₁(G) depends on certain structural properties of graph G as well as the nature of interference constraints. For specific families of graphs, which can represent a wide variety of wireless networks, d₁(G) has been upper bounded by a factor independent of the number of nodes in the network for a wide range of interference models. The scheduling element of our joint congestion control and scheduling scheme is the maximal scheduling policy considered in many of the earlier works. Although, it is widely believed to be amenable to distributed implementation, no algorithms have been proposed for its implementation, except under the node-exclusive interference model which is suitable only for networks in which adjacent nodes can transmit over non-interfering channels. We propose a randomized algorithm for implementing maximal scheduling policy under a 2-hop interference model which is suitable for networks with a limited number of non-interfering channels (e.g., IEEE 802.11 DSSS networks)