Approximation Algorithms for Maximum Weight Independent Set of Links Under the SINR Model

作者：Wang Lixin^*; Xu Xiaohua

来源：Ad Hoc & Sensor Wireless Networks, 2013, 17(3-4): 293-311.

• Physical interference model
• approximation algorithm
• maximum independent set
• link scheduling

We study the following optimization problem in a plane multihop wireless network under the physical interference model. Given a multihop wireless network and a positive link weight (or demand) function, select a set of independent links whose total weight is maximized. This problem is known to be NP-hard. The best known approximation algorithms for this problem achieved logarithmic-factor approximation bounds with either the uniform power assignment or the power control setting. In this paper, we present two approximation algorithms for the problem with pre-specified power assignments. The first algorithm uses the oblivious power assignment and achieves constant approximation bound under certain mild assumptions. The second algorithm achieves constant approximation bound when the link weight-to-length ratio is bounded. Moreover, our constant approximation bounds are valid regardless of the value of the noise power.

• 出版日期2013