4.3.1 Algorithme de Seada et Helmy
Seada et al. en [44] présente 2 algorithmes : le
premier algorithme GFG (Geographic-Forwarding-Geocast) possède une
surcharge du réseau minimale et est idéal pour les réseaux
denses. Le second GFPG (Geographic-Forwarding Perimeter-Geocast) garantit la
livraison des paquets à tous les noeuds de la région geocast
lorsque le réseau est connecté et même si la densité
n'est pas grande ou la distribution des noeuds est irrégulière
avec des obstacles.
GFG (Geographic-Forwarding-Geocast)
Geographic-Forwarding-Geocast [45] commence comme un unicast
géométrique jusqu'à ce qu'il atteigne la région
geocast. Une fois à l'intérieur de la région, le message
est inondé. Les messages inondés qui atteignent des noeuds
extérieurs à la région geocast sont jetés. En
outre, comme l'a noté Casteigts et al. [46], le
Geographic-Forwarding-Geocast peut échouer lors de la délivrance
du message à tous les noeuds dans la région geocast si la
région est déconnectée et la seule connectivité est
à travers des noeuds externes. Dans les applications geocast, les noeuds
se doivent de pouvoir calculer ou de connaitre leurs coordonnées
géographiques. Le protocole GFG utilise donc cette information
géographique cruciale pour diffuser efficacement les paquets vers la
région geocast. Ce protocole combine le greedy
forwarding(routage qui consiste à envoyer un paquet uniquement aux
noeuds qui sont proches de la destination) et le face routing(routage
qui consiste à router les paquets autour des points de terminaison
jusqu'à trouver des noeuds proches de la destination); mais le face
routing n'est utilisé ici que si c'est nécessaire (i.e en
utilisant la greedy forwarding, on arrive à une situation où un
noeud ayant reçu le paquet n'arrive pas à trouver un noeud proche
de la destination). Dès que le paquet parvient aux noeuds à
l'intérieur de la région geocast, ceux-ci le diffusent à
tous leurs voisins et ainsi de
49
CHAPITRE 4. PROTOCOLES DE GEOCASTING DANS LES RÉSEAUX DE
CAPTEURS SANS FIL
suite. Le « Virtual Surrounding Face »
[47] évite ce problème en pré-calculant à l'avance
toutes les faces planes qui interceptent la région geocast.
GFPG
(Geographic-Forwarding-Perimeter-Geocast)
Cet algorithme utilise un savant dosage de routage
géographique et de face routing pour assurer la livraison des paquets
aux noeuds situés dans la région geocast lorsque le réseau
est connecté et en dépit des obstacles qui peuvent survenir
pendant ou après le déploiement. Initialement comme avec le GFG,
les noeuds qui sont à l'extérieur de la région se servent
de la greedy forwarding pour envoyer le paquet vers la région. Lorsque
le paquet finit par rentrer dans la région, les noeuds l'ayant
reçu démarrent le processus d'inondation de la région en
envoyant le paquet à tous leurs voisins. Tous les noeuds de la
région en font de même et en plus les noeuds en bordures de la
région initient un paquet de périmètre en direction de ses
voisins (ceux étant à l'extérieur de la région). En
effet, un noeud est dit noeud en bordure s'il possède un voisin à
l'extérieur de la région. Notons que les paquets de
périmètre sont envoyés uniquement aux voisins dans le
graphe planaire (et non à tous les noeuds). Recevant le paquet, le noeud
à l'extérieur de la région le diffuse à son voisin
dans le graphe planaire en utilisant la règle de la main droite, et
celui-ci fait de même, ainsi de suite. Le paquet sera ainsi relayé
le long de cette face et rentrera à nouveau dans la région. Le
premier noeud à recevoir le paquet dans la région va
démarrer le processus d'inondation si c'est la première fois
qu'il reçoit le paquet sinon il le détruit.
| 
