Auto-stabilisation et partitionnement dans les réseaux Ad Hoc
Institution:
Paris 11Disciplines:
Directors:
Abstract EN:
The clustering problem consists in partitioning network nodes into groups called clusters, thus giving at the network a hierarchical organization. The self-stabilization is an approach which tolerates to the transient faults. This approach tolerates a temporary interruption of the system service and an inconsistent behavior of several processors, but guarantees a return to the normal in finite time. Basagni proposed two clustering algorithms (called DMAC and GDMAC) in an Ad Hoc network. However they are not self-stabilizing. In the first time we proposed a self-stabilizing version of DMAC and GDMAC. In the self-stabilization, no property is guaranteed during the phase of convergence. In the second time we presented a robust version of the self-stabilizing algorithm GDMAC. The property of robustness guarantees that, starting from an arbitrary state, very quickly the network is partitioned into clusters. Then the system continues to build an optimal partition. In the last time we proposed the first self-stabilizing clustering algorithm where the clusters have a bounded size. A bound on the size of a cluster ensures that the leaders are not overloaded by their tasks of leader.
Abstract FR:
Le problème de partitionnement consiste à partitionner les nœuds d’un réseau en grappes donc donner au réseau une organisation hiérarchique. L’auto-stabilisation est une approche qui tolère les défaillances transitoires. Cette approche tolère une interruption temporaire du service du système et un comportement inconsistant de certains processeurs, mais garantit un retour à la normale au bout d’un temps fini. Basagni a proposé deux algorithmes de partitionnement (appelés DMAC et GDMAC) dans un réseau ad hoc. Cependant ils ne sont pas auto-stabilisants. Dans un premier temps nous avons proposé une version auto-stabilisante de DMAC et GDMAC. Dans l’auto-stabilisation, aucune propriété n’est garantie durant la phase de convergence. Donc le système peut avoir un comportement complètement arbitraire durant toute la phase de convergence. Dans un deuxième temps nous avons présenté une version robuste de l’algorithme auto-stabilisant GDMAC. La propriété de robustesse garantit que, à partir d’un état arbitraire, très rapidement le réseau est partitionné en grappes. Ensuite, le système continue à construire une partition optimale. Dans le dernier temps nous avons proposé le premier algorithme auto-stabilisant de partitionnement où les grappes ont une taille bornée. Une borne sur la taille d’une grappe assure que les leaders ne sont pas surchargés par leurs tâches de leader.