2005 | OriginalPaper | Buchkapitel
An Efficient Distributed Algorithm for Finding Virtual Backbones in Wireless Ad-Hoc Networks
verfasst von : B. Paul, S. V. Rao, S. Nandi
Erschienen in: High Performance Computing – HiPC 2005
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
A minimum connected dominating set is an efficient approach to form a virtual backbone for ad-hoc networks. We propose a tree based distributed time/message efficient approximation algorithm to compute a small connected dominating set without using geographic positions. The algorithm has
O
(
n
) time,
O
(
n
log
n
) message complexity, and has an approximation factor of eight. The algorithm is implemented using dominating set simulation program, which shows that our method gives smaller connected dominating set than the existing methods.