A maximum clique based approximation algorithm for wireless link scheduling under SINR model

摘要

In this paper, we focus on the shortest link scheduling (SLS) in wireless networks under the Signal-to-Interference-plus-Noise-Ratio (SINR) constraints. We introduce a consistent graph G¯=(V¯,E¯) where V¯ is the links set and each edge in E¯ indicates that its two ends can be active simultaneously. We interpret SLS as the finding of a clique partition in G¯ and propose a fast approximation algorithm, MCBS (Maximum Clique Based Scheduling), for SLS with a uniform power assignment and with an approximation ratio to the optimal solution of O(1). Theoretical analysis demonstrates the correctness and effectiveness of the proposed algorithm. Our simulation results show that the MCBS algorithm overcomes the best known algorithms in terms of execution time and the number of time slots.