Using linear programming to minimize interference in wireless sensor networks

Holec, Eric
2013-09
No Thumbnail Available

View/Download File

Holec_umn_0130M_14323.pdf (419.77 KB)

Persistent link to this item

https://hdl.handle.net/11299/162351
Statistics
View Statistics

Journal Title

Journal ISSN

Volume Title

Title

Using linear programming to minimize interference in wireless sensor networks

Authors

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.

Keywords

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

Collections

Master's Theses (Plan A and Professional Engineering Design Projects)

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.