Gesellschaft für Informatik e.V.

Lecture Notes in Informatics

10th International Conferenceon Innovative Internet Community Systems (I2CS) - Jubilee Edition 2010 - P-165, 20-29 (2010).

Gesellschaft für Informatik, Bonn

Copyright © Gesellschaft für Informatik, Bonn


Self-stabilizing tree and cluster management for dynamic networks

Olivier Flauzac , Bachar Salim Haggar and Florent Nolot


The lack of infrastructure and dynamic nature of mobile ad hoc networks demand new networking strategies to be implemented in order to provide efficient end-to-end communication. Some researches proposed to organize the network into groups called clusters and use different routing protocols for inter and intra cluster to propagate an information. But with these solutions, the network needs first to be organized into clusters and next, we need to construct each routing table. Other researchers proposed to build a spanning tree on the network to forward informations on a tree but many solutions need to know the global network topology. In this paper, we propose a self-stabilizing algorithm both to construct cluster and simultaneously build a spanning tree on the network. Without any global knowledge, we use only one type of periodically exchanged messages of size $Log(5n + 3)$ bits, and we construct clusters and the spanning tree on the network with a convergence time of at most D+6 rounds.

Full Text: PDF

Gesellschaft für Informatik, Bonn
ISBN 978-3-88579-259-8

Last changed 04.10.2013 18:31:20