Topologies des réseaux de capteurs sans fils

Les réseaux de capteurs

Introduction :Grâce au progrès immense et sans égale dans le domaine technique, une nouvelle architecture a vu le jour, c’est les réseaux de capteurs sans fils. Ce type de réseaux résulte d’une fusion de deux pôles de l’informatique moderne : les systèmes embarqués et les communications sans fils. Les réseaux de capteurs sans fil (RCSF) sont pratiquement composés d’un ensemble d’unités de traitement embarquées, appelées « nœuds de capteur : motes », communiquant via des liens sans fils, leur but général est la collecte d’un ensemble de paramètres de l’environnement entourant, faire le traitement et les transmettre vers le monde d’extérieur. Ces réseaux sont employés dans divers domaines d’applications telles que la médecine, la sécurité, la surveillance environnementale etc. Grâce à ce potentiel riche en applications, les RCSF ont su se démarquer de leur origine MANET et attirer de grandes firmes à travers le monde, tels que IBM, Sun, Intel et Philips.En parallèle, des perspectives d’amélioration et des recherches sont en cours pour régler de multiples contraintes liées aux RCSF telles que la durée de vie du réseau (assuré la connectivité et la couverture), la sécurité, la défaillance des nœuds de capteurs (des cassures, des pannes physique etc.).

Définition : Les réseaux de capteurs (WSN) sont considérés comme un type spécial de réseaux ad hoc. Les nœuds de ce type de réseaux consistent en un grand nombre de micro-capteurs déployés par centaines ou milliers, capables de récolter et de transmettre des données environnementales d’une manière autonome à l’aide d’un support radio, infrarouge ou optique.La position de ces nœuds n’est pas obligatoirement prédéterminée. Ils sont dispersés aléatoirement à travers une zone géographique, appelée champ de captage, qui définit le terrain d’intérêt pour le phénomène capté. Ce dispersement aléatoire des capteurs nécessite que le protocole utilisé pour ce réseau possède des algorithmes d’auto-organisation afin de résister aux déploiements.

Les nœuds capteurs doivent également être très rigides et doivent pouvoir survivre dans des conditions environnementales dures comme le feu ou l’eau par exemple.Les données captées sont acheminées d’un équipement expéditeur jusqu’à leur destinataire par l’intermédiaire d’une architecture multi-saut à un nœud considéré comme un point de collecte (nœud puits). Ce dernier peut être connecté à l’utilisateur du réseau via Internet ou un satellite à l’ordinateur central (gestionnaire de tâches) pour analyser ces données et prendre des décisions.

Systèmes d’exploitation: Les systèmes d’exploitation sont spécifiquement conçus pour optimiser l’usage des ressources matérielles limitées dont les réseaux de capteurs disposent(peu de mémoire RAM, une vitesse de traitement de processeur faible et peu d’énergie électrique). De nombreux systèmes d’exploitation spécialisés existent, parmi lesquels : il y a TinyOS, Contiki, SOS, MantisOS, Nano RK qui sont conçus pour répondre à ces contraintes.

Architecture d’un nœud de capteur

Un nœud de capteur est composé de trois unités alimentées par une source d’énergie embarquée :
Unité de captage : Elle permet de détecter des mesures sur des paramètres environnementaux et transforme le signal analogique en numérique par un convertisseur analogique numérique ADC et le transmettre à l’unité de traitement.
Unité de traitement : Elle est composée d’une mémoire (unité de stockage) et d’un processeur qui permet d’effectuer des calculs pour que ce nœud puisse collaborer avec les autres du réseau et possède également deux interfaces une liée avec l’unité de captage et la seconde liée avec l’unité de transmission par laquelle elle communique les données traitées.
Unité de transmission : Elle est responsable de toutes les émissions et réceptions des données via un support radio. L’unité de transmission est l’unité qui consomme le plus d’énergie par apport aux précédentes unités.
Unité d’énergie : un micro-capteur est muni d’une ressource énergétique limitée généralement une batterie qui alimente tous ses composants

Topologies des réseaux de capteurs sans fil 

Les topologies des réseaux de capteurs sont déterminées à partir des protocoles de routage utilisés pour l’acheminement des données entre les nœuds et le sink. Ces protocoles peuvent être hiérarchiques, plat (Flat) ou basé localisation (location-based).

Topologie Hiérarchique : Les protocoles à topologie hiérarchique forment des réseaux dans lesquels un nœud central sink (le niveau supérieur de la hiérarchie) est relié à un ou plusieurs autres nœuds qui appartiennent à un niveau plus bas dans la hiérarchie (deuxième niveau) avec une liaison point à point. Aussi, chacun des nœuds du deuxième niveau aura également un ou plusieurs autres nœuds de niveau plus bas dans la hiérarchie (troisième niveau) reliés à lui avec une liaison point à point.

Chaque ensemble de nœuds forme une sorte de motif (Cluster). Les nœuds du deuxième niveau jouent le rôle des passerelles entre ceux du troisième niveau et le sink. Dans ce cas, le routage devient plus simple, puisqu’il s’agit de passer par les passerelles pour atteindre le nœud destination. Dans certains types de protocoles (tel que LEACH dans les RCSF), un algorithme d’élection est exécuté dans chaque cluster, les nœuds élisent un d’eux pour être clusterhead.L’élection est basée sur des critères tels que l’énergie disponible, la qualité de communication, et ainsi de suite, ou la combinaison de plusieurs d’entre elles. Le rôle du clusterhead est la collecte des informations issues des nœuds et les renvoyer vers le sink. Un réseau basé sur une topologie hiérarchique doit avoir au moins trois niveaux dans sahiérarchie, puisqu’un réseau avec un nœud central sink et seulement un niveau hiérarchique au-dessous.Si les nœuds dans un réseau basé sur la topologie hiérarchique doivent effectuer un tel traitement sur les données transmises entre les nœuds dans le réseau, alors les nœuds qui sont à des niveaux plus élevés dans la hiérarchie doivent effectuer plus de traitement que les nœuds de niveau inférieur. Dans le cas de LEACH, les informations sont transmises d’un nœud capteur vers le nœud sink .À titre d’exemple des protocoles utilisant une topologie hiérarchique on peut citer le protocole LEACH (Low-energy Adaptive Clustering Hierarchy), CBRP (Cluster Based Routing Protocol).

Topologie plate : Les protocoles à topologie plate (flat) considèrent que tous les nœuds sont égaux, ont lesmêmes fonctions, et peuvent communiquer entre eux sans devoir passer par un nœud particulier ou une passerelle. Seul un nœud particulier, le Sink, est chargé de la collecte des données issues des différents nœuds capteurs afin de les transmettre vers les centres de traitement. En cas où la destination ne fait pas partie du voisinage de la source, les données seront transmises en utilisant les sauts multiples à travers les nœuds intermédiaires .Ce type de réseau présente l’avantage de l’existence de différents chemins d’une source vers une destination et c’est pour remédier au problème de changement brusque de topologie ou la défaillance d’un nœud intermédiaire.

Topologie basée sur localisation : Les protocoles à topologie basée sur localisation suppose que :
– Le réseau est partitionné en plusieurs zones de localisation.
– Chaque zone a son identifiant.
– Chaque nœud a un identifiant EUI (End-system Unique Identifier) et enregistre dynamiquement l’identifiant de la zone à laquelle il appartient temporairement.

L’information temporaire de localisation appelée LDA (Location Dependent Address) qui est un triplet de coordonnées géographiques (longitude, latitude, altitude) obtenues, parexemple, aumoyen d’un GPS. Une telle topologie exige l’implémentation d’un algorithme de gestion de localisation qui permet aux nœuds de déterminer les endroits approximatifs des autres nœuds. Ce type de topologie est mieux adapté aux réseaux avec une forte mobilité. Avant d’envoyer ses données à un nœud destination, le nœud source utilise un mécanisme pour déterminer la localisation de la destination puis inclus l’identifiant de zone de localisation et du nœud destination dans l’entête du paquet à envoyer .À titre d’exemple des protocoles utilisant une topologie basée localisation, ont peut citer GEAR (Geographic and Energy Aware Routing) et LAR (Location-Aided Routing protocol).

Consommation d’énergie dans les RCSF 

Les nœuds de capteurs ne sont pas alimentés par une source qui peut durer à l’infini, au contraire ils possèdent une batterie qui est prête à se décharger à tous moment selon l’utilisation.Ils doivent donc fonctionner avec un bilan énergétique frugal. En outre, ils doivent le plus souvent avoir une durée de vie de l’ordre de plusieurs mois, voire de quelques années, puisque le changement des batteries n’est pas une opération facile lorsqu’on perde leurs emplacements et quand le nombre est important.Afin de concevoir des solutions efficaces en énergie, il est extrêmement important de faire d’abord une analyse des différents facteurs provoquant la dissipation de l’énergie d’un nœud de capteur et par la suite exposer différents protocoles exploités dans ce domaine.

Energie de traitement :   L’énergie de traitement se divise en deux parties : l’énergie de commutation et l’énergie de fuite. L’énergie de commutation est déterminée par la tension d’alimentation et la capacité totale commutée au niveau logiciel (en exécutant un logiciel). Par contre l’énergie de fuite correspond à l’énergie consommée lorsque l’unité de calcul n’effectue aucun traitement. En général, l’énergie de traitement est faible par rapport à celle nécessaire pour la communication.

Energie de capture ou de détection : Il y a plusieurs sources de consommation d’énergie par le module de détection, notamment, la conversion analogique numérique, l’échantillonnage etc.Les capteurs passifs (température) consomment le plus souvent peu d’énergie par rapport aux autres composants du nœud de capteur. Notons, les capteurs actifs tels que les sonars, les capteurs d’images, etc. peuvent consommer beaucoup d’énergie.En outre, il existe d’autres formes de dissipation d’énergie telles que les lectures et les écritures en mémoire. Cependant, la transmission de données est la plus consommatrice en énergie. Le coût d’une transmission d’un bit d’information est approximativement le même que le coût nécessaire au calcul d’un millier d’opérations.

Energie de communication : L’énergie de communication se décline en deux parties : l’énergie de réception et l’énergie de l’émission. Cette énergie est déterminée par la quantité des données à communiquer et la distance de transmission, ainsi que par les propriétés physiques du  module radio. L’émission d’un signal est caractérisée par sa puissance. Quand la puissance d’émission est élevée, le signal aura une grande portée et l’énergie consommée sera plus élevée. Notons que l’énergie de communication présente la portion la plus grande de l’énergie consommée par un nœud de capteur. Un autre facteur déterminant est que le passage de la radio d’un mode à un autre engendre une dissipation d’énergie importante due à l’activité des circuits électroniques. Par exemple, quand la radio passe du mode sommeil au mode émission pour envoyer un paquet, une importante quantité d’énergie est consommée pour le démarrage de l’émetteur lui-même.

Modèle de consommation d’énergie : Heinzelman et al. [10] proposent un modèle radio de consommation d’énergie. Ainsi, les énergies nécessaires pour émettre ETx(s,d) et recevoir ERx(s) des messages sont données par :
 Pour émettre un message de s bits vers un récepteur loin de d mètres, l’émetteur consomme :
ETx(s, d) = ETx elec(s) + ETx amp(s, d) II.1
ETx(s, d) = (Eelec * s) + (Eamp * s * d^2)
 Pour recevoir un message de s bit, le récepteur consomme :
ERx(s) = ERx elec(s)
ERx(s) = Eelec * s
 Eelec et Eamp représentent respectivement l’énergie de transmission électronique et d’amplification.

Algorithmes de conservation d’énergie 

Initialement tous les nœuds se trouvent en mode de veille. Après, un nœud en mode veille s’active et diffuse un message de sondage dans une zone de communication (surface de rayon Rc) puis il attend une réponse. Si aucune réponse n’est reçue durant une période de temps définie, il reste actif jusqu’à ce qu’il épuise son énergie. Sinon, un voisin (se trouvant à une distance plus petite qu’une valeur définie R) répond à l’émetteur lui permettant de repasser en mode de veille.

La valeur R est choisie sur la couverture redondante désirée, alors que la période pour qu’un nœud s’active et émet le message dépend de la période de détection. Cette approche distribuée a une faible complexité et résiste aux pannes au cas de disparition des nœuds. Par contre, il ne garantit pas la couverture de toute la zone d’intérêt. Dans une première phase de découverte du voisinage, des messages bonjour sont émis tour à tour par chacun des nœuds. Ensuite, une règle d’éligibilité est admise permettant à un nœud d’entrer en mode veille tant que ses nœuds voisins surveillent sa région de détection (de couverture).Après l’évaluation de son éligibilité pour passer en mode de veille (au cas où sa région est couverte), un nœud reste actif pour un certain temps pour éviter d’avoir des points non couverts.

Durant ce temps, s’il reçoit un message d’un de ses voisins informant qu’il va se mettre en mode de veille, le nœud marque l’expéditeur comme endormi et il réévalue son éligibilité. Si sa zone est toujours couverte, il diffuse un message informant ses voisins qu’il passera en mode de veille, attend une courte période et éteint sa batterie. Un nœud en mode de veille se réveille périodiquement pour vérifier son éligibilité et ensuite il décidera soit de rester en mode de veille soit de passer au mode actif. Cet algorithme permet de diminuer considérablement le nombre de nœuds actifs et  d’augmenter la durée de vie tout en conservant une couverture totale du réseau.Un autre algorithme de couverture localisé a été proposé par Gallais et al [19]. L’idée de cet algorithme est de maintenir à la fois la connectivité et la couverture tout en réduisant les communications (messages) entre les nœuds. Afin de réduire le taux de communications cette méthode évite la phase d’initialisation et de la découverte des voisins (par exemple message bonjour [18]).

Chaque nœud attend un temps aléatoire avant de prendre une décision d’activité. Une fois le temps d’attente écoulé, si sa région de couverture est totalement couverte alors il décide d’être passif sans envoyer aucun message. S’il doit demeurer actif, en revanche, un message annonçant son activité est envoyé. De cette manière, il informe les nœuds voisins de sa présence. L’inconvénient de cette approche est la synchronisation des nœuds, qui est coûteuse en terme d’énergie. Une analyse géométrique de la relation entre la couverture de la zone surveillée et la connectivité du réseau est faite. Et un protocole CCP (Coverage Configuration Protocol) est proposé qui permet de configurer dynamiquement le réseau pour garantir différents degrés de couverture en fonction des requis de l’application. Dans CCP, chaque capteur choisit son état (actif ou en veille) en fonction du degré de couverture des points d’intersectionde son cercle de couverture avec celui de ses voisins. Il permet ainsi de garantir une K-couverture, c’est à dire la couverture de chaque point de surface par au moins K capteurs.

Table des matières

Introduction générale
Chapitre I : vue générale sur les réseaux de capteurs
I.1 Introduction
I.2 Définition
I.3 Architecture physique des réseaux de capteur
I.4 Caractéristiques du réseau
I.5 Topologies des réseaux de capteurs sans fils
I.5.1 Topologie Hiérarchique
I.5.2 Topologie plate
I.5.3 Topologie basée sur localisation
I.6 La Synchronisation
I.7 Réseau ad hoc
I.7.1 Comparaison entre réseau ad hoc et réseau de capteur
I.8 La pile protocolaire
I.9 Applications militaires
I.10 Conclusion
Chapitre II : réduction de consommation d’énergie
II.1 Introduction
II.2 Notion de durée de vie d’un réseau
II.3 Consommation d’énergie dans les RCSF
II.3.1 Energie de traitement
II.3.2 Energie de capture ou de détection
II.3.3 Energie de communication
II.3.3.1 Modèle de consommation d’énergie
II.4 Facteurs intervenants dans la consommation d’énergie
II.4.1 Accès au medium de transmission
II.4.2 Modèle de propagation radio
II.4.3 Routage des données
II.5 Mécanismes de conservation de l’énergie dans les RCSF
II.5.1 Au niveau des différentes couches
II.5.2 Conservation de l’énergie sous contrainte de couverture
II.5.3 Conservation de l’énergie par la formation de grappes (clustering)
II.5.4 Par l’ajustement optimisé des puissances de transmission
II.5.5 Par la planification optimisée des états des capteurs
II.6 Conclusion
Chapitre III : Les techniques de contrôle de topologie
III.1 Introduction
III. 2 Contrôle de la topologie
III.2.1 Les motivations du contrôle de topologie
III.2.1.1 La conservation del’énergie
III.2.1.2 La Collision
III.2.2 La définition de contrôle de la topologie
III.2.3 Techniques hiérarchiques de la construction de topologie
III.2.3.1 Les techniques Backbone
1.1 Les Protocoles A3 et A3Lite de construction de la topologie pour la connectivité
1.2 L’algorithme A3Lite
1.3 L’algorithme A3Cov
1.4 L’algorithme d’A3CovLite
1.5 Définition -couverture de détection
III .2.4 La maintenance
III.2.5 La puissance de transmission
III.2.4.1 Définition de l’algorithme de KNEIGH-Tree
III.2.4.2 exécution du protocole KNEIGH-Tree
III.3 Conclusion
IV Etude empirique
IV.1 Introduction
IV.2 Simulation I
IV.3 Simulation II
IV.4 Simulation III
IV.4.1 génération de déploiement
IV.5 Simulation IV
IV.6 Simulation V
IV.7 conclusion
Conclusion générale
Annexe
Bibliographie

Télécharger le rapport complet