Using linear programming to minimize interference in wireless sensor networks

Abstract

Interference in wireless sensor networks can have a significant impact on power consumption and throughput. In this paper, we address the problem of finding a network topology that minimizes the maximum interference experienced by any sensor in the network. In the standard interference model, each sensor interferes with every other sensor within its communication range. We approach the problem of minimizing interference by creating a linear relaxation to a similar problem with a different interference model. Using randomized rounding, this relaxation gives an O(OPT*log n) approximation to this new problem. We then show that this solution is an O(OPT^2*log n) approximation to minimize the maximum interference using the standard interference model. If OPT=O(log n) (as is the case in most networks), this is an improvement over existing best known O(OPT*sqrt(n)) approximation. Additionally, we perform several experiments using simulated sensor networks where our algorithm often significantly outperforms its theoretical bounds.