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.
PDF