max planck institut
informatik

MPI-I-2006-1-004

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
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
$(1+\epsilon)$-approximate
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.

Acknowledgement:
References to related material:

176 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: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/2006-1-004
BibTeX
@TECHREPORT{FunkeLaueNaujoksZvi2006,
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},
}