CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

A self-stabilizing (k,r)-clustering algorithm with multiple paths for wireless Ad-hoc networks

Andreas Larsson (Institutionen för data- och informationsteknik, Nätverk och system, Datakommunikation och distribuerade system (Chalmers)) ; Philippas Tsigas (Institutionen för data- och informationsteknik, Nätverk och system, Datakommunikation och distribuerade system (Chalmers))
31st International Conference on Distributed Computing Systems, ICDCS 2011; Minneapolis, MN; 20 June 2011 through 24 June 2011 p. 353-362 . (2011)
[Konferensbidrag, refereegranskat]

Wireless Ad-hoc networks are distributed systems that often reside in error-prone environments. Self-stabilization lets the system recover autonomously from an arbitrary state, making the system recover from errors and temporarily broken assumptions. Clustering nodes within ad-hoc networks can help forming backbones, facilitating routing, improving scaling, aggregating information, saving power and much more. We present the first self-stabilizing distributed (k,r)-clustering algorithm. A (k, r)-clustering assigns k cluster heads within r communication hops for all nodes in the network while trying to minimize the total number of cluster heads. The algorithm uses synchronous communication rounds and uses multiple paths to different cluster heads for improved security, availability and fault tolerance. The algorithm assigns, when possible, at least k cluster heads to each node within O(r) rounds from an arbitrary configuration. The set of cluster heads stabilizes, with high probability, to a local minimum within O(gr log n) rounds, where n is the size of the network and g is an upper bound on the number of nodes within 2r hops.



Den här publikationen ingår i följande styrkeområden:

Läs mer om Chalmers styrkeområden  

Denna post skapades 2011-10-05. Senast ändrad 2012-02-02.
CPL Pubid: 146854

 

Läs direkt!


Länk till annan sajt (kan kräva inloggning)