Abstract
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 in many ways like forming backbones, facilitating routing, improving scaling, aggregating information and saving power. A (k,r)-clustering assigns cluster heads so that exists k cluster heads within r communication hops for all nodes in the network while trying to minimize the total number of cluster heads.We present the first self-stabilizing distributed (k,r)-clustering algorithm. The algorithm uses synchronous communication rounds and uses multiple paths to different cluster heads for providing improved security, availability and fault tolerance. From any starting configuration the algorithm quickly assigns enough cluster heads and stabilizes towards a local minimum using a randomized scheme.
The research leading to these results has received funding from the Swedish Civil Contingencies Agency (MSB) and has received funding from the European Union Seventh Framework Programme (FP7/2007-2013) under grant agreement n° 257007.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Caron, E., Datta, A.K., Depardon, B., Larmore, L.L.: A self-stabilizing k-clustering algorithm using an arbitrary metric. In: Sips, H., Epema, D., Lin, H.-X. (eds.) Euro-Par 2009. LNCS, vol. 5704, pp. 602–614. Springer, Heidelberg (2009)
Chen, Y.P., Liestman, A.L., Liu, J.: Clustering Algorithms for Ad Hoc Wireless Networks, vol. 2, ch. 7, pp. 154–164. Nova Science Publishers, Bombay (2004)
Dolev, S.: Self-Stabilization. MIT Press, Cambridge (March 2000)
Dolev, S., Tzachar, N.: Empire of colonies: Self-stabilizing and self-organizing distributed algorithm. Theoretical Computer Science 410(6-7), 514–532 (2009)
Johnen, C., Nguyen, L.H.: Robust self-stabilizing weight-based clustering algorithm. Theoretical Computer Science 410(6-7), 581–594 (2009)
Larsson, A., Philippas, T.: Self-stabilizing (k, r)-clustering in wireless ad-hoc networks with multiple paths. Technical report, Chalmers University of Technology (2010)
Spohn, M.A., Garcia-Luna-Aceves, J.J.: Bounded-distance multi-clusterhead formation in wireless ad hoc networks. Ad Hoc Networks 5(4), 504–530 (2007)
Sun, K., Peng, P., Ning, P., Wang, C.: Secure distributed cluster formation in wireless sensor networks. In: ACSAC 2006, Washington, DC, USA, pp. 131–140. IEEE Computer Society, Los Alamitos (2006)
Wu, Y., Li, Y.: Construction algorithms for k-connected m-dominating sets in wireless sensor networks. In: MobiHoc 2008, pp. 83–90. ACM, New York (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Larsson, A., Tsigas, P. (2010). Self-stabilizing (k,r)-Clustering in Wireless Ad-hoc Networks with Multiple Paths. In: Lu, C., Masuzawa, T., Mosbah, M. (eds) Principles of Distributed Systems. OPODIS 2010. Lecture Notes in Computer Science, vol 6490. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-17653-1_6
Download citation
DOI: https://doi.org/10.1007/978-3-642-17653-1_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-17652-4
Online ISBN: 978-3-642-17653-1
eBook Packages: Computer ScienceComputer Science (R0)