We consider the problem of assigning powers to nodes of a wireless network in the plane such that a message from a source
node
s reaches all other nodes within a bounded number
k of transmissions and the total amount of assigned energy is minimized. By showing the existence of a
coreset of size
O(([1/(e)])4k)O(\left({{1}\over{\epsilon}}\right)^{4k})
we are able to (1 +
ε)-approximate the bounded-hop broadcast problem in time
linear in
n which is a drastic improvement upon the previously best known algorithm.
While actual network deployments often are in a planar setting, the experienced metric for several reasons is typically not
exactly of the Euclidean type, but in some sense ’close’. Our algorithm (and others) also work for non-Euclidean metrics provided
they exhibit a certain similarity to the Euclidean metric which is known in the literature as bounded doubling dimension. We give a novel characterization of such metrics also pointing out other applications such as space-efficient routing schemes.
This work was supported by the Max Planck Center for Visual Computing and Communication (MPC-VCC) funded by the German Federal
Ministry of Education and Research (FKZ 01IMC01).