Optimisation centralise et distribue de la dure de vie des rseaux de capteurs sans fil

  • Published on
    21-Jun-2015

  • View
    2.796

  • Download
    3

DESCRIPTION

Ceci est un travail de recherche qui reprsente un mmoire de master traitant des rseaux de capteurs sans fil. Ces derniers ont plusieurs domaines d'applications. Cependant, certaines contraintes telles que l'puisement prcoce des capteurs rendent difficiles leur conception. Ce travail a donc eu pour but, aprs avoir ressorti quelques gnralits sur le sujet, d'tudier diffrentes techniques d'optimisation de la dure de vie d'un rseau de capteurs sans fil malgr les dfaillances frquentes des noeuds qui le composent.

Transcript

1. 2. Ddicaces e ` A Allah, Le Tout Puissant, par Qui le savoir a un sens,a` ma tr`s ch`re et brave maman Rokhaya Badiane, eea` mon dfunt et tr`s regrett papa Ibrahima Cisse, ee e a ` ma formidable famille, et ` toutes ces personnes spciales qui ont, durant toutes ces annes, t mesae eeecompagnons de tous les jours et une deuxi`me famille pour moi. Ceux l` qui e anont cess de partager avec moi leur sympathie, leur chaleur, leur estime et leureindulgence.i 3. Remerciements Je tiens a remercier en premier lieu M. Ousmane Thiare qui a accept de men-` ecadrer pour ce travail. Je lui dis merci pour la conance quil ma accorde et poureses pertinentes ides et fructueux conseils. Je remercie aussi M. Maissa Mbayeepour son coup de pouce et pour ses encouragements dont il ma fait bncier.e e Ensuite tous mes sinc`res remerciements iront a tout le corps administratif ete`professoral de lUFR de Sciences appliques et de Technologies qui a assur mae eformation. Je lui suis, pour cela, tr`s reconnaissant. e Je remercie nalement, toute personne qui, de pr`s ou de loin, a contribu ` la eearussite de ce travail. e ii 4. Liste des acronymesADCAnalogic to Digital ConverterASCENT Adaptive Self-Conguring sEnsor Networks TopologiesDARPADefense Advanced Research Projects AgencyGAFGeographic Adaptive FidelityGPSGlobal Positioning SystemIoTInternet of ThingsPDAPersonal Digital AssistantPEAS Probing Environment Adaptive SleepingQoSQuality of ServiceRdCSFRseaux de Capteurs Sans Fileiii 5. ivUAV Unmanned Air VehicleWINSWireless Integrated Network SensorsPrsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 6. Table des gures2.1 Anatomie dun noeud capteur . . . . . . . . . . . . . . . . . . . . . 82.2 Architecture dun rseau de capteurs sans l . . . . . . . . . . . . . 10 e2.3 Architecture en couches des rseaux de capteurs sans l . . . . . . . 11 e2.4 Tracking vehicles with a UAV-delivered sensor network . . . . . . . 142.5 SIstema de Seguimiento y VIgilancia Ambiental . . . . . . . . . . . 162.6 Interfaces de contrle du syst`me . . . . . . . . . . . . . . . . . . . 16 oe2.7 La plateforme Senslab . . . . . . . . . . . . . . . . . . . . . . . . . 193.1 Clusters dynamiques : (a) cluster C en un temps t1 . (b) clusterC en un temps t1 + d. Les noeuds marqus dun mme symboleeeappartiennent au mme cluster. Les chefs de cluster sont reprsentseeepar un gros point. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363.2 Perte dnergie dans le rseau par rapport au nombre de chefs deeecluster . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 v 7. Table des guresvi 3.3 Exemple simpli dautoconguration dun rseau . (a) Trou deee communication. (b) Etat de transition. (c) Etat nal. . . . . . . . . 42 3.4 Etats de transitions dans ASCENT . . . . . . . . . . . . . . . . . . 43 3.5 Rsistance aux dfaillances de nuds . . . . . . . . . . . . . . . . . 49ee 3.6 Extension de la dure de vie . . . . . . . . . . . . . . . . . . . . . . 49e A.1 Anatomie du capteur TelosB . . . . . . . . . . . . . . . . . . . . . . 54Prsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 8. Liste des tableauxA.1 Quelques capteurs et leurs fonctionnalits . . . . . . . . . . . . . . . 55eA.2 Quelques capteurs et leurs caractristiques techniques . . . . . . . . 55 evii 9. Table des mati`res e1 Introduction 12 Gnralits sur les rseaux de capteurs sans l e e e e 42.1 Anatomie dun noeud capteur . . . . . . . . . . . . . . . . . . . . .62.2 Architecture dun rseau de capteurs sans l . . . . . . . . . . . . . e 82.3 Architecture en couches des rseaux de capteurs sans l . . . . . . . 10 e2.4 Les direntes applications des rseaux de capteurs sans l . . . . . 12 e e2.4.1 Applications mdicales . . . . . . . . . . . . . . . . . . . . . 12e2.4.2 Applications militaires . . . . . . . . . . . . . . . . . . . . . 132.4.3 Applications environnementales . . . . . . . . . . . . . . . . 152.4.4 Applications domestiques . . . . . . . . . . . . . . . . . . . . 152.4.5 Autres applications commerciales . . . . . . . . . . . . . . . 172.5 Les contraintes de conception et dexploitation . . . . . . . . . . . . 182.5.1 La tolrance aux fautes . . . . . . . . . . . . . . . . . . . . . 18e2.5.2 Le passage ` lchelle . . . . . . . . . . . . . . . . . . . . . . 19 a eviii 10. Table des mati`reseix 2.5.3 Laspect cot . . . . . . . . . . . . . . . . . . . . . . . . . . 20u 2.5.4 Les contraintes matrielles . . . . . . . . . . . . . . . . . . . 20e 2.5.5 Lenvironnement et la topologie du rseau . . . . . . . . . . 22 e 2.5.6 La consommation dnergie . . . . . . . . . . . . . . . . . . 23 e3 Techniques doptimisation de la dure de vie e 25 3.1 La dure de vie dun rseau de capteurs sans l . . . . . . . . . . . 28 e e 3.2 Techniques centralises . . . . . . . . . . . . . . . . . . . . . . . . . 30 e 3.2.1 Lalgorithme 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 distribues . . . . . . . . . . . . . . . . . . . . . . . . . 33e 3.3.1 Low-Energy Adaptive Clustering Hierarchy : LEACH . . . . 33 3.3.2 Lalgorithme ASCENT : Adaptive Self-Conguring Sensor Networks Topologies . . . . . . . . . . . . . . . . . . . . . . 40 3.3.3 Un protocole robuste de conservation dnergie pour les rseauxe e de capteurs a longue dure de vie : PEAS ` e. . . . . . . . . . 444 Conclusions50A Anatomie du capteur TelosB et comparaison des fonctionnalits e de quelques autres (xbow) 53 A.1 Anatomie du capteur TelosB . . . . . . . . . . . . . . . . . . . . . . 54 A.2 Comparaison des fonctionnalits de quelques capteurs . . . . . . . . 54ePrsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 11. CHAPITRE 1 Introduction1 12. 2es rcentes avances de la micro-lectronique et des technologies sans l ontee eL acclr le processus de miniaturisation des quipements. Le contrle et le ee eeosuivi des phnom`nes physiques deviennent alors beaucoup plus aiss. De nou-e eevelles applications, autrefois dangereuses ou trop couteuses voire irralisables sontedsormais possibles grce a de petits appareils lectroniques sans ls appels nuds ea ` e ecapteurs. Ces derniers sont dploys dans un environnement et sont d`s lors ca- ee epables de recueillir dirents types de donnes provenant de ce milieu, de les traitere eou de les acheminer en plus de pouvoir communiquer entre eux grce ` un dispositif a aradio dont ils sont quips. Lorsquils sont utiliss en quantit et de faon colla-ee ee cborative, ils constituent un rseau de capteurs et sont ` lorigine dapplicationse apousses dans le domaine militaire et dans celui de la mdecine entre autres. ee Dans la plupart des cas, il sagit dapplications ` temps rel dans des mi- aelieux o` lacc`s est dicile et quelquefois impossible a lhomme. En eet, les cap- ue`teurs peuvent tre dploys au fond de locan, dans un champ de bataille, etc.e ee eCeci fait quils sont sans surveillance et quils font dicilement lobjet de main-tenance. Ils sont aussi utiliss en grand nombre et doivent, suivant leur usage,erespecter des spcications lies a la taille et a la consommation dnergie. En ef-e e `` efet, contrairement aux nuds capteurs, dautres quipements lectroniques commee eles tlphones portables, les PDAs, ou autres appareils lectroniques sont la plu- ee epart du temps sous la main de lhomme qui se charge de leur maintenance et deleur entretien. La batterie dun tlphone portable, par exemple, est facilementeerechargeable apr`s puisement. Les nuds capteurs aussi disposent dune sourcee ednergie assez limite mais ne bncient pas cependant dune possibilit de re-ee e e echarge manuelle. Ces facteurs reprsentent autant de contraintes auxquelles fontePrsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 13. 3face ces quipements rendant ainsi la plupart des algorithmes et protocoles, conus ecpour les rseaux sans l, inadapt aux rseaux de capteurs. De nouvelles techniqueseeesont alors mises sur point an de tenir compte des exigences des rseaux de cap-eteurs sans l lies a leur cot, a lanatomie des nuds cest-`-dire de type matriel,e `u `a emais aussi et surtout lies a leur dure de vie. Limpossibilit dune recharge ma-e ` eenuelle et le besoin dassurer une longue dure de fonctionnement aux applicationsequi en dcoulent ont fait que plusieurs chercheurs se concentrent actuellement surela conception dalgorithmes qui tiendront en compte le facteur nergie pour les erseaux de capteurs en optimisant leur dure de vie. ee Ce mmoire de master vient sinscrire dans une logique dtude de quelques eetechniques doptimisation de la dure de vie des rseaux de capteurs sans l. Il fait eeressortir des procds utiliss pour rduire la consommation dnergie des nudse eeeecapteurs tels que la succession alternative des nuds capteurs dans lexcution desetches, lorganisation du rseau en clusters, la division des nuds en hirarchie a e eentres autres mthodes de la littrature. Pour cela, nous avons, apr`s ce premier e eechapitre introductif, parl des gnralits sur les rseaux de capteurs sans l auee e e edeuxi`me chapitre. Cela pour mieux les cerner. Ensuite, au troisi`me chapitre, e enous nous sommes concentrs sur ltude de quelques techniques doptimisation de eeleur dure de vie que nous avons spares en techniques centralises et techniquese e eedistribues. Finalement, cest au quatri`me et dernier chapitre que nous avons faite eune conclusion de ce travail et ouvert quelques perspectives.Prsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 14. CHAPITRE 2Gnralits sur les rseaux de capteurs sans l e e e e 4 15. 5Sommaire 2.1Anatomie dun noeud capteur . . . . . . . . . . . . . . . 6 2.2Architecture dun rseau de capteurs sans l . . . . . . e8 2.3Architecture en couches des rseaux de capteurs sans el . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.4Les direntes applications des rseaux de capteurs e esans l . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.4.1 Applications mdicales . . . . . . . . . . . . . . . . . . . e12 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.5Les contraintes de conception et dexploitation . . . . 18 2.5.1 La tolrance aux fautes . . . . . . . . . . . . . . . . . . e18 2.5.2 Le passage ` lchelle . . . . . . . . . . . . . . . . . . . .a e 19 2.5.3 Laspect cot . . . . . . . . . . . . . . . . . . . . . . . .u 20 2.5.4 Les contraintes matrielles . . . . . . . . . . . . . . . . .e 20 2.5.5 Lenvironnement et la topologie du rseau . . . . . . . . e22 2.5.6 La consommation dnergie . . . . . . . . . . . . . . . . e23Prsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 16. 2.1. Anatomie dun noeud capteur6a micro-lectronique a connu au cours de cette dcennie une avance fulgurantee eeL causant ainsi la miniaturisation progressive des quipements. Les rseaux de e ecapteurs sans l sont une consquence de cet essor. Ils sont de plus en plus amliorsee eet sont dots dune puissance de calcul sans cesse grandissante. Leur organisation een rseau rv`le toute leur utilit non seulement dans le milieu industriel, mili-ee eetaire, environnemental mais aussi dans la vie de chaque jour de lhomme. Ils sontdploys en grand nombre dans dirents milieux pour y eectuer diverses tches. eeeaCependant, ces capteurs de par leur taille, leur cot ou de par lenvironnement udans lequel ils sont dploys peuvent prsenter des dicults dans leur conceptioneeeeet leur exploitation. Nous allons, tout au long de ce chapitre, montrer comment est constitue la eplus petite entit dun rseau de capteurs sans l a savoir le nud capteur. Pour e e `cela nous allons discuter de son anatomie. Puis, nous passerons a larchitecture`dun rseau de capteurs sans l, cest-`-dire le rseau constitu de ces petiteseae eentits. Ensuite, la section suivante exposera les direntes applications qui sont eefaites des rseaux de capteurs sans l dans les domaines mdicaux, militaires,e eenvironnementaux, domestiques et commerciaux. Enn, nous clorons ce chapitreen faisant ressortir les contraintes qui peuvent se prsenter ` la conception et ae a`lexploitation dun rseau de capteurs. e2.1Anatomie dun noeud capteur Un nud capteur ou mote en anglais est constitu dlments de telle sortee eequil peut a lui seul assurer les tches dacquisition et de traitement de linforma- ` aPrsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 17. 2.1. Anatomie dun noeud capteur 7tion. Il peut aussi communiquer avec les autres nuds. Ceci fait que le capteur estconstitu de quatre composants de base :e une unit dacquisition gnralement subdivise en deux sous units que ee e e e sont les capteurs et les convertisseurs analogique-numrique(ADCs)[LEH09]. e Les capteurs sont chargs de dtecter les caractristiques et les variationsee e du milieu ambiant. Ils sont utiliss pour une grande varit de phnom`nes eee e e physiques (acclration, concentration chimique...). Ils rpondent a une va- eee` riation des conditions denvironnement par une variation de caractristiques e lectriques. Ce sont ces variations dordre lectriques qui sont par la suite e e converties par les convertisseurs analogique-numrique pour pouvoir tre e e traites par lunit de traitement[KAC09].e e une unit de traitement qui est compose dun processeur et dun syst`me e ee dexploitation spcique. Elle acquiert les informations en provenance dee lunit dacquisition et les envoie a lunit de transmission. Pour cela, elle est e ` e constitue de deux interfaces : une avec le module dacquisition et une autre e avec le module de transmission. une unit de transmission de donnes ou encore module de communi- ee cation qui est responsable de toutes les missions et rceptions de donnese ee a travers un dispositif radio. Cest un composant classique utilis dans les ` e rseaux sans l.e et une source dnergie constituant une composante cruciale dun noeud ePrsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 18. 2.2. Architecture dun rseau de capteurs sans le8capteur. Son rle est de stocker et de fournir lnergie ncessaire au fonction-oeenement du noeud. Cependant il peut aussi jouer celui consistant a rassembler`lnergie du milieu externe pour pouvoir lutiliser. Il sagit souvent dune pileeAA normale denviron 2.2 - 2.5 Ah fonctionnant a 1.5 V. ` En plus de ces composants de base, il existe des noeuds capteurs dots dautres eunits additionnelles comme un syst`me de localisation (GPS), une unit de mo-eeebilit, etc. Il est prsent a lannexe A sous forme de tableaux quelques exemples eee`de capteurs. Figure 2.1 Anatomie dun noeud capteur2.2Architecture dun rseau de capteurs sans le Dans la plupart des cas, les nuds capteur sont utiliss en grand nombre et edploys de faon tr`s dense dans un milieu. Ils sont capables de communiquer ee c eentre eux et sont donc utiliss comme un rseau dquipements sans l. Indivi- ee eduellement, ils sont capables de collecter des donnes de leur environnement, de eles traiter localement mais ils peuvent aussi communiquer entre eux pour achemi-Prsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 19. 2.2. Architecture dun rseau de capteurs sans le9ner linformation vers un poste central en utilisant leur dispositif radio. Chaquenud capteur du rseau est capable de transmission et de rception de donnes. ee eEn gnral, il existe dans le rseau un ou plusieurs nuds spciaux appels nuds-e ee e epuits ou sink. Ces derniers poss`dent plus de ressources et de puissance que leseautres types de nuds du rseau et permettent, en plus de la rcupration dese e edonnes, linterconnexion du rseau de capteurs avec dautres types de rseauxe e e(Internet, satellite. . .). Dans un rseau de capteurs, les nuds peuvent tre xes eeou dots de syst`me de mobilit pour pouvoir se dplacer. Lenvironnement danse e eelequel sont dploys les nuds est appel la zone dintrt. ee eee Dans un rseau de capteurs sans l, des points dagrgation peuvent tre in-ee etroduits. Cela a pour but de rsoudre le probl`me de la consommation dnergiee ee[MAK08]. En eet, la communication entre les nuds consomme beaucoup dnergie. eAinsi ceci a pour but de rduire cette communication entre les nuds en pri-evilgiant celle entre les points dagrgation. Pour minimiser la consommation eednergie, un type de regroupement appel clustering peut aussi tre appliqu.e e e eUn chef du cluster joue le rle dun point dagrgation. Les nuds sont organisso eeen groupes, chaque groupe a un chef de cluster. La communication au sein dungroupe doit passer a travers le chef, qui ensuite la transmet ` un autre chef du `acluster voisin jusqu` ce quil atteigne sa destination, la station de base. aPrsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 20. 2.3. Architecture en couches des rseaux de capteurs sans le 10 Figure 2.2 Architecture dun rseau de capteurs sans l e2.3 Architecture en couches des rseaux de cap- eteurs sans l Du fait du grand nombre de fonctionnalits implmentes dans les rseaux de eee ecapteurs, larchitecture de ces derniers est particuli`rement complexe. Larchitec-eture en couches dans les RdCSF comme dans les rseaux en gnral, veut rduire ee e ecette complexit en dcomposant les processus qui y sont mis a luvre. Un tel e e `dcoupage permet au rseau de traiter en parall`le les fonctions attribues aux e e eedirentes couches. e Cette architecture est reprsente sur la gure 2.3 et tient compte des contrainteseelies au routage et a la consommation dnergie, int`gre la gestion des donnese ` e e egrce aux protocoles de routage de donnes, permet la communication a moindreae`nergie grce aux dispositifs sans l, anime la collaboration des nuds capteurs.e aLe dcoupage consiste en une couche physique, une couche liaison de donnes, unee ecouche rseau, une couche transport, une couche application ; un plan de gestionePrsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 21. 2.3. Architecture en couches des rseaux de capteurs sans le11 Figure 2.3 Architecture en couches des rseaux de capteurs sans l ede lnergie, un plan de gestion de mobilit et un plan de gestion des tches. e ea En fonction de lusage qui est fait du rseau de capteurs, direntes types dou- e etils exploitant la couche application peuvent tre dvelopps. La couche transporte eepermettra de maintenir le ux de donnes. La couche rseau pourra soccuper du e eroutage des donnes qui lui seront prsentes par la couche transport. Puisque,eeeles nuds capteurs sont aussi dploys en grand nombre, la couche liaison de eedonnes se chargera dviter les collisions qui peuvent tre dues aux communica-e e etions simultanes. La couche physique, quant a elle, assurera les besoins non moinse`importantes de modulation, de rception et dmission. En plus de ces couches, les e eplans de gestion de lnergie, de la mobilit et des tches g`rent la consommatione e aednergie, les dplacements et la distribution des tches entre les nuds capteurs.e e aIls aident les nuds capteurs ` coordonner les taches de dtection et de limiter laa econsommation dnergie. ePrsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 22. 2.4. Les direntes applications des rseaux de capteurs sans le e122.4Les direntes applications des rseaux dee e capteurs sans l Un rseau de capteurs peut tre constitu de direntes sortes de nuds cap- eee eteurs capables de dtecter dirents phnom`nes physiques tels que les phnom`nes eee e e esismiques, magntiques, thermiques, visuels, acoustiques entre autres. Ils sont de ece fait utiliss pour contrler une large varit de conditions du milieu ambianteoeecomme [ASSC02] la temprature, lhumidit, les dplacements des vhicules, lae e eeluminosit, la pression, les caractristiques du sol, le niveau de bruit, la prsence e e eou labsence de quelques objets, la vitesse, la direction et la taille dun objet. Les capacits de dtection et de communication sans-l de ces nuds fait envi-eesager toute une nouvelle vague dapplications dans des domaines dirents. Dans ela suite, nous allons dtailler lusage qui est fait des capteurs dans les milieux de ela sant, les milieux militaires, environnementaux, domestiques et dans quelques emilieux commerciaux.2.4.1 Applications mdicalese Les applications des rseaux de capteurs sans ls dans le domaine mdical eepermettent dans les hpitaux de raliser la surveillance des patients, de faire la o ediagnostique, dassurer normalement ladministration de mdicaments. Elles per- emettent de surveiller dans dautres milieux les dplacements et transformations edes insectes et autre animaux. Les rseaux de capteurs sans l y sont aussi uti-eliss pour surveiller les patients et les mdecins au sein de lhpital mais galement e e o epour faciliter ltude de la physiologie humaine. En eet, les donnes physiologiques e ePrsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 23. 2.4. Les direntes applications des rseaux de capteurs sans le e13collectes par un capteur peuvent tre conserves pendant une longue priode et ee e eutilises par la suite pour une consultation mdicale [O+ 98].e e Les capteurs peuvent aussi surveiller ltat de sant des personnes ages[C+ 94, e e eC+ 95]. Ils ont non seulement lavantage de permettre au mdecin de pouvoiredtecter assez tt les symptmes[N+ 98], mais aussi dempcher lalitement du pa- eo oetient, qui pourra vaquer ` ses occupations, lui procurant ainsi une meilleure qua- alit de vie pendant tout le traitement compare a celle quil aurait eue en milieu e e `hospitalier[BSIP00]. La faisabilit dun tel syst`me mdical est tudie en Grenobleeeeee(France) a travers le projet Health Smart Home [NHR+ 00]. ` Les capteurs peuvent galement tre implants dans le corps humain poure e econtrler les probl`mes mdicaux comme le cancer et pour aider les patients a o e e`maintenir leur sant. En implantant sous la peau des mini capteurs vido, on peut eerecevoir des images en temps rel dune partie du corps sans aucune chirurgie etependant environ 24h. On peut ainsi surveiller la progression dune maladie ou lareconstruction dun muscle. Un projet actuel consiste a crer une rtine articielle` eecompose de cent micro-capteurs pour corriger la vue [MAK08].e2.4.2Applications militaires La recherche militaire est lun des principaux domaines utilisant la technologiedes rseaux de capteurs sans l. En eet, une grande partie de la croissance ra- epide dans la recherche et le dveloppement des rseaux de capteurs sans l a te eeegarantie par des programmes nancs par lAgence amricaine pour les Projets e ePrsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 24. 2.4. Les direntes applications des rseaux de capteurs sans le e14de Recherche Avance de Dfense (DARPA), notamment grce ` un programmeee a aconnu sous le nom de SensIT [KAC09]. Les rseaux de capteurs peuvent tre utiliss pour la surveillance des champs deeeebataille et la traque de cibles. Ils fournissent ainsi des informations sur le nombre,le mouvement, lidentit des soldats, etc. Ils sont aussi tr`s utiles dans la gestion eedes munitions et des quipements des corps militaires[ASSC02]. En eet ltat des e emunitions des troupes peut tre constamment surveill grce a des capteurs qui ee a `sont relis aux vhicules ou aux armes et qui renvoient de temps en temps ltat e eede ces derniers. Un projet de lUniversit de Californie Berkeley[BC] consistait a suivre la e `trace des vhicules militaires passant pr`s de capteurs parsems grce ` un drone e eea aUnmanned Air Vehicle (UAV). La gure 2.4 reprsentent quelques images de elopration qui a dur trois jours.eeFigure 2.4 Tracking vehicles with a UAV-delivered sensor networkPrsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 25. 2.4. Les direntes applications des rseaux de capteurs sans le e152.4.3 Applications environnementales Dans le milieu environnemental aussi, les rseaux de capteurs gardent touteeleur importance. Les capteurs sont dploys en grand nombre et dans la pluparteedu temps dans des milieux hostiles a lhomme. Ceci permet leur utilisation dans `la lutte contre les feux de brousse. Ils peuvent dtecter lorigine du feu vitanteeque celui-ci devienne incontrlable. Dans le milieu de lagriculture, les rseaux de o ecapteurs orent aussi la possibilit de pouvoir surveiller les cultures. Ils fournissent een temps rel des informations relatives au volume de pesticides dans les sols, a lae `vitesse de lrosion et au niveau de pollution de lair. Direntes sciences dtude de eeelenvironnement font recours aux technologies des capteurs. Il peut sagir dtudier eles mouvements des oiseaux, des petits animaux et des insectes ou de surveillerltat de la rcolte et du btail, de contrler lirrigation des terres ou mme de fairee e eoedes tudes a une plus grande chelle.e` e En Espagne, une entreprise qui commercialise des projets de protection de len-vironnement a dvelopp un syst`me de dtection de feux de brousse en utilisant eee edes rseaux de capteurs[Dim]. Ce syst`me a t ralis sur une supercie de 210 e e ee e ehectares dans le nord du pays et a eu pour but de fournir ` direntes organisationsaeune infrastructure de surveillance de lenvironnement et la possibilit de recevoiredes alarmes davertissement. Les gures 2.5 et 2.6 servent a illustrer ce syst`me. `e2.4.4 Applications domestiques Avec la miniaturisation progressive, les capteurs sont de plus en plus intgrs e eaux quipements de la tous les jours. Les tlphones portables, les ordinateurs, leseeePrsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 26. 2.4. Les direntes applications des rseaux de capteurs sans le e 16 Figure 2.5 SIstema de Seguimiento y VIgilancia AmbientalFigure 2.6 Interfaces de contrle du syst`meoePrsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 27. 2.4. Les direntes applications des rseaux de capteurs sans le e 17fours a micro-ondes et mme les cls de voitures sont quips de capteurs. Dans` e e eela maison, laspirateur, le rfrigrateur, la tlvision int`grent des capteurs. La e e ee edomotique fait usage des rseaux de capteurs pour fournir dans les maisons, lesehtels ou les lieux publics des fonctions de confort (gestion dnergie, optimisation oede lclairage et du chauage), de scurit (alarme, vidosurveillance, gardiennage) ee e eet de communication (commandes a distance, signaux visuels ou sonores). ` Quelques travaux [BBC10] ont consist ` lutilisation des rseaux de capteurs ea esans l pour rduire la consommation dnergie des appareils lectroniques de laee emaison. Les rseaux de capteurs sans l constituent aussi une brique de lInternet deseobjets (IoT pour Internet of Things). Ce dernier reprsente lextension dInternet eaux objets de la vie de tous les jours.2.4.5 Autres applications commerciales Quelques une des applications commerciales concernent la gestion des matriaux, ede linventaire, la surveillance de la qualit des produits, la construction de bureaux eintelligents, le contrle environnemental (climatisation, sonorisation, etc.) dans lesoentreprises, les jeux et les muses interactifs, lautomatisation et le contrle deseoprocessus dans lindustrie, etc.[ASSC02] Un syst`me de rseau de capteurs sans l peut tre install pour contrler le uxe ee e odair et de temprature dans direntes parties dune pi`ce. On estime quune tellee e etechnologie peut rduire lnergie de telle faon a faire des conomies a hauteur deeec ` e `Prsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 28. 2.5. Les contraintes de conception et dexploitation 1855 milliards de dollars par an et une rduction de 35 millions de tonnes de carbone emises [RAJ+ 00]. Dans la dtection de voiture voles aussi, les capteurs sont duneeeegrande utilit car permettant en temps rel de renvoyer la position gographique eeede la voiture a un nud central.`2.5Les contraintes de conception et dexploita- tion La mise en place et lexploitation dun rseau de capteurs nest pas sans dif-ecult. Il existe des contraintes lies a la conception de celui ci qui peuvent tre ee ` edordre multiple. La conception de protocoles et dalgorithmes doivent d`s lors enetenir compte pour tre le plus optimal possible. Ces contraintes vont aussi inuen-ecer lexploitation du rseau de capteurs sans l. Nous dtaillerons ici quelques une eede ces contraintes, cependant cette liste nest pas exhaustive.2.5.1 La tolrance aux fautese La tolrance aux fautes est laptitude dun syst`me informatique ` accomplir sa e eafonction malgr la prsence ou loccurrence de fautes, quil sagisse de dgradationseeephysiques du matriel, de dfauts logiciels, dattaques malveillantes, derreurs din-eeteraction homme-machine [A+ 06]. Les nuds peuvent tre sujets a des pannes dues e `a leur fabrication (ce sont des produits de srie bon march, il peut donc y avoir des`e ecapteurs dfectueux) ou plus frquemment a un manque dnergie. Les interactionsee ` eexternes (chocs, interfrences) peuvent aussi tre la cause des dysfonctionnements. eeAn que les pannes naectent pas la tche premi`re du rseau, il faut valuera e eela capacit du rseau ` fonctionner sans interruption [KAC09]. Lexemple donne e aePrsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 29. 2.5. Les contraintes de conception et dexploitation 19dans [KPSV] montre un cas de tolrance aux fautes dans un rseau de capteurseesans l.2.5.2Le passage ` lchellea e Dans un rseau de capteurs sans l, le nombre de nuds dploys dans ltudeeee edun phnom`ne est gnralement de lordre de centaines voire de milliers. En e ee eexemple, la plateforme Senslab [sen] met a disposition 1024 nuds-capteurs rpartis `esur quatre sites en France ` savoir Grenoble, Lilles, Rennes et Strasbourg (cf. gure a2.7). Figure 2.7 La plateforme Senslab De ce fait, les algorithmes et protocoles conus pour les rseaux de capteursc esans l doivent tre a mme de sadapter a ce nombre extensible de nuds. Lese` e `applications des rdcsf doivent mme tre capables de lutiliser a leur avantage.e e `Prsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 30. 2.5. Les contraintes de conception et dexploitation202.5.3 Laspect co t u Par dnition, un rseau de capteurs sans l consiste en un grand ensemblee ede nuds capteurs. Suivant lusage qui en est fait, un rseau de capteurs peutecomporter jusqu` des milliers de nuds. Il sen suit d`s lors que le cot dunaeunud capteur va fortement inuencer celui de tout le rseau. Clairement, le cote ude chaque nud capteur doit tre faible pour que celui du rseau soit acceptable.eeIl est a noter aussi quen fonction de lapplication, le nud capteur peut tre ` edop grce ` des quipements supplmentaires comme un syst`me de localisation, e a a ee eun composant de mobilit pour quil puisse tre capable de dplacements ou un e eegnrateur dnergie. Toutes ces units additionnelles ont un cot supplmentaire. e e e eu eAinsi elles augmentent les fonctionnalits du rseau de capteurs mais galement leeeecot de celui-ci [ASSC02].u2.5.4 Les contraintes matrielles e Un nud capteur est gnralement compos de quatre composants basiques :e e eune unit de dtection, une unit de traitement, un transceiver et une sourcee e ednergie. Le plus souvent et en fonction de lapplication, des units additionnellese epeuvent tre incorpores au capteur. Il sagit dun syst`me de localisation, duneeegnrateur dnergie et dune unit de mobilit pour la plupart du temps. D`s lors, e e ee eela dicult est que tous ces composants doivent tre ajusts a lintrieur dun dis-e e e ` epositif de la taille dune boite dallumette. Pour certains usages, le nud capteurdoit avoir une taille plus petit quun centim`tre cube et peser assez lger pour e epouvoir tre suspendu. Compte tenu des fonctionnalits toujours extensibles, cese econtraintes de taille et de poids viennent sajouter aux dicults lies a la concep-e e `Prsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 31. 2.5. Les contraintes de conception et dexploitation 21tion dun rseau de capteurs sans l [AV10]. eLes contraintes dues a la taille des nuds rendent la capacit de stockage ` ednergie assez faible. Par exemple la quantit totale dnergie stocke dans une eeenud smartdust 1 est de lordre de 1 J [PK00]. Pour les syst`mes WINS [VWPK00],ela moyenne dnergie ne doit pas dpasser 30 A pour esprer une longue dure ee eede vie du syst`me.eCependant, bien que les avances technologiques permettent de plus en plus eune grande puissance de calcul dans de petits quipements a des prix drisoires,e ` ela puissance de calcul des nuds capteurs actuels est signicativement plus petiteque celle de plusieurs autres syst`mes embarqus ` cause de la taille et du prix.e e aPar exemple, les premiers dispositifs tels que le nud smartdust avaient un mi-crocontrleur Atmel AVR 8535 de 4 MHz, une mmoire ash de 8 KB, une RAMo ede 512 octets et une mmoire morte EEPROM de 512 octets aussi. Ces capacitse eont t accrues avec les nuds SunSPOT et Imote2. SunSPOT est quip duneeeeprocesseur 32 bit ARM920T de 180 MHz, dune RAM de 512 KB et dune mmoireeash de 4 MB. Imote2 dispose quant a lui dun microcontrleur Marvell PXA271 `oXScale de 416 MHz, une SRAM de 256 KB, dune mmoire ash de 32 MB etedune SDRAM de 32 MB. Il apparait clairement alors que les capacits des nudsecapteurs vont augmenter, toutefois, ces valeurs fournies ne reprsentent rien com-epares aux capacits dautres types de syst`mes embarqus comme les PDA ou eee e 1. Smartdust est un syst`me de nombreux petits appareils micro-lectromcaniques commeeeeles capteurs, les robots ou dautres quipements, qui peuvent par exemple dtecter la lumi`re, laeeetemprature, la vibration, le magntisme ou des produits chimiques ; qui gnralement commu-eee eniquent sans l, et qui sont rpartis sur une certaine espace pour eectuer des tches de dtection.ea eCest un concept introduit par la DARPA.Prsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 32. 2.5. Les contraintes de conception et dexploitation22les smartphones [AV10]. Par consquent, les applications des rseaux de capteurse eainsi que les protocoles conus doivent tenir compte de ces contraintes matrielles.ce2.5.5 Lenvironnement et la topologie du rseaue Les nuds capteurs sont dploys au sein du milieu ` observer ou assez procheeeade celui-ci. Ce milieu est la plupart du temps dicile dacc`s a lhomme. Ceci faite `que les capteurs sont habituellement dans des rgions loignes et sans surveillance. ee eIls peuvent se trouver [ASSC02] : au fond de locan,e a lintrieur dune tornade, `e dans un champ contamin biologiquement ou chimiquement, e dans un champ de bataille au-del` des lignes ennemies, a attach a des animaux, e` etc.Cette liste nous donne une ide de lenvironnement dans lequel les nuds capteurs esont embarqus.e La topologie du rseau est aussi un facteur ` prendre en compte dans la concep-eation du rseau de capteurs sans l. En eet, le grand nombre de capteurs qui sont edans des milieux inaccessibles et donc sans surveillance ni maintenance est d`s lors esujet ` de frquentes dfaillances. Cela entraine une modication priodique de laae e etopologie du rseau de capteurs.ePrsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 33. 2.5. Les contraintes de conception et dexploitation232.5.6 La consommation dnergiee Dans les rseaux de capteurs, lnergie est tr`s importante car elle est rare. e e eLe nud capteur tant un quipement micro-lectronique est muni dune sourceeeednergie limite. Or contrairement aux ordinateurs portables et aux quipementsee ede poche comme les tlphones portables qui bncient dune constante attentionee e eet maintenance, les capteurs par leur grand nombre, mais aussi par le fait quilssont la plupart du temps parsems dans des milieux hostiles ` lhomme, ne peuvent eapas faire lobjet dune recharge manuelle. Bien que certaines techniques de collectednergie dans lenvironnement existent, la consommation dnergie demeure luneeedes contraintes majeures dans lexploitation des rseaux de capteurs sans l. Eneeet ce challenge est au cur de toutes les autres contraintes et inuence la concep-tion de tout le syst`me [R+ 06].e Dans un rseau multi saut, le nud joue le double rle de source de donnese oeet de routeur. Le dysfonctionnement de quelques nuds pourrait causer dim-portantes modications dans la topologie et pourrait ncessiter un autre routageedes paquets en plus de la rorganisation du rseau. De ce fait, la conservation e eet la gestion de lnergie prennent une importance supplmentaire. Cest pour eeces raisons que plusieurs chercheurs se concentrent actuellement sur la conceptiondalgorithmes et de protocoles qui tiendront en compte le facteur nergie pour leserseaux de capteurs. e Dans dautres types de rseaux sans l, la consommation dnergie est une e econtrainte importante mais pas la contrainte majeure, simplement par le fait queles sources dnergie peuvent tre remplaces lorsquelles sont puises [ASSC02].e e e eePrsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 34. 2.5. Les contraintes de conception et dexploitation24Dans ces rseaux, laccent est plus port sur la qualit de service (QoS). Cependante eedans les rseaux de capteurs, lnergie est une importante mesure de performance.e eAinsi, les protocoles peuvent tre conus en compromettant dautres mesures dee cperformance telles que le dlai ou la bande passante. e La tche principale dun nud capteur est de dtecter des phnom`nes phy- a e e esiques, de faire un traitement local et de transmettre de linformation. Toutes cestrois requi`rent de lnergie, faisant que la consommation dnergie dun nud cap- eeeteur peut tre subdivise en celle ncessaire pour la dtection, une autre ncessaireeeeeepour le traitement local et une derni`re ncessaire pour la communication. De eetoutes ces tches, cest dans lexcution de cette derni`re que le nud capteura e econsomme le plus dnergie. Ceci concerne aussi bien la rception que la transmis- e esion de donnes.ePrsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 35. CHAPITRE3Techniques doptimisation de la dure de vie e25 36. 26Sommaire 3.1La dure de vie dun rseau de capteurs sans l . . . . 28e e 3.2Techniques centralises . . . . . . . . . . . . . . . . . . . 30e 3.2.1 Lalgorithme 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.3Techniques distribues . . . . . . . . . . . . . . . . . . . 33 e 3.3.1 Low-Energy Adaptive Clustering Hierarchy : LEACH . 33 3.3.2 Lalgorithme ASCENT : Adaptive Self-Conguring Sen- sor Networks Topologies . . . . . . . . . . . . . . . . . .40 3.3.3 Un protocole robuste de conservation dnergie pour lese rseaux de capteurs ` longue dure de vie : PEAS . . .ea e44Prsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 37. 27 l est a noter que les rseaux de capteurs sans l ont beaucoup de similitudes `eI avec les rseaux ad-hoc sans l. En eet ces deux types de rseaux sont tous dese erseaux sans infrastructure, ont une architecture dcentralise, utilisent les ondes e e eradio pour communiquer et sont autonomes. De ce fait, la conception de proto-coles et dalgorithmes pour les rseaux de capteurs peuvent prendre en compte les eproprits des rseaux ad-hoc.eee Cependant, les rseaux de capteurs prsentent aussi beaucoup de fonctionna- eelits qui leur sont spciques et donc non prsentes dans les rseaux ad-hoc. Ce eee esont ces fonctionnalits qui am`nent de nouveaux challenges et qui doivent treee eprises en compte dans la conception des protocoles et autres techniques pour lesrseaux de capteurs sans l. Parmi ces dirences [MAK08] : ee la densit de nuds dploys est beaucoup plus importante dans les rseauxe ee e de capteurs sans l que dans les rseaux ad-hoc, e les nuds capteurs ont des capacits limites en nergie et en mmoire, e eee la topologie dans les rseaux de capteurs est souvent dynamique,e la communication entre les nuds dun rseau de capteurs se fait par diusione et non point par point, les capteurs peuvent ne pas avoir un identiant global vu le grand nombre de nuds qui existent gnralement.e e Dans ce document, nous nous intressons plus a la contrainte impose par lae `efaible dure de vie des rseaux de capteurs. De ce fait, nous exposons dans ceeechapitre, direntes techniques non-exhaustives doptimisation de cette dure de e ePrsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 38. 3.1. La dure de vie dun rseau de capteurs sans l e e 28vie. Nous ressortirons dabord la notion de dure de vie dun rseau de capteurs e esans l a travers les direntes dnitions quelle revt en fonction de lobjectif vis`eee edans lexploitation du rseau. Puis, nous aborderons les techniques centralises `ee atravers lalgorithme de Berman et al., les travaux de Zhang et Hou et ceux deCardei et al. Apr`s cela, nous passerons aux techniques distribues en prsentant eeedirents algorithmes et protocoles comme LEACH, ASCENT, PEAS de Fan Ye eet Gary Zhong, PEAS-Weibull et PECAS.3.1La dure de vie dun rseau de capteurs sans e e l La dure de vie est lun des probl`mes les plus srieux dans ltude des rseaux e ee eede capteurs sans l. Comme nous lavons dit dans la sous-section 2.5.6, les nudscapteurs sont des quipements sans contrle avec une dure de vie limite. Lee o eerseau peut rapidement cesser de fonctionner normalement a cause dune dviation e `eou dun manque de planning et puisquun rseau de capteurs est gnralement uti- ee elis pour une longue dure sans possibilit de recharge, prolonger sa dure de vie ee eedevient primordial. Selon lobjectif ou les hypoth`ses pris en compte, il ya plusieurs dnitions de eela dure de vie du rseau. Elle est souvent considre comme la dure qui scoulee e ee eedepuis la mise en place du rseau jusqu` lpuisement de la source dnergie dune a e epremier nud. Bien que la redondance des nuds peut, dans ce cas, permettre aurseau de continuer a fonctionner. Une autre dnition est la dure qui scoule e` eeejusquau moment o` le nombre de capteurs puiss atteint un seuil dtermin. u eeeePrsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 39. 3.1. La dure de vie dun rseau de capteurs sans l e e 29Une dnition plus raliste est de considrer la dure de vie du rseau comme la eeee edure qui scoule depuis la mise en place du rseau jusquau moment o` celui-ci eeeudevient incapable daccomplir les tches qui lui sont assignes. La couverture est aelactivit premi`re dun rseau de capteurs sans l. Elle est dailleurs gnralement ee e e econsidre comme la QoS du rseau. Elle reprsente de ce fait un bon objectif quieee epeut tre pris en compte dans ltude de loptimisation de la dure de vie du rseau eee ede capteurs. Le nud capteur est compos de quatre principales units (voir section 2.1). e eCest la source dnergie qui fournit de lnergie aux trois autres composants eteetoute activit de ces trois derniers que ce soit la dtection, le traitement, la trans- e emission et la rception de donnes consomme de lnergie [QUN07]. Il est connu e e eque les oprations de communication des nuds (transmission et rception dee edonnes) sont les plus consommatrices dnergie. De ce fait, rduire la consomma-e e etion dnergie de leur dispositif radio est une technique de conservation dnergie eeet doptimisation de la dure de vie du rseau. Des techniques de planication e ede lactivit des nuds (actif, en veille, inactif, . . .) sont galement utilises poure e eaugmenter la longvit du rseau de capteurs. Elles sont appeles techniques de e e eeduty cycling . Aussi, dans les rseaux de capteurs organiss en clusters, dese echefs de clusters sont slectionns pour accomplir des tches (comme la mobiliteeaedans le but dquilibrer lnergie) visant ` allonger la dure de vie du rseau.ee ae ePrsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 40. 3.2. Techniques centralises e 303.2Techniques centralises e3.2.1 Lalgorithme de Berman et al. Berman et al. ont, dans leur document [BCSZ05] mis laccent sur la rduction ede la consommation dnergie due ` la dtection (sensing) en utilisant des tech- e a eniques intelligentes dordonnancement. Ils ont dni la dure de vie comme tantee ele temps durant lequel la zone dintrt est partiellement ou totalement couverte.eeIls ont propos un algorithme pour dterminer un planning de la surveillance quie eallonge la dure de vie du rseau lorsquil faut couvrir une q portion de la zonee edintrt. Pour cela, ils ont mis en place une structure de donnes pour reprsenter ee eela zone dintrt avec n2 points, n tant le nombre de capteurs garantissant une ee ecouverture totale. Leur algorithme prend en compte la surveillance partielle et lecout de la communication lorsque la porte de la communication est au moins deuxefois plus large que celle de la couverture. Il est suppos dans le document que des capteurs sont disperss dans la rgione e eR a couvrir et que chaque capteur pi a sa propre rgion a couvrir Ri . Cela veut` e `dire que pi peut collecter les donnes dans Ri sans laide daucun autre capteur. eIl est aussi considr que chaque capteur pi a une quantit dnergie initiale bi ee e equi peut tre mesure par le temps durant lequel pi peut collecter des informa- e etions provenant de Ri . Le nombre de nuds dploys est largement suprieur auee enombre de nuds ncessaire pour couvrir la zone. Ainsi il est possible de rendre einactifs certains nuds pour sauvegarder leur nergie et prolonger la dure de vieeedu rseau. Les capteurs sont capables dalterner leur tat plusieurs fois cependante ela zone dintrt R doit tre ` tout moment soit compl`tement soit partiellement eeea ePrsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 41. 3.2. Techniques centralises e 31couverte par les nuds actifs.Berman et al ont donn une dnition formelle du probl`me de la rduction ee eede la consommation dnergie. Ils ont considr comme tant le planning de la eeeecouverture lensemble de couples (C1 , t1 ), . . . , (Ck , tk ) avec Ci tant un ensembleede capteurs couvrant la zone dintrt R et ti le temps durant lequel Ci est ac-eetif. Ainsi, considrant une zone dintrt R, un ensemble de capteurs p1 , . . . , pn ,e eeune rgion de couverture Ri et une nergie initiale bi pour chacun dentre eux, le e eprobl`me de la dure de vie du rseau se rsume a trouver un planning de couver- ee e e `ture (C1 , t1 ), . . . , (Ck , tk ) avec la plus grande dure t1 + . . . + tk , de telle faon que e cpour chaque capteur pi la priode totale dactivit ne dpasse pas bi . ee e3.2.2Les travaux de Zhang et HouHonghai Zhang et Jennifer Hou ont tudi le probl`me de la prolongation de laee edure de vie dun rseau de capteurs sans l en considrant celle-ci comme tant e eeele temps durant lequel au moins une portion de la zone dintrt est couverte.eeIls ont appel cette dure de vie -lifetime. Ils ont propos un algorithme qui fait ee eune planication de lactivit des nuds pour allonger le -lifetime dun rseau de e ecapteurs sans l. Zhang et Hou ont tudi le probl`me de la dure de vie du rseau ee ee edans le cas o`, a tout moment, seulement portion de la zone dintrt doit tre u ` eeecouverte (avec 0 < < 1). Lalgorithme dtermine un nombre maximum de sous eensembles disjoints de telle sorte que les nuds de chaque sous ensemble puissentcouvrir au moins une portion de la zone dintrt. Il planie les moments dac- eetivit et dinactivit des nuds. Pour cela, il choisit un sous ensemble de nuds e equi devra tre actif a chaque round.e`Prsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 42. 3.2. Techniques centralises e 32 Cette tude [ZH06] montre que pour accroitre la dure de vie du rseau, il est ee epossible soit de dployer un tr`s grand nombre de nuds comme dans le cas deseealgorithmes distribus ou de faire la concession de laisser une petite portion de laezone dintrt non couverte. Pour ce dernier cas, lalgorithme devra d`s le dbuteeeeindiquer une -couverture de la zone dintrt, o` reprsente le pourcentage de laee u ezone dintrt qui ne pourra pas tre couverte. Leur tude a aussi laiss apparaitreee e eeque choisir dans chaque round un nombre minimal de nuds qui vont assurerla couverture est moins optimale que de choisir un ensemble de nuds qui vontminimiser la consommation dnergie des nuds restants.e3.2.3Les travaux de Cardei et al. Cet algorithme de Mihaela Cardei, My T. Thai, Yingshu Li et Weili Wu[CTLW05] propose une mthode ecace pour optimiser la dure de vie du rseauee ede capteurs en organisant les nuds capteurs en un nombre maximal densemblesde couverture qui sont activs successivement. Quand un ensemble est actif, lesecapteurs constituant cet ensemble sont responsables de la couverture de tous lespoints de la zone dintrt et de la transmission des donnes collectes tandis que ee eeles autres nuds sont en tat de veille consommant moins dnergie. e e Lalgorithme utilise la technique du duty cycling . Il sagit dune des mthodeseutilises pour rduire la consommation dnergie des nuds capteurs et consiste ae ee`alterner leur fonctionnement en une mode active et une mode veille. Lalgorithmeaborde le probl`me de la maximisation de la dure de vie du rseau de capteurs en e e etudiant le probl`me de la couverture dun ensemble de points localiss du rseauee eePrsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 43. 3.3. Techniques distribuese 33et consid`re la dure de vie du rseau comme lintervalle de temps durant lequel e e echaque objectif (zone cible) du rseau est couvert par au moins un nud capteur. eIl se propose dallonger la dure de vie du rseau en divisant les nuds en un e enombre densembles non-disjoints de telle faon que chaque ensemble couvre ` luicaseul tous les objectifs du rseau. Ces ensembles sont activs ` tour de rle de telleee a osorte quen tout temps, un seul ensemble est actif a la fois. Cela permet non seule- `ment de couvrir toute la zone dintrt mais aussi dallonger la dure de vie du ee erseau, du moment o` les nuds sont programms pour alterner de ltat actif ` e ue ealtat veille, compar au cas o` tous les nuds du rseau sont tous continuellementee ueactifs.3.3 Techniques distribues e3.3.1 Low-Energy Adaptive Clustering Hierarchy : LEACHLes capteurs sont utiliss pour dtecter des phnom`nes du milieu physique,ee e edeectuer un traitement et de transmettre linformation qui en dcoule a un e`sink . Des protocoles de communication sont alors ncessaires pour le bon edroulement de cette opration. Cependant la plupart de ces protocoles soit ne e etiennent pas en compte des contraintes nergtiques des rseaux de capteur soit ils eeene sont pas optimaux. Ainsi, LEACH est un protocole qui vient palier ` quelques auns de leurs manquements et qui permet de rduire a hauteur de 8 fois la perte e`dnergie compar aux protocoles de routage conventionnels.e eLEACH est un protocole qui utilise des techniques de randomisation pourdistribuer la charge dnergie entre les nuds du rseau [HCB00]. LEACH est e ePrsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 44. 3.3. Techniques distribuese 34compl`tement distribu. Il ne requiert aucun contrle de la station centrale de base e eoet les nuds nont pas a garder des informations sur leurs voisins. Avec LEACH, `les nuds sorganisent en des clusters avec des nuds jouant le rle de o chefs decluster . Dans dautres algorithmes o` les uchefs de cluster sont choisis et xs ea priori, il est remarqu que ces nuds spuisent rapidement et puise aussi la` e eedure de vie du cluster, rendant ainsi inecaces les autres nuds appartenant a e`ce cluster. Cest pour cela que LEACH utilise des techniques de rotation alatoire epour dterminer la position du chef de cluster de telle faon que celle-ci puissee cvarier entre tous les nuds du rseau an de ne pas puiser toute lnergie dune e eseul nud. Egalement, LEACH eectue localement une fusion de donnes an de erduire la quantit de donnes qui doit tre transmise depuis les clusters vers la eeeestation de base, en plus de rduire lnergie consomme et donc daugmenter la eeedure de vie du rseau. e eLes capteurs se dsignent pour tre chef de cluster avec une certaine proba- e ebilit. Ils envoient aux autres nuds un message broadcast contenant leur statut. eChacun de ces autres nuds dtermine alors le cluster auquel il veut appartenir eneindiquant le chef de cluster avec lequel une communication ncessiterait le moinsednergie. Cela revient, la plupart du temps 1 , a choisir le chef de cluster qui est lee`plus proche de lui. Une fois que tous les nuds sont organiss en clusters, chaqueechef de cluster cre un planning au sein de son cluster. Celui-ci a pour but din-ediquer ` tous les nuds ordinaires du cluster dteindre leur dispositif radio et de aene les rallumer que lors de lopration de transmission du chef de cluster. On notee 1. En eet, cela nest pas toujours le cas. Le nud peut choisir comme chef de cluster un nudtr`s loign lorsqu ` cause dinfrences ou dautres dicults techniques, la communication avece ee ae eles autres chefs de cluster qui sont plus proches de lui est rendue plus dicile quavec le chef decluster loign.eePrsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 45. 3.3. Techniques distribuese35ainsi une rduction de lnergie consomme par les autres nuds. Cest aussi le e eenud chef de cluster qui est charg de faire une agrgation des donnes quil reoite e e cdes autres nuds de son cluster et de les transmettre ensuite ` la station de base.aCeci permet de compresser la taille des donnes transmises et donc de rduire leeenombre de communications. Le rseau y gagne en conomie dnergie vu que laeeefusion de donnes consomme moins dnergie que la communication.ee Comme sous-entendu plus haut, le chef de cluster consomme plus dnergie queeles autres nuds ordinaires du fait de toutes les tches qui lui sont assignes. An aede rpartir cette consommation dnergie a travers tout le rseau, le chef de clusteree `eva varier au l du temps et, ` direntes priodes, un autre nud se dsigne chef aeeede cluster. Ainsi, en un temps t1 , un ensemble C de nuds sauto-dsigne chefs ede clusters et en t1 + d, un autre ensemble C de nuds va prendre le relais etdevenir chefs de clusters a son tour, dpendant de la quantit dnergie qui reste`e e ea ces nuds, comme le montre la gure 3.1. De cette faon, ce sont toujours les` cnuds avec le plus de rserve dnergie qui se verront assigner les tches les plus eeaconsommatrices de ressources au sein du rseau. eDtails de lalgorithme LEACH e Lexcution de LEACH est divise en rounds de telle sorte que chaque round e edbute avec une phase dinitialisation, dans laquelle se fait lorganisation des clus- eters, suivie dune phase constante dans laquelle a lieu les transferts de donnes versela station de base. En vue de rduire les consommations de ressources, la phase econstante est longue compare ` la phase dinitialisation. e aPrsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 46. 3.3. Techniques distribuese 36Figure 3.1 Clusters dynamiques : (a) cluster C en un temps t1 . (b) cluster Cen un temps t1 + d. Les noeuds marqus dun mme symbole appartiennent aueemme cluster. Les chefs de cluster sont reprsents par un gros point.e eeLa phase dannonce Initialement lors de la cration des clusters, chaque nud edcide de devenir ou non un chef de cluster pour le round courant. Cette dcision eeest base sur le pourcentage suggr 2 de chefs de clusters dans le rseau et du e eeenombre de fois que le nud a t auparavant chef de cluster. Le nud n dcide de ee edevenir chef de cluster en choisissant un nombre alatoire compris entre 0 et 1. Si ece nombre est plus petit quun seuil T (n), alors le nud n devient chef de cluster.Le seuil est ainsi dtermin :ee P si n G, 1 1P (r mod ) T (n) = P 0 sinon O` P est le pourcentage dsir de chefs de cluster, r le round courant et G estu e e 1lensemble de nuds qui nont pas t chefs de cluster dans lesee P derniers rounds.Durant le round 0 (r = 0), chaque nud a une probabilit P de devenir chef de ecluster. Les nuds qui seront chefs de cluster au round 0 ne pourront pas le devenir2. Ce pourcentage est dtermin ` priori. eeaPrsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 47. 3.3. Techniques distribuese37 1pour les P rounds suivants. De ce fait, la probabilit pour que les nuds restants esoient des chefs de cluster va augmenter puisque un nombre rduit de nuds este1ligible comme chef de cluster. Apr`seeP 1 rounds, (cest-`-dire lorsquil ne reste aquun seul round), T devient gal ` 1 pour tous les nuds qui nont pas encore t eaee1chefs de cluster ; et apr`s eProunds, tous les nuds deviennent a nouveau ligibles` epour tre chef de cluster. e Lorsquun nud devient un chef de cluster pour le round courant, il envoie unmessage broadcast pour lannoncer aux nuds restants. Tous les nuds chefs decluster consomment la mme quantit dnergie lors de cette phase dannonce. Les ee enuds ordinaires ont alors leur quipement radio allum durant toute cette phasee edinitialisation pour tre capable de recevoir ces messages. Cest lorsque cette phaseesach`ve que chaque nud ordinaire choisit le cluster auquel il appartient pour ce eround, grce a la force du signal des messages broadcast quil a reus. Ceci du fait a ` cque le chef de cluster dont le message a t reu avec une plus grande force de signal ee csera sans doute celui avec qui une communication ncessitera moins dnergie. Sileeya cependant ex aequo dans le choix entre plusieurs clusters, la dcision se fera ealatoirement.eLinitialisation des clusters Apr`s quun nud ait choisi le cluster auquel il eappartient, il doit informer le chef de ce cluster. Tous les nuds ordinaires envoientainsi un message de ce type aux chefs de cluster et durant cette phase, le dispositifradio des chefs de clusters est en marche.La cration dun planning Comme soulign un peu plus en haut dans le e edbut de la sous-section 3.3.1, chaque chef de cluster cre un planning au sein de e ePrsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 48. 3.3. Techniques distribuese38son cluster dans le but dindiquer a tous les nuds ordinaires du cluster dteindre `eleur dispositif radio et de ne les rallumer que lorsquil devra eectuer une opration ede transmission. Le chef de cluster reoit les messages de tous les nuds voulantcfaire partie de son cluster. Il se base sur leur nombre et indique ` chacun dentre aeux, grce a un message broadcast le moment auquel ils pourront transmettre. a `La phase de transmission de donnes Apr`s que les clusters soient crseeeeet que le planning soit x, la phase de transmission peut commencer. Lorsquunenud a des donnes ` transmettre au chef de cluster, il le fait durant le moment e ade transmission qui lui est x. La consommation dnergie lie a cette oprationee e `eest optimise puisque le nud ordinaire a eu auparavant a choisir le chef de clus- e`ter avec qui une communication serait moins coteuse. Durant tout le moment deutransmission, les autres nuds ordinaires teignent leur dispositif radio, minimi-esant ainsi leur consommation dnergie. Le chef de cluster quant a lui garde sa e `radio active pour recevoir les signaux qui lui seront transmis de lensemble desnuds du cluster. Lorsque toutes les donnes ont ni de lui tre transmises, le chef eede cluster les compresse en un seul signal quil transmettra a son tour a la station ``de base. Cest cette phase qui correspond a la phase constante de lalgorithme de LEACH.`Cest apr`s cette phase que va dbuter un nouveau round et ainsi reprend le pro- eecessus.Rsum de lvaluation de la performance e ee Dans [HCB00], les simulations ont montr que la dissipation de lnergie danse ele rseau varie en fonction du pourcentage de nuds qui sont chefs de cluster.ePrsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 49. 3.3. Techniques distribuese 39La gure 3.2 permet dillustrer cela. La gure fait aussi remarquer quun tat duerseau o` il nexiste aucun chef de cluster est quivalent a ltat o` tous les nuds eu e` e usont chefs de cluster et que la consommation dnergie est tr`s leve dans chacun e e e ede ces cas. Ceci du fait que dans chacun de ces cas, tous les nuds vont eectuerdes oprations coteuses de transmission vers la station de base. La gure montreeugalement comment la technique de LEACH peut permettre une rduction par 7e ede la perte dnergie compare ` une transmission directe dans laquelle chaquee e anud communique directement avec la station de base. Ceci lorsquun nombreoptimal N de chefs clusters est choisi.Figure 3.2 Perte dnergie dans le rseau par rapport au nombre de chefs de eecluster Dune faon gnrale, ces simulations ont montr que LEACH, compare a une ce e ee `technique de transmission directe, rduit a hauteur de 8 fois lnergie consommee ` eepar la communication ; et que le premier vnement dpuisement dnergie dun e e eenud survient 8 fois plus tard. Une autre performance de LEACH rside dans le faitePrsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 50. 3.3. Techniques distribuese 40que les nuds puisent leur nergie dune faon alatoire. Avec cela, lhomognite e c ee e edu rseau est conserve et il ny aura pas de zones peu couvertes au dtrimenteeedautres.3.3.2 Lalgorithme ASCENT : Adaptive Self-ConguringSensor Networks Topologies Dans les rseaux de capteurs, le grand nombre de nuds empche la congura- e etion manuelle et les changements frquents dans la topologie ne permettent pas une epr-conguration de la conception. De ce fait, dans certains cas, les nuds doiventetre capables de sauto-congurer pour tablir une topologie qui supportera touteseeles communications compte tenu des contraintes nergtiques. ASCENT est bas eeesur lide que, mme quand la densit de nuds augmente, seul un sous ensembleeeedentre eux est ncessaire dans le maintien des oprations de routage [CE04]. Ce eesont ces quelques nuds qui vont excuter les tches de routage et de traitement e apendant que les autres seront en mode passive conomisant ainsi une bonne par-etie de lnergie. Dans ASCENT, chaque nud value son degr de connectivit et e ee eadapte ainsi sa participation ` la topologie du rseau.ae En eet la conception dASCENT a t inuence par beaucoup dautres tra-ee evaux du domaine. Il ya eu un grand nombre de travaux similaires qui se sontconcentrs sur la conguration des topologies dun rseau. La plupart dentre euxe eont utilis des techniques thoriques danalyses et des techniques de simulationeetout en impliquant des mcanismes de contrle de la consommation dnergie. Ilse oese sont bass sur la construction dun sous-ensemble dominant connect de nuds e e(Connecting Dominating Set) ` travers lequel reposaient toutes les stratgies dea ePrsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 51. 3.3. Techniques distribuese 41routage.Conception de ASCENT ASCENT choisit de faon adquate a partir de tous les nuds du rseau, des c e`enuds qui vont tre en mode active. Ceux l` restent ea veills tout le temps ete evont accomplir les tches de routage multi-saut au sein du rseau, pendant quea ele reste des nuds, en mode passive, vont contrler priodiquement sils doivent o eentrer en mode active ou non. Considrons un simple rseau sans l pour la collecte de donnes dans un ee eenvironnement. La gure 3.3 montre un schma simpli dASCENT lors de lini- eetialisation du rseau. Pour des soucis de clart, il nest montr que la formationeeedun rseau ` deux sauts. Cela peut bien videmment tre appliqu ` dautrese aee e arseaux de plus grande taille. e Initialement, seuls quelques nuds sont actifs. Les autres nuds restent enmode passive, a lcoute des paquets de donnes mains sans transmettre (cf. Fig.` e e3.3a). La source commence a mettre des paquets de donnes en direction du` eesink. Ce dernier se trouvant ` une position limite de la porte du radio de la a esource perd beaucoup de donnes. Cette situation est communment appele uneeetrou de communication. Le sink commence d`s lors a envoyer des messages help a e ` `ses nuds voisins qui sont en mode passive et les invite ` rejoindre le rseau. Lors- a equun voisin reoit un message help, il peut dcider de rejoindre le rseau. Cette ce esituation est illustre dans la gure 3.3b. D`s lors, il commence a transmettre et e e`a recevoir des paquets. Il signale aussitt aux nuds passifs lexistence dun nou-`oPrsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 52. 3.3. Techniques distribuese42veau nud actif, cest-`-dire lui, en envoyant un message neighbor announcement. aCette situation continue jusqu` ce que le nombre de nuds actifs se stabilise et adonc le cycle sarrte (cf. Fig. 3.3c). Lorsque ce processus se termine, les nouveaux enuds actifs rendent la transmission des paquets de donnes, de la source vers leesink, beaucoup plus solide. Lorsquaussi survient quelques dfaillances de cer-etains nuds, causant des pertes de donnes, le mcanisme reprend pour corriger les eeerreurs. Les titres suivants vont rentrer en dtail dans la conception de lalgorithmeede ASCENT et mieux dcrire son schma.e eFigure 3.3 Exemple simpli dautoconguration dun rseau . (a) Trou deeecommunication. (b) Etat de transition. (c) Etat nal.Les tats de transition dans ASCENT Dans ASCENT, les nuds peuventetre dans quatre tats dirents : un nud peut tre en mode sleep, passive, test,eee eou active. Il ne peut cependant pas tre dans les quatre en mme temps. La gureee3.4 ilustre les transitions dtat possibles. Initialement, les nuds ont une minute-erie pour eectuer la synchronisation. Quand un nud sort de ltat e endormi , cest-`-dire dmarre sa radio et son a etransceiver, il rentre en mode test. Dans cet tat, les nuds changent des donnese e ePrsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 53. 3.3. Techniques distribuese 43et des messages de routage. Le nud qui rentre en mode test choisi un temps Ttet envoie des messages neighbor announcement a ses voisins passifs. Lorsque Tt `expire, le nud entre en mode active. Si cependant, avant lexpiration de Tt , lenombre de nuds actifs atteint un seuil N T ou si le taux de donnes perdues DL ea dpass le DL qui existait au moment de la transition vers ltat test, alors le eeenud entre plutt en mode passive. Si plusieurs nuds veulent entrer en mme o etemps en mode test, alors les identiants qui leur sont donns lors de lenvoi desemessages neighbor announcement servira ` les dpartager dans la slection. Ainsi, aeeltat test permetedinterroger le rseau, an de savoir si la participation dunenouveau nud pourra accro sa connectivit. treeFigure 3.4 Etats de transitions dans ASCENT Quand un nud entre dans le mode passive, il dmarre un minuteur Tp et eenvoie des messages pour sannoncer. Ces messages sont utiliss par les nuds eactifs pour estimer la densit de nuds actifs dans leur voisinage. Cette densit eeest par la suite envoye a tout nud qui viendra a rentrer en mode passive.e ``Lorsque Tp est coul, le nud entre en mode sleep. Cependant si avant ceci, le eenombre de nuds voisins actifs est au dessous du seuil N T et que soit le DLest plus grand que le seuil de donnes perdues LT , ou que le DL est plus petit ePrsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 54. 3.3. Techniques distribuese 44que le LT mais quun message HELP a t reu par le nud, celui-ci passe versee cltat test. Dans ltat passive, les nuds ont leur dispositif radio allum et sonte eecapables dentendre toutes les transmissions de leurs voisins. Par contre, dans cettat, ils ne peuvent eectuer aucune opration de routage puisquil sagit duneetat dcoute. Donc le mode passive est un tat dans lequel le nud accomplitee edes tches de collecte dinformation concernant ltat du rseau sans interfrer aeeesur celles des autres nuds. Les nuds dans les tats passive et sleep mettentecontinuellement a jour le nombre de voisins actifs et le taux de perte de donnes.` eDe lnergie est consomme dans ltat passive puisque le dispositif radio est actif. ee eLorsque le nud est dans ltat sleep, il teint sa radio, dclenche une minuterie ee eTs . Quand Ts est coul, il rentre en mode passive. Finalement, le nud qui entreeeen mode active eectue des oprations de routage et dacheminement de donnes eejusqu` totale puisement de son stock dnergie. Il envoie des messages HELPae elorsque le taux de perte de donnes dpasse le seuil LT .ee3.3.3 Un protocole robuste de conservation dnergie pour eles rseaux de capteurs ` longue dure de vie : PEAS ea e Fan Ye et al. ont dvelopp un mcanisme appel PEAS [YZC+ 03] qui peutee e eallonger la dure de vie dun rseau de capteurs sans l de grande densit dans e e eun milieu hostile [WX06]. PEAS maintient les oprations robustes en utilisant de egrandes quantits de nuds de capteurs conomiques et de courte dure de vie. Il e e eprolonge le temps de fonctionnement du syst`me en faisant seulement travailler un eensemble de capteurs ncessaires et en mettant le reste en mode veille. Par priode,eeles capteurs qui sont en veille se rveillent et sondent lenvironnement local poureremplacer ceux qui sont hors dusage. Les priodes de veille sont auto-ajustes de eePrsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 55. 3.3. Techniques distribuese45faon dynamique, an de maintenir la vitesse de rveil des capteurs ` peu pr`scea econstante, sadaptant ainsi aux grandes densits de nuds.e PEAS partage la technique basique de dsactivation de nuds avec dautres eprotocoles de conservation dnergie dans les rseaux ad hoc sans l (GAF [XHE01], e eSPAN [CJBM02], AFECA [XHE00]) et dans les rseaux de capteurs (ASCENT e[CE04]). Toutefois, les travaux existants sont destins ` des ordinateurs portables e abeaucoup plus puissants et/ou ` un environnement de rseau relativement stable,aetandis que la conception de PEAS cible un environnement de travail beaucoupplus sv`re voire hostile, o` :e e u les dfaillances des nuds de capteurs peuvent devenir plutt frquentes,e o e la densit du dploiement des nuds peut tre dune grandeur beaucoup pluse e eleve que le minimum requis pour le fonctionnement normale e et les nuds sont trop limits en ressources mmoire et en ressources de cal- e ecul pour se permettre des protocoles relativement complexes. Aucun des travaux apparents naborde la question des oprations robustes e edans la mise en environnement hostile que la conception de PEAS a pris enconsidration. PEAS ralise une opration tr`s robuste en dcidant alatoirementeee ee ela dure du sommeil des nuds endormis an de dtecter et de remplacer acti-eevement les nuds en panne. Il limine les tats par voisins, supprimant ainsi lae ecomplexit de suivre chaque voisin dans un dploiement dense. Cest en contra- eediction avec les travaux apparents qui ncessitent soit un entretien des tats par e eevoisin ou une estimation des temps dactivit des nuds en travail, qui sont di-ePrsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 56. 3.3. Techniques distribuese 46ciles a raliser lorsque les nuds sont densment dploys et soumis a de frquentes` e eee`epannes.La conception de PEAS PEAS consiste en deux algorithmes simples que nous pourrons nommer : son-dage de lenvironnement (Probing Environment) et mise en veille approprie (Adap-etive Sleeping), qui dterminent respectivement (1) quels capteurs devraient fonc- etionner et comment un capteur qui vient de se rveiller dcide si il doit se rendormir, e eet (2) comment les temps de sommeil moyens des capteurs sont ajusts de mani`ree eapproprie pour garder une vitesse de rveil relativement constante.eeProbing Environment (Sondage de lenvironnement) Lobjectif de cet al-gorithme est de maintenir un nombre susant des nuds, en cas de dfaillancesede quelques autres nuds. PEAS utilise un mcanisme de sondage simple pour ersoudre le probl`me. Initialement tous les nuds sont en veille et cela pendant un e ecertain temps alatoire exponentiellement distribu. Quand un nud se rveille,e eeil envoie un message P ROBE au sein dune certaine plage de sondage Rp . Tousdes nuds en activit au sein de Rp devraient renvoyer un message de rponse.e eUn nud en veille commence son travail en permanence seulement sil ne reoit cpas de message de rponse. Sinon, il retourne a nouveau en veille pour une autre e`dure alatoire. ee Le temps de sommeil distribu de faon exponentielle permet de mesurer la vi- ectesse de rveil des nuds et dajuster les priodes de veille facilement dans la misee een veille approprie (cf. paragraphe sur Adaptive Sleeping). La plage de sondageeRp est donne par lapplication en fonction du degr de robustesse dont elle a be- e ePrsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 57. 3.3. Techniques distribuese47soin. Une application ncessitant un fonctionnement tr`s robuste peut choisir une eepetite Rp pour obtenir une plus grande densit, une redondance donc plus leve e e edes nuds en travail. Pour viter la dconnexion du rseau, Rp est gnralement eeee ebeaucoup plus petit que la plage de transmission maximale Rt dun capteur. Ilest suppos que les nuds peuvent ajuster leur puissance de transmission pourediuser des messages P ROBE en fonction de la plage de sondage Rp .Adaptive Sleeping (Mise en veille approprie) Lobjectif de la mise eneveille adaptative est de maintenir le nombre dveils par unit de temps constant eeet indpendant des densits de nuds locaux, qui varient suivant les dploiements,eeesuivant les endroits ou les moments. La frquence souhaite des rveils dpendee e ede lapplication. La mise en veille approprie ajuste, pour chaque nud actif,eles rveils de ses nuds voisins en veille, ` des niveaux appropris, an que les ea einterruptions transitoires dans la dtection et la communication causes par deseedfaillances de nud soient tolres par lapplication. e ee Lide de base est de laisser chaque nud actif mesurer le taux total de sondage e quil peroit de tous ses voisins en veille. Le nud actif inclut alors le taux mesur c e lorsqu il envoie un message REP LY a un voisin qui sonde lenvironnement. Tous`les nuds qui taient entrain de sonder ajustent alors la dure de leur sommeil eneeconsquence.eRsum de lvaluation de la performance e ee Fan Ye et Gary Zhong ont implment PEAS et valu ses performances grce `ee eea adeux indicateurs principaux : la dure de vie de la couverture et celle de la livraisonede donnes. La dure de vie de la couverture dsigne la priode pendant laquelle le ee eePrsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 58. 3.3. Techniques distribuese 48rseau a susamment de nuds actifs pour sassurer que chaque endroit est sur- eveill par des nuds actifs. La dure de vie de la livraison de donnes reprsente le e ee etemps pendant lequel le rseau peut fournir des rapports de donnes avec succ`s. eeeLes rsultats montrent que PEAS maintient une rsistance robuste contre les e edfaillances de nuds ` hauteur de 38% (incluant les puisements dnergie) ` eae eamoins de 1% de lnergie gnrale, et prolonge le temps de fonctionnement du ee esyst`me proportionnellement au nombre de nuds dploys.e ee Ils ont dabord vari le pourcentage de dfaillance des nuds de 7% ` 38%. eeaLa dure de vie de la couverture et celle de la livraison des donnes diminuente eharmonieusement avec les dfaillances des nuds (cf. gure 3.5). Mme pour lese edfaillances de nuds portes ` 38%, les dductions sont denviron 20%. Puis ils ee a eont fait varier a plus de 5 fois le nombre de nuds ncessaires dans un champ pour`ecouvrir la dtection de base avec une dfaillance des nuds xe a 13%. Aussi bieneee `la dure de vie de la couverture que celle de la livraison de donnes augmentent dee efaon linaire au nombre de nuds dploys (cf. gure 3.6). Enn ils ont mesurce ee ele surcot de PEAS dans lnergie consomme par les oprations de sondage et deu eeerponse et ils ont trouv quelle tait infrieure ` 1% de la consommation totale ee ee adnergie.ePrsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 59. 3.3. Techniques distribuese49Figure 3.5 Rsistance aux dfaillances de nudseeFigure 3.6 Extension de la dure de vieePrsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 60. CHAPITRE 4Conclusions50 61. 51 Les avances de la micro-lectronique ont favoris lusage de la technologie dese e ecapteurs sans l. Ce sont de petits quipements munis dune unit dacquisition,e edune unit de traitement, dune unit de transmission de donnes et dune sourceeeednergie qui leur permettent dassurer des tches de dtection de phnom`nesea e e ephysiques, de traitement de linformation et de transmission des donnes. Ces ap- epareils lorsquils sont utiliss de faon collaborative forment un rseau de capteurse c esans l et sont dune tr`s grande utilit dans plusieurs domaines de la science maise eaussi dans la vie de tous les jours. Ils sont utiliss dans la mdecine, larme, lae e edomotique, etc. Toutefois, vu leur capacit en stockage, leur puissance de calcul eteleur source dnergie limites, les rseaux de capteurs sans l doivent faire face aee e `dimportants ds dans leur conception et leur exploitation. Ainsi, direntes solu-eetions prenant en considration ces contraintes ont t envisages pour les rseaux e ee e ede capteurs. Dans ce document, apr`s notre introduction, nous avons eu a traiter de quelquese`gnralits dans les rseaux de capteurs sans l pour mieux entamer le sujet de e e eenotre travail. Nous y avons tudi lanatomie des capteurs pris individuellementeepuis larchitecture du rseau de capteurs ainsi que leur organisation protocolaireeen couches. Nous avons aussi, toujours dans les gnralits, montr quelques do- e e eemaines dans lesquels les applications des rseaux de capteurs sont dune grande eutilit. Cela nous a donn une ide des exigences auxquelles les rseaux de capteursee eedoivent satisfaire et il a par la suite t facile de ressortir des contraintes lies aeee `leur conception et ` leur exploitation. Ce sont ces contraintes parmi tant dautres aqui ont motiv beaucoup de chercheurs ` dvelopper un bon nombre de protocoles ea eet algorithmes pour les rseaux de capteurs. Cependant, il est tr`s dicile voire e ePrsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 62. 52impossible de trouver une solution gnrique adapte a toutes les applications dese e e `rseaux de capteurs. Cest cela qui nous a pouss ` aborder le probl`me de lop- eeaetimisation de leur dure de vie a travers direntes techniques trouves dans lae `e elittrature que lon a juges comme couvrant plus ou moins les direntes mthodese e eeexistantes de rduction dnergie dans les rseaux de capteurs sans l. Nous les ee eavons spares en techniques centralises et en techniques distribues pour rester e eeed`le au sujet de notre travail. Cest ainsi que, toujours a un dessein de clart,e`enous avons dabord eu a indiquer les nombreuses dnitions qui sont donnes de`eela dure de vie dun rseau de capteurs sans l. Ces dnitions dpendent de lob-e e eejectif de lapplication ou des hypoth`ses prises en compte. Ensuite, munis de cet eclaircissement sur ce quest la dure de vie dun rseau de capteurs, nous avonse e eanalys quelques solutions centralises et distribues visant ` rduire la consom-e eea emation dnergie donc a optimiser cette dure de vie. Elles utilisent pour la plupart e`edes techniques de duty cycling , de randomisation, etc. Certaines dentre ellesobligent chaque nud a avoir linformation sur ltat de ses voisins tandis que cela ` enest pas ncessaire dans dautres. Quelques unes divisent le rseau en clusters, e efont une certaine hirarchisation au sein des nuds du rseau en choisissant dese echefs de cluster, tandis que dans dautres une station centrale est ncessaire. Tous eces procds ont toutefois pour objectif principal dconomiser lnergie des nudse eeeet dallonger la dure de vie du rseau de capteurs sans l.e ePrsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 63. ANNEXEAAnatomie du capteur TelosB et comparaison desfonctionnalits de quelques autres (xbow) e 53 64. A.1. Anatomie du capteur TelosB54A.1Anatomie du capteur TelosB Figure A.1 Anatomie du capteur TelosBA.2Comparaison des fonctionnalits de quelquese capteursPrsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 65. A.2. Comparaison des fonctionnalits de quelques capteurse55 Fonctionnalits MTS300e MTS310MTS400MTS420 Acclrom`tre ee e X X XLumi`re ambientee X X Barom`tree X XVibreur X XGPSX Champ magntiquee XMicro X X PhotosensibleXXPhotorsistante X X Humidit et tempraturee e XX Thermistance X XTable A.1 Quelques capteurs et leurs fonctionnalitse XM2110M2110MPR2400 MPR400 Champ de 2.4GHz2.4GHz2.4GHz868-870 ; frquence eISM BandISM BandISM Band902-928MHz ProcesseurAtmel Atmel AtmelAtmel ATMega 1281 ATMega 1281 ATMega 128L ATMega 128L TransceiverRF230 RF230TITI Radio Atmel AtmelCC2420 CC1000 Atmel Atmel AtmelAtmel Serial FlashAT45DB41B AT45DB41B AT45DB41B AT45DB41B (512 kB)(512 kB)(512 kB) (512 kB) RAM 8 KBytes8 KBytes4 KBytes4 KBytesTable A.2 Quelques capteurs et leurs caractristiques techniques ePrsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 66. Bibliographie[A+ 06]Jean ARLAT et al. Tolrance aux fautes. In Encyclopdie de lin-e e formatique et des syst`mes dinformation, (J. Akola and I. Comyn- e Wattiau, Eds.), pages 240270. Vuibert, Paris, France, 2006.[ASSC02] I. F. AKYILDIZ, W. SU, Y. SANKARASUBRAMANIAM, and E. CAYIRCI. Wireless sensor networks : a survey. Computer Net- works, 38 :393422, 2002.[AV10] I. F. AKYILDIZ and M. C. VURAN. Wireless Sensor Networks, chap- ter 3, pages 3739. 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-Ecient Computing and Networking e- Energy 2010, Passau, Germany, April 2010.[BC] UC Berkeley and MLB Co.29 palms xed/mobile expe- riment, tracking vehicles with a uav-delivered sensor network, http ://robotics.eecs.berkeley.edu/~pister/29palms0103/. 56 67. Bibliographie57[BCSZ05] P. BERMAN, G. CALINESCU, C. SHAH, and A. ZELIKOVSKY. Ecient 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 1721, 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 908909, New York, 1994.[C+ 95]G. COYLE et al. Home telecare for the elderly. Journal of Telemedi- cine and Telecare 1, pages 183184, 1995.[CE04] Alberto CERPA and Deborah ESTRIN.Ascent : Adaptive self- conguring sensor networks topologies. IEEE Transactions on Mobile Computing, 3 :272285, July 2004.[CJBM02] Benjie CHEN, Kyle JAMIESON, Hari BALAKRISHNAN, and Ro- bert MORRIS. Span : An energy-ecient coordination algorithm for topology maintenance in ad hoc wireless networks. Wireless Networks, 8 :481494, 2002. 10.1023/A :1016542229220.[CTLW05] Mihaela CARDEI, My T. THAI, Yingshu LI, and Weili WU. Energy- ecient target coverage in wireless sensor networks. In IEEE Infocom, 2005.Prsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 68. Bibliographie 58[Dim]Dimap. Sistemas de seguimiento y vigilancia ambiental, http ://www.libelium.com/wireless sensor networks to detec forest res/.[HCB00]Wendi Rabiner HEINZELMAN, Anantha CHANDRAKASAN, and Hari BALAKRISHNAN. Energy-ecient 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 dnergie pour lese rseaux de capteurs sans l. PhD thesis, Institut National Polytech-e 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. Diusion et couverture bases sur le clustering e dans les rseaux de capteurs : application ` la domotique. PhD the- ea sis, Universit A.B Tlemcen Facult des Sciences pour l ? ?Ingnieur e ea eee & Universit de Franche-Comt U.F.R Sciences et Techniques Ecole Doctorale SPIM, 2009.[MAK08]Abdallah MAKHOUL. Rseaux de capteurs : localisation, couver-e ture et fusion de donnes. PhD thesis, Laboratoire dInformatique de eee lUniversit de Franche-Comt (LIFC) Ecole Doctorale Sciences Pour lIngnieur et Microtechniques (SPIM), November 2008.e[N+ 98]Y. H. NAM et al. Development of remote diagnosis system integrating digital telemetry for medicine. In International Conference IEEE-Prsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 69. Bibliographie 59EMBS, pages 11701173, Hong Kong, 1998.[NHR+ 00] N. NOURY, T. HERVE, V. RIALLE, G. VIRONE, E. MERCIER,G. MOREY, A. MORO, and T. PORCHERON. Monitoring behaviorin home using a smart fall sensor. In IEEE-EMBS Special Topic Confe-rence on Microtechnologies in Medicine and Biology, pages 607610,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 19471050, Hong Kong, 1998.[PK00]G. POTTIE and W.J. KAISER. Wireless integrated network sensors.Communications of the ACM, 43 :5158, 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 910. Springer Science+Business Media, 2006.[RAJ+ 00] Jan M. RABAEY, M. Josie AMMER, Julio L. DA SILVA Jr., DannyPATEL, and Shad ROUNDY. Picoradio supports ad hoc ultra-lowpower wireless networking. IEEE Computer Magazine, pages 4248,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-Prsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e 70. Bibliographie 60sing for mission and ight systems. In IEEE Aerospace Conference,volume 7, pages 459463, 2000.[WX06]L. WANG and Y. XIAO. A survey of energy-ecient 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 7084, 2001.[YZC+ 03] Fan YE, Gary ZHONG, Jesse CHENG, Songwu LU, and LixiaZHANG. Peas : A robust energy conserving protocol for long-lived sen-sor networks. In Proceedings of the 23rd International Conference onDistributed Computing Systems, ICDCS 03, Washington, DC, USA,2003. IEEE Computer Society.[ZH06]Honghai ZHANG and Jennifer C. HOU. Maximising -lifetime forwireless sensor networks. Int. J. Sen. Netw., 1 :6471, September2006.Prsent et soutenu par Papa Cheikh Cisse | UGB St-Louis Sngaleee e