An improved approximation algorithm for the shortest link scheduling in wireless networks under SINR and hypergraph models

Link scheduling is a fundamental problem in wireless ad hoc and sensor networks. In this paper, we focus on the shortest link scheduling (SLS) under Signal-to-Interference-plus-Noise-Ratio and hypergraph models, and propose an approximation algorithm $$SLS_{pc}$$SLSpc (A link scheduling algorithm with oblivious power assignment for the shortest link scheduling) with oblivious power assignment for better performance than GOW* proposed by Blough et al. [IEEE/ACM Trans Netw 18(6):1701---1712, 2010]. For the average scheduling length of $$SLS_{pc}$$SLSpc is 1 / m of GOW*, where $$m=\lfloor \varDelta _{max}\cdot p \rfloor $$m=źΔmax·pź is the expected number of the links in the set V returned by the algorithm HyperMaxLS (Maximal links schedule under hypergraph model) and $$0