II.2.3.2 Le protocole de routage CBRP
Dans le "Protocole de Routage Basé sur les Groupes"
appelé CBRP (Cluster Based Routing Protocol), l'ensemble des noeuds du
réseau est décomposé en groupes [Jia99]. Le principe de
formation des groupes est le suivant : Un noeud p qui n'a pas de
statut (i.e. qui n'est ni membre ni représentant de groupe), active un
timer et diffuse un message "Hello". Lorsqu'un
représentant de groupe reçoit le message "Hello", il
envoie immédiatement une réponse à l'émetteur. Lors
de la réception de réponse, le noeud p change son
état "indécis" à l'état "membre". Sip
dépasse un certain timeout en attendant la réponse et
dans le cas où il possède un lien bidirectionnel vers au moins un
noeud voisin, il considère lui-même un représentant de
groupe. Dans le cas contraire, p reste dans l'état
indécis et il répète la même procédure. A
cause des changements rapides de la topologie des
réseaux ad hoc, l'attente des n°uds indécis est très
courte.
Afin de sauvegarder la répartition des noeuds dans les
groupes, chaque noeud maintient une table des voisins. Chaque entrée de
cette table est associée à un voisin, elle indique l'état
du lien (uni ou bidirectionnel), et le statut du voisin (membre ou
représentant de groupe). Un représentant de groupe, maintient les
informations des membres qui appartiennent à son groupe. Il
possède aussi une table des groupes adjacents. Une entrée dans
cette table est associée à un groupe voisin, elle contient :
l'identificateur du groupe, et l'identificateur du noeud de liaison à
travers lequel le groupe peut être atteint (voir la figure suivante).
La table des groupes adj acents
Groupe Nd liaison Nd
représentant
La table des voisins
Voisin Statut Etat
de lien
1 3
Les membres du groupe
5
6
7
8
5 2
membre représent
5 8
uni d bi d.
1 3
6
Groupe2
7
2
5
8
1
3
4
Groupe3
9
Groupe1
Figure 2.8: L'organisation du réseau dans le CBRP.
Le
routage dans le protocole CBRP se fait de la manière suivante : quand un
noeud source
veut envoyer des données à un noeud destination,
il diffuse par inondation une requête de
demande de chemin, et cela
uniquement aux représentants des groupes voisins.
Un
représentant de groupe qui reçoit la requête de
demande, vérifie en utilisant sa table de
membres de groupes,
l'existence du noeud destination dans son groupe. Si la destination
existe,
le représentant y envoie directement la requête, dans le cas
contraire, la requête est
diffusée aux représentants des
groupes voisins. L'adresse des représentants des groupes est
incluse
dans la requête de demande de chemin, un représentant de groupe
ignore toute requête
déjà traitée. Quand la
destination reçoit le paquet contenant la requête, elle
répond par l'envoi
du chemin qui a été
sauvegardé dans le paquet de la requête. Dans le cas où le
noeud source
ne reçoit pas de réponse en expirant une certaine
période, il envoie de nouveau une requête de demande de chemin.
Lors de l'acheminement des données, si un noeud
détecte qu'un lien est défaillant, il fait retourner un message
d'erreur à la source et il applique un mécanisme de
réparation locale. Dans ce mécanisme, si un noeud p
trouve qu'un noeud suivant n, ne peut pas être atteint, il
essaie de vérifier si le noeud n ou le noeud qui vient
après n, peuvent être atteints à travers un autre
noeud voisin. Si l'un des deux cas est vérifié, les
données sont envoyées en utilisant le chemin
réparé.
| 
