Upload
lina-mjahed
View
235
Download
0
Embed Size (px)
Citation preview
8/3/2019 Chapitre 2 rseaux ad hoc
1/16
Chapitre 2
Les Rseaux Mobiles Ad Hoc
&
les Protocoles de Routage
2.1. Introduction
Les rseaux sans fil (Wireless LAN ou WLAN ou IEEE 802.11), offrent
aujourd'hui de nouvelles perspectives dans le domaine des tlcommunications. Cest
un systme de transmission des donnes, conu pour assurer une liaison indpendante
de l'emplacement des priphriques informatiques qui compose le rseau. Les rseaux
sans fil sont principalement employ lorsqu'il s'agit d'interconnecter des utilisateurs
nomades (par exemple des portables) entre eux.
Ce systme ne pose aucune restriction sur la localisation des usagers. Il utilise
des ondes radio plutt qu'une infrastructure cble pour communiquer. Ce nouveau
mode de communication engendrent de nouvelles caractristiques, propres
lenvironnement mobile : de frquentes dconnexions, un dbit de communication et
des ressources modestes, et des sources dnergie limites.
Les rseaux mobiles peuvent tre classs en deux grandes classes :
Rseau sans fil avec infrastructure (comme le GSM).
Rseau sans fil sans infrastructure (comme les rseau ad hoc).
Cette deuxime classe de rseaux sans fil constitue la base de notre sujet
dtude, et cest ce que lon va dvelopper dans ce prsent chapitre.
Dans le but de bien comprendre les stratgies et les approches utilises dans la
conception des protocoles permettant aux rseaux ad hoc de se relier Internet, nous
allons, tout dabord, prsent le routage dans les rseaux ad hoc eux-mmes. Aprs
avoir dcrit les rseaux ad hoc et leurs principales caractristiques, nous prsenterons
les principes des protocoles de routages inter ad hoc les plus connus.
8/3/2019 Chapitre 2 rseaux ad hoc
2/16
LES RESEAUX AD HOC &CHAPITRE 2 LES PROTOCOLES DE ROUTAGE
16
2.2. La transmission radio dans les environnements sans fil
La transmission radio utilise dans la communication sans fil est base sur le
principe que l'acclration d'un lectron cre un champ lectromagntique qui, son
tour acclre d'autres lectrons et ainsi de suite. Il est alors possible de provoquer undplacement lectromagntique [3]. Ce dplacement coordonn d'lectrons peut alors
servir pour le transfert d'information et constitue la base de la communication sans fil.
Deux signaux sur la mme frquence interfrent et s'altrent mutuellement.
Pour y remdier, le spectre de frquence est divis en plusieurs parties (bandes de
frquence), chaque partie est ddie une utilisation spcifique. La taille limite du
spectre de frquence impose donc le regroupement d'usagers dans des bandes. Par
exemple, la bande de 25 Mhz 890 Mhz est rserve aux missions de tlvision et la
bande suprieure 890 Mhz pour la tlphonie cellulaire et la transmission par satellite
[3].
2.3. Modes de communication dans les rseaux mobile
La communication dans les rseaux mobiles Ad Hoc utilise plusieurs modes
dont : la communication point point ou Unicast , la communication
multipoint ou Multicast , et la diffusion Brodcast . Ces trois modes de
communication peuvent tre schmatiss par la figure 2.1.
Figure 2.1 :Les diffrents modes de communication
Multicast
Groupe Multicast
S : SourceD : Destination
Transmission
Unicast Broadcast
Transmission
8/3/2019 Chapitre 2 rseaux ad hoc
3/16
LES RESEAUX AD HOC &CHAPITRE 2 LES PROTOCOLES DE ROUTAGE
17
2.4.Les classes de rseaux mobiles
Dans lespace des rseaux mobiles, nous pouvons distinguer deux classes de
rseaux, savoir, les rseaux mobiles bass sur une infrastructure de communication
(modle cellulaire), et les rseaux mobiles sans infrastructure (modle ad hoc).
2.4.1. Les rseaux avec infrastructure (cellulaires)
Dans ce mode, le rseau sans fil est compos de deux ensembles d'entits
distinctes : les sites fixes d'un rseau de communication filaire classique, et les sites
mobiles . Certains sites fixes, appels stations de bases (SB) sont munis d'une interface
de communication sans fil pour la communication directe avec les sites ou les units
mobiles (UM) localiss dans une zone gographique limite, appele cellule.
Chaque station de base dlimite une cellule partir de laquelle des unitsmobiles peuvent mettre et recevoir des messages. Alors que les sites fixes sont
interconnects entre eux travers un rseau de communication filaire, gnralement
fiable et d'un dbit lev. Les liaisons sans fil ont une bande passante limite qui rduit
svrement le volume des informations changes.
Dans ce modle, une unit mobile ne peut tre, un instant donn, directement
connecte qu' une seule station de base. Elle peut communiquer avec les autres sites
travers la station laquelle elle est directement rattache. L'autonomie rduite de sa
source d'nergie, lui occasionne de frquentes dconnexions du rseau; sa reconnexion
peut alors se faire dans un environnement nouveau voire dans une nouvelle localisation.
8/3/2019 Chapitre 2 rseaux ad hoc
4/16
LES RESEAUX AD HOC &CHAPITRE 2 LES PROTOCOLES DE ROUTAGE
18
Figure 2.2 :Le rseau cellulaire (GSM)
A fin dagrandir la surface de couverture, plusieurs points d'accs1
peuvent tre
installs pour un mme groupe de travail2
. Dans le cas d'utilisateurs mobiles, il y'a
possibilit de passer d'un point d'accs un autre sans perte de lien rseau (comme pourun rseau GSM schmatiser dans la figure 2.2). Cette fonctionnalit s'appelle
"Roaming".
2.4.2. Les rseaux sans infrastructure (AD HOC)
2.4.2.1. Dfinition dun rseau ad hoc
Un rseau mobile Ad Hoc ( figure 2.3), appel gnralement MANET (Mobile Ad hoc NETwork), consiste en une grande population, relativement dense, d'units
mobiles qui se dplacent dans un territoire quelconque. Le seul moyen de
communication est l'utilisation des ondes radio qui se propagent entre les diffrents
nuds mobiles, sans l'aide d'une infrastructure prexistante ou administration
centralise.
1 Points daccs sont les stations de base.2 Groupe de travail est un ensemble dunits mobiles connectes une mme station de base.
8/3/2019 Chapitre 2 rseaux ad hoc
5/16
LES RESEAUX AD HOC &CHAPITRE 2 LES PROTOCOLES DE ROUTAGE
19
Figure 2.3 : un rseau Ad Hoc.
La topologie du rseau peut changer tout moment, elle est donc dynamique etimprvisible ce qui fait que la dconnexion des units soit trs frquente (figure 2.4).
Figure 2.4 : Le changement de la topologie des rseaux Ad Hoc
2.4.2.2. Les caractristiques des rseaux Ad Hoc
Les rseaux sans fil ad hoc se caractrisent principalement par :
Bande passante limite : Une des caractristiques primordiales des rseaux basssur la communication sans fil est l'utilisation d'un mdium de communication
partag (ondes radio). Ce partage fait que la bande passante rserve un hte soit
modeste.
Contraintes d'nergie : Les htes mobiles sont aliments par des sources d'nergieautonomes comme les batteries ou les autres sources consommables. Le paramtre
d'nergie doit tre pris en considration dans tout contrle fait par le systme.
Nud mobile
Lien de communication
8/3/2019 Chapitre 2 rseaux ad hoc
6/16
LES RESEAUX AD HOC &CHAPITRE 2 LES PROTOCOLES DE ROUTAGE
20
Scurit physique limite : Les rseaux mobiles Ad Hoc sont plus touchs par leparamtre de scurit que les rseaux filaires classiques. Cela se justifie par les
contraintes et limitations physiques qui font que le contrle des donnes transfres
doit tre minimis.
Erreur de transmission : Les erreurs de transmission radio sont plus frquentesque dans les rseaux filaires.
Interfrences : Les liens radios ne sont pas isols, deux transmissions simultanes
sur une mme frquence ou, utilisant des frquences proches peuvent interfrer [5].
Absence d'infrastructure : Les rseaux ad hoc se distinguent des autres rseaux
mobiles par la proprit d'absence d'infrastructures prexistante et de tout genre
d'administration centralise. Les htes mobiles sont responsables d'tablir et de
maintenir la connectivit du rseau d'une manire continue.
Topologie dynamique : Les units mobiles du rseau se dplacent d'une faonlibre et arbitraire. Par consquent, la topologie du rseau peut changer des instants
imprvisibles, d'une manire rapide et alatoire.
Nuds cachs : Ce phnomne est trs particulier lenvironnement sans fil. Unexemple est illustr par la figure 2.5. Dans cet exemple, les nuds B et C ne
sentendent pas, cause dun obstacle qui empche la propagation des ondes. Les
mcanismes daccs au canal vont permettre alors ces nuds de commencer leurs
missions simultanment. Ce qui provoque des collisions au niveau du nud A [5].
Figure 2.5 :Les nuds cachs
2.4.2.3. Les applications des rseaux mobiles Ad Hoc :
Les applications ayant recours aux rseaux ad hoc couvrent un trs large
spectre, incluant les applications militaires et de tactique, lenseignement distance, les
oprations de secoursetc.
D'une faon gnrale, les rseaux ad hoc sont utiliss dans toutes applications
o le dploiement d'une infrastructure rseau filaire est trop contraignant, soit parce
Nud mobile
Lien de
communication
Obstacle
8/3/2019 Chapitre 2 rseaux ad hoc
7/16
LES RESEAUX AD HOC &CHAPITRE 2 LES PROTOCOLES DE ROUTAGE
21
quil est difficile le mettre en place, soit parce que la dure d'exploitation du rseau ne
justifie pas de cblage demeure [3].
2.5. Le routage dans les rseaux ad hoc
Pour mieux comprendre les stratgies et les approches utilises dans la conception
des protocoles permettant aux rseaux ad hoc de se relier Internet, nous allons, tout
dabord, parler du routage lintrieur des rseaux ad hoc. Dans ce qui suit nous allons
prsenter les principes des protocoles de routages inter ad hoc les plus connus.
2.5.1. Dfinition du routageLe routage est une mthode travers laquelle on fait transiter une information
donne depuis un certain metteur vers un destinataire bien prcis. Le problme duroutage ne se rsume pas seulement trouver un chemin entre les deux nuds du
rseau, mais encore trouver un acheminement optimal et de qualit des paquets de
donnes.
2.5.2. Difficult de routage dans les rseaux Ad HocAfin de palier aux problmes dues aux diffrents mouvements des nuds
mobiles qui pourront modifier le trafic, un rseau ad hoc doit donc pouvoir
sordonnancer automatiquement de tel sorte tre dployable rapidement, et de pouvoir
saccommoder aux conditions de propagation. Dans le cas o le nud destinataire se
trouve dans la porte du nud metteur nous naurons pas besoin de routage
proprement dit, malheureusement ce nest pas toujours le cas, en effet, chaque nud
sera donc susceptible de jouer un rle dans lacheminement du paquet vers sa
destination finale. Ce qui nous pousse dire quil se peut que plusieurs nuds puisse
participer au routage. Nous parlons alors dun environnement dit "multihop"3.
Autrement dit, chaque nud participera au processus de routage du paquet.
Vu les modestes capacits de calcul et de sauvegarde dont est caractris un
rseau ad hoc, et la taille du rseau, il est trs important de signaler que les mthodes et
les approches utiliss pour lacheminement des paquets dans le rseau sont videmmentdiffrentes et plus complexes mettre en uvre par rapport celles utilises dans les
rseaux classiques (statique). Ce qui nous pousse dire que la gestion du routage dans
un environnement ad hoc diffre de loin celle utilise dans les rseaux filaires. [3]
2.6. Classification des protocoles de routageLe principal but de toute stratgie de routage est de mettre en uvre une bonne
gestion dacheminement qui sot robuste et efficace. Dune manire gnrale, toute
3
Le nombre de stations mobiles qui peuvent tre utilise comme routeurs intermdiaires peut dpasser leun
8/3/2019 Chapitre 2 rseaux ad hoc
8/16
LES RESEAUX AD HOC &CHAPITRE 2 LES PROTOCOLES DE ROUTAGE
22
stratgie de routage repose sur des mthode et des mcanismes que lon peu regrouper
en trois grandes classes : les protocoles de routage proactifs, les protocoles de routage
ractifs et les protocoles de routage hybrides.
2.6.1. Les protocoles de routage proactifsUn protocole de routage est dit proactif si les procdures de cration et de
maintenance des routes, durant la transmission des paquets de donnes, sont contrles
priodiquement. Cette maintenance reste toujours active mme sil ny a pas de trafic
circulant dans le rseau.
Deux principales mthodes sont utilises dans cette classe de protocoles
proactifs : la mthode Link state et la mthode Distance Vector. Ces mthodes sont
utilises aussi dans les rseaux filaires. Parmi les protocoles de routages proactifs les
plus connus on citera le DSDV, FSR, OLSR
a- Link StatDans cette mthode, chaque nud garde une vision de toute la topologie du
rseau et ce par lintermdiaire des requtes priodiques portant sur ltat des liaisons
avec les nuds voisins. En effet la mise jour dans cette mthode se fait pour chaque
nud diffusant ltat des liens des nuds voisins dans le rseau. Cette opration est
aussi faite en cas de changement dans ltat des liens [3] [64] [65] [66].
b- Distance VectorDans cette mthode par contre, chaque nud diffuse ses nuds voisins sa
vision des distances qui le sparent de tous les htes du rseau. En se basant sur les
informations reues par tous ses voisins, chaque nud de routage fait un certain calcul
pour trouver le chemin le plus court vers n'importe quelle destination. Le processus de
calcul se rpte, s'il y a un changement de la distance minimale sparant deux nuds, et
cela jusqu' ce que le rseau atteigne un tat stable. Cette technique est base sur
l'algorithme distribu de Bellman Ford (DBF) [67] [68] [69] [70] [71].
2.6.2. Les protocoles de routage ractifs ( la demande)
Ce sont des protocoles dans lesquels la mise jour ou le contrle des routes se
fait la demande, c'est--dire lorsquune source veut transmettre des paquet de donnes
vers une destination. Dans ce cadre plusieurs politiques peuvent tre adoptes, les plus
importantes sont :
a. La Technique dapprentissage en arrireLe mcanisme dapprentissage en arrire ou le backward learning [20]est bas
sur le fait que lorsquun nud source veut transmettre un message une destinationprcise, il procde tout dabord lopration dinondation de sa requte sur tout le
8/3/2019 Chapitre 2 rseaux ad hoc
9/16
LES RESEAUX AD HOC &CHAPITRE 2 LES PROTOCOLES DE ROUTAGE
23
rseau. Ainsi chaque nud intermdiaire dit de transit (appartenant au chemin par
lequel va passer le message), indique le chemin au nud source lors de la rception de
la requte.
On dit quil apprend le chemin au nud source, tout en sauvegardant la route dansla table transmise. Enfin, lorsque la requte arrive bon port, le nud destinataire, et
suivant le mme chemin, transmet sa rponse sous forme de requte. Notons que le
chemin tablit entre les nuds est un chemin Full duplex. Signalant aussi que la source
garde trace du chemin tant quil restera en cours dutilisation une fois que le chemin
sera calcul.
b. Technique du routage sourceDans cette technique, le nud source dtermine toute la liste des nuds par
lesquels doit transiter le message, ainsi le nud metteur inclut dans lentte du paquet
une route source. En effet, afin de construire la route, le nud source doit prciser lesadresses exactes des nuds par lesquels le message transitera jusqu' atteindre le
destinataire. Ainsi, le nud source transmet le paquet au premier nud spcifi dans la
route. Notons que chaque nud par lequel le paquet transit, supprime son adresse de
lentte du paquet avant de le retransmettre. Une fois que le paquet arrive sa
destination, il sera dlivr la couche rseau du dernier hte.
Plusieurs protocoles de routage ractifs existent dont lAODV, TORA, DSRetc.
2.6.3. Les protocoles de routages Hybrides
Les protocoles hybrides combinent les deux ides : celle des protocoles
proactifs et celle des protocoles ractifs. Ils utilisent un protocole proactif pour avoir des
informations sur les voisins les plus proches (au maximum les voisins deux sauts).
Au-del de cette zone prdfinie, le protocole hybride fait appel aux techniques des
protocoles ractifs pour chercher des routes.
Ce type de protocoles sadapte bien aux grands rseaux, cependant, il cumule
aussi les inconvnients des protocoles ractifs et proactifs en mme temps (messages de
contrle priodique, le cot douverture dune nouvelle route). Plusieurs protocoles
hybride existent dont le CBRP et le ZRP (Zone Routing Protocol) [13].
2.7. Quelques protocoles de routages unicast
Dans ce qui suit, on va dcrire trois protocoles de routages, conus pour les
rseaux ad hoc :
Le protocole DSDV.
Le protocole AODV.
Le protocole ZRP.
8/3/2019 Chapitre 2 rseaux ad hoc
10/16
LES RESEAUX AD HOC &CHAPITRE 2 LES PROTOCOLES DE ROUTAGE
24
Nous avons choisit ces trois protocoles, suivant les trois grandes classes de
protocoles de routages cits ci-avant.
2.7.1.Le protocole DSDV
Le DSDV ( Dynamic Destination-Sequenced Distance-Vector) [17] est
principalement inspir de lalgorithme distribu de Bellman Ford (DBF : DistributedBellman-Ford) [17]. Toute fois, chaque station mobile se voit maintenir une table deroutage contenant :
Toutes les destinations possibles dans le rseau.
Le nombre de nuds (ou de sauts) ncessaire pour atteindre chacune de ces
destinations.
Le numro de squences (SN : Squence Number) qui correspond un nuddestination [3].
Afin de conserver la consistance des tables de routages dans un rseau, souvent
connue par la forte variation de la topologie, chaque nud est attribu un numro de
squence NS qui permet de distinguer les nouvelles routes des anciennes. Ce qui permet
de remdier au problme de boucle de routage. Ainsi chaque nud transmet son
voisin direct sa table de routage priodiquement ou en cas de changement imprvu de la
table. Donc, la mise jour se fait selon deux facteurs : le temps et les vnements qui
peuvent surgir (dplacement de nuds, apparition dun nouveau voisin ...etc). Vu ces
deux facteurs, on peut distinguer deux types de mise jour [19] :
Mise jour complte : qui nest rien autre que la mise jour priodique, c'est-
-dire que le nud transmet la totalit de sa table de routage vers ses voisins.
Mise jour incrmentale : cette mise jour nest faite quen cas dvnements
(Apparition dun nouveau voisin, disparition dun nud ...etc.), et dans ce cas il ny a
que lentre concernant le nud en question dans la table de routage qui change. Cette
mise jour est aussi ditemise jour partielle.
Notons que la mise jour se fait travers la transmission dun paquet
gnralement contenant :
Le nouveau numro de squence, incrment, du nud metteur.
L'adresse de la destination.
Le nombre de sauts sparant le nud de la destination.
Le numro de squence (des donnes reues de la destination) tel qu'il a t
estampill par la destination.
8/3/2019 Chapitre 2 rseaux ad hoc
11/16
LES RESEAUX AD HOC &CHAPITRE 2 LES PROTOCOLES DE ROUTAGE
25
Figure 2.6 :Exemple dun rseau Ad Hoc
Si lon considre que le DSDV est le protocole de routage utilis dans la figure
3.2, la table de routage correspondante au nud M1 ressemblera la suivante :
Destination Nombre de sauts Prochain nud Numro de squence
M1 0 M1 NS1
M2 1 M2 NS2
M3 2 M2 NS3
M4 1 M4 NS4
M5 2 M4 NS5
M6 3 M4 NS6
Figure 2.7 : Table de routage du nud M1 du graphe 2.6.
Ainsi tout nud, qui a subit une mise jour, compare les donnes de routage
reus avec les siennes, et la route la plus rcente (celle avec la plus grande valeur du
numro de squence) sera utilise. Si deux routes ont le mme numro de squence,alors la route qui possde la meilleure mtrique est celle qui sera utilise. La mtrique
utilise dans le calcul des plus courts chemins est, tout simplement, le nombre de nuds
intermdiaires existants sur ce chemin. Un lien rompu est matrialis par une valeur
infinie de sa mtrique, i.e. une valeur plus grande que la valeur maximale permise par la
mtrique [3].
Parmi les inconvnients du protocole DSDV, est quil est trs lent, du fait quil
doit attendre la mise jour transmise par le destinataire pour modifier lentre adquate
dans la table de distance. Bien quil remdie au problme de boucle de routage
Routing Loop et du Counting to Infinity (du DBF) [17].
2.7.2. Le protocole AODV
LAODV (Ad hoc On Demand Distance Vector) [17, 8] ou bien le routage avec
vecteur de distance la demande adopte en ralit deux politiques prsentes comme
optimisation du protocole DSDV. Le protocole AODV minimise sensiblement le
nombre de diffusions de messages en crant le chemin la demande en plus du routagenud nud et le principe des numros de squence. AODV utilise aussi lchange
Nud mobile
Lien de
communication
8/3/2019 Chapitre 2 rseaux ad hoc
12/16
LES RESEAUX AD HOC &CHAPITRE 2 LES PROTOCOLES DE ROUTAGE
26
priodique dune part, dautre part, il a hrit des deux mcanismes qui caractrisent le
DSR et qui sont : la dcouverte et la maintenance des routes
Comme dans le DSDV, lAODV utilise le principe des numros de squence, il
permet aux nuds dutiliser les routes les plus fraches suivant leurs numros desquence.
Le concept du paquet Route Requestet aussi bien utilis dans lAODV. En
effet dans une table de routage propre lAODV, les chemins sont maintenus dune
manire distribue au niveau de chaque nud.
Une entre de la table de routage contient essentiellement [31] :
1) L'adresse de la destination.2) Adresse du nud suivant.
3) La distance en nombre de sauts (i.e. le nombre de nuds ncessaires pour atteindrela destination).
4) Le numro de squence destination.
5) Le temps d'expiration de chaque entre dans la table.
Prcisons que le protocole AODV ne supporte que les liens symtriques dans la
construction des chemins inverses; c'est--dire que lorsquun nud intermdiaire
transmet le paquet Route Request un voisin, il procde la sauvegarde de
l'identificateur du nud partir duquel la premire copie de la requte est reue. Ce
chemin inverse sera travers par le paquetRoute Reply, et de cette faon tous les nuds
appartenant au chemin retour modifieront leurs tables de routage en fonction du paquet
rponse de route.
Dans le cas o les routes ne sont par dtermins lavance, ou bien la dure de
vie du chemin vers la destination expire ou encore une dfaillance surgit pour un
chemin donn, le nud diffuse un paquetRoute Request(RREQ) (figure 2.8). Le champNS destination de ce dernier nous indiquera le dernier numro de squence associ au
nud destination. En effet si le NS nest pas connu, la valeur zro lui sera attribue par
dfaut. Si aprs un certain temps le nud metteur ne reoit pas le paquet Route Reply(RREP), le nud source rediffuse une nouvelle fois le RREQ. Ainsi, et chaque fois
que RREQ est rediffus, le champ Broadcast ID [31] du paquet RREQ est
incrment. Un message derreur est dlivr si au bout dun certain nombre derediffusions duRREQ, leRREPnest pas rceptionn.
8/3/2019 Chapitre 2 rseaux ad hoc
13/16
LES RESEAUX AD HOC &CHAPITRE 2 LES PROTOCOLES DE ROUTAGE
27
Figure 2.8 :Les deux requtes RREQ et RREP utilises dans le protocoleAODV.
Comme nous lavons dj dit, le protocole AODV excute lui aussi une
procdure de maintenance des routes, cette procdure se fait par lmission priodique
dun message "HELLO". Le lien entre deux nuds voisins sera considr commedfaillant dans le cas o trois messages "HELLO" ne sont pas reus respectivement.
Les dfaillances des liens sont gnralement dues la mobilit du rseau ad
hoc. Les mouvements des nuds qui ne participent pas dans le chemin actif naffectent
pas la consistance des donnes de routage. Quand un lien, reliant un nud p avec le
nud qui le suit sur le chemin de routage, devient dfaillant, le nud p diffuse unpaquet UNSOLICITED RREP avec une valeur de numro de squence gale
l'ancienne valeur du paquet RREP incrmente de un, et une valeur infinie de ladistance. Le paquet UNSOLICITED RREPest diffus aux voisins actifs jusqu' ce qu'ilarrive la source. Une fois le paquet est reu, la source peut initier le processus de la
dcouverte de routes.
L'AODV maintient les adresses des voisins travers lesquels les paquets
destins un certain nud arrivent. Un voisin est considr actif, pour une destination
donne, s'il dlivre au moins un paquet de donne sans dpasser une certaine priode
(appele : active time out period). Une entre de la table du routage est active, si elle est
utilise par un voisin actif. Le chemin reliant la source et la destination, en passant par
les entres actives des tables de routage, est dit un chemin actif. Dans le cas des
dfaillances des liens, toutes les entres des tables de routage participantes dans lechemin actif, et qui sont concernes par la dfaillance, sont supprimes. Cela est
accomplit par la diffusion d'un message d'erreur entre les nuds actifs.
Le protocole de routage AODV (et mme le protocole DSR), n'assure pas
l'utilisation du meilleur chemin existant entre la source et la destination. Cependant, des
valuations de performances rcentes ont montr qu'il n'y a pas de grandes diffrences
(en terme doptimisation) entre les chemins utiliss par le protocole AODV et ceux
utiliss par les protocoles bass sur les algorithmes de recherche des plus courts
chemins [10].
8/3/2019 Chapitre 2 rseaux ad hoc
14/16
LES RESEAUX AD HOC &CHAPITRE 2 LES PROTOCOLES DE ROUTAGE
28
En plus de cela, le protocole AODV ne prsente pas de boucle de routage, et
vite le problme "Counting to Infinity" de Bellman-Ford [17], ce qui offre une
convergence rapide quand la topologie du rseau ad hoc change.
2.7.3. Le protocole ZRP
Le protocole de routage ZRP ( Zone Routing Protocol) utilise les deux
approches (Proactif et Ractif), il limite la procdure proactive uniquement aux nudsvoisins (les changements de la topologie doivent avoir un impact local) et, bien que denature global, offre une recherche rapide et efficace dans le rseau. Contrairement une
recherche sur tout le rseau [13], dans ce protocole, la dtection des boucles de routage
est possible grce la connaissance de la topologie du rseau.
Une Zone de routage est alors dfinie pour chaque nud, elle inclut les nuds
qui sont une distance minimale (en terme de nombre de sauts), du nud en question,infrieure ou gale au rayon de la zone [13]. Lexemple ci-dessous illustre la zoneassocie au nud A avec un rayon gal 2 sauts.
Figure 2.9 : la zone de routageA avec =2.
Dans lexemple de la figure 2.9, les nuds B, D, H, et F appartiennent la
zone de routage de A, ils sont considrs comme nuds internes (la distance qui lessparent du nudA est strictement infrieure au rayon ). Les nuds C, E, I, et Gqui
sont distant du nud A dune distance gale au rayon (=2) sont dit nuds
priphriques. Pour ce qui est des nuds J et K, ils ne sont pas inclus dans la zone de A.
En rsum, ZRP dfinit donc deux types de protocoles : lun fonctionnant
localement et le deuxime fonctionnant entre zones. Ces deux protocoles sont :
IARP [14] ( IntrAzone Routing Protocol) offrant les routes optimales vers lesdestinations qui se trouvent lintrieur de la zone une distance dtermine, et
tout changement est rpercut uniquement lintrieur de la zone .
Zone de routage
proactif
Nud priphrique
8/3/2019 Chapitre 2 rseaux ad hoc
15/16
LES RESEAUX AD HOC &CHAPITRE 2 LES PROTOCOLES DE ROUTAGE
29
IERP [15] ( IntErzone Routing Protocol) quant lui soccupe de rechercher les
routes la demande pour des destinations en dehors dune zone.
En plus de ces deux protocoles, le ZRP utilise le protocole BRP (Bordercast
routing protocol) [16]. Ce dernier utilise les donnes de la topologie fournies par leprotocole IARP afin de construire sa liste des nuds de priphrie et la faon de les
atteindre. Il est utilis pour guider la propagation des requtes de recherche de route de
lIERP dans le rseau.
La recherche des chemins est effectue en vrifiant tout dabord si le nud
destinataire ne se trouve pas dans la zone du nud source (la procdure IERP suppose
que chaque nud connat le contenu de sa zone), auquel cas, le chemin est dj connu.
Autrement, une demande dtablissement de route RREQ est initie vers
tous les nuds priphriques, ces derniers vrifient, leur tour, si la destination
spcifie par la source existe dans leurs zones. Dans le cas positif, la source recevraalors un paquet RREP contenant le chemin menant la destination, sinon, les nuds
priphriques diffusent la requte de demande leurs propres nuds priphriques, qui
leurs tours, effectuent le mme traitement.
Dans la Figure 2.10, le nud A veut envoyer un paquet au nud J, puisque ce
dernier nest pas dans la zone de routage de A, une requte RREQ est envoye par A
aux nuds priphriques qui sont C, E, I, et G. Ces derniers vrifient lexistence du
nud J dans sa zone de routage et, par consquent, lenvoie dun message RREP ,contenant le chemin tabli, du nud G.
Figure 2.10 :Demande de route A --- J (=2)
Les erreurs de route sont galement prvues par lIERP en utilisant un
mcanisme de rponse ractif. Lors dune propagation dun paquet, si une erreur
survient au niveau du prochain nud (le nud devient inaccessible), un message
RERR est dlivr la source.
Zone de routage
proactif
Nud priphrique
Destination
8/3/2019 Chapitre 2 rseaux ad hoc
16/16
LES RESEAUX AD HOC &CHAPITRE 2 LES PROTOCOLES DE ROUTAGE
30
En rsum, le ZRP combine plusieurs sous protocoles, savoir, IARP (
lintrieur de la zone), IERP ( lextrieur de la zone), et dautres ( ICMP et BRP
etc.).
2.8. Conclusion
Ltude effectue sur les rseaux mobiles ad hoc nous a permis de connatre
leurs diffrentes caractristiques (absence dinfrastructure, topologie dynamique, bandes
passantes limites, scurit physique limite, contraintes dnergie, etc.), et ainsi
constater que leur apparition a, certes, facilit la mise en uvre dapplications mobiles
et ne supportant pas dinfrastructure prexistante (telles que les applications militaires),
mais en revanche, a laiss merger un bon nombre de problmes dont celui du routage.
Dans ltude des protocoles de routage, on a commenc par prsenter les trois
classes de protocoles de routages : Proactifs, Ractifs et hybrides, ainsi que lespolitiques et les mthodes dacheminement sur lesquelles ils reposent. Par la suite on a
donn un exemple de protocole pour chacune des trois classes : DSDV, AODV, ZRP.
Dautres protocoles existent videmment, mais, dans le care de note travail, on se
contente de ce peu, car le plus important pour nous est de choisir un protocole de
routage unicast qui semble plus flexible, afin de ltendre pour une nouvelle application
qui est : la connexion des rseaux ad hoc Internet. Pour cela, le chapitre suivant vient
pour mettre en claire cette nouvelle technologie.