2.4.2 Partitionnement pour un contrôle
hiérarchique : Algorithme de Banerjee et al.
Dans cette section, nous présentons l'algorithme de
Banerjee et al.[27] qui permet de construire des clusters hiérarchiques.
A la fin de l'algorithme, les différents clusters formés doivent
respecter les conditions suivantes :
1. les noeuds compris dans chaque cluster doivent tous
être connectés;
2. chaque cluster a une taille minimale et une taille
maximale;
3. un noeud à chaque niveau de la hiérarchie
appartient à un nombre constant de clusters de ce niveau;
Le problème à résoudre peut être
redéfinit en comment former des composantes connectées
V1, V2, ..., Vn du graphe G = (V, E)
étant donné un entier positif k tel que 1 k
= |V |
respectant les conditions suivantes :
1. uli=1 Vi = V . Chaque noeud
appartient à au moins un cluster.
2. G[Vi], le sous graphe de G induit par chaque
Vi est connecté.
3. La taille des clusters est bornée par :
(a) Vi, |Vi| < 2k.
(b) Vi, il existe un unique k tel que k
= |Vi|, il ne peut avoir qu'un seul cluster de taille
inférieure à k.
4. Vi n Vj 'O(1) : deux clusters doivent
avoir au plus un nombre constant de noeuds en commun.
5. 8(v)|O(1), où
8(v) = {Vi|v E Vi} : un noeud appartient
à un nombre constant de cluster.
La solution centralisée
Banerjee et al. en [27] proposent deux solutions selon que
l'on soit en architecture centralisée ou en architecture
distribuée. Lorsque l'environnement est centralisé, l'algorithme
commence par déterminer un arbre couvrant enraciné du graphe
initial. Les auteurs choisissent d'utiliser le BFS [29]. Les auteurs appliquent
au graphe de départ le parcours BFS et obtiennent un arbre
enraciné dont la racine est le noeud choisit pour lancer le parcours.
Soient T cet arbre,
24
CHAPITRE 2. LES PROTOCOLES DE CLUSTERING DANS LES RÉSEAUX
DE CAPTEURS SANS FIL
T(u) le sous arbre enraciné en u et
C(u) l'ensemble des fils de u. En supposant que
V ~ 2k, il existe toujours un noeud u tel que
T(u) ~ k et que pour chaque fils v de
u, T(v) < k. Supposons que
C(u) = v1, v2, ..., vl. La création des
clusters peut se faire en partitionnant l'ensemble T(v1),
T(v2), ..., T(v,) des sous-arbres de u
enracinés en v1, v2, ..., v, respectivement. Par construction,
les différentes partitions sont disjointes et chacune d'elle est
constituée d'un ensemble de sous arbre tel que le nombre de noeuds la
composant soit compris entre k - 1 et 2(k - 1). Le processus
de création de chaque partition est simple. On y ajoute de façon
séquentielle des sous arbres jusqu'à ce que la taille de la
partition soit comprise entre k - 1 et 2(k - 1). Notons que
l'ajout d'un sous arbre ne peut pas faire exploser la taille de la partition
car un sous arbre a une taille maximale de k - 1. Une seule partition
et notamment la dernière partition à être
créée peut avoir une taille inférieure à k
- 1 (condition 3a). Le noeud racine u de départ est
maintenant ajouté à chaque partition crée afin de garantir
la connectivité de chaque partition et de respecter la condition (2).
Tous les noeuds compris dans des partitions ou clusters sont supprimés
de l'arbre. Le noeud u n'est pas détruit de l'arbre si le
dernier cluster ne satisfait pas la condition sur sa borne. Il sera alors peut
être utilisé pour former le cluster de niveau supérieur.
Ces différentes étapes sont répétées pour
créer tous les clusters. Supposons que l'algorithme de parcours en
largeur ait été appliqué à un graphe et que la
figure 2.6 est la résultante de ce parcours. On suppose que les fils
x, y, p , q, v ,z, r
et s du noeud racine u sont
FIGURE 2.6: Formation de clusters par
l'algorithme de Banerjee et al.
des sous arbres de tailles respectives 0.8k,
0.6k,
0.8k,0.7k,1.3k,
0.7k,0.6k et 0.5k. Au
passage de l'algorithme, on construit cinq clusters B, C,
D, F et A. En traitant le noeud racine x,
la taille de son sous arbre est 0.8k inférieure
à k. On traite ensuite le sommet y et il forme avec x un cluster car
leur taille est supérieure à k. On traite ensuite les sommets p
et q. On forme un nouveau cluster de taille 1.5k. Le sous
arbre enraciné en v est de taille supérieure à k. Donc il
forme un cluster. Les sommets r et s sont traités comme x et y. Ils
forment un nouveau cluster. Le sous arbre enraciné en z est de taille
inférieure à k. Il formera peut être un cluster avec la
racine de l'arbre ou alors il sera le seul cluster de taille inférieure
à k.
La solution distribuée
Il est question de montrer ici comment l'algorithme de
clustérisation de Banerjee et al. s'applique dans un environnement
distribué. Ici, chaque noeud du réseau lance le protocole
25
CHAPITRE 2. LES PROTOCOLES DE CLUSTERING DANS LES RÉSEAUX
DE CAPTEURS SANS FIL
de formation de clusters. Celui-ci est constitué de
deux phases : la création de cluster et la maintenance de cluster
La création des clusters
Ce protocole possède deux étapes importantes
à savoir la découverte de l'arbre et la formation de
clusters. Ici, nous avons une version distribuée de l'algorithme de
création de clusters. Chaque noeud est capable de lancer le protocole de
formation de clusters. Mais les auteurs choisissent la racine de l'arbre BFS du
graphe. Si plusieurs noeuds lancent en même temps le
procédé, on devra alors utiliser un algorithme d'élection
par exemple pour les départager.
La maintenance de clusters
Cette phase du protocole est consacrée aux
opérations internes aux clusters dans deux cas : d'abord lorsqu'un
nouveau noeud rejoint un cluster et ensuite lorsqu'un noeud quitte le cluster.
Ici on modifie la condition sur la taille des clusters et maintenant la borne
supérieure est de 3k. On peut ainsi réunir le cluster de taille
inférieure à k et un cluster de taille inférieure à
2k.
Un noeud rejoint le cluster : Un noeud
capteur v fils du noeud u en rejoignant un cluster établit la liste de
ses voisins N(v). Si un noeud w, élément de
N(v) appartient à un cluster de taille strictement
inférieure à 3k - 1 alors on ajoute le noeud v à
ce cluster. Il peut arriver que l'on se trouve dans la situation où
chaque voisin w de N(v) appartient à un cluster de taille 3k -
1. Dans ce cas, on ajoute le noeud v à un tel cluster ramenant ainsi sa
taille à 3k. Il est ensuite partitionné en deux clusters de
taille supérieure à k pour satisfaire les conditions de taille de
chaque cluster. Notons ici que le noeud v peut appartenir aux clusters
partitionnés.
Un noeud quitte le cluster : Lorsqu'un noeud
quitte le ou les clusters dans lesquels il se trouve, il risque de rendre ces
clusters déconnectés. On peut prouver que le nombre de
composantes restantes dans le cluster est borné. La taille de chacune de
telles composantes est examinée et si elle est supérieure ou
égale à k, cette composante forme à elle seule un cluster.
Sinon, cette partition cesse d'être un cluster et ses noeuds membres
rejoindront un cluster voisin. Le mécanisme est pareil à celui du
paragraphe plus haut.
| 
