Special Issue – Advances in Parallel and Distributed Computational ModelsNo Access

AN ADAPTIVE RANDOM WALK BASED DISTRIBUTED CLUSTERING ALGORITHM

PRiSM (UMR CNRS 8144), Université de Versailles-Saint-Quentin-en-Yvelines 45, avenue des Etats-Unis, 78035 Versailles Cedex, France

Search for more papers by this author

ABDURUSUL KUDIRETI

CReSTIC-SysCom, Université de Reims Champagne Ardenne, BP 1039 - 51687 Reims Cedex 2, France

Search for more papers by this author

, and

DEVAN SOHIER

PRiSM (UMR CNRS 8144), Université de Versailles-Saint-Quentin-en-Yvelines 45, avenue des Etats-Unis, 78035 Versailles Cedex, France

Search for more papers by this author

https://doi.org/10.1142/S0129054112400370Cited by:3 (Source: Crossref)

Abstract

In this paper, we present a fully distributed random walk based clustering algorithm intended to work on dynamic networks of arbitrary topologies.

A bounded-size core is built through a random walks based procedure. Its neighboring nodes that do not belong to any cluster are recruited by the core as ordinary nodes. Using cores allow us to formulate constraints on the clustering and fulfill them on any topology.

The correctness and termination of our algorithm are proven. We also prove that when two clusters are adjacent, at least one of them has a complete core (i.e. a core with the maximum size allowed by the parameter).

One of the important advantages of our mobility-adaptive algorithm is that the re-clustering is local: the management of the connections or disconnections of links and reorganization of nodes affect only the clusters in which they are, possibly adjacent clusters, and at worst, the ordinary nodes of the clusters adjacent to the neighboring clusters. This allows us to bound the diameter of the portion of the network that is affected by a topological change.

Keywords:

References

D. J. Baker and A. Ephremides, IEEE Transactions on Communications 29(11), 1694 (1981). Crossref, Web of Science, Google Scholar
A. Ephremides, J. E. Wieselthier and D. J. Baker, Proceedings of IEEE 75(1), 56 (1987). Crossref, Web of Science, Google Scholar
Abhay K. Parekh, ITS (1994). Google Scholar
M. Gerla and J. T.-C. Tsai, ACM Baltzer Journal of Wireless Networks 1(3), 255 (1995). Crossref, Web of Science, Google Scholar
S. Basagni, Distributed clustering for ad hoc networks, Proceedings of the 1999 International Symposium on Parallel Architectures, Algorithms and Networks (1999) pp. 310–315. Google Scholar
S. Basagni, Distributed and mobility-adaptive clustering for multimedia support in multi-hop wireless networks, Proceedings of the 50th IEEE International Vehicular Technology Conference (1999) pp. 889–893. Google Scholar
C. Johnen and L. Nguyen, Theor. Comput. Sci. 410(6-7), 581 (2009). Crossref, Web of Science, Google Scholar
D. Beinet al., A self-stabilizing link-cluster algorithm in mobile ad hoc networks, Proceedings of the 8th International Symposium on Parallel Architectures, Algorithms and Networks(ISPAN'05) (2005) pp. 436–441. Google Scholar
Y. Fernaes and D. Malkhi, K-clustering in wireless ad hoc networks, In the 2nd ACM international workshop on Principles of mobile computing (2002) pp. 31–37. Google Scholar
F. G. Nocetti, J. S. Gonzalez and I. Stojmenovic, In wireless networks. Telecommunication Systems 22(1-4), 205 (2003). Crossref, Web of Science, Google Scholar
Sulyun Sung, Yuhwa Seo and Yongtae Shin, Hierarchical Clustering Algorithm Based on Mobility in Mobile Ad Hoc Networks, ICCSA (2006) pp. 954–963. Google Scholar
N. Mittonet al., Self-stabilization in self-organized multihop wireless networks, Proceedings of the 25th IEEE International Conference on Distributed Computing Systems Workshops(WWAN'05) (2005) pp. 909–915. Google Scholar
N. Mitton , A. Busson and E. Fleury , Self-organization in large scale ad hoc networks , Proceedings of the third Annual Mediterranean Ad Hoc Networking Workshop(MED-HOC-NET'04) ( 2004 ) . Google Scholar
T. H. P. V. Alanet al., Max-min d-cluster formation in wireless ad hoc networks, IEEE INFOCOM (2000) pp. 32–41. Google Scholar
Satu Elisa Schaeffer, Computer Science Review 1, 27 (2007). Crossref, Web of Science, Google Scholar
A. Bui and D. Sohier, Fundamenta Informaticae 80(4), 363 (2007). Web of Science, Google Scholar
C. Rabat, Studia Informatica Universalis 7, (2009). Google Scholar