Une approche de protocole de géocasting sécurisé dans un réseau de capteurs sans fil déployés dans l'espace.

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, ..., V_n 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.