On the clustering of mobile ad hoc networks
Contribution à la clusterisation dans les réseaux mobiles ad hoc
Résumé
This thesis is about clustering of mobile ad hoc networks, which consists in building some sets of nodes, called clusters, in order to introduce hierarchy in the network and thus improve its scalability. The main goal is to design new distributed clustering algorithms suited to i) unstructured networks, where all the nodes are equal, and suited to ii) structured networks that have an inherent hierarchical structure, and in which the nodes are gathered in operational groups. In order to allow the implementation of a radio resource allocation process that is more efficient within clusters than between clusters, the proposed algorithms form clusters satisfying specific topology constraints: connectivity, maximum size and diameter. In the first part of the thesis, to compare these new solutions to the ones from the literature, independently to the medium access scheme, we introduce network cost functions which take into account the user traffic profil and the intra-cluster and inter-cluster communication costs. Then, we propose a distributed clustering algorithm suited to structured networks, and compare its performance to several clustering schemes from the literature. A salient feature of this algorithm is that it does not need to resort to the notion of cluster-head. In the last part, thanks to the coalition game theory we revisit this algorithm. This theoretical framework allows us to formalize the clustering problem in a more general context. This leads us to defining a generic algorithm suitable to any kind of ad hoc network, and enables us to acquire a better knowledge of its properties.
Cette thèse traite de la clustérisation des réseaux ad hoc mobiles. Ce mécanisme consiste à rassembler les noeuds du réseau en grappes appelés clusters, dans le but d'introduire de la hiérarchie dans le réseau, et ainsi de permettre son passage à l'échelle. L'objectif principal est de concevoir de nouveaux algorithmes distribués de clustérisation, adaptés aux réseaux non structurés, où tous les noeuds sont des pairs, ainsi qu'aux réseaux structurés, où il existe déjà une structure hiérarchique intrinsèque. Dans le but de permettre une allocation des ressources radio à l'intérieur des clusters plus efficace qu'entre les clusters, les algorithmes proposés forment des clusters qui satisfont certaines contraintes de topologie : la connectivité, une taille et un diamètre maximaux. Afin d'évaluer les performances de ces nouvelles solutions, comparativement à celles de la littérature, et de manière indépendante des mécanismes d'accès au canal radio employés, la première partie de la thèse introduit des fonctions de coût de réseau, qui incorporent le profil de trafic utilisateur ainsi que les coûts de communication intra-cluster. Ensuite, un algorithme distribué adapté aux réseaux structurés est proposé, et ses performances comparées par simulation à plusieurs autres solutions de la littérature. Une caractéristique originale de cet algorithme est qu'il ne fait pas appel à la notion de chef de cluster. Dans la dernière partie, grâce à la théorie des jeux de coalition nous revisitons l'algorithme précédemment proposé pour les réseaux structurés. Ce cadre théorique permet de formaliser le problème de la clustérisation dans un contexte plus général, et conduit à la définition d'un algorithme générique, applicable à tous types de réseaux, ainsi qu'à une meilleure connaissance théorique de ses propriétés.
Origine : Version validée par le jury (STAR)