Power Assignment Problems in Wireless Communication

Simple item page
dc.creatorFunke, Stefan
dc.creatorLaue, Soeren
dc.creatorLotker, Zvi
dc.creatorNaujoks, Rouven
dc.date2006-12-22
dc.date.accessioned2026-07-07T07:36:46Z
dc.date.available2026-07-07T07:36:46Z
dc.descriptionA 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 \cite{Carrots, Bilo} 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+ε)$-approximate solution for this problem from $n^{((α/ε)^{O(d)})}$ as reported by Bilo et al. (\cite{Bilo}) to $O(n+ {(\frac{k^{2d+1}}{ε^d})}^{\min{\{2k, (α/ε)^{O(d)} \}}})$ 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.
dc.description13 pages
dc.identifierhttps://arxiv.org/abs/cs/0612121
dc.identifierhttp://arxiv.org/abs/cs/0612121
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/120544
dc.subjectComputational Geometry
dc.subjectHardware Architecture
dc.subjectNetworking and Internet Architecture
dc.titlePower Assignment Problems in Wireless Communication
dc.typetext

Files

Collections

arXiv