Using linear programming to minimize interference in wireless sensor networks

Loading...
Thumbnail Image

Persistent link to this item

Statistics
View Statistics

Journal Title

Journal ISSN

Volume Title

Title

Using linear programming to minimize interference in wireless sensor networks

Published Date

2013-09

Publisher

Type

Thesis or Dissertation

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.

Description

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

Related to

Replaces

License

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, https://hdl.handle.net/11299/162351.

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.