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

Une Approche de protocole de Géocasting sécurisé dans

un Réseau de Capteurs sans fil déployés dans l'espace

KEUMBOUK DONFACK ANGE ANASTASIE

27 juillet 2016

Dédicaces

i

A mes parents:

KEUMBOUK Robert & TONFAC Marthe Huguette Aurelie

ii

Remerciements

En préambule à ce travail, je souhaiterais adresser mes remerciements les plus sincères à toutes les personnes qui m'ont aidée, de près ou du loin, dans la réalisation de ce travail.

Tout d'abord et avant tout, je remercie vivement le bon Dieu, le tout puissant qui nous guide le chemin droit, de m'avoir permis d'emprunter le chemin de la recherche et de m'avoir donné suffisamment de courage et de patience pour accomplir ce travail.

. Ma profonde gratitude et mes sincères remerciements vont également à l'encontre de :

· Pr. TAYOU DJAMEGNI Clémentin, qui grâce à ses précieux conseils et ses multiples remarques, m'a donné le goût de la recherche; une fois de plus, merci Professeur.

· Mon encadreur Dr. BOMGNI Alain Bertrand , qui a cru en mes capacités et m'a permis de mener à bien mes travaux. Ce mémoire doit beaucoup à ses conseils précieux, à sa rigueur, son sens du travail bien fait, à son calme et à sa disponibilité.

· FOKO SIDJOUNG Landry, pour sa disponibilité, son aide, ses conseils, et pour toutes les prestigieuses remarques qu'il a fait à mon encontre afin d'améliorer ce travail.

· Tous les enseignants du département de Mathématiques-Informatique de l'université de Dschang, et plus particulièrement aux Docteurs TCHOUPE TCHENDJI Maurice, KENGNE TCHENDJI Vianey, FUTE TAGNE Elie, TCHEKA, pour m'avoir permis de rêver et de poursuivre mes études dans ce merveilleux domaine qu'est l'informatique.

· Mon camarade KENFACK ZEUKENG Ulrich, qui était toujours là, prêt à m'aider , me conseiller et me déboguer face à une difficulté rencontrée.

· Mon père, papa KEUMBOUK ROBERT, qui m'a toujours soutenu, encouragé, et motivé; et qui, grâce à ses multiples remarques sur la vie me permet de me remettre toujours en question, et de chercher à atteindre le sommet.

· Ma mère, Maman KEUMBOUK MARTHE HUGUETTE qui a toujours été là pour moi dans tout les domaines de ma vie à me soutenir et m'encourager. Sa confiance, sa tendresse et sa prière me guident tous les jours.

· Mon Bien-aimé MODESTE DOUNTIO pour tous les conseils et soutiens multiformes qu'ils ne cessent de m'offrir.

· Mes frères Boris, Vital et Vanneck , mes soeurs Marie Laure et Cynthia , pour tout leur soutien et le sens de l'écoute qu'ils ont toujours sû développer à mon égard.

· Tous mes camarades de promotion, et mes voisins de cité avec qui j'ai toujours passé d'agréables moments.

· Enfin, je remercie tous ceux qui ont contribué de près ou de loin pour la réalisation de ce travail, tous ceux qui m'ont accompagné et soutenu et que j'ai pas cité.

iii

Résumé

Composés d'appareils fortement limités en ressources (puissance de calcul, mémoire et énergie disponible) et qui communiquent par voie hertzienne, les réseaux de capteurs sans fil composent avec leurs faibles capacités pour déployer une architecture de communication de manière autonome, collecter des données sur leur environnement et les faire remonter jusqu'à l'utilisa-teur. Des « transports intelligents » à la surveillance du taux de pollution environnemental, en passant par la détection d'incendies ou encore l'« internet des objets », ces réseaux sont aujourd'hui utilisés dans une multitude d'applications. Certaines d'entre elles, de nature médicale ou militaire par exemple, ont de fortes exigences en matière de sécurité. Dans les RCFs, la sécurité et la conservation d'énergie sont deux aspects importants et nécessaires à considérer. Particulièrement, la sécurité permet de s'assurer qu'un tel réseau ne sera pas sujet des attaques qui concernent la lecture, la modification et la destruction des informations tandis la conservation de l'énergie permet de prolonger le cycle de vie du réseau tant il est vrai que l'énergie des noeuds capteurs est extrêmement limitée, non rechargeable et non remplaçable.

Les travaux de ce mémoire se concentrent sur le problème du géocasting. le géocasting ou le multi-géocasting dans un RCSF est la livraison des paquets de la source à tous les noeuds situés dans une ou plusieurs zones géographiques. L'objectif du protocole de géocasting est la garantie de livraison et le moindre coût de transmission. De nombreux protocoles de géocasting ont été proposés dans la littérature. Mais ces protocoles s'appliquent sur des capteurs déployés sur une surface plane, or l'espace de déploiement peut présenter des irrégularités. Ainsi, il est nécessaire de concevoir des protocoles de géocasting prenant en compte ces irrégularités. Nous considérons une architecture virtuelle de réseau de capteurs anonymes en dimension 3 (3-D), centré sur une station de base (noeud sink). Dans un premier temps, nous proposons un algorithme de géocasting avec garantie de livraison et avec une surcharge de réseau moindre que ceux des protocoles existants. Par la suite, nous intégrons la sécurité et la conservation d'énergie. En effet, nous avons proposé un protocole efficace et sécurisé de géocasting dans un RCSF déployé dans l'espace, avec garantie de livraison des paquets de la source vers tous les noeuds situés dans une ou plusieurs régions géocast.

Mots clés : Géocasting, Multi-géocasting, Réseaux de Capteurs Sans Fil, Énergie, Par-titionnement, Partitionnement hiérarchique, Architecture virtuelle, Conservation de l'énergie, Sécurité, 3D, Simulation.

iv

Abstract

Wireless sensor networks are made of small devices with low resources (low computing power, little memory and little energy available), communicating through electromagnetic transmissions. In spite of these limitations, sensors are able to self-deploy and to auto-organize into a network collecting, gathering and forwarding data about their environment to the user. Today those networks are used for many purposes : «intelligent transportation», monitoring pollution level in the environment, detecting fires, or the «Internet of things» are some example applications involving sensors. Some of them, such as applications from medical or military domains, have strong security requirements. In WSNs, security and economy of energy are two important and necessary aspects to consider. Particularly, security helps to ensure that such a network is not subject to attacks that involve reading, modification or destruction of information while economy of energy prolong the network life as the energy supply for sensor nodes is usually extremely limited, non-rechargeable and non-replaceable.

In this work, we are interested in the problem of geocasting. Geocasting or Multi-Geocasting in wireless sensor network is the delivery of packets from a source (or sink) to all the nodes located in one or several geographic areas. The objectives of a geocasting (multi-geocasting) protocol are the guarantee of message delivery and low transmission cost. The existing protocols which guarantee delivery run on network in which each node has an ID beforehand. They either are valid only in dense networks or must derive a planar graph from the network topology. But protocols with sensors in the space has not yet been well defined. Hence the nodes may be adapted in order to carry out huge operations to make the network planar. Firstly, we consider a 3-D virtual sensors anonymous network architecture and derive geocast and multi-geocast algorithms that guarantee delivery and that need less overhead with respect to the existing protocols. They are both suitable for networks with irregular distributions with gaps or obstacles and dense networks. Then, we add security and energy-efficient issues. Effectively, we propose an energy-efficient and secure geocast algorithm for wireless sensor networks spread in the space, with guaranteed delivery of packets from the sink to all nodes located in several geocast regions by consider à virtual architecture in 3D.

Keywords : Geocast, Multi-geocast, Wireless Sensor Networks, Clustering, Hierarchical Clustering, Virtual architecture, Energy Efficiency, Security, simulation, Energy.

v

Table des matières

Dédicaces i

Remerciements ii

Résumé iii

Abstract iv

Table des figures viii

Liste des tableaux x

Liste des abréviations et acronymes xi

Introduction 1

Introduction générale 1

Contexte d'étude 1

Objectifs 1

Problématique 2

Organisation du travail 2

1 Généralités sur les Réseaux de Capteur Sans Fil 3

1.1 Introduction 3

1.2 Définition et architecture d'un capteur 4

1.3 Caractéristiques et Contraintes des RCSFs 6

1.3.1 Caractéristiques liées aux noeuds capteurs 6

1.3.2 Caractéristiques liées au RCSF 7

1.3.3 Contraintes 7

1.4 Architecture d'un RCSF 8

1.5 Les enjeux fondamentaux d'un RCSF 9

1.6 Applications des Réseaux de capteurs Sans Fil 10

1.7 Conclusion 11

2 Les Protocoles de Clustering dans les Réseaux de Capteurs Sans Fil 13

2.1 Introduction 13

vi

TABLE DES MATIÈRES

	2.2 2.3 2.4	Principe du Clustering dans les RCSF Partitionnement Centré sur le noeud 2.3.1 Algorithme de clustérisation de Basagni : DCA, DMAC et GDMAC . Partitionnement centré sur le Cluster		14 15 15 17
	2.4.1 Partitionnement en Clique : Algorithme de Sun et al. 18
	2.4.2 Partitionnement pour un contrôle hiérarchique : Algorithme de Banerjee
	et al. 23
	2.4.3 Architecture virtuelle d'un réseau de capteurs : Algorithme de clustéri-
	sation de A. Wadaa et al. 25
	2.4.4 partitionnement en 3D	27
2.5	Conclusion	35		3
Sécurité dans les Réseaux de Capteurs Sans Fil	36
3.1	Introduction	36
3.2	Principes d'attaques et d'attaquants	37
3.3	Politiques de sécurité dans les RCSFs	38
3.4	Taxonomie des attaques	38
	3.4.1 Attaques passives	39
	3.4.2 Attaques actives	39
	3.4.3 Attaques physiques	42
3.5	Mécanismes de sécurité	42
	3.5.1 Le partitionnement de données	42
	3.5.2 La cryptographie	43
	3.5.3 Détection d'intrusions	44
3.6	Conclusion	44		4
Protocoles de Geocasting dans les réseaux de capteurs sans fil	45
4.1	Introduction	45
4.2	Algorithmes de géocasting sans garantie de livraison. 46
	4.2.1 Algorithme de KO-VAIDYA	46
	4.2.2 Les protocoles LBM,VDBG,GeoGRID et GeoTORA	47
4.3	Algorithme de géocasting avec garantie de livraison	48
	4.3.1 Algorithme de Seada et Helmy	48
	4.3.2 Algorithme de Bomgni et al	49
	4.3.3 Protocole de Myoupo et al. 51
4.4	Conclusion	55

5 Notre contribution : Une approche de protocole de géocasting sécurisé dans

un RCSF déployé dans l'espace (en 3D) 56

5.1 Introduction 57

vii

TABLE DES MATIÈRES

5.2 Notre approche de sécurité 57

5.2.1 Au pré-déploiement 59

5.2.2 Phase de Construction 59

5.2.3 Phase de reconstruction 60

5.2.4 Phase de renouvellement 60

5.2.5 Phase de révocation 60

5.2.6 Insertion des nouveaux noeuds 61

5.3 Étape 1 : Formation sécurisée de la structure 61

5.3.1 Partitionnement sécurisé du réseau en cluster 61

5.3.2 Identification des noeuds 62

5.3.3 Découverte de voisinage 62

5.3.4 Construction et Définition de notre arbre couvrant le graphe 63

5.3.5 Routage sécurisé inter-cluster 63

5.3.6 Routage sécurisé intra-cluster 65

5.3.7 Élection du Cluster Head 65

5.4 Étape 2 : Protocole sécurisé de géocasting 69

5.4.1 Geocasting avec plusieurs régions géocast 70

5.5 Analyse de la sécurité 71

5.6 Analyse de la consommation de l'énergie 71

5.7 Implémentation et Analyse des résultats 72

5.7.1 Les métriques 73

5.7.2 Nombre et la taille des clés stockées 73

5.7.3 Nombre de paquets échangés 74

5.7.4 Consommation d'énergie 75

5.8 Conclusion 77

6 Conclusion Générale 78

Conclusion générale 78

6.1 Bilan 78

6.2 Perspectives 79

Bibliographie 80

viii

Table des figures

1.1 Anatomie d'un capteur, [1] 4

1.2 Fonction d'un capteur, [2] 4

1.3 Exemple de capteur, [3] 5

1.4 Architecture d'un capteur [2] 6

1.5 Exemple d'un réseau de capteur sans fil [4] 8

2.1 Exemple de topologie basée sur des clusters 14

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

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

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

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

2.6 Formation de clusters par l'algorithme de Banerjee et al. 24

2.7 Architecture Virtuelle 26

2.8 Système de coordonnées dynamiques 28

2.9 Formation des couronnes 29

2.10 Formation des couronnes pour k = 4 30

2.11 Étiquetage et parcours 30

2.12 Formation des sections horizontales 32

2.13 Les différents angles d'émission du noeud sink pour m = 8. 34

2.14 Formation des sections verticales 34

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

3.1 Stratégies de sécurité dans un RcSF 38

3.2 Types d'attaques actives 39

3.3 Technique de partitionnement des données 43

3.4 Principe de la cryptographie 43

4.1 succès/Echec de livraison de paquets lors de l'exécution du schéma à zone adaptée 47

4.2 Protocole de découverte de voisins 50
4.3 BS network cutting with Cp = 0.5 and Ca = 40°. Here, we take the second level

formation case. Broadcast step 53

ix

TABLE DES FIGURES

5.1	Réseau de capteurs déployé dans l'espace		57	5.2
petit aperçu de la structure de notre arbre	63		5.3
Routage dans un réseau dense	64		5.4
Nombre de paquets échangés en absence d'intrus	75		5.5
Nombre de paquets échangés en présence d'intrus	75		5.6
Évolution de l'énergie des capteurs	76		5.7
Évolution de l'énergie lors du déroulement de deux protocoles avec 400 capteurs	76

x

Liste des tableaux

2.1	Calcul des angles de transmissions horizontales pour m=4		33	2.2
Calcul des angles de transmissions horizontales pour m = 8.	33		5.1
Taille des clés ECC et de leurs paramètres de calcul	74		5.2
Le nombre et la taille des clés stockées dans notre méthode	74

Liste des abréviations et acronymes

Abréviations

BS CH

Description
Base station
Cluster Head

DSN

DCA

DMAC

GDMAC

IP

RCSF

ECC

GPS

MAC

MANET

NS-2

LBM

WSNs

VDBG

ASP

ACK

CDMA

CSMA/CA

CTS

FDMA

NAV

RTS

TDMA

TRAMA

LMC

TESLA

WATS

ADC

DPR

Diviser Pour Régner

xi

Distributed Sensor Network

Distributed Clustering Algorithm

Distributed and Mobility-Adaptive Clustering

Generalized Distributed and Mobility-Adaptive Clustering Internet Protocol

Réseau de Capteur Sans Fil

Elliptic Curve Cryptography

Global Positioning System

Media Access Control

Mobile Ad Hoc Network

Network Simulator 2^nd version

Location Based Multicast

Wireless Sensors Networks

Voronoi Diagram Based Geocasting

Acknowledge System Positioning

Acknowlegment

Code DivisionMultiple Access

Carrier Sense Multiple Access/Collision Avoidance

Clear ToSend

Frequency Divisio nMultiple Access

Network Allocation Vector

Request To Send

Time Division Multiple Access

Traffic-adaptive medium access protocol

Local Maximum Clique.

Timed Efficient Stream Loss-tolerance Authentification

Wide Area Tracking System.

Analog to Digital Converter

1

Introduction Générale

Contexte d'étude

Les progrès observés dans les domaines de la micro-électronique, de la micro-mécanique et dans le perfectionnement des techniques de communication ont permis aux chercheurs et industriels de développer et de produire à moindre coûts des composants électroniques de tailles très réduites. Ces micro-composants sont utilisés dans la confection d'appareils permettant la surveillance de zones géographiquement étendues, l'acquisition, le traitement et la transmission de données extrêmement sensibles. De ce fait, s'est développé un nouveau type de réseau appelé réseau de capteurs sans fil, dans lequel des capteurs communiquent entre eux en utilisant des connexions non filaires. Les capteurs sont des petits dispositifs dont la fonction principale est de collecter les informations concernant l'environnement dans lequel ils sont déployés et de les acheminer vers d'autres capteurs ou vers une station de base (encore dénommée noeud sink). Les réseaux de capteurs sans fil sont souvent caractérisés par un déploiement dense et à grande échelle dans des environnements limités en terme de ressources. Les limites imposées sont d'une part énergétiques car ils sont généralement alimentés par des piles. Recharger les batteries dans un réseau de capteurs est parfois impossible en raison de l'emplacement des noeuds, mais le plus souvent pour la simple raison que cette opération est pratiquement ou économiquement infaisable. Il est donc largement reconnu que la limitation énergétique est une question incontournable dans la conception des réseaux de capteurs sans fil en raison des contraintes strictes qu'elle impose sur sa conception.

Motivation et Objectifs

Dans le cadre de notre travail, nous allons supposer que le réseau n'est pas mobile; autrement dit, les capteurs ne peuvent pas se déplacer dans la zone de perception. Notre objectif est de définir une approche de protocole sécurisé de géocasting dans un réseau de capteurs sans fil déployé dans l'espace. Ce protocole sera économe en énergie, diminuera la charge de travail des CHs et évitera de surestimer la mémoire des capteurs du réseau. Ainsi, la stratégie adoptée dans cette approche repose sur une technique de partitionnement en 3D permettant de minimiser la consommation de l'énergie durant le processus de livraison des paquets. Les différents challenges auxquels nous allons être confrontés sont multiples. Il sera question d'abord de maitriser les

2

Introduction générale

enjeux,les caractéristiques et les problématiques des RCSFs; ensuite, présenter les différents protocoles de clustering et de géocasting qui ont retenu notre a attention dans la littérature; et enfin, nous allons présenter une approche de protocole sécurisé de geocasting en dimension 3.

Problématique

La caractéristique principale d'un réseau de capteurs sans fil est qu'un noeud peut solliciter d'autres noeuds comme lui dans son voisinage pour retransmettre des paquets de données dont le destinataire serait hors de sa propre portée. les paquets envoyés par une station peuvent ne pas être reçu par tous les noeuds situés dans une zone précise. En effet, la station de base peut être amenée à envoyer des instructions aux capteurs situés dans une région bien précise. Dans ce cas, il s'agit de résoudre efficacement le problème de multicast géographique bien connu sous le nom "géocasting". Le géocasting est un procédé qui consiste à envoyer des données à une poignée de capteurs situés dans une région d'intérêt (région géographique) appelée région géocast. En outre, Une des contraintes principales dans les réseaux de capteurs sans fil est la protection des communications. les réseaux de capteurs sont vulnérables à différents types d'attaques qui peuvent être lancées de façon relativement simple. En particulier, la nature des communications sans fil facilite l'écoute clandestine permettant ainsi une analyse facile du trafic réseau. Il est donc d'un grand intérêt pour tous les protocoles destinés à fonctionner dans les réseaux de capteurs sans fil critiques d'intégrer des mécanismes de sécurité efficace et peu couteux. De plus, la majorité des protocoles de geocasting existants ne s'appliquent que dans le cas où les capteurs sont déployés dans le plan. Or la réalité voudrait que ces protocoles puissent 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, tout en tenant compte de la consommation d'énergie.

Organisation du travail

Ce mémoire est organisé de la façon suivante: dans le chapitre 1 nous faisons une généralité sur les réseaux de capteurs en insistant sur l'architecture physique des capteurs, les caractéristiques, les contraintes et les domaines d'application des RCSFs. Le chapitre 2 sera consacré à la présentation de quelques protocoles de partitionnement des RCSFs. Le Chapitre 3 quant à lui sera réservé à la sécurité dans les RCSFs. Au chapitre 4, nous présentons quelques protocoles de géocasting avec garantie de livraison qui ont déjà été réalisés et sur lesquels nous allons nous baser pour établir le notre. Le chapitre 5 quant à lui est réservé à notre contribution et aux résultats des simulations que nous avons effectués. Une conclusion générale sera dégagée à la lumière de tout ce qui précède ainsi que quelques perspectives.

3

Chapitre 1

Généralités sur les Réseaux de Capteur

Sans Fil

Sommaire				1.1 1.2 1.3
Introduction Définition et architecture d'un capteur Caractéristiques et Contraintes des RCSFs		3 4 6
1.3.1 Caractéristiques liées aux noeuds capteurs		6
1.3.2 Caractéristiques liées au RCSF		7
1.3.3 Contraintes		7	1.4
Architecture d'un RCSF		8	1.5
Les enjeux fondamentaux d'un RCSF		9	1.6
Applications des Réseaux de capteurs Sans Fil		10	1.7
Conclusion		11

1.1 Introduction

Les progrès récents dans les domaines de micro-électronique et des communications sans fil ont abouti au développement de très petits capteurs dont l'anatomie est présentée à la figure1.1. Leur remarquable essor est dû à leur taille de plus en plus réduite, leurs prix de plus en plus faible ainsi que leur support de communication sans fils attrayant peu encombrant mais également peu de ressources. Ces capteurs peuvent être déployés n'importe où pour assurer des fonctions de surveillance ou autres. Le réseau ainsi établi est appelé Réseau de Capteurs Sans Fils (RCSF ou Wireless Sensor Network), composé d'un nombre souvent très important de noeuds qui sont, soit posés à un endroit précis, soit dispersés aléatoirement (souvent déployés par voie aérienne à l'aide d'avions ou hélicoptères). Une fois déployés, les noeuds coopèrent entre eux d'une manière autonome afin de collecter et de transmettre des données vers une station de base dans le but de surveiller et/ou de contrôler un phénomène donné.

CHAPITRE 1. GÉNÉRALITÉS SUR LES RÉSEAUX DE CAPTEUR SANS FIL

1.2 Définition et architecture d'un capteur

FIGURE 1.1: Anatomie d'un capteur, [1]

FIGURE 1.2: Fonction d'un capteur, [2]

4

Un capteur peut être définie comme un petit appareil électronique qui convertit une grandeur physique reçu précédemment en une quantité numérique sur laquelle des traitements peuvent être effectués [1]. Ces capteurs, non autonomes doivent donc être connectés à un appareil capable d'en interpréter la mesure, puis, selon l'usage souhaité permettre l'utilisation. Chaque capteur assure trois fonctions principales : la collecte, le traitement et la communication de l'information vers un ou plusieurs points de collecte appelés station de base (figure 1.2); et comporte cinq grandes caractéristiques : une faible capacité de stockage, une source autonome d'énergie limitée, une faible puissance de calcul, un rayon de transmission et un rayon de perception. Le rayon de transmission d'un capteur définit la circonférence dans laquelle doit se trouver un autre capteur pour que ceux-ci puissent communiquer directement, tandis que le rayon de perception définit la circonférence maximale dans laquelle un capteur peut collecter ou capter des informations [3]. Suivant le type d'application, il existe plusieurs types de capteurs : les capteurs de température, d'humidité, de pression, etc. malgré cette diversité apparente, ils restent dotés d'une architecture matérielle similaire. Un capteur est doté principalement de quatre unités[5, 6] tel que représenté à la figure 1.4 : unité de captage ou d'acquisition (encore appelée unité de capture), unité de traitement, unité de communication et unité d'énergie. Des composants additionnels peuvent être ajoutés selon le domaine d'application, comme par exemple un système de localisation de l'environnement tel qu'un GPS, d'un système de mobilité mais

5

CHAPITRE 1. GÉNÉRALITÉS SUR LES RÉSEAUX DE CAPTEUR SANS FIL

aussi parfois d'un générateur d'énergie (exemple : cellule solaire). L'unité de Captage ou

FIGURE 1.3: Exemple de capteur, [3]

d'acquisition ("Sensing unit") est responsable de la collecte des données. Elle est composée de deux dispositifs : un dispositif de capture physique qui prélève l'information de l'environnement local(dispositif de transformation des données interceptées en signaux analogiques) et un convertisseur analogique/numérique appelé ADC ( dispositif de conversion de ces signaux analogiques en signaux numériques compréhensibles par l'unité de traitement).

L'unité de traitement ("Processing unit")quant à lui, est l'unité principale du capteur. Généralement Composée d'un microprocesseur et d'une mémoire de stockage (processeur couplé à une mémoire vive), il a pour rôle de contrôler le bon fonctionnement des autres unités en effectuant des traitements sur les données captées en exécutant les commandes et les instructions contenues dans les protocoles de communication pré-chargés sur le capteur. Elle est équipée de deux interfaces : i) interface par unité d'acquisition et ii) interface par unité de communication. Sur certains capteurs elle peut embarquer un système d'exploitation pour faire fonctionner le capteur. Elle peut aussi être couplée à une unité de stockage, qui servira par exemple à y enregistrer les informations transmises par l'unité de capture.

L'unité de communication ("Transceiver unit") est responsable de toutes les émissions et réceptions de données via un support de communication radio. elle met en application les procédures nécessaires pour convertir les bits à transmettre dans des ondes radio fréquences pour qu'ils soient récupérés correctement à l'autre extrémité. De plus, le RCSF est relié en réseau grace à cette unité.

L'unité d'énergie ("Power unit") est responsable de gérer l'alimentation en énergie de tous les composants du noeud capteur. Elle est généralement intégrée au capteur et est irremplaçable. l'énergie est la ressource la plus précieuse d'un capteur, car elle influe directement sur sa durée de vie. .

Système de localisation de l'environnement ("Power unit") : les tâches de détection et les techniques de routage ont besoin de connaitre souvent la localisation géographique d'un noeud. Ainsi, un noeud peut être équipé d'un système de localisation géographique. Ce système peut se composer d'un module de GPS pour un noeud de haut niveau ou bien d'un module de software qui implémente des algorithmes de localisation qui fournissent les informations sur l'emplacement du noeud par des calculs distribués.

Système de mobilité : la mobilité est parfois nécessaire pour permettre à un noeud de se déplacer pour accomplir ses tâches. Le support de mobilité exige des ressources énergétiques étendues qui devraient être fourni efficacement. Le système de mobilité peut, également, opérer

6

CHAPITRE 1. GÉNÉRALITÉS SUR LES RÉSEAUX DE CAPTEUR SANS FIL

dans l'interaction étroite avec l'unité de détection et le processeur pour contrôler les mouvements du noeud.

FIGURE 1.4: Architecture d'un capteur [2]

1.3 Caractéristiques et Contraintes des RCSFs

Les réseaux de capteurs présentent des caractéristiques intrinsèques au niveau des noeuds capteurs (énergie, portée de transmission et puissance de stockage et de traitement...) et au niveau du réseau formé par ces noeuds capteurs (Bande passante, déploiement, type de réseau et topologie dynamique).

1.3.1 Caractéristiques liées aux noeuds capteurs

Les noeuds capteurs s'appuient sur certaines caractéristiques pour transmettre les données du monde physique sur lequel ils sont déployés :

L'énergie : Elle représente une contrainte dans les réseaux de capteurs sans fil : Chaque noeud capteur fonctionne avec une batterie, généralement, non rechargeable avec une capacité limitée étant donné sa petite taille. Dans la majorité des cas, ces noeuds capteurs sont déployés dans des zones hostiles ou difficiles d'accès et il est très peu probable qu'ils soient récupérables. Aussi, vu leur nombre très grand (des milliers) on ne peut pas s'occuper de chaque noeud capteur un à un.

La portée de transmission : Elle est limitée par la capacité de rayonnement des antennes utilisées et la puissance du signal mises en jeu. Par exemple, la communication entre deux noeuds capteurs ne peut avoir lieu que si la distance qui les sépare n'est pas trop importante (quelques dizaines de mètres en pratique).

La puissance de stockage et de traitement : Elle est relativement faible. Par exemple, les noeuds capteurs de type "mote" sont composés d'un microcontrôleur 8 bits 4 MHz, 40 Ko de mémoire et d'une radio de débit environ 10 kbps. Cela reste vrai même pour les noeuds de moyenne gamme, comme les "UCLA/ROCKWELL'S WINS", qui ont un processeur StrongARM

7

CHAPITRE 1. GÉNÉRALITÉS SUR LES RÉSEAUX DE CAPTEUR SANS FIL

1100 avec une mémoire flash de 1 Mo, une mémoire RAM de 128 Ko et une radio dont le débit est 100 Kbps

1.3.2 Caractéristiques liées au RCSF

Un RCSF possède plusieurs caractéristiques parmi lesquelles [5] :

· les ressources limitées des capteurs en calcul, en mémoire et en énergie;

· la durée de vie limitée et l'auto-configuration des noeuds capteurs;

· le mode de communication direct ou en multi-sauts et la densité importante des capteurs qui peuvent atteindre des dizaines de millions pour certaines applications;

· la possibilité de découper le réseau en clusters et d'utiliser les capteurs comme calculateurs ou des agrégateurs;

· la coopération entre les noeuds capteurs pour les taches complexes et l'absence d'un identifiant global pour les capteurs;

· deux modes de fonctionnement : « Un à plusieurs » où la station de base diffuse des informations aux différents capteurs; et « Plusieurs à un » où les noeuds capteurs diffusent des informations à la station de base;

· les types de communication : unicast, broadcast, multicast, local gossip, convergeCast.

1.3.3 Contraintes

les principaux facteurs qui influencent la conception d'un RCSF sont : passage à l'échelle, la tolérance aux pannes, les contraintes matérielles, les coûts de production, la topologie du réseau, la consommation d'énergie te le média de transmission [7].

Passage à l'échelle (Scalability) : le bon fonctionnement d'un réseau est conditionné par la définition d'un schéma de déploiement efficace respectant la propriété de haute densité. Le passage à l'échelle est défini comme la possibilité de déployer un grand nombre de noeuds sur une petite surface. Il est donné par la valeur calculant les distances entre les noeuds. Il est utilisé pour connaitre exactement la densité, le rayon d'émission et le nombre moyen de voisins d'un noeud donné.

Tolérance aux pannes : le fonctionnement d'un ou de plusieurs capteurs peut être interrompu au cours du cycle de vie du réseau. Les causes de ces défaillances sont multiples : i) manque en ressources énergétiques, ii) dégâts matériels, iii) interférences environnementales, iv) compromission des noeuds . . . etc. Ces pannes ne doivent pas affecter le fonctionnement global du réseau. La tolérance aux pannes se définie alors comme la capacité du réseau à continuer à fonctionner normalement sans interruption même après le dysfonctionnement d'un ou de plusieurs de ses noeuds capteurs.

Environnement de déploiement : dans la majorité des applications, les noeuds capteurs sont déployés dans des zones distantes, hostiles et sans aucune surveillance ni intervention

8

CHAPITRE 1. GÉNÉRALITÉS SUR LES RÉSEAUX DE CAPTEUR SANS FIL

humaine. Les capteurs doivent être conçus pour résister aux différentes conditions climatiques telles que la chaleur, l'humidité, le froid, la pression . . . etc.

Topologie du réseau : l'ajout de nouveaux capteurs sur la zone de captage ou la défection d'un ou de plusieurs noeuds capteurs du réseau peut causer une instabilité de la topologie du réseau.

Contraintes matérielles : la consommation stricte et mesurée de l'énergie, un coût faible, le fonctionnement autonome des capteurs, l'adaptation aux conditions de déploiement, une portée radio limité, un faible débit... etc.

Economie d'énergie : la batterie est considérée comme l'unique alimentation en ressources énergétiques des capteurs. L'énergie d'un capteur est consommée par toutes ses unités.

1.4 Architecture d'un RCSF

Un RCSF est un type particulier de réseaux Ad Hoc[5] composé d'un grand nombre de noeuds qui sont généralement des capteurs de petite taille capable d'agir de façon autonome. La figure1.5 présente un exemple classique de réseau de capteurs sans fil: les capteurs sont déployés de manière aléatoire dans une zone à surveiller, et un puits ou/et collecteur situé à l'extrémité de cette zone, est chargé de récupérer les données collectées par les capteurs. Lorsqu'un capteur détecte un événement pertinent, un message d'alerte est envoyé au puits/collecteur par le biais d'une communication multi-sauts. Selon [8] , il existe deux types d'architecture pour les RCSFs :

FIGURE 1.5: Exemple d'un réseau de capteur sans fil [4] Les RCSF plats et les RCSF hiérarchiques.

Architecture de communication

Après le déploiement des noeuds capteurs sur une certaine zone de captage, ceux-ci commencent par la découverte de leurs voisins afin de construire la topologie de communication. Ainsi, ils deviennent capables d'accomplir les tâches qui leur sont affectées. Selon une communication multi-sauts, les capteurs sont chargés de collecter des données, les router vers un

9

CHAPITRE 1. GÉNÉRALITÉS SUR LES RÉSEAUX DE CAPTEUR SANS FIL

noeud particulier appelé noeud puits. Ce dernier analyse ces données et transmet à son tour l'information collectée à l'utilisateur via internet ou bien satellite.

Mécanisme d'accès au canal lors des communications sans fil

les RCSF n'utilisent aucun câble physique pour communiquer entre eux ou avec la station de base : toutes les transmissions sont effectuées par voie hertzienne. Un défi important dans ce type de réseau est la conservation d'énergie et la gestion des collisions dues à un transfert de données simultané entre deux noeuds sur le même support. Les protocoles de contrôle d'accès au support (MAC)ont été développés essentiellement pour essayer d'éviter ce genre de collisions en aidant les noeuds à décider quand et comment ils peuvent accéder au support. Le rôle de la couche MAC peut être simulé par celui de la régulation de la circulation dans les grandes routes. Plusieurs véhicules traversent la même route mais des règles sont nécessaires pour éviter les accidents [9]. Il existe iverses techniques d'accès au médium dans les RCSF : TDMA [10], FDMA [11], CDMA et CSMA/CA. [12] [13]

Architecture protocolaire

Dans le but d'établir efficacement un RCSF, une architecture en couches est adoptée afin d'améliorer la robustesse du réseau. Une pile protocolaire de cinq couches (application, transport, réseau, liaison de données et physique) est donc utilisée par les noeuds du réseau. Cette pile possède trois plans (niveaux) de gestion : le plan de gestion des tâches qui permet de bien affecter les tâches aux noeuds capteurs, le plan de gestion de mobilité qui permet de garder une image sur la localisation des noeuds pendant la phase de routage, et le plan de gestion de l'énergie qui permet de conserver le maximum d'énergie.

1.5 Les enjeux fondamentaux d'un RCSF

Les enjeux des réseaux de capteurs que nous présentons ici sont fondamentaux pour les dits réseaux, il s'agit de :

Le Routage

L'acheminement des données entre le noeud collecteur et la station de base via un réseau de connexion est une tâche difficile qui nécessite un travail de collaboration de l'ensemble des noeuds capteurs participant à ce transfert. Pour un acheminement optimal, les fonctions de routage doivent tenir compte des ressources limitées des noeuds notamment de leur niveau d'énergie. On distingue deux modes de transmission d'informations dans les RCSFs [7] :i) Envoi direct (en un seul saut) : c'est-à-dire que le noeud émetteur peut atteindre directement la BS. Cette transmission est possible si la BS est directement accessible par le noeud émetteur; on parle dans ce cas de Routage à topologie plate; ii) Envoi en multi-sauts : dans le cas où la BS n'est pas accessible par le noeud émetteur, on utilise la méthode d'envoi par noeuds intermédiaires. Ceci permet de créer des routes entre le noeud émetteur et sa destination. On parle dans ce cas

10

CHAPITRE 1. GÉNÉRALITÉS SUR LES RÉSEAUX DE CAPTEUR SANS FIL

de Routage Hiérarchique. Suivant la méthode de création et de maintenance des routes lors de l'acheminement des paquets, les protocoles de routages des RCSF peuvent être classés en 03 catégories [14] :

les protocoles de routages Proactifs : ici, les routes sont calculées à l'avance. Chaque noeud met à jour plusieurs tables de routage par échange de paquet de contrôle entre voisins. Son inconvénient est la table de routage des informations qui ne seront pas forcement utilisées ce qui est une perte en espace pour les capteurs.

les protocoles de routages Réactifs : ici, les routes ne sont calculées que sur demande. Si un noeud veut transférer une information à un autre noeud, il doit tout d'abord déterminer la route avant d'effectuer le transfert. Son inconvénient est le temps mis pour déterminer la route des paquets ce qui peut entrainer une dégradation des performances des applications.

les protocoles de routages Hybrides : qui combine les 2 premiers afin de profiter des avantages de chacun.

Le Protocole

Un protocole assure la liaison des équipements par la définition de moyens physiques et procéduraux garantissant l'interconnexion entre eux, en procédant à la définition et le contrôle des flux d'informations échangées. Dans les RCSFs, plusieurs protocoles sont déployés aux différents niveaux de la couche protocolaire pour assurer la communication entre les équipements du réseau et la sécurité des informations échangées. On cite les protocoles TRAMA, S-MAC pour la couche liaison de données, TEEN, APTEEN, LEACH pour la couche réseau ou Pike, LEAP comme protocoles cryptographiques assurant la sécurité des données.

La sécurité

Comme les capteurs sont souvent déployés dans des zones publiques, ils doivent être capables de maintenir privées les informations qu'ils recueillent. Par conséquent, la sécurité des données dans les RCSFs devient encore plus significative. Toute politique de sécurité doit prendre en considération toutes les contraintes des capteurs.

Le clustering

La clusterisation est une technique qui consiste à diviser le réseau en groupe de noeuds également appelés clusters ou grappes. Chaque cluster est dirigé par un chef (Cluster Head) désigné soit par élection par les noeuds de son cluster, soit choisi et imposé par la station de base [15, 16]. L'objectif de cette technique est de présenter le meilleur moyen de répartition et de conservation de la consommation d'énergie par un traitement et une transmission contrôlée des données récoltées. Nous détaillerons cette partie dans le chapitre suivant.

1.6 Applications des Réseaux de capteurs Sans Fil

Les RCSFs ont un champ d'application vaste et diversifié (voir figure ??). Ceci est rendu possible par leur cout faible, leur taille réduite, le support de communication sans fil utilisé et la large gamme des types de capteurs disponibles. Parmi elles, nous citons [5] :

11

CHAPITRE 1. GÉNÉRALITÉS SUR LES RÉSEAUX DE CAPTEUR SANS FIL

Domaine militaire : les RCSFs sont le résultat de la recherche militaire. Ils sont utilisés dans la surveillance des champs de bataille pour connaitre exactement la position, le nombre, l'armement (chimique, biologique, nucléaire...etc), l'identité et le mouvement des soldats et ainsi empêcher leur déploiement sur des zones à risques.

Domaine civil : Apparus dans plusieurs contextes notamment dans la surveillance des habitations (concept de bâtiments intelligents), des infrastructures, des installations et des zones à risques. Leur utilisation permet de réduire considérablement le budget consacré à la sécurité des humains tout en garantissant des résultats sûrs et fiables.

Domaine agricole et environnemental : Les RCSFs sont très utiles dans la protection de l'environnement. Ils peuvent être utilisés pour la détection des feux de forets, des inondations, surveillance des volcans, le déplacement des animaux.. . etc. Dans le domaine agricole, on cite le déploiement des capteurs sur un champ agricole afin d'identifier les zones sèches et permettre leur irrigation à temps.

Domaine industriel : Le suivi des chaines de production dans une usine, détection des dysfonctionnements de machines, suivi du mouvement des marchandises dans les entrepôts de données, suivi du courrier, des colis expédiés.. . etc. sont, entre autres, des exemples concrets d'application des RcSF dans le domaine industriel.

Domaine de la santé : Un moyen très efficace pour le domaine médical et le suivi temps-réel de l'état des patients, notamment ceux atteints de maladies chroniques, ils permettent de collecter des informations physiologiques de meilleure qualité [17][18] pouvant être stockées pour une longue durée ou alors détecter des comportements anormaux chez des personnes âgées ou handicapées comme les chutes, les chocs, les cris. . . etc.

Applications domestiques : Les RCSFs sont l'un des moyens les plus importants dans la lutte contre le réchauffement climatique. En effet, l'intégration des capteurs dans des murs ou sur les plafonds des maisons permet d'économiser un maximum d'énergie en gérant au mieux l'éclairage et le chauffage en fonction de la localisation des personnes. Également, les capteurs peuvent être embarqués dans des appareils électroménagers et d'interagir entre eux et avec un réseau externe pour assurer un meilleur contrôle à distance de ces appareils par leur propriétaire [19].

La liste des applications des RCSFs est non exhaustive. Ils peuvent être utiles dans d'autres domaines comme la sécurité alimentaire, les télécommunications, la robotique ou dans des applications traditionnelles (automobile, aéronautiques, applications commerciales. . . etc.).

1.7 Conclusion

Le but de ce chapitre était de présenter de manière globale la notion de réseaux de capteurs sans fil. Pour y parvenir nous avons commencé par présenter dans la première section l'architecture d'un capteur, élément principal d'un RCSF. Par la suite, nous avons présenté les différentes caractéristiques des RCSFs ainsi que les contraintes liées à la conception de ces derniers. Enfin,

12

CHAPITRE 1. GÉNÉRALITÉS SUR LES RÉSEAUX DE CAPTEUR SANS FIL

nous avons présenté quelques domaines de leur utilisation. A la lumière de ce qui précède, nous pouvons dire que Les RCSFs possèdent des caractéristiques particulières qui les différencient des autres types de réseaux sans fil. Ces spécificités telles que la consommation d'énergie réduite, la scalabilité ou le routage incitent le besoin de concevoir de nouveaux protocoles d'accès au support, de routage, de sécurité qui s'adapteront aux caractéristiques des RCSFs. Après avoir passé en revue les différentes notions qui gravitent autour des RCSfs, il devient primordial de présenter les différents protocoles de routage géographiques dans les RCSFs. Mais avant, nous allons dans le chapitre suivant présenter les différents Protocoles de clustering qui sont à la base de ces protocoles de routage.

13

Chapitre 2

Les Protocoles de Clustering dans les

Réseaux de Capteurs Sans Fil

Sommaire

2.1 Introduction 13

2.2 Principe du Clustering dans les RCSF 14

2.3 Partitionnement Centré sur le noeud 15

2.3.1 Algorithme de clustérisation de Basagni : DCA, DMAC et GDMAC . 15

2.4 Partitionnement centré sur le Cluster 17

2.4.1 Partitionnement en Clique : Algorithme de Sun et al. 18

2.4.2 Partitionnement pour un contrôle hiérarchique : Algorithme de Ba-

nerjee et al. 23
2.4.3 Architecture virtuelle d'un réseau de capteurs : Algorithme de clus-

térisation de A. Wadaa et al. 25

2.4.4 partitionnement en 3D 27

2.5 Conclusion 35

2.1 Introduction

Les auteurs en [20, 21] définissent le clustering comme une méthode utilisée pour partition-ner un réseau de grande taille en un certain nombre de groupes virtuels ou logiques appelés "clusters", plus homogènes selon une métrique spécifique ou une combinaison de paramètres, pour former une topologie virtuelle. Le clustering permet d'optimiser les fonctions et les services du réseau tel que le routage, la maintenance, la sécurité, etc. C'est une approche DPR qui est utilisée dans de nombreux domaines pour résoudre des problèmes qui sont globalement complexes. Si dans les groupes de noeuds formés, l'un des noeuds est élu comme chef alors on parle de cluster ou de clique. Dans le cas contraire, on parle de zone. Dans les différentes cliques formées, le chef de clique est responsable des différentes opérations qui se déroulent

14

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

dans la clique. Tous les protocoles de géocasting dans les RCSFs à multiples sauts débutent par une phase de clustering dans laquelle l'on transforme l RCSF à multiples sauts en plusieurs sous réseaux accessibles sans sauts. Dans l'optique d'alléger la présentation des différents protocoles de géocasting dans un RCSF à multiples sauts, nous allons présenter dans ce chapitre les différents algorithmes de partitionnement qu'ils utilisent.

2.2 Principe du Clustering dans les RCSF

La solution retenue le plus communément pour organiser un très grand RCSF est de regrouper les noeuds en clusters comme le montre la figure 2.1. Ce type d'organisation permet de réduire le nombre de noeuds participant à des communications sur de longues distances. De manière générale, le partitionnement d'un réseau s'effectue sur le principe suivant [22] : les noeuds sont divisés en clusters, et certains noeuds, nommés chef de cluster (ou clusterhead en anglais) sont responsables tant de la formation que de la maintenance des clusters. L'ensemble des clusterheads est appelé l'ensemble dominant. C'est le backbone du réseau. Dans les solutions existantes, le partitionnement est effectué en deux phases distinctes : la phase d'initia-lisation des clusters et la phase de maintenance des clusters. La première phase est accomplie en choisissant certains noeuds pour qu'ils agissent comme l'ensemble dominant du processus de partitionnement. Les clusters sont alors formés autour des clusterheads. Ceux qui ne sont pas clusterheads sont qualifiés de noeud ordinaire. Les algorithmes de partitionnement actuels diffèrent essentiellement sur l'heuristique utilisée pour choisir qui peut prétendre au statut de clusterhead.

FIGURE 2.1: Exemple de topologie basée sur des clusters

Il existe dans la littérature, 02 types de partitionnement : Partitionnement centré sur le noeud et le Partitionnement centré sur le cluster.

15

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

2.3 Partitionnement Centré sur le noeud

Ici, les clusters sont formés autour des CH. Plusieurs protocoles ont été proposés pour choisir le clusterhead dans les RCSFs. Dans les algorithmes dits à " plus petit identifiant ", chaque noeud se voit assigné un identifiant unique et le noeud avec le plus petit identifiant est élu CH. Un noeud qui peut entendre un ou plusieurs CHs est une " passerelle ", qui est généralement utilisée pour le routage d'informations entre les clusters. Sinon, il est un noeud ordinaire. Parmi les algorithmes de partitionnement centré sur le noeud, nous pouvons citer : l'approche de Gerla et Tsai [23], l'algorithme de clusterisation de Basagni (DCA, DMAC et GDMAC), l'algorithme de partitionnement sans unicité de poids de Idrissa Sow,... etc.

2.3.1 Algorithme de clustérisation de Basagni : DCA, DMAC et GDMAC

Bassagni propose en [24] un algorithme de clustering pour les RCSFs en considérant comme paramètre de clustérisation le poids relatif de chaque noeud. Compte tenu de la mobilité récurrente des noeuds, le paramètre du poids de chaque noeud est introduit pour choisir les noeuds chefs de clusters. A la fin de la procédure de clustérisation, les trois propriétés suivantes doivent être satisfaites : chaque noeud ordinaire a au moins un CH comme voisin; chaque noeud ordinaire est associé au CH de plus grand poids et deux CHs ne peuvent pas être voisins. Cet algorithme de clustérisation est divisé en deux sous étapes : l'étape d'initialisation des clusters et l'étape de maintenance des clusters. Les auteurs supposent également que durant l'exécution de l'algorithme, la topologie du réseau ne change pas; et qu'un message envoyé par un noeud est bien reçu après un temps fini (un seuil) par tous ses voisins; tout noeud connaît son poids, son identifiant et les identifiants et poids de tous ses voisins.

L'algorithme est exécuté par chaque noeud individuellement de telle façon qu'un noeud u décide de son propre rôle (clusterhead ou noeud ordinaire) en fonction seulement de la décision de ses voisins avec des poids plus forts que lui. Donc, initialement, seuls ces noeuds avec le poids le plus élevé du voisinage vont diffuser un message à leurs voisins directs, établissant qu'ils sont les clusterheads. Si aucun noeud avec un poids plus fort n'a envoyé de tel message, alors u va envoyer un message établissant son statut de clusterhead.

Choix du Cluster-Head (CH)

Le choix du CH est fonction du degré sortant de chaque noeud. Dans le cas où plusieurs noeuds ont le même degré on met en exergue le poids de chaque noeud. La procédure de choix du CH est la suivante : les noeuds de plus grand degré initient la procédure en envoyant des requêtes d'être CH à tous leurs voisins. De là, tout noeud dont le degré est supérieur à celui de ses voisins diffuse sa décision d'être chef de cluster. Si un noeud connait un de ses voisins de degré supérieur au sien, il ne peut plus être chef de cluster. Il adopte ce noeud là comme chef de cluster.

16

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

Choix des noeuds ordinaires

Cette étape est aussi basée sur la comparaison des degrés des autres noeuds. En effet, pour un noeud vi dont le degré est inférieur à celui de ses voisins, deux cas possibles se présentent : Si ce noeud vi est voisin d'un noeud CHi qui est chef de cluster, alors vi rejoint automatiquement le cluster dont le chef est CHi. Si le voisin de vi de plus haut degré appartient à un cluster, deux cas sont possibles : si un chef de cluster CHi est parmi ses voisins, alors il devient membre du cluster dont le chef est CHi ; sinon, il crée un nouveau cluster.

L'algorithme utilise deux types de messages : ch(v) utilisé par un noeud v pour mettre au courant ses voisins qu'il sera clusterhead, et join(v, u), avec lequel v communique à ses voisins qu'il va faire partie du cluster dont le clusterhead est u. la description de cet algorithme est la suivante:

Chaque noeud démarre l'exécution de l'algorithme en même temps, en utilisant une même procédure d'initialisation. Seuls les noeuds qui ont le poids le plus élevé par rapport à tous leurs voisins directs vont envoyer un message du type ch(noeuds avec les forts poids) pour dire qu'il veut être clusterhead. Tous les autres noeuds se contentent d'attendre de recevoir un tel message. A partir de là, on dispose de 2 procédures spécifiques dont l'exécution est déclenchée par les réceptions de message :

lors de la réception d'un message ch venant d'un voisin u, le noeud v vérifie d'abord s'il a déjà reçu de tous ses voisins z , tels que w, > w_u un message join(z, x) de type ch avec x un noeud quelconque du réseau. Dans le cas négatif, et si u est le noeud de plus fort poids dans le voisinage de v ayant envoyé un message ch, alors v rejoint u, et quitte l'exécution de l'algorithme;

lors de la Réception d'un message JOIN(u, t) : Le noeud v vérifie s'il a précédemment envoyé un message ch. Si c'est bien le cas, v vérifie si le noeud u veut rejoindre son propre cluster et actualise, si besoin, son ensemble cluster(v). Lorsque tous les voisins z de v tel que w, < w_u ont déjà témoigné leur volonté à rejoindre son cluster, v quitte l'exécution de l'algorithme. Un noeud v qui a dans sa liste de voisins des noeuds de poids supérieurs au sien et qui n'a pas reçu des messages de type CH(u) attend de recevoir de tous ces voisins x de poids supérieur au sien des message de type JOIN(x, t), pour dire en fait que ses voisins ont rejoint un ou plusieurs CH de poids supérieur aux leurs. Dans ce cas le noeud v décide alors de devenir CH en diffusant alors le message CH(v). Illustrons le fonctionnement de l'algorithme DCA de Basagni avec le graphe représenté par la figure 2.2

Cet algorithme convient pour des réseaux " quasi-statiques ". En ce qui concerne la maintenance, l'auteur propose d'abord une succession de clusterisations afin que DCA s'adapte à la mobilité des noeuds. Par la suite, il propose une autre version du DCA qu'il baptise DMAC plus adapté pour les réseaux où les capteurs sont mobiles. La métrique de sélection des CHs est cette fois ciliée à la mobilité des capteurs. DMAC géra tant l'initialisation que la maintenance de l'organisation des clusters malgré la mobilité des noeuds. La maintenance quant à elle se fait

17

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

à présent par actions réduites [24]. désormais on n'a plus besoin de supposer que la topologie du réseau est statique durant la construction des clusters. L'adaptation aux changements de la topologie du réseau est rendue possible en laissant chaque noeud réagir non seulement à la réception d'un message venant d'autres noeuds, mais également à la défaillance d'un lien de communication vers un autre noeud

Afin d'économiser en énergie et limiter l'impact de la mobilité, l'auteur introduit l'algorithme GDMAC. Son propos est le suivant : conformément aux spécifications de l'algorithme DMAC, un noeud ordinaire va toujours se soumettre avec le clusterhead de son voisinage qui a le plus fort poids. Si plus tard, un autre clusterhead avec un poids plus élevé apparaît dans son voisinage, le noeud ordinaire va changer son affiliation afin de se soumettre toujours au noeud, a priori, le plus capable d'être un bon clusterhead. Une autre forme de réaffiliation apparaît quand deux CHs, à cause de leur mobilité, se retrouvent dans la portée d'influence l'un de l'autre. A ce moment-là, seul le plus lourd des deux va conserver son statut de clusterhead, tandis que l'autre va devenir noeud ordinaire et se chercher un clusterhead convenable. Si aucun n'est à portée de transmission, le noeud va redevenir son propre clusterhead (élection).

Nous pouvons remarquer que ce schéma de clustering présente plusieurs points faibles. En effet, l'algorithme de Basagni ne prend pas en compte la sécurité du processus de formation de clusters. Outre, à la fin de cet algorithme, un noeud quelconque peut appartenir à plusieurs clusters. De plus, la constitution des noeuds est dépendante d'un noeud précis (le clusterhead)et on peut avoir à la fin, des clusters non disjoints. Ceci nous amènent à des interrogations telles que : Que se passerait-il si ce clusterhead avait menti sur ces métriques ou était en effet un noeud malicieux? le protocole suivant vient pallier à ces insuffisances.

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.

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.

2.4.3 Architecture virtuelle d'un réseau de capteurs : Algorithme de clustérisation de A. Wadaa et al.

Le protocole présenté ici est celui de la construction d'une architecture virtuelle des RCSFs [26]. Il permet le partitionnement d'un RCSF en secteurs et en couronnes de telle sorte qu'après le partitionnement, chaque capteur ne se retrouve que dans un seul secteur et une couronne bien précise. Le problème est qu'initialement, un noeud ou un ensemble de noeuds ne sont pas directement détectable dans l'espace par la BS, et aucune structure n'était clairement définie. La solution proposée consiste donc à la partition du réseau en différentes zone par la BS. Cette dernière a la possibilité de diffuser des informations avec une échelle plus ou moins grande, celle-ci étant utilisée pour créer des couronnes; aussi, elle a la possibilité de diffuser des informations

26

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

dans certaines directions, afin de créer divers secteurs angulaires. La zone (i, j) est l'intersection d'un secteur angulaire j et d'une Couronne i. Les capteurs d'une même zone sont donc dans le même emplacement géographique et forme un cluster. Ceci est illustré par la figure 2.7. Pour la suite, le temps est divisé en slot s1, s2, ..., _{sd_1} et on va considérer que chaque capteur

FIGURE 2.7: Architecture Virtuelle

synchronise son temps avec le sink à interval de temps régulier. D'autre part, on considère que si le sink émet un signal et qu'un capteur le reçoit, celui-ci met son bit b1 à 0 et celui qui ne le reçoit pas met le sien à 1.

Partitionnement en couronne

Le partitionnement en couronne permettra à tout capteur du réseau d'enregistrer l'identité de la couronne dans laquelle il se trouve. les auteurs supposent que tous les capteurs connaissent le nombre k de couronnes que l'on souhaite former. Pour cela, chaque capteur doit déterminer une chaine de log₂ k bits afin de déterminer le numéro de la couronne de rayon ri avec 1 < i < k à laquelle il appartient. Le protocole de partitionnement en couronne se déroule comme suit :

Au premier slot, tous les capteurs sont éveillés et le sink émet une transmission de rayon rk/2 et donc tous les capteurs situés dans les k/2 premières couronnes mettent leur bit b1 à 0 tandis que les autres mettent les leurs à 1. Après d - 1 slots, les capteurs auront appris tous les bits nécessaires au calcul de leur numéro de secteur. En effet, après avoir appris les bits b1, b2, . .. , _blogk, un capteur effectue la somme

log k

l = 1 + _X bj2log k_j (2.1)

j=1

qui est le numéro de sa couronne [26]. Partitionnement en secteur

Tout comme précédemment, le partitionnement en secteur permettra à tout capteur du réseau d'enregistrer l'identité du secteur angulaire dans lequel il se trouve. On suppose dans un premier temps que les capteurs connaissent le nombre d de secteurs que le réseau doit contenir.

27

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

Ensuite, que tous les secteurs obtenus après le partitionnement doivent couvrir les secteurs 360°

angulaires d'angles _d et en fin que le sink est capable d'effectuer une diffusion angulaire suivant un angle donné. Ainsi seuls les capteurs situés dans la zone de couverture recevront le signal. Chaque capteur doit apprendre une chaine de logd bits afin de déterminer le numéro du secteur dans lequel il se trouve.

Déroulement :

Au premier slot, tous les capteurs sont éveillés et le sink émet un signal couvrant _rd/2 premiers secteurs angulaires. Tous les capteurs qui recevront le signal mettront leur bit b1 à 0 tandis

360°

que les autres mettront les leurs à 1. Posons á = d et considérons les résultats obtenus aux lemme 1 et 2.

Corollaire 1. après avoir appris les bits b1, b2, . .. , _bi-1, un capteur doit se réveiller au temps slot z = 1 + i-1

j=1 cj pour apprendre le bit bi. d'autre part, au temps z, le sink effectue une transmission correspondant au secteur angulaire d'angle z * á

conclusion : après d-1 slots, les capteurs auront appris tous les bits nécessaires au calcul de leur numéro de secteur. en effet, après avoir appris les bits b1, b2, .. . , _blogd, un capteur effectue la somme l = 1 + log d

j=1 bj2log ^d-j qui est le numéro de sa couronne.

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édant 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.

2.5 Conclusion

Dans ce chapitre, nous avons présenté quelques algorithmes de partitionnement centré sur le noeud à l'instar de l'algorithme de clustérisation de Gerla et Tsai et ceux de Basagni et ensuite, ceux centré sur le cluster parmi lesquels le schéma de clustérisation de Sun et al., l'algorithme de Banerjee et al. et l'architecture virtuelle de A.Wadaa et al. Nous remarquons que chaque protocole est une amélioration de l'autre. L'algorithme de A Waada et al. permet d'avoir une architecture virtuelle uniquement pour une surface plane. D'où le protocole de partitionnement en 3D pour un réseau déployé dans l'espace. Il serait intéressant de voir comment ils peuvent être utilisées pour résoudre efficacement le problème de geocasting.

36

Chapitre 3

Sécurité dans les Réseaux de Capteurs

Sans Fil

Sommaire

3.1 Introduction 36

3.2 Principes d'attaques et d'attaquants 37

3.3 Politiques de sécurité dans les RCSFs 38

3.4 Taxonomie des attaques 38

3.4.1 Attaques passives 39

3.4.2 Attaques actives 39

3.4.3 Attaques physiques 42

3.5 Mécanismes de sécurité 42

3.5.1 Le partitionnement de données 42

3.5.2 La cryptographie 43

3.5.3 Détection d'intrusions 44

3.6 Conclusion 44

3.1 Introduction

Les RCSFs sont souvent très denses et déployés dans des zones à risques pour des applications sensibles où l'information récoltée est d'une importance capitale pour l'utilisateur final du réseau. Les conditions de déploiement et la nature de l'information captée exige un niveau de sécurité important pour contrer les différents types d'attaques sur la topologie du réseau et le routage de données tout en respectant les contraintes des RCSFs et le maintien de leurs performances. Plusieurs solutions existent pour assurer un routage efficace d'informations en contournant les nombreuses contraintes influençant le bon fonctionnement du réseau. Deux de ces contraintes sont essentielles : i) assurer une consommation raisonnable d'énergie afin de prolonger la durée de vie des noeuds capteurs et par conséquent la durée de vie du réseau

37

CHAPITRE 3. SÉCURITÉ DANS LES RÉSEAUX DE CAPTEURS SANS FIL

et ii) garantir des communications sécurisées où les utilisateurs légitimes sont authentifiés et l'information véhiculée est fraiche, disponible et confidentielle. Dans ce chapitre, Nous allons présenter une taxonomie des attaques sur les RCSFs, par la suite, nous présenterons quelques défis et solutions de sécurité présentes dans la littérature.

3.2 Principes d'attaques et d'attaquants

Une attaque [30] peut être définie comme une tentative d'accès illégale à une ressource du système. Les attaques visent essentiellement les liens de communication et les entités du réseau afin de s'autoriser à récupérer et manipuler les données échangées. Un attaquant est une personne qui s'intéresse au fonctionnement du réseau dans le but de s'adjuger les moyens et le pouvoir de déjouer la sécurité du système. L'existence d'un noeud compromis est très problématique car cela nécessite de revoir complètement la politique de sécurité appliquée. Les attaquants d'un RCSF peuvent opérer à deux niveaux : s'attaquer aux informations échangées entre les noeuds et s'attaquer aux noeuds eux-mêmes. Ils se classent en plusieurs catégories en fonction de leurs objectifs et de leurs capacités de nuisance. On distingue [31] : les attaquants passifs dont l'objectif est d'analyser et de récupérer les informations qui circulent sur le réseau sans toutefois toucher à son fonctionnement; les attaquants actifs qui visent à détruire le réseau par la compromission ou la destruction physique de ses noeuds; les attaquants externes qui essayent d'infiltrer le réseau de l'extérieur en exploitant certaines failles de sécurité et enfin les attaquants internes qui revendiquent leurs appartenances au réseau afin d'accéder aux ressources du système.

Tenant compte du fait que les capteurs sont limités par leur puissance d'énergie et de calcul, les solutions de sécurité doivent relever les défis suivants :

Minimiser la consommation d'énergie : l'objectif est de concevoir des mécanismes de sécurité performants et économes en énergie. L'énergie dissipée pour assurer les fonctions de sécurité est utilisée pour le calcul, la transmission des certificats de sécurité, les chiffrages, déchiffrages, signatures, vérifications des signatures et le stockage des paramètres de sécurité.

S'adapter à l'environnement de déploiement : dans la plupart des applications des RCSFs, les noeuds sont déployés dans des zones hostiles ce qui rend leur compromission assez facile. Les mécanismes de sécurité doivent détecter et réagir rapidement à la capture et à la compromission des noeuds afin de changer les paramètres de sécurité appliqués.

Contourner l'absence de la sécurité physique des capteurs : la topologie des RCSF les rends exposés à différents types d'attaques pouvant survenir de toute part et qui cible n'importe quel entité du réseau. L'absence d'une sécurité physique, contrairement aux réseaux filaires où la sécurité est renforcée par des firewalls, doit être contournée par des techniques de détection d'intrusions.

Développer des schémas propres aux communications sans-fil : les solutions classiques de sécurité pour les réseaux filaires et autres types de réseaux sans fil sont inapplicables

38

CHAPITRE 3. SÉCURITÉ DANS LES RÉSEAUX DE CAPTEURS SANS FIL

aux RCSF. Les mécanismes de sécurité doivent coupler le médium de communication sans-fil utilisé aux caractéristiques spécifiques aux réseaux de capteurs sans fil.

3.3 Politiques de sécurité dans les RCSFs

Une politique de sécurité dans les RCSFs est un ensemble de mécanismes, d'algorithmes, de procédures et de schémas cohérents conçus pour maintenir un certain niveau de sécurité. Une politique de sécurité doit assurer au minimum : i) un contrôle d'accès : détecter et interdire l'ajout de nouveaux éléments corrompus au réseau; ii) l'intégrité et iii) la confidentialité des données transmises. Les protocoles de sécurité reposent sur les politiques telles que: la sécurité des communication (choisir des outils adéquats pour l'établissement de liens sécurisés entre les noeuds communicants), la sécurité du routage et des données agrégées (l'accès aux données pour les agréger, les filtrer ou les compresser doit se faire uniquement par les noeuds autorisés du réseau) et la sécurité physique des noeuds (protéger les noeuds contre toute tentative de compromission, détecter et mettre en quarantaine les noeuds compromis). Quant au routage, sa politique de sécurité concerne les différents niveaux de communication selon la topologie du réseau et le type de routage appliqué pour acheminer les informations. Comme le montre la figure 3.1, sa stratégie de sécurité met en avant la sécurité des liens, la sécurité intra-cluster, la sécurité inter-cluster et la sécurité noeud du réseau - station de base.

FIGURE 3.1: Stratégies de sécurité dans un RcSF

3.4 Taxonomie des attaques

Dans cette section, nous allons présenter une série des menaces (liste non exhaustive) les plus redoutables et les plus connues sur le routage de données dans les RCSFs [32].

CHAPITRE 3. SÉCURITÉ DANS LES RÉSEAUX DE CAPTEURS SANS FIL

3.4.1 Attaques passives

Dans ce type d'attaques, généralement, l'attaquant passe inaperçu. En effet, son objectif est d'écouter le réseau sans chambouler ou altérer son fonctionnement. Pendant ce temps, aucun paquet de données n'est émis sur le réseau par l'attaquant ce qui rend sa détection très difficile. L'objectif de ces attaques est d'analyser les paquets de données circulant sur le réseau et d'extraire des informations précieuses, d'une part, et d'analyser les chemins empruntés par ces paquets de données afin de se procurer des informations stratégiques sur le fonctionnement global du réseau comme la position de la BS, l'identité des CHs etc. D'autres parts, les informations obtenues par un attaquant passif peuvent être utilisées pour créer des attaques actives [33].

3.4.2 Attaques actives

Contrairement aux attaques passives, les attaques actives visent à modifier l'état du réseau. En effet, un attaquant émet périodiquement des paquets de données sur le réseau pour différents objectifs qu'on va énumérer en présentant quelques techniques d'attaques sur le routage, les plus répandues pour les RCSFs. Les menaces actives appartiennent principalement à quatre catégories illustrées par la figure3.2) :

· Interruption : Vise la disponibilité des données.

· Interception : Vise la confidentialité des données.

· Modification : Vise l'intégrité des données.

· Fabrication : Vise l'authenticité des données.

39

FIGURE 3.2: Types d'attaques actives

Parmi les attaques actives, nous pouvons citer (liste non exhaustive) :

Jamming attack : cette attaque sévit au niveau de la couche physique, son objectif est de causer un déni de service(DoS) en émettant des signaux à une certaine fréquence, proche de celle utilisée dans le réseau, sur le médium de communication afin de le saturer pour que les noeuds ne puissent pas communiquer [34] entre eux.

Usurpation d'identité : c'est l'une des attaques les plus dommageables dans les réseaux informatiques en général et les réseaux de capteurs en particulier. Elle permet à un attaquant

40

CHAPITRE 3. SÉCURITÉ DANS LES RÉSEAUX DE CAPTEURS SANS FIL

de confisquer l'identité de sa victime pour s'acquérir les privilèges qui lui sont associés. Typiquement, l'attaquant se limite uniquement à emprunter l'identité de l'un des noeuds communicants, la source ou la destination, pour pouvoir lire et transmettre des messages en utilisant les coordonnées de sa victime. Cette attaque est initiée par un type d'attaquant appelé man-in-the-middle (la technique de l'homme au milieu).

Sinkhole attack (l'attaque du trou de la base) : l'attaquant devient attractif en proposant des chemins optimaux pour atteindre la station de base avec des connexions puissantes ce qui pousse les noeuds émetteurs à modifier leurs tables de routage pour acheminer les données par ce noeud malicieux. Ainsi, toutes les informations qui y transitent pourront être récupérées par l'attaquant [35] .

Wormhole attack (l'attaque du trou de ver) : ce type d'attaques nécessite au moins deux noeuds malicieux. Les deux noeuds sont liés par une liaison radio puissante ou par une liaison filaire. Ce chemin attaquant-attaquant est à un saut donc plus rapide et plus optimal ce qui facilite la création de deux noeuds attaquants de type Sinkhole attack et permettre à chacun des deux de récupérer des informations dans un point du réseau, les modifier, puis les transmettre sur l'autre point du réseau en ignorant les noeuds intermédiaires. Les informations compromises seront envoyées vers la BS [35]. Les protocoles victimes de ce type d'attaques sont ceux basés sur i) la latence de routes, ii) la première route découverte et iii) le nombre de sauts pour atteindre la destination.[35]

Blackhole attack (l'attaque du trou noir) : le principe est d'insérer un nouveau noeud ou bien compromettre un noeud du réseau pour obliger un maximum de voisins à modifier leurs tables de routage et faire transiter leurs données émises par ce noeud malicieux. Les informations reçues par ce dernier seront détruites et ne seront jamais réinsérées sur le réseau. Blackhole attack vise souvent les architectures hiérarchiques et plus particulièrement les noeuds agrégateurs.

Rushing attack : cette attaque vise particulièrement les protocoles de routage basés sur la première route découverte [36]. Lors du processus d'établissement de routes par la diffusion de requêtes, et à la réception d'une requête de construction, l'attaquant émet automatiquement une réponse via un ou plusieurs noeuds malicieux insérés dans le réseau même si aucune information sur la destination n'est disponible sur sa table de routage (c'est-à-dire que l'attaquant n'est pas concerné par la requête). Cette réponse lui permet, à fortes chances, d'être choisi comme noeud intermédiaire dans le routage de données. Les informations qui lui seront destinées seront alors compromises.

Routing table poisoning : l'attaquant encombre le réseau avec de fausses informations sur des routes fictives ce qui contraint les noeuds à mettre à jour excessivement leurs tables de

41

CHAPITRE 3. SÉCURITÉ DANS LES RÉSEAUX DE CAPTEURS SANS FIL

routage. Les mises à jour engendrent un débordement et les tables de routage seront remplies et saturées par de fausses informations sur les routes.

Sybil attack : l'objectif de cette attaque est de faire passer le noeud malicieux pour plusieurs noeuds en lui endossant plusieurs identités, afin de créer une multitude de chemins passant par ce noeud qui ne sont en réalité qu'un seul chemin. Sybil attack s'intéresse aux protocoles basés sur l'instauration d'une redondance de chemin pour assurer la fiabilité du réseau [37].

Flooding attack : l'objectif de cette attaque est de provoquer un déni de service (DoS). En effet, un ou plusieurs noeuds malicieux du réseau effectuent des envois réguliers de messages à une puissance d'émission forte dans le but de saturer le réseau [38].

Hello flooding attack : l'objectif de cette attaque est de consommer l'énergie des noeuds capteurs, notamment les plus éloignés, par un envoi continu, à un signal puissant des messages de découverte du voisinage de type HELLO. Les noeuds destinataires du message essayent de répondre au noeud malicieux même s'ils sont situés à des distances lointaines ne permettant pas de l'atteindre. A force de tenter de lui répondre, tous les noeuds concernés par ce message HELLO consomment l'intégralité de leur énergie.

Écoute passive : Cette attaque consiste à écouter le réseau et à intercepter les informations circulant dans le médium. Elle est facilement réalisable si les messages circulant dans le ré- seau ne sont pas cryptés. De par sa nature passive, l'écoute passive est difficilement détectable car elle ne modifie pas la structure du réseau.

Insertion de boucles infinies: cette attaque vise à consommer l'énergie des noeuds capteurs en modifiant leurs tables de routage de manière à générer des boucles infinies entre les noeuds.

Injection ou altération de messages : le principe est d'injecter sur le réseau des messages véhiculant de fausses informations sur le routage ou bien récupérer puis altérer les messages circulant sur le réseau. L'objectif d'une telle attaque est de perturber la fonction du routage et donc le fonctionnement global du réseau.

Réplication de données : cette attaque vise la fraicheur des données échangées sur le réseau. En effet, l'attaquant récupère et enregistre des informations au temps (T) puis les reproduire sur le réseau au temps (T+N). Ceci va tromper le système de surveillance et des décisions erronées seront prises. Pour illustrer ce cas, on cite l'exemple d'un RcSF ayant pour mission la détection d'un départ d'incendie. Si un incendie se déclare au temps (T), l'attaquant récupère cette information et va la reproduire ultérieurement faisant croire au centre de contrôle qu'un nouvel incendie s'est produit.

42

CHAPITRE 3. SÉCURITÉ DANS LES RÉSEAUX DE CAPTEURS SANS FIL

Attaque du trou noir (Black Hole Attack) Cette attaque consiste tout d'abord à insérer un noeud malicieux dans le réseau. Par divers moyens, ce noeud va modifier les tables de routage pour obliger le maximum de noeuds voisins à faire passer toutes les informations à transmettre par lui. Ensuite, comme un trou noir dans l'espace, les informations qui vont passer par ce noeud ne seront jamais retransmises.

3.4.3 Attaques physiques

Dans la plupart des applications de RCSF, les capteurs sont déployés dans des zones inaccessibles au coeur du territoire ennemi. Le risque d'exposition aux attaques ennemies est très présent, parmi elles on cite :

Destruction physique : l'ennemi ou toute personne étrangère à l'application du RCSF, se trouvant sur le périmètre de déploiement, peut subtiliser des noeuds capteurs pour les détruire et ainsi faire perdre au réseau sa connectivité et le diviser en sous réseaux incapables de communiquer entre eux et avec la BS [39, 40].

Attaques spécifiques aux types de capteurs : en déduisant le type et la tâche du capteur déployé, l'attaquant peut le faire réagir en produisant un événement attendu par le capteur, comme allumer une lampe devant un capteur de luminosité ou allumer une flamme devant un capteur thermique. Le capteur réagit et transmet de fausses informations en continu à la BS jusqu'à l'épuisement de son énergie.

Empêcher le capteur de se mettre en veille : l'attaquant essaye d'empêcher un noeud capteur de se mettre en veille par différents moyens. Le fonctionnement sans cesse du capteur lui causera la perte de son énergie

3.5 Mécanismes de sécurité

Plusieurs solutions ont été développées pour lutter contre les attaques sur les RCSFs. On distingue des solutions spéciales au routage où la fonction de sécurité concerne la protection de la donnée transmise, d'autres solutions sont conçues pour protéger les communications entre les noeuds capteurs en assurant la fiabilité des liaisons par des fonctions cryptographiques, et enfin des solutions qui se chargent de protéger les noeuds du réseau, de détecter et d'exclure les noeuds malicieux par des mécanismes de détection d'intrusions. Dans [41], on propose les mécanismes simples, les plus efficaces et les plus appropriés aux RCSFs, regroupés selon l'objectif de la solution proposée.

3.5.1 Le partitionnement de données

C'est une solution proposée dans le but d'empêcher les attaquants de récupérer l'intégralité des informations qui circulent sur le réseau. Le principe est de découper, au niveau du noeud source, l'information à transmettre en plusieurs paquets de tailles fixes et chaque paquet de

43

CHAPITRE 3. SÉCURITÉ DANS LES RÉSEAUX DE CAPTEURS SANS FIL

données sera envoyé sur un chemin différent. L'entité de destination finale, après la réception de tous les paquets de données, procède à la reconstitution du message initial émis par le noeud source. Afin de saisir intégralement l'information échangée entre la source et sa destination, un attaquant doit scruter tous les chemins utilisés dans la transmission du message, ce qui est difficile voire impossible vu la taille des réseaux et le nombre important de chemins possibles entre chaque paire de noeuds. Cependant, cette solution est gourmande en énergie car elle implique un grand nombre de noeuds pour acheminer chaque paquet vers l'entité destinataire. Un exemple d'une telle solution est donné par la figure3.3.

FIGURE 3.3: Technique de partitionnement des données

3.5.2 La cryptographie

Le mot cryptographie est composé de deux mots grecs : « crypto » qui signifie caché et « graphie » qui signifie écrire, d'où la signification complète de la cryptographie est « l'écriture secrète ». La cryptographie est définie comme la science qui convertit les informations en clair en informations cryptées c'est-à-dire codées [42]. Le principe est donné par la figure3.4. La plupart des mécanismes de sécurité des communications sont basés sur des outils cryptographiques utilisant des informations secrètes représentées par des nombres premiers, dites clés, combinées en entrée d'une opération cryptographique, au message à coder pour produire le message crypté. On distingue quatre types de clés utilisées dans les opérations cryptographiques [42] : clé individuelle, clé par paire, clé de groupe et clé globale. Cependant, les solutions cryptographiques

FIGURE 3.4: Principe de la cryptographie

ne sont intéressantes que lorsque l'attaquant ne désire que lire le contenu des messages. Si un
attaquant ne désire que supprimer un message, alors ces solutions ne sont plus très appropriées.

44

CHAPITRE 3. SÉCURITÉ DANS LES RÉSEAUX DE CAPTEURS SANS FIL

3.5.3 Détection d'intrusions

Détection d'intrusions par localisation : ici, les noeuds capteurs doivent être équipés de moyens qui permettent de connaitre leurs positions géographiques (exemple le GPS). Ce type de noeuds capteurs sont dits capteurs balises. Si un capteur souhaite faire partie du réseau, il adresse une demande d'insertion aux capteurs balises afin d'estimer sa localisation par rapport au domaine d'écoute. Les capteurs balises vont quadriller par la suite leurs zones d'écoutes respectives et demandent aux noeuds qui ont reçu la demande d'insertion de voter pour la zone de quadrillage qu'ils peuvent entendre. La zone qui obtient le plus de voix sera considérée comme celle où est censé se trouver le capteur.

Détection d'intrusions par indice de confiance: contrairement à la solution de détection d'intrusions présentée précédemment où des moyens supplémentaires et couteux sont exigés, la détection d'intrusions par indice de confiance consiste à générer une alerte pour tout scénario ou comportement suspect détecté.

Approche par comportements : observer le comportement du système et le comparer au comportement normal. Si le comportement observé est différent du comportement normal, on conclut que le système présente des anomalies et fait objet d'intrusions. L'avantage est la rapidité et la simplicité de détection alors que l'inconvénient est le nombre important de faux positifs que le système détecte à cause d'éventuels changements inattendus qui ne correspondent pas à des attaques.

Approche par scénarios : son fonctionnement ressemble beaucoup au fonctionnement des anti-virus et des anti-trojan des systèmes informatiques classiques. En effet, on utilise une base de signatures où sont répertoriés les différents scénarios d'attaques. Les données reçues sont analysées afin de détecter d'éventuels scénarios d'attaques prédéfinis dans la base de signatures. Cette approche présente l'avantage de précision de diagnostic par rapport à l'approche par comportement mais elle est incapable de détecter les nouvelles attaques non répertoriées.

3.6 Conclusion

Le développement de mécanismes de sécurité spécifiques aux RCSFs a attiré une grande part d'intention parmi les chercheurs de la communauté scientifique du domaine. En outre, les solutions de sécurité proposées pour les autres réseaux sans fil (ad hoc, Wifi, Bluetooth. . . etc.) ne sont pas applicables directement dans les RCSF. En effet, l'absence de sécurité physique et les limites en ressources énergétiques des capteurs, entre autres, s'imposent comme contraintes importantes dans la conception des solutions de sécurité efficaces et économes en énergie pour les RCSFs.

45

Chapitre 4

Protocoles de Geocasting dans les

réseaux de capteurs sans fil

Sommaire
4.1 4.2	Introduction Algorithmes de géocasting sans garantie de livraison. 46		45
	4.2.1	Algorithme de KO-VAIDYA	46
	4.2.2	Les protocoles LBM,VDBG,GeoGRID et GeoTORA	47
4.3	Algorithme de géocasting avec garantie de livraison		48
	4.3.1	Algorithme de Seada et Helmy	48
	4.3.2	Algorithme de Bomgni et al. 49
	4.3.3	Protocole de Myoupo et al. 51
4.4	Conclusion		55

4.1 Introduction

Le geocasting qui est une variante du multicasting a été proposé comme mécanisme pour adresser des messages à tous les hôtes d'une région géographique donnée. Dans le multicasting classique, un hôte devient membre du groupe de multicast en le rejoignant explicitement. Dans le cas du geocasting, l'hôte devient automatiquement membre du groupe de géocast si sa position géographique est en conformité avec la région spécifiée pour le geocast (il perd donc sa qualité de membre s'il se déplace hors de cette région). La technique la plus évidente pour résoudre le problème de geocasting, est l'utilisation de l'inondation simple (flooding en anglais) : la station de base (BS) envoie un message à tous ses voisins qui à leur tour, relaient le message à leurs propres voisins et ainsi de suite, jusqu'à ce que tous les capteurs des régions géocast soient atteints et aient une connaissance du message. Mais cette approche induit plusieurs problèmes tels que la surcharge du réseau, les collisions, etc. Une autre technique consiste dans le paquet

46

CHAPITRE 4. PROTOCOLES DE GEOCASTING DANS LES RÉSEAUX DE CAPTEURS SANS FIL

géocast à définir implicitement ou explicitement une zone appelée forwarding zone. Un noeud n'a le droit de diffuser le paquet géocast à tous ses voisins que s'il appartient à cette zone. Ainsi, le paquet géocast sera diffusé par un petit ensemble de noeuds réduisant ainsi la surcharge du réseau par rapport à l'inondation simple. Pour accroitre la probabilité qu'un paquet géocast soit transmis à tous les noeuds de la région de géocast, la forwarding zone doit inclure en plus de la région de géocast certaines zones autour de celle-ci. En effet, dans le cas où la source n'appartient pas à la région de géocast, ladite source et les noeuds sur le chemin menant à la région de géocast doivent appartenir à la forwarding zone.

Outre l'aspect évident d'inondations, de nombreuses techniques ont été développés dans la littérature, les uns garantissant la réception du paquet par tous les noeuds de la région et les autres non. Dans ce qui suit, nous allons tout d'abord présenter quelques algorithmes de géocasting sans garantie de livraison. puis, par la suite, présenter ceux avec garantie de livraison et économe en énergie.

4.2 Algorithmes de géocasting sans garantie de livraison. 4.2.1 Algorithme de KO-VAIDYA

Les auteurs en [43] ont proposés trois protocoles pour la résolution du problème de geocas-ting : le static zone scheme, l'adaptive zone scheme et l'adaptive distance scheme. La définition de la forwarding zone est l'élément substantiel qui diffèrent dans les trois solutions. Cette technique permet de diminuer la surcharge, le taux de collisions par rapport au flooding simple en ce sens que seul un sous-groupe de l'ensemble des noeuds exécute le flooding.

Static Zone Scheme

La forwarding zone ici est rectangulaire. C'est le plus petit rectangle comprenant la source et la région de geocast ou tout autre polygone. La source peut donc déterminer les quatre points de la forwarding zone et inclure leurs coordonnées dans le paquet geocast à transmettre. Ainsi, Chaque paquet geocast contient une description de cette zone qui statique durant tout le parcours du paquet de l'origine jusqu'à la destination. Lorsqu'un noeud reçoit le paquet geocast, il le supprime s'il ne se trouve pas dans la forwarding zone constituée du rectangle. Le terme statique ici est justifié par le fait que la forwarding zone spécifiée dans le paquet geocast par la source n'est modifiée par aucun autre noeud. Ainsi, la forwarding zone reste statique durant tout le processus de geocasting.

Adaptive zone scheme

Avec cette technique, la fowarding zone est redéfinie à chaque noeud intermédiaire sur le parcours du paquet. Ce protocole est identique au précédent en ce sens que lorsqu'un noeud X

47

CHAPITRE 4. PROTOCOLES DE GEOCASTING DANS LES RÉSEAUX DE CAPTEURS SANS FIL

reçoit le paquet geocast, il détermine si le paquet doit être relayé ou non en se basant sur sa situation géographique et la définition de la forwarding zone incluse dans le paquet geocast reçu. Dans le schéma à zone statique, lorsqu'un noeud X diffuse un paquet geocast, la définition de la forwarding zone dans ce paquet ne sera pas modifié pendant le processus de diffusion. Ce n'est pas le cas du schéma à zone adaptée. En effet, la fowarding zone n'est plus statique tout au long du parcours du paquet. Le protocole stipule que lorsqu'un noeud A envoie un paquet geocast, il modifie la spécification de la forwarding zone. La nouvelle forwarding zone est constituée du plus petit rectangle contenant le noeud A et la région geocast tel que les côtés du rectangle soient parallèles aux axes des abscisses et des ordonnées dans un repère orthonormé. On note tout de même en [43] que les performances de ce protocole peuvent se dégrader drastiquement dans certains cas (Figure 4.1).

FIGURE 4.1: succès/Echec de livraison de paquets lors de l'exécution du schéma à zone adaptée

Adaptive distance scheme

Dans les deux variantes précédentes, la forwarding zone est explicitement spécifiée dans le paquet geocast. Dans le présent schéma, la source S inclut trois informations dans le paquet geocast sans toutefois inclure explicitement la forwarding zone : les spécifications de la région geocast, les coordonnées du centre de la région et les coordonnées de la source. Lorsqu'un noeud reçoit un paquet, il calcule la distance qui le sépare du centre de la région de geocast et la compare à celle de l'émetteur du message. Le résultat permet de décider s'il faut détruire ou réémettre le paquet

4.2.2 Les protocoles LBM,VDBG,GeoGRID et GeoTORA

Le LBM est un protocole basé sur le flooding, plus précisément sur la fowarding zone. Une implémentation du LBM peut exploiter n'importe quelle variante de la fowarding zone sus-présentée. Le LBM réduis la zone de Fowarding et du même coup diminue la charge réseau tout en maintenant une bonne fiabilité par rapport au flooding simple. Le VDBG et le GeoGRID quant à eux, ont pour but de réduire la charge du réseau tout en augmentant la fiabilité du réseau par rapport au LBM. En effet, la fowarding zone est désormais constituées des noeuds qui sont proches de la région de destination (les régions de Voronoi qui intersectent la région geocast).

48

CHAPITRE 4. PROTOCOLES DE GEOCASTING DANS LES RÉSEAUX DE CAPTEURS SANS FIL

Ceci vient résoudre le problème des fowarding zones qui n'ont pas de noeuds pouvant permettre l'acheminement des paquets vers la zone de destination. Pour le GeoGrid, le réseau tout entier est partitionné en grille. Ainsi, pour chaque grille contenue dans la zone de fowarding est élu un noeud dit gateway responsable du fowarding. La clé de cette technique est l'élection du gateway qui a encore des zones d'ombre. Le GeoTORA et le Mesh-based Geocast Protocol ont été introduits pour résoudre le problème de redondance, de surcharge et de collisions multiples. Ils permettent de créer en outre des routes entre la source et la destination à la demande. Pour le transfert du paquet on évite ainsi le flooding. Un avantage indéniable est la réduction considérable de la surcharge du réseau lors de la transmission du paquet. Le contre poids est la nécessité de plus de latence et d'une éventuelle surcharge du réseau lors de la recherche des routes.

4.3 Algorithme de géocasting avec garantie de livraison

4.3.1 Algorithme de Seada et Helmy

Seada et al. en [44] présente 2 algorithmes : le premier algorithme GFG (Geographic-Forwarding-Geocast) possède une surcharge du réseau minimale et est idéal pour les réseaux denses. Le second GFPG (Geographic-Forwarding Perimeter-Geocast) garantit la livraison des paquets à tous les noeuds de la région geocast lorsque le réseau est connecté et même si la densité n'est pas grande ou la distribution des noeuds est irrégulière avec des obstacles.

GFG (Geographic-Forwarding-Geocast)

Geographic-Forwarding-Geocast [45] commence comme un unicast géométrique jusqu'à ce qu'il atteigne la région geocast. Une fois à l'intérieur de la région, le message est inondé. Les messages inondés qui atteignent des noeuds extérieurs à la région geocast sont jetés. En outre, comme l'a noté Casteigts et al. [46], le Geographic-Forwarding-Geocast peut échouer lors de la délivrance du message à tous les noeuds dans la région geocast si la région est déconnectée et la seule connectivité est à travers des noeuds externes. Dans les applications geocast, les noeuds se doivent de pouvoir calculer ou de connaitre leurs coordonnées géographiques. Le protocole GFG utilise donc cette information géographique cruciale pour diffuser efficacement les paquets vers la région geocast. Ce protocole combine le greedy forwarding(routage qui consiste à envoyer un paquet uniquement aux noeuds qui sont proches de la destination) et le face routing(routage qui consiste à router les paquets autour des points de terminaison jusqu'à trouver des noeuds proches de la destination); mais le face routing n'est utilisé ici que si c'est nécessaire (i.e en utilisant la greedy forwarding, on arrive à une situation où un noeud ayant reçu le paquet n'arrive pas à trouver un noeud proche de la destination). Dès que le paquet parvient aux noeuds à l'intérieur de la région geocast, ceux-ci le diffusent à tous leurs voisins et ainsi de

49

CHAPITRE 4. PROTOCOLES DE GEOCASTING DANS LES RÉSEAUX DE CAPTEURS SANS FIL

suite. Le « Virtual Surrounding Face » [47] évite ce problème en pré-calculant à l'avance toutes les faces planes qui interceptent la région geocast.

GFPG (Geographic-Forwarding-Perimeter-Geocast)

Cet algorithme utilise un savant dosage de routage géographique et de face routing pour assurer la livraison des paquets aux noeuds situés dans la région geocast lorsque le réseau est connecté et en dépit des obstacles qui peuvent survenir pendant ou après le déploiement. Initialement comme avec le GFG, les noeuds qui sont à l'extérieur de la région se servent de la greedy forwarding pour envoyer le paquet vers la région. Lorsque le paquet finit par rentrer dans la région, les noeuds l'ayant reçu démarrent le processus d'inondation de la région en envoyant le paquet à tous leurs voisins. Tous les noeuds de la région en font de même et en plus les noeuds en bordures de la région initient un paquet de périmètre en direction de ses voisins (ceux étant à l'extérieur de la région). En effet, un noeud est dit noeud en bordure s'il possède un voisin à l'extérieur de la région. Notons que les paquets de périmètre sont envoyés uniquement aux voisins dans le graphe planaire (et non à tous les noeuds). Recevant le paquet, le noeud à l'extérieur de la région le diffuse à son voisin dans le graphe planaire en utilisant la règle de la main droite, et celui-ci fait de même, ainsi de suite. Le paquet sera ainsi relayé le long de cette face et rentrera à nouveau dans la région. Le premier noeud à recevoir le paquet dans la région va démarrer le processus d'inondation si c'est la première fois qu'il reçoit le paquet sinon il le détruit.

4.3.2 Algorithme de Bomgni et al.

Bomgni et al. propose en [48] un algorithme de géocast et de multigeocast économe en énergie avec garantit de livraison et avec une surcharge du réseau moindre que celle des protocoles présentés plus haut. Son algorithme est une amélioration de ceux présentés plus haut, et se déroule en 05 phases :

Phase 1 : Identification des noeuds et Découverte des voisins

Identification des noeuds : Soit n le nombre de capteurs dans le réseau. Chaque capteur

-1

O(

)

n

tel

peut avoir un identifiant compris entre 1 et n³ avec une probabilité supérieure à e

que deux capteurs quelconques n'aient pas le même identifiant. La preuve de ce théorème a été démontrée dans [48].

Découverte des voisins : Une fois les identifiants attribués, à chaque noeud doit découvrir son voisinage à un saut. Quelque soit le noeud u du réseau, le protocole de découverte ci-dessous(figure 4.2) lui permet de connaitre ses voisins directs. N désigne la borne maximale du degré de tous les noeuds et du le degré du noeud quelconque u (notons que N < n).

CHAPITRE 4. PROTOCOLES DE GEOCASTING DANS LES RÉSEAUX DE CAPTEURS SANS FIL

Phase 2 : partitionnement du réseau en clique

Les capteurs exécutent le protocole de sun et al. [25] pour former des cliques. On suppose que cette phase génère k cliques et donc k CHs. On note _CHcliquei le clusterhead de la clique i. On rappelle qu'après cette procédure tous les noeuds dans une même clique sont à un saut l'un de l'autre. Ce qui permettra d'avoir un gain en énergie énorme lors des transmissions comparées aux transmissions dans un environnement partitionné où les noeuds d'un même cluster peuvent être à plusieurs sauts les uns des autres.

Phase 3 : Partitionnement hiérarchique

On se focalise uniquement sur les CHs générés à la phase 2. Considérons le réseau G' engendré par ces k CHs. Il est clair que G^' = k. Partitionnons ce réseau en utilisant la technique de partitionnement hiérarchique de Banerjee et al. [27] présentée au chapitre précédent tel que

k

chaque cluster résultant de cette phase de partitionnement ait au moins ₂ capteurs et au plus

k capteurs. Il est facile de remarquer que ce partitionnement engendrera un seul cluster et donc un seul clusterhead (le super clusterhead). Ce dernier connait les identifiants de tous les résidents du cluster dont il est le coordonnateur i.e les identifiants des k - 1 capteurs.

Phase 4 : Phase de requête

Lorsque la source souhaite envoyer un paquet à tous les noeuds situés dans une région géo-cast, elle diffuse dans l'ensemble dominant un petit paquet constitué du message et de la spécification de la région géocast comme suit (REQUEST(Message, CoordonnéesRégionGéocast)). Tout paquet de ce type est tout d'abord envoyé au superclusterhead qui est la seule entité à pouvoir prendre une décision par rapport au paquet. Ainsi, le paquet partira d'un clusterhead de niveau 1 jusqu'au superclusterhead.

Après avoir reçu le paquet, ce dernier va envoyer un message de recherche contenant la définition de la région géocast (SEARCH(CoordonnéesRégionGéocast, f3)) à tous les cluste-rheads des niveaux inférieurs pour savoir si ces derniers ont des noeuds situés dans la région de geocast spécifiée dans le paquet. Ce message est accompagné d'une variable booléenne 3.

50

FIGURE 4.2: Protocole de découverte de voisins

51

CHAPITRE 4. PROTOCOLES DE GEOCASTING DANS LES RÉSEAUX DE CAPTEURS SANS FIL

Chaque clusterhead de premier niveau envoie le paquet de recherche à tous les noeuds membres de son cluster. Ceux-ci déterminent si oui ou non ils sont situés dans la région geocast. Si c'est le cas, ils mettent la variable binaire 3 à 1 et renvoient la réponse avec leur identifiant à leur clusterhead. Dans le cas contraire, aucune action n'est menée, cela signifie que ces derniers ne sont pas dans la région geocast. Ces clusterheads enregistrent la provenance des réponses positives.

Les clusterheads ayant reçu au moins une réponse positive à leurs tours acheminent au superclusterhead un petit paquet (SEARCH(CoordonnéesRégionGéocast, 3 = 1)) avec 3 mis à 1.

Phase 5 : Phase de diffusion

Après avoir reçu les réponses des clusterheads de niveaux inférieurs, le superclusterhead renvoie un paquet (REQUEST(Message, 3 = 1)) uniquement à ceux de ces clusterheads qui ont répondu positivement au message de recherche. Le message passera donc par tous les clusterheads qui ont enregistré 3 à 1 et parviendra finalement à tous les noeuds ayant mis 3 à 1 lors de la phase de recherche. les auteurs dans [48] prouvent par la suite que cet algorithme garantit la livraison des paquets à tous les noeuds situés dans la région géocast et est économe en énergie. Une évaluation de la consommation d'énergie y est également faite.

4.3.3 Protocole de Myoupo et al.

Le protocole présenté ici est une amélioration de celui présenté en [48] et est composé de deux grandes parties qui sont complémentaires et permettent une économie globale d'énergie. Tout d'abord la formation hiérarchique basée sur les cliques et un concept d'architecture virtuelle permet de construire une base solide, rapide et sécurisée pour l'acheminement de l'information. Ensuite, la diffusion géocast elle-même est tout simplement réduite à la phase de recherche dans le réseau qui est une étape d'envoi des données. En plus de combiner l'aspect essentiel de la sécurité, le protocole de Myoupo et al.[49] est économe en énergie et permet de minimiser la surcharge de diffusion. Il se déroule en 2 étapes : la formation sécurisée de la structure et la mise en oeuvre du protocole sécurisé de geocasting proprement dit.

Étape 1 : Formation sécurisée de la structure

Cette formation se fait en 3 phases : initialisation, Construction du 1^er niveau de Cluster, Construction des niveaux supérieurs. Soient Kn/u la chaine de clé à sens unique de taille n + 1 générés par le noeud u, MACK(M) un message d'authentification de 8 octets généré au-dessus de M en utilisant la clef K et H la fonction de hachage à sens unique utilisant ,iTESLA. Soient les hypothèses suivantes :

1. Le réseau est statique, connexe et toujours connecté.

CHAPITRE 4. PROTOCOLES DE GEOCASTING DANS LES RÉSEAUX DE CAPTEURS SANS FIL

2. La BS est la seule entité de confiance dans le réseau qui a une forte capacité énergétique que les autres noeuds, et dont la portée de transmission peut couvrir l'ensemble du réseau.

3. Chaque noeud partage une clé secrète avec la BS, qui est chargé avant le déploiement.

4. Chaque noeud connait ses voisins à 1 saut et a un identifiant unique. Tous les messages échangés entre deux noeuds sont authentifiés, grâce à la clé partagée entre ces noeuds. Chaque noeud peut générer une clé publique basée sur une signature. Les messages (diffusion) sont authentifiés grâce à une combinaison de signatures et de protocole de (aTESLA).

Les niveaux hiérarchiques sont formés en utilisant le protocole de Barnejee et al.[27] : Au niveau initial, les noeuds sont répartis en clusters dits "de niveau 1", et dans chacun de ces clusters, un chef doit être élu (un CH¹). Les clusters de niveau 1 sont à leur tour divisé en clusters de " niveau 2", et un chef serait élu pour chaque cluster (un CH² élu parmi les CH¹s) et ainsi de suite jusqu'au niveau N où la tête de cluster CH^N+1 de chaque cluster de niveau N est élue parmi les CH^Ns.

Phase 1 : Initialisation

Cette phase se produit avant le déploiement du réseau. La BS génère d'abord une chaine de clés Kn/bs nécessaire pour effectuer des émissions à tous les capteurs authentifiés. On charge alors chaque capteur u avec un identifiant unique UDi, avec une clé secrète Kbs, u (clé secrète partagée entre la BS et le noeud u) partagé avec elle-même afin d'assurer à l'avenir des communications unicast (pour garantir la confidentialité et l'authentification), et la première clé K0/bs de sa chaine de clé, afin de mener à bien les diffusions /émissions sur l'ensemble du réseau. Enfin, la BS charge chaque noeud u avec la clé cryptographique établie avec tous ses voisins, pour des communications sécurisées entre paire de voisin. Deux noeuds voisins u et v ont une clé sécrète partagée Ku, v.

Phase 2 : Construction du 1^er niveau de cluster

Cette seconde phase est donc d'abord l'application du protocole de Sun et al.[25] en utilisant l'approche Cluster-First (CF) sécurisé. Ce dernier utilise les touches Ku, V mis en place entre deux noeuds u et v. on utilise également la diffusion d'authentification avec (1aTESLA) : chaque noeud u génère en utilisant son matériel cryptographique - une chaine de clés Kn/u et distribue la première clé de la chaine K0/u à ses voisins. Une fois les clusters créés, les noeuds à l'intérieur de chacun s'accordent sur un chef et procèdent à une élection : nous obtenons un CH¹ dans chaque cluster de niveau 1. Enfin, chaque CH élu envoie un message à la BS contenant la liste des membres de son cluster. Le BS ayant été informé par les membres du réseau, elle est capable de lancer la phase suivante quand elle reçoit tous les accusés de réception des CH.

52

Phase 3 (récursive) : Construction des Niveaux Supérieurs

53

CHAPITRE 4. PROTOCOLES DE GEOCASTING DANS LES RÉSEAUX DE CAPTEURS SANS FIL

La phase précédente a permis d'obtenir une base réellement saine pour chaque cluster de niveau 1. Or, les auteurs s'appuient sur un mécanisme d'architecture virtuelle présenté en [26] pour partitionner le cluster de Niveau 1 aux niveaux plus supérieures. C'est la BS - seule entité de confiance dans le réseau - qui est en charge de cette opération. Dans un premier temps, la BS connait le réseau, et détermine- en fonction du nombre de noeuds et de la volonté de partitionnement fixé par l'administrateur - un coefficient de gamme C_p (entre 0, 1 et 1, 1 représentant 100% de la distance séparant la BS du capteur le plus éloigné dans le réseau - ce paramètre peut être donnée par diffusion successive de la BS au moment de l'initialisation) et un coefficient angulaire C_a (entre 1° et 360°). La BS est donc capable de couper le réseau en faisant diffuser sur différentes plages et angles, selon C_a et C_p, comme le montre la figure4.3. Chaque

FIGURE 4.3: BS network cutting with Cp = 0.5 and Ca = 40°. Here, we take the second level formation case. Broadcast step

zone définie par BS est indiqué par un couple d'entier: (nombre angulaire, numéro corona). Le processus de génération de cluster est alors le suivant pour chaque niveau N (N > 1) :

- La BS effectue une diffusion à l'aide de la clé Kn/bs afin de communiquer d'une manière authentifiée le couple d'entier de tous les noeuds. Elle émet ainsi successivement un message de type (angle, couronne) selon Ca et Cp et ainsi à différents angles et couronnes. Pour chaque zone (angle, corona) défini par la BS selon Ca et Cp : BS- > WSN^* : D, MACKj/bs(D), Kj/bs avec Kj/bs la clé actuelle de la chaine de clé Kn/bs, D le couple entier à envoyer et correspondant à une certaine zone selon la BS. Chaque noeud u reçoit alors le message. Il authentifie les révélé des clés Kj/bs en utilisant la clé Kj - 1/bs précédemment mémorisée : pour cela il utilise la fonction irréversible de hachage H qu'il détient, et vérifie la correspondance Kj - 1/bs = H(Kj/bs). Une fois cette première étape fait, les noeuds contrôlent l'authentification fournie par MAC fixée au message et est en mesure de mettre à niveau sa dernière clé connue. Enfin, un noeud est informé du paramètre (angle, couronne) qui lui est affecté. Chaque noeud w appartenant à CH¹ communique à tous les membres de son cluster de niveau 1 le paramètre qu'il détient, en utilisant la chaine clé Kj/w de Kn/w pour l'authentification. L'objectif est de mettre en accord tous les membres de chaque cluster de niveau 1 (en cas où certains membres ont un réglage différent). w- > W1 w : D, MACKj/w(D), Kj/w

54

CHAPITRE 4. PROTOCOLES DE GEOCASTING DANS LES RÉSEAUX DE CAPTEURS SANS FIL

- Ils lisent ensuite le paramètre et améliorent leur valeur locale s'il y a une différence avec la valeur diffusé par BS, et retourne un accusé de réception contenant cette valeur de fin à leur CH¹, qui est authentifié avec Ku, bs.

- Chaque CH¹ reçoit ainsi un groupe de réponses qu'il ne peut pas lire ou modifier. Une fois toutes les réponses reçues, il les envoie tous à la BS, avec la signature Kch, bs, en incluant l'ID_u des membres qui n'ont pas répondu.

- La BS reçoit un message, l'authentifie, puis vérifie un par un tous les accusés de réceptions des noeuds des clusters. Si une incohérence est remarquée, ou si elle ne reçoit pas un message d'un CH, elle prend des mesures : la réélection, bannissement des noeuds, ou autres.

- A ce moment, les clusters de niveau N sont implicitement formés : un cluster de niveau N est un ensemble de cluster de niveau N - 1, dont les membres ont les mêmes paramètres (angle, corona) et sont directement liés.

- La poursuite de l'algorithme consiste alors à l'élection d'un CH^N+1 parmi tous les CH^N accessible entre eux sans changer le paramètre (angle, couronne). Par conséquent, un CH^N+1 est également CH^N, CH^N_1, CH^N_2, CH¹ ... . Le cluster est supposée être formée. Le concept de cluster est un peu abstrait ici, car un noeud appartenant à un groupe de niveau N(N > 1) ne connait pas directement tous les autres membres, il n'a que des connaissances de son CH^N et les membres de son cluster de niveau 1.

- Une fois le choix fait, chaque nouvel élu CH informe la BS qui commence à nouveau toute cette phase pour un niveau supérieur, en multipliant Cp et Ca par un facteur j à corriger. La formation de Cluster est terminée lorsque la BS voit qu'il n'y a rien à gauche, mais un CH pour le niveau N. La formation du Cluster est terminée et ne doit pas être rediffusé. Toutefois, il est possible que les opérations d'ajustement soient réalisées en interne, telles que les opérations de mise à jour, la tolérance au faute, l'ajout de noeuds, ou encore les mécanismes de relégation ou réélection si un noeud malveillant est détecté. Par la suite, les auteurs dans [49] mettent sur pied un mécanisme pour assurer le bon entretien de la structure

Étape 2 : Protocole de geocasting

Ce protocole comporte deux phases. Ici, La BS possède l'information à envoyer aux noeuds dans les régions géocast. L'objectif de la première phase du protocole est la découverte de ces noeuds. La seconde phase consiste en l'envoi d'informations depuis la BS.

Phase 1 : Découverte de capteurs dans les régions géocast

L'objectif pour la BS est de transmettre une donnée D à une zone géographique B. Cette phase consiste à la découverte des noeuds situés dans B. Afin d'économiser de l'énergie et limiter le temps d'exécution de cette phase, précisons que le temps est divisé en Slot S⁰, S¹, ..., Sⁿ. Cette étape se déroule comme suit : au slot Sⁱ, la BS effectue tout d'abord une diffusion en utilisant la clé Kn/bs afin de communiquer d'une façon authentifié un petit paquet qui représente la zone géographique B à l'ensemble des capteurs dans le réseau : BS- > WSN^* :

55

CHAPITRE 4. PROTOCOLES DE GEOCASTING DANS LES RÉSEAUX DE CAPTEURS SANS FIL

B, MACKj/bs(B), Kj/bs Avec Kj/bs la clé actuelle de la chaîne de clés Kn/bs, et B la zone de recherche. Chaque noeud u reçoit alors le message et contrôle son authenticité. Il est informé de la zone B requise et alors est capable de savoir s'il est située dans cette zone ou pas (Hypothèse (4)). Dans le cas négatif, il ne fait rien. Dans le cas positif, il envoie un accusé de réception à la BS, contenant B, authentifié en utilisant la clé (Kbs, u) partagée entre BS et le noeud u : u- > BS : B, _MACKbs,u(B), Kbs, u Notons que le routage de u à BS se fait simplement en remontant la hiérarchie déterminée par la structure. A la fin du slot S^j, Si la BS a reçu des accusés de réception, alors elle sait où envoyer les données D à transmettre.

Phase 2 : envoi de la requête

Pour chaque capteur u ayant répondu à la BS durant le temps de slot S^j, et étant ainsi située dans B, la BS est capable d'envoyer directement à ces capteurs les informations D, en l'authentifiant et la protégeant avec la cléKbs, u et pendant la tranche de temps slot S^j+1. Une limite de ce protocole est que les noeuds sont statique et le concept de cluster est un peu abstrait ici, car un noeud appartenant à un groupe de niveau N(N > 1) ne connait pas directement tous les autres membres, il n'a que des connaissances de son CH^N et les membres de son cluster de niveau 1.

4.4 Conclusion

Dans ce chapitre, nous avons présenté les différents protocoles de géocasting existants dans la littérature; les uns garantissant la livraison des paquets et les autres pas. A la lumière de ce qui précède, nous constatons que ces protocoles s'appliquent sur des capteurs déployés sur une surface plane, or l'espace de déploiement peut, présenter des irrégularités. Par conséquent, il est nécessaire de concevoir des protocoles prenant en compte ces irrégularités.

56

Chapitre 5

Notre contribution : Une approche de

protocole de géocasting sécurisé dans

un RCSF déployé dans l'espace (en 3D)

Sommaire

5.1 Introduction 57

5.2 Notre approche de sécurité 57

5.2.1 Au pré-déploiement 59

5.2.2 Phase de Construction 59

5.2.3 Phase de reconstruction 60

5.2.4 Phase de renouvellement 60

5.2.5 Phase de révocation 60

5.2.6 Insertion des nouveaux noeuds 61

5.3 Étape 1 : Formation sécurisée de la structure 61

5.3.1 Partitionnement sécurisé du réseau en cluster 61

5.3.2 Identification des noeuds 62

5.3.3 Découverte de voisinage 62

5.3.4 Construction et Définition de notre arbre couvrant le graphe 63

5.3.5 Routage sécurisé inter-cluster 63

5.3.6 Routage sécurisé intra-cluster 65

5.3.7 Élection du Cluster Head 65

5.4 Étape 2 : Protocole sécurisé de géocasting 69

5.4.1 Geocasting avec plusieurs régions géocast 70

5.5 Analyse de la sécurité 71

5.6 Analyse de la consommation de l'énergie 71

5.7 Implémentation et Analyse des résultats 72

57

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

	5.7.1	Les métriques	73
	5.7.2	Nombre et la taille des clés stockées	73
	5.7.3	Nombre de paquets échangés	74
	5.7.4	Consommation d'énergie	75
5.8	Conclusion		77

5.1 Introduction

Nous avons présenté dans le chapitre précédent, quelques algorithmes de géocasting qui garantissent la réception du message par les destinataires. Ils sont particulièrement intéressant sur des surfaces planes et lorsque la région géocast est relativement petite. Notons cependant que, les capteurs sont caractérisés par une faible batterie et une petite mémoire de stockage dû à leur taille; par conséquent, le principal défi est de développer un protocole de géocasting économe en énergie et garantissant la réception du paquet à tous les noeuds de la région géocast. L'un de ces protocoles est celui de MYOUPO et al.[49] présenté au chapitre précédent. L'hypothèse émise par Myoupo et al. est que les capteurs sont déployés sur une surface plane. De plus, son concept de cluster est un peu abstrait, car un noeud appartenant à un cluster ne connait pas tous ses voisins. Nous allons donc utiliser ce protocole et l'adapter en 3 dimensions(3-D) i.e dans l'espace. Dans ce qui suit, Nous supposons les capteurs sont déployés dans l'espace défini par une sphère de rayon R. R est le rayon de transmission du noeud sink, qui est le seul élément du réseau capable de communiquer directement avec n'importe quel capteur du réseau. La figure 5.1 montre un réseau de capteur déployé dans l'espace.

FIGURE 5.1: Réseau de capteurs déployé dans l'espace

5.2 Notre approche de sécurité

L'approche adoptée est l'établissement d'une clé secrète entre deux ou plusieurs noeuds. C'est l'un des services de sécurité le plus important qui assure la confidentialité et l'intégrité

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

des échanges. C'est une technique hybride à la fois symétrique et asymétrique. On calcule des clés publiques ECC en utilisant le principe du logarithme discret. Le problème est exponentiel d'où la solution pour l'attaquant devient impossible à calculer (le problème est NP-complet) et l'algorithme devient intéressant pour la cryptographie. Les clés publiques sont échangées par les entités communicantes du réseau afin d'établir des clés symétriques [50] [51].

Cette approche de sécurité permet d'éviter entre autres les attaques telles que le Flooding attack, l'attaque du trou noir, la réplication des données, le sybil attack,le Jamming attack, l'écoute passive...

Dans cette partie, nous décrivons en détail les étapes de notre approche de sécurité. Elle s'effectue sur 03 niveaux : avant le déploiement, pendant la construction de notre topologie et pendant la phase de maintenance.

· Au pré-déploiement : la BS pré-charge chaque capteur avec un identifiant unique et une clé initiale K {n/bs};

· Au déploiement pendant la construction de la topologie : tous les échanges sont sécurisés par la clé K {n/bs} en utilisant des fonctions de hachage à sens unique (non réversibles) et des codes d'authentification MAC afin d'assurer l'intégrité, la confidentialité et l'authentification;

· Après la phase de clustering, pendant la maintenance : les noeuds communicants utilisent les clés symétriques générées lors de la construction de la topologie du réseau. Les clés symétriques sont révoquées et renouvelées après chaque détection de noeuds compromis. En effet, Le schéma de gestion de clés [52] est déterministe et permet de sécuriser toutes les étapes d'initialisation, de construction et de maintenance de l'architecture du réseau en garantissant des communications intra-cluster, inter-clusters, BS-CH, SB - Noeuds relais et CH - noeuds relais sécurisées.

Hypothèses :

1. Le réseau est connexe et totalement dense.

2. Le réseau est tel que la BS est placé au centre et les capteurs sont déployés aléatoirement autour de lui;

3. La BS est la seule station en qui on puisse faire confiance et qu'on ne peut pas compromettre;

4. Un attaquant peut opérer à n'importe quel niveau de la topologie du réseau mais ne peut jamais compromettre la BS.

5. Aucune contrainte n'est imposée sur les capacités en calcul, en stockage et en énergie de la station de base.

58

Notations et terminologies

59

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

· ID_a : Unique identifiant de 4 octets du noeud U.

· A- > B : M : Message M diffusé par A pour B

· WSN^* : l'ensemble des capteurs du réseau. .

· Kn/u : chaine de clé à sens unique de taille n + 1 générés par le noeud u.

· Ku, v : une clé secrète partagée entre les noeuds u et v.

· Kbs, u : une clé secrète partagée entre la station de base et un noeud u.

· MACK(M) : un message d'authentification de 8 octets généré au-dessus de M en utilisant la clef K.

· H : une fonction de hachage à sens unique (1aTESLA)

Les différents niveaux de sécurité sont :

5.2.1 Au pré-déploiement

La station de base génère d'abord une chaîne de clés K {n/bs} nécessaire pour effectuer des émissions à tous les capteurs authentifiés afin de former notre structure. Elle charge ensuite chaque capteur u avec un seul identifiant Id_a, avec une clé secrète Kbs, u partagé avec elle-même, afin d'assurer à l'avenir des communications unicast (pour garantir la confidentialité et l'authentification), et la première clé K {0/bs} de sa chaîne de la clé, afin de méner à bien les diffusions/émissions sur l'ensemble du réseau (nous utiliserons ,iTESLA pour garantir l'authentification). Enfin, la BS charge chaque noeud u avec l'établissement des clé matériel cryptographique établi avec tous ses voisins, pour sécuriser les communications entre paires de voisins. Deux noeuds voisins u et v partage une clé Ku, v

5.2.2 Phase de Construction

La phase de construction est celle pendant laquelle l'algorithme de clustering s'effectue. Pendant cette phase, les échanges sont sécurisées par la clé K {n/bs}, car c'est la BS - seule entité de confiance dans le réseau - qui est en charge de cette opération.

· La BS effectue une diffusion successive à l'aide de la clé K {n/bs} afin de communiquer d'une manière authentifiée des informations à tous les noeuds, selon différents angles et rayons. BS- > WSN^* : D, MACK(M)(D), K {j/bs} avec K {j/bs} la clé actuelle de la chaîne clé K {n/bs} et D le triplet d'entier à transmettre et correspondant à une certaine zone.

· Chaque noeud u reçoit alors le message et l'authentifie en utilisant la fonction de hachage irréversible H qu'il détient, et vérifie la correspondance K {j - 1/bs} = H(K {j/bs}). Une fois cette première étape terminée, le noeud vérifie l'authentification fournie par MAC jointe au message et est capable de mettre à jour sa dernière clé connue. Ceci est une simple application du protocole ,iTESLA.

60

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

· Après la formation des clusters vient la phase de découverte de voisinage et d'élection des CHs. Celle-ci est sécurisée à l'aide de la clé Ku, v partagée entre 2 noeuds u et v.

· A la fin de cette étape, tous les noeuds CH auront établis trois types de clés : une clé partagée avec la BS (Kch, bs) , une clé partagée avec chacun des noeuds du cluster (Kch, u) et une clé commune partagée avec tous les noeuds du cluster(K {n/ch}). Les noeuds membres établissent deux types de clés : une clé partagée avec le CH (Ku, ch) et une clé commune partagée avec tous les noeuds du cluster.

5.2.3 Phase de reconstruction

La reconstruction de la topologie du réseau se fait à chaque fois que le niveau en ressources énergétiques d'un noeud CH atteint un niveau beaucoup plus inférieur aux autres niveaux des autres noeuds du réseau. Cette constatation sera faite par la BS qui diffuse un message de reconstruction du cluster ayant pour chef le noeud à remplacer et l'identité du nouveau noeud CH du cluster. Ce dernier envoi un message en broadcast à tous les noeuds membres du cluster pour les informer de ce changement en leur notifiant l'identité du nouveau chef et en supprimant les clés partagées avec l'ancien CH et lancent des messages d'établissement et d'échange de clés avec le nouveau CH.

5.2.4 Phase de renouvellement

Cette mesure vise à renforcer la sécurité du réseau. la BS diffuse un message de renouvellement de clés. Ce message sera relayé par tous les noeuds CH. Chaque CH lance la procédure de renouvellement de clés avec ses noeuds membres du cluster. Durant la procédure de renouvellement, chaque CH calcule P_Y = gY mod p et le transmet à tous ses noeuds membres et chaque noeud membre calcule son P_x = g^x mod p et le transmet au CH. Les deux parties génèrent une clé de session en calculant (P_Y)^x du coté des noeuds membres et (P_x) du coté du CH (p est un grand nombre et g un point). Notons qu'avant le déploiement, la SB calcule toutes les clés publiques et les paramètres de génération des clés symétriques, et les charge dans chaque capteur [4].

5.2.5 Phase de révocation

La phase de révocation se déclenche à chaque compromission d'un noeud du réseau. Si le noeud compromis est un noeud membre d'un cluster, son CH supprime de sa mémoire la clé partagé avec lui, le place en quarantaine, ignore ses messages et le signale à la station de base pour ne jamais le désigner CH lors des phases de reconstruction du réseau. Si le noeud compromis est un CH, la station de base supprime la clé partagée avec lui, désigne un autre CH parmi les membres du cluster du CH compromis qui se charge d'informer et d'avertir tous les noeuds membres du cluster. Aussitôt informés, ils procèdent à la suppression des clés partagées avec

61

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

le CH compromis, ignorent ses messages, le mettent en quarantaine et mettent à jour l'identité du nouveau CH.

5.2.6 Insertion des nouveaux noeuds

La BS pré-charge un nouveau noeud avec les valeurs (Id, k {n/bs}) et diffuse un message à tous les noeuds CH comportant l'identité du nouveau noeud à insérer. Après le déploiement, le nouveau noeud diffuse un message d'appartenance à un cluster et le noeud CH le plus proche du nouveau noeud vérifie son identité avec les identités des nouveaux noeuds à ajouter sur le réseau. Si l'identité du noeud est vérifiée, le noeud CH établit une clé de session avec lui.

Après avoir décris comment sera gérer la sécurité dans notre protocole, nous décrivons à présent dans les sections suivantes les détails du déroulement de notre approche de protocole de géocasting. Il se déroule en 2 étapes : formation sécurisée de la structure et protocole sécurisé de géocasting proprement dite.

5.3 Étape 1 : Formation sécurisée de la structure

5.3.1 Partitionnement sécurisé du réseau en cluster

Cette étape est initiée par la station de base qui, via des communications sécurisées, va partitionner le réseau en plusieurs clusters en utilisant le protocole de partitionnement en 3D présenté à la section 2.4.4.

Formation des couronnes : les capteurs enregistrent le numéro de leur couronne. La sécurité ici, est gérée à l'aide de la clé K {n/bs}. Et comme mentionnée à la section 2.4.4, la réception d'un message par un capteur est codée par 0 et la non-réception du message après un délai r est codée par la valeur 1.

Formation des sections horizontales : les capteurs enregistrent le numéro de leur section horizontale. De même, les communications seront sécurisées à l'aide de la clé K {n/bs} tout en respectant le principe proposé à la section 2.4.4.

Formation des sections verticales : les capteurs enregistrent le numéro de leur section verticale. Comme précédemment, les communications sont sécurisées à l'aide de la clé K {n/bs}.

Les clusters sont donc obtenus après la formation des couronnes, des sections horizontales et des sections verticales. Ainsi, un cluster est constitué des capteurs ayant les mêmes coordonnées géographiques et est noté cluster (i, j, k) où i,j et k sont les numéro de la couronne, section horizontale et verticale respectivement.

62

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

5.3.2 Identification des noeuds

Soit n le nombre de capteurs dans le réseau. Chaque capteur peut avoir un identifiant compris entre 1 et n³ avec une probabilité supérieure à e^O(-1/ⁿ⁾)[48] tel que deux capteurs quelconques n'aient pas le même identifiant.

5.3.3 Découverte de voisinage

Après la formation des clusters, il est question ici de montrer comment chaque noeud découvre ses voisins du cluster . Cette phase de découverte est initiée par le noeud sink et se déroule en 2 étapes : l'attribution des canaux de communication aux différents clusters et la découverte des voisins proprement dite.

Attribution du canal de communication aux clusters

Le sink attribue les canaux de communications aux différents clusters en se rassurant que deux clusters voisins n'utilisent pas le même canal. En effet, deux clusters sont voisins s'ils ont une arête commune. Pour respecter ce principe,le noeud sink applique l'algorithme de coloration de graphe qui consiste à assigner une couleur à chaque sommet d'un graphe de sorte que deux sommet adjacents ont des couleurs différentes tout en minimisant le nombre de couleurs utilisées. En considérant un cluster comme un sommet et une couleur comme un canal dans notre cas, il revient à assigner un canal à chaque cluster de sorte que deux clusters adjacents ont des canaux différents. La notion d'adjacence dans ce cas étant renvoyée à celle de voisinage entre 2 clusters , car 2 clusters sont dits adjacents s'ils ont une arête en commun ou si la distance les séparant est inférieure à la distance D de réutilisation de canal. On démontre facilement

_s,_/

que D = R 3N [53]. R étant le rayon du cluster et N sa taille (i.e le nombre de cellule qu'il contient) A la fin de cette étape, les stations sauront dans quel canal effectuer la diffusion en vue de découvrir leurs voisins dans le cluster. Ainsi, lorsque la clique j sera en possession du canal i, ses stations utiliseront le mécanisme CSMA/CA pour effectuer des diffusions.

Diffusion

Après avoir pris connaissance du canal où ils transmettront leur message, les noeuds peuvent alors commencer la diffusion en utilisant le mécanisme CSMA/CA. Chaque message envoyé est constitué de l'identifiant de la station émettrice du message. Lorsque un noeud fait une diffusion pour la 1^ère fois, il écoute le réseau. A la réception du précédent message, chaque noeud enregistre l'identifiant contenu dans le message. Ainsi, à la fin des différentes diffusions, Toutes les stations auront enregistré les identifiants de tous leurs voisins.

63

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

5.3.4 Construction et Définition de notre arbre couvrant le graphe

Comme le montre la figure 5.2, notre réseau a plusieurs niveaux. Afin de permettre l'information d'arriver chez le noeud Sink, il est nécessaire de mettre sur pied des protocoles de routage.

L'idée est la suivante : l'information est routée dans son propre secteur angulaire (intersection entre une section horizontale et une section verticale) à travers un chemin virtuel reliant le noeud Sink au secteur le plus éloigné de celui-ci. La collection de tous ces chemins virtuels (un par secteur angulaire) définit un arbre dont la racine est le noeud sink. Quelques propriétés de cet arbre sont les suivantes :

· Le noeud sink a autant de fils que de secteur angulaire.

· Il existe une communication directe en un saut entre le noeud sink et ses clusters voisins

· Le nombre de fils d'un cluster est au plus 1.

· Chaque noeud interne (sauf le noeud racine qui est le noeud sink) a exactement un fils; ce qui permet d'éviter plusieurs disputes lors de l'envoi des données. La figure 9 décrit la structure de notre arbre

FIGURE 5.2: petit aperçu de la structure de notre arbre

5.3.5 Routage sécurisé inter-cluster

Nous supposons qu'après le partitionnement, le réseau est totalement dense, i.e qu'il existe au moins un capteur dans chaque cluster. Ainsi, les capteurs d'un cluster de coordonnées (i,j, k) peuvent directement communiquer avec ceux du cluster de coordonnées (i - 1, j, k). Or nous savons que les capteurs des clusters de coordonnées (1, j, k) peuvent directement communiquer avec le noeud sink de coordonnées (-1, -1, -1), qui est en fait la destination finale des paquets qui transitent dans le réseau. De façon successive donc, les données peuvent être acheminées du cluster de coordonnées (i,j, k) aux clusters de coordonnées (i - 1,j, k), (i - 2,j, k), ..., (1,j, k).

64

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

FIGURE 5.3: Routage dans un réseau dense

Les capteurs des clusters de coordonnées (1, j, k) pourront alors à leur tour envoyer ces données au noeud sink. Afin d'économiser de l'énergie, les capteurs ne sont pas tout le temps éveillés; ils peuvent automatiquement passer en mode veille pendant un certain temps et passer en mode éveillé pendant une période bien définie en exécutant le protocole d'accès au canal de Nakano et al. [54]. Pendant que les capteurs sont éveillés, il y a deux actions possibles :

Un événement se produit : les capteurs du cluster de coordonnées (i, j, k) construisent un message contenant le code de l'événement et leurs coordonnées, et les envoient à en direction du cluster (i - 1, j, k) ou directement au noeud sink si leur cluster est de coordonnées (1, j, k).

Réception d'un message : le capteur du cluster (i, j, k) vérifie s'il en est le destinataire; si c'est le cas, il l'achemine tout simplement au cluster (i-1, j, k) ou au noeud sink si son cluster est de coordonnées (1, j, k). Si ce n'est pas le cas, il l'ignore tout simplement. La figure 5.3 montre comment les données sont routées entre les clusters. En réalité la notion de cluster est virtuelle, ce sont les capteurs qui détectent les événements, envoient et reçoivent les messages. Comme les capteurs ont une source d'énergie limitée, il faut les empêcher de diffuser anarchiquement et inutilement les données.

Principe de l'algorithme de réservation du canal de Nakano et al. Étant donné que les noeuds ont déjà découvert leur voisinages, Pour pallier aux problèmes de collisions et de retransmission des paquets qui influent sur la durée de vie des capteurs dans un réseau, la technique de réservation de canal de Nakano et al.[54] est utilisée. L'idée de base de cette méthode est qu'un capteur n'est éveillé que s'il émet ou reçoit des paquets. Soit un réseau de capteurs sans fil disposant de p capteurs C(1), C(2), C(3), ..., C(p - 1), C(p). Supposons que pour tout i, tel que 1 < i < p, chaque capteur C(i) possède ni paquets à transmettre. Au début de l'algorithme, seul le capteur C(i) connait ni. Au premier intervalle de temps, le capteur C(1) transmet le nombre de paquets n1 qu'il dispose. Pendant ce même intervalle, tous les autres capteurs sont endormis à l'exception du capteur C(1) qui transmet et du capteur C(2) qui reçoit n1. C(2) calcule ensuite n1 + n2 et transmet le résultat à C(3). Durant cet intervalle de temps

65

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

tous les autres capteurs sont endormis excepté C(2) qui émet et C(3) qui reçoit. De la même manière, lorsque C(3) reçoit n1 +n2 , il calcule n1 +n2 +n3 et envoi le résultat au capteur C(4). Ce processus est réitéré p-1 fois et à la fin, le capteur C(p) calcul n1+n2+n3+...+np_2+np_1. De manière précise, un capteur C(i) calcule n1 + n2 + n3 + ... + _{ni_2} + _{ni_1} et il se réveille au tempsn1 + n2 + n3 + ... + _{ni_2} + _{ni_1} + 1 pour commencer à transmettre les informations qu'il dispose. Dès que sa transmission est terminée, il se rendort. A la fin de cet algorithme, chaque capteur est à mesure de déterminer de manière exacte le nombre de slots qu'il utilisera pour transmettre les capteurs qui le précède. Ce protocole de réservation de canal se termine en p-1 intervalles de temps et aucun capteur n'est éveillé pendant plus de deux intervalles de temps.

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).

5.4 Étape 2 : Protocole sécurisé de géocasting

Le protocole de geocasting comporte deux phases. Ici, la BS possède l'information à envoyer aux noeuds situés dans la région géocast. L'objectif de la première phase de notre protocole est la découverte de ces noeuds. La seconde phase consiste en l'envoi d'informations depuis la BS. Considérons les hypothèses suivantes :

1. Le réseau est statique, connexe et toujours connecté;

2. La BS est la seule entité de confiance dans le réseau qui a une forte capacité énergétique que les autres noeuds, et dont la portée de transmission peut couvrir l'ensemble du réseau;

3. Chaque noeud partage une clé secrète avec la BS, qui est chargé avant le déploiement;

4. Chaque capteur est capable de se localiser dans l'espace en utilisant soit le GPS, soit la triangulation ou un système de positionnement pour un réseau ad hoc;

5. Les messages (diffusion) sont authentifiés grâce à une combinaison de signatures et de protocole de (1aTESLA). Les horloges des noeuds sont synchronisés, comme (1aTESLA) l'exige.

Phase 1 : Découverte de capteurs dans la région géocast

L'objectif pour la BS est de transmettre une donnée D à une zone géographique B. Cette phase consiste à la découverte des noeuds situés dans B.

70

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

Afin d'économiser de l'énergie et limiter le temps d'exécution de cette phase, précisons que le temps est divisé en slot S⁰, S¹, ..., Sⁿ. Si la source souhaite envoyer un paquet à tous les noeuds situés dans une région géocast, alors au slot Sⁱ, elle diffuse en direction de la BS ( seule entité à pouvoir prendre une décision par rapport au paquet) un paquet B, constitué du message et des spécifications de la région géocast. B = (REQUEST(Message, CoordomméesRegiomGéocast))

- Après avoir reçu le paquet B = (REQUEST(Message, CoordommeesRégiomGéocast, )), la BS va envoyer un message M de recherche contenant la définition de la région géocast à tous les clusterheads afin de savoir si ces derniers ont des noeuds situés dans la région géocast spécifiée dans le paquet. Ce message est accompagné d'une variable binaire 3 et authentifié à l'aide de la clé K {m/bs}. M = SEARCH(CoordomméesRégiomGéocast, 3, K {m/bs}). BS- > WSN^* : M, _{MACK{n/bs}(M),} K {j/bs} avec K {j/bs} la clé actuelle de la chaine de clés K {m/bs}.

- Les clusterheads à leur tour, envoie le paquet de recherche à tous les noeuds membres de leur cluster en utilisant la clé Kch, u. Chaque noeud u reçoit alors le message et contrôle son authenticité. Il est informé de la zone B requise et alors est capable de savoir s'il est situé dans cette zone ou pas (Hypothèse (4)). Dans le cas négatif, il ne fait rien. Dans le cas positif, il met la variable binaire 3 à1, puis envoie un accusé de réception à son CH, contenant B, authentifié en utilisant la clé (Kch, u) partagée entre CH et le noeud. u- > CH : B, _MACKch,u(B), Kch, u.

- Les CHs ayant reçu au moins une réponse positive, à leurs tours acheminent à la BS un paquet (SEARCH(CoordommeesRégiomGéocast, kbs, ch, 3 = 1)) avec 3 mis à 1. A la fin du slot Sⁱ, Si la BS a reçu des accusés de réception, alors elle sait où envoyer les données D à transmettre.

Phase 2 : Phase de diffusion

Pour chaque capteur u ayant répondu à la BS durant le temps slot Sⁱ, et étant ainsi située dans B, la BS est capable d'envoyer à ces capteurs en passant par leur clusterhead, les informations D, en l'authentifiant et la protégeant avec la clé Kbs, ch et pendant la tranche de temps slot Sⁱ⁺¹.

5.4.1 Geocasting avec plusieurs régions géocast

Sur la base du protocole décrit précédemment, qui fournit seulement une information à une seule zone, il est possible d'effectuer des recherches parallèles pour plusieurs zones, en remplaçant la zone B par une concaténation des différents zones : »b1, b2, ..., bm».

Theoreme 3. L'algorithme de regroupement géocast multi-niveaux ci-dessus garantit la livraison à tous les noeuds dans la région geocast

Preuve. Supposons qu'il y ait au moins un noeud dans la région géocast qui ne soit pas atteinte. Alors ce noeud a été déconnecté du réseau qui n'est plus connecté. Il n'est donc pas un réseau de capteur.

71

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

5.5 Analyse de la sécurité

Nous étudions ici plus en détail l'aspect sécuritaire de notre protocole. Le déroulement de la sécurité pour le protocole de formation a été expliqué plus haut et semble clair pour nous; nous passons directement sur le protocole de géocasting, décrit dans la section 5.4. En ce qui concerne la première phase de recherche de la région géocast,au cours de sa première étape, le protocole ,iTESLA est utilisé, ce qui permet une transmission depuis la BS authentifié. Chaque noeud recevant l'information est donc certain que c'est un élément d'information provenant de la BS, entité de confiance du réseau, et il n'y a d'erreur à ce sujet. A la fin de sa deuxième étape, les noeuds CH qui veulent envoyer un accusé de réception à la BS utilise la clé Kbs, ch. L'authenticité de l'ensemble étant assurée, il est impossible pour un noeud j situé entre u et la BS de modifier le contenu des paquets. De la même manière, si un tel noeud ne souhaite pas transmettre l'information qui lui est transmise, le noeud u est capable de détecter l'erreur après un certain temps, car il a été informé qu'il recevra un message dans la Phase 2. À la troisième étape, la BS est une entité de confiance : il n'y a pas risque d'attaque. La deuxième phase consiste à envoyer des informations à un noeud u situé dans B : la BS utilise la clé Kbs, ch pour chiffrer et authentifier D à transmettre. Notre protocole garantit que s'il y a une tentative de modifier, supprimer ou changer le chemin d'une donnée, c'est détectable par la BS. La majorité des attaques externes sont ainsi évités, et les compromettants des noeuds CH sont également détectable.

5.6 Analyse de la consommation de l'énergie

Le modèle utilisé dans ce travail est similaire à celui qui a été adopté par plusieurs contributions efficientes à l'instar de[55].

E = ET + ER = Nx(et + _eampdn) + Nxe_r

Où ET et ER sont les énergies totales utilisées respectivement pour les transmissions dans le réseau et les réceptions. Les énergies dissipées par l'émetteur, l'amplificateur et le récepteur radio sont respectivement exprimées par et, _eamp et e_r ; d est la distance entre les noeuds et n est le paramètre d'atténuation d'énergie (2 < n < 4). A partir de ce modèle, une pseudo évaluation peut être faite dans les différentes phases de ce protocole :

Réduction de la consommation de l'énergie durant la phase de partitionnement : la consommation d'énergie peut être étudié sous différents niveaux. d'une part, dans un cluster, chaque élément est à un saut de l'autre. Ceci contribue à gaspiller moins d'énergie lors des transmissions intra-cluster. De plus n'importe quel noeud peut prétendre au poste de cluste-rhead si son niveau de batterie lui permet. D'autre part, c'est la station de base qui prend en charge la plupart des actions nécessaire pour la formation des clusters, qui assure la plus faible consommation d'énergie sur l'ensemble du réseau, tout en offrant une certaine sécurité.

72

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

Logiquement, la BS est une entité ayant plus d'énergie que d'autres capteurs.

Réduction de la consommation de l'énergie pendant la phase de diffusion intra-cluster : l'étude de la consommation d'énergie correspondant à notre structure étant fait, il nous reste à étudier le protocole de geocasting, qui se compose de 3 étapes principales. Tout d'abord une diffusion faite par la BS sur l'ensemble du réseau se fait en demandant à tous d'indiquer s'il est dans la région géocast ou non. Ensuite, suit une transmission possible d'un accusé de réception à plusieurs sauts d'un ou plusieurs CH vers la BS. Finalement, l'envoi d'information à plusieurs niveaux de la BS à ces CH est effectué pendant que les capteurs qui ne sont pas concernés sont endormis. L'énergie utilisée est donc vraiment minimisé. Enfin, notons que le geocasting est effectuée en utilisant des tranches de temps (slot), qui peut être utilisé comme slot de capteurs d'éveil. Certainement, pour un geocasting dans une zone B impliquant seulement un seul capteur, la consommation d'énergie d'un noeud est au moins e_r et au maximum 2x(et + _eampxdn) + 3Xe_r.

5.7 Implémentation et Analyse des résultats

Dans cette sous section, nous présentons les résultats des simulations de notre algorithme de partitionnement pour montrer l'influence de l'heuristique mise en oeuvre pour le choix du clusterhead et de la solution de sécurité. Ces simulations ont été exécutées sur un laptop (Core i2-950B CPU@ 2.10Ghz x2, 4GO de RAM, Ubuntu 12.04 LTS ) en utilisant le logiciel WSNet [56] et sont basés sur la zone sphérique de 9km de diamètre, sur lequel nous générons au hasard des réseaux connectés de 500 et 1000 capteurs. Le simulateur NS-2 a été utilisé pour le modèle énergétique et les courbes ont été réalisées grâce à l'outil Gnuplut version 4.3.

Nous avons comparé notre solution de sécurité et de gestion de clés à une solution combinant les approches probabilistes et dites t-secure (dont les principaux inconvénients sont l'absence d'authentification entre chaque paire de noeuds et le problème d'espace mémoire réservé aux clés stockées). Les problèmes du nombre et de la taille des paquets de données échangés durant les phases de déroulement du protocole (découverte de voisinage, installation des clés, renouvellement des clés et insertion des nouveaux noeuds) ainsi que le problème de la consommation d'énergie par les noeuds capteurs sont deux concepts majeurs déterminant la durée de vie d'un réseau de capteurs sans fil (RcSF). C'est pour cette raison que la plupart des solutions proposées essayent davantage de réduire le nombre de messages émis et reçus et la quantité d'énergie consommée dans les opérations cryptographiques durant tout le cycle de vie du réseau. Dans la littérature, l'idée de combiner le modèle probabiliste avec les schémas dits t-secure est illustrée par le protocole TinyKeyMan [57]. En adoptant les deux modèles, TinyKeyMan souffre de quelques inconvénients : A chaque construction ou reconstruction de routes pour une installation ou une mise à jour des clés, le nombre de paquets échangés entre les noeuds accroit

73

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

rapidement avec la taille du réseau et la probabilité que deux noeuds partagent un même secret ou trouvent un voisins commun pour établir une clé symétrique devient de plus en plus faible. Par conséquent, on peut dire que ces deux approches combinées n'offrent pas de compromis entre la taille du réseau et le nombre de messages échangés. Dans ce contexte, nous avons présenté une nouvelle solution déterministe qui assure une probabilité complète (100%) d'établir une clé symétrique entre chaque paire de noeuds sans le partage d'aucune information. Ce gain de messages transmis et reçus est synonyme d'une consommation réduite de l'énergie. Les opérations de calcul de secrets et de clés sont également optimisées pour une consommation raisonnable de ressources physiques et énergétiques des noeuds capteurs. Dans ce qui suit, nous allons présenter les métriques et paramètres utilisés, la librairie TinyKeyMan, et les résultats obtenus par rapport à ces métriques et en fonction du nombre de noeuds du réseau.

5.7.1 Les métriques

Pour l'évaluation des performances de notre solution, nous nous basons sur les métriques suivantes :

· Le nombre de clés stockées dans la mémoire des noeuds capteurs.

· La taille des clés stockées dans la mémoire des noeuds capteurs.

· Le nombre de paquets de données échangés durant les différentes phases de déroulement du protocole : initialisation (découverte du voisinage), installation des clés symétriques, révocation des clés découvertes par les noeuds intrus, renouvellement des clés et insertion des nouveaux noeuds.

· La consommation d'énergie moyenne par tous les noeuds du réseau en fonction de la taille du réseau.

· La consommation d'énergie par composant : énergie consommée durant les opérations de calcul des clés et l'énergie consommée pour l'émission / réception des paquets de données. Le nombre de clés stockées dans la mémoire des noeuds est obtenu par l'exécution de notre protocole de sécurité et de gestion de clés sur le protocole LEACH [58], considéré comme la référence des protocoles hiérarchiques et qui convient mieux aux besoins en simulation de notre solution.

La taille des clés ECC présentes dans la mémoire des noeuds capteurs et utilisées par notre protocole de sécurité et de gestion de clés est calculée sur la base des données présentées sur le tableau 5.1 :

5.7.2 Nombre et la taille des clés stockées

Dans le tableau 5.2, nous avons calculé le nombre et la taille des clés stockées par un noeud Cluster Head (CH) et par un noeud normal membre d'un cluster dans une topologie hiérarchique. Dans cette topologie, chaque noeud CH partage trois types de clés : i) une clé partagée avec son noeud parent dans la hiérarchie, ii) une clé partagée avec chacun des noeuds de son cluster et iii)

74

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

Taille du nombre premier P	160 bits
Taille du secret x	< 160 bits
Taille d'un point Px	320 bits
Taille d'une clé publique	320 bits
Taille d'une clé privée	160 bits

TABLE 5.1: Taille des clés ECC et de leurs paramètres de calcul

une clé commune partagée avec tous les noeuds de son cluster. Un noeud membre d'un cluster partage deux types de clés : i) une clé personnelle avec son CH et ii) une clé commune avec son CH et tous les autres noeuds du cluster. On note que tous les noeuds du réseau partagent entre eux à la phase d'initialisation une clé commune qui sert à authentifier et sécuriser toutes les communications durant la phase d'installation des clés par paires. Cette clé n'est pas prise en compte car elle sera supprimée à la fin de la phase d'initialisation et d'installation des clés. La taille des clés est calculée selon les informations données par le tableau 5.2 ci-dessus. Le tableau 5.2 donne le nombre et la taille des clés stockées par chaque noeud du réseau où N_c est le nombre moyen de noeuds d'un cluster.

Type du noeud	Nombre de clés stockées	Taille des clés stockées
Noeud CH	(Nc + 2)	20 (Nc + 2) octets
Noeud membre	2	40 octets

TABLE 5.2: Le nombre et la taille des clés stockées dans notre méthode

5.7.3 Nombre de paquets échangés

Les figures 5.4 et 5.5 présentent le nombre de paquets de données échangés lors de l'installation des clés sur des réseaux de taille variant de 100 à 1000 noeuds capteurs en présence ou non de noeuds attaquants. Les messages échangés concernent ceux des opérations d'authentification, de découverte de voisinage et de calcul des clés secrètes. Les deux figures ci-dessus résument les résultats obtenus après avoir réalisé différentes expériences. Sur la figure 21 où on suppose l'absence de noeuds attaquants, la complexité en communication de notre protocole est meilleure.

Dans la figure 5.5 où on suppose la présence de 10% de noeuds attaquants de l'ensemble des noeuds du réseau, le nombre d'informations échangées par radio est beaucoup plus important (environ une différence de 500% de paquets) et cela est dû à la diffusion d'un grand nombre de fausses informations de contrôle. Chaque noeud du réseau essaye alors d'authentifier l'émetteur puis d'ignorer ses futurs messages dans le cas d'une intrusion. Dans le protocole TinyKeyMan, les informations produites par les noeuds malicieux comportent une forte probabilité de partage d'un même polynôme ce qui touche à un plus grand nombre de noeuds. Notre solution échange

75

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

FIGURE 5.4: Nombre de paquets échangés en absence d'intrus

moins de paquets pour installer les clés ce qui garantie un temps d'installation plus court et un
niveau de sécurité plus élevé. Sur la figure 5.4 où on suppose l'absence de noeuds attaquants,

FIGURE 5.5: Nombre de paquets échangés en présence d'intrus

la complexité en communication de notre protocole est meilleure notamment pour des réseaux denses comme les RCSF et sont négligeables pour les réseaux de petite taille. Notre solution échange moins de paquets, environ 10 fois moins que la solution probabiliste du protocole TinyKeyMan.

5.7.4 Consommation d'énergie

Tenant compte du modèle énergétique que nous utilisons et de l'analyse de la consommation de cette dernière, nous remarquons que c'est le cluster-head qui dépense le plus d'énergie, car c'est lui qui fait plus de transmissions de paquets dans son cluster. Ceci est illustré par la courbe de la figure 5.6 où nous pouvons observer que l'énergie du cluster-head décroit plus rapidement que celle d'un noeud ordinaire. Nous avons utilisé les moyennes des dépenses énergétiques des cluster-head et des capteurs ordinaires pour réaliser cette courbe. Nous supposons que chaque noeud dispose de 100 unités d'énergie. L'émission et la réception d'un paquet d'information coûtent chacune une unité d'énergie. On suppose aussi que lorsqu'un capteur est éveillé, il

76

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

FIGURE 5.6: Évolution de l'énergie des capteurs

dépense un dixième de son énergie. Les courbes de la figure 5.7 illustre les différents scénario de l'évolution de l'énergie des capteurs lors du déroulement de deux protocoles de géocasting dans les RCSFs à multiples sauts à savoir le protocole présenté dans les travaux de Myoupo et al. [49] et notre protocole.

FIGURE 5.7: Évolution de l'énergie lors du déroulement de deux protocoles avec 400 capteurs

On remarque que l'approche que nous avons utilisé en 3D et dans laquelle chaque capteur découvre ses voisins du même cluster consomme moins d'énergie que l'approche présentée en

77

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

[49] dans laquelle la notion de cluster est un peu abstraite et statique. .

5.8 Conclusion

La solution présentée dans cet article est notre approche sécurisé pour la résolution du problème de géocasting dans un RCSF déployé dans l'espace. La structure virtuelle sur laquelle notre protocole est basé permet une utilisation répartie du réseau, et particulièrement l'utilisation efficace, pour un contrôle toujours assurée par la BS. La solution de sécurité est une fonction de gestion de clés basée sur la cryptographie sur les courbes elliptiques (ECC) pour générer des clés symétriques et résoudre le problème d'échange de clés entre les noeuds capteurs du réseau après leur déploiement. Elle évite la majorité des attaques. En plus de combiner l'aspect essentiel de la sécurité, notre protocole est rapide et économe en énergie; elle présente une connectivité totale, une génération réduite du nombre et de la taille des paquets échangés ainsi qu'une consommation minimisée d'énergie comparativement aux autres méthodes.

78

Chapitre 6

Conclusion Générale

Sommaire

6.1 Bilan 78

6.2 Perspectives 79

6.1 Bilan

L'essor des technologies sans fil a rendu possible aujourd'hui, la manipulation de l'information à travers des dispositifs qui ont des caractéristiques particulières et qui se mettent en réseau via une interface de communication sans fil. Les réseaux de capteurs sans fil peuvent être identifiés comme l'une des technologies clefs de l'avenir en raison de l'incroyable potentiel applicatif qu'elle renferme. Mais à cause de la jeunesse de cette technologie, le domaine de RCSF soulève encore d'importantes problématiques comme la gestion de l'énergie, la gestion de la sécurité et la prise en compte d'un espace de déploiement présentant des irrégularités. Pour ce fait, Il était question pour nous dans ce mémoire, de concevoir un protocole efficace et sécurisé pour la gestion du routage géographique dans un RCSF déployé dans l'espace. Pour atteindre notre objectif, nous avons commencé par présenter les enjeux, les caractéristiques et quelques domaines d'application des RCSFs. Puis, après avoir passé en revue de littérature quelques protocoles de sécurité et de partitionnement des RCSFs, nous avons étudié quelques protocoles de géocasting existants dans la littérature à l'instar du protocole de Seada et al., de Stojmenovic, de A.B. Bomgni et al. et enfin de Myoupo et al.. Ceci nous a permis de prendre connaissance de ce qui a déjà été fait dans notre domaine d'étude et d'y apporter notre contribution. Pour cela, nous nous sommes basés sur une des limite du protocole présenté dans les travaux de Myoupo et al. [49] qui suppose ses capteurs déployés sur une surface plane et sur un concept de cluster un peu abstrait.

Nous avons pu mettre sur pied un protocole qui est en même temps économe en énergie et sécurisé, par lequel chaque capteur apprend ses coordonnées et découvre ses voisins. Par la suite, nous avons montré comment le routage des données pouvait facilement être mis sur pied grâce

79

CONCLUSION GENERALE

à notre architecture virtuelle bien formé. La solution de sécurité est une fonction de gestion de clés basée sur la cryptographie permettant de générer des clés symétriques afin de résoudre le problème d'échange de clés entre les noeuds capteurs du réseau après leur déploiement. Cette solution garantit un niveau de sécurité élevé en utilisant des clés de petites tailles.

La solution proposée dans ce mémoire est une approche de service sécurisé permettant d'effectuer de manière simple et rapide le geocasting dans un RCSF. La structure virtuelle sur laquelle notre protocole est basé permet une utilisation répartie du réseau, et particulièrement l'utilisation efficace, pour un contrôle toujours assurée par la BS.

6.2 Perspectives

Malgré les résultats assez encourageants que nous laissent observer nos simulations, plusieurs problèmes restent tout de même ouverts. Une ouverture à explorer serait de produire un algorithme tolérant aux fautes pour le problème de géocasting en dimension 3, ce qui garantirait que les stations normales recevront en temps fini les paquets qui leurs seront destinés; une autre perspective à long terme serait de créer un environnement de sécurité pour la résolution de ce problème en prenant en compte le fait que la station de base ne soit pas au centre du réseau et qu'elle ne peut non plus atteindre tous les noeuds. Il serait également intéressant d'étudier le problème en incluant certains noeuds mobiles dans le réseau.

80

Bibliographie

[1] Idrissa Sow. Partitionnement et Géocasting dans les Réseaux Mobiles Ad Hoc et Collecte de données dans les Réseaux de Capteurs Sans fil. Phd thesis, Université de PIRCARDIE JULES VERNES, Juin 2009.

[2] Malick GAYE. Etat de l'art sur les réseaux de capteurs sans fil. Technical report, Université Cheikh Anta DIOP de DAKAR, 2014.

[3] Alex Landry FOUTHE WEMBE. Un nouveau protocole de routage par permutation dans les réseaux mobiles de capteurs sans fil a multiple sauts economes en energie. Master's thesis, Université de Dschang, January 2014.

[4] RAMDANI MOHAMED. ProblÈmes de sÉcuritÉ dans les rÉseaux de capteurs avec prise en charge de l'Énergie. MÉmoire de magister, UNIVERSITÉ DE SAAD DAHLAB DE BLIDA, Novembre 2013.

[5] E. Cayirci. I.F. Akyildiz, W.S. Sankarasubramaniam. Wireless Sensor Network A survey on sensor networks. PhD thesis, IEEE Communications Magazine, Vol. 38, 40 (8), 8 Août 2002.

[6] Malick GAYE. Ab initio molecular dynamics for liquid metals. Technical report, Université Cheikh Anta DIOP de Dakar, Juin 2014.

[7] K.BOUCHAKOUR. Routage Hiérarchique sur les réseaux de capteurs sans fils protocole khlch(k-hop layered clustering hierarchy). Mémoire de magister, Ecole Nationale superieure de l'informatique, Republique algérienne, April 2012.

[8] H Woesner I. Chlamtac, I. Carreras. From internets to bionets :biological kinetic service oriented networks. The case study of Bionetic Sensor networks. CREATE-NET Research Consortium, Trento, Italy, 2005.

[9] S. Tariq. Mac algorithms in wireless networks. Master's thesis, Umea University, Sweden, www.cs.umu.se/education/examina/Rapporter/ShoaibTariq.pdf, December 2005.

[10] Karl H. and Willig A. Protocols and architectures for wireless sensor networks. John Wiley and Sons, Ltd, 2005.

[11] K. D.Wong. Physical layer considerationsfor wireless sensor networks. The 2004 IEEE International Conference on Networking, Sensing 8. Control Taipei. Taiwan, pages 2 :1201- 1206, March 2004.

81

BIBLIOGRAPHIE

[12] B.P. Mohapatra. K.B.Kredo. Medium access control in wireless sensor networks. Computer network 51(4), pages 961-994, 2007.

[13] K. Langendoen and G. Halkes. Embedded systems handbook, chapter 34 : Energy-effcient medium access control. CRC press, http // www.st.ewi.tudelft.nl/koen/papers/MAC - chapter.pdf, 2005.

[14] Kamal Beydoun. Conception d'un protocole de routage hiérarchique pour les réseaux de capteurs. Phd thesis, Université de Franche-Comté, France Novembre 2009.

[15] D. Song H. Chan, A. Perrig. Random key predistribution schemes for sensor networks. In IEEE Symposium on Security and Privacy, Berkeley, California, pages 197-213, May 2003.

[16] Y. S. Han S. Chen P . K. Varshney W. Du, J. Deng. A key management scheme for wireless sensor networks using deployment knowledge. In Proceedings of IEEE INFOCOM'04, Hong Kong : IEEE Press, pages 586-597, 2004.

[17] D.C Andrews, P. Johnson. Remote continuous monitoring in the home. telemedicine and telecare. Mémoire de master of sciences en informatique, school, Mars 2006. pp. 107-113.

[18] A. N. Badache D. Djenouri, L. Khelladi. A survey of security issues in mobile ad hoc and sensor networks, communications surveys tutorials. IEEE 7, No. 4, 2005.

[19] D.C. Petriu D. Makrakis V.Z. Groza. E.M. Petriu, N.D. Georganas. Sensor-based information appliances. IEEE Instrumentation Measurement Magazine. Vol. 3 (4), pages pp. 31-35, December 2000.

[20] Yaser Youssef. Routage pour la gestion de l'énergie dans les réseaux de capteurs sans fil. PhD thesis, Université de Hautes ALsaces, France Juillet 2010.

[21] Badreddine Guizani. Algorithme de clustérisation et de routage dans les réseaux Ad hoc. PhD thesis, Université de Technologie de Belfort-Montbéliard, 2012.

[22] KENFACK ZEUKENG Ulrich. Clusterisation et routage dans les réseaux ad hoc de capteurs sans fil. Master's thesis, Université de Dschang, 2016.

[23] J.T.C. Tsaï M. Gerla. Multicluster, mobile, multimedia radio network,. Wireless Networks 1(3), pages 255-265, 1995.

[24] Stefano Basagni. Distributed clustering for ad hoc networks. In Parallel Architectures, Algorithms, and Networks 1999.(I-SPAN'99) Proceedings. Fourth InternationalSymposium on, page 310-315, 1999.

[25] K.Sun P.Peng et P.Ning. Secure distributed cluster formation in wireless sensor networks. 22nd annual computer security application conference, page 131-140, Decembre 2006.

[26] L. Wilson M. Eltoweissy K. Jones A. Wadaa, S. Olariu. Training a wireless sensor network,. Mobile Networks and Applications 3, pages 151-168, 2005.

82

BIBLIOGRAPHIE

[27] Suman Banerjee et Samir Khuller. A clustering scheme for hierarchical control in multihop wireless networks. Proceedings of the 20th IEEE International Conference on Computer Communications,, page 1028-1037, Decembre 2001.

[28] K. BEYDOUN. Conception d'un protocole de routage pour les réseaux de capteurs. PhD thesis, L'U.F.R des sciences et Techniques de l'Université de FRANCHE-COMTE, 2009.

[29] Gilles Brassard et Paul Bratley. Algorithmique conception et analyse. Masson, 1987.

[30] Catégorie :Attaque réseau, http :// fr.wikipedia.org/wiki/Catégorie :Attaque_réseau.

[31] G. Kresse and J. Furthmüller. Wassin znaidi. quelques propositions de solutions pour la sécurité des réseaux de capteurs sans fil.phd thesi. Institut national des sciences appliquées de Lyon, 10 octobre 2010.

[32] J.P. Babau. W. Znaidi, M. Minier. An ontology for attacks in wireless sensor networks. Research Report RR-6704, INRIA, 2008.

[33] H. Guyennet D. Martins. Etat de l'art. sécurité dans les réseaux de capteurs sans fil. Manuscrit auteur, publié dans SAR-SSI 2008 : 3rd conference on security of network architect, 2008.

[34] Amar. Bensaber Boucif. Introduction à la sécurité dans les réseaux de capteurs sans fil.

[35] D. Wagner C. Karlof. Secure routing in wireless sensor networks : Attacks and countermeasures. Elsevier's AdHoc Networks Journal, Special Issue on Sensor Network Applications and Protocols., pages 293-315., 2008.

[36] D.B. Johnson Y.C. Hu, A. Perrig. Rushing attacks and defense in wireless ad hoc network routing protocols. Proceedings of the 2003 ACM workshop on Wireless security (New York, NY, USA), ACM Press., page 30-40, 2003.

[37] Mehdi DIOURI Mohammed. Réseaux de capteurs sans fils : routage et sécurité. PhD thesis, 2010.

[38] MARTINS David. Sécurité dans les réseaux de capteurs sans fils Stéganographie et réseau de confiance. PhD thesis, U.F.R. des sciences et techniques de l'université de France-Comté, Novembre 2010.

[39] K. Schosek S. Chellappan D. Xuan X. Wang, W. Gu. Sensor network configuration under physical attacks. In Xicheng Lu andWei Zhao, editors, ICCNMC.ol. 3619 of Lecture Notes in Computer Science, page 23-32., 2005.

[40] V. D. Gligor. B. Parno, A. Perrig. Distributed detection of node replication attacks in sensor networks. page 49-63., 2005.

[41] S. Mishra J. Deng, R. Han. Countermeasures against traffic analysis attacks in wireless sensor networks. In SECURECOMM '05 : Proceedings of the First International Conference on Security and Privacy for Emerging Areas in Communications Networks, page 113-126, 2005.

[42] Minier Marine. Quelques problèmes de sécurité dans les réseaux de capteurs. Laboratoire CITI, 2007.

83

BIBLIOGRAPHIE

[43] N. Vaidya Y. Ko. Flooding-based geocasting protocols for mobile ad hoc networks. Mobile Networks and Applications (MONET),, 7 :471-480, 2002.

[44] A. Helmy K. Seada. Efficient geocasting with perfect delivery in wireless networks. WNNC, IEEE, 2004.

[45] Karim Seada and Ahmed Helmy. Efficient and robust geocasting protocols for sensor networks. Computer Communications,, 29(2)(number) :151-161, 2006.

[46] Amiya Nayak Arnaud Casteigts and Ivan Stojmenovic. Multicasting, geocasting, and anycasting in sensor and actuator networks. Wireless Sensor and Actuator Networks,, page 127, 2010.

[47] Yunhao Liu Jie Lian, Kshirasagar Naik and Lei Chen. Virtual surrounding face geocasting with guaranteed message delivery for ad hoc and sensor networks. In Network Protocols, 2006. ICNP'06. Proceedings of the 2006 14th IEEE International Conference, pages 198-207, 2006.

[48] Alain Bertrand Bomgni. Qualité de services dans les protocoles de multicast géographique et de routage par permutation dans les réseaux de capteurs sans fil. PhD thesis, Université de Picardie Jules Verne, 28 Mars 2013.

[49] Sébastien Faye and Jean Frédéric Myoupo. Secure and energy-efficient geocast protocols for wireless sensor networks based on a hierarchical clustered structure. International Journal of Network Security,, 15(No.1) :121-130, Jan 2013.

[50] Ismail MANSOUR. Contribution à la sécurité des communications des réseaux de capteurs sans fil. PhD thesis, UNIVERSITÉ BLAISE PASCAL - CLERMONT II, 5 juillet 2013.

[51] H. Chan et A. Perrig. Pike: peer intermediaries for key establishment in sensor networks. In in Proceedings IEEE INFOCOM, volume vol. 1, p. 524 535 vol. 1. 4th Annual Joint Conference of the IEEE Computer and Communications Societies, 2005.

[52] M. Benmohammed M. Ramdani. Un nouveau schéma de gestion de clés basé sur les ecc pour les réseaux de capteurs sans fil. 2013.

[53] Reseaux et Télécommunication Réseaux GSM. 5e Edition Revuet et augmentée.

[54] K.Nakano S.Olariu A.Y.Zomaya. Energy-efficient permutation routing in radio networks. IEEE transactions on parallel and distributed systems,, page 544-577, Juin 2001.

[55] S. Kaplan D. Wei and H. A. Chan. Energy efficient clustering algorithms for wireless sensor networks. Proceedings of IEEE Conference on Communications, Beijing, pages 236-240, 2008.

[56] Wsnet, http :// wsnet.gforge.inria.fr/index.html, visité le 19 Mars 2016.

[57] P. Ning. D. Liu. Establishing pairwise keys in distributed sensor networks. In Proceedings of the 10th ACM Conference on Computer and Communications Security (CCS03), 2003.

[58] A. Chandrakasan W. Heinzelman and H. Balakrishnan. Energy efficient communication protocols for wireless microsensor networks. In in Proceedings of the 33rd Hawaiian International Conference on Systems Science, pages 3005-3014, January 2000.