La clustérisation des réseaux sans fil ad hoc : une approche efficace et performante

El Bazzal, Zouhair (2008). La clustérisation des réseaux sans fil ad hoc : une approche efficace et performante. Thèse de doctorat électronique, Montréal, École de technologie supérieure.

Prévisualisation	PDF Télécharger (81MB) | Prévisualisation
Prévisualisation	PDF Télécharger (11MB) | Prévisualisation

Résumé

Un réseau sans fil Ad hoc consiste en un groupe de noeuds mobiles facilement déployables sans l'existence d'une infrastructure préexistante. Chaque noeud joue le rôle d'un hôte/routeur et utilise le canal radio comme le seul moyen de communication. Le routage classique s'appuie souvent sur une vue à plat du réseau Ad hoc et utilise un mécanisme d'inondation des paquets de contrôle afin de maintenir les routes. Cette inondation crée des problèmes d'utilisation inefficace des ressources en termes de traitement, de capacité, d'énergie et de bande passante. Aucun protocole de routage ne permet le déploiement à grande échelle du réseau Ad hoc; la raison principale est le manque d'une hiérarchie.

Dans cette thèse, nous proposons de découper le réseau en clusters afin de réduire la complexité de la topologie et de bâtir un réseau mis à l'échelle. Chaque cluster comprend un chef qui joue le rôle d'un point d'accès mobile. Nous pouvons ainsi imaginer une dorsale virtuelle dynamique servant d'une part à acheminer le trafic de contrôle entre les chefs d'une manière fiable et efficace et d'autre part, de limiter l'effet des changements de topologie et des conditions des noeuds dans les clusters adjacents. Le choix du noeud-chef est sujet à plusieurs critères en termes de performances (stabilité, mobilité, énergie, capacité, etc.). Ces critères constituent des métriques à considérer dans les calculs analytiques et les simulations.

Pour que les clusters puissent s'adapter dynamiquement aux changements de l'environnement, nous avons proposé un mécanisme de maintenance distribuée permettant de gérer les adhésions, les handoff des noeuds et la réélection des noeuds-chefs. Parallèlement, un modèle analytique élaboré a été proposé pour faire les estimations nécessaires des paramètres de qualité de service. Ce qui nous a également permis d'intégrer un mécanisme de contrôle d'admission sur les noeuds-chefs, permettant d'éviter les congestions et toutes les perturbations intraclusters. Ceci nous a amené à balancer la charge entre les différents clusters et d'optimiser l'utilisation des ressources du réseau ^ ^ hoc. Les résultats numériques obtenus nous ont aidés à réajuster les paramètres utilisés dans la clustérisation afin de fournir une meilleure qualité de service aux applications utilisées.

Finalement, pour valider nos résultats, nous avons défini quelques paramètres utiles à l'étude des performances du modèle. Les résultats des simulations ont clairement montré le niveau de stabilité des clusters en présence de mobilité et en termes de nombre de clusters formés, nombre de ré-affiliations, nombre de transitions sur les chefs, niveau de qualité de service globale, équilibrage de charge et passage à l'échelle. Nous avons aussi remarqué une meilleure connectivité et un niveau de stabilité élevé en comparant notre modèle avec un autre de la littérature et en présence de mobilité.

Titre traduit

Clustering in wireless ad hoc networks: an efficient and performant approach

Résumé traduit

In recent years, most research is focusing on clustering approaches for Ad hoc networks because of its effectiveness in building a virtual backbone formed by a set of suitable clusterhead (CH) to guarantee the communications across clusters. Clustering has been proven to be a promising approach for mimicking the operation of the fixed infrastructure and managing the resources in Ad hoc networks. An Ad hoc network is characterized by a collection of wireless nodes which communicate with each other using high-frequency radio waves. These nodes arbitrarily and randomly change their locations and capabilities without the aid of any fixed infrastructure.

We propose a clustering algorithm in order to elect suitable nodes' representatives, i.e. CH and to store minimum topology information by reducing the propagation of routing information which facilitates the spatial reuse of resource and increase the system capacity. We use the node degree, the remaining battery power, the transmission power, and the node mobility for the CH's election. Each CH will act as a temporary base station within its zone or cluster and communicates with other CHs. Thus, packets for route finding may only spread among CHs instead of flooding among all nodes. On the other hand, the topology change information caused by movement of some nodes is limited in adjacent clusters, not in the whole network.

The clusters must adapt dynamically to the environment changes, we proposed a distributed maintenance procedure that allows managing nodes' adhesion, nodes' handoff and the re-election of the CHs. In parallel, an elaborate analytical model was proposed to estimate the quality of service parameters (local allowed saturation throughput, delay and packet error rate). Based on the results from the analytical model, we implement a new admission control algorithm in order to determine the number of members inside a cluster that can be accommodated while satisfying the constraints imposed by the current applications. In this matter, the estimated knowledge of the number of members sharing a cluster might effectively drive congestion avoidance on the CH and interclusters load-balancing to achieve better network resource utilization. The obtained results will help us to readjust the used parameters of the clustering algorithm in order to provide better maintenance and quality of service guarantees depending on the used applications.

Through numerical analysis and simulations, we have studied the performance of our model and compared it with that of other existing algorithms. The results demonstrate the superior performance of the proposed model in terms of number of clusters, number of re-affiliations, number of transitions (state change) on CH, quality of service, load balancing and scalability. We also observed how the connectivity and the stability are maximized when the number of nodes increases in presence of mobility.

Type de document:	Mémoire ou thèse (Thèse de doctorat électronique)
Renseignements supplémentaires:	"Thèse présentée à l'École de technologie supérieure comme exigence partielle à l'obtention du doctorat en génie". Bibliogr : f. [190]-205.
Mots-clés libres:	Réseaux ad hoc (Réseaux d'ordinateur) Réseaux locaux sans fil. Performance des réseaux. Ordinateurs Entretien et réparations. cluster, echelle, maintenance, qualité de service, mise à l'échelle
Directeur de mémoire/thèse:	Directeur de mémoire/thèse Kadoch, Michel
Programme:	Doctorat en génie > Génie
Date de dépôt:	18 mars 2011 16:07
Dernière modification:	13 déc. 2016 20:50
URI:	https://espace.etsmtl.ca/id/eprint/158

Gestion Actions (Identification requise)

Dernière vérification avant le dépôt