License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2015.529
URN: urn:nbn:de:0030-drops-56243
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5624/
Go to the corresponding LIPIcs Volume Portal

Halldórsson, Magnús M. ; Tonoyan, Tigran

The Price of Local Power Control in Wireless Scheduling

pdf-format:
8.pdf (0.5 MB)

Abstract

We consider the problem of scheduling wireless links in the physical model, where we seek an assignment of power levels and a partition of the given set of links into the minimum number of subsets satisfying the signal-to-interference-and-noise-ratio (SINR) constraints. Specifically, we are interested in the efficiency of local power assignment schemes, or oblivious power schemes, in approximating wireless scheduling. Oblivious power schemes are motivated by networking scenarios when power levels must be decided in advance, and not as part of the scheduling computation.

We present the first O(log log Delta)-approximation algorithm, which is known to be best possible (in terms of Delta) for oblivious power schemes, where Delta is the longest to shortest link length ratio. We achieve this by representing interference by a conflict graph, which allows the application of graph-theoretic results for a variety of related problems, including the weighted capacity problem. We explore further the contours of approximability and find the choice of power assignment matters; that not all metric spaces are equal; and that the presence of weak links makes the problem harder. Combined, our results resolve the price of local power for wireless scheduling, or the value of allowing unfettered power control.

BibTeX - Entry

@InProceedings{halldrsson_et_al:LIPIcs:2015:5624,
  author =	{Magn{\'u}s M. Halld{\'o}rsson and Tigran Tonoyan},
  title =	{{The Price of Local Power Control in Wireless Scheduling}},
  booktitle =	{35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
  pages =	{529--542},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-97-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{45},
  editor =	{Prahladh Harsha and G. Ramalingam},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5624},
  URN =		{urn:nbn:de:0030-drops-56243},
  doi =		{10.4230/LIPIcs.FSTTCS.2015.529},
  annote =	{Keywords: Wireless Scheduling, Physical Model, Oblivious Power}
}

Keywords: Wireless Scheduling, Physical Model, Oblivious Power
Collection: 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)
Issue Date: 2015
Date of publication: 14.12.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI