Using linear programming to minimize interference in wireless sensor networks

Thumbnail Image

Persistent link to this item

View Statistics

Journal Title

Journal ISSN

Volume Title


Using linear programming to minimize interference in wireless sensor networks

Published Date




Thesis or Dissertation


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.


University of Minnesota M.S. thesis. September 2013. Major: Computer Science. Advisor: Nikolaos Papanikolopoulos. 1 computer file (PDF); iii, 16 pages.

Related to



Series/Report Number

Funding information

Isbn identifier

Doi identifier

Previously Published Citation

Suggested citation

Holec, Eric. (2013). Using linear programming to minimize interference in wireless sensor networks. Retrieved from the University Digital Conservancy,

Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.