Efficient Approximation Algorithms for Link Scheduling With Power Assignment in Wireless Networks Under SINR and Rayleigh-Fading Models

Abstract

Link scheduling remains a fundamental challenge in wireless networks, as it directly affects critical performance metrics such as throughput, delay, fairness, and energy efficiency. In this paper, we investigate the Maximum Link Scheduling (MLS) and Shortest Link Scheduling (SLS) problems with power assignment, considering two widely adopted interference models: the Signal-to-Interference-plus-Noise Ratio (SINR) model and the Rayleigh fading model. We propose two approximation algorithms: the TMP algorithm for MLS and the TSP algorithm for SLS, both of which employ a class-dependent oblivious power assignment strategy. The validity of these algorithms is established rigorously for both interference models. Our approach classifies the set of links into distinct classes and schedules them by partitioning the link deployment plane associated with each class into small triangular regions. Our theoretical analysis and simulation results demonstrate that the plane partitioning and classification framework outperforms the considered baseline schemes in terms of scheduling efficiency and resource utilization. Moreover, simulation results show that our power assignment method achieves a substantial reduction in energy consumption of nodes compared to competing algorithms.