Construction et maintenance d'une dorsale virtuelle dans les réseaux AD HOC mobiles

Mnif, Kais (2006). Construction et maintenance d'une dorsale virtuelle dans les réseaux AD HOC mobiles. Thèse de doctorat électronique, Montréal, École de technologie supérieure.

Prévisualisation

PDF Télécharger (6MB) | Prévisualisation

Résumé

Un réseau ad hoc mobile est un réseau complètement distribué ne nécessitant pas d'infrastructure fixe. Les terminaux sont libres de se déplacer n'importe quand et dans n'importe quelle direction. L'absence d'une infrastructure nécessite la collaboration de tous les terminaux pour acheminer le trafic d'une source vers une destination. De nombreux protocoles de routage ont été proposés pour assurer le relayage multi saut, utilisant différentes approches (réactives, proactives et hybrides). Toutefois, les performances de ces protocoles se dégradent en présence de la mobilité. Dans cette thèse, nous proposons d'améliorer la performance des protocoles de routage dans les réseaux ad hoc en construisant une dorsale virtuelle.

Une dorsale virtuelle est un sous-ensemble de noeuds sélectionnés de façon à ce que chaque noeud dans le réseau possède au moins un voisin dans la dorsale. L'ensemble des noeuds qui forment la dorsale doit être toujours maintenu connecté même quand les noeuds changent de position. Plus la taille de la dorsale est minimale, plus la maintenance est efficace. Pour construire la dorsale, nous avons proposé un nouvel algorithme basé sur l'approximation de l'ensemble de domination connexe de taille minimale (MCDS). Un réseau ad hoc est généralement modélisé par un graphe à disque unitaire UDG (Unit Disc Graph). Trouver l'ensemble MCDS dans un graphe UDG est un problème NP-Complet. Dans le but de réduire cette complexité, nous avons décomposé le problème en deux étapes: la première étape consiste à déterminer l'ensemble de domination connexe (MDS) au moyen d'une formulation en programmation linéaire et la deuxième étape consiste à trouver l'arbre de recouvrement de l'ensemble MDS et en déduire l'ensemble MCDS. Les résultats de simulations montrent bien que la solution donnée par notre algorithme est très proche de celle fournie par l'analyse théorique. De plus, la taille de la dorsale est nettement inférieure comparée à d'autres algorithmes proposés dans la littérature quand la taille du réseau augmente.

Nous avons également proposé une procédure de maintenance distribuée. Cette procédure est basée sur un échange simple des messages de contrôle hello modifiés, ces messages étant utilisés pour la découverte au voisinage. Un noeud qui change de position va alors appliquer cette procédure pour se connecter à la dorsale. Une maintenance locale de la dorsale sera effectuée dans la zone où le noeud va se retrouver dans sa nouvelle position. Les résultats de simulation ont démontré l'efficacité et la fiabilité de cette approche. En effet, plus de 90% des noeuds restent connectés pour une mobilité élevée (vitesse moyenne égale à 30 m/s). De plus, cette procédure est peu sensible au facteur de mise à l'échelle (Scalability). La nature distribuée de la procédure de maintenance s'adapte bien à la dynamique de la structure du réseau engendrée par le mouvement des noeuds.

Dans le but de vérifier l'amélioration apportée par la présence d'une dorsale pour les protocoles de routage dans les réseaux ad hoc mobiles, nous avons comparé les performances de certains protocoles de routage, en fonction de la mobilité, en présence de la dorsale avec leurs performances dans leurs versions standards. Les résultats de simulations ont démontré qu'une amélioration de leurs performances peut atteindre 20% pour certains protocoles même pour une mobilité élevée.

En conclusion, ce travail de recherche présente de nouvelles solutions pour différents problèmes reliés au routage dans les réseaux ad hoc mobiles.

Titre traduit

Construction and maintenance of virtual backbone in mobile AD HOC networks

Résumé traduit

Mobile ad hoc networks are totally distributed which do not need a fixed infrastructure and terminals are free to move anywhere at anytime. The absence of an infrastructure requires collaboration of all the terminals to forward traffic from a source to a destination. Many routing protocols have been proposed to ensure the multi hop relaying, with either reactive, proaçtive or hybrid approach. However, the performance of these protocols degrades when mobility is present. In this thesis, a virtual backbone based routing protocol is proposed and evaluated for mobile ad hoc networks.

A virtual backbone is a subset of selected nodes with each node having at least one neighbour in the backbone. Nodes forming the backbone should be stay connected even when the nodes move. Smaller the size of the backbone, the better the maintenance will be. A new algorithm to build the backbone based on the computation of the minimum connected dominating set (MCDS) is proposed. An ad hoc network is modelled by a graph has dise unit UDG (Unit Graph Disc).Finding MCDS in a graph UDG is a NPComplet problem. In order to reduce the complexity, we divide the problem in two steps: the first step computes the minimum dominating set (MDS) using a linear programming formulation and the second step determines the spanning tree of the MDS set, then we deduce the MCDS. Simulation results show that the solution given by our algorithm is very close solution to the one given by analysis. Moreover, the size of the backbone is significantly lower compared with other proposed algorithms.

A distributed procedure for maintaining the connectivity of the backbone is also proposed. It is based on a simple exchange of the modified control message hello. A node which changes its position then will apply this procedure to be connected to the dorsal. A local maintenance of the backbone will be realized, only in the zone where the node is moved. Simulation results show the effectiveness and the reliability of this approach. Indeed, more than 90% of the nodes remain connected for a high mobility (average speed 30 m/s). Moreover, this procedure is not very sensitive to the scalability. The distributed nature makes maintenance procedure adapt well to the dynamic of the network structure caused by nodes movement.

In order to verify the improvement achieved by the presence of a backbone for routing protocols in mobile ad hoc networks. We make comparison of three existing protocols with and without a virtual backbone. Simulation results show that an improvement of 20% can be achieved for some protocols with high mobility.

In summary, this dissertation presents new results in many current problems regarding routing in wireless ad hoc networks.

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. 197-205.
Mots-clés libres:	Ad, Construction, Diffusion, Dorsale, Fil, Hoc, Maintenance, Mobile, Performance, Protocole, Reseau, Routage, Sans, Virtuel
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:	16 mars 2011 20:34
Dernière modification:	03 nov. 2016 23:58
URI:	https://espace.etsmtl.ca/id/eprint/537

Gestion Actions (Identification requise)

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