Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
Local Construction of Spanners in the 3-D Space
verfasst von : Iyad A. Kanj, Ge Xia, Fenghui Zhang
Erschienen in: Distributed Computing in Sensor Systems
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
In this paper we present local distributed algorithms for constructing spanners in wireless sensor networks modeled as
unit ball graphs
(shortly
UBGs
) and
quasi-unit ball graphs
(shortly
quasi-UBGs
), in the 3-dimensional Euclidean space. Our first contribution is a local distributed algorithm that, given a UBG
U
and a parameter
α
<
π
/3, constructs a sparse spanner of
U
with stretch factor 1/(1 − 2sin(
α
/2)), improving the previous upper bound of 1/(1 −
α
) by Althöfer et al. which is applicable only when
$\alpha < 1/(1+2\sqrt{2}) < \pi/3$
. The second contribution of this paper is in presenting the
first
local distributed algorithm for the construction of bounded-degree lightweight spanners of UBGs and quasi-UBGs.
The simulation results we obtained show that, empirically, the weight of the spanners, the stretch factor and locality of the algorithms, are much better than the theoretical upper bounds proved in this paper.