Computer Science – Computational Geometry
Scientific paper
2006-12-22
Computer Science
Computational Geometry
13 pages
Scientific paper
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 \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+\epsilon)$-approximate solution for this problem from $n^{((\alpha/\epsilon)^{O(d)})}$ as reported by Bilo et al. (\cite{Bilo}) to $O(n+ {(\frac{k^{2d+1}}{\epsilon^d})}^{\min{\{2k, (\alpha/\epsilon)^{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.
Funke Stefan
Laue Soeren
Lotker Zvi
Naujoks Rouven
No associations
LandOfFree
Power Assignment Problems in Wireless Communication does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Power Assignment Problems in Wireless Communication, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Power Assignment Problems in Wireless Communication will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-531053