Conclusion:
Nous avons présentés dans ce chapitre les
technologies sur laquelle se base les réseaux VANet, les
différents modes de routage de l'information et quelques applications de
ces réseaux. Dans le chapitre suivant nous traiterons le protocole GPSR
dans le cadre du routage C et ses différentes fonctionnalités.
Chapitre 2: Le protocole GPSR
Introduction:
Dans les réseaux de mobiles s'interconnectant sans
hiérarchie tels que les réseaux ad hoc, la topologie a un
caractère relativement éphémère dû à
la mobilité des noeuds. Pour cette raison, les protocoles de routage les
plus étudiés pour ce type de réseaux sont les protocoles
de routage géographiques car ils permettent d'éviter la surcharge
d'informations échangées entre les noeuds qui chercheraient
à obtenir la topologie du réseau ou des tables de routage.
Ces protocoles de routage géographique se basent sur le
fait que tous les noeuds connaissent leur position, par exemple, grâce
à un équipement GPS (Global Positioning System) ou encore par un
système de positionnement distribué.
1. Motivation:
Il existe plusieurs protocoles qui définissent
différentes manières d'obtenir la position d'un noeud : ce
sont les protocoles de localisation. Parmi les principaux, on peut citer SLURP,
SLALOM, HGRID, GLS. Une fois la position obtenue, il reste à acheminer
le message. Pour ce faire, plusieurs protocoles de routage géographique
sont à l'étude : GEAR, DREAM, GPSR.
Nous avons choisi de nous baser sur GPSR. Ce dernier est un
protocole de routage géographique qui garantit un passage à
l'échelle car seules les informations locales sont stockées et
utilisées.
Lorsque GPSR se trouve face à une zone de vide, il
passe du mode greedy au mode perimeter. Ce faisant, il va
choisir le prochain saut par rapport à la règle de la main
droite . Ce choix a un caractère arbitraire et ne tient pas compte
de la possibilité qu'il y ait plus d'opportunités d'acheminement
d'un côté ou d'un autre.
2. Principe:
GPSR (Greedy Perimeter
Stateless Routing) est un protocole de
routage réactif et efficace qui a été conçu et
adapté pour les réseaux ad hoc mobiles et les réseaux de
capteurs. Son modèle de fonctionnement suppose que tous les noeuds se
trouvent au niveau d'un même plan. Du fait de la mobilité des
noeuds, certains algorithmes de routage qui se basent sur la topologie du
réseau, ou lance une phase de découverte de routes pour acheminer
des données ne sont pas adaptés à GPSR. De ce fait, il
utilise la position géographique des noeuds pour l'acheminement des
paquets de données ou de contrôle.
Dans un réseau mobile, les noeuds sont susceptibles de
se déplacer. Il faut ainsi un mécanisme permettant à
chaque noeud se savoir la position de ses voisins. Afin de signaler leur
présence et leur localisation, les noeuds inondent le réseau en
envoyant un paquet de signalement (messages « beacon») contenant
la position et un identifiant (par exemple, son adresse IP). Nous proposons
d'utiliser les messages « beacon » de contrôle pour
renseigner les noeuds voisins sur les directions que peuvent assumer un
noeud.
L'échange périodique de ces paquets de
contrôle permet aux noeuds de construire leur table de position. La
période d'émission des messages « beacon »
dépend du taux de mobilité dans le réseau ainsi que de la
portée radio des noeuds. En effet, lorsqu'un noeud ne reçoit pas
de message « beacon » d'un voisin après un temps T,
il considère que le voisin en question n'est plus dans sa zone de
couverture et l'efface de sa table de position. Il faut donc adapter le temps
d'émission des paquets de contrôle. Un des avantages du BP
(Beaconing Protocol) est que chaque noeud n'a besoin que des informations sur
ses voisins directs, ce qui nécessite peu de mémoire.
Alternativement, le protocole GPSR permet au noeud
d'encapsuler sur quelques bits leur position dans les paquets de données
qu'il envoie. Dans ce cas, toutes les interfaces des noeuds doivent être
en mode promiscuité afin de recevoir les paquets s'ils se trouvent dans
la zone de couverture de l'émetteur.
L'acheminement des paquets par GPSR se fait selon deux modes
suivant la densité du réseau : le « Greedy
Forwarding » et le « Perimeter Forwarding »
(appelés respectivement GF et PF dans la suite).
2.1. Greedy Forwarding:
Le GF construit un chemin parcourant les noeuds de la source
à la destination où chaque noeud qui reçoit un paquet
l'achemine en faisant un saut vers le noeud intermédiaire le plus proche
de la destination dans sa zone de couverture. La figure 2.1 montre un exemple
de ce mode d'acheminement.
Figure 2.1 : y est le voisin
de x le plus proche de la destination D
Cet algorithme d'acheminement offre un taux de réussite
assez proche des réseaux filaires dans le cas où la
mobilité de la destination n'est très forte. Lorsqu'un paquet de
données atteint une région où le GF échoue, alors
le PF est utilisé.
Figure 2.2. : X est plus
proche de d que ses voisins y, w
2.2. Perimeter Forwarding:
Cet algorithme utilise la règle de la main droite qui
est définie comme suit : Lorsqu'un paquet arrive à un noeud
x du noeud y, le chemin à suivre est le prochain qui se trouve dans le
sens inverse des aiguilles d'une montre en partant de x et par rapport au
segment [xy] tout en évitant les « crossing links »
(route déjà parcourue). La figure 2.3 montre un exemple plus
précis de ce mode.
Figure 2.3 : Passage au mode
PR
2.3. Gabriel Graph:
Pour augmenter le taux de réussite d'acheminement des
paquets, GPSR utilise les deux algorithmes en fonction de la densité
locale du réseau. Chaque noeud construit un graphe du réseau lui
permettant de diminuer les possibilités de routage. Ce graphe, le
Gabriel Graph (GG) permet de représenter le réseau avec moins de
noeuds pour éviter les « crossing links ». Le GG est
un ensemble de noeuds {Wi, Wi+1, ...Wi+n} tel qu'il existe aucun noeud dans la
portion de disque de rayon d(Wi, Wi+1) à portée des deux noeuds
concernés, avec Wi+1 étant noeud le plus éloigné
dans la zone de couverture de Wi.
Figure 2.4 : Pour que {u,v}
° GG, il faut qu'il n'existe aucun noeud dans le disque.
Ces éliminations n'introduisent pas de déconnexions
dans le cas de réseaux uniformes.
3. Exemple de scénario:
Ce protocole détermine la route à suivre en
minimisant les distances entre les noeuds et la destination (c'est le mode
Greedy Forwarding), mais un second mécanisme est mis en oeuvre en cas de
blocage (c'est le mode Perimeter). Dans ce cas, le noeud n'ayant pas de voisin
plus proche (en distance) que lui de la destination passe le relais à
ses voisins qui eux peuvent avoir un voisin plus proche de la destination (en
distance). Sur la Figure 2.5, le noeud B utilise le mode
Perimeter car il n'a pas de voisin plus proche en distance de la destination
finale G, ce qui permet de trouver une route passant par le noeud C qui, lui,
peut à nouveau utiliser le mode Greedy Forwarding ayant un voisin plus
proche de G (en l'occurrence D).
Figure 2.5 : Exemple de scénario:
Conclusion:
Tout au long de ce
chapitre, nous avons vu le fonctionnement général du protocole
GPSR. Nous avons aussi détaillé les composantes principales du
protocole. Nous allons voir dans le chapitre suivant le principe de simulation,
les différents simulateurs disponibles et le simulateur choisi.
Chapitre 3:
Simulateur
| 
