3.5 CLASSIFICATION DES PROTOCOLES DE ROUTAGE
Vue la difficulté de routage dans les réseaux ad
hoc, les stratégies existantes utilisent une variété de
techniques afin de résoudre ce problème. Suivant ces techniques,
plusieurs classifications sont apparues, parmi lesquelles nous allons citer
:
3.5.1 Routage hiérarchique ou plat :
Le premier critère utilisé pour classifier les
protocoles de routage dans les réseaux ad hoc concerne le type de vision
qu'ils ont du réseau et les rôles qu'ils accordent aux
différents mobiles.
Les protocoles de routage à plat :
considèrent que tous les noeuds sont égaux (FIG 3.1). La
décision d'un noeud de router des paquets pour un autre dépendra
de sa position. Parmi les protocoles utilisant cette technique, on cite
l'AODV ( Ad hoc On Demand Distance Vector)9.
N2
N7
N12
N9
N1
N3
N6
N4
N11
N5
N8
FIG 3.1 Routage à plat
Les protocoles de routage hiérarchique :
fonctionnent en confiant aux mobiles des rôles qui varient de
l'un à l'autre. Certains noeuds sont élus et assument des
fonctions particulières qui conduisent à une vision en plusieurs
niveaux de la topologie du réseau. Par exemple, un mobile pourra servir
de passerelle pour un certain nombre de noeuds qui se seront attachés
à lui. Le routage en sera simplifié, puisqu'il se fera de
passerelle à passerelle, jusqu'à celle directement
attachée au destinataire. Un exemple est donné sur la figure (FIG
3.2), où le noeud N3 passe par les passerelles P1, P2 et P3 pour
atteindre N7. Dans ce type de protocole, les passerelles supportent la majeure
partie de la charge du routage (les mobiles qui s'y rattachent savent que si le
destinataire n'est pas dans leur voisinage direct, il suffit d'envoyer à
la passerelle qui se débrouillera). Un exemple de protocole utilisant
cette stratégie est l'OLSR (Optimized Link State Routing)
9 M. Dawoud. Analyse du protocole AODV.
Université Paul sabatier, 2006.
FIG 3.2 Routage Hiérarchique
3.5.2 Le routage à la source et le routage saut par
saut :
Le routage à la source : le routage
à la source ou << source routing >> consiste à
indiquer dans le paquet routé l'intégralité du chemin que
devra suivre le paquet pour atteindre sa destination. L'entête de paquet
va donc contenir la liste des différents noeuds relayeur vers la
destination. Le protocole le plus connu basant sur cette classe est :
DSR10.
Le routage saut par saut : le routage saut
par saut ou <<hop by hop>> consiste à donner uniquement
à un paquet l'adresse du prochain noeud vers la destination. AODV fait
partie des protocoles qui utilisent cette technique.
3.5.3 Etat de lien et Vecteur de distance :
Autres classifications, hérité du monde filaire,
est possible pour les protocoles de routage : les protocoles basés sur
l'état des liens et sur le vecteur de distance. Les deux méthodes
exigent une mise à jour périodique des données de routage
qui doivent être diffusées par les différents noeuds de
routage du réseau. Les algorithmes de routage basés sur ces deux
méthodes, utilisent la même technique qui est la technique des
plus courts chemins, et permettent à un hôte donné, de
trouver le prochain hôte pour atteindre la destination en utilisant le
trajet le plus court existant dans le réseau.
Les protocoles basés sur l'état de lien
: La famille des protocoles à état de liens se base sur
les informations rassemblées sur l'état des liens dans le
réseau. Ces informations sont disséminées dans le
réseau périodiquement ce qui permet ainsi aux noeuds de
construire une carte complète du réseau. Un noeud qui
reçoit les informations concernant l'état des liens, met à
jour sa vision de la topologie du réseau et applique un algorithme de
calcul des chemins optimaux afin de choisir
10 Dynamic Source Routing
le noeud suivant pour une destination donnée. En
générale ces algorithmes se basent sur le principe de
l'algorithme de Djikstra pour calculer les chemins les plus courts entre un
noeud source et les autres noeuds du réseau. . Les principaux protocoles
de routage dans les réseaux ad hoc qui appartiennent à cette
classe sont les suivants : TORA11 , OLSR et
TBRPF12.
Les protocoles basés sur le vecteur de distance
: Les protocoles à vecteur de distance se basent sur un
échange, entre voisins, des informations de distances des destinations
connues. Chaque noeud envoie à ses voisins la liste des destinations qui
lui sont accessibles et le coût correspondant. Le noeud récepteur
met à jour sa liste locale des destinations avec les coûts
minimums. Le processus de calcul se répète, s'il y a un
changement de la distance minimale séparant deux noeuds, et cela
jusqu'à ce que le réseau atteigne un état stable. Les
calculs des routes se basé sur le principe de l'algorithme
distribué de Bellman-Ford (DBF). Les protocoles de routage basés
sur le vecteur de distance les plus connus pour les réseaux ad hoc sont
: DSR, DSDV13 et AODV.
| 
