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

5.3.6 Routage sécurisé intra-cluster

Une fois que le routage inter-cluster est défini, il faut encore spécifier comment les données sont gérées au sein d'un même cluster afin d'éviter la surcharge du réseau. Pour ce faire, nous utilisons la notion de CH qui sera pour un cluster donné l'unique noeud chargé d'acheminer les données vers le cluster relais ¹. Les données sont collectées aux membres d'un cluster par un CH et acheminer à un autre cluster ou au noeud sink. Ainsi une phase de détermination du CH est nécessaire.

5.3.7 Élection du Cluster Head

Les CHs auront pour rôle d'acheminer les données d'un cluster vers un autre cluster qui, à son tour, les acheminera vers le noeud sink. Cette élection est initiée par le noeud sink qui diffuse dans tout l'espace de déploiement des capteurs, un message authentifié à l'aide de la clé K {n/bs}, indiquant la date de début pour que les capteurs soient synchronisés entre eux, mais le noeud sink n'intervient pas lors de l'élection proprement dite. Précisons que lors du processus d'élection du CH, tous les noeuds exécutent l'algorithme de réservation du canal de Nakano et al. [54] afin d'éviter les interférences/collisions lors des communications.

La gestion du routage dans un cluster fait que le CH dépense plus d'énergie qu'un noeud ordinaire. De ce fait, il serait judicieux d'octroyer le rôle de CH aux noeuds qui disposent assez d'énergie (supérieure à un seuil donné que nous notons E_s) [22]. L'énergie résiduelle est propre à chaque noeud et est notée E_r(u). supposons qu'un un noeud est capable d'évaluer son énergie résiduelle E_r(u); elle n'a pas d'impact lors de la première exécution de l'algorithme de partitionnement, puisque à ce stade, les noeuds disposent tous de la même quantité d'énergie. Pour élire un CH, les capteurs du cluster (i, j, k) (i > 1) qui ont une énergie résiduelle supérieure au seuil E_s, envoient un message Hello en direction du cluster (i-1,j, k) et attendent un accusé de réception. Ensuite, tous les capteurs ayant reçu des accusés de réception (Hi) se proposent comme CH, en diffusant le message Head en direction de leur propre cluster. Le capteur ayant la plus grande énergie résiduelle E_r(u) parmi ceux qui se sont proposés comme CH est élu. S'il y

1. Cluster par lequel transite les données d'un autre cluster pour atteindre le noeud sink.

66

CHAPITRE 5. NOTRE CONTRIBUTION : UNE APPROCHE DE PROTOCOLE DE GÉOCASTING SÉCURISÉ DANS UN RCSF DÉPLOYÉ DANS L'ESPACE (EN 3D)

a plusieurs noeuds candidats qui ont la même énergie résiduelle, le noeud qui est élu est celui qui a le plus grand identifiant. En ce qui concerne les capteurs des clusters (1, j, k), ils n'envoient pas de message Hello, mais répondent aux messages Hello envoyés par les capteurs des clusters (2, j, k). Ensuite, ceux qui ont une énergie résiduelle supérieure au seuil E₈ envoient un message Head en direction de leur propre cluster, et les critères d'élection sont les mêmes pour tous les capteurs. Ainsi, quand les noeuds du même cluster veulent transmettre des paquets, ils les acheminent d'abord vers le CH qui se chargera de les transmettre au cluster suivant (que nous désignons cluster relais). Un capteur qui reçoit des paquets qui ont pour destinataire sa grappe les achemine vers le CH. Si les données reçues ne sont pas destinées à son cluster, il les ignore tout simplement. Quand le CH atteint le seuil de niveau de batterie E₈, il relance le processus d'élection d'un nouveau CH, mais il ne se présente plus. Notons que cet élection se fait de façon parallèle et les communications sont sécurisées à l'aide de la clé commune partagée avec tous les noeuds du cluster. La procédure 5.3.1 permet d'initialiser le processus d'élection par

Algorithme 5.3.1: Procédure init()

Entrees: E_r, E₈

Sorties: : Le message Hello 1 Debut

2		Si (Er > E8) Alors			3
		Si (i > 1) Alors	4
			Hello +- msg(ID, (i,j, k), (i - 1,j, k)) ;	5
			radio.transmit(Hello) ;	6
		Sinon	7
			deja_recu +- vrai ;	8
		Finsi	9
Finsi

10 Fin

la diffusion du message Hello. La procédure 5.3.2 décrit le comportement des capteurs lors de la réception du message Hello et la procédure 5.3.3 quant à elle décrit l'action à faire lors de la réception d'un message Hi. Enfin, la procédure 5.3.4 est l'élection proprement dite du CH après réception du message Head.

· La variable globale deja_recu permet de s'assurer qu'un capteur réagit une seule fois à la réception des messages Hi;

· La variable globale Cluster_Head permet de garder l'identité du CH;

· La variable cluster_relais permet de garder l'identité du cluster relais.

L'algorithme 5.3.5 fait appel aux procédures 5.3.1,5.3.2, 5.3.3 et 5.3.4 pour donner la démarche complète de l'élection du CH. Il se subdivise en deux phases : une première dans laquelle les capteurs qui ont une énergie résiduelle supérieure au seuil minimum E₈ s'assurent qu'ils peuvent communiquer avec le cluster relais (procédures 5.3.1, 5.3.2 et 5.3.3) et une seconde phase qui consiste en l'élection proprement dite (via la procédure 5.3.4).

2

3

4

5

6

CHAPITRE 5. NOTRE CONTRIBUTION : UNE APPROCHE DE PROTOCOLE DE GÉOCASTING SÉCURISÉ DANS UN RCSF DÉPLOYÉ DANS L'ESPACE (EN 3D)

Algorithme 5.3.2: Après la réception d'un message Hello : reception_Hello()

Entrees : Le message Hello Sorties: : Le message Hi 1 Debut

Si (desti(Hello) == vrai) Alors

ID1 +- Hello.ID ;

Hi +- msg(ID, ID1, (i,j, k), (i + 1,j, k)) ;

radio.transmit(Hi) ;

Finsi

7 Fin

Algorithme 5.3.3: Après la réception d'un message Hi : reception_Hi()

Entrees: Le message Hi

Sorties: : Les coordonnées du cluster relais. 1 Debut

2

3

4

5

6

Si (desti(Hi) == vrai) Alors

deja_recu +- vrai;

cluster_relais +- (i - 1,j, k) ;

Cluster_Head +- (ID, E_r) ; Finsi

2

3

4

5

6

7

8

9

10

11

12

13

14

15

7 Fin

Algorithme 5.3.4: Après la réception d'un message Head: reception_Head()

Entrees: Le message Head

Sorties: : L'identifiant du Clustr Head

1 Debut

Si (desti(Head) == vrai) Alors

Si (deja_recu == faux) Alors

Cluster_Head +- (Head.ID, Head.E_r) ;

deja_recu +- vrai ;

Sinon

Si (Head.E_r > Cluster_Head.E_r) Alors

Cluster_Head +- (Head.ID, Head.E_r) ;

Sinon

Si (Head.E_r == Cluster_Head.E_r) et (Head.ID > Cluster_Head.ID) Alors

Cluster_Head +- (Head.ID, Head.E_r) ;

Finsi

Finsi

Finsi

Finsi

16 Fin

67

CHAPITRE 5. NOTRE CONTRIBUTION : UNE APPROCHE DE PROTOCOLE DE GÉOCASTING SÉCURISÉ DANS UN RCSF DÉPLOYÉ DANS L'ESPACE (EN 3D)

Puisqu'un capteur peut recevoir (et/ou envoyer) les messages Hello, Hi et Head plusieurs fois, il peut aussi exécuter les procédures correspondantes plusieurs fois. Puisque nous avons comme seule hypothèse le fait que le réseau est dense, nous ne pouvons pas prédire le nombre de capteurs dans les différents clusters. Ainsi, le nombre d'appels des procédures 5.3.1, 5.3.2,5.3.3 et 5.3.4 n'est pas prévisible. D'où, il sera à la charge de l'utilisateur final de paramétrer la durée de chacune des phases de l'algorithme 5.3.5. Néanmoins, la durée de chaque phase doit permettre que chacune des procédures 5.3.2,5.3.3 et 5.3.4 puisse se réaliser plusieurs fois.

Remarque 1. Les temps T1 et T2 de chacune des phases de l'algorithme 5.3.5 doivent être déterminées en fonction du nombre de slots nécéssaires à l'exécution de chacune des procédures 5.3.1,5.3.2, 5.3.3 et 5.3.4 et du nombre maximal de capteurs dans un cluster.

Algorithme 5.3.5: Election_CH

Entrees : Les durées T1 et T2.

Sorties: : L'identifiant du Cluster Head. 1 Debut

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

deja_recu +- faux;

step1 +- time() + T1 ;

init() ;

Tantque (time() step1) Faire

Si (Hello +- radio.receive()) == vrai) Alors

reception_Hello() ; Finsi

Si (Hi +- radio.receive()) == vrai) et (deja_recu == faux) et (Hi.ID1 == ID) Alors

reception_Hi() ; Finsi

Fintantque

step2 +- time() + T2 ;

Si (deja_recu == vrai) Alors

Head +- msg(ID, E_r, (i,j, k)); radio.transmit(Head) ;

Finsi

Tantque (time() step2) Faire

Si (Head +- radio.receive()) == vrai) Alors

reception_Head() ; Finsi

Fintantque

68

23 Fin

Chacune des procédures 5.3.1, 5.3.2, 5.3.3 et 5.3.4 se déroule en temps constant. Si nous désignons par C le nombre total de capteurs, alors, la plus mauvaise répartition des capteurs dans l'espace d'intérêt est la suivante : (l x m x n - 1) clusters contiennent exactement un seul capteur chacun et le dernier cluster en contient tout le reste, c'est-à-dire (C - l x m x n - 1).

69

CHAPITRE 5. NOTRE CONTRIBUTION : UNE APPROCHE DE PROTOCOLE DE GÉOCASTING SÉCURISÉ DANS UN RCSF DÉPLOYÉ DANS L'ESPACE (EN 3D)

Ainsi, le nombre de capteurs contenu dans un cluster est compris entre 1 et C - l x in x n - 1. Ceci nous permet d'énoncer le théorème 2.

Theoreme 2. Dans le pire des cas, l'algorithme 5.3.5 nécessite O(C) temps d'exécution.

Preuve. Les capteurs exécutent la procédure init() une seule fois, donc O(1) temps d'exécution. Dans la première boucle tantque de l'algorithme 5.3.5 (ligne 5), les procédures 5.3.2 et 5.3.3 sexécutent au plus (C - l x in x n - 1) fois chacune. Donc cette boucle nécessite 2 x O(C) = O(C) temps d'exécution. De même, la deuxième boucle tantque de l'algorithme 5.3.5 (ligne 18), fait au plus (C -lxinxn-1) appels de la procédure 5.3.4, donc sa complexité est temporelle est donnée par O(C). On peut conclûre de tout ceci que la complexité temporelle de l'algorithme 5.3.5 est en O(C). C'est-à-dire que son temps dexécution est fonction du nombre total de capteurs dans le pire des cas.

Remarque 2. Dans notre travail, nous supposons que tous les capteurs des clusters (1, j, k) peuvent directement communiquer avec le noeud sink. Dans le cas contraire, les capteurs des clusters (1, j, k), candidats pour devenir CH, devraient s'assurer de leur connexion directe avec le sink avant d'envoyer le message Head. Et dans ce cas, le noeud sink devra participer au processus en tant que seul capteur du cluster (-1, -1, -1).