Vous êtes ici : UVSQ RechercheDoctorat

Mécanismes pour la cohérence, l'atomicité et les communications au niveau des clusters : application au clustering hiérarchique distribué adaptatif par François Avril

Présentée par: Monsieur François Avril Discipline: Informatique Laboratoire: PRiSM

Résumé :
Nous nous intéressons dans cette thèse à l’organisation des systèmes distribués dynamiques de grande taille : ensembles de machines capables de communiquer entre elles et pouvant à tout instant se connecter ou se déconnecter. Nous proposons de partitionner le système en groupes connexes, appelés clusters. Afin d'organiser des réseaux de grande taille, nous construisons une structure hiérarchique imbriquée dans laquelle les clusters d'un niveau sont regroupés au sein de clusters du niveau supérieur.
Pour mener à bien ce processus, nous mettons en place des mécanismes permettant aux clusters d'être les nœuds d'un nouveau système distribué exécutant l'algorithme de notre choix. Cela nécessite en particulier des mécanismes assurant la cohérence de comportement pour le niveau supérieur au sein de chaque cluster. En permettant aux clusters de constituer un nouveau système distribué exécutant notre algorithme de clustering, nous construisons une hiérarchie de clusters par une approche ascendante.
Nous démontrons cet algorithme en définissant formellement le système distribué des clusters, et en démontrant que chaque exécution de notre algorithme induit sur ce système une exécution de l'algorithme de niveau supérieur. Cela nous permet, en particulier, de démontrer par récurrence que nous calculons bien un clustering hiérarchique imbriqué.
Enfin, nous appliquons cette démarche à la résolution des collisions dans les réseaux de capteurs. Pour éviter ce phénomène, nous proposons de calculer un clustering adapté du système, qui nous permet de calculer un planning organisant les communications au sein du réseau et garantissant que deux messages ne seront jamais émis simultanément dans la portée de communication de l'un des capteurs.

Abstract :
To manage and handle large scale distributed dynamic distributed systems, constituted by communicating devices that can connect or disconnect at any time, we propose to compute connected subgraphs of the system, called clusters. We propose to compute a hierarchical structure, in which clusters of a level are grouped into clusters of the higher level.
To achieve this goal, we introduce mechanisms that allow clusters to be the nodes of a distinct distributed system, that executes an algorithm. In particular, we need mechanisms to maintain the coherence of the behavior among the nodes of a cluster regarding the higher level. By allowing clusters to be nodes of a distributed system that executes a clustering algorithm, we compute a nested hierarchical clustering by a bottom-up approach.
We formally define the distributed system of clusters, and prove that any execution of our algorithm induces an execution of the higher level algorithm on the distributed system of clusters. Then, we prove by induction that our algorithm computes a nested hierarchical clustering of the system.
Last, we use this approach to solve a problem that appears in sensor networks : collision. To avoid collisions, we propose to compute a clustering of the system. This clustering is then used to compute a communication schedule in which two messages cannot be sent at the same time in the range of a sensor.
Informations complémentaires
Colette JOHNEN, Professeur des Universités, à l’Université de Bordeaux - LaBRI - UMR CNRS 5800 - Bordeaux - Rapporteur
Maria POTOP BUTUCARU, Professeur des Universités, à l’Université de Paris VI - LIP6 - UMR7606 UPMC-CNRS - Paris - Rapporteur
Alain BUI, Professeur des Universités, à l’Université de Versailles Saint-Quentin-en-Yvelines - PRiSM - FRE CNRS 3709 - Versailles - Directeur de thèse
Devan SOHIER, Maître de conférence à l’Université de Versailles Saint-Quentin-en-Yvelines - PRiSM - FRE CNRS 3709 Versailles - Co-Directeur de thèse
Johanne COHEN, Chargée de recherche à l’Université Paris-Sud - LRI - UMR8623 - Paris - Examinateur
Jean-Christophe LAPAYRE, Professeur des Universités, à l’Université de Franche-Comté - FEMTO-ST - UMR CNRS 6174 - Besançon - Examinateur
Contact :
DREDVal service FED :