Efficient Link Scheduling in Wireless Networks Under Rayleigh-Fading and Multiuser Interference

Link scheduling plays a key role in the network capacity and the transmission delay. In this paper, we study the problem of maximum link scheduling (MLS), aiming to characterize the maximum number of links that can be successfully scheduled simultaneously under Rayleigh-fading and multiuser interference. After analyzing the minimum distance between successful links in the existing GHW scheduling algorithm, we propose a DLS (Distance-based Link Scheduling) algorithm. Then, the global interference is characterized and bounded by introducing a separation distance between selected links, building on which we propose a distributed version of DLS (denoted by DDLS) that converges to a constant factor of the non-fading optimum within time complexityO(nln n), wherenis the number of links. Furthermore, we study the Shortest Link Scheduling (SLS) problem, which minimizes the number of time slots to successfully schedule each link for at least once. An algorithm for SLS with approximation factor ofO(ln n)is obtained by executing DDLS. Extensive simulations show that DDLS greatly outperforms GHW and the other two popular algorithms.