MASTER INFORMATIQUE Systmes Informatiques & Rseaux

Projet Bibliographique

Fabien RISSON
Nicolas GAONA

Dcembre 2004

SOMMAIRE
SOMMAIRE...............................................................................................................................2
INTRODUCTION......................................................................................................................1
1 PRESENTATION DES RESEAUX AD-HOC....................................................................2
1-1) Le concept.......................................................................................................................2
1-2) Les avantages et inconvnients des rseaux Ad Hoc .....................................................3
2 LE ROUTAGE DANS LES RESEAUX AD HOC..............................................................5
2-1) Introduction au routage...................................................................................................5
2-2) Le routage proactif..........................................................................................................5
a) Protocole de routage DSDV............................................................................................6
b) Protocole de routage WRP..............................................................................................8
c) Protocole de routage GSR.............................................................................................10
d) Protocole de routage FSR.............................................................................................11
e) Protocole de routage OLSR..........................................................................................12
2-3) Le routage ractif...........................................................................................................13
a) Protocole de routage DSR.............................................................................................14
b) Protocole de routage AODV.........................................................................................16
c) Protocole de routage TORA..........................................................................................17
2-4) le routage hybride..........................................................................................................19
a) Protocole de routage ZRP.............................................................................................19
b) Le protocole de routage CBRP.....................................................................................20
3 LAVENIR DES RESEAUX AD HOC..............................................................................22
3-1) Une technologie militaire..............................................................................................22
3-2) Une technologie apportant des applications inattendues...............................................22
3-3) Un rseau destin aux utilisateurs.................................................................................22
CONCLUSION.........................................................................................................................24

INTRODUCTION
Le monde du sans fil ne cesse de sagrandir, le Wi-Fi et le Blue Tooth sont les agents
principaux de cet essor. Les environnements mobiles permettent la mise en rseau
dquipements o le cblage serait une alternative trop onreuse, trop compliqu mettre en
place voir impossible. Cependant cette mobilit engendre de nouveaux problmes, frquente
dconnexion, dbit de connexion modeste. La principale cause de ces problmes provient du
fait que lon a reproduit larchitecture filaire au sans fil.. Les rseaux Ad Hoc proposent une
alternative, en effet dans la logique Ad Hoc, tous les quipements cooprent au bon
fonctionnement du rseau.
Les rseaux Ad Hoc sont caractriss par leur absence dadministration et par le fait
que tout lment du rseau, tant trs mobile, est susceptible de disparatre. Il ny a pas
dlment fixe au sein dun rseau Ad Hoc. Dans un rseau Ad Hoc, tous les lments doivent
cooprer de manire crer une architecture temporaire pour pouvoir faire transiter les
communications. Pour crer cette architecture afin dacheminer les donnes, les rseaux Ad
Hoc doivent donc utiliser des protocoles de routages performants. Cest la thmatique
principale de ce document.
Ce document est compos de trois parties, la premire propose une brve prsentation
des rseaux Ad Hoc, la seconde dtaille les concepts de routages ainsi que les diffrents
protocoles de routage des rseaux Ad Hoc. Enfin la dernire partie prsente les domaines
dapplications o les rseaux Ad Hoc ont su apporter une solution adapte.

1 PRESENTATION DES RESEAUX AD-HOC

1-1) Le concept
Larchitecture sans fil la plus rpandue aujourdhui est sans conteste larchitecture
cellulaire. Cette architecture est constitue de plusieurs points daccs. Ces points daccs
sont relis entre eux la plupart du temps par une architecture filaire. Chaque point daccs
couvre une certaine zone gographique, appel cellule. Pour communiquer entre elles les
machines doivent dabord passer par ces points daccs, quelles soient ou non dans la mme
cellule. Cela induit que si lun des points daccs devient indisponible, tous les quipements
se trouvant dans la zone gographique couverte par ce point daccs, ne peuvent plus
communiquer.

Fig. 1 : Architecture cellulaire

Lambition des rseaux Ad Hoc est de supprimer cette notion de point daccs, ou plus
exactement de transformer tous les quipements en points daccs. En effet, au sein dun
rseau Ad Hoc, toutes machines le composant devient metteur, rcepteur et routeur pour ses
voisins. Dans un rseau Ad Hoc, les diffrents lments doivent donc cooprer de manire
construire un rseau temporaire. Les units mobiles ayant un rayon de propagation des
donnes restreint, il se peut que le destinataire dune transmission soit hors de porte de
2

lmetteur. A ce moment l lmetteur doit passer par des machines intermdiaires afin
dacheminer la transmission. Etant donn que chaque nud du rseau est mobile, il se peut
quun des nuds disparaisse, il est donc important que le protocole qui gre lacheminement
des paquets soit trs robuste et trs adaptable.

Fig. 2 : Architecture Ad Hoc

1-2) Les avantages et inconvnients des rseaux Ad Hoc

Les rseaux Ad Hoc ont donc en thorie une trs grande robustesse puisque pour
quun rseau local cesse de fonctionner, il faudrait quun nombre important de machines qui
le compose soient hors service. En effet si un des lments du rseau devient indisponible,
cela ne change rien ou presque pour les autres, de nouvelles routes vont tre cres puis
empruntes pour acheminer les donnes comme si llment ne fonctionnant plus navait
jamais exist. Contrairement au rseau sans fil architecture cellulaire o tout dpend de
ltat du point daccs tant donn que toute communication passe par lui.
Le second avantage provient de nos faiblesses technologiques en matire de rseau
sans fil. Il est certain que pour le moment certains obstacles physiques gnent la propagation
des donnes, parfois un simple mur peut stopper une connexion WiFi. Dans un rseau sans fil
cellulaire, si le point daccs se trouve de lautre cot du mur on perd alors la connexion. Dans
un rseau Ad Hoc, si le rcepteur se trouve de lautre cot du mur, lmetteur va chercher
tablir une connexion en passant par un ou plusieurs nud intermdiaire afin de contourner le
3

mur. Dans un rseau Ad Hoc, les obstacles physiques ne sont plus un frein ltablissement
du rseau, mais lisolement. Ce type de rseau parat donc bien adapt au milieu urbain.
Cependant, les rseaux Ad Hoc ne prsentent pas que des avantages. Les donnes pour
rejoindre le destinataire partir de lmetteur vont peut tre devoir traverser de nombreuses
machines et chaque relais travers apportent un dlai supplmentaire. Les rseaux Ad Hoc ont
donc dans la plupart des cas une latence plus importante que les rseaux sans fil cellulaire. Le
second inconvnient est li la nature mme des rseaux Ad Hoc, en effet dans un rseau Ad
Hoc tout les lments cooprent de manire acheminer les donnes y compris les machines
non-concernes par ces donnes. Il y a donc un problme vident de confidentialit, et il est
donc obligatoire dutiliser des outils de cryptage. Ceci entrane aussi un autre problme, les
machines servant de relais utilisent leurs ressources (batterie, carte rseau sans fil, etc.) pour
acheminer des donnes qui ne les concernent pas, en retour dautres machines font de mme
pour leurs transmissions. Enfin il est difficile voir impossible dtablir une qualit de service
sur un rseau Ad Hoc puisque les lments composant une route sont susceptibles de
disparatre tout moment.

??
Fig. 3 : Dans une architecture cellulaire, un simple mur devient un obstacle limitant la porte
du rseau sans fil, dans le cas dun rseau Ad Hoc, lobstacle est contourn.

2 LE ROUTAGE DANS LES RESEAUX AD HOC

2-1) Introduction au routage
Le routage est une mthode dacheminent des informations la bonne destination
travers un rseau de connexions dfini. Son intrt consiste trouver le chemin optimal au
sens dun certain critre de performance (bande passante, dlai, etc.). Il doit aussi tre de
capable de sadapter aux vnements venant perturber le rseau (panne, congestion, etc.).
Dans le cas des rseaux Ad Hoc, larchitecture est caractrise par une absence
dinfrastructure fixe. Il doit donc sorganiser automatiquement et ragir rapidement aux
diffrents mouvements de ses units. Chaque unit devient donc un nud susceptible dtre
mis contribution pour participer au routage.
Pour pallier ce type de problme, il existe deux types de routage bien distinct, le
routage ractif et le routage proactif. Dans le routage ractif, les routes sont cres la
demande, tandis que dans le routage proactif, les routes sont maintenues en permanence. Il
existe enfin des mthodes pour combiner les deux, on parle alors de protocole de routage
mixte. Ces deux types de routages ont chacun leurs avantages et inconvnients.

2-2) Le routage proactif

Les protocoles proactifs sont bass sur la mme philosophie que les protocoles de
routages utiliss dans les rseaux filaires conventionnels. C'est--dire quelle est fonde sur la
mthode tat de lien et vecteur de distance. La mthode tat de lien repose sur le fait que
chaque nud diffuse dans le rseau son voisinage. La mthode vecteur de distance est
base sur la propagation dinformation concernant sa distance tous les nuds du rseau.
Elles exigent des mises jour priodique. Ces deux mthodes, en se basant sur des
algorithmes de routage, recherchent toujours le plus court chemin entre lmetteur et le
rcepteur. Ce calcul repose sur le nombre de saut, ces sauts pouvant tre pondrs selon
diffrents critres (taux dutilisation du lien, dlais, etc.).

Le maintient des tables de routages est ralis par inondation, lors des mises jour
priodique ou lors dun changement dtat dun lien. Linondation consiste propager
lensemble du rseau une information. Lmetteur initial envoie tous ses voisins une
information, ces derniers se chargeant de la rediffuser leurs tours.

Fig. 4 : Lhte A envoie des informations par inondation.

Actuellement ils existent plusieurs protocoles proactifs (DSDV, OLSR, FSR, WRP, GSR,
HSR, ZHLS, CGSR, DREAM).
a) Protocole de routage DSDV
DSDV signifie Vecteur de Distance Dynamique Squence ( Dynamic
Destination-Sequenced Distance Vector ).
Cet algorithme de routage de Perkins a t conu spcialement pour les rseaux
mobiles. Il a t cr partir de lalgorithme distribu de Bellman-Ford.
La mtrique utilise par DSDV est tout simplement le nombre de nud sparant lhte
de la destination.
6

La table de routage de ce protocole prend en compte :

-

Toutes les destinations possibles

Le nombre de sauts ncessaire afin datteindre la destination

Le numro de squence associ chaque nud de destination

Dans un routage vecteur de distance, des boucles de routage peuvent se produire si la

convergence lente d'un rseau avec une nouvelle configuration entrane des entres de routage
incohrentes. Les tables de routage ne peuvent plus assurer alors leur fonction pour une ou
plusieurs destinations, et ainsi tous les paquets destins une entre errone seront transmis
mais ne parviendra jamais lhte de destination et circuleront sur une boucle constitue de
plusieurs routeurs. Pour permettre de faire la distinction entre les anciennes et les nouvelles
routes et ainsi viter les boucles de routage, DSDV utilise les numros de squence (NS). Le
numro de squence est une amlioration apporte lalgorithme distribu de Bellman-Ford.
Pour chaque nud i , un numro de squence de la destination j est associ chaque
entre de distance Dijk pour chaque voisin k .
Un autre problme important est celui de mtrique de mesure infinie, cest dire
lincrmentation du vecteur de distance du nombre de saut linfini par le routeur lors denvoi
de mises jour errones. DSDV rsout ce problme en limitant linfini une valeur relle. Un
lien rompu sera donc matrialis par une valeur suprieure la valeur dfinie comme valeur
infinie.
Le DSDV limine ainsi les deux problmes qui sont la boucle de routage et le
problme de mtrique de mesure infinie.
Les paquets de mise jour contiennent :
- Le nouveau NS incrment, du nud metteur.
- Les informations concernant chaque nouvelle route :
- L'adresse de la destination.
- Le nombre de sauts entre le nud et la destination.
- Le NS (des donnes reues de la destination)
Lors dune mise jour, les donnes reues sont compares avec celle dj disponibles.
La route avec le plus grand NS (donc la plus rcente) sera conserve. Si elle possde le mme
numro de squence alors celle avec la meilleure mtrique sera retenue.

La topologie des rseaux mobiles tant peu stable, chaque nud envoie
priodiquement sa table de routage ses voisins directs mais aussi lors dvnement
entranant la modification de celle-ci.
La mise jour de la table de routage peut seffectuer de manire complte ou de manire
incrmentale. Un nud procdant la mise jour complte transmet sa table en totalit ce qui
implique plusieurs paquets de donnes envoys. Tandis quune mise jour incrmentale
nentrane lenvoie des entres ayant subit un changement donc moins de paquets de donnes
quune mise jour complte.
Dans un rseau assez stable, la mthode incrmentale serait prconise car le nombre
dvnement serait moindre et donc le trafic de mise jour aussi. Dans le cas contraire, les
vnements seront frquents et donc les mises jour compltes aussi.
Avec le protocole DSDV, chaque modification de la table de routage locale dun nud
est aussitt diffuse lensemble de ses voisins. Les routes reues par une diffusion seront
aussi envoyes quand le rcepteur procdera l'envoi de ses paquets de routage. Sans oublier
quil devra incrmenter les mtriques des routes reues avant lenvoi car il reprsente un
nud en plus. Lunit mobile doit alors attendre la prochaine mise jour initie par la
destination afin de mettre jour lentre associe celle-ci rendant ainsi le DSDV lent. De
plus, DSDV utilise les mises jour priodique et bases sur les vnements causant un
contrle excessif au point de vue de la communication.
b) Protocole de routage WRP
WRP signifie Protocole de routage sans-fil ( Wireless Routing Protocol ).
Ce protocole est bas sur les algorithmes de recherche de chemin nomm PFA ( PathFinding Algorithme ). Afin dviter le problme de mtrique de mesure infinie, les PFAs
garde en mmoire le nud prdcesseur du chemin le plus court correspondant chaque
destination.
Par contre, le problme des PFAs est lapparition des boucles de routage temporaires
dans le chemin spcifi du prdcesseur avant la convergence, c'est dire lorsquils auront
une vue prcise et cohrente de la nouvelle topologie du rseau.

Pour rsoudre ce problme, dans WRP, chaque nud maintient :

- une table de distance
- une table de routage
- une table des cots des liens
- une liste de retransmission de messages ( MRL )
La table de distance dun nud i est une matrice contenant pour chaque destination
j et pour chaque voisin k de i , la distance Dijk avec le prdcesseur Pijk de k.
La table de routage dun nud i est reprsente par un vecteur dont chaque entre
est associe une destination j connue. Une entre doit comporter ladresse de destination,
la distance vers celle-ci ( Dij , du plus court chemin), le prdcesseur ( Pij ), le
successeur ( Sij ) et une marque ( tag ij ). Cette marque est utile lors de la mise jour des
tables de routage. En cas de boucle tag ij= error ou en cas de destination non marque
tag ij = null sinon tag ij = correct .
La table des cots des liens dun nud i contient les cots ( Lik ) pour chaque
voisin k et le nombre de dures priodiques de mise jour depuis le dernier message de
type error-free du nud k reu. Le cot dun lien dfaillant est considr comme tant
infini.
La MRL dun nud i sert connatre les voisins k nayant pas acquitts son
message de mise jour et ainsi leur retransmettre.
Les mises jour seffectuent aprs rception des donnes de mise jour dun voisin ou
lors dun changement dtat de lien dun voisin. Les voisins prsents dans la MRL doivent
acquitter aprs rception du message. Si la table de routage na pas t modifie lors de la
dernire mise jour, un message HELLO est cependant envoyer afin de sassurer de la
connectivit. Le protocole WRP vrifie ainsi sa connexion avec ses voisins chaque fois
quun changement dtat dun lien est dtect.
Le protocole WRP permet ainsi daider llimination des boucles de routages mais
aussi de minimiser le temps de convergence du protocole.

c) Protocole de routage GSR

GSR signifie Routage Etat Global ( Global State Routing ).
GSR est semblable DSDV mais comporte quelques amliorations comme la
suppression du mcanisme dinondation des messages de routage et lutilisation de la vue
globale de la topologie du rseau comme les protocoles tats de liens.
Pour ne pas se servir du mcanisme dinondation, GSR utilise la mthode de
dissmination utilise dans le DBF. Chaque nud i maintient :
- une liste de voisins Ai
- une table de topologie TTi
- une table des nuds suivants NEXTi
- une table de distance Di
La table de topologie TTi du nud i contient, pour chaque destination j ,
linformation de ltat de lien telle quelle a t envoye par j et une estampille de
linformation.
La table des nuds suivants NEXTi du nud i contient, pour chaque
destination j , le nud vers lequel les paquets destins j seront envoys.
La table de distance Di du nud i contient la plus courte distance pour chaque
destination j .
Lalgorithme de recherche des plus courts chemins du GSR est un algorithme de
Dijkstra modifi afin quil puisse construire la table des nuds NEXTi et la table des
distances en parallle en parallle avec la construction de l'arbre des plus courts chemins.
Comme les protocoles tat de liens, les messages de routage sont crs suivant les
changements dtats des liens. Lors de la rception de lun de ces messages, il modifie si
ncessaire sa table de topologie (si le NS est suprieur ), puis reconstruit sa table de routage
et enfin diffuse les mises jour ses voisins. En revanche, contrairement aux protocoles
tats de liens, il diffuse ses messages de faon priodique et seulement ses voisins et non
plus par inondation dans tout le rseau chaque vnement. De plus il assure une plus grande
prcision sur les donnes de routage qui schangent dans le rseau.
10

d) Protocole de routage FSR

FSR signifie Routage Etat de lil du poisson ( Fisheye State Routing ).
Ce protocole peut-tre considr comme une volution du protocole GSR. Cette
volution vise encore la diminution de la consommation de la bande passante. Pour cela, FSR
utilise la technique dite de lil du poisson propose par Kleinrock et Stevens.
L'il d'un poisson capture avec prcision les points proches du point focal. La
prcision diminue quand la distance, sparant le point vu et le point focal, augmente. Cette
technique de lil du poisson permet la rduction du volume dinformations ncessaire pour
les donnes graphiques. Elle sous-entend une diminution du dtail et de la prcision plus la
distance augmente. Pour revenir notre contexte du routage, on dfinira la porte ou le champ
de vision du poisson en nombre de sauts, plus un nud est proche plus les donnes
maintenues envers celui-ci seront plus prcises. La rduction du volume des donnes de mise
jour est obtenue en utilisant des priodes dchanges diffrentes pour les diffrentes entres
en fonction de leur distance. Les entres qui correspondent aux nuds les plus proches sont
envoyes aux voisins avec une frquence leve (donc avec une priode d'change
relativement petite). Ainsi un grand nombre de donnes de routage est vit, ce qui rduit le
volume des messages qui circule sur le rseau.
Lutilisation du protocole de routage GSR dans un rseau de grande taille entrane
des messages de mise jour pouvant consommer de faon importante la bande passante. Avec
FSR ce volume peut-tre rduit sans toucher la consistance et la prcision des donnes
de routage grce la technique de lil de poisson et limite par la mme occasion le
travail norme de recherche de chemins effectu dans les protocoles ractifs acclrant la
transmission.

11

Atteignable en 1 saut

Atteignable en 2 sauts

Atteignable en 3 sauts

Fig. 5 : Reprsentation de lil de poisson dans un rseau Ad Hoc

e) Protocole de routage OLSR

OLSR signifie Routage tats de liens optimis ( Optimazed Link State
Routing ).
OLSR est le rsultat du travail d'HIPERCOM, quipe de recherche de l'INRIA
Rocquencourt.
Ce protocole se rapproche du protocole OSPF, protocole tat de liens. Par contre
dans un protocole tat de liens, chaque nud dclare ses liens directs avec ses voisins tout
le rseau, tandis que dans le cas dOLSR, les nuds ne dclarent quune sous-partie de leur
voisinage grce la technique des relais multipoints. Cette technique permet doptimiser la
diffusion des messages de routage conomisant une grande partie de la bande passante du
rseau.
Les relais multipoints consistent essentiellement, en un nud donn, ignorer un
ensemble de liens et de voisins directs, qui ont redondant pour le calcul des routes de plus
courts chemins. Plus prcisment, dans lensemble des voisins dun nud, seul un sousensemble des ces voisins est considr comme pertinent. Il est choisi de faon pouvoir
12

atteindre tout le voisinage deux sauts (tous les voisins des voisins), cet ensemble est appel
lensemble des relais multipoints. Ces relais multipoints sont utiliss pour diminuer le trafic
d la diffusion des messages de contrle dans le rseau, et aussi pour diminuer le nombre de
retransmission tout le rseau puisque les routes sont construites base des relais multipoint.
La diffusion par relais multipoints utilise la rgle suivante : Un nud retransmet un message
si et seulement sil ne lavait pas dj reu, et sil vient de le recevoir dun nud dont il est un
relais multipoint.
Les nuds schangent des informations priodiquement (messages HELLO et
TC ) afin de se maintenir jour.
Les messages HELLO contiennent la liste de leurs voisins pour sinformer du
proche voisinage et permettre ainsi chacun de choisir son ensemble de relais multipoints.
Les messages TC ( Topology Control ) dclarent les sous-ensembles de
voisinage que constituent les relais multipoints. Ils sont diffuss en utilisant une diffusion
optimise par relais multipoints. Ces informations offrent une carte de rseau contenant tous
les nuds et un ensemble partiel des liens, mais suffisant pour la construction la table de
routage. La table de routage est calcule par chacun des nuds et le routage des donnes
seffectue saut par saut sans lintervention dOLSR dont son rle sarrte la mise jour de la
table de routage.

2-3) Le routage ractif.

Le routage ractif est bas sur le principe de louverture de route la demande, ainsi
lorsquun quipement veut communiquer avec une station distante, il est oblig de dterminer
une route dynamiquement. Cette technique permet de ne pas inonder le rseau de paquets de
contrle de routage et de ne conserver que les routes utilises. Lorsque le rseau besoin
dune nouvelle route, un processus de dcouverte de route est alors lanc, ce processus
dpend des diffrents protocoles de routages ractifs. Il existe plusieurs protocoles de
dcouvertes de routes, le backward learning et le routage source sont les plus couramment
utiliss.
Le backward learning consiste ce que la source diffuse par inondation une requte de
recherche de route vers une destination. Lors de la rception dune telle requte, les nuds
intermdiaires compltent leurs tables de routage. Une fois la destination atteinte, celle-ci peut
13

envoyer une rponse en utilisant le chemin trac par la requte. Evidement si un chemin vers
la destination est connu par un des nuds intermdiaires, celui-ci est utilis rduisant ainsi le
temps et le travail ncessaire ltablissement dune route.
Le routage ractif induit forcment une lenteur lors de louverture dune nouvelle
connexion, et lon ne peut prvoir lavance la qualit de la route dcouverte (dlai, bande
passante, etc.). Cependant ces inconvnients sont mineurs par rapport au gain apport la
bande passante, non satur par des paquets de contrle de routage.
Actuellement ils existent plusieurs protocoles ractifs (DSR, AODB, TORA, ABR,
SSR, LAR, RDMAR). Nous allons expliciter les plus importants.
a) Protocole de routage DSR
Le protocole de routage DSR, qui signifie Dynamic Source Routing, utilise la
technique du routage source.
Le routage source consiste ce que la source dtermine un chemin et envoie dans
chaque paquet de donnes tous les nuds traverser pour atteindre la destination. Chaque
nud intermdiaire retire son adresse du paquet avant de le retransmettre. Cette technique
ncessite la connaissance de la route utiliser de la part de la source. Cette connaissance des
routes est obtenue par une table de routage maintenue dans chaque nud. Il faut donc dans un
premier temps dcouvrir les routes, puis les conserver tant quelles existent.
Pour tablir ces routes, chaque nud peut initier une dcouverte dynamique de route.
Pour cela le nud qui lance une telle procdure va inonder le rseau dune requte dcouverte
de route qui identifie la source. Si la requte parvient jusqu la destination, celle-ci renvoie le
paquet la source. Le paquet contient la liste des nuds traverser pour latteindre. En plus
de ladresse de la source le paquet contient la liste de tous les nuds jusqu' prsent visit,
ainsi chaque nud qui reoit le paquet peut dresser partir de celui-ci une table de routage
quil pourra par la suite utiliser. Chaque paquet de requte de route contient un identificateur
unique permettant de dtecter les duplications de ce paquet. Chaque nud du rseau maintient
ainsi une liste de couple <adresse de linitiateur, identificateur de requte> des requtes
reues, chaque entr de la liste possde un temps de vie limit.

14

Lors de la rception d'un paquet requte de route par un nud p du rseau, les
oprations suivantes sont effectues :
-

Dans le cas o le couple <adresse de l'initiateur, identificateur de requte du paquet

reu> existe dj dans la liste des requtes rcemment reues, le paquet est ignor.

Dans le cas contraire, si l'adresse de p existe dans le champ enregistrement de

route du paquet de la requte, le paquet est ignor.

Sinon, si l'adresse de p est la mme que l'adresse de la destination, alors

l'enregistrement de route (contenu dans le paquet de la requte) contient le chemin
travers lequel le paquet de la requte est pass avant d'atteindre le nud p. Une
copie de ce chemin est envoye dans un paquet rponse de route la source.

Sinon, l'adresse de p est ajoute dans l'enregistrement de route du paquet reu, et le

paquet est rediffus.

M4

[1,3,4]

[1,3]

M7
[1,3,5,7]

[1,3,4]
[1,3,5]

M9
[1,3,5]

[1]

M3

[1,3]

[1,3,5,7,9]

M5

M10

M1
[1]

M2

[1,2,6,8]

[1,2]
[1,2,6,8]

M6

[1,2,6]

M8

[1,2,6,8]
[1,2,6,8]

[1,2,6,8]

Fig. 6 : M1 veut trouver une route vers M10,

on voit ici le principe de dcouverte de route par DSR
Pour retourner le paquet, la destination utilise un chemin quelle connat dj, si elle
ne possde pas de chemin pour joindre la source elle peut utiliser le chemin qui se trouve dans
le paquet quelle a reu, si lenvironnement le permet. En effet dans certains rseaux les
nuds ne sont pas forcment bidirectionnels.

15

Les protocoles de routages proactifs maintiennent les chemins dcouverts en

changeant priodiquement des informations de mise jour de leur table de routage, ce nest
pas le cas de ce protocole. Le protocole DSR maintient une route et lutilise jusqu' ce quun
nud du chemin dtecte une erreur de transmission, cette erreur est dtecte par la couche de
liaison de donnes. Lorsque cela se produit, le nud qui a dcouvert lerreur de transmission
envoie un message la source indiquant que le chemin nest plus valide aprs lui. Ainsi la
source peut adapter sa table de routage et doit relancer une nouvelle requte de dcouverte de
route.
Lavantage dun tel protocole rside dans le fait que les nuds intermdiaires nont
pas maintenir de table de routage pour les paquets quils reoivent tant donn que ces
derniers possdent dj toutes les dcisions de routages. De plus on vite les boucles de
routage. Cependant le chemin utilis nest pas forcment optimum, et la dcouverte dun
chemin demande du temps.
b) Protocole de routage AODV
Le protocole de routage AODV, qui signifie Ad Hoc Ondemand Distance Vector, soit
Routage Avec Vecteur de Distance la Demande, est une amlioration du protocole DSDV.
Cette amlioration consiste ne plus maintenir lensemble des routes mais uniquement celle
dont on a besoin. Il conserve cependant les principes de numros de squences et de routage
nud par nud. Les numros de squences permettant de dater une route, et dutiliser ainsi la
plus rcente. Cette notion est importante dans un rseau Ad Hoc qui est suppos tre trs
dynamique.
La dcouverte des routes suit le mme principe que DSR, cependant les informations
stockes au niveau de chaque nud au sein des tables de routages diffrent, de plus la
maintenance des routes nest pas gre de la mme manire.
Au niveau de la dcouverte des routes, AODV conserve sur chaque nud de transit
des informations sur la route dcouverte, les tables de routages AODV contiennent :
- ladresse de destination
- le nud suivant
- la distance en nombre de nuds traverser
- le numro de squence de destination
- le temps dexpiration de lentr de la table.
16

Lorsquun nud reoit un paquet de dcouverte de route, il note aussi dans sa table de
routage les informations du nud source et du nud qui vient de lui envoyer le paquet, ainsi
il sera capable de retransmettre le paquet rponse. Ceci implique que les liens sont forcment
symtriques. Le champ numro de squence de destination dune requte de dcouverte de
route est nul si la source na jamais eut de lien avec la destination, sinon il utilise le dernier
numro de squence connu. Il indique aussi dans cette requte son propre numro de
squence. Lors dun envoie dune requte de dcouverte de route, la source attend un certain
moment avant de rediffuser sa requte de recherche de route, au bout dun certain nombre
dessais, il dfinit que la source est injoignable.
Le maintient des routes seffectue par lenvoie priodique de message court, appel
requte "HELLO", si trois messages conscutifs ne sont pas reus partir dun voisin le lien
en question est considr comme dfaillant. Quand un lien reliant deux nuds dun chemin de
routage devient dfaillant, les nuds diffusent des paquets pour indiquer que ce lien nest plus
valide. Une fois que la source est prvenue, elle peut relancer un processus de dcouverte de
routes. AODV maintient ses tables de routages selon leur utilisation, un voisin est considr
comme actif tant quil dlivre au nud des paquets pour une destination donn, au-del dun
certain temps sans transmission, le voisin est considr comme inactif. Une entr de la table
de routage est considre comme actif, si au moins un des voisins actifs lutilise, le chemin
reliant la source et la destination en passant par les entres actives des tables de routage est
appel chemin actif. Si une dfaillance de lien est dtecte, toutes les entres des tables de
routage participant au chemin actif sont supprimes.
Tout comme DSR, AODV ne permet pas de dcider du chemin optimum, cependant il
vite lui aussi les boucles de routage.
c) Protocole de routage TORA
TORA signifie Algorithme de Routage Ordonn Temporairement ( Temporary
Ordering Routing Algorithm ).
TORA sattaque aux problmes dconomie de la bande passante en tentant de
minimiser leffet des frquents changements de la topologie, particularit des rseaux Ad Hoc
due la mobilit des noeuds.
Afin dy parvenir, la recherche du meilleur chemin est dlaisse non pas en terme de
calcul mais en terme de procdure. De cette manire un protocole pourra choisir un plus long
17

chemin entre la source et le nud destination dans le but dviter le processus, coteux, de
dcouverte de nouveau voisin. De plus, TORA conserve plusieurs chemins vers une mme
destination et non plus seulement le meilleur chemin ce qui a pour consquence de limiter les
effets induits par une modification de la topologie sur le routage des donnes.
Le protocole est aussi caractris par la limitation des messages de contrle
lensemble des nuds proches de lvnement.
TORA est bas sur lutilisation de la proprit appele "orientation destination" des
graphes acycliques orients. Un graphe est orient si les liens qui le composent ont une
direction, cest dire quun lien nest pas forcment bidirectionnel. Un graphe acyclique
signifie que le graphe ne possde aucune boucle. Un graphe acyclique orient est dit orient
destination s'il y a toujours un chemin possible vers une destination spcifie. Lorsque le
graphe perd un ou plusieurs arcs de manire devenir non orient destination, alors les
algorithmes utilisent le concept dinversement de lien pour permettre de retrouver un graphe
orient destination. Pour raliser ceci, TORA utilise le concept de taille des nuds, la
destination possde une taille nulle, et chaque nud a pour taille, celle de son voisin
possdant la plus petite taille incrment de un.

[1,2]

[2,1]

Destination
Source
Source
[2,0] Destination

[0,2]

[1,1]
Fig. 7 : Taille des nuds avec TORA

18

2-4) le routage hybride

Le modle hybride apparat comme un bon compromis qui dun ct utilise une
procdure de dtermination sur demande et de lautre un cot de recherche limit.
Il existe plusieurs protocoles hybrides tels que le protocole de routage ZRP et
CBRP que nous allons expliciter.
a) Protocole de routage ZRP
ZRP signifie Protocole de zone de routage ( Zone Routing Protocol ).
Le protocole de routage ZRP est un modle hybride entre un schma proactif et un
schma ractif. Il est bas sur deux procdures : le protocole de routage intrazone, nomm
IARP et le protocole de routage interzone, nomm IERP.
IARP est utilis uniquement lintrieur de la zone de routage. Cette zone est dfinie
pour chaque nud et comporte une taille de rayon correspondant une valeur de nombre de
saut. Par exemple, pour un nud, si cette valeur vaut deux alors tous les nuds ayant une
distance suprieure deux sauts ne feront pas parti de la zone de ce nud. Les nuds se
trouvant une distance de deux nuds seront les nuds priphriques ce nud. La valeur
doit tre fixe par ladministrateur rseau et est quivalente pour chaque nud du rseau. Elle
est importante car elle dtermine la performance du protocole ZRP. Plus un rseau est instable
plus il est essentiel que la valeur soit faible.
IARP est gnralement implment par des protocoles proactifs varis mais comme
cela nest pas vraiment spcifi, il peut ltre partir de diffrents protocoles comme des
drivs de protocoles vecteur de distance (AODV). Le protocole doit de toute faon
dterminer la distance qui spare le nud des autres nuds du rseau afin quil dlimite sa
zone de routage. Cependant quel que soit le choix, le protocole ncessite dtre modifi afin
de le restreindre la zone de routage du nud ce qui limite ainsi les mises jour. Le contenu
de la zone est connu par le nud mais en contre partie il na aucune information concernant
les autres nuds appartenant linterzone.

19

Grce ce partage entre intrazone et interzone, les changements de topologies du

rseau ont uniquement un impact local et nest plus rpercut lautre bout du rseau ce qui
rduit lutilisation de la bande passante du rseau.
IERP est responsable dtablir des liens avec les nuds situs dans linterzone. Pour
cela, il sappuie sur les techniques de bordercasting (via BRP : Protocole de Rsolution
Bordercast) qui permet denvoyer un paquet tous les nuds priphriques.
Lors dune demande de route, IERP vrifie tout dabord que le destinataire ne soit pas
prsent dans lintrazone (pas de requte, la source connat son contenu). Sil est prsent alors
aucun processus de connexion nest ncessaire. En revanche, sil ne sy trouve pas alors la
source fait une demande dtablissement de route ( Route Request ) tous les nuds
priphriques. Les nuds priphriques, la rception du message, effectuent la mme
opration. Chaque nud recevant la requte inscrit son identificateur lintrieur avant de la
renvoyer, cela sappelle le processus daccumulation de route. Le nud priphrique
contenant la destination dans sa zone de routage lui rpond, laide des identificateurs
prsents dans la requte, par un signal Route Reply en lui indiquant le chemin emprunter
pour latteindre. Comme il prfrable quune requte de type Route Request ne soit pas
retransmis une zone qui a t dj parcourue, IERP utilise deux mcanismes. Le premier tue
les messages qui contiennent un identificateur dun nud prsent dans son intrazone (except
sil sagit du nud prcdent videmment). Le suivant est un mcanisme complmentaire qui
enregistre lidentificateur de lhte dans sa liste de requte uniquement en priode de Route
Request afin dignorer une requte dj formule auparavant.
IERP dispose galement dun mcanisme de rponse ractive aux erreurs de route
lorsque le saut suivant est dtermin comme inaccessible. Un paquet Route Failure est
alors envoy la source pour lavertir et la voie de communication ayant expire est retire de
la table de routage interzone. IERP peut tre configur afin de rparer localement la route
interzone endommage avec une procdure dtablissement de route vers le nud
inaccessible.
b) Le protocole de routage CBRP
CBRP signifie Protocole de Routage Bas sur les groupes ( Cluster Based
Routing Protocol ).

20

Dans CBRP, le rseau est dcompos en groupe. Chaque groupe est constitu de
nud membres et un reprsentant de groupe. Un nud nayant pas de statut (ni membre, ni
reprsentant) active un timer et diffuse un message HELLO . Lorsquun reprsentant dun
groupe reoit ce message, il envoie immdiatement une rponse la source. A sa rception, le
nud peut alors devenir membre ce groupe condition que lattente de la rponse nait pas
dpasse le timeout. En cas de dpassement du timeout et si le nud possde au moins un lien
bidirectionnel vers un nud voisin, le nud peut se proclamer reprsentant dun groupe.
Sinon il reste dans ltat indcid et rpte la mme procdure mais linstabilit des rseaux
Ad Hoc fait que lattente des nuds indcids soit souvent courte.
Les nuds maintiennent une table des voisins dont chaque entre est associe un
voisin. Elle indique ltat des liens (uni ou bidirectionnel) et le statut du voisin.
Le reprsentant dun groupe regroupe les informations concernant les membres de son
groupe et possde une table contenant les groupes adjacents. Une entre de cette table est
associe un groupe voisin. La table des groupes adjacents contient lidentificateur du
groupe, lidentificateur du nud de son groupe permettant la liaison avec ce groupe, et
lidentificateur du reprsentant de ce groupe.
La requte de demande de chemin seffectue par inondation et est destine uniquement
aux reprsentants des groupes voisins. Un reprsentant de groupe recevant ce message
vrifiera, en utilisant sa table de membres de groupes, lexistence du nud de destination dans
son groupe. Sil sy trouve, il lui envoie directement la requte. Dans le cas contraire, il fait
poursuivre le message aux autres reprsentants voisins en y inscrivant au pralable son
adresse. Un reprsentant pourra ainsi ignorer les requtes dj traites. Quand la requte
parvient au destinataire, celui-ci rpond par lenvoi du chemin qui a t sauvegard dans le
paquet de la requte. Si le nud source ne reoit pas de rponse au bout dune certaine
priode, il envoie de nouveau la requte.
Lorsquun nud dtecte un lien dfaillant pendant lacheminement des donnes, il
retourne un message derreur la source et applique un mcanisme de rparation locale. Ce
mcanisme cherche si le nud inaccessible ou le nud aprs celui-ci dans le chemin peut-tre
atteint travers un autre voisin. En cas de russite, les donnes sont achemines en utilisant le
chemin rpar.

21

3 LAVENIR DES RESEAUX AD HOC

3-1) Une technologie militaire
Cest sans relle surprise que les premiers utilisateurs de cette technologie soient les
militaires. Mis au point avant tout pour crer des groupes mobiles qui possderaient un rseau
de communication sans fil avec une souplesse et une robustesse plus importante.
Linconvnient majeur ici dun rseau sans fil avec borne daccs serait quune seule unit du
groupe servirait de relais pour tout le groupe, or si cette unit venait tre injoignable, tout le
groupe serait sans rseau. Cest pour la mme raison que lon utilise cette technologie lors
dexpdition dexploration ou de secourisme.
3-2) Une technologie apportant des applications inattendues
Mais lemploi des rseaux ad hoc ne se limite pas a cette configuration. Certaine
socit pense dvelopper lInternet sans fil dans les zones urbaines. Lune delle a imagin
crer un rseau de transports en commun o il serait possible de se connecter sur Internet
lintrieur de ces transports. Ici la technologie Ad Hoc serait utilise pour relier les points
daccs de chaque transporteur entre eux.
Les rseaux Ad Hoc ont aussi un avenir dans les milieux urbains, il est en effet
concevable de crer des rseaux Ad Hoc de la taille dune ville et de crer ainsi un rseau
communautaire sans passer par les architectures propritaires.
3-3) Un rseau destin aux utilisateurs
Le dernier point important concernant les rseaux Ad Hoc ne concerne pas la
technique mais plus une idologie. En effet une communaut sest cre pour promouvoir les
rseaux sans fil citoyen incitant fortement les utilisateurs semparer de ce concept. On parle
dun Internet organique, cest dire libre, des serveurs mis disposition de la communaut,
de la tlvision et de la radio de voisinage en accs libre, et mme dun contenu accessible
librement sur les mobiles. Il est question dun rseau libr du corporatisme et du commerce,
qui cesserait de privilgier la recherche du profit au dtriment de la performance, dun rseau
gr par les utilisateurs pour les utilisateurs (http://www.communitywireless.com).

22

Les rseaux Ad Hoc pourrait devenir une technologie bon march permettant de crer
des rseaux mtropolitains sans fil efficaces, auto grs et libre daccs. Cette utilisation
favoriserait de plus lexpansion des technologies sans fil tel que le WiFi.

23

CONCLUSION
Les rseaux informatiques sans fil se distinguent en deux catgories, les rseaux sans
fil avec une infrastructure prexistante et fixe, et les rseaux sans fils sans infrastructure. Le
premier modle est gnralement utilis avec larchitecture cellulaire ou chaque point daccs
est reli aux autres par linfrastructure fixe et couvre une certaine zone appele cellule.
Lautre modle est reprsent par les rseaux Ad Hoc et tend les notions de mobilit a tous
les lments composant le rseau. Il est possible de mlanger les deux modles en crant un
rseau Ad Hoc reli dautres rseaux Ad Hoc par des infrastructures fixes.
Dans les rseaux Ad Hoc, tout quipement peut tre mis contribution pour acheminer
des donnes qui ne le concerne pas et chaque nud participe une stratgie de routage afin
que tous les nuds puissent ensemble crer un rseau efficace.
Cest pour cela que les protocoles de routages mis en oeuvre dans les rseaux Ad Hoc
ont une importance cruciale, il est impensable de vouloir crer un routage statique dans un
environnement mobile et les protocoles de routages doivent tre trs ractifs la dynamique
du rseau. Cette tude a montr les diffrentes techniques utilises par les protocoles de
routages pour les rendre plus ractifs en consommant un minimum de bande passante. Ces
protocoles sont diviss en deux catgories. Les protocoles de routage proactif qui tentent de
maintenir jour une reprsentation actuelle du rseau, et les protocoles de routage ractifs qui
dterminent une route uniquement en cas de besoin. Il existe aussi les protocoles mlangeant
les deux procds, ce sont les protocoles de routage hybride.
Cette tude montre quil existe de nombreux protocoles de routage pour les rseaux
Ad Hoc ayant chacun leurs avantages et inconvnients, il nexiste pas de protocole meilleur
que les autres mais certains sont plus adapts que dautres suivants les situations.

24