Weighted wireless link scheduling without information of positions and interference/communication radii

Link scheduling is a fundamental design issue in multihop wireless networks. All existing link scheduling algorithms require the precise information of the positions, and/or communication/interference radii of all nodes. For practical networks, it is not only difficult or expensive to obtain these parameters, but also often impossible to get their precise values. The link scheduling determined by the imprecise values of these parameters may fail to guarantee the same approximation bounds of the link scheduling determined by precise values. Therefore, the existing link scheduling algorithms lack performance robustness. In this paper, we propose a robust link scheduling, which can be easily computed with only the information on whether a given pair of links have conflict or not and therefore is robust. In addition, our link scheduling does not compromise the approximation bound and indeed sometimes can achieve better approximation bound. Particularly, under the 802.11 interference model, its approximation bound is 16 in general and 6 with uniform interference radii, an improvement over the respective best-known approximation bounds 23 and 7. © 2011 IEEE.