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(lmax/lmin))-approximation algorithm called shortest link scheduling with power control (SLSPC) with oblivious power assignment and an O(log1+φ(lmax/lmin)-approximation algorithm called shortest link scheduling with uniform or mean power assignment (SLSUM) with uniform or mean power control, where φ>0 is a constant serving as a regulatory factor for slight transmit power adjustment, and where lmax and lmin 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 φ. Our numerical analysis demonstrates that the approximation ratios of our algorithms are tighter than the best known ratios.