Shortest Link Scheduling Algorithms in Wireless Networks Under the SINR Model.

This paper considers the shortest link scheduling problem in wireless networks under the signal-to-interference-plus-noise ratio (SINR) model. We propose an $O({}\log({}l_{\max}/l_{\min}{}){})-approximation algorithm called shortest link scheduling with power control (SLSPC) with oblivious power assignment and an O(\log1+\varphi(l\max/l\min)-approximation algorithm called shortest link scheduling with uniform or mean power assignment (SLSUM) with uniform or mean power control, where \varphi > 0 is a constant serving as a regulatory factor for slight transmit power adjustment, and where l\max and l\min denote the lengths of the longest and shortest links, respectively. We conduct a rigorous theoretical performance analysis to analyze the feasibility and approximation factors of the proposed algorithms. We also carry out an extensive comparison-based simulation study, whose results indicate that the performances of SLSPC and SLSUM are superior over the state of the art as the set of the so-called “black and gray” links, which are difficult to schedule and should be sequentially scheduled, is completely removed by adjusting the transmit power appropriately via $\varphi$. Our numerical analysis demonstrates that the approximation ratios of our algorithms are tighter than the best known ratios. [ABSTRACT FROM PUBLISHER]