Soutenance mémoire
Classification des protocoles de routage
Réseau mobile Ad Hoc (MaNet)
Les réseaux ad hoc auxquels nous nous sommes intéressés sont ceux décrits et étudiés par le groupe de travail MANET (Mobile Ad hoc NETworks) de l’IETF (l’Internet Engineering Task Force). Une définition de ces réseaux est donnée formellement dans la RFC 2501 .
Un réseau mobile ad hoc est formé dynamiquement par un ensemble de nœuds mobiles qui sont reliés par l’intermédiaire des liens sans fil, sans recours à une infrastructure préexistante ou à une administration centralisée. Les nœuds sont libres de se déplacer aléatoirement et de s’organiser arbitrairement, ainsi la topologie du réseau peut changer rapidement et de manière imprévisible.
Les réseaux mobiles ad hoc sont des réseaux sans infrastructure puisqu’ils n’exigent aucune infrastructure fixe telle qu’une station de base pour leur fonctionnement. Les itinéraires dans un réseau ad hoc peuvent inclure des sauts multiples pour atteindre une cible demandée, et par conséquent, il est approprié d’appeler de tels réseaux « les réseaux ad hoc sans fil de multi-Sauts».
Protocoles de routage proactifs
Les approches proactives de routage, conçues pour les réseaux ad hoc, sont dérivés des protocoles traditionnels du vecteur d’état et à vecteur de distance développés pour l’usage dans les réseaux filaires. La caractéristique primaire des approches proactives est que chaque nœud dans le réseau maintient un itinéraire à tous les autres nœuds dans le réseau à tout moment. La création et l’entretien d’itinéraire sont accomplis par une combinaison des mises à jour périodiques et par le déclenchement des événements :
Les mises à jour périodiques se font par des échanges d’informations de routage entre les nœuds dans des intervalles de temps prédéfinis, indépendamment des caractéristiques de mobilité et du trafic du réseau.
Les mises à jour par le déclenchement d’événements, se faites par des échanges d’informations de routage toutes les fois qu’un certain événement est produit, tel qu’une addition de liens ou un déplacement d’un nœud. Dans ce cas, le taux de mobilité affecte directement la fréquence des mises à jour parce que les changements de lien se produisent à mesure que la mobilité augmente.
Protocoles de routage réactifs
Les techniques de routage réactives, également appelées le routage sur demande, adoptent une approche très différente par rapport aux protocoles proactifs. Une grande partie des frais de contrôle des protocoles proactifs proviennent du besoin de chaque nœud de maintenir un itinéraire vers chaque autre nœud du réseau et à tout moment. Dans un réseau filaire, où les modèles de connectivité changent rarement et les ressources sont abondantes, maintenant la connectivité totale du graphe a des dépenses valables. Dans un réseau ad hoc, cependant, la connectivité de lien peut changer fréquemment et les frais généraux de contrôle sont coûteux. Pour ses raisons, les approches réactives de routage ont prit place aux approches de routage proactives. Ces approches réactives ne maintiennent pas, sans interruption, des itinéraires entre les nœuds du réseau. Au lieu de cela, les itinéraires sont seulement découverts quand ils sont réellement nécessaires. Quand un nœud source veut envoyer des paquets de données à une certaine destination, il vérifie sa table d’itinéraire à la recherche d’itinéraire vers cette destination. Si aucun itinéraire n’est trouvé, il lance une procédure de découverte d’itinéraire pour trouver un chemin à la destination. Par conséquent, la découverte d’itinéraire devient sur demande. Si deux nœuds ne doivent jamais communiquer entre eux, alors ils n’ont pas besoin d’utiliser leurs ressources pour le maintien d’un chemin entre eux. La découverte d’itinéraire se faite typiquement par l’inondation du réseau par des messages de demande d’itinéraire. Pour réduire les frais généraux, le secteur de recherche peut être réduit par un certain nombre d’optimisations.
Protocoles basés sur le positionnement
Les protocoles basés sur le positionnement éliminent certaines limitations des protocoles basés sur la topologie en utilisant des informations additionnelles. Elles exigent des informations sur les positions physiques des nœuds. Généralement, chaque nœud détermine sa propre position par l’utilisation du GPS ou un autre type de service de localisation , un aperçu de ces méthodes peut être trouvé dedans . Un service de localisation est employé par l’expéditeur d’un paquet pour déterminer la position de la destination et pour l’inclure dans l’adresse de destination du paquet.
La décision de routage à chaque nœud est alors basée sur la position de la destination contenue dans le paquet et la position des voisins du nœud expéditeur. Le routage basé sur le positionnement n’exige pas l’établissement ou l’entretien des itinéraires. Ainsi Les nœuds n’ont pas à stocker ni des tables de routage ni à transmettre des messages de mise ajour des tables de routage. Comme un autre avantage, le routage basé sur le positionnement supporte la livraison des paquets à tous les nœuds dans une région géographique donnée d’une manière normale. Ce type de service s’appelle le geocasting.
Le protocole TORA (Temporally Ordered Routing Algorithm)
Ce protocole présenté par Park et Corson dans Park1997, appartient à la famille des algorithmes de cheminement d’inversion de lien (Link Revesral). Il a été conçu principalement pour minimiser l’effet des changements de la topologie qui sont fréquents dans les réseaux ad hoc. Le protocole TORA s’adapte à ces changements en stockant plusieurs chemins vers une même destination. Ce qui fait que beaucoup de changements dans la topologie, n’auront pas d’effets sur le routage des données, à moins que tous les chemins qui mènent vers la destination seront perdus (rompus). La principale caractéristique de TORA, est que les messages de contrôle sont limités à un ensemble réduit de nœuds. Cet ensemble représente les nœuds proches du lieu de l’occurrence du changement de la topologie.
Comme c’est le cas pour tous les protocoles réactifs, les chemins sont crées est installés lors du besoin. TORA est basé sur le principe des algorithmes qui essaient de maintenir la propriété appelée « orientation destination » des graphes acycliques orientés (ou DAG : Directed Acyclic Graph) . Un graphe acyclique orienté est orienté destination s’il y a toujours un chemin possible vers une destination spécifiée. Le graphe devient non orienté destination, si un lien (ou plus) devient défaillant. Dans ce dernier cas, l’algorithmes utilise le concept d’inversement de liens. Ce concept assure la transformation du graphe précédent, en un graphe orienté destination durant un temps fini.
|
Table des matières
Introduction générale
1 Généralités sur les réseaux mobiles
1.1 Classification des réseaux mobiles
1.1.1 Par formation et architecture de réseau
1.1.2 Par champ de couverture du réseau
1.1.2.1 Réseaux Étendus Sans fil (WWAN: Wireless Wide Area Networks)
1.1.2.2 Réseau métropolitain sans fil (WMAN : Wireless Metropolitan Area Network)
1.1.2.3 Réseaux locaux sans fil (WLAN : Wireless Local Area Network)
1.1.2.4 Réseaux personnels sans fil ou WPAN (Wireless Personal Area Network)
1.1.3 Par technologie d’accès
1.1.4 Par types d’applications de réseau
1.2 Réseau mobile Ad Hoc (MaNet)
1.2.1 Histoire des réseaux ad hoc mobiles
1.2.2 Définition
1.2.3 Applications des réseaux ad hoc
1.2.4 Conception et contraintes
1.3 Conclusion
2 Classification des protocoles de routage
2.1 Protocoles de routage proactifs versus protocoles réactifs
2.1.1 Protocoles de routage proactifs
2.1.2 Protocoles de routage réactifs
2.1.3 Protocoles de routage Hybrides
2.2 Protocoles basés sur la topologie hiérarchique ou la construction des clusters
2.3 Protocoles basés sur le positionnement
2.4 Protocoles uniformes versus protocoles non uniformes
2.5 Protocoles basés sur la connaissance de la topologie totale versus réduite
2.6 Utilisation de routage par la source
2.7 Stratégie de diffusion des messages
2.8 Protocoles basés sur la stratégie de sélection de route
2.9 Mécanisme de rétablissement de route
2.10 Conclusion
3 Protocoles de routage dans les réseaux Ad Hoc
3.1 Le protocole AODV (Ad-Hoc On-Demand Distance Vector Routing)
3.1.1 Recherche et installation d’itinéraire
3.1.2 Maintenance d’itinéraire
3.2 Le protocole DSR (Dynamic Source Routing)
3.2.1 Recherche et installation d’itinéraire
3.2.2 Maintenance d’itinéraire
3.2.3 Avantages et Désavantages
3.3 Le protocole OLSR (Optimized Link State Routing Protocol)
3.3.1 Concept de relais Multipoints (MPR Sets)
3.3.2 Election des MPR dans OLSR
3.3.4 Construction de la topologie dans OLSR
3.3.5 Avantages et Désavantages
3.4 Le protocole ABR (Associativity-Based-Routing for Mobile Networks)
3.4.1 Concept d’associativité Tick des nœuds
3.4.2 Installation d’itinéraire dans ABR
3.4.3 Choix d’itinéraire dans ABR
3.4.4 Maintenance d’itinéraire dans ABR
3.5 Le protocole SSA (Signal Stability-Based Adaptive Routing)
3.5.1 Concept de lien Stable (métrique de stabilité)
3.5.2 Les Modules du protocole
3.5.3 Recherche et Installation d’itinéraire
3.5.4 Entretien d’itinéraire
3.6 Le protocole TORA (Temporally Ordered Routing Algorithm)
3.6.1 Recherche et Installation d’itinéraire
3.6.2 Maintenance d’itinéraire dans TORA
3.7 Le protocole POWER (POwer and Link failure aWare rEliable Routing)
3.7.1 Concept de lien stable
3.7.2 Installation d’itinéraire
3.7.3 Maintenance d’itinéraire dans POWER
3.8 Le protocole FORP (Flow Oriented Routing Protocol)
3.8.1 Concept de Durée d’expiration d’un Lien
3.8.2 Concept de Durée d’expiration d’une route
3.8.3 Recherche et Installation d’itinéraire
3.8.4 Maintenance d’itinéraire dans FORP
3.9 Le protocole TBRF (Topology Broadcast Based On Reverse-Path Forwarding)
3.9.1 Découverte de voisinage et Construction d’arbre de cheminement
3.9.2 Maintenance d’itinéraire dans TBRF
3.10 Le protocole CBRP (Cluster Based Routing Protocol)
3.10.1 Principe de formation de groupe
3.10.2 Recherche et Installation d’itinéraire
3.10.3 Maintenance d’itinéraire dans CBRP
3.11 Le protocole LAR (Location Aided Routing)
3.11.1 Recherche et Installation d’itinéraire
3.12 Le protocole DREAM (Distance Routing Effect Algorithm for Mobility)
3.12.1 Choix d’itinéraire
3.13 Le protocole ZRP (Zone Routing Protocol)
3.13.1 Principe de Zone
3.13.2 Architecture du protocole
3.13.3 Recherche et Installation d’itinéraire
3.13.4 Maintenance d’itinéraire
3.14 Le protocole HSR (Hierarchical State Routing)
3.14.1 Recherche et Installation d’itinéraire
3.15 Conclusion
4 Modélisation et simulation des réseaux Ad Hoc
4.1 Conception et modélisation des réseaux Ad Hoc
4.1.1 Modèle de mobilité
4.1.1.1 Traces de mouvement
4.1.1.2 Modèles synthétiques
4.1.1.2.1 Modèles de mobilité par entité
4.1.1.2.2 Modèles de mobilité par groupe
4.1.2 L’impact de choix des modèles de mobilité sur les performances des protocoles
4.1.3 Simulation des réseaux Ad Hoc
4.1.3.1 Métriques de performance
4.2 Conclusion
5 Mobilité et rupture de route dans les réseaux Ad Hoc
5.1 Stabilité d’itinéraire
5.2 Concept de lien stable
5.2.1 Métriques extraites des protocoles SSA et ABR
5.2.2 Métriques basées sur les zones de propagation du signal
5.2.2.1 Métriques de stabilité de lien
5.2.2.2 Fonction de Stabilité de lien
5.2.2.3 Zone de rupture
5.3 Etablissement d’itinéraires
5.3.1 Recherche et installation d’itinéraire
5.3.2 Algorithme de choix d’itinéraire
5.3.2.1 Cas de la première métrique
5.3.2.2 Cas de la deuxième métrique
5.4 Maintenance d’itinéraire
5.4.1 Réparation locale
5.4.2 Réparation de bout en bout (de la source à la destination)
5.5 Evaluation des performances
5.5.1 Environnement de simulation OPNet
5.5.1.2 Modélisation hiérarchique
5.5.1.3 Exécution de la simulation
5.5.2 Modèle de simulation
5.5.3 Résultat de simulation
5.5.3.1 Métriques de performances
5.5.3.2 Analyse des résultats de simulation
5.6 Conclusion
Conclusion et perspectives
Télécharger le rapport complet
