Bounded-hop energy-efficient Broadcast in low-dimensional Metrics via Coresets

Stefan Funke, Soeren Laue

We consider the problem of assigning powers to nodes of a wireless network in the plane such that a message originating from a specific source node $s$ reaches all other nodes within a bounded number $k$ o f transmissions and the total amount of assigned energy is minimized. We show that there exists a $(k,\epsilon)$-coreset for this problem, which is of size independent of $n$. In particular we show that there exists a $(k,\epsilon)$-coreset of size $\bigO(\left(\frac{1}{\epsilon}\ri ght)^{4k})$. Using this coreset we are able to $(1+\epsilon)$-approximate the bounded-hop bro adcast problem in time linear in $n$ which is a drastic improvement upon the previously best known algorithm. While actual network deployments most of the time are in a planar setting, the experienced metric for several reasons is typically not exactly of the Eucli dean type, but often in some sense 'close'. Our algorithm (and others) also work for non-Euclidean metrics pr ovided they exhibit a certain similarity to the Euclidean metric which is known in the literature as \emph{bou nded doubling dimension}. We give a novel characterization of such metrics also pointing out other applications such as space-efficient routing schemes.

Proc. of 24th International Symposium on Theoretical Aspects of Computer Science (STACS) 2007, Aachen