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 Partitionnement centré sur le Cluster

A l'opposé des solutions de partitionnement dites centrées sur les noeuds qui permettent la construction de clusters d'au plus deux sauts, il existe les solutions dites centrées sur les clusters

FIGURE 2.2: Exemple de Partitionnement du réseau par l'algorithme DCA

18

CHAPITRE 2. LES PROTOCOLES DE CLUSTERING DANS LES RÉSEAUX DE CAPTEURS SANS FIL

qui permettent la construction de clusters à k sauts. Un k-cluster est constitué d'un groupe de noeuds qui sont mutuellement accessibles par un chemin d'une longueur k ~ 1. Dans cette approche, le réseau est décomposé en clusters de noeuds sans qu'un noeud particulier ne soit désigné comme CH. Dans ce qui suit nous présenterons 03 protocoles qui ont été développés en [25], [26] et [27].

2.4.1 Partitionnement en Clique : Algorithme de Sun et al.

Nous présentons ici un protocole de partitionnement du réseau utilisant l'approche CF (Cluster First ) [25]. Il s'agit d'une approche qui consiste à former les clusters avant l'élection des CHs. Cette approche requiert le fait que chaque noeud accepte l'appartenance à un groupe avant l'élection du leader. C'est ainsi que le réseau est partitionné en clique où la communication directe est possible entre les noeuds appartenant à une même clique. Le protocole développé en [25] a les propriétés suivantes :

· Le protocole est essentiellement distribué et chaque noeud calcule sa clique d'appartenance en envoyant des messages à ses voisins directs.

· L'algorithme de partitionnement se termine. Les noeuds qui y participent et qui ne suivent pas les spécifications du protocole sont systématiquement identifiés et enlevés de toutes les cliques.

· A la fin du partitionnement, le réseau est constitué en cliques deux à deux disjointes et chaque noeud a une vue nette des noeuds membres de sa clique d'appartenance.

Vocabulaire

Le protocole mis sur pied a pour objectif de partitionner un RCSF en des cliques deux à deux disjointes tel que les noeuds d'une même clique puissent communiquer directement entre eux. Chaque noeud doit individuellement déterminer sa clique d'appartenance en se servant des informations échangées avec ses voisins directs. Ce protocole obéit au vocabulaire suivant : on désigne par Ci la clique à laquelle le noeud i appartient. Un noeud est dit normal s'il suit tout le processus de formation des cliques, sinon il est dit malicieux. Les noeuds normaux doivent avoir des cliques consistantes telle que définie par la conformité de clique.

Il y'a conformité de clique pour un noeud normal i si quelque soit le noeud j E Ci, Cj = Ci, autrement dit, s'il existe un noeud j E Ci tel que Cj E/ Ci, on dira qu'il y'a inconsistance de clique. On suppose que chaque noeud a un unique ID, qu'il peut être identifié de manière unique et qu'il connait tous ses voisins qui sont dans sa zone de communication avec les autres[28]. Ce protocole se déroule en quatre étapes s'il n'y a pas une inconsistance de clique et en cinq étapes sinon. Les différentes étapes du protocole de Sun et al. sont les suivantes :

19

CHAPITRE 2. LES PROTOCOLES DE CLUSTERING DANS LES RÉSEAUX DE CAPTEURS SANS FIL

Étape 1 : calcul du LMC :

Notons par LZ la liste des voisins du noeud i. Ici, il est question de déterminer le plus grand groupe (encore appelé LMC) auquel peut appartenir un noeud. Cette étape se divise en 2 sous-étapes : chaque noeud i commence d'abord par envoyer la liste LZ de ses voisins à tous ceux-ci et dès réception, chaque noeud i construit et met à jour la matrice MZ qui représente l'état de la connectivité entre deux noeuds quelconque du groupe de noeuds. cette matrice est construite comme suit :

M(i, j)=

{

1 si j ? LZ 0 si j ?/ LZ

Si un noeud i ne reçoit pas la liste de voisins Li du noeud j, le noeud i considère que le noeud j a été corrompu et le retire de sa liste de voisins LZ. Après cette étape, les différentes matrices sont ensuite symétrisées c'est-à-dire que l'on ne considère que les liens bidirectionnels entre deux noeuds quelconques du graphe induit. Avec cette matrice des voisins, chaque noeud calcule le LMC auquel il appartient. En se basant sur la matrice des voisins de i, on peut construire le graphe GZ = (VZ, EZ) où VZ est constitué des noeuds i et de ses voisins et EZ est l'ensemble des liens bidirectionnels entre les noeuds de VZ. Le calcul du LMC est fait en utilisant l'algorithme suivant :

Algorithme 2.4.1: calcul du LMC

Entrees : Le graphe GZ = {VZ, EZ}, i ? VZ Sorties: : Le groupe LMC YCZ

Etapes :

1 SZ = {j|(i,j) ? EZ};CZ = {i};

2 Tantque SZ =6 Ø Faire

3	Chercher k ? SZ avec le plus grand |LZ n Lk|
4	LZ ? LZ n Lk
5	CZ ? CZ ? {k}
6	SZ ? SZ - {k} - {j|(j,k) ?/ EZ,j ? SZ}

7 Fintantque

La figure 2.3, présente un RCSF non partitionné constitué de 8 sommet à clustériser par l'algorithme de sun et al. Illustrons la construction des LMC pour le noeud 1 de la figure2.3. Notons par C^k_Z le LMC issu du noeud i à la k - ième étape. Pour le noeud 1, L1 = 0, 2, 3, 4, 7 et sa matrice de voisinage est donnée par :

20

CHAPITRE 2. LES PROTOCOLES DE CLUSTERING DANS LES RÉSEAUX DE CAPTEURS SANS FIL

1 ? ? ? ? 1 ? ? ? 1 ? ? ? 0 ? ? ? 0 0 ?

1 1 1 1 1 1

1 1 1 1 0 0

1

=> 1 1 1 1 0

0

0 1 0 1 1 0

0 ? 1 0 0 0 ? ? ? ? ? ? ? ? ? ? ? ? ? 0

On remarque que le lien 0 => 3 n'est pas bidirectionnel donc il ne sera pas considéré comme étant un lien. Les listes des voisins des autres noeuds sont données par : L0 = 1, 2 , L2 = 0, 1, 3, L3 = 1, 2, 4, 5, 6, L4 = 1,3,5,6, L5 = 3,4,6, L6 = 3,4,5, L7 = 1. Initialement, pour le noeud 1, C1 = 1, L1 = 0, 2, 3, 4,7 et S1 = 0, 2, 3, 4, 7. A la première étape, on cherche k. L0L1 = 2, L2L1 = 0,3 , L3L1 = 2,4, L4L1 = 3, _L7L1 =6= 0. Nous trouvons ainsi deux valeurs maximales de k : 2 et 3. On préfère k=2 car c'est le noeud de plus petit identifiant. Ainsi, on ajoute 2 à C1 et on retire 2 de S1. C'est à dire C1 = 1, 2 et S1 = 0, 3,4,7 . Comme les noeuds 4 et 7 ne sont pas directement accessibles depuis le noeud 2, on les retire de S1 et S1 = 0, 3. Au deuxième passage, les noeuds 0 et 3 ont le même nombre de voisins commun avec les noeuds 1 et 2 (membres de C1 ). Le noeud 1 choisit le noeud O car il a le plus petit identifiant. Ainsi, on ajoute le noeud 0 dans C1 et C1 1 = 0, 1,2. On retire les noeuds 0 et 3 de S1 et S1 = . Notons que le noeud 3 est enlevé de S1 uniquement parce qu'il n'est pas directement accessible depuis le noeud 0 comme dit plus haut. L'algorithme prend fin car l'ensemble S1 =6= 0. La sortie est C1 = 0, 1, 2. De la même manière, on obtient C0 1 = C1 2 = 0, 1,2 , C1 3 = C1 4 = C1 6 = 3,4,5,6 et C1 7 = 1,7.

Étape 2 : mise à jour du LMC

Comme le calcul du LMC se fait sur la base d'une heuristique portée sur les voisins, il est possible que les LMC calculés à l'étape 1 par les noeuds voisins diffèrent. Il est donc question de trouver une politique qui permettra de mettre tous les noeuds d'accord sur la composition du groupe de noeuds dans lequel ils se trouvent. Chaque noeud j envoie C1 i à tous ses voisins. Pour question de sécurité, chaque message est authentifié par ,iTESLA¹ Comme le noeud j calcule C1 i par une heuristique basée sur les informations de ses voisins, il est possible que j

1. Le protocole /1TESLA est une variante du protocole TESLA qui est utilisé pour l'authentification des messages émis par diffusion.

FIGURE 2.3: Un graphe à 8 sommets à clustériser par l'algorithme de Sun et al.

21

CHAPITRE 2. LES PROTOCOLES DE CLUSTERING DANS LES RÉSEAUX DE CAPTEURS SANS FIL

reçoive plus de LMC C1 j d'un voisin j qu'il ne contienne. D'où, après réception des LMC de ses voisins, le noeud i vérifie s'il existe une clique C1 j meilleure que C1 i . Pour y remédier, Sun et al. ont défini une relation d'ordre sur les groupes formés par chaque noeud i. Ainsi, pour deux

i i

groupes de clusters Ci et Cj la relation d'ordre ? définit par : Cj ? Ck si et seulement si :

1. i ? Cj,i ? Ck et

2. (a) |Cj| < |Ck|, ou

(b) |Cj| = |Ck|, mais cj < ck, où cj = min{ai|ai ? Cj ? ai ?/ Ck} et ck = min{bi|bi ? Ck ? bi ?/ Cj} ou

(c) cj = ck mais j < k i

Cette relation d'ordre ? sur les groupes maximaux locaux construits par chaque noeud i du graphe est une relation d'ordre total². Ils peuvent ainsi comparer les LMC reçus par chaque noeud. L'illustration de cette étape sur l'exemple de la figure 2.3 est la suivante : Après réception des LMC de ses voisins, le noeuds 1 a C1 0 = C1 1 = C1 2 = {0,1,2}, C1 3 = C1 4 = {3,4,5,6} et C1 7 = {1, 7}, et dès lors, il supprime directement C1 3 = C1 4 car il n'apparait pas dans cette

i

dernière. D'une part, comme |C¹ ₇| < |C¹ ₀|, on a C¹ ? C¹ ₀. D'autre part, C1 0 = C1 1 = C1 2 mais les

7

1 1

ID des noeuds sont rangés comme suit 0 < 1 < 2, on alors C¹ ? C¹ ? C¹ ₂. D'où le noeud 1

0 1

1 1 1

ordonne les cliques des noeuds 0, 1, 2 et 7 comme suit : C¹ ? C¹ ? C¹ ? C1 2 et met à jour sa

7 0 1

clique en faisant C²₁ = C1 2 = {0, 1, 2}.

La figure2.4 illustre le graphe de la figure 2.3 clustérisé à la fin de la deuxième étape du protocole.

FIGURE 2.4: Le graphe clustérisé à la fin de l'étape 2 de l'algorithme de Sun et al.

Etape 3 : détermination de la clique finale

A la fin de l'étape 2, il se pose encore un problème car les différents LMC ne sont pas disjoints (par exemple, C²₁ et C2 7 contiennent tous deux le noeud 1). Pour déterminer le groupe de noeuds final, chaque noeud diffuse son LMC construit à tous ses voisins toujours en application du protocole sécurisé de diffusion ,iTESLA. Pour chaque noeud j membre de C2 i , le noeud i vérifie s'il est inclut dans le LMC de j C2 j . Si tel n'est pas le cas, le noeud i retire le noeud j de C2 i . Si le noeud i ne reçoit pas C2 j mis à jour du noeud j, le noeud i conserve le noeud j dans son LMC. Avec le même exemple, parce que C²₁ ne contient pas le noeud 7, le noeud 7 retire le noeud 1 de C²₁ et

2. une relation d'ordre est dite totale si elle est réflexive, transitive et antisymétrique

22

CHAPITRE 2. LES PROTOCOLES DE CLUSTERING DANS LES RÉSEAUX DE CAPTEURS SANS FIL

obtient C3 7 = 7. A la fin, on obtient C3 0 = C3 1 = C3 2 = 0,1,2 , C3 3 = C3 4 = C3 5 = C3 6 = 3,4,5,6 et C3 7 = 7. La figure2.5 illustre les différents clusters formés par l'algorithme de Sun et al. en utilisant comme graphe de départ celui de la figure2.3

FIGURE 2.5: Le graphe final clustérisé en utilisant l'algorithme de Sun et al.

Étape 4 : vérification de la conformité des cliques

Chaque noeud i calcule également un code de sécurité en se basant sur les messages reçus lors des quatre premières étapes, le signe et l'ajoute dans le message contenant la clique finale. Quand un noeud normal reçoit la première copie de la clique finaleC3 _j de son voisin j ou envoyé par un autre voisin, si j E C3 i , alors j ré-envoie la clique C3 j . Le but de ce ré-envoie est de prévenir les attaques silencieuses. Chaque noeud i vérifie la conformité de la clique, c'est-à-dire le noeud i vérifie que pour tout j E C3 i , C3 j = C3 i . Si une inconsistance de clique est détectée, le noeud i entre à l'étape 5, sinon il termine le processus de formation des cliques.

Étape 5 : identification des noeuds malicieux

Cette étape s'effectue en deux phases : la vérification de la conformité des cliques et la suppression des noeuds malicieux. La première phase à savoir la vérification de la conformité a pour objectif d'identifier les noeuds malicieux qui ont envoyé les messages inconsistants dans les précédentes étapes. Quand les noeuds malicieux sont détectés par le noeud i, ce dernier envoie une alerte aux autres noeuds en utilisant la signature du noeud malicieux comme preuve. Après avoir enlevé les noeuds malicieux du réseau, le protocole est relancé. Le déroulement de ce stage est le suivant : si un noeud i détecte une inconsistance de clique avec le noeud j, le noeud i demande au noeud j de lui envoyer tous les messages qu'il a reçu aux 4 premières étapes. Comme le noeud j a reçu la clique authentifiée finale C3 i à l'étape 4, seulement si C3 i =6 C3 j , le noeud j fournit tous ses précédents messages reçus de i. Le noeud j a besoin de signer ces messages pour prouver qu'ils ont été envoyés par lui. Après identification des noeuds malicieux, le noeud i entre à la deuxième phase.

La deuxième phase est la suivante : quand une attaque silencieuse³ est lancée par un noeud malicieux, un noeud normal ne peut pas avoir de preuve pour convaincre les autres noeuds

3. Il y'a attaque silencieuse par un noeud malicieux lorsque ce dernier envoie les messages à certains de ses voisins et pas à d'autres

23

CHAPITRE 2. LES PROTOCOLES DE CLUSTERING DANS LES RÉSEAUX DE CAPTEURS SANS FIL

normaux qui ont reçu les messages du noeud malicieux. De plus, le noeud normal ne peut pas distinguer le noeud normal qui a réellement détecté un noeud malicieux du noeud malicieux qui cherche à lancer une fausse alerte sur un noeud normal.

Une limite de l'algorithme de Sun et al. présenté ci dessus est le fait qu'il ne permet pas de former une hiérarchie de clusters. Pour pallier à cette insuffisance, Banerjee et al. montrent comment on peut réaliser un clustering hiérarchique dans un réseau.