Clustering hiérarchique et adaptatif à base de marches aléatoires
Institution:
Versailles-St Quentin en YvelinesDisciplines:
Directors:
Abstract EN:
We propose in this work size-oriented distributed clustering algorithms aimed at large-scale dynamic distributed networks. The clusters we build are of size between K and 2K, with K a parameter of the algorithm and we build cluster spanning trees to allow for their organization. We present a first algorithm to compute a binary hierarchy of nested disjoint clusters in static networks. A token browses the network randomly and recruits nodes to its cluster. When a cluster reaches a maximal size defined by the parameter K, it is divided (when possible), and tokens are created in both new clusters. The naming process used for the clusters, along with the information stored during each division, allows routing between any two clusters. Next, we present a version o this algorithm adaptive to topological changes. The algorithm is made resistant to topological changes through the broadcast of renaming messages in clusters. We have developed methods allowing the management of a topological change inside a cluster. They divide into 2 a hierarchical structure that does not meet the specification any longer, and merge them. Last, we present a silent self-stabilizing clustering algorithm. Based on a different approach, we forbid that two adjacent clusters are both of size less than K. We build a cluster tree rooted in an elected node.
Abstract FR:
Nous proposons dans ces travaux des algorithmes distribués de clustering basé sur la taille destinés à créer des structures adaptatives pour les réseaux distribués dynamiques à large échelle. Nous construisons des clusters dont la taille est comprise entre K et 2K, avec K un paramètre de l'algorithme et nous construisons des arbres couvrants des clusters pour permettre leur organisation. Après avoir donné une spécification pour ce problème, nous présentons un premier algorithme distribué pour le résoudre. Les clusters grandissent en recrutant des nœuds à l'aide d'un jeton se déplaçant aléatoirement dans le réseau et sont divisés quand c'est possible en deux clusters disjoints composés d'au moins K nœuds. Ce processus, associé à une identification binaire permet la construction hiérarchique de clusters imbriqués avec un mécanisme de communication inter et intra-cluster. Dans un second algorithme, nous appliquons notre méthode de construction à des réseaux dynamiques. La résistance de notre algorithme aux changements topologiques est obtenue par la diffusion de messages de renommage dans les clusters. Nous avons développé des méthodes permettant de gérer un changement topologique à l'intérieur d'un cluster. Elles permettent de séparer en deux une structure hiérarchique de clusters ne respectant plus la spécification, puis de les fusionner. Nous présentons enfin un algorithme silencieux de clustering auto-stabilisant. Avec une approche différente, nous interdisons la construction de deux clusters adjacents dont la taille est inférieure à K. Nous construisons un arbre de clusters enraciné en un nœud élu comme leader.