Bassagni propose en [24] un algorithme de clustering pour les
RCSFs en considérant comme paramètre de clustérisation le
poids relatif de chaque noeud. Compte tenu de la mobilité
récurrente des noeuds, le paramètre du poids de chaque noeud est
introduit pour choisir les noeuds chefs de clusters. A la fin de la
procédure de clustérisation, les trois propriétés
suivantes doivent être satisfaites : chaque noeud ordinaire a au moins un
CH comme voisin; chaque noeud ordinaire est associé au CH de plus grand
poids et deux CHs ne peuvent pas être voisins. Cet algorithme de
clustérisation est divisé en deux sous étapes :
l'étape d'initialisation des clusters et l'étape de maintenance
des clusters. Les auteurs supposent également que durant
l'exécution de l'algorithme, la topologie du réseau ne change
pas; et qu'un message envoyé par un noeud est bien reçu
après un temps fini (un seuil) par tous ses voisins; tout noeud
connaît son poids, son identifiant et les identifiants et poids de tous
ses voisins.
L'algorithme est exécuté par chaque noeud
individuellement de telle façon qu'un noeud u décide de
son propre rôle (clusterhead ou noeud ordinaire) en fonction seulement de
la décision de ses voisins avec des poids plus forts que lui. Donc,
initialement, seuls ces noeuds avec le poids le plus élevé du
voisinage vont diffuser un message à leurs voisins directs,
établissant qu'ils sont les clusterheads. Si aucun noeud avec un poids
plus fort n'a envoyé de tel message, alors u va envoyer un
message établissant son statut de clusterhead.
Choix du Cluster-Head (CH)
Le choix du CH est fonction du degré sortant de chaque
noeud. Dans le cas où plusieurs noeuds ont le même degré on
met en exergue le poids de chaque noeud. La procédure de choix du CH est
la suivante : les noeuds de plus grand degré initient la
procédure en envoyant des requêtes d'être CH à tous
leurs voisins. De là, tout noeud dont le degré est
supérieur à celui de ses voisins diffuse sa décision
d'être chef de cluster. Si un noeud connait un de ses voisins de
degré supérieur au sien, il ne peut plus être chef de
cluster. Il adopte ce noeud là comme chef de cluster.
16
CHAPITRE 2. LES PROTOCOLES DE CLUSTERING DANS LES RÉSEAUX
DE CAPTEURS SANS FIL
Choix des noeuds ordinaires
Cette étape est aussi basée sur la comparaison
des degrés des autres noeuds. En effet, pour un noeud vi dont
le degré est inférieur à celui de ses voisins, deux cas
possibles se présentent : Si ce noeud vi est voisin d'un noeud
CHi qui est chef de cluster, alors vi rejoint automatiquement
le cluster dont le chef est CHi. Si le voisin de vi de plus
haut degré appartient à un cluster, deux cas sont possibles : si
un chef de cluster CHi est parmi ses voisins, alors il devient membre
du cluster dont le chef est CHi ; sinon, il crée un nouveau
cluster.
L'algorithme utilise deux types de messages : ch(v)
utilisé par un noeud v pour mettre au courant ses voisins
qu'il sera clusterhead, et join(v, u), avec lequel v
communique à ses voisins qu'il va faire partie du cluster dont le
clusterhead est u. la description de cet algorithme est la
suivante:
Chaque noeud démarre l'exécution de
l'algorithme en même temps, en utilisant une même procédure
d'initialisation. Seuls les noeuds qui ont le poids le plus élevé
par rapport à tous leurs voisins directs vont envoyer un message du type
ch(noeuds avec les forts poids) pour dire qu'il veut être
clusterhead. Tous les autres noeuds se contentent d'attendre de recevoir un tel
message. A partir de là, on dispose de 2 procédures
spécifiques dont l'exécution est déclenchée par les
réceptions de message :
lors de la réception d'un message
ch venant d'un voisin u, le noeud
v vérifie d'abord s'il a déjà reçu de tous
ses voisins z , tels que w, > wu un message
join(z, x) de type ch avec x un noeud quelconque du
réseau. Dans le cas négatif, et si u est le noeud de
plus fort poids dans le voisinage de v ayant envoyé un message
ch, alors v rejoint u, et quitte l'exécution
de l'algorithme;
lors de la Réception d'un message
JOIN(u, t) : Le noeud v vérifie s'il a
précédemment envoyé un message ch. Si c'est bien
le cas, v vérifie si le noeud u veut rejoindre son
propre cluster et actualise, si besoin, son ensemble cluster(v).
Lorsque tous les voisins z de v tel que w, <
wu ont déjà témoigné leur
volonté à rejoindre son cluster, v quitte
l'exécution de l'algorithme. Un noeud v qui a dans sa liste de
voisins des noeuds de poids supérieurs au sien et qui n'a pas
reçu des messages de type CH(u) attend de recevoir de tous ces
voisins x de poids supérieur au sien des message de type
JOIN(x, t), pour dire en fait que ses voisins ont rejoint un ou
plusieurs CH de poids supérieur aux leurs. Dans ce cas le noeud v
décide alors de devenir CH en diffusant alors le message CH(v).
Illustrons le fonctionnement de l'algorithme DCA de Basagni avec le graphe
représenté par la figure 2.2
Cet algorithme convient pour des réseaux "
quasi-statiques ". En ce qui concerne la maintenance, l'auteur propose d'abord
une succession de clusterisations afin que DCA s'adapte à la
mobilité des noeuds. Par la suite, il propose une autre version du DCA
qu'il baptise DMAC plus adapté pour les réseaux où les
capteurs sont mobiles. La métrique de sélection des CHs est cette
fois ciliée à la mobilité des capteurs. DMAC géra
tant l'initialisation que la maintenance de l'organisation des clusters
malgré la mobilité des noeuds. La maintenance quant à elle
se fait
17
CHAPITRE 2. LES PROTOCOLES DE CLUSTERING DANS LES RÉSEAUX
DE CAPTEURS SANS FIL
à présent par actions réduites [24].
désormais on n'a plus besoin de supposer que la topologie du
réseau est statique durant la construction des clusters. L'adaptation
aux changements de la topologie du réseau est rendue possible en
laissant chaque noeud réagir non seulement à la réception
d'un message venant d'autres noeuds, mais également à la
défaillance d'un lien de communication vers un autre noeud
Afin d'économiser en énergie et limiter
l'impact de la mobilité, l'auteur introduit l'algorithme GDMAC. Son
propos est le suivant : conformément aux spécifications de
l'algorithme DMAC, un noeud ordinaire va toujours se soumettre avec le
clusterhead de son voisinage qui a le plus fort poids. Si plus tard, un autre
clusterhead avec un poids plus élevé apparaît dans son
voisinage, le noeud ordinaire va changer son affiliation afin de se soumettre
toujours au noeud, a priori, le plus capable d'être un bon clusterhead.
Une autre forme de réaffiliation apparaît quand deux CHs, à
cause de leur mobilité, se retrouvent dans la portée d'influence
l'un de l'autre. A ce moment-là, seul le plus lourd des deux va
conserver son statut de clusterhead, tandis que l'autre va devenir noeud
ordinaire et se chercher un clusterhead convenable. Si aucun n'est à
portée de transmission, le noeud va redevenir son propre clusterhead
(élection).
Nous pouvons remarquer que ce schéma de clustering
présente plusieurs points faibles. En effet, l'algorithme de Basagni ne
prend pas en compte la sécurité du processus de formation de
clusters. Outre, à la fin de cet algorithme, un noeud quelconque peut
appartenir à plusieurs clusters. De plus, la constitution des noeuds est
dépendante d'un noeud précis (le clusterhead)et on peut avoir
à la fin, des clusters non disjoints. Ceci nous amènent à
des interrogations telles que : Que se passerait-il si ce clusterhead avait
menti sur ces métriques ou était en effet un noeud malicieux? le
protocole suivant vient pallier à ces insuffisances.
