4.3.2 Algorithme de Bomgni et al.
Bomgni et al. propose en [48] un algorithme de géocast
et de multigeocast économe en énergie avec garantit de livraison
et avec une surcharge du réseau moindre que celle des protocoles
présentés plus haut. Son algorithme est une amélioration
de ceux présentés plus haut, et se déroule en 05 phases
:
Phase 1 : Identification des noeuds et Découverte
des voisins
Identification des noeuds : Soit n le
nombre de capteurs dans le réseau. Chaque capteur
-1
O(
)
n
tel
peut avoir un identifiant compris entre 1 et n3
avec une probabilité supérieure à e
que deux capteurs quelconques n'aient pas le même
identifiant. La preuve de ce théorème a été
démontrée dans [48].
Découverte des voisins : Une fois les
identifiants attribués, à chaque noeud doit découvrir son
voisinage à un saut. Quelque soit le noeud u du réseau,
le protocole de découverte ci-dessous(figure 4.2) lui permet de
connaitre ses voisins directs. N désigne la borne maximale du
degré de tous les noeuds et du le degré du noeud
quelconque u (notons que N < n).
CHAPITRE 4. PROTOCOLES DE GEOCASTING DANS LES RÉSEAUX DE
CAPTEURS SANS FIL
Phase 2 : partitionnement du réseau en
clique
Les capteurs exécutent le protocole de sun et al. [25]
pour former des cliques. On suppose que cette phase génère k
cliques et donc k CHs. On note CHcliquei le
clusterhead de la clique i. On rappelle qu'après cette
procédure tous les noeuds dans une même clique sont à un
saut l'un de l'autre. Ce qui permettra d'avoir un gain en énergie
énorme lors des transmissions comparées aux transmissions dans un
environnement partitionné où les noeuds d'un même cluster
peuvent être à plusieurs sauts les uns des autres.
Phase 3 : Partitionnement hiérarchique
On se focalise uniquement sur les CHs
générés à la phase 2. Considérons le
réseau G' engendré par ces k CHs. Il est clair
que G' = k. Partitionnons ce réseau en
utilisant la technique de partitionnement hiérarchique de Banerjee et
al. [27] présentée au chapitre précédent tel que
k
chaque cluster résultant de cette phase de partitionnement
ait au moins 2 capteurs et au plus
k capteurs. Il est facile de remarquer que ce
partitionnement engendrera un seul cluster et donc un seul clusterhead (le
super clusterhead). Ce dernier connait les identifiants de tous les
résidents du cluster dont il est le coordonnateur i.e les
identifiants des k - 1 capteurs.
Phase 4 : Phase de requête
Lorsque la source souhaite envoyer un paquet à tous les
noeuds situés dans une région géo-cast, elle diffuse dans
l'ensemble dominant un petit paquet constitué du message et de la
spécification de la région géocast comme suit
(REQUEST(Message, CoordonnéesRégionGéocast)).
Tout paquet de ce type est tout d'abord envoyé au superclusterhead qui
est la seule entité à pouvoir prendre une décision par
rapport au paquet. Ainsi, le paquet partira d'un clusterhead de niveau 1
jusqu'au superclusterhead.
Après avoir reçu le paquet, ce dernier va
envoyer un message de recherche contenant la définition de la
région géocast
(SEARCH(CoordonnéesRégionGéocast, f3)) à
tous les cluste-rheads des niveaux inférieurs pour savoir si ces
derniers ont des noeuds situés dans la région de geocast
spécifiée dans le paquet. Ce message est accompagné d'une
variable booléenne 3.
50
FIGURE 4.2: Protocole de découverte de
voisins
51
CHAPITRE 4. PROTOCOLES DE GEOCASTING DANS LES RÉSEAUX DE
CAPTEURS SANS FIL
Chaque clusterhead de premier niveau envoie le paquet de
recherche à tous les noeuds membres de son cluster. Ceux-ci
déterminent si oui ou non ils sont situés dans la région
geocast. Si c'est le cas, ils mettent la variable binaire 3 à 1
et renvoient la réponse avec leur identifiant à leur clusterhead.
Dans le cas contraire, aucune action n'est menée, cela signifie que ces
derniers ne sont pas dans la région geocast. Ces clusterheads
enregistrent la provenance des réponses positives.
Les clusterheads ayant reçu au moins une réponse
positive à leurs tours acheminent au superclusterhead un petit paquet
(SEARCH(CoordonnéesRégionGéocast, 3 = 1)) avec
3 mis à 1.
Phase 5 : Phase de diffusion
Après avoir reçu les réponses des
clusterheads de niveaux inférieurs, le superclusterhead renvoie un
paquet (REQUEST(Message, 3 = 1)) uniquement à ceux de ces
clusterheads qui ont répondu positivement au message de recherche. Le
message passera donc par tous les clusterheads qui ont enregistré 3
à 1 et parviendra finalement à tous les noeuds ayant mis
3 à 1 lors de la phase de recherche. les auteurs dans [48]
prouvent par la suite que cet algorithme garantit la livraison des paquets
à tous les noeuds situés dans la région géocast et
est économe en énergie. Une évaluation de la consommation
d'énergie y est également faite.
| 
