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(\log_{1+\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.