Anzeige
Erschienen in:
2007 | OriginalPaper | Buchkapitel
Bounded-Hop Energy-Efficient Broadcast in Low-Dimensional Metrics Via Coresets
verfasst von : Stefan Funke, Sören Laue
Erschienen in: STACS 2007
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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(\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.