Optimisation centralisée et distribuée de la durée de vie des réseaux de capteurs sans fil

é é é

é é

é

é é

Dedicaces

A Allah, Le Tout Puissant, par Qui le savoir a un sens,

a ma tres chere et brave maman Rokhaya Badiane,

a mon defunt et tres regrette papa Ibrahima Cisse,

a ma formidable famille,

et a toutes ces personnes speciales qui ont, durant toutes ces annees, ete mes

compagnons de tous les jours et une deuxieme famille pour moi. Ceux la qui

n’ont cesse de partager avec moi leur sympathie, leur chaleur, leur estime et leur

indulgence.

i

Remerciements

Je tiens a remercier en premier lieu M. Ousmane Thiare qui a accepte de m’en-

cadrer pour ce travail. Je lui dis merci pour la confiance qu’il m’a accordee et pour

ses pertinentes idees et fructueux conseils. Je remercie aussi M. Maissa Mbaye

pour son coup de pouce et pour ses encouragements dont il m’a fait beneficier.

Ensuite tous mes sinceres remerciements iront a tout le corps administratif et

professoral de l’UFR de Sciences appliquees et de Technologies qui a assure ma

formation. Je lui suis, pour cela, tres reconnaissant.

Je remercie finalement, toute personne qui, de pres ou de loin, a contribue a la

reussite de ce travail.

ii

Liste des acronymes

ADC Analogic to Digital Converter

ASCENT Adaptive Self-Configuring sEnsor Networks Topologies

DARPA Defense Advanced Research Projects Agency

GAF Geographic Adaptive Fidelity

GPS Global Positioning System

IoT Internet of Things

PDA Personal Digital Assistant

PEAS Probing Environment Adaptive Sleeping

QoS Quality of Service

RdCSF Reseaux de Capteurs Sans Fil

iii

iv

UAV Unmanned Air Vehicle

WINS Wireless Integrated Network Sensors

Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal

Table des figures

2.1 Anatomie d’un noeud capteur . . . . . . . . . . . . . . . . . . . . . 8

2.2 Architecture d’un reseau de capteurs sans fil . . . . . . . . . . . . . 10

2.3 Architecture en couches des reseaux de capteurs sans fil . . . . . . . 11

2.4 Tracking vehicles with a UAV-delivered sensor network . . . . . . . 14

2.5 SIstema de Seguimiento y VIgilancia Ambiental . . . . . . . . . . . 16

2.6 Interfaces de controle du systeme . . . . . . . . . . . . . . . . . . . 16

2.7 La plateforme Senslab . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.1 Clusters dynamiques : (a) cluster C en un temps t1. (b) cluster

C ′ en un temps t1 + d. Les noeuds marques d’un meme symbole

appartiennent au meme cluster. Les chefs de cluster sont representes

par un gros point. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

3.2 Perte d’energie dans le reseau par rapport au nombre de chefs de

cluster . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

v

Table des figures vi

3.3 Exemple simplifie d’autoconfiguration d’un reseau . (a) Trou de

communication. (b) Etat de transition. (c) Etat final. . . . . . . . . 42

3.4 Etats de transitions dans ASCENT . . . . . . . . . . . . . . . . . . 43

3.5 Resistance aux defaillances de nœuds . . . . . . . . . . . . . . . . . 49

3.6 Extension de la duree de vie . . . . . . . . . . . . . . . . . . . . . . 49

A.1 Anatomie du capteur TelosB . . . . . . . . . . . . . . . . . . . . . . 54


Liste des tableaux

A.1 Quelques capteurs et leurs fonctionnalites . . . . . . . . . . . . . . . 55

A.2 Quelques capteurs et leurs caracteristiques techniques . . . . . . . . 55

vii

Table des matieres

1 Introduction 1

2 Generalites sur les reseaux de capteurs sans fil 4

2.1 Anatomie d’un noeud capteur . . . . . . . . . . . . . . . . . . . . . 6

2.2 Architecture d’un reseau de capteurs sans fil . . . . . . . . . . . . . 8

2.3 Architecture en couches des reseaux de capteurs sans fil . . . . . . . 10

2.4 Les differentes applications des reseaux de capteurs sans fil . . . . . 12

2.4.1 Applications medicales . . . . . . . . . . . . . . . . . . . . . 12

2.4.2 Applications militaires . . . . . . . . . . . . . . . . . . . . . 13

2.4.3 Applications environnementales . . . . . . . . . . . . . . . . 15

2.4.4 Applications domestiques . . . . . . . . . . . . . . . . . . . . 15

2.4.5 Autres applications commerciales . . . . . . . . . . . . . . . 17

2.5 Les contraintes de conception et d’exploitation . . . . . . . . . . . . 18

2.5.1 La tolerance aux fautes . . . . . . . . . . . . . . . . . . . . . 18

2.5.2 Le passage a l’echelle . . . . . . . . . . . . . . . . . . . . . . 19

viii

Table des matieres ix

2.5.3 L’aspect cout . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.5.4 Les contraintes materielles . . . . . . . . . . . . . . . . . . . 20

2.5.5 L’environnement et la topologie du reseau . . . . . . . . . . 22

2.5.6 La consommation d’energie . . . . . . . . . . . . . . . . . . 23

3 Techniques d’optimisation de la duree de vie 25

3.1 La duree de vie d’un reseau de capteurs sans fil . . . . . . . . . . . 28

3.2 Techniques centralisees . . . . . . . . . . . . . . . . . . . . . . . . . 30

3.2.1 L’algorithme de Berman et al. . . . . . . . . . . . . . . . . . 30

3.2.2 Les travaux de Zhang et Hou . . . . . . . . . . . . . . . . . 31

3.2.3 Les travaux de Cardei et al. . . . . . . . . . . . . . . . . . . 32

3.3 Techniques distribuees . . . . . . . . . . . . . . . . . . . . . . . . . 33

3.3.1 Low-Energy Adaptive Clustering Hierarchy : LEACH . . . . 33

3.3.2 L’algorithme ASCENT : Adaptive Self-Configuring Sensor

Networks Topologies . . . . . . . . . . . . . . . . . . . . . . 40

3.3.3 Un protocole robuste de conservation d’energie pour les reseaux

de capteurs a longue duree de vie : PEAS . . . . . . . . . . 44

4 Conclusions 50

A Anatomie du capteur TelosB et comparaison des fonctionnalites

de quelques autres (xbow) 53

A.1 Anatomie du capteur TelosB . . . . . . . . . . . . . . . . . . . . . . 54

A.2 Comparaison des fonctionnalites de quelques capteurs . . . . . . . . 54


CHAPITRE 1

Introduction

1

2

Les recentes avancees de la micro-electronique et des technologies sans fil ont

accelere le processus de miniaturisation des equipements. Le controle et le

suivi des phenomenes physiques deviennent alors beaucoup plus aises. De nou-

velles applications, autrefois dangereuses ou trop couteuses voire irrealisables sont

desormais possibles grace a de petits appareils electroniques sans fils appeles nœuds

capteurs. Ces derniers sont deployes dans un environnement et sont des lors ca-

pables de recueillir differents types de donnees provenant de ce milieu, de les traiter

ou de les acheminer en plus de pouvoir communiquer entre eux grace a un dispositif

radio dont ils sont equipes. Lorsqu’ils sont utilises en quantite et de facon colla-

borative, ils constituent un reseau de capteurs et sont a l’origine d’applications

poussees dans le domaine militaire et dans celui de la medecine entre autres.

Dans la plupart des cas, il s’agit d’applications a temps reel dans des mi-

lieux ou l’acces est difficile et quelquefois impossible a l’homme. En effet, les cap-

teurs peuvent etre deployes au fond de l’ocean, dans un champ de bataille, etc.

Ceci fait qu’ils sont sans surveillance et qu’ils font difficilement l’objet de main-

tenance. Ils sont aussi utilises en grand nombre et doivent, suivant leur usage,

respecter des specifications liees a la taille et a la consommation d’energie. En ef-

fet, contrairement aux nœuds capteurs, d’autres equipements electroniques comme

les telephones portables, les PDAs, ou autres appareils electroniques sont la plu-

part du temps sous la main de l’homme qui se charge de leur maintenance et de

leur entretien. La batterie d’un telephone portable, par exemple, est facilement

rechargeable apres epuisement. Les nœuds capteurs aussi disposent d’une source

d’energie assez limitee mais ne beneficient pas cependant d’une possibilite de re-

charge manuelle. Ces facteurs representent autant de contraintes auxquelles font


3

face ces equipements rendant ainsi la plupart des algorithmes et protocoles, concus

pour les reseaux sans fil, inadapte aux reseaux de capteurs. De nouvelles techniques

sont alors mises sur point afin de tenir compte des exigences des reseaux de cap-

teurs sans fil liees a leur cout, a l’anatomie des nœuds c’est-a-dire de type materiel,

mais aussi et surtout liees a leur duree de vie. L’impossibilite d’une recharge ma-

nuelle et le besoin d’assurer une longue duree de fonctionnement aux applications

qui en decoulent ont fait que plusieurs chercheurs se concentrent actuellement sur

la conception d’algorithmes qui tiendront en compte le facteur energie pour les

reseaux de capteurs en optimisant leur duree de vie.

Ce memoire de master vient s’inscrire dans une logique d’etude de quelques

techniques d’optimisation de la duree de vie des reseaux de capteurs sans fil. Il fait

ressortir des procedes utilises pour reduire la consommation d’energie des nœuds

capteurs tels que la succession alternative des nœuds capteurs dans l’execution des

taches, l’organisation du reseau en clusters, la division des nœuds en hierarchie

entres autres methodes de la litterature. Pour cela, nous avons, apres ce premier

chapitre introductif, parle des generalites sur les reseaux de capteurs sans fil au

deuxieme chapitre. Cela pour mieux les cerner. Ensuite, au troisieme chapitre,

nous nous sommes concentres sur l’etude de quelques techniques d’optimisation de

leur duree de vie que nous avons separees en techniques centralisees et techniques

distribuees. Finalement, c’est au quatrieme et dernier chapitre que nous avons fait

une conclusion de ce travail et ouvert quelques perspectives.


CHAPITRE 2

Generalites sur les reseaux de capteurs sans fil

4

5

Sommaire

2.1 Anatomie d’un noeud capteur . . . . . . . . . . . . . . . 6

2.2 Architecture d’un reseau de capteurs sans fil . . . . . . 8

2.3 Architecture en couches des reseaux de capteurs sans

fil . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.4 Les differentes applications des reseaux de capteurs

sans fil . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.4.1 Applications medicales . . . . . . . . . . . . . . . . . . . 12

2.4.2 Applications militaires . . . . . . . . . . . . . . . . . . . 13

2.4.3 Applications environnementales . . . . . . . . . . . . . . 15

2.4.4 Applications domestiques . . . . . . . . . . . . . . . . . 15

2.4.5 Autres applications commerciales . . . . . . . . . . . . . 17

2.5 Les contraintes de conception et d’exploitation . . . . 18

2.5.1 La tolerance aux fautes . . . . . . . . . . . . . . . . . . 18

2.5.2 Le passage a l’echelle . . . . . . . . . . . . . . . . . . . . 19

2.5.3 L’aspect cout . . . . . . . . . . . . . . . . . . . . . . . . 20

2.5.4 Les contraintes materielles . . . . . . . . . . . . . . . . . 20

2.5.5 L’environnement et la topologie du reseau . . . . . . . . 22

2.5.6 La consommation d’energie . . . . . . . . . . . . . . . . 23


2.1. Anatomie d’un noeud capteur 6

La micro-electronique a connu au cours de cette decennie une avancee fulgurante

causant ainsi la miniaturisation progressive des equipements. Les reseaux de

capteurs sans fil sont une consequence de cet essor. Ils sont de plus en plus ameliores

et sont dotes d’une puissance de calcul sans cesse grandissante. Leur organisation

en reseau revele toute leur utilite non seulement dans le milieu industriel, mili-

taire, environnemental mais aussi dans la vie de chaque jour de l’homme. Ils sont

deployes en grand nombre dans differents milieux pour y effectuer diverses taches.

Cependant, ces capteurs de par leur taille, leur cout ou de par l’environnement

dans lequel ils sont deployes peuvent presenter des difficultes dans leur conception

et leur exploitation.

Nous allons, tout au long de ce chapitre, montrer comment est constituee la

plus petite entite d’un reseau de capteurs sans fil a savoir le nœud capteur. Pour

cela nous allons discuter de son anatomie. Puis, nous passerons a l’architecture

d’un reseau de capteurs sans fil, c’est-a-dire le reseau constitue de ces petites

entites. Ensuite, la section suivante exposera les differentes applications qui sont

faites des reseaux de capteurs sans fil dans les domaines medicaux, militaires,

environnementaux, domestiques et commerciaux. Enfin, nous clorons ce chapitre

en faisant ressortir les contraintes qui peuvent se presenter a la conception et a

l’exploitation d’un reseau de capteurs.

2.1 Anatomie d’un noeud capteur

Un nœud capteur ou ”mote” en anglais est constitue d’elements de telle sorte

qu’il peut a lui seul assurer les taches d’acquisition et de traitement de l’informa-


2.1. Anatomie d’un noeud capteur 7

tion. Il peut aussi communiquer avec les autres nœuds. Ceci fait que le capteur est

constitue de quatre composants de base :

– une unite d’acquisition generalement subdivisee en deux sous unites que

sont les capteurs et les convertisseurs analogique-numerique(ADCs)[LEH09].

Les capteurs sont charges de detecter les caracteristiques et les variations

du milieu ambiant. Ils sont utilises pour une grande variete de phenomenes

physiques (acceleration, concentration chimique...). Ils repondent a une va-

riation des conditions d’environnement par une variation de caracteristiques

electriques. Ce sont ces variations d’ordre electriques qui sont par la suite

converties par les convertisseurs analogique-numerique pour pouvoir etre

traitees par l’unite de traitement[KAC09].

– une unite de traitement qui est composee d’un processeur et d’un systeme

d’exploitation specifique. Elle acquiert les informations en provenance de

l’unite d’acquisition et les envoie a l’unite de transmission. Pour cela, elle est

constituee de deux interfaces : une avec le module d’acquisition et une autre

avec le module de transmission.

– une unite de transmission de donnees ou encore module de communi-

cation qui est responsable de toutes les emissions et receptions de donnees

a travers un dispositif radio. C’est un composant classique utilise dans les

reseaux sans fil.

– et une source d’energie constituant une composante cruciale d’un noeud


2.2. Architecture d’un reseau de capteurs sans fil 8

capteur. Son role est de stocker et de fournir l’energie necessaire au fonction-

nement du noeud. Cependant il peut aussi jouer celui consistant a rassembler

l’energie du milieu externe pour pouvoir l’utiliser. Il s’agit souvent d’une pile

AA normale d’environ 2.2 - 2.5 Ah fonctionnant a 1.5 V.

En plus de ces composants de base, il existe des noeuds capteurs dotes d’autres

unites additionnelles comme un systeme de localisation (GPS), une unite de mo-

bilite, etc. Il est presente a l’annexe A sous forme de tableaux quelques exemples

de capteurs.

Figure 2.1 – Anatomie d’un noeud capteur

2.2 Architecture d’un reseau de capteurs sans fil

Dans la plupart des cas, les nœuds capteur sont utilises en grand nombre et

deployes de facon tres dense dans un milieu. Ils sont capables de communiquer

entre eux et sont donc utilises comme un reseau d’equipements sans fil. Indivi-

duellement, ils sont capables de collecter des donnees de leur environnement, de

les traiter localement mais ils peuvent aussi communiquer entre eux pour achemi-


2.2. Architecture d’un reseau de capteurs sans fil 9

ner l’information vers un poste central en utilisant leur dispositif radio. Chaque

nœud capteur du reseau est capable de transmission et de reception de donnees.

En general, il existe dans le reseau un ou plusieurs nœuds speciaux appeles nœuds-

puits ou ”sink”. Ces derniers possedent plus de ressources et de puissance que les

autres types de nœuds du reseau et permettent, en plus de la recuperation des

donnees, l’interconnexion du reseau de capteurs avec d’autres types de reseaux

(Internet, satellite. . .). Dans un reseau de capteurs, les nœuds peuvent etre fixes

ou dotes de systeme de mobilite pour pouvoir se deplacer. L’environnement dans

lequel sont deployes les nœuds est appele la zone d’interet.

Dans un reseau de capteurs sans fil, des points d’agregation peuvent etre in-

troduits. Cela a pour but de resoudre le probleme de la consommation d’energie

[MAK08]. En effet, la communication entre les nœuds consomme beaucoup d’energie.

Ainsi ceci a pour but de reduire cette communication entre les nœuds en pri-

vilegiant celle entre les points d’agregation. Pour minimiser la consommation

d’energie, un type de regroupement appele ”clustering” peut aussi etre applique.

Un chef du cluster joue le role d’un point d’agregation. Les nœuds sont organises

en groupes, chaque groupe a un ”chef de cluster”. La communication au sein d’un

groupe doit passer a travers le chef, qui ensuite la transmet a un autre chef du

cluster voisin jusqu’a ce qu’il atteigne sa destination, la station de base.


2.3. Architecture en couches des reseaux de capteurs sans fil 10

Figure 2.2 – Architecture d’un reseau de capteurs sans fil

2.3 Architecture en couches des reseaux de cap-

teurs sans fil

Du fait du grand nombre de fonctionnalites implementees dans les reseaux de

capteurs, l’architecture de ces derniers est particulierement complexe. L’architec-

ture en couches dans les RdCSF comme dans les reseaux en general, veut reduire

cette complexite en decomposant les processus qui y sont mis a l’œuvre. Un tel

decoupage permet au reseau de traiter en parallele les fonctions attribuees aux

differentes couches.

Cette architecture est representee sur la figure 2.3 et tient compte des contraintes

liees au routage et a la consommation d’energie, integre la gestion des donnees

grace aux protocoles de routage de donnees, permet la communication a moindre

energie grace aux dispositifs sans fil, anime la collaboration des nœuds capteurs.

Le decoupage consiste en une couche physique, une couche liaison de donnees, une

couche reseau, une couche transport, une couche application ; un plan de gestion


2.3. Architecture en couches des reseaux de capteurs sans fil 11

Figure 2.3 – Architecture en couches des reseaux de capteurs sans fil

de l’energie, un plan de gestion de mobilite et un plan de gestion des taches.

En fonction de l’usage qui est fait du reseau de capteurs, differentes types d’ou-

tils exploitant la couche application peuvent etre developpes. La couche transport

permettra de maintenir le flux de donnees. La couche reseau pourra s’occuper du

routage des donnees qui lui seront presentees par la couche transport. Puisque,

les nœuds capteurs sont aussi deployes en grand nombre, la couche liaison de

donnees se chargera d’eviter les collisions qui peuvent etre dues aux communica-

tions simultanees. La couche physique, quant a elle, assurera les besoins non moins

importantes de modulation, de reception et d’emission. En plus de ces couches, les

plans de gestion de l’energie, de la mobilite et des taches gerent la consommation

d’energie, les deplacements et la distribution des taches entre les nœuds capteurs.

Ils aident les nœuds capteurs a coordonner les taches de detection et de limiter la

consommation d’energie.


2.4. Les differentes applications des reseaux de capteurs sans fil 12

2.4 Les differentes applications des reseaux de

capteurs sans fil

Un reseau de capteurs peut etre constitue de differentes sortes de nœuds cap-

teurs capables de detecter differents phenomenes physiques tels que les phenomenes

sismiques, magnetiques, thermiques, visuels, acoustiques entre autres. Ils sont de

ce fait utilises pour controler une large variete de conditions du milieu ambiant

comme [ASSC02] la temperature, l’humidite, les deplacements des vehicules, la

luminosite, la pression, les caracteristiques du sol, le niveau de bruit, la presence

ou l’absence de quelques objets, la vitesse, la direction et la taille d’un objet.

Les capacites de detection et de communication sans-fil de ces nœuds fait envi-

sager toute une nouvelle vague d’applications dans des domaines differents. Dans

la suite, nous allons detailler l’usage qui est fait des capteurs dans les milieux de

la sante, les milieux militaires, environnementaux, domestiques et dans quelques

milieux commerciaux.

2.4.1 Applications medicales

Les applications des reseaux de capteurs sans fils dans le domaine medical

permettent dans les hopitaux de realiser la surveillance des patients, de faire la

diagnostique, d’assurer normalement l’administration de medicaments. Elles per-

mettent de surveiller dans d’autres milieux les deplacements et transformations

des insectes et autre animaux. Les reseaux de capteurs sans fil y sont aussi uti-

lises pour surveiller les patients et les medecins au sein de l’hopital mais egalement

pour faciliter l’etude de la physiologie humaine. En effet, les donnees physiologiques



collectees par un capteur peuvent etre conservees pendant une longue periode et

utilisees par la suite pour une consultation medicale [O+98].

Les capteurs peuvent aussi surveiller l’etat de sante des personnes agees[C+94,

C+95]. Ils ont non seulement l’avantage de permettre au medecin de pouvoir

detecter assez tot les symptomes[N+98], mais aussi d’empecher l’alitement du pa-

tient, qui pourra vaquer a ses occupations, lui procurant ainsi une meilleure qua-

lite de vie pendant tout le traitement comparee a celle qu’il aurait eue en milieu

hospitalier[BSIP00]. La faisabilite d’un tel systeme medical est etudiee en Grenoble

(France) a travers le projet ”Health Smart Home” [NHR+00].

Les capteurs peuvent egalement etre implantes dans le corps humain pour

controler les problemes medicaux comme le cancer et pour aider les patients a

maintenir leur sante. En implantant sous la peau des mini capteurs video, on peut

recevoir des images en temps reel d’une partie du corps sans aucune chirurgie et

pendant environ 24h. On peut ainsi surveiller la progression d’une maladie ou la

reconstruction d’un muscle. Un projet actuel consiste a creer une retine artificielle

composee de cent micro-capteurs pour corriger la vue [MAK08].

2.4.2 Applications militaires

La recherche militaire est l’un des principaux domaines utilisant la technologie

des reseaux de capteurs sans fil. En effet, une grande partie de la croissance ra-

pide dans la recherche et le developpement des reseaux de capteurs sans fil a ete

garantie par des programmes finances par l’Agence americaine pour les Projets



de Recherche Avancee de Defense (DARPA), notamment grace a un programme

connu sous le nom de ”SensIT” [KAC09].

Les reseaux de capteurs peuvent etre utilises pour la surveillance des champs de

bataille et la traque de cibles. Ils fournissent ainsi des informations sur le nombre,

le mouvement, l’identite des soldats, etc. Ils sont aussi tres utiles dans la gestion

des munitions et des equipements des corps militaires[ASSC02]. En effet l’etat des

munitions des troupes peut etre constamment surveille grace a des capteurs qui

sont relies aux vehicules ou aux armes et qui renvoient de temps en temps l’etat

de ces derniers.

Un projet de l’Universite de Californie Berkeley[BC] consistait a suivre la

trace des vehicules militaires passant pres de capteurs parsemes grace a un drone

”Unmanned Air Vehicle” (UAV). La figure 2.4 representent quelques images de

l’operation qui a dure trois jours.

Figure 2.4 – Tracking vehicles with a UAV-delivered sensor network



2.4.3 Applications environnementales

Dans le milieu environnemental aussi, les reseaux de capteurs gardent toute

leur importance. Les capteurs sont deployes en grand nombre et dans la plupart

du temps dans des milieux hostiles a l’homme. Ceci permet leur utilisation dans

la lutte contre les feux de brousse. Ils peuvent detecter l’origine du feu evitant

que celui-ci devienne incontrolable. Dans le milieu de l’agriculture, les reseaux de

capteurs offrent aussi la possibilite de pouvoir surveiller les cultures. Ils fournissent

en temps reel des informations relatives au volume de pesticides dans les sols, a la

vitesse de l’erosion et au niveau de pollution de l’air. Differentes sciences d’etude de

l’environnement font recours aux technologies des capteurs. Il peut s’agir d’etudier

les mouvements des oiseaux, des petits animaux et des insectes ou de surveiller

l’etat de la recolte et du betail, de controler l’irrigation des terres ou meme de faire

des etudes a une plus grande echelle.

En Espagne, une entreprise qui commercialise des projets de protection de l’en-

vironnement a developpe un systeme de detection de feux de brousse en utilisant

des reseaux de capteurs[Dim]. Ce systeme a ete realise sur une superficie de 210

hectares dans le nord du pays et a eu pour but de fournir a differentes organisations

une infrastructure de surveillance de l’environnement et la possibilite de recevoir

des alarmes d’avertissement. Les figures 2.5 et 2.6 servent a illustrer ce systeme.

2.4.4 Applications domestiques

Avec la miniaturisation progressive, les capteurs sont de plus en plus integres

aux equipements de la tous les jours. Les telephones portables, les ordinateurs, les



Figure 2.5 – SIstema de Seguimiento y VIgilancia Ambiental

Figure 2.6 – Interfaces de controle du systeme



fours a micro-ondes et meme les cles de voitures sont equipes de capteurs. Dans

la maison, l’aspirateur, le refrigerateur, la television integrent des capteurs. La

domotique fait usage des reseaux de capteurs pour fournir dans les maisons, les

hotels ou les lieux publics des fonctions de confort (gestion d’energie, optimisation

de l’eclairage et du chauffage), de securite (alarme, videosurveillance, gardiennage)

et de communication (commandes a distance, signaux visuels ou sonores).

Quelques travaux [BBC10] ont consiste a l’utilisation des reseaux de capteurs

sans fil pour reduire la consommation d’energie des appareils electroniques de la

maison.

Les reseaux de capteurs sans fil constituent aussi une brique de l’Internet des

objets (IoT pour Internet of Things). Ce dernier represente l’extension d’Internet

aux objets de la vie de tous les jours.

2.4.5 Autres applications commerciales

Quelques une des applications commerciales concernent la gestion des materiaux,

de l’inventaire, la surveillance de la qualite des produits, la construction de bureaux

intelligents, le controle environnemental (climatisation, sonorisation, etc.) dans les

entreprises, les jeux et les musees interactifs, l’automatisation et le controle des

processus dans l’industrie, etc.[ASSC02]

Un systeme de reseau de capteurs sans fil peut etre installe pour controler le flux

d’air et de temperature dans differentes parties d’une piece. On estime qu’une telle

technologie peut reduire l’energie de telle facon a faire des economies a hauteur de


2.5. Les contraintes de conception et d’exploitation 18

55 milliards de dollars par an et une reduction de 35 millions de tonnes de carbone

emises [RAJ+00]. Dans la detection de voiture volees aussi, les capteurs sont d’une

grande utilite car permettant en temps reel de renvoyer la position geographique

de la voiture a un nœud central.

2.5 Les contraintes de conception et d’exploita-

tion

La mise en place et l’exploitation d’un reseau de capteurs n’est pas sans dif-

ficulte. Il existe des contraintes liees a la conception de celui ci qui peuvent etre

d’ordre multiple. La conception de protocoles et d’algorithmes doivent des lors en

tenir compte pour etre le plus optimal possible. Ces contraintes vont aussi influen-

cer l’exploitation du reseau de capteurs sans fil. Nous detaillerons ici quelques une

de ces contraintes, cependant cette liste n’est pas exhaustive.

2.5.1 La tolerance aux fautes

La tolerance aux fautes est l’aptitude d’un systeme informatique a accomplir sa

fonction malgre la presence ou l’occurrence de fautes, qu’il s’agisse de degradations

physiques du materiel, de defauts logiciels, d’attaques malveillantes, d’erreurs d’in-

teraction homme-machine [A+06]. Les nœuds peuvent etre sujets a des pannes dues

a leur fabrication (ce sont des produits de serie bon marche, il peut donc y avoir des

capteurs defectueux) ou plus frequemment a un manque d’energie. Les interactions

externes (chocs, interferences) peuvent aussi etre la cause des dysfonctionnements.

Afin que les pannes n’affectent pas la tache premiere du reseau, il faut evaluer

la capacite du reseau a fonctionner sans interruption [KAC09]. L’exemple donne



dans [KPSV] montre un cas de tolerance aux fautes dans un reseau de capteurs

sans fil.

2.5.2 Le passage a l’echelle

Dans un reseau de capteurs sans fil, le nombre de nœuds deployes dans l’etude

d’un phenomene est generalement de l’ordre de centaines voire de milliers. En

exemple, la plateforme Senslab [sen] met a disposition 1024 nœuds-capteurs repartis

sur quatre sites en France a savoir Grenoble, Lilles, Rennes et Strasbourg (cf. figure

2.7).

Figure 2.7 – La plateforme Senslab

De ce fait, les algorithmes et protocoles concus pour les reseaux de capteurs

sans fil doivent etre a meme de s’adapter a ce nombre extensible de nœuds. Les

applications des rdcsf doivent meme etre capables de l’utiliser a leur avantage.



2.5.3 L’aspect cout

Par definition, un reseau de capteurs sans fil consiste en un grand ensemble

de nœuds capteurs. Suivant l’usage qui en est fait, un reseau de capteurs peut

comporter jusqu’a des milliers de nœuds. Il s’en suit des lors que le cout d’un

nœud capteur va fortement influencer celui de tout le reseau. Clairement, le cout

de chaque nœud capteur doit etre faible pour que celui du reseau soit acceptable.

Il est a noter aussi qu’en fonction de l’application, le nœud capteur peut etre

dope grace a des equipements supplementaires comme un systeme de localisation,

un composant de mobilite pour qu’il puisse etre capable de deplacements ou un

generateur d’energie. Toutes ces unites additionnelles ont un cout supplementaire.

Ainsi elles augmentent les fonctionnalites du reseau de capteurs mais egalement le

cout de celui-ci [ASSC02].

2.5.4 Les contraintes materielles

Un nœud capteur est generalement compose de quatre composants basiques :

une unite de detection, une unite de traitement, un transceiver et une source

d’energie. Le plus souvent et en fonction de l’application, des unites additionnelles

peuvent etre incorporees au capteur. Il s’agit d’un systeme de localisation, d’un

generateur d’energie et d’une unite de mobilite pour la plupart du temps. Des lors,

la difficulte est que tous ces composants doivent etre ajustes a l’interieur d’un dis-

positif de la taille d’une boite d’allumette. Pour certains usages, le nœud capteur

doit avoir une taille plus petit qu’un centimetre cube et peser assez leger pour

pouvoir etre suspendu. Compte tenu des fonctionnalites toujours extensibles, ces

contraintes de taille et de poids viennent s’ajouter aux difficultes liees a la concep-



tion d’un reseau de capteurs sans fil [AV10].

Les contraintes dues a la taille des nœuds rendent la capacite de stockage

d’energie assez faible. Par exemple la quantite totale d’energie stockee dans un

nœud smartdust 1 est de l’ordre de 1 J [PK00]. Pour les systemes WINS [VWPK00],

la moyenne d’energie ne doit pas depasser 30 µA pour esperer une longue duree

de vie du systeme.

Cependant, bien que les avancees technologiques permettent de plus en plus

une grande puissance de calcul dans de petits equipements a des prix derisoires,

la puissance de calcul des nœuds capteurs actuels est significativement plus petite

que celle de plusieurs autres systemes embarques a cause de la taille et du prix.

Par exemple, les premiers dispositifs tels que le nœud smartdust avaient un mi-

crocontroleur Atmel AVR 8535 de 4 MHz, une memoire flash de 8 KB, une RAM

de 512 octets et une memoire morte EEPROM de 512 octets aussi. Ces capacites

ont ete accrues avec les nœuds SunSPOT et Imote2. SunSPOT est equipe d’un

processeur 32 bit ARM920T de 180 MHz, d’une RAM de 512 KB et d’une memoire

flash de 4 MB. Imote2 dispose quant a lui d’un microcontroleur Marvell PXA271

XScale de 416 MHz, une SRAM de 256 KB, d’une memoire flash de 32 MB et

d’une SDRAM de 32 MB. Il apparait clairement alors que les capacites des nœuds

capteurs vont augmenter, toutefois, ces valeurs fournies ne representent rien com-

parees aux capacites d’autres types de systemes embarques comme les PDA ou

1. Smartdust est un systeme de nombreux petits appareils micro-electromecaniques commeles capteurs, les robots ou d’autres equipements, qui peuvent par exemple detecter la lumiere, latemperature, la vibration, le magnetisme ou des produits chimiques ; qui generalement commu-niquent sans fil, et qui sont repartis sur une certaine espace pour effectuer des taches de detection.C’est un concept introduit par la DARPA.



les smartphones [AV10]. Par consequent, les applications des reseaux de capteurs

ainsi que les protocoles concus doivent tenir compte de ces contraintes materielles.

2.5.5 L’environnement et la topologie du reseau

Les nœuds capteurs sont deployes au sein du milieu a observer ou assez proche

de celui-ci. Ce milieu est la plupart du temps difficile d’acces a l’homme. Ceci fait

que les capteurs sont habituellement dans des regions eloignees et sans surveillance.

Ils peuvent se trouver [ASSC02] :

– au fond de l’ocean,

– a l’interieur d’une tornade,

– dans un champ contamine biologiquement ou chimiquement,

– dans un champ de bataille au-dela des lignes ennemies,

– attache a des animaux,

– etc.

Cette liste nous donne une idee de l’environnement dans lequel les nœuds capteurs

sont embarques.

La topologie du reseau est aussi un facteur a prendre en compte dans la concep-

tion du reseau de capteurs sans fil. En effet, le grand nombre de capteurs qui sont

dans des milieux inaccessibles et donc sans surveillance ni maintenance est des lors

sujet a de frequentes defaillances. Cela entraine une modification periodique de la

topologie du reseau de capteurs.



2.5.6 La consommation d’energie

Dans les reseaux de capteurs, l’energie est tres importante car elle est rare.

Le nœud capteur etant un equipement micro-electronique est muni d’une source

d’energie limitee. Or contrairement aux ordinateurs portables et aux equipements

de poche comme les telephones portables qui beneficient d’une constante attention

et maintenance, les capteurs par leur grand nombre, mais aussi par le fait qu’ils

sont la plupart du temps parsemes dans des milieux hostiles a l’homme, ne peuvent

pas faire l’objet d’une recharge manuelle. Bien que certaines techniques de collecte

d’energie dans l’environnement existent, la consommation d’energie demeure l’une

des contraintes majeures dans l’exploitation des reseaux de capteurs sans fil. En

effet ce challenge est au cœur de toutes les autres contraintes et influence la concep-

tion de tout le systeme [R+06].

Dans un reseau multi saut, le nœud joue le double role de source de donnees

et de routeur. Le dysfonctionnement de quelques nœuds pourrait causer d’im-

portantes modifications dans la topologie et pourrait necessiter un autre routage

des paquets en plus de la reorganisation du reseau. De ce fait, la conservation

et la gestion de l’energie prennent une importance supplementaire. C’est pour

ces raisons que plusieurs chercheurs se concentrent actuellement sur la conception

d’algorithmes et de protocoles qui tiendront en compte le facteur energie pour les

reseaux de capteurs.

Dans d’autres types de reseaux sans fil, la consommation d’energie est une

contrainte importante mais pas la contrainte majeure, simplement par le fait que

les sources d’energie peuvent etre remplacees lorsqu’elles sont epuisees [ASSC02].



Dans ces reseaux, l’accent est plus porte sur la qualite de service (QoS). Cependant

dans les reseaux de capteurs, l’energie est une importante mesure de performance.

Ainsi, les protocoles peuvent etre concus en compromettant d’autres mesures de

performance telles que le delai ou la bande passante.

La tache principale d’un nœud capteur est de detecter des phenomenes phy-

siques, de faire un traitement local et de transmettre de l’information. Toutes ces

trois requierent de l’energie, faisant que la consommation d’energie d’un nœud cap-

teur peut etre subdivisee en celle necessaire pour la detection, une autre necessaire

pour le traitement local et une derniere necessaire pour la communication. De

toutes ces taches, c’est dans l’execution de cette derniere que le nœud capteur

consomme le plus d’energie. Ceci concerne aussi bien la reception que la transmis-

sion de donnees.


CHAPITRE 3

Techniques d’optimisation de la duree de vie

25

26

Sommaire

3.1 La duree de vie d’un reseau de capteurs sans fil . . . . 28

3.2 Techniques centralisees . . . . . . . . . . . . . . . . . . . 30

3.2.1 L’algorithme de Berman et al. . . . . . . . . . . . . . . 30

3.2.2 Les travaux de Zhang et Hou . . . . . . . . . . . . . . . 31

3.2.3 Les travaux de Cardei et al. . . . . . . . . . . . . . . . . 32

3.3 Techniques distribuees . . . . . . . . . . . . . . . . . . . 33

3.3.1 Low-Energy Adaptive Clustering Hierarchy : LEACH . 33

3.3.2 L’algorithme ASCENT : Adaptive Self-Configuring Sen-

sor Networks Topologies . . . . . . . . . . . . . . . . . . 40

3.3.3 Un protocole robuste de conservation d’energie pour les

reseaux de capteurs a longue duree de vie : PEAS . . . 44


27

Il est a noter que les reseaux de capteurs sans fil ont beaucoup de similitudes

avec les reseaux ad-hoc sans fil. En effet ces deux types de reseaux sont tous des

reseaux sans infrastructure, ont une architecture decentralisee, utilisent les ondes

radio pour communiquer et sont autonomes. De ce fait, la conception de proto-

coles et d’algorithmes pour les reseaux de capteurs peuvent prendre en compte les

proprietes des reseaux ad-hoc.

Cependant, les reseaux de capteurs presentent aussi beaucoup de fonctionna-

lites qui leur sont specifiques et donc non presentes dans les reseaux ad-hoc. Ce

sont ces fonctionnalites qui amenent de nouveaux challenges et qui doivent etre

prises en compte dans la conception des protocoles et autres techniques pour les

reseaux de capteurs sans fil. Parmi ces differences [MAK08] :

– la densite de nœuds deployes est beaucoup plus importante dans les reseaux

de capteurs sans fil que dans les reseaux ad-hoc,

– les nœuds capteurs ont des capacites limitees en energie et en memoire,

– la topologie dans les reseaux de capteurs est souvent dynamique,

– la communication entre les nœuds d’un reseau de capteurs se fait par diffusion

et non point par point,

– les capteurs peuvent ne pas avoir un identifiant global vu le grand nombre

de nœuds qui existent generalement.

Dans ce document, nous nous interessons plus a la contrainte imposee par la

faible duree de vie des reseaux de capteurs. De ce fait, nous exposons dans ce

chapitre, differentes techniques non-exhaustives d’optimisation de cette duree de


3.1. La duree de vie d’un reseau de capteurs sans fil 28

vie. Nous ressortirons d’abord la notion de duree de vie d’un reseau de capteurs

sans fil a travers les differentes definitions qu’elle revet en fonction de l’objectif vise

dans l’exploitation du reseau. Puis, nous aborderons les techniques centralisees a

travers l’algorithme de Berman et al., les travaux de Zhang et Hou et ceux de

Cardei et al. Apres cela, nous passerons aux techniques distribuees en presentant

differents algorithmes et protocoles comme LEACH, ASCENT, PEAS de Fan Ye

et Gary Zhong, PEAS-Weibull et PECAS.

3.1 La duree de vie d’un reseau de capteurs sans

fil

La duree de vie est l’un des problemes les plus serieux dans l’etude des reseaux

de capteurs sans fil. Comme nous l’avons dit dans la sous-section 2.5.6, les nœuds

capteurs sont des equipements sans controle avec une duree de vie limitee. Le

reseau peut rapidement cesser de fonctionner normalement a cause d’une deviation

ou d’un manque de planning et puisqu’un reseau de capteurs est generalement uti-

lise pour une longue duree sans possibilite de recharge, prolonger sa duree de vie

devient primordial.

Selon l’objectif ou les hypotheses pris en compte, il y’a plusieurs definitions de

la duree de vie du reseau. Elle est souvent consideree comme la duree qui s’ecoule

depuis la mise en place du reseau jusqu’a l’epuisement de la source d’energie d’un

premier nœud. Bien que la redondance des nœuds peut, dans ce cas, permettre au

reseau de continuer a fonctionner. Une autre definition est la duree qui s’ecoule

jusqu’au moment ou le nombre de capteurs epuises atteint un seuil determine.


3.1. La duree de vie d’un reseau de capteurs sans fil 29

Une definition plus realiste est de considerer la duree de vie du reseau comme la

duree qui s’ecoule depuis la mise en place du reseau jusqu’au moment ou celui-ci

devient incapable d’accomplir les taches qui lui sont assignees. La couverture est

l’activite premiere d’un reseau de capteurs sans fil. Elle est d’ailleurs generalement

consideree comme la QoS du reseau. Elle represente de ce fait un bon objectif qui

peut etre pris en compte dans l’etude de l’optimisation de la duree de vie du reseau

de capteurs.

Le nœud capteur est compose de quatre principales unites (voir section 2.1).

C’est la source d’energie qui fournit de l’energie aux trois autres composants et

toute activite de ces trois derniers que ce soit la detection, le traitement, la trans-

mission et la reception de donnees consomme de l’energie [QUN07]. Il est connu

que les operations de communication des nœuds (transmission et reception de

donnees) sont les plus consommatrices d’energie. De ce fait, reduire la consomma-

tion d’energie de leur dispositif radio est une technique de conservation d’energie

et d’optimisation de la duree de vie du reseau. Des techniques de planification

de l’activite des nœuds (actif, en veille, inactif, . . .) sont egalement utilisees pour

augmenter la longevite du reseau de capteurs. Elles sont appelees techniques de

� duty cycling �. Aussi, dans les reseaux de capteurs organises en clusters, des

chefs de clusters sont selectionnes pour accomplir des taches (comme la mobilite

dans le but d’equilibrer l’energie) visant a allonger la duree de vie du reseau.


3.2. Techniques centralisees 30

3.2 Techniques centralisees

3.2.1 L’algorithme de Berman et al.

Berman et al. ont, dans leur document [BCSZ05] mis l’accent sur la reduction

de la consommation d’energie due a la detection (sensing) en utilisant des tech-

niques intelligentes d’ordonnancement. Ils ont defini la duree de vie comme etant

le temps durant lequel la zone d’interet est partiellement ou totalement couverte.

Ils ont propose un algorithme pour determiner un planning de la surveillance qui

allonge la duree de vie du reseau lorsqu’il faut couvrir une q − portion de la zone

d’interet. Pour cela, ils ont mis en place une structure de donnees pour representer

la zone d’interet avec n2 points, n etant le nombre de capteurs garantissant une

couverture totale. Leur algorithme prend en compte la surveillance partielle et le

cout de la communication lorsque la portee de la communication est au moins deux

fois plus large que celle de la couverture.

Il est suppose dans le document que des capteurs sont disperses dans la region

R a couvrir et que chaque capteur pi a sa propre region a couvrir Ri. Cela veut

dire que pi peut collecter les donnees dans Ri sans l’aide d’aucun autre capteur.

Il est aussi considere que chaque capteur pi a une quantite d’energie initiale bi

qui peut etre mesuree par le temps durant lequel pi peut collecter des informa-

tions provenant de Ri. Le nombre de nœuds deployes est largement superieur au

nombre de nœuds necessaire pour couvrir la zone. Ainsi il est possible de rendre

inactifs certains nœuds pour sauvegarder leur energie et prolonger la duree de vie

du reseau. Les capteurs sont capables d’alterner leur etat plusieurs fois cependant

la zone d’interet R doit etre a tout moment soit completement soit partiellement



couverte par les nœuds actifs.

Berman et al ont donne une definition formelle du probleme de la reduction

de la consommation d’energie. Ils ont considere comme etant le planning de la

couverture l’ensemble de couples (C1, t1), . . . , (Ck, tk) avec Ci etant un ensemble

de capteurs couvrant la zone d’interet R et ti le temps durant lequel Ci est ac-

tif. Ainsi, considerant une zone d’interet R, un ensemble de capteurs p1, . . . , pn,

une region de couverture Ri et une energie initiale bi pour chacun d’entre eux, le

probleme de la duree de vie du reseau se resume a trouver un planning de couver-

ture (C1, t1), . . . , (Ck, tk) avec la plus grande duree t1 + . . .+ tk, de telle facon que

pour chaque capteur pi la periode totale d’activite ne depasse pas bi.

3.2.2 Les travaux de Zhang et Hou

Honghai Zhang et Jennifer Hou ont etudie le probleme de la prolongation de la

duree de vie d’un reseau de capteurs sans fil en considerant celle-ci comme etant

le temps durant lequel au moins une portion α de la zone d’interet est couverte.

Ils ont appele cette duree de vie α-lifetime. Ils ont propose un algorithme qui fait

une planification de l’activite des nœuds pour allonger le α-lifetime d’un reseau de

capteurs sans fil. Zhang et Hou ont etudie le probleme de la duree de vie du reseau

dans le cas ou, a tout moment, seulement α portion de la zone d’interet doit etre

couverte (avec 0 < α < 1). L’algorithme determine un nombre maximum de sous

ensembles disjoints de telle sorte que les nœuds de chaque sous ensemble puissent

couvrir au moins une portion α de la zone d’interet. Il planifie les moments d’ac-

tivite et d’inactivite des nœuds. Pour cela, il choisit un sous ensemble de nœuds

qui devra etre actif a chaque round.



Cette etude [ZH06] montre que pour accroitre la duree de vie du reseau, il est

possible soit de deployer un tres grand nombre de nœuds comme dans le cas des

algorithmes distribues ou de faire la concession de laisser une petite portion de la

zone d’interet non couverte. Pour ce dernier cas, l’algorithme devra des le debut

indiquer une α-couverture de la zone d’interet, ou α represente le pourcentage de la

zone d’interet qui ne pourra pas etre couverte. Leur etude a aussi laisse apparaitre

que choisir dans chaque round un nombre minimal de nœuds qui vont assurer

la couverture est moins optimale que de choisir un ensemble de nœuds qui vont

minimiser la consommation d’energie des nœuds restants.

3.2.3 Les travaux de Cardei et al.

Cet algorithme de Mihaela Cardei, My T. Thai, Yingshu Li et Weili Wu

[CTLW05] propose une methode efficace pour optimiser la duree de vie du reseau

de capteurs en organisant les nœuds capteurs en un nombre maximal d’ensembles

de couverture qui sont actives successivement. Quand un ensemble est actif, les

capteurs constituant cet ensemble sont responsables de la couverture de tous les

points de la zone d’interet et de la transmission des donnees collectees tandis que

les autres nœuds sont en etat de veille consommant moins d’energie.

L’algorithme utilise la technique du � duty cycling �. Il s’agit d’une des methodes

utilisees pour reduire la consommation d’energie des nœuds capteurs et consiste a

alterner leur fonctionnement en une mode active et une mode veille. L’algorithme

aborde le probleme de la maximisation de la duree de vie du reseau de capteurs en

etudiant le probleme de la couverture d’un ensemble de points localises du reseau


3.3. Techniques distribuees 33

et considere la duree de vie du reseau comme l’intervalle de temps durant lequel

chaque objectif (zone cible) du reseau est couvert par au moins un nœud capteur.

Il se propose d’allonger la duree de vie du reseau en divisant les nœuds en un

nombre d’ensembles non-disjoints de telle facon que chaque ensemble couvre a lui

seul tous les objectifs du reseau. Ces ensembles sont actives a tour de role de telle

sorte qu’en tout temps, un seul ensemble est actif a la fois. Cela permet non seule-

ment de couvrir toute la zone d’interet mais aussi d’allonger la duree de vie du

reseau, du moment ou les nœuds sont programmes pour alterner de l’etat actif a

l’etat veille, compare au cas ou tous les nœuds du reseau sont tous continuellement

actifs.

3.3 Techniques distribuees

3.3.1 Low-Energy Adaptive Clustering Hierarchy : LEACH

Les capteurs sont utilises pour detecter des phenomenes du milieu physique,

d’effectuer un traitement et de transmettre l’information qui en decoule a un

� sink �. Des protocoles de communication sont alors necessaires pour le bon

deroulement de cette operation. Cependant la plupart de ces protocoles soit ne

tiennent pas en compte des contraintes energetiques des reseaux de capteur soit ils

ne sont pas optimaux. Ainsi, LEACH est un protocole qui vient palier a quelques

uns de leurs manquements et qui permet de reduire a hauteur de 8 fois la perte

d’energie compare aux protocoles de routage conventionnels.

LEACH est un protocole qui utilise des techniques de randomisation pour

distribuer la charge d’energie entre les nœuds du reseau [HCB00]. LEACH est



completement distribue. Il ne requiert aucun controle de la station centrale de base

et les nœuds n’ont pas a garder des informations sur leurs voisins. Avec LEACH,

les nœuds s’organisent en des clusters avec des nœuds jouant le role de � chefs de

cluster �. Dans d’autres algorithmes ou les � chefs de cluster �sont choisis et fixes

a priori, il est remarque que ces nœuds s’epuisent rapidement et epuise aussi la

duree de vie du cluster, rendant ainsi inefficaces les autres nœuds appartenant a

ce cluster. C’est pour cela que LEACH utilise des techniques de rotation aleatoire

pour determiner la position du chef de cluster de telle facon que celle-ci puisse

varier entre tous les nœuds du reseau afin de ne pas epuiser toute l’energie d’un

seul nœud. Egalement, LEACH effectue localement une fusion de donnees afin de

reduire la quantite de donnees qui doit etre transmise depuis les clusters vers la

station de base, en plus de reduire l’energie consommee et donc d’augmenter la

duree de vie du reseau.

Les capteurs se designent pour etre chef de cluster avec une certaine proba-

bilite. Ils envoient aux autres nœuds un message broadcast contenant leur statut.

Chacun de ces autres nœuds determine alors le cluster auquel il veut appartenir en

indiquant le chef de cluster avec lequel une communication necessiterait le moins

d’energie. Cela revient, la plupart du temps 1, a choisir le chef de cluster qui est le

plus proche de lui. Une fois que tous les nœuds sont organises en clusters, chaque

chef de cluster cree un planning au sein de son cluster. Celui-ci a pour but d’in-

diquer a tous les nœuds ordinaires du cluster d’eteindre leur dispositif radio et de

ne les rallumer que lors de l’operation de transmission du chef de cluster. On note

1. En effet, cela n’est pas toujours le cas. Le nœud peut choisir comme chef de cluster un nœudtres eloigne lorsqu’ a cause d’inferences ou d’autres difficultes techniques, la communication avecles autres chefs de cluster qui sont plus proches de lui est rendue plus difficile qu’avec le chef decluster eloigne.



ainsi une reduction de l’energie consommee par les autres nœuds. C’est aussi le

nœud chef de cluster qui est charge de faire une agregation des donnees qu’il recoit

des autres nœuds de son cluster et de les transmettre ensuite a la station de base.

Ceci permet de compresser la taille des donnees transmises et donc de reduire le

nombre de communications. Le reseau y gagne en economie d’energie vu que la

fusion de donnees consomme moins d’energie que la communication.

Comme sous-entendu plus haut, le chef de cluster consomme plus d’energie que

les autres nœuds ordinaires du fait de toutes les taches qui lui sont assignees. Afin

de repartir cette consommation d’energie a travers tout le reseau, le chef de cluster

va varier au fil du temps et, a differentes periodes, un autre nœud se designe chef

de cluster. Ainsi, en un temps t1, un ensemble C de nœuds s’auto-designe chefs

de clusters et en t1 + d, un autre ensemble C ′ de nœuds va prendre le relais et

devenir chefs de clusters a son tour, dependant de la quantite d’energie qui reste

a ces nœuds, comme le montre la figure 3.1. De cette facon, ce sont toujours les

nœuds avec le plus de reserve d’energie qui se verront assigner les taches les plus

consommatrices de ressources au sein du reseau.

Details de l’algorithme LEACH

L’execution de LEACH est divisee en rounds de telle sorte que chaque round

debute avec une phase d’initialisation, dans laquelle se fait l’organisation des clus-

ters, suivie d’une phase constante dans laquelle a lieu les transferts de donnees vers

la station de base. En vue de reduire les consommations de ressources, la phase

constante est longue comparee a la phase d’initialisation.



Figure 3.1 – Clusters dynamiques : (a) cluster C en un temps t1. (b) cluster C ′

en un temps t1 + d. Les noeuds marques d’un meme symbole appartiennent aumeme cluster. Les chefs de cluster sont representes par un gros point.

La phase d’annonce Initialement lors de la creation des clusters, chaque nœud

decide de devenir ou non un chef de cluster pour le round courant. Cette decision

est basee sur le pourcentage suggere 2 de chefs de clusters dans le reseau et du

nombre de fois que le nœud a ete auparavant chef de cluster. Le nœud n decide de

devenir chef de cluster en choisissant un nombre aleatoire compris entre 0 et 1. Si

ce nombre est plus petit qu’un seuil T (n), alors le nœud n devient chef de cluster.

Le seuil est ainsi determine :

T (n) =

P

1−P×(r mod 1P )

si n ∈ G,

0 sinon

Ou P est le pourcentage desire de chefs de cluster, r le round courant et G est

l’ensemble de nœuds qui n’ont pas ete chefs de cluster dans les 1P

derniers rounds.

Durant le round 0 (r = 0), chaque nœud a une probabilite P de devenir chef de

cluster. Les nœuds qui seront chefs de cluster au round 0 ne pourront pas le devenir

2. Ce pourcentage est determine a priori.



pour les 1P

rounds suivants. De ce fait, la probabilite pour que les nœuds restants

soient des chefs de cluster va augmenter puisque un nombre reduit de nœuds est

eligible comme chef de cluster. Apres 1P− 1 rounds, (c’est-a-dire lorsqu’il ne reste

qu’un seul round), T devient egal a 1 pour tous les nœuds qui n’ont pas encore ete

chefs de cluster ; et apres 1P

rounds, tous les nœuds deviennent a nouveau eligibles

pour etre chef de cluster.

Lorsqu’un nœud devient un chef de cluster pour le round courant, il envoie un

message broadcast pour l’annoncer aux nœuds restants. Tous les nœuds chefs de

cluster consomment la meme quantite d’energie lors de cette phase d’annonce. Les

nœuds ordinaires ont alors leur equipement radio allume durant toute cette phase

d’initialisation pour etre capable de recevoir ces messages. C’est lorsque cette phase

s’acheve que chaque nœud ordinaire choisit le cluster auquel il appartient pour ce

round, grace a la force du signal des messages broadcast qu’il a recus. Ceci du fait

que le chef de cluster dont le message a ete recu avec une plus grande force de signal

sera sans doute celui avec qui une communication necessitera moins d’energie. S’il

y’a cependant ex aequo dans le choix entre plusieurs clusters, la decision se fera

aleatoirement.

L’initialisation des clusters Apres qu’un nœud ait choisi le cluster auquel il

appartient, il doit informer le chef de ce cluster. Tous les nœuds ordinaires envoient

ainsi un message de ce type aux chefs de cluster et durant cette phase, le dispositif

radio des chefs de clusters est en marche.

La creation d’un planning Comme souligne un peu plus en haut dans le

debut de la sous-section 3.3.1, chaque chef de cluster cree un planning au sein de



son cluster dans le but d’indiquer a tous les nœuds ordinaires du cluster d’eteindre

leur dispositif radio et de ne les rallumer que lorsqu’il devra effectuer une operation

de transmission. Le chef de cluster recoit les messages de tous les nœuds voulant

faire partie de son cluster. Il se base sur leur nombre et indique a chacun d’entre

eux, grace a un message broadcast le moment auquel ils pourront transmettre.

La phase de transmission de donnees Apres que les clusters soient crees

et que le planning soit fixe, la phase de transmission peut commencer. Lorsqu’un

nœud a des donnees a transmettre au chef de cluster, il le fait durant le moment

de transmission qui lui est fixe. La consommation d’energie liee a cette operation

est optimisee puisque le nœud ordinaire a eu auparavant a choisir le chef de clus-

ter avec qui une communication serait moins couteuse. Durant tout le moment de

transmission, les autres nœuds ordinaires eteignent leur dispositif radio, minimi-

sant ainsi leur consommation d’energie. Le chef de cluster quant a lui garde sa

radio active pour recevoir les signaux qui lui seront transmis de l’ensemble des

nœuds du cluster. Lorsque toutes les donnees ont fini de lui etre transmises, le chef

de cluster les compresse en un seul signal qu’il transmettra a son tour a la station

de base.

C’est cette phase qui correspond a la phase constante de l’algorithme de LEACH.

C’est apres cette phase que va debuter un nouveau round et ainsi reprend le pro-

cessus.

Resume de l’evaluation de la performance

Dans [HCB00], les simulations ont montre que la dissipation de l’energie dans

le reseau varie en fonction du pourcentage de nœuds qui sont chefs de cluster.



La figure 3.2 permet d’illustrer cela. La figure fait aussi remarquer qu’un etat du

reseau ou il n’existe aucun chef de cluster est equivalent a l’etat ou tous les nœuds

sont chefs de cluster et que la consommation d’energie est tres elevee dans chacun

de ces cas. Ceci du fait que dans chacun de ces cas, tous les nœuds vont effectuer

des operations couteuses de transmission vers la station de base. La figure montre

egalement comment la technique de LEACH peut permettre une reduction par 7

de la perte d’energie comparee a une transmission directe dans laquelle chaque

nœud communique directement avec la station de base. Ceci lorsqu’un nombre

optimal N de chefs clusters est choisi.

Figure 3.2 – Perte d’energie dans le reseau par rapport au nombre de chefs decluster

D’une facon generale, ces simulations ont montre que LEACH, comparee a une

technique de transmission directe, reduit a hauteur de 8 fois l’energie consommee

par la communication ; et que le premier evenement d’epuisement d’energie d’un

nœud survient 8 fois plus tard. Une autre performance de LEACH reside dans le fait



que les nœuds epuisent leur energie d’une facon aleatoire. Avec cela, l’homogeneite

du reseau est conservee et il n’y aura pas de zones peu couvertes au detriment

d’autres.

3.3.2 L’algorithme ASCENT : Adaptive Self-Configuring

Sensor Networks Topologies

Dans les reseaux de capteurs, le grand nombre de nœuds empeche la configura-

tion manuelle et les changements frequents dans la topologie ne permettent pas une

pre-configuration de la conception. De ce fait, dans certains cas, les nœuds doivent

etre capables de s’auto-configurer pour etablir une topologie qui supportera toutes

les communications compte tenu des contraintes energetiques. ASCENT est base

sur l’idee que, meme quand la densite de nœuds augmente, seul un sous ensemble

d’entre eux est necessaire dans le maintien des operations de routage [CE04]. Ce

sont ces quelques nœuds qui vont executer les taches de routage et de traitement

pendant que les autres seront en mode ”passive” economisant ainsi une bonne par-

tie de l’energie. Dans ASCENT, chaque nœud evalue son degre de connectivite et

adapte ainsi sa participation a la topologie du reseau.

En effet la conception d’ASCENT a ete influencee par beaucoup d’autres tra-

vaux du domaine. Il y’a eu un grand nombre de travaux similaires qui se sont

concentres sur la configuration des topologies d’un reseau. La plupart d’entre eux

ont utilise des techniques theoriques d’analyses et des techniques de simulation

tout en impliquant des mecanismes de controle de la consommation d’energie. Ils

se sont bases sur la construction d’un sous-ensemble dominant connecte de nœuds

(Connecting Dominating Set) a travers lequel reposaient toutes les strategies de



routage.

Conception de ASCENT

ASCENT choisit de facon adequate a partir de tous les nœuds du reseau, des

nœuds qui vont etre en mode active. Ceux la restent � eveilles �tout le temps et

vont accomplir les taches de routage multi-saut au sein du reseau, pendant que

le reste des nœuds, en mode passive, vont controler periodiquement s’ils doivent

entrer en mode active ou non.

Considerons un simple reseau sans fil pour la collecte de donnees dans un

environnement. La figure 3.3 montre un schema simplifie d’ASCENT lors de l’ini-

tialisation du reseau. Pour des soucis de clarte, il n’est montre que la formation

d’un reseau a deux sauts. Cela peut bien evidemment etre applique a d’autres

reseaux de plus grande taille.

Initialement, seuls quelques nœuds sont actifs. Les autres nœuds restent en

mode passive, a l’ecoute des paquets de donnees mains sans transmettre (cf. Fig.

3.3a). La source commence a emettre des paquets de donnees en direction du

”sink”. Ce dernier se trouvant a une position limite de la portee du radio de la

source perd beaucoup de donnees. Cette situation est communement appelee un

trou de communication. Le ”sink” commence des lors a envoyer des messages help a

ses nœuds voisins qui sont en mode passive et les invite a rejoindre le reseau. Lors-

qu’un voisin recoit un message help, il peut decider de rejoindre le reseau. Cette

situation est illustree dans la figure 3.3b. Des lors, il commence a transmettre et

a recevoir des paquets. Il signale aussitot aux nœuds passifs l’existence d’un nou-



veau nœud actif, c’est-a-dire lui, en envoyant un message neighbor announcement.

Cette situation continue jusqu’a ce que le nombre de nœuds actifs se stabilise et

donc le cycle s’arrete (cf. Fig. 3.3c). Lorsque ce processus se termine, les nouveaux

nœuds actifs rendent la transmission des paquets de donnees, de la source vers le

”sink”, beaucoup plus solide. Lorsqu’aussi survient quelques defaillances de cer-

tains nœuds, causant des pertes de donnees, le mecanisme reprend pour corriger les

erreurs. Les titres suivants vont rentrer en detail dans la conception de l’algorithme

de ASCENT et mieux decrire son schema.

Figure 3.3 – Exemple simplifie d’autoconfiguration d’un reseau . (a) Trou decommunication. (b) Etat de transition. (c) Etat final.

Les etats de transition dans ASCENT Dans ASCENT, les nœuds peuvent

etre dans quatre etats differents : un nœud peut etre en mode sleep, passive, test,

ou active. Il ne peut cependant pas etre dans les quatre en meme temps. La figure

3.4 ilustre les transitions d’etat possibles. Initialement, les nœuds ont une minute-

rie pour effectuer la synchronisation.

Quand un nœud sort de l’etat � endormi �, c’est-a-dire demarre sa radio et son

transceiver, il rentre en mode test. Dans cet etat, les nœuds echangent des donnees



et des messages de routage. Le nœud qui rentre en mode test choisi un temps Tt

et envoie des messages neighbor announcement a ses voisins passifs. Lorsque Tt

expire, le nœud entre en mode active. Si cependant, avant l’expiration de Tt, le

nombre de nœuds actifs atteint un seuil NT ou si le taux de donnees perdues DL

a depasse le DL qui existait au moment de la transition vers l’etat test, alors le

nœud entre plutot en mode passive. Si plusieurs nœuds veulent entrer en meme

temps en mode test, alors les identifiants qui leur sont donnes lors de l’envoi des

messages neighbor announcement servira a les departager dans la selection. Ainsi,

l’etat test permet � d’interroger �le reseau, afin de savoir si la participation d’un

nouveau nœud pourra accroıtre sa connectivite.

Figure 3.4 – Etats de transitions dans ASCENT

Quand un nœud entre dans le mode passive, il demarre un minuteur Tp et

envoie des messages pour s’annoncer. Ces messages sont utilises par les nœuds

actifs pour estimer la densite de nœuds actifs dans leur voisinage. Cette densite

est par la suite envoyee a tout nœud qui viendra a rentrer en mode passive.

Lorsque Tp est ecoule, le nœud entre en mode sleep. Cependant si avant ceci, le

nombre de nœuds voisins actifs est au dessous du seuil NT et que soit le DL

est plus grand que le seuil de donnees perdues LT , ou que le DL est plus petit



que le LT mais qu’un message HELP a ete recu par le nœud, celui-ci passe vers

l’etat test. Dans l’etat passive, les nœuds ont leur dispositif radio allume et sont

capables d’entendre toutes les transmissions de leurs voisins. Par contre, dans cet

etat, ils ne peuvent effectuer aucune operation de routage puisqu’il s’agit d’un

etat d’ecoute. Donc le mode passive est un etat dans lequel le nœud accomplit

des taches de collecte d’information concernant l’etat du reseau sans interferer

sur celles des autres nœuds. Les nœuds dans les etats passive et sleep mettent

continuellement a jour le nombre de voisins actifs et le taux de perte de donnees.

De l’energie est consommee dans l’etat passive puisque le dispositif radio est actif.

Lorsque le nœud est dans l’etat sleep, il eteint sa radio, declenche une minuterie

Ts. Quand Ts est ecoule, il rentre en mode passive. Finalement, le nœud qui entre

en mode active effectue des operations de routage et d’acheminement de donnees

jusqu’a totale epuisement de son stock d’energie. Il envoie des messages HELP

lorsque le taux de perte de donnees depasse le seuil LT .

3.3.3 Un protocole robuste de conservation d’energie pour

les reseaux de capteurs a longue duree de vie : PEAS

Fan Ye et al. ont developpe un mecanisme appele PEAS [YZC+03] qui peut

allonger la duree de vie d’un reseau de capteurs sans fil de grande densite dans

un milieu hostile [WX06]. PEAS maintient les operations robustes en utilisant de

grandes quantites de nœuds de capteurs economiques et de courte duree de vie. Il

prolonge le temps de fonctionnement du systeme en faisant seulement travailler un

ensemble de capteurs necessaires et en mettant le reste en mode veille. Par periode,

les capteurs qui sont en veille se reveillent et sondent l’environnement local pour

remplacer ceux qui sont hors d’usage. Les periodes de veille sont auto-ajustees de



facon dynamique, afin de maintenir la vitesse de reveil des capteurs a peu pres

constante, s’adaptant ainsi aux grandes densites de nœuds.

PEAS partage la technique basique de desactivation de nœuds avec d’autres

protocoles de conservation d’energie dans les reseaux ad hoc sans fil (GAF [XHE01],

SPAN [CJBM02], AFECA [XHE00]) et dans les reseaux de capteurs (ASCENT

[CE04]). Toutefois, les travaux existants sont destines a des ordinateurs portables

beaucoup plus puissants et/ou a un environnement de reseau relativement stable,

tandis que la conception de PEAS cible un environnement de travail beaucoup

plus severe voire hostile, ou :

– les defaillances des nœuds de capteurs peuvent devenir plutot frequentes,

– la densite du deploiement des nœuds peut etre d’une grandeur beaucoup plus

elevee que le minimum requis pour le fonctionnement normal

– et les nœuds sont trop limites en ressources memoire et en ressources de cal-

cul pour se permettre des protocoles relativement complexes.

Aucun des travaux apparentes n’aborde la question des operations robustes

dans la mise en environnement hostile que la conception de PEAS a pris en

consideration. PEAS realise une operation tres robuste en decidant aleatoirement

la duree du sommeil des nœuds endormis afin de detecter et de remplacer acti-

vement les nœuds en panne. Il elimine les etats par voisins, supprimant ainsi la

complexite de suivre chaque voisin dans un deploiement dense. C’est en contra-

diction avec les travaux apparentes qui necessitent soit un entretien des etats par

voisin ou une estimation des temps d’activite des nœuds en travail, qui sont diffi-



ciles a realiser lorsque les nœuds sont densement deployes et soumis a de frequentes

pannes.

La conception de PEAS

PEAS consiste en deux algorithmes simples que nous pourrons nommer : son-

dage de l’environnement (Probing Environment) et mise en veille appropriee (Adap-

tive Sleeping), qui determinent respectivement (1) quels capteurs devraient fonc-

tionner et comment un capteur qui vient de se reveiller decide si il doit se rendormir,

et (2) comment les temps de sommeil moyens des capteurs sont ajustes de maniere

appropriee pour garder une vitesse de reveil relativement constante.

Probing Environment (Sondage de l’environnement) L’objectif de cet al-

gorithme est de maintenir un nombre suffisant des nœuds, en cas de defaillances

de quelques autres nœuds. PEAS utilise un mecanisme de sondage simple pour

resoudre le probleme. Initialement tous les nœuds sont en veille et cela pendant un

certain temps aleatoire exponentiellement distribue. Quand un nœud se reveille,

il envoie un message PROBE au sein d’une certaine plage de sondage Rp. Tous

des nœuds en activite au sein de Rp devraient renvoyer un message de reponse.

Un nœud en veille commence son travail en permanence seulement s’il ne recoit

pas de message de reponse. Sinon, il retourne a nouveau en veille pour une autre

duree aleatoire.

Le temps de sommeil distribue de facon exponentielle permet de mesurer la vi-

tesse de reveil des nœuds et d’ajuster les periodes de veille facilement dans la mise

en veille appropriee (cf. paragraphe sur Adaptive Sleeping). La plage de sondage

Rp est donnee par l’application en fonction du degre de robustesse dont elle a be-



soin. Une application necessitant un fonctionnement tres robuste peut choisir une

petite Rp pour obtenir une plus grande densite, une redondance donc plus elevee

des nœuds en travail. Pour eviter la deconnexion du reseau, Rp est generalement

beaucoup plus petit que la plage de transmission maximale Rt d’un capteur. Il

est suppose que les nœuds peuvent ajuster leur puissance de transmission pour

diffuser des messages PROBE en fonction de la plage de sondage Rp.

Adaptive Sleeping (Mise en veille appropriee) L’objectif de la mise en

veille adaptative est de maintenir le nombre d’eveils par unite de temps constant

et independant des densites de nœuds locaux, qui varient suivant les deploiements,

suivant les endroits ou les moments. La frequence souhaitee des reveils depend

de l’application. La mise en veille appropriee ajuste, pour chaque nœud actif,

les reveils de ses nœuds voisins en veille, a des niveaux appropries, afin que les

interruptions transitoires dans la detection et la communication causees par des

defaillances de nœud soient tolerees par l’application.

L’idee de base est de laisser chaque nœud actif mesurer le taux total de sondage

λ qu’il percoit de tous ses voisins en veille. Le nœud actif inclut alors le taux mesure

λ lorsqu’ il envoie un message REPLY a un voisin qui sonde l’environnement. Tous

les nœuds qui etaient entrain de sonder ajustent alors la duree de leur sommeil en

consequence.

Resume de l’evaluation de la performance

Fan Ye et Gary Zhong ont implemente PEAS et evalue ses performances grace a

deux indicateurs principaux : la duree de vie de la couverture et celle de la livraison

de donnees. La duree de vie de la couverture designe la periode pendant laquelle le



reseau a suffisamment de nœuds actifs pour s’assurer que chaque endroit est sur-

veille par des nœuds actifs. La duree de vie de la livraison de donnees represente le

temps pendant lequel le reseau peut fournir des rapports de donnees avec succes.

Les resultats montrent que PEAS maintient une resistance robuste contre les

defaillances de nœuds a hauteur de 38% (incluant les epuisements d’energie) a

moins de 1% de l’energie generale, et prolonge le temps de fonctionnement du

systeme proportionnellement au nombre de nœuds deployes.

Ils ont d’abord varie le pourcentage de defaillance des nœuds de 7% a 38%.

La duree de vie de la couverture et celle de la livraison des donnees diminuent

harmonieusement avec les defaillances des nœuds (cf. figure 3.5). Meme pour les

defaillances de nœuds portees a 38%, les deductions sont d’environ 20%. Puis ils

ont fait varier a plus de 5 fois le nombre de nœuds necessaires dans un champ pour

couvrir la detection de base avec une defaillance des nœuds fixee a 13%. Aussi bien

la duree de vie de la couverture que celle de la livraison de donnees augmentent de

facon lineaire au nombre de nœuds deployes (cf. figure 3.6). Enfin ils ont mesure

le surcout de PEAS dans l’energie consommee par les operations de sondage et de

reponse et ils ont trouve qu’elle etait inferieure a 1% de la consommation totale

d’energie.



Figure 3.5 – Resistance aux defaillances de nœuds

Figure 3.6 – Extension de la duree de vie


CHAPITRE 4

Conclusions

50

51

Les avancees de la micro-electronique ont favorise l’usage de la technologie des

capteurs sans fil. Ce sont de petits equipements munis d’une unite d’acquisition,

d’une unite de traitement, d’une unite de transmission de donnees et d’une source

d’energie qui leur permettent d’assurer des taches de detection de phenomenes

physiques, de traitement de l’information et de transmission des donnees. Ces ap-

pareils lorsqu’ils sont utilises de facon collaborative forment un reseau de capteurs

sans fil et sont d’une tres grande utilite dans plusieurs domaines de la science mais

aussi dans la vie de tous les jours. Ils sont utilises dans la medecine, l’armee, la

domotique, etc. Toutefois, vu leur capacite en stockage, leur puissance de calcul et

leur source d’energie limitees, les reseaux de capteurs sans fil doivent faire face a

d’importants defis dans leur conception et leur exploitation. Ainsi, differentes solu-

tions prenant en consideration ces contraintes ont ete envisagees pour les reseaux

de capteurs.

Dans ce document, apres notre introduction, nous avons eu a traiter de quelques

generalites dans les reseaux de capteurs sans fil pour mieux entamer le sujet de

notre travail. Nous y avons etudie l’anatomie des capteurs pris individuellement

puis l’architecture du reseau de capteurs ainsi que leur organisation protocolaire

en couches. Nous avons aussi, toujours dans les generalites, montre quelques do-

maines dans lesquels les applications des reseaux de capteurs sont d’une grande

utilite. Cela nous a donne une idee des exigences auxquelles les reseaux de capteurs

doivent satisfaire et il a par la suite ete facile de ressortir des contraintes liees a

leur conception et a leur exploitation. Ce sont ces contraintes parmi tant d’autres

qui ont motive beaucoup de chercheurs a developper un bon nombre de protocoles

et algorithmes pour les reseaux de capteurs. Cependant, il est tres difficile voire


52

impossible de trouver une solution generique adaptee a toutes les applications des

reseaux de capteurs. C’est cela qui nous a pousse a aborder le probleme de l’op-

timisation de leur duree de vie a travers differentes techniques trouvees dans la

litterature que l’on a jugees comme couvrant plus ou moins les differentes methodes

existantes de reduction d’energie dans les reseaux de capteurs sans fil. Nous les

avons separees en techniques centralisees et en techniques distribuees pour rester

fidele au sujet de notre travail. C’est ainsi que, toujours a un dessein de clarte,

nous avons d’abord eu a indiquer les nombreuses definitions qui sont donnees de

la duree de vie d’un reseau de capteurs sans fil. Ces definitions dependent de l’ob-

jectif de l’application ou des hypotheses prises en compte. Ensuite, munis de cet

eclaircissement sur ce qu’est la duree de vie d’un reseau de capteurs, nous avons

analyse quelques solutions centralisees et distribuees visant a reduire la consom-

mation d’energie donc a optimiser cette duree de vie. Elles utilisent pour la plupart

des techniques de ” duty cycling ”, de randomisation, etc. Certaines d’entre elles

obligent chaque nœud a avoir l’information sur l’etat de ses voisins tandis que cela

n’est pas necessaire dans d’autres. Quelques unes divisent le reseau en clusters,

font une certaine hierarchisation au sein des nœuds du reseau en choisissant des

chefs de cluster, tandis que dans d’autres une station centrale est necessaire. Tous

ces procedes ont toutefois pour objectif principal d’economiser l’energie des nœuds

et d’allonger la duree de vie du reseau de capteurs sans fil.


ANNEXE A

Anatomie du capteur TelosB et comparaison des

fonctionnalites de quelques autres (xbow)

53

A.1. Anatomie du capteur TelosB 54

A.1 Anatomie du capteur TelosB

Figure A.1 – Anatomie du capteur TelosB

A.2 Comparaison des fonctionnalites de quelques

capteurs


A.2. Comparaison des fonctionnalites de quelques capteurs 55

Fonctionnalites MTS300 MTS310 MTS400 MTS420Accelerometre X X X

Lumiere ambiente X XBarometre X X

Vibreur X XGPS X

Champ magnetique XMicro X X

Photosensible X XPhotoresistant X X

Humidite et temperature X XThermistance X X

Table A.1 – Quelques capteurs et leurs fonctionnalites

XM2110 M2110 MPR2400 MPR400

Champ de 2.4GHz 2.4GHz 2.4GHz 868-870 ;frequence ISM Band ISM Band ISM Band 902-928MHzProcesseur Atmel Atmel Atmel Atmel

ATMega 1281 ATMega 1281 ATMega 128L ATMega 128LTransceiver RF230 RF230 TI TIRadio Atmel Atmel CC2420 CC1000

Atmel Atmel Atmel AtmelSerial Flash AT45DB41B AT45DB41B AT45DB41B AT45DB41B

(512 kB) (512 kB) (512 kB) (512 kB)RAM 8 KBytes 8 KBytes 4 KBytes 4 KBytes

Table A.2 – Quelques capteurs et leurs caracteristiques techniques


Bibliographie

[A+06] Jean ARLAT et al. Tolerance aux fautes. In Encyclopedie de l’in-

formatique et des systemes d’information, (J. Akola and I. Comyn-

Wattiau, Eds.), pages 240–270. Vuibert, Paris, France, 2006.

[ASSC02] I. F. AKYILDIZ, W. SU, Y. SANKARASUBRAMANIAM, and

E. CAYIRCI. Wireless sensor networks : a survey. Computer Net-

works, 38 :393–422, 2002.

[AV10] I. F. AKYILDIZ and M. C. VURAN. Wireless Sensor Networks, chap-

ter 3, pages 37–39. John Wiley and Sons, 2010.

[BBC10] Antimo BARBATO, Luca BORSANI, and Antonio CAPONE. Home

energy saving through wireless sensor networks. In 1st International

Conference on Energy-Efficient Computing and Networking e- Energy

2010, Passau, Germany, April 2010.

[BC] UC Berkeley and MLB Co. 29 palms fixed/mobile expe-

riment, tracking vehicles with a uav-delivered sensor network,

http ://robotics.eecs.berkeley.edu/~pister/29palms0103/.

56

Bibliographie 57

[BCSZ05] P. BERMAN, G. CALINESCU, C. SHAH, and A. ZELIKOVSKY.

Efficient energy management in sensor networks. In Ad Hoc and Sensor

Networks. Nova Science Publishers. Nova Science Publisher, 2005.

[BSIP00] P. BAUER, M. SICHITIU, R. ISTEPANIAN, and K. PREMA-

RATNE. The mobile patient : wireless distributed sensor networks

for patient monitoring and care. In Proceedings 2000 IEEE EMBS

International Conference on Information Technology Applications in

Biomedicine, pages 17–21, 2000.

[C+94] B. G. CELLER et al. An instrumentation system for the remote mo-

nitoring of changes in functional health status of the elderly. In Inter-

national Conference IEEE-EMBS, pages 908–909, New York, 1994.

[C+95] G. COYLE et al. Home telecare for the elderly. Journal of Telemedi-

cine and Telecare 1, pages 183–184, 1995.

[CE04] Alberto CERPA and Deborah ESTRIN. Ascent : Adaptive self-

configuring sensor networks topologies. IEEE Transactions on Mobile

Computing, 3 :272–285, July 2004.

[CJBM02] Benjie CHEN, Kyle JAMIESON, Hari BALAKRISHNAN, and Ro-

bert MORRIS. Span : An energy-efficient coordination algorithm for

topology maintenance in ad hoc wireless networks. Wireless Networks,

8 :481–494, 2002. 10.1023/A :1016542229220.

[CTLW05] Mihaela CARDEI, My T. THAI, Yingshu LI, and Weili WU. Energy-

efficient target coverage in wireless sensor networks. In IEEE Infocom,

2005.


Bibliographie 58

[Dim] Dimap. Sistemas de seguimiento y vigilancia ambiental,

http ://www.libelium.com/wireless sensor networks to detec forest fires/.

[HCB00] Wendi Rabiner HEINZELMAN, Anantha CHANDRAKASAN, and

Hari BALAKRISHNAN. Energy-efficient communication protocol for

wireless microsensor networks. In Proceedings of the 33rd Hawaii In-

ternational Conference on System Sciences, 2000.

[KAC09] Rahim KACIMI. Techniques de conservation d’energie pour les

reseaux de capteurs sans fil. PhD thesis, Institut National Polytech-

nique de Toulouse, July 2009.

[KPSV] Farinaz KOUSHANFAR, Miodrag POTKONJAK, and Alberto

SANGIOVANNI-VINCENTELLI. Fault tolerance in wireless sensor

networks,” book chapter. In in Handbook of Sensor Networks, I. Mah-

goub and M. Ilyas, page 2004.

[LEH09] Mohamed LEHSAINI. Diffusion et couverture basees sur le clustering

dans les reseaux de capteurs : application a la domotique. PhD the-

sis, Universite A.B Tlemcen Faculte des Sciences pour la ? ?Ingenieur

& Universite de Franche-Comte U.F.R Sciences et Techniques Ecole

Doctorale SPIM, 2009.

[MAK08] Abdallah MAKHOUL. Reseaux de capteurs : localisation, couver-

ture et fusion de donnees. PhD thesis, Laboratoire d’Informatique de

l’Universite de Franche-Comte (LIFC) Ecole Doctorale Sciences Pour

l’Ingenieur et Microtechniques (SPIM), November 2008.

[N+98] Y. H. NAM et al. Development of remote diagnosis system integrating

digital telemetry for medicine. In International Conference IEEE-


Bibliographie 59

EMBS, pages 1170–1173, Hong Kong, 1998.

[NHR+00] N. NOURY, T. HERVE, V. RIALLE, G. VIRONE, E. MERCIER,

G. MOREY, A. MORO, and T. PORCHERON. Monitoring behavior

in home using a smart fall sensor. In IEEE-EMBS Special Topic Confe-

rence on Microtechnologies in Medicine and Biology, pages 607–610,

October 2000.

[O+98] M. OGAWA et al. Fully automated biosignal acquisition in daily rou-

tine through 1 month. In International Conference on IEEE-EMBS,

pages 1947–1050, Hong Kong, 1998.

[PK00] G. POTTIE and W.J. KAISER. Wireless integrated network sensors.

Communications of the ACM, 43 :51–58, May 2000.

[QUN07] Zhao QUN. lifetime maximization for connected target coverage in wi-

reless sensor networks. PhD thesis, National University of Singapore,

Department of Electrical and Computer Engineering, 2007.

[R+06] C. S. RAGHAVENDRA et al. Wireless Sensor Networks, chapter 1,

pages 9–10. Springer Science+Business Media, 2006.

[RAJ+00] Jan M. RABAEY, M. Josie AMMER, Julio L. DA SILVA Jr., Danny

PATEL, and Shad ROUNDY. Picoradio supports ad hoc ultra-low

power wireless networking. IEEE Computer Magazine, pages 42–48,

July 2000.

[sen] Senslab, very large scale open wireless sensor network testbed,

http ://www.senslab.info/.

[VWPK00] S. VARDHAN, M. WILCZYNSKI, G. POTTIE, and W.J. KAISER.

Wireless integrated network sensors (wins) : distributed in situ sen-


Bibliographie 60

sing for mission and flight systems. In IEEE Aerospace Conference,

volume 7, pages 459–463, 2000.

[WX06] L. WANG and Y. XIAO. A survey of energy-efficient scheduling me-

chanisms in sensor networks. Mobile Networks and Applications, 11,

October 2006.

[XHE00] Ya XU, John HEIDEMANN, and Deborah ESTRIN. Adaptive energy-

conserving routing for multihop ad hoc networks. Technical report,

Research Report 527, USC/Information Sciences Institute, 2000.

[XHE01] Ya XU, John HEIDEMANN, and Deborah ESTRIN. Geography-

informed energy conservation for ad hoc routing. In ACM MOBICOM,

pages 70–84, 2001.

[YZC+03] Fan YE, Gary ZHONG, Jesse CHENG, Songwu LU, and Lixia

ZHANG. Peas : A robust energy conserving protocol for long-lived sen-

sor networks. In Proceedings of the 23rd International Conference on

Distributed Computing Systems, ICDCS ’03, Washington, DC, USA,

2003. IEEE Computer Society.

[ZH06] Honghai ZHANG and Jennifer C. HOU. Maximising α-lifetime for

wireless sensor networks. Int. J. Sen. Netw., 1 :64–71, September

2006.


Education

Optimisation centralisée et distribuée de la durée de vie des réseaux de capteurs sans fil