Power assignment problems in wireless communication: Covering points by disks, reaching few receivers quickly, and energy-efficient travelling salesman tours
✍ Scribed by Stefan Funke; Sören Laue; Zvi Lotker; Rouven Naujoks
- Publisher
- Elsevier Science
- Year
- 2011
- Tongue
- English
- Weight
- 327 KB
- Volume
- 9
- Category
- Article
- ISSN
- 1570-8705
No coin nor oath required. For personal study only.
✦ Synopsis
In this paper, we present approximation algorithms for a variety of problems occurring in the design of energy-efficient wireless communication networks. We first study the k-station network problem, where for a set S of stations and some constant k, one wants to assign transmission powers to at most k senders such that every station in S can receive a signal from at least one sender. We give a (1 + )-approximation algorithm for this problem. The second problem deals with energy-efficient networks, allowing bounded hop multicast operations, that is given a subset C of the stations S and a designated source node s 2 S, we want to assign powers to the sending stations, such that every node in C can be reached by a transmission from s within k hops. For this problem, we provide an algorithm which runs in time linear in jSj. The last problem deals with a variant of the non-metric TSP problem where the edge costs correspond to the Euclidean distances to the power of some a P 1; this problem is motivated by data aggregation schemes in wireless sensor networks.
We provide a simple constant approximation algorithm, which improves upon previous results when 2 6 a 6 2.7.