# 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

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

$(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:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

| 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},`

`}`