4.2 Algorithmes de géocasting sans garantie de
livraison. 4.2.1 Algorithme de KO-VAIDYA
Les auteurs en [43] ont proposés trois protocoles pour
la résolution du problème de geocas-ting : le static zone
scheme, l'adaptive zone scheme et l'adaptive distance scheme. La
définition de la forwarding zone est l'élément substantiel
qui diffèrent dans les trois solutions. Cette technique permet de
diminuer la surcharge, le taux de collisions par rapport au flooding simple en
ce sens que seul un sous-groupe de l'ensemble des noeuds exécute le
flooding.
Static Zone Scheme
La forwarding zone ici est rectangulaire. C'est le plus petit
rectangle comprenant la source et la région de geocast ou tout autre
polygone. La source peut donc déterminer les quatre points de la
forwarding zone et inclure leurs coordonnées dans le paquet geocast
à transmettre. Ainsi, Chaque paquet geocast contient une description de
cette zone qui statique durant tout le parcours du paquet de l'origine
jusqu'à la destination. Lorsqu'un noeud reçoit le paquet geocast,
il le supprime s'il ne se trouve pas dans la forwarding zone constituée
du rectangle. Le terme statique ici est justifié par le fait que la
forwarding zone spécifiée dans le paquet geocast par la source
n'est modifiée par aucun autre noeud. Ainsi, la forwarding zone reste
statique durant tout le processus de geocasting.
Adaptive zone scheme
Avec cette technique, la fowarding zone est redéfinie
à chaque noeud intermédiaire sur le parcours du paquet. Ce
protocole est identique au précédent en ce sens que lorsqu'un
noeud X
47
CHAPITRE 4. PROTOCOLES DE GEOCASTING DANS LES RÉSEAUX DE
CAPTEURS SANS FIL
reçoit le paquet geocast, il détermine si le
paquet doit être relayé ou non en se basant sur sa situation
géographique et la définition de la forwarding zone incluse dans
le paquet geocast reçu. Dans le schéma à zone statique,
lorsqu'un noeud X diffuse un paquet geocast, la définition de
la forwarding zone dans ce paquet ne sera pas modifié pendant le
processus de diffusion. Ce n'est pas le cas du schéma à zone
adaptée. En effet, la fowarding zone n'est plus statique tout au long du
parcours du paquet. Le protocole stipule que lorsqu'un noeud A envoie
un paquet geocast, il modifie la spécification de la forwarding zone. La
nouvelle forwarding zone est constituée du plus petit rectangle
contenant le noeud A et la région geocast tel que les
côtés du rectangle soient parallèles aux axes des abscisses
et des ordonnées dans un repère orthonormé. On note tout
de même en [43] que les performances de ce protocole peuvent se
dégrader drastiquement dans certains cas (Figure 4.1).
FIGURE 4.1: succès/Echec de livraison de
paquets lors de l'exécution du schéma à zone
adaptée
Adaptive distance scheme
Dans les deux variantes précédentes, la
forwarding zone est explicitement spécifiée dans le paquet
geocast. Dans le présent schéma, la source S inclut
trois informations dans le paquet geocast sans toutefois inclure explicitement
la forwarding zone : les spécifications de la région geocast, les
coordonnées du centre de la région et les coordonnées de
la source. Lorsqu'un noeud reçoit un paquet, il calcule la distance qui
le sépare du centre de la région de geocast et la compare
à celle de l'émetteur du message. Le résultat permet de
décider s'il faut détruire ou réémettre le
paquet
4.2.2 Les protocoles LBM,VDBG,GeoGRID et GeoTORA
Le LBM est un protocole basé sur le flooding, plus
précisément sur la fowarding zone. Une implémentation du
LBM peut exploiter n'importe quelle variante de la fowarding zone
sus-présentée. Le LBM réduis la zone de Fowarding et du
même coup diminue la charge réseau tout en maintenant une bonne
fiabilité par rapport au flooding simple. Le VDBG et le GeoGRID quant
à eux, ont pour but de réduire la charge du réseau tout en
augmentant la fiabilité du réseau par rapport au LBM. En effet,
la fowarding zone est désormais constituées des noeuds qui sont
proches de la région de destination (les régions de Voronoi qui
intersectent la région geocast).
48
CHAPITRE 4. PROTOCOLES DE GEOCASTING DANS LES RÉSEAUX DE
CAPTEURS SANS FIL
Ceci vient résoudre le problème des fowarding
zones qui n'ont pas de noeuds pouvant permettre l'acheminement des paquets vers
la zone de destination. Pour le GeoGrid, le réseau tout
entier est partitionné en grille. Ainsi, pour chaque grille contenue
dans la zone de fowarding est élu un noeud dit gateway responsable du
fowarding. La clé de cette technique est l'élection du gateway
qui a encore des zones d'ombre. Le GeoTORA et le Mesh-based Geocast
Protocol ont été introduits pour résoudre le
problème de redondance, de surcharge et de collisions multiples. Ils
permettent de créer en outre des routes entre la source et la
destination à la demande. Pour le transfert du paquet on évite
ainsi le flooding. Un avantage indéniable est la réduction
considérable de la surcharge du réseau lors de la transmission du
paquet. Le contre poids est la nécessité de plus de latence et
d'une éventuelle surcharge du réseau lors de la recherche des
routes.
4.3 Algorithme de géocasting avec garantie
de livraison
| 
