Low-complexity scheduling for wireless networks
Guanhong Pei, Anil Kumar S. Vullikanti · 2012
Designing efficient scheduling and power control algorithms for distributed wireless communication has been a challenging issue, especially in the physical interference model based on SINR constraints. In this paper, we discuss the first local distributed scheduling and power control algorithm in the SINR model that achieves an O(g(L)) approximation factor of the rate region, where O(g(L)) denotes the link diversity. As an intermediate step, we develop a scheduling algorithm in a k-hop interference model, which is used in the analysis of the more general model. Our algorithms are based on random-access and use local queue size information. Exchanging queue size information is challenging, and the complexity of this step is often ignored in prior local distributed algorithms. A novel aspect of our paper is the use of stale and infrequently updated queue size info, which significantly improves the complexity of our algorithms.