TSLS and TSLSU: Two Novel Approximation SINR-Based Shortest Link Scheduling Algorithms in Wireless Networks

In this paper, we address the fundamental problem of shortest link scheduling (SLS) in wireless networks under the Signal-to-Interference-plus-Noise-Ratio (SINR) constraints and propose two efficient Triangle-based Shortest Link Scheduling (TSLS and TSLSU) algorithms by assuming both oblivious power control and uniform power assignment scenarios. Many existing algorithms, to solve SLS under the SINR constraints, partition the set of links into classes and for each class, schedule the links by partitioning the link deployment plane into small regions. In this paper, we present a new triangle-based method for plane partitioning, showing that it significantly improves efficiency by increasing the number of simultaneously schedulable same-color regions. Consequently, more links can be activated within a time slot compared to other partitioning methods. Theoretical analysis indicates the correctness and effectiveness of our algorithms. Theoretical analysis demonstrates that our plane partition and approximation ratios are respectively much more efficient and tighter than those of state-of-the-art algorithms' results. In summary, both theoretical analysis and simulation results confirm that our algorithms offer superior performance in terms of efficiency and solution quality compared to the state-of-the-art algorithms.