é é é
é é
é
é é
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
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
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
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
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
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
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.
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
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
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
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-
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
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
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
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-
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
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.
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
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
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
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.
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
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
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
2.4. Les differentes applications des reseaux de capteurs sans fil 13
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
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
2.4. Les differentes applications des reseaux de capteurs sans fil 14
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
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
2.4. Les differentes applications des reseaux de capteurs sans fil 15
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
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
2.4. Les differentes applications des reseaux de capteurs sans fil 16
Figure 2.5 – SIstema de Seguimiento y VIgilancia Ambiental
Figure 2.6 – Interfaces de controle du systeme
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
2.4. Les differentes applications des reseaux de capteurs sans fil 17
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
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
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
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
2.5. Les contraintes de conception et d’exploitation 19
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.
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
2.5. Les contraintes de conception et d’exploitation 20
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-
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
2.5. Les contraintes de conception et d’exploitation 21
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.
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
2.5. Les contraintes de conception et d’exploitation 22
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.
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
2.5. Les contraintes de conception et d’exploitation 23
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].
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
2.5. Les contraintes de conception et d’exploitation 24
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.
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
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
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
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
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
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.
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
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.
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
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
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
3.2. Techniques centralisees 31
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.
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
3.2. Techniques centralisees 32
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
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
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
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
3.3. Techniques distribuees 34
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.
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
3.3. Techniques distribuees 35
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.
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
3.3. Techniques distribuees 36
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.
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
3.3. Techniques distribuees 37
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
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
3.3. Techniques distribuees 38
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.
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
3.3. Techniques distribuees 39
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
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
3.3. Techniques distribuees 40
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
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
3.3. Techniques distribuees 41
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-
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
3.3. Techniques distribuees 42
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
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
3.3. Techniques distribuees 43
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
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
3.3. Techniques distribuees 44
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
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
3.3. Techniques distribuees 45
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-
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
3.3. Techniques distribuees 46
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-
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
3.3. Techniques distribuees 47
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
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
3.3. Techniques distribuees 48
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.
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
3.3. Techniques distribuees 49
Figure 3.5 – Resistance aux defaillances de nœuds
Figure 3.6 – Extension de la duree de vie
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
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
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
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.
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
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
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
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
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
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.
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
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-
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
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-
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal
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.
Presente et soutenu par Papa Cheikh Cisse | UGB St-Louis Senegal