The power of non-uniform wireless power

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

doi:10.1137/1.9781611973105.114

The power of non-uniform wireless power

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

Department of Computer Science

Reykjavik University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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.

Original language	English
Title of host publication	Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013
Publisher	Association for Computing Machinery, Inc
Pages	1595-1606
Number of pages	12
ISBN (Print)	9781611972511
DOIs	https://doi.org/10.1137/1.9781611973105.114
Publication status	Published - 2013
Event	24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013 - New Orleans, LA, United States Duration: 6 Jan 2013 → 8 Jan 2013

Publication series

Name	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Conference

Conference	24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013
Country/Territory	United States
City	New Orleans, LA
Period	6/01/13 → 8/01/13

Access to Document

10.1137/1.9781611973105.114

Cite this

Halldórsson, M. M., Holzer, S., Mitra, P., & Wattenhofer, R. (2013). The power of non-uniform wireless power. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013 (pp. 1595-1606). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms). Association for Computing Machinery, Inc. https://doi.org/10.1137/1.9781611973105.114

@inproceedings{adac91e7b72344f2ba839e7d0113eb2a,

title = "The power of non-uniform wireless power",

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.",

author = "Halld{\'o}rsson, \{Magn{\'u}s M.\} and Stephan Holzer and Pradipta Mitra and Roger Wattenhofer",

year = "2013",

doi = "10.1137/1.9781611973105.114",

language = "English",

isbn = "9781611972511",

series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Association for Computing Machinery, Inc",

pages = "1595--1606",

booktitle = "Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013",

note = "24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013 ; Conference date: 06-01-2013 Through 08-01-2013",

}

Halldórsson, MM, Holzer, S, Mitra, P & Wattenhofer, R 2013, The power of non-uniform wireless power. in Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery, Inc, pp. 1595-1606, 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, LA, United States, 6/01/13. https://doi.org/10.1137/1.9781611973105.114

The power of non-uniform wireless power. / Halldórsson, Magnús M.; Holzer, Stephan; Mitra, Pradipta et al.
Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013. Association for Computing Machinery, Inc, 2013. p. 1595-1606 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - The power of non-uniform wireless power

AU - Halldórsson, Magnús M.

AU - Holzer, Stephan

AU - Mitra, Pradipta

AU - Wattenhofer, Roger

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/84876056319

U2 - 10.1137/1.9781611973105.114

DO - 10.1137/1.9781611973105.114

M3 - Conference contribution

SN - 9781611972511

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1595

EP - 1606

BT - Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013

PB - Association for Computing Machinery, Inc

T2 - 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013

Y2 - 6 January 2013 through 8 January 2013

ER -

The power of non-uniform wireless power

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this