Optimal Distributed Scheduling in Wireless Networks Under the SINR Interference Model

In wireless networks, the design of radio resource sharing mechanisms is complicated by the complex interference constraints among the various links. In their seminal paper (IEEE Trans. Autom. Control, vol. 37, no. 12, pp. 1936–1948), Tassiulas and Ephremides introduced Maximum Weighted Scheduling, a centralized resource sharing algorithm, and proved its optimality. Since then, there have been extensive research efforts to devise distributed implementations of this algorithm. Recently, distributed adaptive CSMA scheduling schemes have been proposed and shown to be optimal, without the need of message passing among transmitters. However, their analysis relies on the assumption that interference can be accurately modeled by a simple interference graph. In this paper, we consider the more realistic and challenging signal-to-interference-plus-noise ratio (SINR) interference model. We present distributed scheduling algorithms that: 1) are optimal under the SINR interference model; and 2) do not require any message passing. These algorithms are based on a combination of a simple and efficient power allocation strategy referred to as Power Packing and randomization techniques. The optimality of our algorithms is illustrated in various traffic scenarios using numerical experiments.