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

摘要

We study the following optimization problem in a plane multihop wireless network under the physical interference model. Given a multi-hop 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 cither 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.