We consider the problem of assigning powers to nodes of a wireless network in the plane such that a message from a source node
reaches all other nodes within a bounded number
of transmissions and the total amount of assigned energy is minimized. By showing the existence of a
we are able to (1 +
)-approximate the bounded-hop broadcast problem in time
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.