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.4 partitionnement en 3D

le protocole [26] présenté ci-dessus permettant d'avoir une architecture virtuelle, ne s'applique que dans le cas où les capteurs sont déployés dans le plan. Or la réalité voudrait que ce protocole puisse prendre en compte un réseau où les capteurs sont déployés dans un espace sujets à des irrégularités, ou simplement quand les capteurs sont déployés dans un espace. le protocole présenté ici est celui de [22]. Il se base de celui réalisé en [26] pour établir un protocole de partitionner pour un RCSF déployé dans l'espace (en dimension 3).

Système de coordonnées dynamiques

Pour des raisons de simplicité nous appellerons couronne de rayon ri, 1 < i < l, l'espace délimité par les sphères de rayon _ri-1 et ri. Notre système de coordonnées est centré sur le noeud sink. On suppose que ce dernier peut effectuer l puissances transmissions omnidirectionnelles, m transmissions directionnelles⁴ horizontales et n transmissions directionnelles verticales. Les l puissances d'émission omnidirectionnelles déterminent l sphères de rayon r1 < r2 < r3 < rl. Les m transmissions directionnelles horizontales définissent les sections horizontales et les n transmissions directionnelles verticales quant à elles définissent les sections verticales. Cette stratégie d'émission permet de définir une structure composée de l x m x n grappes ou clusters de coordonnées (i, j, k). Les capteurs d'une grappe ont les mêmes coordonnées géographiques.

4. Une transmission directionnelle est une transmission qui est émise dans une directions précise suivant un angle donné, recouvrant ainsi une portion de l'espace de déploiement semblable à une tranche d'orange.

28

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

La figure 2.8 illustre l'architecture virtuelle de notre réseau de capteurs, on y montre un exemple de section verticale ainsi qu'un cluster appartenant à la couronne la plus externe (couronne 4).

FIGURE 2.8: Système de coordonnées dynamiques

Formation des couronnes

L'entier l est connu de tous les capteurs. Ainsi, chaque noeud doit lire une chaîne de log₂(l) bits, déterminant l'identité de sa couronne, comme le montre la figure 2.9. On suppose que le temps est divisé en slots s1, s2, s3, ..., _{sl_1} et que les horloges des capteurs sont synchronisées avec celle du noeud sink. La réception d'un signal émis par le noeud sink est codée par 0 et la non-réception du signal après un délai r est codée par la valeur 1. Les capteurs connaissent le numéro du slot en cours. Au premier slot, tous les capteurs sont éveillés et enregistrent le bit de poids fort du numéro de la couronne dans laquelle ils se trouvent. Les capteurs qui enregistrent la valeur 0 au slot i resteront éveillés au slot i+1. Quant aux capteurs qui enregistrent la valeur 1 au slot i, ils s'endormiront jusqu'au slot k (la valeur de k est déterminée dans la section 2.4.4). Dès qu'un capteur a enregistré ses log₂(l) bits, il s'endort jusqu'au slot l - 1. L'algorithme de construction des couronnes se poursuit ainsi jusqu'à son achèvement selon le protocole de partitionnement d'idrissa SOW [1] mais en utilisant la clé _Kinit lors des communications.

Illustration de la formation des couronnes pour k = 4 :

Étant donné que log₂(4) = 2, on utilisera donc 2 bits pour identifier chaque couronne. Ce cas de figure est illustré par la figure 2.9, où nous avons quatre couronnes numérotées de 1 à 4. Premier slot

Pour le premier bit, on veut que les capteurs des couronnes 1 et 2 enregistrent la valeur 0 et que ceux des couronnes 3 et 4 enregistrent la valeur 1. Étant donné que la réception du signal est codée par la valeur 0 et la non réception par la valeur 1, le noeud sink au premier slot doit utiliser le rayon de transmission r2. Ainsi les capteurs des couronnes 1 et 2 enregistreront la valeur 0 tandis que les capteurs des couronnes 3 et 4 enregistreront la valeur 1.

29

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

Deuxième slot

Puisque les capteurs des couronnes 1 et 2 ont enregistré la valeur 0 au premier slot, ils restent éveillés au slot 2. Le noeud sink émet en broadcast dans le rayon r1 pour permettre aux capteurs de la couronne 1 d'enregistrer 0 et ceux de la couronnes 2 d'enregistrer la valeur 1. Comme ces capteurs ont déjà enregistré 2 bits =log₂(l), ils s'endorment jusqu'à la fin du slot 3 = 4 - 1. Pendant le slot 2 les capteurs des couronnes 3 et 4 sont en veille, donc ils n'enregistrent rien.

Troisième slot

Le noeud sink émet en broadcast dans le rayon r3 pour permettre aux capteurs de la couronne 3 d'enregistrer 0 et ceux de la couronne 4 d'enregistrer la valeur 1. Pendant le slot 3 les capteurs des couronnes 1 et 2 sont en veille, donc ils n'enregistrent rien.

La figure 2.10a illustre la formation des couronnes pour k = 4. On y voit clairement que tous les capteurs enregistrent leur bit de poids fort au premier slot. Au deuxième slot, seulement les capteurs des couronnes 1 et 2 enregistrent leur second bit. Enfin, les capteurs des couronnes 3 et 4 enregistrent leur second bit au slot 3. Le rayon de transmission utilisé par le noeud sink a chaque slot est aussi mentionné. L'arbre binaire de la figure 2.10b est utilisé par le noeud sink pour déterminer les différents slots et rayons de transmission. Nous le définissons dans la section 2.4.4.

Méthode analytique de détermination des rayons de transmissions omnidirectionnelles

Considérons l'arbre binaire A complet à l feuilles numérotées de 1 à l comme le montre la figure 2.11. Pour chaque sommet, l'arête menant à son sous arbre gauche est étiquetée par 0 et

celle menant à son sous arbre droit est étiquetée par 1. Soit x, (1 x l), le numéro d'une
feuille quelconque u de l'arbre A et b1, b2, ..., _blog2(l) les étiquettes de l'unique chemin allant de la racine jusqu'à u;. On a :

FIGURE 2.9: Formation des couronnes

30

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

(a) (b)

FIGURE 2.10: Formation des couronnes pour k = 4

1 =	1	+ ^0×2log2(4))-1+ ^0×2log2(4))-2,				log2(4) = 2
2 =	1	+ 0×2^2-1+ 1×2^2-2
3 =	1	+ 1×2^2-1+ 0×2^2-2
4 =	1	+ 1×2^2-1+ 1×2^2-2
Doù la formule:				log2(l)
			x = 1 +	X j=1	bj2log2(l)-j (2.2)

(a) Parcours préfixé. (b) Parcours infixé.

FIGURE 2.11: Étiquetage et parcours.

Soit A, le sous arbre constitué essentiellement des noeuds internes de A numérotés dans le parcours préfixé de 1 à l - 1 comme l'indique la figure 2.11a. Soit u un sommet quelconque de A et b1, b2, ..., _blog2(l) les étiquettes de l'unique chemin allant de la racine jusqu'à u; j est la profondeur de u. Les lemmes ci-après sont tirés de [22].

Lemme 1. Le rang de u dans le parcours préfixé de A^' est donné par la formule:

p(u) = 1 + i-1_X Cj (2.3)

j=1

Avec Cj =

? ? ?

1 si bj = 0 2j si bj = 1 l

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

Preuve. Pour la racine, on a p(rac) = 1 + P0 j=1 C1 = 1. Supposons la formule vraie pour un noeud quelconque x/p(x) < p(u); soit v le père de u; alors u et v partagent l'unique chemin b1b2...bi-2. Donc, p(v) = 1 + Pi-2

j=1 Cj et comme u est le fils de v , on a :

p(u) = p(v) +	? ? ?		1 si u est le fils gauche de v 2i-1 si u est le fils gauche de v k
d'où p(u) = 1+		i-2 X j=1		Cj + Ci-1 =	i-1X j=1	Cj

31

Considérons A^' dans son parcours infixé comme le montre la figure 2.11b.

Lemme 2. Soit u un sommet quelconque de A et n(u) son rang dans le parcours infixé de A . Soit t le rang de la feuille de A la plus à droite dans le sous arbre gauche enraciné en u. Alors, n(u) est donné par:

n(u) = t (2.4)

Preuve. On procède par récurrence sur l'ordre de visite des sommets de A^' par un parcours infixe. Pour n(u) = 1, u est la feuille la plus à gauche dans A^' et son sous arbre gauche dans A se résume à la feuille la plus à gauche dans A.

Supposons la propriété est vraie pour tout sommet x de A^' tel que n(x) < n(u). On distingue alors deux cas :

Premier cas Soit v un parent de u dans A^'. Notons par A^'(v) le sous arbre de A^' enraciné en v. Le sommet u est dans ce cas, la feuille la plus à gauche dans le sous arbre droit de A^'(v). Soit q le rang de la feuille de A la plus à droite dans le sous arbre gauche de A^'(v). Par hypothèse de récurrence n(v) = q. Puisque u est une feuille dans A^', il possède deux fils (feuilles) de rang q + 1 et q + 2 dans A. Alors dans ce cas n(u) = n(v) + 1 = q + 1.

Deuxième cas Soit u un parent de v dans A^'. Notons par A^'(u) le sous arbre de A^' enraciné en u. Le sommet v est dans ce cas, la feuille la plus à droite dans le sous arbre gauche de A^'(u). Supposons que n(u) = r. Le sommet v il possède deux fils (feuilles) dans A. Par hypothèse de récurrence ces fils sont au rang r et r + 1. Par conséquent n(u) = n(v) + 1 = r + 1.

Pour la méthode de détermination des rayons de transmission omnidirectionnelles, les paramètres p(u) et n(u) des sommets internes de A correspondent respectivement aux découpes de temps en des instants appelés slots et aux rayons de transmissions utilisés par le noeud sink. Soit i un entier tel que 2 i log₂(k) - 1, supposons qu'un noeud u a renseigné son (i - 1)^e bit de poids fort à la fin du slot s. Le résultat qui suit est une conséquence des lemmes 1 et 2.

Corollaire 2. En ayant lu les bits _b1b2...bi-1, le capteur u doit se réveiller au slot z = p(u) :

z = p(u) = 1 + i-1_X Cj (2.5)

j=1

32

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

Ainsi, lorsqu'un capteur quelconque a enregistré 1 comme son i^e bit / i < log₂(l) au slot j, il s'endort et se réveille au slot k où k est le rang du fils droit du noeud interne de profondeur

j dans le parcours infixé de A.

l

Alors,k = j + (2.6)

2i

Si on se place dans notre exemple pour l = 4, les capteurs des zones 3 et 4 après avoir enregistré la valeur 1 pour leur premier bit (i = 1) au slot 1, ils dorment et se réveillent au début du slot

k = 3.

4

= 3

k = 1 + 21

Formation et méthode de détermination des sections horizontales

FIGURE 2.12: Formation des sections horizontales

Ici, on subdivise l'espace de déploiement en m sections angulaires horizontales d'angles égaux à áh comme le montre la figure 2.12. Comme dans le cas précédent les capteurs doivent lire une chaîne de longueur log2(m) pour déterminer l'identité de leur section horizontale. Le temps est découpé en slots s1, s2, ..., _sm-1 et à chaque slot correspond une émission directionnelle d'angle âi. Pour les capteurs, le procédé est similaire à celui de formation des couronnes. La réception d'un signal est codée par 0 et la non réception du signal par 1. La différence ici se situe au niveau du noeud sink qui n'effectue plus des transmissions omnidirectionnelles, mais plutôt des transmissions directionnelles selon un angle âi. Le noeud sink utilise le même arbre binaire A de la figure 2.11 pour déterminer les différents angles de transmission directionnelles. Le parcours préfixé détermine les différents slots p(A) = s1, s2, ..., _sm-1. Le parcours infixé donne un second paramètre n(A) qui permet de calculer les angles d'émission du noeud sink.

Soit u un noeud quelconque de A^', p(u) son rang dans le parcours préfixé de A^' et n(u) son rang dans le parcours infixé de A^'. La direction d'émission du noeud sink au slot p(u) est donnée par:

âi = n(u) X 2ð/m (2.7)

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

Le tableau 2.1 récapitule les différents slots et angles de transmission pour m = 4.

Préfixe de A : p(A)	Infixe de A : n(A)	Direction de lantenne : âi
1	2	n(u) X 2ir/m = 2 X 2ir/4 = ð
2	1	ir/2
3	3	3ir/2

TABLE 2.1: Calcul des angles de transmissions horizontales pour m=4

Illustration de la formation des sections horizontales pour k = 4 :

Premier slot

Au premier slot, les capteurs des sections 1 et 2 doivent enregistrer la valeur 0 et ceux des sections 3 et 4 la valeur 1. Le noeud sink au premier slot utilise l'angle de transmission horizontale âi = 2ð 2 = ir. Ainsi les capteurs des sections 1 et 2 enregistreront la valeur 0 tandis que les capteurs des sections 3 et 4 enregistreront la valeur 1.

Deuxième slot

Étant donné que les capteurs des sections 1 et 2 ont enregistré la valeur 0 au premier slot, ils restent éveillés au slot 2. Le noeud sink effectue une transmission horizontale d'angle ₂ pour permettre aux capteurs de la section 1 d'enregistrer 0 et ceux de la section 2 d'enregistrer la valeur 1. Puisque les capteurs des sections 1 et 2 ont déjà enregistré leur 2 bits, ils s'endorment jusqu'à la fin du slot 3. Pendant le slot 2, les capteurs de la section 3 et 4 sont en veille, donc ils n'enregistrent rien.

Troisième slot

Le noeud sink émet une transmission horizontale d'angle3ð ₂ pour permettre aux capteurs de la section 3 d'enregistrer 0 et ceux de la section 4 d'enregistrer le valeur 1. Pendant le slot 3, les capteurs de la section 1 et 2 sont en veille, donc ils n'enregistrent rien.

Le tableau 2.2 récapitule les différents slots et angles de transmissions horizontales pour

m = 8. La figure 2.13 illustre les angles de transmission dont il est question dans le tableau 2.2.

Préfixe de A : p(A)	infixe de A : n(A)	Direction de lantenne : âi
1	2	n(u) x 2ir/m = ir
2	4	ir/2
3	1	ir/4
4	3	3ir/4
5	6	3ir/2
6	5	5ir/2
7	7	7ir/2

33

TABLE 2.2: Calcul des angles de transmissions horizontales pour m = 8.

34

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

FIGURE 2.13: Les différents angles d'émission du noeud sink pour in = 8.

FIGURE 2.14: Formation des sections verticales Formation et méthode de détermination des sections verticales.

Ici, on subdivise l'espace de déploiement en n sections angulaires verticales d'angles égal à á_v=2ð/n comme le montre la figure 2.14. Comme dans le cas précédent les capteurs doivent lire une chaîne de longueur log2(n) pour déterminer l'identité de la section verticale dans laquelle ils se trouvent. Le temps est découpé en slots et à chaque slot correspond une émission directionnelle d'angle /3j. Le procédé est similaire à celui de formation des sections horizontales. On utilise le même arbre binaire A, définis dans la section 2.4.4. Les tableaux récapitulant les différents slots et angles de transmissions verticales pour n = 4 et n = 8, sont pareilles à ceux des angles de transmissions horizontales définis dans la section 2.4.4. Il en est de même pour la figure 2.13, qui illustre les différent angles des transmission dont il est question dans le tableau 2.2. Ici le noeud sink effectue plutôt des transmission directionnelles verticales comme l'illustre la figure 2.14.

Récapitulatif pour la formation des clusters de la sphère la plus interne

La figure 2.15 retrace sommairement les trois phases de notre algorithme de partitionnement pour les capteurs se trouvant dans la couronne de rayon r1. Initialement, les capteurs n'ont

35

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

FIGURE 2.15: Récapitulatif pour la formation des clusters de la sphère la plus interne

aucune idée de leur emplacement.

Phase 1 : tous les capteurs enregistrent leur numéro de couronne; Phase 2 : ils enregistrent leur numéro de section horizontale; Phase 3 : ils enregistrent leur numéro de section verticale.

Theoreme 1. Le temps d'exécution total de l'algorithme de partitionnement de l'espace d'intérêt est donné par :

T = (l - 1) x ô + (m - 1) x ô + (n - 1) x ô = (l + m + n - 3) x ô (2.8)

Preuve. L'étape de formation des couronnes nécessite (l - 1) slots, et un slot dure ô temps. Il en est de même pour la formation des m sections horizontales et des n sections verticales.