Download pdf - WSN these

Rpublique Algrienne Dmocratique et Populaire

Universit Abou Bakr Belkaid Tlemcen

Facult desSciences

Dpartement dInformatique

Mmoire de fin dtudes pour lobtention du diplme de Master en

Informatique

Option: Rseaux et Systmes Distribus (R.S.D)

Thme Scurisation du protocole de routage

hirarchique LEACH dans les rseaux de

capteurs sans fil

Ralis par :

- CHARIF Meryem - BENYAGOUB Amina

Prsent le 19 Septembre 2013 devant le jury compos de MM.

- Mme DIDI Fedoua (Prsidente du jury)

- Mme LABRAOUI Nabila (Encadreur)

- Mme BELHABI Amel (Examinatrice)

- Mr BELHOUCINE Amine (Examinateur)

Anne universitaire: 2012-2013

Remerciement

Tout dabord, nos vifs remerciements notre encadreur Madame Labraoui Nabila de

nous avoir accord sa confiance et permis de raliser ce travail de recherche avec elle. A

travers ses qualits professionnelles, en tant que directrice de ce travail, elle nous a transmis

de prcieuses connaissances. Merci galement pour sa disponibilit, sa patience et sa bonne

humeur constantes qui ont rendu ce travail trs agrable et enrichissant, ainsi que pour sa

rigueur scientifique.

Nous remercions vivement Mme Didi .F qui nous a fait lhonneur daccepter la prsidence

de jury. Merci pour lattention constante quelle a porte notre travail.

Nous remercions galement Mme Belhabi.A. pour avoir voulu tre examinatrice.

Nous tenons galement exprimer nos profonds remerciements Mr Belhoucine. A.

pour lintrt quil a port notre travail

Enfin, nous adressons nos plus sincres remerciements tous nos proches et amis, qui nous

ont toujours soutenu et encourag au cours de la ralisation de ce mmoire.

Merci toutes et tous.

Table des matires

LISTE DE FIGURES ......................................................................................................................................... 4

LISTE DES TABLEAUX .................................................................................................................................... 5

INTRODUCTION ........................................................................................................................................... 1

CHAPITRE 1: ROUTAGE DANS LES RESEAUX DE CAPTEURS SANS FIL

1. INTRODUCTION ....................................................................................................................................... 1

2. PRESENTATION DUN CAPTEUR SANS FIL ................................................................................................. 1

3. COMPOSANTS DUN CAPTEUR SANS FIL................................................................................................... 2

4. RESEAUX DE CAPTEURS SANS FIL ............................................................................................................. 4

4.1 ARCHITECTURE.............................................................................................................................................. 4

TYPES DES NUDS ....................................................................................................................................... 5

5. DOMAINE DAPPLICATION ....................................................................................................................... 6

6. CARACTERISTIQUES DES RESEAUX DE CAPTEURS ..................................................................................... 7

7. FACTEURS DE CONCEPTION DE PROTOCOLES DE ROUTAGE ..................................................................... 8

7.1 TOLERANCE AUX PANNES ................................................................................................................................. 8

7.2 CONSOMMATION D'ENERGIE ............................................................................................................................ 8

7.3 LIMITATIONS DE CAPACITES DES NUDS ............................................................................................................. 8

7.4 SCALABILITE ................................................................................................................................................. 9

7.5 HETEROGENEITE ............................................................................................................................................ 9

7.6 MODELES DE TRANSMISSION DE DONNEES .......................................................................................................... 9

8. CLASSIFICATION DES PROTOCOLES DE ROUTAGE DANS LES RCSF .......................................................... 10

8.1 SELON LA TOPOLOGIE DU RESEAU .................................................................................................................... 11

8.2. SELON LA METHODE DETABLISSEMENT DE ROUTES ...................................................................................... 13

8.3 SELON LES PARADIGMES DE COMMUNICATION .................................................................................................. 13

8.4 SELON LE MODE DE FONCTIONNEMENT DU PROTOCOLE ....................................................................................... 15

8.5 SELON LE MODELE DE LIVRAISON DE DONNEES ................................................................................................... 16

9. CONCLUSION ......................................................................................................................................... 16

CHAPITRE 2: LE PROTOCOLE DE ROUTAGE LEACH: FONCTIONNEMENT ET SECURITE

1. INTRODUCTION ..................................................................................................................................... 19

2. ARCHITECTURE DE LEACH ...................................................................................................................... 19

3. ALGORITHME DETAILLE DE LEACH ......................................................................................................... 20

3.1 PHASE DINITIALISATION ......................................................................................................................... 20

3.1.1 Phase dannonce ......................................................................................................................... 21

3.1.2 Phase dorganisation de groupes ................................................................................................ 22

3.1.3 Phase dordonnancement ............................................................................................................ 22

3.2 PHASE DE TRANSMISSION ....................................................................................................................... 23

4.AVANTAGES ET INCONVENIENTS DE LEACH ............................................................................................ 23

4.1 AVANTAGES ......................................................................................................................................... 23

4.2 INCONVENIENTS ................................................................................................................................... 24

5. LES ATTAQUES CONTRE LEACH .............................................................................................................. 25

5.1 SINK HOLE ........................................................................................................................................... 25

5.2 SELECTIVE FORWARDING ........................................................................................................................ 25

5.3 HELLO FLOOD ...................................................................................................................................... 26

5.4 SPOOFED CLUSTER HEAD ....................................................................................................................... 26

6. CONCLUSION ......................................................................................................................................... 26

CHAPITRE 3: SECURISATION DU PROTOCOLE LEACH

1. INTRODUCTION ..................................................................................................................................... 29

2. LES DEFIS DE LA SECURITE ...................................................................................................................... 29

3. OBJECTIFS DE LA SECURITE POUR LEACH ............................................................................................... 29

3.1 AUTHENTIFICATION DE SOURCES DE MESSAGES .................................................................................................. 30

3.1.1 Diffrents types de transmissions scuriser ................................................................................. 30

3.1.2 Diffrents liens de communication scuriser ................................................................................ 30

4. MECANISMES DE SECURITE POUR LE PROTOCOLE SAFE-LEACH .................................................. 31

4.1 MECANISMES NECESSAIRES POUR LAUTHENTIFICATION DE SOURCES DE MESSAGES ................... 31

4.1.1 Protocoles de gestion de cls ........................................................................................................... 32

4.2 MECANISMES NECESSAIRES POUR LINTEGRITE DE DONNEES .................................................................................. 36

5. OUTILS UTILISES ..................................................................................................................................... 44

TINYOS ................................................................................................................................................... 44

NESC ...................................................................................................................................................... 44

6. LES COMPOSANTS DE LAPPLICATION .................................................................................................... 45

7. EVALUATION DE SAFE -LEACH ................................................................................................................ 47

7.1 METRIQUES DEVALUATION ............................................................................................................................ 47

7.2 GRAPHES DE SIMULATION .............................................................................................................................. 47

7.3 CONSOMMATION ENERGETIQUE ...................................................................................................................... 48

8. CONCLUSION ......................................................................................................................................... 50

CONCLUSION ............................................................................................................................................. 53

BIBLIOGRAPHIE .................................................................................................................................... 54

Liste de Figures

Figure 1. 1 : Schma interne dun Capteur sans fil [3]. ....................................................................... 2

Figure 1. 2 : Architecture dun capteur [2]. ......................................................................................... 3

Figure 1. 3 : Architecture gnrale dun rseau de capteurs sans fil [3]. ........................................... 5

Figure 1. 4: Diffrents types de sink [3]. ............................................................................................. 6

Figure 1. 5 : Classification des protocoles de routage dans les RCSF [14]. ....................................... 11

Figure 1. 6 : Topologie base de cluster [3]. .................................................................................... 12

Figure 2. 1 : Architecture du routage hirarchique LEACH [31]. ....................................................... 20

Figure 2. 2 : Oprations de ltape dinitialisation [32]..................................................................... 20

Figure 2. 3: Rpartition du temps et diffrentes phases pour chaque round [17]. .......................... 23

Figure 3. 1: Gestion de cls Nuds-puits. ........................................................................................ 34

Figure 3. 2: gestion de cls CH-Membres.......................................................................................... 35

Figure 3. 3 : Format dun paquet dans Safe-LEACH .......................................................................... 37

Figure 3. 4: Dclenchement et relai du nouveau round, annonce du CH 7. ...................................... 39

Figure 3. 5: Formation de groupes et envoi slots aux nuds membre. ........................................... 40

Figure 3. 6: Envoi des donnes captes au CH 7 qui les agrge au puits. ......................................... 40

Figure 3. 7 : lattaque Sink Hole. ....................................................................................................... 41

Figure 3. 8: Appartenance des nuds aux attaquants 17,18 et 19 dans LEACH. ............................. 42

Figure 3. 9: Dtection de lattaquant 17 dans Safe-LEACH. .............................................................. 43

Figure 3. 10 : Reprsentation graphique des composants de lapplication. ....................................... 46

Figure 3. 11: Evaluation de Safe-Leach ............................................................................................. 48

Figure 3. 12: nergie consomme pour chaque nud ....................................................................... 49

Figure 3. 13 : Energie consommes par le rseau. ............................................................................ 50

Liste des Tableaux

Tableau 3. 1 : Notations utilises par le protocole Safe-LEACH. ...................................................... 32

Tableau 3. 2 :Linformation transmise selon lmetteur. ................................................................. 37

Tableau 3. 3:Champs du paquet puits. .............................................................................................. 38

Tableau 3. 4:Champs du paquet membre. ......................................................................................... 38

Tableau 3. 5: Champs du paquet CH. ................................................................................................ 39

Tableau 3. 6 : champs additionnelles au paquet puits ....................................................................... 42

Tableau 3. 7 : champs additionnelles au paquet membre .................................................................. 42

Tableau 3. 8 : champs additionnelles au paquet CH ......................................................................... 43

Tableau 3. 9 : Consommation dnergie par les algorithmes Skipjack et RC5 [40]. .......................... 43

Tableau 3. 10 : Evaluation de Safe-Leach .......................................................................................... 47

Tableau 3. 11 : moyenne dnergie consomme par le rseau ........................................................ 49

Introduction

________________________________________________________________________________

-1-

Introduction

es avances technologiques ralises dans les domaines de la

microlectronique et de la communication sans fil ont permis

de concevoir et de fabriquer des composants miniaturiss,

autonomes et fiable tels que les capteurs. En effet, ces composants lectroniques classs

parmi les systmes embarqus, dploys sur une surface gographique importante formant

un rseau de nuds capteurs afin de collecter des informations sur des vnements bien

dfinis, et de les acheminer vers un nud particulier de traitement, appel puits (Sink) ou

bien station de base (BS). Les informations collectes servent construire une vision

globale de la zone couverte pour prendre des dcisions.

Dans ce mmoire, nous allons nous intresses aux problmes relatifs au routage de

donnes sur les WSNs et plus prcisment le routage hirarchique de donnes. Ce dernier

est considr comme un outil permettant plus de performance en ce qui concerne la

consommation de lnergie par rapport aux autres types de routage, savoir, le routage a

topologie plate et le routage gographique.

De nombreux protocoles de routage ont t proposs pour les rseaux de capteurs.

La plupart de ces protocoles supposent que tous les capteurs du WSN sont amicals et

coopratifs. Toutefois, cette hypothse n'est pas valable dans presque tous les rseaux.

Tous les priphriques ne sont pas amicaux. Et tous les dispositifs d'coute sont des

auditeurs passifs. Par consquent, pour prserver les bonnes oprations du rseau, la

scurit doit tre considre comme une composante essentielle du mcanisme de routage.

Notre projet consiste scuriser le protocole de routage LEACH, conu pour les

topologies des RCSF hirarchiques. Notre solution scurise doit garantir un compromis

entre simplicit et efficacit en performances.

Le prsent document est organis en trois chapitres.

Le premier est une introduction aux rseaux de capteurs. Il dfinit les concepts de

bases pour ces types de rseaux, leurs principales caractristiques aussi que ses domaines

dapplication et passe en revue les principaux facteurs et contraintes qui influencent la

conception des protocoles de routage au sein des RCSF.

Le second chapitre concerne LEACH qui est un protocole de routage conu aux

rseaux de capteurs mais qui nest pas scuris. Il prsente larchitecture et lalgorithme de

ce dernier et aussi les attaques pouvant perturber le fonctionnement de LEACH et les

diffrentes contre-mesures proposes pour les pallier.

L

________________________________________________________________________________

-2-

Le troisime chapitre concerne une solution de scurisation pour le protocole

LEACH. Il prsente le schma de scurisation, le droulement de notre protocole Safe-

LEACH et les rsultats d'implmentation et de tests de simulation de notre solution,

prcd par une prsentation des outils ncessaires pour notre ralisation savoir le

systme dexploitation TinyOS, le langage de programmation NesC et le simulateur

TOSSIM

________________________________________________________________________________

-3-

Chapitre 1

Routage dans les

rseaux de capteurs

Chapitre 1 Routage dans les Rseaux de Capteurs

________________________________________________________________________________

-1-

1. Introduction

Les progrs raliss ces dernires annes dans les domaines des microsystmes

lectromcaniques ainsi que des techniques de communication sans fil ont permis de voir

apparatre un nouveau type de rseau [1] : le rseau de capteurs sans fil (RCSF). Ces

rseaux sont composs dun ensemble de petits appareils, ou capteurs, possdant des

ressources particulirement limites, mais qui leur permettent de collecter et transmettre

des donnes environnementales (la temprature, lhumidit, la prsence dun gaz.etc.)

vers un ou plusieurs points de collecte.

Le routage est un service trs important dans les rseaux de capteurs. Il doit permettre

larrive des donnes la station de base avec le minimum de pertes et de dissipation

dnergie. Le problme de routage consiste dterminer un acheminement optimal des

paquets travers le rseau suivant certains critres de performance comme la

consommation nergtique.

Lutilisation des protocoles de routages conus pour les rseaux filaires ou encore les

rseaux mobiles Ad Hoc dans les RCSF est inapproprie. Ceci est en raison des

caractristiques par lesquelles se distinguent les deux types de rseaux, do la ncessit de

dvelopper de nouveaux protocoles de routage propre aux RCSFs.

Dans ce chapitre nous allons introduire et faire une description des rseaux de capteurs

sans fil, en prsentant leurs diffrents composants, larchitecture, les caractristiques,

leurs domaines dapplications, les deux types de topologies existants dans les rseaux de

capteurs : topologie plate et base de cluster, par la suite nous dfinissons galement les

principaux facteurs et contraintes qui influencent la conception des rseaux de capteurs sans

fil ainsi affectent la conception des protocoles de routage au sein des RCSF.

2. Prsentation dun capteur sans fil

Les capteurs sont des dispositifs lectroniques de taille extrmement rduite avec

des ressources trs limites, autonomes, capable de mesurer une valeur physique

environnementale (temprature, lumire, pression, etc.) et de la communiquer un centre

de contrle via une station de base [2]. La figure 1.1 illustre le schma interne dun capteur

sans fil.


________________________________________________________________________________

-2-

Figure 1. 1 : Schma interne dun Capteur sans fil [3].

3. Composants dun capteur sans fil

Un capteur sans fil est dot, principalement dune unit de : captage, traitement,

communication, stockage et nergie. Dautres modules peuvent tre ajouts selon le

domaine dapplication comme une unit de localisation, afin didentifier la position

gographique dun capteur tel quun GPS (Global Position System), un mobilisateur pour

que les capteurs puissent se dplacer et un gnrateur de puissance tel que des cellules

solaires afin daliment lectriquement le capteur sans avoir changer ses batteries [4]. Ces

lments principaux et optionnels sont visibles sur la figure 1.2.


________________________________________________________________________________

-3-

Figure 1. 2 : Architecture dun capteur [2].

1. Unit de captage : elle est constitue de deux composants, un dispositif qui intercepte les

donnes du monde physique et les transforme en signaux analogiques, et un convertisseur

analogique/numrique qui transforme ces signaux analogiques en un signal numrique

comprhensible par lunit de traitement [2].

2. Unit de traitement : elle est compose dun microprocesseur ou dun microcontrleur

associ gnralement une unit de stockage. Elle est charge dexcuter les protocoles de

Communication, comme elle peut aussi effectuer des semi traitements sur les donnes

captes [2].

3. Unit de communication : elle est responsable des missions et rceptions des donnes

sur un medium sans fil. Elle se base sur les technologies sans fil faible porte de

communication, Zigbee, Bluetooth ou Wifi [2].

4. Unit dalimentation nergtique : elle est responsable de la gestion de lnergie et de

lalimentation de tous les composants du capteur. Elle consiste, gnralement, en une

batterie qui est limite et irremplaable, ce qui a rendu lnergie comme principale

contrainte pour un capteur [2].


________________________________________________________________________________

-4-

4. Rseaux de capteurs sans fil

Un rseau de capteurs sans fil (RCSF) est un type particulier des rseaux ad hoc [5]. Il

est compos de centaines ou de milliers dlments nomms nuds ou capteurs placs de

manire plus au moins alatoire. Dans ces rseaux, chaque nud est capable de surveiller

son environnement et de ragir en cas de besoin en envoyant linformation collecte un ou

plusieurs points de collecte, laide dune connexion sans fil [6].

4.1 Architecture

Un rseau de capteurs est constitu essentiellement de : plusieurs nuds capteurs, un

nud Sink et un centre de traitement des donnes [3].

Nuds : Sont des capteurs, leur type, leur architecture et leur disposition

gographique dpendent de lexigence de lapplication en question. Leur nergie

est souvent limite puisquils sont aliments par des piles

Sink : cest un nud particulier du rseau. Il est charg de la collecte des donnes

issues des diffrents nuds du rseau. Il doit tre toujours actif puisque larrive des

informations est alatoire. Cest pourquoi son nergie doit tre illimite. Dans un

rseau de capteur sans fils plus ou moins large et charge un peu leve, on peut

trouver deux sinks ou plus pour allger la charge.

Centre de traitement des donnes : cest le centre vers lequel les donnes

collectes par le sink sont envoyes. Ce centre a le rle de regrouper les donnes

issues des nuds et les traiter de faon en extraire de linformation utile

exploitable. Le centre de traitement peut tre loign du sink, alors les donnes

doivent tre transfres travers un autre rseau, cest pourquoi on introduit une

passerelle entre le sink et le rseau de transfert pour adapter le type de donnes au

type du canal (comme cest illustr dans la figure 1.3).


________________________________________________________________________________

-5-

Figure 1. 3 : Architecture gnrale dun rseau de capteurs sans fil [3].

Types des nuds

Dans un rseau de capteurs il existe deux types de nuds : nud source et nud sink.

Un nud source est nimporte quelle entit dans le rseau qui peut fournir de linformation,

cest dire un simple nud capteur.

Un nud sink est lentit o les donnes sont rcupres. Il y a essentiellement trois types

de sink [3] :

Un nud appartenant au rseau comme nimporte quel autre nud.

Une entit extrieure au rseau. Pour ce deuxime cas, le sink peut tre un dispositif

extrieur, par exemple, un ordinateur portatif ou un PDA interagissant avec le

rseau.

Une passerelle vers un autre rseau tel quInternet, o la demande de linformation

vient dun certain centre de traitement lointain.


________________________________________________________________________________

-6-

Figure 1. 4 : Diffrents types de sink [3].

5. Domaine dapplication

Les rseaux de capteurs peuvent se rvler trs utiles dans de nombreuses applications,

Parmi les domaines o ces rseaux peuvent offrir les meilleures contributions, nous citons

les domaines : militaire, commercial, environnemental, mdical, architectural, etc. Des

exemples d'applications potentielles dans ces diffrents domaines sont exposs ci-dessous :

[1, 7].

1. Domaine militaire : les RCFSs sont utiliss pour la surveillance, la dtection des

intrusions, la dtection des substances dangereuses, la communication, la reconnaissance

et le ciblage exemple Shotspotter.

2. Domaine commercial : les capteurs peuvent tre utiliss pour le contrle

environnemental des btiments, pour permettre une meilleure gestion des ressources

faibles couts. Un autre exemple est celui de lutilisation des capteurs dans des muses

scientifiques pour un apprentissage plus rapide des visiteurs.

3. Domaine environnemental : dans ce domaine, les capteurs peuvent tre exploits pour

dtecter les catastrophes naturelles (feux de forets, tremblements de terre, ), traquer les

mouvements des animaux et surveiller les conditions denvironnement qui affectent les

rcoltes, les stocks et tout autre systme dagriculture.

4. Domaine mdical : parmi ses applications, on peut citer la surveillance, ltat des

patients et le taux de mdicaments qui leur ont t administrs, et laide la localisation

des mdecins et des patients au sein dun hpital.


________________________________________________________________________________

-7-

5. Domaine architectural : transformation des btiments en environnements intelligents

capables de reconnaitre des personnes, interprter leurs actions et y ragir.

6. Caractristiques des rseaux de capteurs

Parmi les caractristiques les plus importantes dun rseau de capteurs, nous citons [8] :

La dure de vie limite :

Les nuds capteurs sont trs limits par la contrainte dnergie, ils fonctionnent

habituellement sans surveillance dans des rgions gographiques loignes. Par consquent

recharger ou remplacer leurs batteries devient quasiment impossible.

Ressources limites :

Habituellement les nuds capteurs ont une taille trs petite, ce facteur de forme limite la

quantit de ressources qui peuvent tre mises dans ces nuds. En consquence, la capacit

de traitement et de mmoire est trs limite.

Topologie dynamique :

La topologie des rseaux de capteurs change dune manire frquente et rapide car: les

nuds capteurs peuvent tre dploys dans des environnements hostiles (par exemple un

champ de bataille), la dfaillance dun nud capteur peut donc tre trs probable. De plus,

les nuds capteurs et les nuds finaux o ils doivent envoyer linformation capture

peuvent tre mobiles.

Agrgation des donnes :

Dans les rseaux de capteurs, les donnes produites par les nuds capteurs sont trs

relies, ce qui implique lexistence de redondances de donnes. Une approche rpandue

consiste agrger les donnes au niveau des nuds intermdiaires afin de rduire la

consommation dnergie lors de la transmission de ces donnes.

La scalabilit :

Les rseaux de capteurs engendrent un trs grand nombre de capteurs, ils peuvent

atteindre des milliers voir des millions de capteurs. Le dfi relever par les RCFSs est

dtre capable de maintenir leurs performances avec ce grand nombre de capteurs.


________________________________________________________________________________

-8-

Bande passante limite :

En raison de la puissance limite, les nuds capteurs ne peuvent pas supporter des

dbits levs.

Scurit physique limite:

Cela se justifie par les contraintes et limitations physiques qui minimisent le contrle des

donnes transmises.

7. Facteurs de conception de protocoles de routage

Plusieurs facteurs sont dcisifs pour toute conception dun protocole de routage pour les

RCSFs, nous allons les mentionns comme suit :

7.1 Tolrance aux pannes

La proprit de tolrance aux pannes est dfinie par l'aptitude du protocole de

routage maintenir ses fonctionnalits, en cas de panne de quelques nuds. Le but de la

tolrance aux pannes est dviter la faille totale du systme malgr la prsence de fautes

dans un sous ensemble de ses composants lmentaires [9].

7.2 Consommation d'nergie

Le facteur le plus important prendre en considrations est lnergie consomme

par un capteur lors de la dtection et de la transmission des donnes captes sur le rseau.

Nous avons vu que la transmission est la fonction qui consomme le plus dnergie, elle est

proportionnelle au carre de la distance de transmission [10], et a la taille du paquet

envoyer. Pour prserver de lnergie et augmenter la dure de vie dun rseau, les

chercheurs ont opte pour des techniques qui favorisent le traitement local des donnes afin

de rduire la taille du paquet.ces techniques vitent la redondance des informations

transmettre et qui mettent le capteur en mode sommeil le plus longtemps possible [11].

7.3 Limitations de capacits des nuds

Un capteur est trs limite, en ce qui concerne, les traitements locaux cause de sa

taille minimale. Cela signifie que le protocole de routage doit tre simple et peu exigeant

en capacit de calcul et de stockage.


________________________________________________________________________________

-9-

7.4 Scalabilit

Les applications des RCSF ncessitent en gnral un dploiement dense des nuds.

Les protocoles de routage doivent donc tre trs scalables. Autrement dit, les protocoles de

routage ne devraient pas souffrir dune dgradation de performances dans le cas

dendommagement de nuds aussi bien quavec un nombre plus lev de nuds [12].

7.5 Htrognit

Gnralement, les nuds dun RCSF sont homognes ayant les mmes capacits de

calcul, de mmoire et de ressources nergtiques. Ces nuds pourront tre rapidement

puiss puisquils ralisent plusieurs tches la fois comme le captage, le traitement et le

routage de donnes. Pour y remdier, une solution envisage par certaines applications

consiste intgrer des nuds spciaux plus puissants que les autres et qui seront chargs

d'effectuer les tches les plus coteuses en termes de ressources nergtiques. Cependant,

l'intgration d'un ensemble de nuds htrognes dans un seul rseau impose de nouvelles

contraintes lies au routage de donnes. En effet, les donnes rcoltes par ces nuds

peuvent tre soumises des fortes qualits de service, et peuvent suivre des modles de

transmission de donnes diffrents. Par consquent, la conception des protocoles de routage

doit prendre en compte les diffrents types de nuds, et les contraintes qui en rsultent

[13].

7.6 Modles de transmission de donnes

Les RCSFs se caractrisent par une communication particulire par rapport aux

autres rseaux; ou les donnes transitent, souvent, entre des capteurs qui scrutent

lenvironnement qui les entourent et envoient linformation vers un ou plusieurs nuds dits

puits. Selon lapplication implmente au niveau du puits, nous distinguons trois types de

communications principales [11] :

a) Continue:

La collecte de donnes se fait priodiquement dune faon continue ou bien selon une

certaine distribution (i.e. gaussienne, gomtrique,) dterministe ou probabiliste. Le

processus denvoi planifie les priodes du sommeil des capteurs qui ne participent pas

(exemple: les applications de la mto).

b) Dirige par un vnement (event-driven):


________________________________________________________________________________

-10-

Dans ce type, les capteurs ne transmettent leurs donnes que si un vnement prdfini

est observe comme un changement brusque. Ainsi, le dlai de la transmission est limit et la

rception doit tre assure (des envois multiples sont prvoir) (exemple: les applications

de la surveillance).

c) Dirige par lapplication (application-driven):

La transmission de donnes est initie par la rception de la requte envoye par le puits

qui dfinit le type et les frquences des envois. Dans ce cas, des mcanismes de

correspondance sont ncessaires pour que les capteurs russissent dchiffrer les requtes

reues (exemple: les applications du contrle des systmes automatises).

8. Classification des protocoles de routage dans les RCSF

Rcemment, les protocoles de routage pour les RCSF ont t largement tudis,

Comme lillustre la figure 1.5, ils peuvent tre classs selon plusieurs critres :


________________________________________________________________________________

-11-

Figure 1. 5 : Classification des protocoles de routage dans les RCSF [14].

8.1 Selon la topologie du rseau

La topologie dtermine lorganisation des capteurs dans le rseau. Globalement, il existe

deux topologies dans les RCSFs [15] : La topologie plate et la topologie hirarchique.

1. Topologie Plate :

Un rseau de capteurs sans fil plat est un rseau homogne, o tous les nuds sont

identiques en termes de batterie et des fonctions, except le Sink [16]. Dans ce type de

topologie, les capteurs communiquent entre eux afin dacheminer linformation au nud

centralis (station de base). Ce processus dacheminement dinformation peut prendre deux

formes [17]: communiquer directement avec la station de base (Figure 1.6 (a)), ou via un

mode multi-sauts (Figure 1.6 (b)). De plus dans ce type de topologie (Figure 1.6 (a)) tous


________________________________________________________________________________

-12-

les nuds peuvent envoyer leurs donnes la station de base en utilisant une forte

puissance, ceci peut conduire la diminution de la dure de vie du rseau [18].

Figure 1.6 : Architecture de communication dans une topologie plate [17].

2. Topologie hirarchique :

Dans cette architecture, le rseau est constitu dun ensemble de groupe de capteurs

(cluster), tel quil est illustr dans la Figure 1.7. Le nud reprsentant le cluster, appel

cluster-head, a la responsabilit de transmettre les donnes la station de base. Lavantage

majeur de ce type darchitecture est le prolongement de la dure de vie du rseau de

capteurs. Ce rsultat est achev en dsignant le cluster-head comme tant le nud

responsable de la transmission des informations (agrges). Ce procd est meilleur de

celui o tous les nuds envoient leurs donnes un emplacement distant [18].

Figure 1. 6 : Topologie base de cluster [3].


________________________________________________________________________________

-13-

8.2. Selon la mthode dtablissement de routes

Suivant la manire de cration et de maintien des chemins pendant le routage nous

distinguons trois catgories de protocoles de routages : protocoles proactifs, ractifs ou

hybrides [19].

1. Protocole proactif :

Ces protocoles de routage essaient de maintenir les meilleurs chemins existants vers

toutes les destinations possibles au niveau de chaque nud du rseau. Les routes sont

sauvegardes mmes si elles ne sont pas utilises. Chaque nud du rseau maintient une

table de routage pour toutes les destinations indpendamment de l'utilit des routes. Les

protocoles proactifs sont adapts aux applications qui ncessitent un prlvement

priodique des donnes. Et par consquent, les capteurs peuvent se mettre en veille pendant

les priodes d'inactivit, et n'enclencher leur dispositif de capture qu' des instants

particuliers.

2. Protocoles ractifs :

Ces protocoles (dits aussi, les protocoles de routage la demande) crent et

maintiennent des routes selon les besoins. Lorsque le rseau a besoin d'une route, une

procdure de dcouverte de route est lance. Ce type de protocoles est pratique pour des

applications temps rel o les capteurs doivent ragir immdiatement des changements

soudains des valeurs captes. En effet, un prlvement priodique des donnes aurait t

inadapt pour ce type de scnarios.

3. Protocoles hybrides :

Ces protocoles combinent les deux ides des protocoles proactifs et ractifs. Ils utilisent

un protocole proactif pour apprendre le proche voisinage (par exemple le voisinage deux

ou trois sauts), ainsi, ils disposent de routes immdiatement dans le voisinage. Au-del de

la zone du voisinage, le protocole hybride fait appel un protocole ractif pour chercher

des routes.

8.3 Selon les paradigmes de communication

Le paradigme de communication dtermine la manire dont les nuds sont interrogs.

Dans le RCSFs, il existe trois paradigmes de communication [20].


________________________________________________________________________________

-14-

1. Centr-nuds :

Ce paradigme est celui employ dans les rseaux conventionnels, o il est ncessaire de

connaitre et didentifier les nuds communicants (comme ladresse IP). Les rseaux ad hoc

utilisent ce genre de paradigme, qui sintgre bien avec lutilisation de ce type

denvironnement. Cependant pour les rseaux de capteurs, un routage bas sur une

identification individuelle des nuds ne reflte pas lusage rel du rseau. Pour cela, un

autre paradigme a t introduit : Centr-donnes. Nanmoins, le paradigme Centre-nuds

nest pas carter totalement, car certaines applications ncessitent une interrogation

individuelle des capteurs.

2. Centr-donnes :

Dans les RCSF, la donne est gnralement plus importante que le nud lui-mme. De

ce fait, le routage et lidentification, dans ce paradigme, se font en fonction des donnes

disponibles au niveau des capteurs. Ainsi le systme peut tre vu comme une base de

donnes distribue, o les nuds forment des tables virtuelles, alimentes par les donnes

captes [21].

Le protocole Directed Diffusion (DD) est un exemple des protocoles de routage Centr-

donnes.

3. Bas-localisation :

Dans cette approche, les positions des nuds reprsentent le moyen principal

d'adressage et de routage. Dans ce cas, le routage s'effectue grce des techniques

gomtriques afin d'acheminer l'information d'une zone gographique vers une autre.

Ce type de mcanismes ncessite le dploiement dune solution de positionnement, dont

le degr de prcision requis dpend de lapplication cible. Lutilisation du GPS reste trop

coteuse dans un RCSF. Pour cela, plusieurs mthodes de localisation et de positionnement

de capteurs ont t dveloppes telles que la triangulation et la localisation par centrodes

[22].

On peut citer les protocoles Geographic Adaptive Fidelity (GAF) [23] et Geographicand

Energy Aware Routing (GEAR) [24] comme exemples de protocoles position centric.


________________________________________________________________________________

-15-

8.4 Selon le mode de fonctionnement du protocole

Le mode de fonctionnement dfinit la manire avec laquelle les donnes sont propages

dans le rseau. Selon ce critre, les protocoles de routage peuvent tres classifies quatre

catgories : routage bas sur la qualit de service QoS (Quality of Service QoS based

routing), routage base sur les requtes (query-based routing), routage multi-chemins (Multi-

path routing), et routage bas sur la ngociation (Negociation based routing) [15].

1. Routage bas sur les multi-chemins :

Dans cette catgorie, les protocoles de routage utilisent des chemins multiples plutt

quun chemin simple afin daugmenter la performance du rseau. La fiabilit dun

protocole peut tre mesure par sa capacit trouver des chemins alternatifs entre la

source et la destination en cas de dfaillance du chemin primaire. Pour cette raison

certains protocoles construisent plusieurs chemins indpendants, c.--d. : ils ne

partagent quun nombre rduit (voir nul) de nuds. Malgr leur grande tolrance aux

pannes, ces protocoles requirent plus de ressources nergtiques et plus de message de

contrle.

2. Routage bas sur les requtes :

Dans ce type de routage, le puits gnre des requtes afin dinterroger les capteurs.

Ces requtes sont exprimes soit par un schma valeur-attribut ou bien en utilisant un

langage spcifique (par exemple SQL : Structured Query Language). Les nuds qui

dtiennent les donnes requises doivent les envoyer au nud demandeur travers le

chemin inverse de la requte. Les requtes mises par le puits peuvent aussi tre cibles

sur des rgions spcifiques de rseau.

3. Routage bas sur la ngociation :

En dtectant le mme phnomne, les nuds capteurs inondent le rseau par les

mmes paquets de donnes. Ce problme de redondance peut tre rsolu en employant des

protocoles de routage bass sur la ngociation. En effet, avant de transmettre, les nuds

capteurs ngocient entre eux leur donnes en changeant des paquets de signalisation

spciales, appels mtadonnes. Ces paquets permettent de vrifier si les nuds voisins

disposent dj de la donne transmettre. Cette procdure garantit que seules les

informations utiles seront transmises et limine la redondance des donnes.


________________________________________________________________________________

-16-

4. Routage bas sur la qualit de service :

Dans les protocoles de routage bas sur la QoS, le rseau doit quilibrer entre la

consommation dnergie et la qualit de donnes. En particulier, le rseau doit satisfaire

certaines mtriques de QoS, par exemple, retard, nergie, largeur de bande passante, etc.

Les protocoles de cette approche sont trs recommands pour les applications de

surveillance (centrales nuclaires, applications militaires, etc).

8.5 Selon le modle de livraison de donnes

Il est possible de distinguer trois modles de livraison de donnes : time-driven, query-

driven et event-driven [14, 25].

1. Time-driven :

Cette approche consiste la livraison des donnes de faon priodique. Cet aspect

permet aux capteurs de se mettre en veille pendant les priodes dinactivit, et nenclencher

leur dispositif de capture qu des instants particuliers. Ainsi, la dure de vie du rseau va

tre allonge.

Le modle time-driven est appropri pour des applications qui ncessitent un

prlvement priodique des donnes. Par exemple, cela est utile dans des applications de

monitoring (feu, mto).

2. Query-driven :

Dans les applications query driven, la collecte dinformations sur ltat de

lenvironnement et la livraison des donnes sont inities par des requtes envoyes

gnralement par le nud puits.

3. Event-driven :

Ce modle est gnralement adopt dans les applications temps-rel o les capteurs

doivent ragir immdiatement des changements soudains des valeurs captes. Dans ce

cas, le protocole de routage doit tre ractif et doit donner des rponses rapides

loccurrence dun certain nombre dvnements.

9. Conclusion

Dans ce premier chapitre, nous avons prsent les rseaux de capteurs sans fil, leurs

architectures, leurs contraintes ainsi que leurs domaines dapplications. Nous avons vue


________________________________________________________________________________

-17-

quils prsentent un intrt considrable et ralisent une nouvelle tape dans lvolution des

technologies de linformation et de la communication.

La conception de rseaux de capteurs autonomes, relis par des liens sans fil, est un

domaine de recherche trs actif qui suscite un intrt croissant vu la diversit de ces

applications : sant, environnement, industrie et mme dans le domaine sportif.

Le routage de donnes est considr comme le domaine le plus explor parmi les

domaines de recherche sur les rseaux de capteur. Il reprsente aussi un problme complexe

car nous devons assurer la fiabilit de livraison de donnes, la performance du systme et

tout cela en consommant moins dnergie.

Les protocoles de routage pour les RCSFs sont nombreux avec un unique objectif :

Assurer la dlivrance des paquets collects par les nuds capteurs tout en parvenant

tendre la dure de vie du rseau.

Nous avons vu aussi dans ce chapitre que les algorithmes de routage sont dcoups en

trois familles : les algorithmes de routage donnes centrales, hirarchiques ou

gographiques. Chaque protocole doit affronter de multiples dfis et fournir des

caractristiques rpondant au besoin du rseau (nergie, scurit, temps rel).

Parmi les protocoles existants on sintresse particulirement la classe des protocoles

hirarchiques. Le protocole LEACH qui manipule des clusters et qui sera tudi dans le

chapitre qui suit.

-18-

Chapitre 2

Protocole de

routage LEACH :

Fonctionnement et

scurit

Chapitre 2 Protocole de Routage LEACH : fonctionnement et scurit

________________________________________________________________________________

-19-

1. Introduction

Le routage hirarchique est considr comme tant lapproche la plus favorable en

termes defficacit nergtique. Il se base sur le concept (nud fils nud pre) o les

nuds fils acheminent leurs messages leur pre, lequel les achemine ensuite dans le

rseau tout entier via d'autres nuds pres jusqu la station de base (sink).

Deux grandes approches sont drives de ce type de protocoles savoir : chane-based

approach (approche chane) et cluster-based approach (approche grappe). LEACH est

considr comme tant le premier protocole de routage hirarchique bas sur la seconde

approche. Il est aussi l'un des algorithmes de routage hirarchique le plus populaire pour les

rseaux de capteurs. L'ide est de former des clusters de nuds de capteurs bass sur les

zones o il y a un fort signal reu, puis utiliser des clusters-heads locaux comme passerelle

pour atteindre la destination [26].

Dans ce chapitre, nous expliquerons les protocoles MAC utiliss par le protocole

LEACH, larchitecture et lalgorithme de ce dernier. Par la suite, nous tudierons les

attaques pouvant perturber le fonctionnement de LEACH et les diffrentes contre-mesures

proposes pour les pallier.

2. Architecture de LEACH

La hirarchie de regroupement d'adaptation faible nergie (Leach) propos par

Heinzelman et al. [30] est un protocole de routage hirarchique bien connue appliqu dans

les RCSF.

LEACH divise le rseau en zone et clusters de faon distribue, des nuds CH (cluster-

Head) sont constitus puis utiliss comme relais pour atteindre le puits en optimisant la

consommation dnergie suivant un algorithme qui utilise la rotation randomise des ttes

de groupe pour distribuer quitablement la charge d'nergie entre les nuds de rseau. Un

nud dcide quel cluster rejoindre en se basant sur la puissance des signaux reus.

A la formation des groupes comme indique la figure 2.1, tous les nuds non CH

transmettent leurs donnes a la tte du groupe. Quand le CH reoit les donnes de tout les

membres du groupe, effectue des fonctions de traitement sur les donnes (par exemple

agrge et compresse les donnes), et les transmet la station de base (BS) selon une

communication unicast ( un seul saut).


________________________________________________________________________________

-20-

Figure 2. 1 : Architecture du routage hirarchique LEACH [31].

3. Algorithme dtaill de LEACH

Lalgorithme se droule en rounds qui ont approximativement le mme intervalle de

temps dtermin au pralable. O chaque cycle commence par une phase d'initialisation

suivie d'une phase de transmission.

3.1Phase dinitialisation

Comme lindique la figure 2.2, la phase dinitialisation est compose de 3 sous phases:

dannonce, dorganisation des groupes et enfin dordonnancement.

Figure 2. 2 : Oprations de ltape dinitialisation [32].


________________________________________________________________________________

-21-

3.1.1 Phase dannonce

Cette phase commence par lannonce du nouveau round par le nud puits, et, par la

prise de dcision locale dun nud pour devenir CH avec une certaine probabilit Pi(t) au

dbut du round r+1 qui commence linstant t. Chaque nud i gnre un nombre alatoire

entre 0 et 1. Si ce nombre est infrieur Pi(t), le nud deviendra CH durant le round r+1.

Pi(t) est calcul en fonction de K et de round r [29]:

O N est le nombre total de nuds dans le rseau. Si on a N nuds et K CH, alors, il faudra

N/K rounds durant lesquels un nud doit tre lu seulement une seule fois autant que CH

avant que le round soit rinitialis 0. Donc la probabilit de devenir CH pour chaque

nud i est :

(2)

(1)

O Ci(t) gal 0 si le nud i a dj t CH durant lun des (r mod N/K) rounds prcdents,

et, il est gal 1 dans le cas contraire. Donc, seuls les nuds qui nont pas encore t CH,

ont vraisemblablement une nergie rsiduelle suffisante que les autres et ils pourront tre

choisis.

Le terme reprsente le nombre total des nuds ligibles dtre CH linstant t.

Il est gal (2)

Utilisant lquation (1) et (2), le nombre de CH par round est :

Nombre

(CH)


________________________________________________________________________________

-22-

La probabilit Pi(t) est base sur la supposition que tous les nuds sont initialement

homognes et commencent avec la mme quantit rsiduelle dnergie et meurent

approximativement en mme temps. Cependant, ceci pourrait tre le cas juste aprs le

dploiement, mais il nest pas rellement valable aprs un certain temps. Alors, si lnergie

des nuds diffre, il sera plus pratique que la probabilit Pi(t) soit en rapport avec lnergie

restante au niveau de chaque nud. Cette probabilit sera donc gale :

(3)

O Ei(t) est lnergie rsiduelle relative chaque nud i. Utilisant cette probabilit, le

nud avec une plus grande ressource dnergie a une plus grande chance de devenir CH.

Ainsi, le nombre de nuds souhaits pour tre CH dans chaque round est:

Les quations (2) et (3) seront gales si les nuds commencent avec la mme nergie. De

plus, en utilisant lquation (3), les nuds requirent des informations sur toute lnergie

disponible dans le rseau.

3.1.2 Phase dorganisation de groupes

Aprs quun nud soit lu CH, il doit informer les autres nuds non-CH de son

nouveau rang dans le round courant. Pour cela, un message davertissement ADV contenant

lidentificateur du CH est diffus tous les nuds non-CH en utilisant le protocole MAC

CSMA pour viter les collisions entre les CH. La diffusion permet de sassurer que tous les

nuds non-CH ont reu le message. Par ailleurs, elle permet de garantir que les nuds

appartiennent au CH qui require le minimum dnergie pour la communication. La

dcision est base donc sur lamplitude du signal reu; le CH ayant le signal le plus fort (i.e.

le plus proche) sera choisi. En cas dgalit des signaux, les nuds non-CH choisissent

alatoirement leur CH [29].

3.1.3 Phase dordonnancement

Aprs la formation des groupes chaque CH agit comme un centre de commande local

pour coordonner les transmissions des donnes dans sa grappe. Il cre un modle de

communication en se basant sur TDMA, ensuite il le transmet aux nuds de sa grappe


________________________________________________________________________________

-23-

(cluster). Etant donn que chaque nud connat davance le slot de temps quil va occuper,

cela permet alors au nud de passer ltat "endormi" durant les slots inactifs. Ainsi, la

perte dnergie due aux tats de sur coute (overhearing) et dcoute passive (idle) est

vite.

Chaque CH choisit alatoirement un code dans une liste de codes de propagation CDMA,

il le transmet aux nuds appartenant son cluster afin de lutiliser pour leurs transmissions,

ceci afin de minimiser les interfrences entre les messages des CHs les plus proches [32].

3.2Phase de transmission

Dans la deuxime phase, le transfert des donnes actuelles la station de base a lieu. La

dure de la deuxime phase est plus longue que celle de la premire phase afin de rduire

au minimum les problmes doveheading. Cependant, la collection de donnes est

centralise et est excute priodiquement. Par consquent, ce protocole s'avre le plus

appropri quand on constate un besoin de surveillance de constante par le rseau de

capteurs [32].

Aprs un intervalle de temps donn prdtermin, le rseau va passer un nouveau round.

Ce processus est rpt jusqu ce que tous les nuds du rseau seront lus CH, une seule

fois, tout au long des rounds prcdents. Dans ce cas, le round est rinitialis 0.

Figure 2. 3: Rpartition du temps et diffrentes phases pour chaque round [17].

4. Avantages et inconvnients de LEACH

4.1 Avantages

Le protocole LEACH prsente les avantages suivants :


________________________________________________________________________________

-24-

Lauto-configuration des clusters se fait indpendamment de la station de base

(algorithme distribu).

Les donnes sont fusionnes pour rduire la quantit dinformations transmise vers la

station de base.

La consommation dnergie est partage sur lensemble des nuds prolongeant ainsi la

dure de vie du rseau.

Lutilisation des techniques TDMA/CDMA permet davoir une hirarchie et de raliser

des clusterings sur plusieurs niveaux. Ces derniers permettent dconomiser lavantage

dnergie.

Rotation randomise de la grappe effectue par "les stations de base" ou "les ttes de

cluster" [32].

Compression locale (agrgation) : Les nuds CH compressent les donnes arrivant des

nuds appartenant leurs grappes respectives, et envoient un paquet d'agrgation la

station de base afin de rduire la quantit d'information qui doit tre transmise la

station de base [32].

4.2 Inconvnients

En revanche, LEACH a les inconvnients suivants :

Sans justifier leur choix, les auteurs fixent le pourcentage optimal de CHs pour le rseau

5% du nombre total des nuds. Nanmoins, la topologie, la densit et le nombre de

nuds peuvent tre diffrents dans dautres rseaux.

Aucune suggestion nest faite propos du temps de rlection des CHs (temps des

itrations).

Les CHs les plus loigns de la station de base meurent rapidement par rapport ceux

qui sont proches de la station.

On pourra ne pas avoir des CH durant un round si les nombres alatoires gnrs par

tous les nuds du rseau sont suprieurs la probabilit Pi(t).

Lutilisation dune communication un seul saut au lieu dune communication multi-

sauts diminue lnergie des nuds.

LEACH ne fournit pas de clart sur la position des nuds capteurs et le nombre de CHs

dans le rseau [33].


________________________________________________________________________________

-25-

Le CH est toujours allum et lorsquil meurt, le groupe deviendra inutile car les donnes

recueillies par les nuds du cluster ne sauront jamais atteindre la station de base.

LEACH ne garantie pas une distribution homogne des CHs sur le rseau, car le seul

critre dlection du CH est une probabilit alatoire. Cela nempche pas une

concentration des CHs dans une rgion limite au dtriment de lensemble du rseau

Le protocole LEACH nest pas scuris, il est trs vulnrable mme aux simples

attaques [33].

Dans la section suivante, nous tudierons certaines attaques pouvant cibler le protocole

LEACH.

5. Les Attaques contre LEACH

Comme la plupart des protocoles de routage dans les RCSFs, LEACH est vulnrable

un certain nombre d'attaques de scurit, Toutefois tant un protocole base de clusters

nous comptons entirement sur le CH pour la tche d'agrgation des donnes et de routage.

Par consquent les attaques qui visent les CHs sont prjudiciables. Si un intrus parvient

devenir un CH, il peut provoquer des crises, perturbant ainsi le fonctionnement du rseau.

L'intrus peut galement essayer d'injecter de fausses donnes dans le rseau sans affecter le

routage. Ou bien peut seulement couter les flux et cest un troisime type d'attaque

(passive).

5.1 Sink Hole

Dans ce cas, lattaquant achemine tout le trafic vers lui afin de contrler la plupart des

donnes circulant dans le rseau. Ainsi il apparat aux autres nuds comme tant le nud

puits en mettant un signal plus fort que celui du nud puits original. Donc, les CH vont

transmettre leurs donnes au puits avec une puissance plus faible. En consquence, les

donnes ne peuvent pas atteindre ce dernier. Dans le cas o elles peuvent latteindre, il peut

aussi les modifier ou les supprimer [34, 35]. Cest cette attaque que nous nous sommes

intresses dans ce travail.

5.2 Selective Forwarding

Dans ce type dattaque on suppose que tout les nuds du cluster sont "honntes" et vont

transmettre normalement les paquets capts vers leurs chefs. Cependant, un attaquant (CH)

peut violer cette rgle en supprimant la totalit ou une partie de ces paquets.


________________________________________________________________________________

-26-

De plus, si l'attaquant au paravent avait utilis une attaque Sink Hole, il devient un routeur

important momentanment pour un grand nombre de nuds du rseau. Donc, en

abandonnant son rle, les performances du systme seront gravement dgrades [34].

5.3 Hello Flood

Linondation par des messages HELLO. Le nud malveillant et lors de ltape de

formation des clusters diffuse pour s'annoncer ses voisins des messages Hello avec une

grande puissance de transmission suffisante qui pourrait convaincre chaque nud du rseau

que l'adversaire est son voisin, et un nud recevant un tel paquet peut supposer que c'est

l'intrieur du rseau. Apres llection dun CH en se basant sur la force du signale reu,

L'adversaire peut choisir de faire un rejet slectif de donnes qui latteignent rellement, ou

nachemine aucune donne et le rseau va tre effectivement dsactive [36].

5.4 Spoofed Cluster Head

Cette attaque regroupe les trois attaques vu prcdemment et dans laquelle lattaquant

peut prsenter un nud malveillant ayant une grande puissance du signale par lutilisation

de lattaque hello flood qui va par consquent tre choisi la tte du cluster. Cela lui

permettra de devenir le chef de groupe pour une grande partie du rseau ou pour le rseau

tout entier (Sink hole).

En tant que chef de cluster lattaquant peut choisir de passer tous les paquets ou de les

ngliger (Sellectif Forwarding). Il aurait aussi la capacit modifier les slots de temps

TDMA qui malicieusement va provoquer des collisions entre les transmissions par

diffrents nuds capteurs [37].

6. Conclusion

Dans ce chapitre, nous avons prsent le protocole de routage hirarchique LEACH dont

lobjectif principal est le prolongement du temps de la vie du rseau ainsi que la gestion

efficace de la consommation nergtique.

Nous avons vu que LEACH est un protocole base de cluster, en s'appuyant

fondamentalement sur les CHs pour l'agrgation des donnes et le routage. Cependant,

puisquils sont considrs comme les points les plus vulnrables dans le rseau, les attaques

peuvent les viser en brouillant seulement les liens de communication entre ces CH et le


________________________________________________________________________________

-27-

nud puits. Pour cela, nous proposerons dans le prochain chapitre une alternative scurise

du protocole LEACH qui permet de pallier aux problmes de scurit les plus importants.

-28-

Chapitre 3 Scurisation du

protocole de routage LEACH

Chapitre 3 Scurisation du protocole de routage LEACH ________________________________________________________________________________

-29-

1. Introduction

Les RCSF connaissent actuellement une grande extension et une large utilisation dans

diffrents types dapplications, les nuds de ces rseaux sont disperss dans des

environnements qui peuvent tre propices des hostilits dun adversaire, le bon

fonctionnement du rseau peut tre compromis. Cest la raison pour laquelle assurer la

scurit dans ce type de rseaux devient un enjeu trs important et ce notamment en ce qui

concerne le bon acheminement des donnes vers le nud puits. Et comme il a dj t cit

dans le chapitre prcdent, LEACH est un protocole de routage non scuris. Nous allons

dans ce chapitre proposer une solution de scurisation pour ce protocole. Pour cela, nous

commenons par citer les dfis de la scurit. Par la suite, nous dsignerons les services de

scurit assurer. A la fin, nous expliquerons le fonctionnement de la solution propose,

avec une description des outils mis disposition pour atteindre les objectifs souhaits.

2. Les dfis de la scurit

La scurisation doit tre en mesure de garantir la minimisation de la consommation de

lnergie tout en maximisant les performances de rseau c..d. ne pas dgrader les

performances du rseau aprs la scurisation, aussi obtenir une meilleur stratgie contre les

attaques

3. Objectifs de la scurit pour LEACH

Lorsque nous abordons le problme de scurit, nous visons atteindre certains

objectifs telles que : lauthentification de sources de donnes, et lintgrit de donnes.

Notre travail consiste dterminer lensemble de mesures prendre, et cela dans le but

datteindre les objectifs viss afin de faire face aux quelques attaques dcrites dans le

chapitre prcdent.

Le protocole LEACH a besoin de garantir lauthentification de sources de donnes la

confidentialit et lintgrit de ces donnes. Ainsi, nous obtenons un nouveau protocole

scuris que nous appelons Safe-LEACH .


-30-

3.1 Authentification de sources de messages

Cest le service le plus important car on ne pourra pas assurer une confidentialit ou une

intgrit de messages changs si, ds le dpart, nous ne sommes pas srs de communiquer

avec le bon nud. Cette solution assure que les sources de donnes ne parviennent pas dun

nud malveillant. Lauthentification des donnes est assure grce au Code

dAuthentification de Message (CAM), ou MAC en anglais (Message Authentication

Code). [18]

3.1.1 Diffrents types de transmissions scuriser

Il est ncessaire dauthentifier les paquets mis sur tous les liens de communication

reliant les diffrentes entits du rseau. A travers ces liens, deux types de transmissions sont

employs (unicast (CH puits, CH MBR) et Broadcast a partir des CHs et puits vers tout

le rseau), dont chacun ncessite un mcanisme de scurit particulier [35] :

Unicast : Lauthentification de sources de donnes dans les transmissions unicast est

facilement ralise grce aux fonctions MAC qui seront vues plutard.

Broadcast : Les techniques implmentant la transmission unicast ne peuvent pas tre

appliques telles quelles aux transmissions de groupes. En effet les mcanismes bass

sur une cl secrte ne peuvent pas tre applique directement lauthentification en

broadcast, car un nud compromis rcepteur peut facilement deviner le message de

lexpditeur Par consquent, dautres mcanismes doivent tre utiliss pour garantir

lauthentification de sources de messages dans de telles transmissions

3.1.2 Diffrents liens de communication scuriser

CH-Membres : Ce lien est utilis au moment de lannonce du nouveau CH aux autres

nuds capteurs o lattaquant peut usurper lidentit de ce CH dans la phase dannonce.

Membres-CH : On utilise ce lien au moment de la construction des clusters en

choisissant les chefs (CHs). Un CH doit tre sr de lauthenticit des membres de son

groupe. Si ce lien nest pas scuris, Un nud malicieux peut alors injecter de fausses

donnes au CH ou linonder avec des messages et le forcera a les trait et cela mnera

lpuisement de son nergie.


-31-

CH-puits : ce lien est utilis lors de lenvoi des rsultats dagrgation du CH au noud

puits, Un nud malicieux peut alors attaquer ce schma en injectant de fausses donnes

dans le rseau ou en falsifiant le rsultat dune opration dagrgation. Dans ce cas Le

nud puits doit authentifier les CH afin de ne pas recevoir des donnes dun nud

malicieux

3.2 Confidentialit

Une fois les parties authentifies, la confidentialit reste un point important, elle

consiste prserver le secret des messages changs et ne pas les rvler aux adversaires.

En ce qui concerne LEACH, il ne manipule aucune donne secrte. Par consquent, on na

pas besoin dassurer ce service au niveau du routage [35].

3.3 Intgrit de messages changs

Elle assure que les donnes reues nont pas t altres durant leur transit dans le

rseau comme lannonce dun nouveau round, le statut du CH et les slots des membres. On

peut distinguer les altrations accidentelles lies par exemple, une mauvaise couverture

des ondes, et les altrations volontaires dun attaquant. Cela concerne aussi la protection

contre linjection ou la modification des paquets.

4. Mcanismes de scurit pour le protocole Safe-LEACH

Dans le but de fournir les services de scurit que nous avons fix, nous devons avoir

recours un certain nombre de mcanismes qui nous permettent dimplmenter les services

de scurit dsirs.

4.1 Mcanismes ncessaires pour lauthentification de sources de

messages

Lauthentification de la source de messages est assure par Le code dauthentification

de message MAC (Message Authentication Code) laide d'un ensemble de cls secrtes

partages entre les diffrentes entits du rseau. Pour assurer le partage de ces cls on a fait

appel aux protocoles de gestion de cls. Nous tudierons, dans ce qui suit, un ensemble de

ces protocoles [34].


-32-

4.1.1 Protocoles de gestion de cls

Aprs leur dploiement, des cls cryptographiques doivent tre installes dans des nuds

fin d'assurer lauthentification de sources de messages. Puisque notre objectif est de

scuriser un protocole de routage hirarchique, ltude est limite aux protocoles de gestion

de cls hirarchiques bass-cluster utilisant la mthode de pr-distribution de cls [35].

Dans ce qui suit nous allons dterminer le meilleur protocole pouvant assurer la gestion de

cls dans Safe-LEACH.

Protocoles bass sur la pr-distribution de cls

Ces protocoles suivent des schmas de gestion de cls symtriques qui permettent un

rseau de capteurs d'tablir des cls cryptographiques d'une faon autonome, sans compter

sur une cryptographie coteuse ni sur des serveurs de confiance [38].Parmi ces protocoles

nous avons choisi le protocole de gestion de cls basse consommation d'nergie qui offre

une gestion de cls simple et optimise et quil assure le service de partage de cls en

prenant en charge les contraintes dnergie et des capacits de mmoire et de calcul. Ceci le

favorise comme tant le meilleur candidat qui peut tre adopt dans LEACH.

Ce protocole utilise la notation suivante :

Notation Description

Chi Cluster head i

MBRi Le nud membre i

CHall Ensemble de tous les cluster-heads dans le rseau

Idi Lidentit du nud I

DATA Donnes sur la location et le niveau d'nergie de capteur

Cl partage entre CH et MBR

( , ) Fonction symtrique de cryptage utilisant la cl

Operateur de concatnation

Tableau 3. 1 : Notations utilises par le protocole Safe-LEACH.

Principe du protocole propos :

Ce protocole dterministe de gestion de cls est bas sur la mthode de pr- distribution.

Il a lavantage doffrir une gestion de cls optimise. Il consiste en un ensemble de

protocoles qui dfinie comment les cls sont distribues, ajoutes, rvoques et renouveles


-33-

pendant la dure de vie du rseau de capteurs. Dans cette approche, Chaque nud de

capteurs stocke deux cls secrtes, une est partage avec le CH et l'autre avec le nud puits.

Puisque les nuds puits sont scuriss et ont une mmoire suffisante, ils peuvent stocker

toutes les cls secrtes dans le rseau qui est gal au nombre total de CH et de nuds

membres (|CH|+|MBR|). Chaque CH stocke les cls qu'elle partage avec les capteurs de

son groupe et la cl partage avec le nud puits, il partage galement une cl avec un autre

CH dans le rseau. Les cls sont pr-dployes, donc il n'y a aucune transmission/rception

de cl (pas de consommation d'nergie) du cote nud de capteurs pendant l'amorage [38].

Les tapes du protocole sont les suivantes [38]:

1) Chaque nud capteur est pr-charg avec lidentificateur de son CH CHI D qui

contient sa cl partage. Aprs le dploiement, le nud capteur diffuse un message

Hello son identificateur MBRID et lidentificateur CHID

(1)

2) Processus de clustering (construction des groupes) (2)

3) Chaque CHi identifie l'ensemble des capteurs MBRIDi, qui sont dans son groupe et la

diffuse aux autres CH ((CHall)

(3)

4) Chaque CHj rpond CHi avec lensemble des identificateurs {(KMBR CH, IDMBRi) i.

(4)

5) Ensuite, Chaque membre du CHi reoit un message de ce dernier qui lui assigne la

passerelle CHj.


-34-

(5)

Par ailleurs ce protocole est bas sur certaines suppositions qui ne sappliquent pas

larchitecture de LEACH qui a besoin dune distribution de cls dynamique. Aussi que ses

nuds sont homognes contrairement que ceux du protocole de gestion de cls. Pour cela,

nous allons proposer des adaptations ce protocole afin quil puisse tre intgr dans le

protocole de routage LEACH.

Gestion de cls propose dans Safe-LEACH

Cls pr-charges au niveau du nud puits

Daprs ce quon a vu prcdemment, Chaque nud de capteurs stocke une cl secrte

avec le nud puits. Afin de ne pas surcharger la mmoire du nud puits, ces cls peuvent

tre les mmes pour un certain nombre de nuds. Qui ne doit pas tre trs lev

Figure 3. 1: Gestion de cls Nuds-puits.

Cls pr-charges au niveau de chaque nud capteur

Afin de ne pas saturer le nud puits avec un nombre important de cls reli au rseau

nous avons pens assigner des cls Nk aux autres nuds avec :


-35-

Et puisque le nombre de CH doit tre de 5 15% comme vu prcdemment donc le nombre

de membres MBR=Nombre de nuds du rseau nombre de CH.

Pour les nuds membres non identifis, le CH va se charger denvoyer leurs

identificateurs sous forme dun ensemble {id} i , au nud puits donc le but dallger la

charge pour ce dernier et surtout de minimiser le nombre de collisions. Le puits son tour

doit vrifier l'authenticit des nuds et voit s'il existe dans sa table et renvoi la liste des

nuds authentifis au CH pour qu'il puisse former son groupe.

Figure 3. 2: gestion de cls CH-Membres

Cls partages lors dun broadcast

Comme nous avons indiqu prcdemment, la technique base sur les codes MAC ne

peut pas tre utilise dans une transmission broadcast. Pour cela, nous avons fait recours

des protocoles de scurisation du broadcast, et parmi ces protocoles, nous avons choisi le

protocole Tesla pour sa simplicit et son efficacit [39]. Il fournit l'authentification

d'mission base sur la cryptographie symtrique par la rvlation retarde de cls

didentification. La station de base partage avec lensemble des capteurs une cl de groupe

kg. Cependant, Tesla vise a authentifier lorigine des paquets mis par la station de base et


-36-

a viter quun nud du groupe devenu malveillant nusurpe lidentit de la station de base

lors de lmission dun message.

Une liste chaine de cls est gnre

, de telle sorte que

, o F est une fonction de hachage irrversible. Chaque capteur est

initialis avec la cl

avant le dploiement du rseau. De plus, chaque capteur i partage

une cl symtrique principale avec la station de base qui permet de sauthentifier

mutuellement.

Les capteurs authentifient les paquets en deux tapes ; pour cela, le temps est dcompos

en intervalles T. Dans la premire tape, la station de base diffuse les paquets authentifie

P1, P2, avec la cl (k correspondant lintervalle de temps choisi pour mettre) ces

paquets sont conservs sans traitement par les capteurs qui ne peuvent pas encore vrifier

leur provenance car ils ne possdent pas la cl dauthentification . En effet, ils ne

connaissent que la cl .

Dans une seconde tape, la station de base diffuse la cl dauthentification dans

lintervalle de temps , les capteurs vrifient alors que

. Puis ils

vrifient que les paquets prcdemment envoys dans lintervalle sont correctement

authentifis. La station de base doit tre sure que tous les paquets sont arrivs destination

des capteurs avant de divulguer la cl dauthentification.

4.2 Mcanismes ncessaires pour lintgrit de donnes

Pour assurer le mcanisme dintgrit de donnes dans le protocole Safe-LEACH nous

avons choisi des mcanismes logiques de contrle d'erreurs tel que le code

dauthentification de message MAC (Message Authentication Code) qui fait partie des

fonctions de hachage cl cryptographiques. Un autre mcanisme doit tre mis en place qui

est bas sur lajout d'une information appele condensat (checksum) qui permet au

rcepteur de vrifier que le message reu na pas t altr [35].


-37-

5. Schma de scurit propos dans Safe-LEACH

1. Format des paquets envoyer

Lors de lenvoi des paquets, chaque nud calcule un MAC en utilisant la cl partage

sur la donne envoyer. Les paquets contiennent les champs suivant : La valeur du round

R, lidentificateur de nud ID, le champ de scurit MAC et aussi le champ qui contient

linformation transmise par le paquet qui change selon lmetteur :

Lmetteur Linformation transmise

Puits -un message de dclenchement de round

-un tableau des nuds authentifis.

CH -un message contenant le statut dun CH

-les slots de ses membres

-le rsultat de lagrgation de donnes.

Membre -un message dappartenance un CH

-une donne capte.

Tableau 3. 2 :Linformation transmise selon lmetteur.

Figure 3. 3 : Format dun paquet dans Safe-LEACH

Le nud metteur doit authentifier ses paquets avant les envoyer par la construction du

MAC en utilisant la cl partag Key de la faon suivante MAC (M, Key).


-38-

Le rcepteur calcule son tour le code MAC avec cette mme cl et le compare au code

quil a reu Sils sont bien identiques, alors la source est authentique et les donnes nont

pas t altres [34].

6. Ralisation et droulement

Notre travail sest droul en deux phases :

A. Etude du protocole LEACH.

B. Implmentation et valuation de lattaque SinkHole.

C. Implmentation et valuation du nouveau protocole scuris Safe-LEACH.

Nous donnons donc un aperu de notre implmentation afin de voir lvolution de LEACH

jusqu Safe-LEACH.

A. Ltude du protocole LEACH

Champs des paquets envoys

Nud puits :

Champs Descriptions

ID Lidentifiant du nud avec

TOS_LOCAL_ADRESS=0

Round Le round courant

Probability La probabilit que chaque nud devienne CH

Depth La profondeur du nud dans le rseau

Tableau 3. 3:Champs du paquet puits.

Nud membre :

Champs Descriptions

ID_MEMBRE Identifiant du nud

ID_CH Lidentifiant du CH au quel le nud appartient

Temp Dfinit la donne capte

Req Si req=1 message dappartenance au CH

req=2 message contenant la donne capte

Tableau 3. 4:Champs du paquet membre.


-39-

Nud Cluster Head :

Champs Descriptions

ID_MEMBRE Identifiant du nud

ID_CH Identifiant du CH

DONNE_AGG La donne agrge envoye au puits

FREQ La frquence utilise

SLOT_ATT Le nombre de slot attribuer a chaque membre

NBR_MBR Nombre de membre

Tableau 3. 5: Champs du paquet CH.

Etapes du protocole LEACH

Le nud puits 0 lance le dbut du round le cercle bleu reprsente le broadcast,

les autres nuds a la rception font a leur tour un broadcaste leur voisins. Le led

rouge activ dans nud 7 signifie quil est lu CH.

Figure 3. 4: Dclenchement et relai du nouveau round, annonce du CH 7.

Le CH dans cette tape envoi le nombre de slots ddis ses membres, les flches

en rose refltent lenvoi unicast de donnes.


-40-

Figure 3. 5: Formation de groupes et envoi slots aux nuds membre.

Les membres aprs captage de donne lenvoi au CH dans leur slots attribus, la

rception le CH les agrgent aux puits avec une transmission unicast.

Figure 3. 6: Envoi des donnes captes au CH 7 qui les agrge au puits.


-41-

B. Implmentation de lattaque SinkHole :

LEACH repose principalement sur les CHs qui sont vulnrables et viss par les

attaquants. Un lger problme dans ces derniers causera le disfonctionnement du rseau

pour un certain temps. Dans cette attaque le nud malicieux met un puissant signale et ce

fait passer par un CH pour quil reoit tout les paquets et l, soit il les modifie et les

rinjecte soit il ne fait rien et dans les deux cas cela paralyse le rseau.

Safe-LEACH avec son principe dauthentifier les e