III / Le routage dans les réseaux mobiles Ad hoc

[pic] Année 2002-2003 LE ROUTAGE
dans les réseaux mobiles Ad hoc
SOMMAIRE Introduction 3 I / Les environnements mobiles 5 1.1 Présentation des environnements mobiles 5
1.2 L'utilisation des ondes radio dans la communication sans fil 6
1.3 La fiabilité de la communication sans fil 7
1.4 La communication cellulaire 7
1.5 Quelques éléments de l'infrastructure sans fil 8 II / Les réseaux mobiles Ad hoc 9 2.1 Définition 9
2.2 Les applications des réseaux mobiles ad hoc 10
2.3 Les caractéristiques des réseaux ad hoc 10 III / Le routage dans les réseaux mobiles Ad hoc 12 3.1 Définition 12
3.2 La difficulté du routage dans les réseaux ad hoc 12
3.3 La conception des stratégies de routage 13
3.4 L'évaluation des protocoles de routage 14
3.5 Autres notions 14
3.5.1 Le "multihoping" 14
3.5.2 L'inondation 15
3.5.3 Le concept de groupe 15 IV / Les différents protocoles de routage 17 4.1 Les protocoles de routage pro-actifs 17
4.1.1 Présentation 17
4.1.2 Le protocole de routage DSDV 18
4.1.3 Le protocole de routage WRP 20
4.1.4 Le protocole de routage GSR 21
4.1.5 Le protocole de routage FSR 22
4.1.6 Le protocole de routage HSR 24
4.1.7 Le protocole de routage ZHLS 26
4.1.8 Le protocole de routage CGSR 27
4.1.9 Le protocole de routage DREAM 28
4.2 Les protocoles de routage réactifs (à la demande) 29
4.2.1 Présentation 29
4.2.2 Le protocole de routage CBRP 29
4.2.3 Le protocole de routage DSR 31
4.2.4 Le protocole de routage AODV 33
4.2.5 Le protocole de routage TORA 35
4.2.6 Le protocole de routage ABR 37
4.2.7 Le protocole de routage SSR 38
4.2.8 Le protocole de routage LAR 39
4.2.9 Le protocole de routage RDMAR 39 Conclusion 43
|Introduction | L'essor des technologies sans fil offre aujourd'hui des perspectives
intéressantes dans le domaine des télécommunications. L'évolution récente
des moyens de communication sans fil a permis la manipulation
d'informations au travers d'unités de calcul portables aux caractéristiques
bien particulières (faible capacité de stockage, source d'énergie
autonomie, puissance limitée, etc.) qui accèdent au réseau par le biais
d'une interface de communication sans fil. Les environnements mobiles offrent une grande flexibilité d'emploi. En
particulier, ils permettent la mise en réseau de sites dont le câblage
serait trop onéreux à réaliser dans leur totalité, voire même impossible (
par exemple en présence d'une composante mobile ). Contrairement à
l'environnement statique, l'environnement mobile permet aux unités de
calcul une libre mobilité et ne pose aucune restriction sur la localisation
des usagers. La mobilité et le nouveau mode de communication utilisé
engendrent des problèmes propres à l'environnement mobile : une fréquente
déconnexion, un débit de communication et des ressources modestes et des
sources d'énergie limitées.
Les réseaux mobiles sans fil, peuvent être classés en deux catégories
: les réseaux avec infrastructure qui utilisent généralement le modèle de
la communication cellulaire, et les réseaux sans infrastructure ou les
réseaux ad hoc. Plusieurs systèmes utilisent déjà le modèle cellulaire et
connaissent une très forte expansion à l'heure actuelle ( les réseaux GSM
par exemple ) mais requièrent une importante infrastructure logistique et
matérielle fixe.
L'alternative à ces réseaux cellulaires sont les réseaux mobiles ad
hoc. Un réseau ad hoc peut être défini comme une collection d'entités
mobiles interconnectées par une technologie sans fil formant un réseau
temporaire sans l'aide de toute administration ou de tout support fixe.
Dans un réseau ad hoc les hôtes mobiles doivent former, d'une manière ad
hoc, une sorte d'architecture globale qui peut être utilisées comme
infrastructure du système. Les applications des réseaux ad hoc sont
nombreuses, on cite l'exemple classique de leur application dans le domaine
militaire et les autres applications de tactique comme les opérations de
secours et les missions d'exploration. Du fait que le rayon de propagation
des transmissions des hôtes soit limité, et afin que le réseau ad hoc reste
connecté, il se peut qu'un hôte mobile se trouve dans l'obligation de
demander de l'aide à un autre hôte pour pouvoir communiquer avec son
correspondant. Il se peut donc que l'hôte destination soit hors de la
portée de communication de l'hôte source, ce qui nécessite l'emploi d'un
routage interne par des n?uds intermédiaires afin de faire acheminer les
paquets de messages à la bonne destination. La gestion de l'acheminement de
données ou le routage, consiste à assurer une stratégie qui garantie, à
n'importe quel moment, la connexion entre n'importe quelle paire de n?uds
appartenant au réseau. La stratégie de routage doit prendre en
considération les changements de la topologie ainsi que les autres
caractéristiques du réseau ad hoc ( bande passante, nombre de liens,
ressources du réseau...etc. ). En outre, la méthode adoptée dans le
routage, doit offrir le meilleur acheminement des données en respect des
différentes métriques de coûts utilisées. Ce travail entre dans le cadre de
l'étude du problème de routage dans les réseaux mobiles ad hoc. Notre étude offre principalement une étude synthétique des travaux de
recherche qui ont été fait, et qui se font à l'heure actuelle, dans le but
de résoudre le problème d'acheminement de données entre les hôtes mobiles
du réseau ad hoc. Comme nous allons voir le problème de routage est très
compliqué, cela est du essentiellement à la propriété qui caractérise les
réseaux ad hoc et qui est l'absence d'infrastructure fixe et de toute
administration centralisée.
Ce document est composé de trois chapitres : dans le premier chapitre
nous présentons les environnements mobiles et les principaux concepts liés
à ces environnements. Nous commençons par la définition de l'environnement
et citer les deux classes qui le constituent, ainsi que les principaux
avantages offerts. Nous donnons par la suite quelques notions importantes
utilisées dans les systèmes mobiles et qui sont plus liées à la technologie
sans fil qui représente le c?ur de la télécommunication sans fil.
Dans le deuxième chapitre, nous introduisons le concept de réseau ad
hoc et le problème de routage dans cet environnement. Ceci permet d'un coté
de situer les réseaux ad hoc par rapport à l'environnement mobile, et d'un
autre coté de mettre l'accent sur le problème de routage, problème qui est
propre à l'environnement du réseau ad hoc. Après la description des
principales applications et caractéristiques de l'environnement ad hoc,
nous définissons le problème d'acheminement de données dans de tels
environnements et nous soulignons sa difficulté et les principales
contraintes que la stratégie de routage doit respecter.
Des notions importantes liées au problème de routage sont par la suite
discutées. Le dernier chapitre est consacré à la présentation des
différents protocoles de routage existant dans le contexte des réseaux ad
hoc. Nous décrivons les principales caractéristiques et fonctionnalités des
stratégies de routage les plus connues permettant d'assurer l'acheminement
des données entre les hôtes mobiles. Le but d'une stratégie de routage est
l'établissement de routes qui soient correctes et efficaces entre une paire
quelconque d'hôte, les protocoles de routage qui existent se diffèrent par
la manière de recherche de chemins entre la source et la destination et par
la maintenance des routes construites.
|I / Les environnements mobiles |
Les environnements mobiles permettent une grande flexibilité d'emploi.
En particulier, ils permettent la mise en réseau des sites dont le câblage
serait trop onéreux à réaliser dans leur totalité, voire même impossible.
Les solutions de déploiement conçues pour les systèmes distribués ne
regroupant que des sites statiques ne peuvent pas être utilisées
directement dans ce type d'environnement. De nouvelles solutions doivent
être trouvées pour s'adapter aux limitations qui existent, ainsi qu'aux
facteurs qui rentrent en jeu lors de la conception.
Ce chapitre a pour but de présenter l'environnement mobile et les
principaux concepts qui lui sont liés. Le modèle de l'environnement étudié,
dans ce chapitre, n'exclut pas l'existence d'une infrastructure
préexistante ( un ensemble de stations liées par un réseau filaire )
puisque l'esprit de la communication est la même pour tous les réseaux
mobiles. 1.1 Présentation des environnements mobiles
Un environnement mobile est un système composé de sites mobiles et qui
permet à ses utilisateurs d'accéder à l'information indépendamment de leurs
positions géographiques. Les réseaux mobiles ou sans fil, peuvent être
classés en deux classes : les réseaux avec infrastructure et les réseaux
sans infrastructure. Le modèle de système intégrant des sites mobiles et
qui a tendance à se généraliser, est composé de deux ensembles d'entités
distinctes : les "sites fixes" d'un réseau de communication filaire
classique ( wired network ), et les "sites mobiles" ( wireless network ).
Certains sites fixes, appelés stations support mobile ( Mobile Support
Station ) ou station de base ( SB ) sont munis d'une interface de
communication sans fil pour l