2006/12/22 by Stefan Funke, Funke, Stefan, Laue, Soeren +3
Computer Science · Engineering · #Advanced MIMO Systems Optimization #Computational Geometry (cs.CG) #Cooperative Communication and Network Coding #FOS: Computer and information sciences #Hardware Architecture (cs.AR) #Mobile Ad Hoc Networks #Networking and Internet Architecture (cs.NI)
paper · pdf · doi:10.48550/arxiv.cs/0612121
openalex publication_date 2006/12/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
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 \citeCarrots, 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. (\citeBilo) to O(n+ (\frack2d+1εd)^min\2k, (α/ε)O(d) \) that is, we obtain a running time that is 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.