SINR based shortest link scheduling with oblivious power control in wireless networks

In this paper, we consider shortest link scheduling (SLS), a fundamental problem in wireless networks to improve the network performance, under the signal-to-interference-plus-noise-ratio (SINR) constraints. It is challenging to design efficient SLS algorithms due to the intrinsic non-locality of SINR. However, if two transmission links are far away from each other, the interference of one link on the other should be small under the SINR model. This motivates us to consider the interference only in a local area, which decreases the difficulty of designing link scheduling under SINR, by partitioning the links into disjoint local link sets with a certain distance away from each other, such that independent scheduling inside each local link set is possible. Based on this idea, we propose a novel approximation algorithm PPSLS (Plane Partition based Shortest Link Scheduling) for SLS with oblivious power control. Theoretical analysis and simulations demonstrate the correctness and effectiveness of the proposed algorithm.