Routage dans les réseaux ad hoc

par Paul MÜHLETHALER

Directeur de recherches INRIA
Projet HiPERCOM

Cet article est inspiré du livre de chez Eyrolles : 802.11 et Les Réseaux Sans Fil publié en
août 2002
http://www.eyrolles.com

1. Routage dans les réseaux ad hoc ........................................................ TE 7 520 - 3

1.1 Groupe MANET............................................................................................ — 3
1.2 Routage au niveau IP et classification des protocoles ............................. — 3
2. Protocoles proactifs................................................................................ — 4
2.1 Protocole OLSR (Optimized Link State Routing ) ...................................... — 4
2.2 Protocole FSR (Fisheye State Routing ) ..................................................... — 4
3. Protocoles réactifs .................................................................................. — 4
3.1 Protocole AODV (Ad Hoc On demand Distance Vector Routing )............. — 5
3.1.1 Création d’une route........................................................................... — 5
3.1.2 Entretien des routes ........................................................................... — 5
3.2 Protocole DSR (Dynamic Source Routing )................................................ — 5
3.2.1 Création des routes ............................................................................ — 5
3.2.2 Entretien des routes ........................................................................... — 6
4. Protocoles hybrides................................................................................. — 6
4.1 Protocole ZRP (Zone Routing Protocol )..................................................... — 6
4.2 Protocole CBRP ............................................................................................ — 6
5. Routage géographique ........................................................................... — 7
6. Autres problèmes techniques rencontrés dans les réseaux
ad hoc.......................................................................................................... — 7
Pour en savoir plus ........................................................................................... Doc. TE 7 520

es réseaux ad hoc ont pour but de connecter des entités communicantes

L (qui pourront être mobiles) en dehors de toutes infrastructures pré-
existantes au sein de réseaux spontanés. Une façon intuitive et simple de
concevoir les réseaux ad hoc est de considérer qu’ils correspondent à la géné-
ralisation ultime des réseaux sans fil car ils limitent au maximum le rôle de
l’infrastructure fixe. Cette généralisation est obtenue par l’amélioration des
capacités de connectivité des réseaux locaux sans fil.
Un réseau ad hoc doit pouvoir être déployé à la demande et pour couvrir une
large palette de situations pratiques. Son type de fonctionnement ne peut être
de type centralisé car une telle hypothèse limite le champs des applications
possibles et on peut s’attendre à ce que les technologies sans fil, qui sont par
nature plus aisées à mettre en œuvre, soient utilisées en priorité. Pour finir, un
réseau ad hoc doit être un véritable réseau ; il ne doit pas souffrir de limitation
forte quant à son domaine de couverture. Par suite, un réseau ad hoc, qui fait
de la technologie de transmission radio sa technologie de prédilection, doit uti-
liser la technique du relayage pour assurer l’extension possible de son
domaine de couverture. Étant par nature spontané, un réseau ad hoc

Toute reproduction sans autorisation du Centre français d’exploitation du droit de copie est strictement interdite.
© Techniques de l’Ingénieur TE 7 520 − 1

Dossier délivré pour

DOCUMENTATION
21/10/2008
ROUTAGE DANS LES RÉSEAUX AD HOC _____________________________________________________________________________________________________

accueillera en son sein avec une forte probabilité un large pourcentage de

nœuds mobiles.
Le réseau ad hoc peut se voir comme une généralisation ultime du réseau
sans fil. Les motivations doivent se chercher parmi les applications du réseau
sans fil qui n’ont pas reçu de réponses complètement satisfaisantes de cette
technologie. Si les réseaux sans fil savent traiter la mobilité sur des domaines
de couverture limitée, les applications de réseau ad hoc vont rechercher la
généralisation de cette mobilité. Les applications qui vont s’orienter vers les
réseaux ad hoc sont naturellement celles qui ne peuvent se contenter d’une
mobilité restreinte ou reposant sur une infrastructure existante. Nous trouve-
rons bien sûr dans ces applications les réseaux militaires ; nous y trouverons
également les réseaux d’urgence et les réseaux temporaires d’exposition ou
correspondant à un événement particulier.
Le domaine militaire est par excellence le domaine de prédilection pour les
réseaux ad hoc. Un réseau de communication tactique doit pouvoir être déployé
à la demande et fonctionner sans infrastructure de communication préexistante.
Il doit bien sûr tolérer la mobilité ; il doit aussi rester furtif, ce qui interdit les
systèmes centralisés avec antenne sur un point haut. Il doit aussi être perfor-
mant car de plus en plus les informations échangées sur le champ de bataille
comportent des images ; ces dernières impliquent un coût de transmission
important en termes de volume. Il existe en Europe de nombreux programmes
militaires qui utilisent la technologie des réseaux ad hoc :
— le programme FÉLIN (Fantassin à Équipement et Liaisons INtégrées) qui est
un programme de la DGA (Délégation Générale de l’Armement) ;
— le programme FIST qui est le programme équivalent au Royaume-Uni ;
— le programme RHD (Radio Haut Débit) qui est un programme français de
conception d’une radio haut débit pour les réseaux ad hoc.

Principales abréviations Principales abréviations

AODV Ad hoc On demand Distance Vector protocol IPsec IP Security
CBRP Cluster Based Routing Protocol MAC Medium Access Control (Partie basse de la couche 2
du mobèle OSI dont la première fonction est d’assu-
CDMA Code Division Multiple Access (technique d’accès rer le partage de la ressource de communication)
multiple utilisant des codes permettant
de transmettre simultanément sur un même canal) MANET Mobile Ad hoc NETwork
CSMA Carrier Sense Multiple Access (technique d’accès OLSR Optimized Link State Routing Protocol
multiple utilisant la détection de porteuse) RHD Radio Haut Débit
DGA Délégation Générale de l’Armement RREQ Route Request
DSR Distance Source Routing RERR Route Error
FDMA Frequency Division Multiple Access (technique ZRP Zone Routing Protocol
d’accès multiple qui utilise plusieurs fréquences
de sorte à pouvoir transmettre simultanément
plusieurs flux de données)
FÉLIN Fantassin à Équipement et Liaisons Intégrées
1. Routage dans les réseaux
FSR Fisheye State Routing protocol
ETSI European Telecommunication Standard Institute
ad hoc
IARP IntrAzone Routing Protocol
Le routage est, dans les réseaux ad hoc, la brique technologique
IEEE Institute of Electrical and Electronical Engineer fondamentale permettant d’assurer la connectivité du réseau. La
(Organisme de normalisation américain spécialisé figure 1 représente la topologie d’un tel réseau ad hoc multisaut.
dans la standardisation des réseaux locaux ou Dans un tel réseau, les nœuds radio ne sont pas nécessairement à
métropolitains)
portée directe. Un paquet peut donc devoir être relayé par des
IERP IntErzone Routing Protocol nœuds intermédiaires pour atteindre sa destination finale.
IETF Internet Engineering Task Force (groupe de normali- Le caractère multisaut ne suffit pas à assurer la connectivité du
sation qui normalise les protocoles Internet) réseau. Il faut en outre disposer d’un aiguillage, qui permette à un

Toute reproduction sans autorisation du Centre français d’exploitation du droit de copie est strictement interdite.
TE 7 520 − 2 © Techniques de l’Ingénieur

Dossier délivré pour

DOCUMENTATION
21/10/2008
 ____________________________________________________________________________________________________ ROUTAGE DANS LES RÉSEAUX AD HOC

peut disposer de plusieurs interfaces sans fil différentes. Ces nœuds

radio peuvent se trouver dans des avions, des bateaux, des
camions, des voitures, voire sur des personnes. Un tel réseau forme
un système indépendant de nœuds mobiles. Ce système peut être
isolé, mais il peut aussi comporter des passerelles ou des interfaces
le reliant à un réseau fixe. Dans son fonctionnement futur, MANET
pourra être considéré comme un réseau de distribution finale (Stub
Network ).
Les nœuds du réseau MANET sont équipés d’émetteurs et de
récepteurs sans fil utilisant des antennes, qui peuvent être omni-
Dans un réseau multisaut ad-hoc, une trame peut être relayée directionnelles et permettre la diffusion, ou directionnelles et donc
avant d’atteindre sa destination être dédiées à une liaison point à point. À un instant donné, en fonc-
tion de la position des nœuds, de la configuration de leur émetteur-
récepteur et des niveaux de puissance de transmission et d’inter-
Figure 1 – Principe de fonctionnement d’un réseau ad hoc multisaut férence entre les canaux, une connectivité sans fil se met en place
entre les nœuds sous forme de graphe multisaut. Cette topologie
ad hoc peut changer avec le temps en fonction du mouvement des
paquet de trouver son chemin vers sa destination. Cet aiguillage nœuds et de l’ajustement de leurs paramètres d’émission-réception.
est obtenu par le protocole de routage.
Dans ses grandes lignes, la problématique du routage dans les
réseaux sans fil ressemble à celle du routage dans les réseaux tra- 1.2 Routage au niveau IP
ditionnels. Il s’agit d’aiguiller les paquets vers leur destination. Pour et classification des protocoles
connaître la topologie du réseau, les stations échangent des paquets
comportant de l’information topologique. Le routage au niveau de la couche IP donne un avantage équi-
Pourtant, le routage dans ces réseaux sans fil présente toutefois valent à la vision originale d’Internet, à savoir « une possibilité
des particularités. Il est bien connu qu’une transmission radio est d’interconnexion et d’interopérabilité sur une infrastructure de
intrinsèquement plus fragile qu’une transmission sur support câblé. réseaux hétérogènes ». Ici, cette infrastructure est constituée de plu-
Cela entraîne une première différence importante entre le routage sieurs technologies sans fil, de plusieurs protocoles d’accès aux
dans les réseaux sans fil et celui sur support câblé. Cette caracté- canaux, etc. Le routage IP et les services réseau associés forment
ristique est d’autant plus importante que le routage s’appuie géné- la colle qui permet de conserver l’intégrité du segment mobile inter-
ralement sur la diffusion et que la diffusion ne peut être protégée réseau dans cet environnement plus dynamique.
par un accusé de réception, contrairement à ce qui se pratique dans Dans un réseau MANET, les nœuds qui prennent les décisions de
les transmissions en point à point. routage en utilisant la structure IP, peuvent communiquer entre eux
L’utilisation en diffusion de la ressource radio permet de joindre par une quelconque technologie de communication radio exis-
en une seule transmission tous les voisins. Ce n’est pas le cas pour tante. Au fur et à mesure que de nouvelles technologies se déve-
le routage filaire, dans lequel une transmission en diffusion néces- lopperont au niveau de la couche physique, de nouvelles interfaces
site, pour un routeur, la transmission du paquet sur toutes ses inter- pourront être ajoutées au-dessous de la structure IP de routage.
faces. Inversement, dans un réseau radio, la transmission en point Les technologies de transmission radio les plus anciennes pourront
à point d’un nœud A est reçue par tous les voisins et empêche une dès lors être abandonnées.
transmission simultanée du nœud vers d’autres nœuds.
Le groupe MANET fait une distinction entre deux types de
Pour des raisons physiques, liées à la propagation des ondes protocoles : les protocoles réactifs et les protocoles proactifs.
radio, la bande passante disponible en radio est sensiblement plus
limitée que sur un support filaire. Ce phénomène est d’autant plus
vrai si l’on considère les transmissions dans lesquelles il n’existe Protocoles réactifs. Ces protocoles ne cherchent à calculer une
pas de chemin en vue directe, c’est-à-dire sans obstacle entre la route qu’à la demande d’une application. Un paquet de requête
source et la destination. Cette restriction impose de définir des tech- est envoyé en diffusion dans le réseau à la recherche d’une route
niques de routage « économiques » en bande passante pour le vers la destination. Le trafic de contrôle du protocole de routage
maintien ou l’acquisition des informations de routage. est de la sorte réduit. Cependant, du fait que l’on ne dispose pas
immédiatement de la route vers la destination, le délai néces-
Une liaison radio peut être unidirectionnelle. Si les émetteurs ont
saire à l’acheminement des paquets vers la destination aug-
une puissance inégale, par exemple, l’un peut recevoir l’autre sans
mente pour l’application. Par ailleurs, une modification des
que la réciproque soit vraie. La liaison peut également être uni-
couches IP est nécessaire du fait que ces dernières ne pemettent
directionnelle en raison de phénomènes physiques, même si les
généralement pas de conserver des paquets en mémoire avant
équipements ont les mêmes caractéristiques de sensibilité et de
que la route vers cette dernière soit créée.
puissance. Ce caractère unidirectionnel d’une liaison n’existe pas
généralement dans les liaisons filaires. Protocoles proactifs. Au contraire des précédents, ces proto-
coles entretiennent toutes les routes du réseau par l’échange de
trames périodiques de contrôle. Il est possible de fournir instan-
tanément la route vers une destination quelconque au prix de
1.1 Groupe MANET l’envoi périodique de trames de topologie. Les protocoles pro-
actifs fonctionnent vis-à-vis de la couche réseau comme des pro-
En 1997, l’IETF (Internet Engineering Task Force ) crée le groupe tocoles de routage classiques.
de travail MANET (Mobile Ad Hoc Networks ) pour définir une spé-
cification de protocole de routage pour les réseaux sans fil ad hoc.
À notre connaissance, c’est le seul organisme de normalisation à Des protocoles hybrides qui mélangent des techniques réactives
ce jour qui se penche sur ce problème. et proactives ont également été proposés à l’IETF.
Un réseau MANET est constitué de nœuds mobiles. Par défaut, Par ailleurs, le monde académique a proposé une technologie
ces nœuds sont supposés disposer de fonctionnalités de routage. novatrice de routage qui peut être particulièrement propice pour les
Plusieurs nœuds hôtes peuvent éventuellement être rattachés à un réseaux ad hoc : le routage géographique. Nous donnerons (§ 5)
nœud MANET par des liaisons filaires fixes. Par ailleurs, un nœud quelques éléments concernant cette technologie.

Toute reproduction sans autorisation du Centre français d’exploitation du droit de copie est strictement interdite.
© Techniques de l’Ingénieur TE 7 520 − 3

Dossier délivré pour

DOCUMENTATION
21/10/2008
ROUTAGE DANS LES RÉSEAUX AD HOC _____________________________________________________________________________________________________

2. Protocoles proactifs
Dans cette classe de protocoles, un système d’échange pério-
dique de paquets de contrôle est mis en place de telle sorte que
chaque nœud puisse construire de façon distribuée la topologie du
réseau.
Il peut exister plusieurs types de paquets de contrôle. En règle
générale, on distingue les paquets qui sont envoyés localement à
un saut et les paquets qui sont diffusés dans tout le réseau. Les pre-
miers permettent d’acquérir la connaissance du voisinage. Les
Envoi périodique d'information topologique
seconds permettent à un nœud donné de diffuser dans le réseau
l’état du voisinage, lequel se ramène le plus souvent aux nœuds
voisins ou à un sous-ensemble de ces derniers. Dans un protocole Figure 2 – Principe de fonctionnement des protocoles proactifs
proactif, un nœud met périodiquement à jour ses tables de routage
lors de la réception des paquets de contrôle. L’envoi régulier de
paquets d’information et le traitement de ces derniers sont la
contrepartie à l’obtention immédiate des informations topologiques Relais multipoints du nœud i
(permettent d’atteindre tous ses nœuds à deux sauts)
(figure 2).
Avec ces protocoles, chaque nœud maintient une ou plusieurs o p
tables, qui permettent d’atteindre tous les autres nœuds du réseau. 2
3
Chaque nœud met régulièrement à jour ces informations. Lorsque j
m
la topologie du réseau évolue, les nœuds diffusent des messages n 1
de mise à jour à travers tout le réseau. i q

Les protocoles de cette famille se différencient par la manière l

k
dont cette information de mise à jour est transmise à travers le
réseau ainsi que par le nombre de table de routage utilisée.
Trois transmissions permettent la diffusion à partir de i
Les principaux protocoles proactifs sont :
— OLSR (Optimized Link State Routing ) Figure 3 – Optimisation des relais multipoint
— FSR (Fisheye State Routing ).

2.1 Protocole OLSR

(Optimized Link State Routing )
OLSR [3] est un protocole de routage proactif pour réseaux ad
hoc. Inspiré de la norme HiperLAN type 1 [7] [8], il minimise l’inon-
dation du réseau par des messages de contrôle. Il n’utilise que
quelques nœuds, appelés relais multipoint, pour diffuser ces mes-
sages. Le protocole fonctionne de façon complètement distribuée
et ne dépend de ce fait d’aucune entité centrale. Envoi toutes
Un lien entre un nœud et ses voisins peut avoir l’un des trois les périodes
Envoi toutes
états suivants : les trois périodes
— ASYM-LINK : lien non encore valide avec un voisin ;
— SYM-LINK : lien valide avec un voisin ; Figure 4 – Principe de fonctionnement de FSR
— MPR-LINK : lien avec un relais multipoint.
Exemple : la figure 3 illustre le mécanisme d’optimisation des Même lorsqu’aucune information précise n’est disponible sur le
relais multipoint. La retransmission par les nœuds m et j est suffisante nœud à joindre, le routage s’effectue correctement. Cela tient au
pour assurer la diffusion d’une trame en provenance de la station i. fait que l’information de routage devient de plus en plus précise au
L’ensemble des stations m et j forme un ensemble de relais multipoint fur et à mesure que les paquets s’approchent de leur destination.
du nœud i. Une diffusion issue du nœud i va donc utiliser uniquement Grâce à cette propriété, FSR peut gérer de grands réseaux. On dit
trois transmissions. que le protocole FSR supporte le passage à l’échelle.

2.2 Protocole FSR (Fisheye State Routing )

3. Protocoles réactifs
FSR est un protocole classique de type état des liens [4]. Son ori-
ginalité réside dans le fait que chaque nœud diffuse son voisinage
Un protocole réactif ne calcule pas d’information topologique
local avec une fréquence qui dépend du nombre de sauts qu’un
avant que celle-ci soit rendue nécessaire par la demande de route
paquet doit effectuer. Par conséquent, si un nœud peut obtenir des
d’un paquet vers une destination par une application. Le protocole
informations précises sur son voisinage local, les informations
ne tente de découvrir une route qu’à la demande d’une application
concernant les nœuds à grande distance lui sont moins disponibles.
qui souhaite envoyer un paquet vers une destination, et ce par la
Exemple : la figure 4 illustre les différents niveaux de précision diffusion d’une requête dans tout le réseau. La réponse à cette
obtenus pour un nœud central. Ces niveaux dépendent du nombre de requête en diffusion permet à la source d’obtenir les informations
sauts nécessaires pour atteindre un autre nœud. topologiques concernant cette route. Durant cette phase de

Toute reproduction sans autorisation du Centre français d’exploitation du droit de copie est strictement interdite.
TE 7 520 − 4 © Techniques de l’Ingénieur

Dossier délivré pour

DOCUMENTATION
21/10/2008
 ____________________________________________________________________________________________________ ROUTAGE DANS LES RÉSEAUX AD HOC

Destination RRQ D RRP D

RR
RR RR RR RRQ RRP
RRQ
RR RR RR
RR RR RR
RRQ
RR RR
RR RRQ RRQ RRP
Source RR RR RR
RR RR
RR RR RR S S
RRQ
RR Route Request
a demande de route b réponse
Figure 5 – Fonctionnement des protocoles réactifs RRQ Route Request
RRP Route Reply

recherche de route, le paquet IP est mis en attente d’une réponse Figure 6 – Fonctionnement de la procédure de demande de recherche
du protocole de routage jusqu’à ce qu’une route soit disponible. de route

Exemple : la figure 5 illustre le fonctionnement des protocoles

réactifs. La source envoie une requête en diffusion pour la recherche
d’une route vers une destination. La destination adresse en retour une B
réponse vers la source en utilisant les routes déjà créées. Sur son
chemin de retour, le paquet crée la route vers la destination. RRP D

Cette technique ne va pas sans un inconvénient important : les RRP

implémentations actuelles ne prévoient pas la possibilité pour un
paquet IP d’attendre la création d’une route. Dans ce cas, la couche A Route alternative
réseau indique simplement à l’application qu’il existe pas de route créée après une nouvelle
RERR recherche de route
vers la destination. Ces protocoles nécessitent donc une modifica-
tion des couches IP susceptible d’introduire des files d’attente pour
conserver les paquets en attente de route. S
Dans cette famille de protocoles, les routes ne sont pas mainte-
nues en permanence vers tous les nœuds. Quand un nœud cherche Figure 7 – Principe du mécanisme d’entretien des routes avec AODV
à communiquer avec un autre nœud, il déclenche un mécanisme de
découverte de route. Une route est ainsi créée à la demande et sub-
siste dans le réseau tant qu’elle est valide ou jusqu’à ce qu’elle Exemple : la figure 6 illustre le mécanisme de création des routes
devienne inutile. On parle alors de timeout après fin d’utilisation. d’AODV. Il y a d’abord diffusion de la demande de route. Ensuite, la des-
tination envoie une réponse, qui, grâce aux informations recueillies par
Les principaux protocoles réactifs sont :
les nœuds lors de la diffusion de la demande de route, crée une route
— AODV (Ad Hoc On demand Distance Vector Routing ) ; de la destination vers la source.
— DSR (Dynamic Source Routing ).

3.1.2 Entretien des routes

3.1 Protocole AODV (Ad Hoc On demand AODV incorpore un mécanisme pour signaler les ruptures de
Distance Vector Routing ) lien. Lorsqu’un nœud repère la rupture d’un lien sur le trajet d’une
route reliant une source S à une destination D, il génère vers S une
AODV est un protocole de routage réactif de type vecteur de dis- trame RERR (Route ERRor ) d’erreur de route. Cette dernière
tance, voir [AODV]. Il reprend certains principes de DSDV (Destination relance une nouvelle procédure de recherche de route.
Sequence Distance Vector ) mais réduit l’overhead en ne calculant
que les routes sur demande et en limitant la répercussion des modifi- Exemple : la figure 7 illustre ce mécanisme d’entretien des routes.
cations topologiques aux seules routes en cours d’utilisation. Sur cet exemple, le nœud A, qui ne peut plus joindre le nœud destination
D par B, va envoyer au nœud source S un message RERR. La source va
refaire une procédure de création de route vers le nœud destination.
3.1.1 Création d’une route
Lorsqu’un nœud reçoit une demande d’une application pour une
route vers une destination, il cherche d’abord à savoir s’il en pos- 3.2 Protocole DSR
sède une. Si tel est le cas, le protocole n’a pas d’algorithme parti- (Dynamic Source Routing )
culier à mettre en œuvre. Dans le cas contraire, le nœud source
diffuse une demande de route RREQ (Route REQest ). Les nœuds DSR est un protocole réactif, qui utilise une technique de routage
qui reçoivent ces paquets les diffusent à leur tour jusqu’à atteindre par source dans laquelle les nœuds intermédiaires ne doivent pas
la destination ou au moins un nœud qui possède une information nécessairement garder trace de la route [2]. Cela permet de résou-
de routage récente vers la destination recherchée. dre facilement le problème des boucles. Chaque paquet contient
Les nœuds situés sur le parcours de la requête de route dans son en-tête la liste complète des adresses des nœuds à traver-
conservent dans leur cache l’adresse du nœud qui leur a relayé la ser vers la destination. DSR fonctionne de façon similaire à AODV.
requête. L’adresse de ce nœud fournit l’adresse du saut suivant pour
la route vers la source initiale. On a simplement inversé le chemin 3.2.1 Création des routes
du paquet de requête. Cette information est utilisée lors du retour de
la réponse de demande de route pour permettre d’aiguiller cette Si un destinataire est dans le cache du nœud source, la route
réponse jusqu’à la source initiale. AODV utilise un algorithme à vec- connue est utilisée. Sinon, une procédure de découverte de route
teur de distance dans lequel la mise à jour des routes est protégée est déclenchée. Les paquets de découverte de route contiennent les
par un numéro de séquence associé à la destination. adresses source et destination ainsi qu’un identifiant permettant

Toute reproduction sans autorisation du Centre français d’exploitation du droit de copie est strictement interdite.
© Techniques de l’Ingénieur TE 7 520 − 5

Dossier délivré pour

DOCUMENTATION
21/10/2008
ROUTAGE DANS LES RÉSEAUX AD HOC _____________________________________________________________________________________________________

A B

Destination D
C IERP I IARP
D
J
Source, F, E, E F
Destination F
Source S
Source, F, E Source, F
K
Figure 8 – Demande d’une route pour DSR

A B Figure 10 – Principe de fonctionnement du protocole ZRP

4.1 Protocole ZRP

D
Destination C (Zone Routing Protocol )
Source, F, E, E F ZRP [5] est un protocole hybride. Dans le voisinage proche d’un
Destination nœud, ZRP utilise une technique de routage proactif classique.
Source Pour router des chemins en dehors de cette zone de voisinage, ZRP
Source, F, E Source, F s’appuie sur une technique réactive.
ZRP définit pour chaque nœud une zone de routage, qui inclut
Figure 9 – Réponse à la requête d’une route dans DSR tous les nœuds dont la distance minimale à ce nœud est x. Les
nœuds qui sont exactement à la distance x sont appelés nœuds
périphériques. Pour trouver une route vers des nœuds situés à une
aux nœuds intermédiaires de savoir s’ils ont déjà traité les paquets.
distance supérieure à x, ZRP utilise un système réactif, qui envoie
Le chemin vers la destination est créé dans le paquet de recherche
une requête à tous les nœuds périphériques. ZRP met pour cela en
de route. Chaque nœud qui reçoit ce paquet ajoute à la route pré-
œuvre deux types de fonctionnement : IARP (IntrAzone Routing
existante dans ce paquet sa propre adresse (figure 8). Lorsqu’un des
Protocol ) et IERP (IntErzone Routing Protocol ).
paquets de recherche de route atteint sa destination ou un nœud
qui possède une route valide vers la destination, ce nœud répond Fondé sur un protocole à vecteur de distance, IARP donne toutes
à la source initiale (figure 9). Comme, a priori, ce nœud ne possède les routes jusqu’à une distance x, selon une technique proactive.
pas de route vers la source initiale, une nouvelle recherche de route IERP donne les routes pour des destinations à plus de x sauts d’une
doit être entreprise. Pour éviter un bouclage infini des recherches façon réactive.
de route, la route construite est ajoutée à la nouvelle recherche de Le processus de recherche de route fonctionne de la façon sui-
route, en sorte que le nœud source connaisse une route valide pour vante :
sa réponse. Si l’on fait l’hypothèse que les liens rapportés par la
— si une route est connue, cela signifie que la destination est à
recherche de route initiale sont symétriques, on peut utiliser cette
moins de x sauts. Cette route est la route retournée par le protocole ;
route pour créer une réponse.
— si aucune route n’est connue, cela signifie que le nœud est
DSR possède le même mécanisme qu’AODV pour limiter le situé à une distance supérieure à x. Dans ce cas, le nœud envoie
nombre de saut d’une recherche de route. une requête par IERP à tous les nœuds périphériques ;
— si un nœud périphérique a connaissance d’une route dispo-
nible, il renvoie une réponse. Dans le cas contraire, le protocole se
3.2.2 Entretien des routes poursuit récursivement jusqu’à obtention d’une route.
Exemple : la figure 10 illustre le fonctionnement de ZRP, avec x
En cas de rupture d’un lien sur un trajet, le nœud situé en amont
défini à 2. S cherche une route vers D, D n’étant pas à une distance 1
de la rupture envoie à la source une indication concernant la
ou 2 de S. Par suite, une requête de demande de route est envoyée à
rupture du lien. La source peut alors relancer une procédure de
tous les nœuds frontières, soit F, I, J et K dans l’exemple. Ces nœuds
recherche de route.
recherchent une route vers P de façon réactive. Une fois la route
trouvée – dans l’exemple, c’est F qui doit trouver cette route –, elle est
ensuite rapportée à S.
4. Protocoles hybrides
4.2 Protocole CBRP
Ces protocoles, qui mêlent généralement les modes proactif et
réactif, fonctionnent dans l’un ou l’autre mode suivant des condi- Le protocole CBRP (Cluster Based Routing Protocol ) [8] utilise un
tions prédéfinies. mécanisme de routage hiérarchique à deux niveaux. CBRP définit
la notion de « cluster » de stations : c’est un groupe de stations
Dans ce système, on peut garder la connaissance locale de la formé de membres et d’une tête de cluster, chaque membre du
topologie jusqu’à un nombre prédéfini – a priori petit – de saut par cluster étant à portée radio directe d’une tête de cluster. Les têtes
un échange périodique de trames de contrôle, autrement dit par de cluster doivent maintenir une connectivité en eux, ce faisant ils
une technique proactive. Les routes vers des nœuds plus lointains assurent la connectivité de tout le réseau, les nœuds du réseau
sont obtenues par schéma réactif, c’est-à-dire par l’utilisation de devront passer par des têtes de cluster. Nous ne décrirons pas en
paquets de requête en diffusion. détail ce protocole.

Toute reproduction sans autorisation du Centre français d’exploitation du droit de copie est strictement interdite.
TE 7 520 − 6 © Techniques de l’Ingénieur

Dossier délivré pour

DOCUMENTATION
21/10/2008
 ____________________________________________________________________________________________________ ROUTAGE DANS LES RÉSEAUX AD HOC

5. Routage géographique 6. Autres problèmes

L’idée des protocoles de routage géographique est d’utiliser des
techniques rencontrés
informations géographiques pour acheminer les paquets. Pour dans les réseaux ad hoc
simplifier la présentation, nous supposerons que tous les nœuds
connaissent leur position et que ceux-ci connaissent également la
position de tous les autres nœuds du réseau. Avec ces hypothèses, Un problème crucial dans les réseaux ad hoc est le partage de
il est facile de concevoir qu’un nœud peut facilement choisir parmi la bande radio. Si les réseaux sans fil (WLAN Wireless LAN ) pro-
ses voisins un relais pour acheminer un paquet dont il connaît la posent des solutions, ces dernières ne sont pas complètement
destination finale et donc aussi sa position. Il est très simple adaptées aux réseaux ad hoc. Il convient de mettre en place de
d’envisager des critères de sélection parmi ces voisins ; donnons nouvelles techniques qui tiennent d’abord compte du caractère
quelques exemples parmi les heuristiques les plus classiques. naturellement ouvert d’un réseau ad hoc. Ensuite, il convient d’uti-
liser au mieux la bande radio partagée ; pour ce faire, il convient
de trouver le meilleur compromis entre la réutilisation spatiale et
Une heuristique particulièrement simple est celle qui choisit le le problème des nœuds cachés. Les réseaux ad hoc qui sont actuel-
voisin qui permet de se rapprocher le plus de la position du des- lement expérimentés utilisent souvent des interfaces radio
tinataire final. Une autre heuristique proche bien que différente 802.11 [9] et donc un protocole CSMA pour partager la bande radio.
est celle qui choisit le voisin qui permet de progresser le plus en Plusieurs références sur la technique CSMA et ses adaptations au
direction du destinataire finale, c’est l’heuristique de la progres- médium radio et aux réseaux ad hoc sont fournies en bibliographie
sion maximale. C’est celle que nous avons représenté sur la (cf. Doc. TE 7 520], Partage du médium radio).
figure 11. Cette dernière heuristique est intéressante car on
peut montrer qu’en moyenne elle permet de minimiser le nom-
bre de sauts vers la destination. Par ailleurs, les réseaux ad hoc comme les autres réseaux
Une autre heuristique très simple est celle qui choisit le voisin doivent parfois être en mesure d’offrir des services ou fonctionna-
le plus proche en direction de la destination finale. Il est possible lités qui dépassent la simple fourniture de connectivité. Ces
de montrer que cette heuristique permet de minimiser l’énergie services peuvent être requis par des applications particulières, par
locale pour relayer le paquet vers sa destination finale. exemple si celles-ci nécessitent de la qualité de service. D’autres
fonctionnalités comme la sécurité peuvent être requises pour des
raisons extérieures au réseau lui-même, par exemple pour parer
des attaques.
Destination
finale Voici une liste non exhaustive des services ou fonctionnalités qui
peuvent être requis dans un réseau ad hoc :

— sécurité ;
— qualité de service ;
— autoconfiguration.

Nous n’allons pas développer ces sujets. Le lecteur intéressé trou-

Source
vera dans les références une liste d’articles lui permettant d’aborder
ceux-ci.
Meilleur relais pour l’heuristique
de la meilleure progression
Ensemble des voisins
de la source Le domaine des réseaux ad hoc est en plein essor. Il ouvre des
perspectives de recherche importantes et une palette de nou-
Figure 11 – Routage géographique avec l’heuristique de la meilleure velles applications surtout très intéressantes en mobilité.
progression vers la destination

Toute reproduction sans autorisation du Centre français d’exploitation du droit de copie est strictement interdite.
© Techniques de l’Ingénieur TE 7 520 − 7

Dossier délivré pour

DOCUMENTATION
21/10/2008