The Power of Non-Uniform Wireless Power

Magnús M. Halldórsson, Stephan Holzer, Pradipta Mitra, Roger Wattenhofer

Abstract

We study a fundamental measure for wireless interference in the SINR model known as (weighted) inductive independence. This measure characterizes the effectiveness of using oblivious power — when the power used by a transmitter only depends on the distance to the receiver — as a mechanism for improving wireless capacity. We prove optimal bounds for inductive independence, implying a number of algorithmic applications. An algorithm is provided that achieves — due to existing lower bounds — capacity that is asymptotically best possible using oblivious power assignments. Improved approximation algorithms are provided for a number of problems for oblivious power and for power control, including distributed scheduling, connectivity, secondary spectrum auctions, and dynamic packet scheduling.
BibTeX
@inproceedings{halldorsson2013power,
  author = {Magnús M. Halldórsson and Stephan Holzer and Pradipta Mitra and Roger Wattenhofer},
  title = {{The Power of Non-Uniform Wireless Power}},
  booktitle = {SODA},
  year = {2013},
  doi = {10.1137/1.9781611973105.114},
}

Loading related content...

Figure