Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


Power assignment problems in wireless communication

Funke, Stefan and Laue, Sören and Naujoks, Rouven and Zvi, Lotker

MPI-I-2006-1-004. December 2007, 25 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
A fundamental class of problems in wireless communication is concerned
with the assignment of suitable transmission powers to wireless
devices/stations such that the
resulting communication graph satisfies certain desired properties and
the overall energy consumed is minimized. Many concrete communication
tasks in a
wireless network like broadcast, multicast, point-to-point routing,
creation of a communication backbone, etc. can be regarded as such a
power assignment problem.

This paper considers several problems of that kind; for example one
problem studied before in (Vittorio Bil{\`o} et al: Geometric Clustering
to Minimize the Sum
of Cluster Sizes, ESA 2005) and (Helmut Alt et al.: Minimum-cost
coverage of point sets by disks, SCG 2006) aims to select and assign
powers to $k$ of the
stations such that all other stations are within reach of at least one
of the selected stations. We improve the running time for obtaining a
solution for this problem from $n^{((\alpha/\epsilon)^{O(d)})}$ as
reported by Bil{\`o} et al. (see Vittorio Bil{\`o} et al: Geometric
Clustering to Minimize the Sum
of Cluster Sizes, ESA 2005) to
$O\left( n+ {\left(\frac{k^{2d+1}}{\epsilon^d}\right)}^{ \min{\{\;
2k,\;\; (\alpha/\epsilon)^{O(d)} \;\}} } \right)$ that is, we obtain a
running time that is \emph{linear}
in the network size. Further results include a constant approximation
algorithm for the TSP problem under squared (non-metric!) edge costs,
which can be employed to
implement a novel data aggregation protocol, as well as efficient
schemes to perform $k$-hop multicasts.

References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-2006-1-004.pdf176 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document:
Hide details for BibTeXBibTeX
  AUTHOR = {Funke, Stefan and Laue, S{\"o}ren and Naujoks, Rouven and Zvi, Lotker},
  TITLE = {Power assignment problems in wireless communication},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-2006-1-004},
  MONTH = {December},
  YEAR = {2007},
  ISSN = {0946-011X},