MASTER 1 INFORMATIQUE DES SYSTEMES EMBARQUES
PROMOTION
2012 ETAT DE L’ART DES RESEAUX DE
CAPTEURS SANS FIL
ENSEIGNANT ENCADRANT : Mme AOUDIA Hania
REALISE PAR : Mlle BOUAZA NADIA
. Mr LAHOUAZI FERHAT
RAPPORT DE PROJET
TUTORE
2
Résumé……………………………………………………………………………….7
Introduction générale……………………………………………………………..8
Chapitre 1 : Généralités sur les réseaux de capteurs sans fil
1. Introduction……………………………………………………………………...9
2. Définition d’un réseau de capteurs sans fil……………………………………....9
3. Architecture de communication d’un RCSF………………………………….…9
4. Définition d’un nœud capteur. ………………………………………………...10
5. Composition d’un nœud capteur………………………………………………10
6. Topologie des RCSFs…………………………………………………………..11
7. Domaines d’applications des RCSFs. …………………………………………11
8. Caractéristiques et contraintes des RCSFs ………………………………….…12
9. Conclusion …………………………………………………………………...…13
Chapitre2 : Les protocoles de routage dans les RCSFs.
1. Introduction……………………………………………………………………...15
2. Contraintes de conception des protocoles de routage pour les RCSFs………….15
3. Classification des protocoles de routage des RCSFs…………………………...15
4. Les protocoles de routage à plat…………………………………………………16
5. Les protocoles de routage hiérarchiques………………………………………....23
6. Conclusion ……………………………………………………………………....29
Chapitre 3 : Implémentation du protocole MCFA
1. Introduction……………………………………………………………………..30
2. Les outils de simulation et d’implémentation…………………………………....30
3. Organigramme du MCFA………………………………………………………..33
4. Résultats de la simulation ……………………………………………………….34
5. Conclusion ……………………………………………………………………....36
Problèmes rencontrés……………………………………………………………..36
Conclusion générale………………………………………………………………..37
3
Liste des figures
Figure 1 : Architecture de communication d’un RCSF.
Figure 2 : Les composants d’un nœud capteur.
Figure 3: Fonctionnement du protocole SPIN
Figure 4: Fonctionnement du protocole EAR
Figure 5 : Propagation des intérêts et établissement des gradients
Figure 6 : Renforcement des chemins.
Figure 7 : Agents d'événements.
Figure 8 : Formation de clusters dans LEACH
Figure 9 : Organigramme MCFA pour l’établissement des coûts de transmissions.
Figure 10 : La simulation sous TinyViz.
4
Acronymes
ADC : Convertisseur analogique/numérique.
ADV: Advertissement.
APTEEN: Adaptive Threshold-sensitive Energy Efficient sensor Network protocol.
CH: Cluster Head.
HEED: Hybrid, Eenergy-Efficient, Distributed approach.
RCSF : Réseau de Capteurs Sans Fil.
LS: Link State.
TTDD: Two-Tier Data Dissemination.
MCFA: Minimum Cost Fordwarding Algorithm.
TEEN: Threshold-sensitive Energy Efficient sensor Network protocol.
GSR: Global State Routing.
PEGASIS: Power-Efficient Gathering in Sensor Information Systems.
LEACH: Low Energy Adaptive Clustering Hierarchy.
RR: Rumour Routing.
SPIN: Sensor Protocol for Information via Negotiation.
CTLMN: Clustering Technique for Large multihop Mobile wireless Networks.
VGA: Virtual Grid Architecture routing.
RPT : Report, un paquet contenant des informations pour les intérêts et préférences de
l’utilisateur.
DD : Directed Diffusion.
EAR: Eavesdrop And Register.
RREQ: Route Request.
RREP: Route Reply.
CT : Compteur de temps.
ST: Seuil Soft.
HT: Seuil Hard.
Mas: Master Aggregators.
Las: Local Aggregators.
WSN: Wireless Sensor Network.
5
Remerciements
Nous tenons à remercier en premier lieu Mme Hania AOUDIA, qui nous a
proposé un sujet intéressant, sur une technologie nouvelle et dont l'approche est similaire
à celle du monde de la recherche. En effet, nous avons dû faire une démarche personnelle
pour obtenir des sources d'informations et nous la remercions de nous avoir offert cette
ouverture d'esprit. Nous la remercions aussi pour ses critiques constructives et son
assistance.
Nos reconnaissances sont également adressées aux membres de jury qui feront
l’honneur d’examiner et de juger notre travail.
6
Résumé
Le but de notre projet consiste à étudier les protocoles de routage dans les réseaux de
capteurs sans fil (RCSFs) et d’implémenter le protocole MCFA (Minimum Cost Fordwarding
Algorithm).
Grâce à leur apport concret et à leur réalisme, les RCSFs ont pu attirer un nombre
croissant d'industriels, et entrer dans divers domaines. Mais malheureusement, ils sont loin
d’être parfaits ; ils présentent encore quelques contraintes et caractéristiques qui restent
toujours à améliorer et qui ont fait le sujet de plusieurs recherches; notamment la durée de vie,
les ressources limitées des nœuds et le coût de communication qui doit être minimisé.
Ce rapport est composé de trois grandes parties. La première présente quelques
généralités que nous avons suggérées utiles pour la bonne compréhension du thème. La
seconde est consacrée pour le routage et les différents protocoles de routage des réseaux de
capteurs sans fil. La troisième présente l’implémentation du protocole MCFA que notre
encadrant nous a proposé d’étudier, ainsi que les outils utilisés et enfin une conclusion.
7
Introduction générale :
Depuis leur création, les réseaux de communication sans fil ont connu un succès sans
cesse au sein des communautés scientifiques et industrielles. Grâce à ses divers avantages, cette
technologie a pu s'instaurer comme acteur incontournable dans les architectures réseaux
actuelles.
Au cours de son évolution, le paradigme sans fil a vu naître diverses architectures
dérivées, telles que : les réseaux cellulaires, les réseaux locaux sans fil et autres. Durant cette
dernière décennie, une architecture nouvelle a vu le jour : les réseaux de capteurs sans fil. 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 fil. Un réseau de capteurs sans fil (RCSF), ou "Wireless
Sensor Network" (WSN), est composé d'un ensemble d'unités de traitements embarquées,
appelées "nœuds", communiquant via des liens sans fil. Le but général d'un WSN est la collecte
d'un ensemble de paramètres de l'environnement entourant les nœuds tels que la température ou
la pression de l'atmosphère, afin de les acheminer vers des points de traitement [5].
Les RCSF sont souvent considérés comme étant les successeurs des réseaux ad hoc. En
effet, les RCSF partagent avec les MANET (Mobile Ad hoc NETworks) plusieurs propriétés
telles que l'absence d'infrastructure et les communications sans fil. Mais l'une des différences
clés entre les deux architectures est le domaine d'application. Contrairement aux réseaux
MANET, qui n'ont pas pu connaître un vrai succès, les RCSF ont su attirer un nombre croissant
d'industriels, vu leur réalisme et leur apport concret. En effet, le besoin d'un suivie continu d'un
environnement donné est assez courant dans diverses activités de la société [7].
Les processus industriels, les applications militaires, le domaine médical, ainsi que
l'agriculture de précision ne sont que quelques exemples d'une panoplie vaste et variée
d'applications possibles du suivi continu offert par les RCSF. 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, telles qu’IBM, Sun, Intel et Philips [12].
8
Chapitre 1
Généralités sur les réseaux de capteurs sans fil
1. Introduction
Les progrès réalisés ces dernières décennies dans les domaines de la microélectronique,
de la micromécanique et des technologies de communication sans fil, ont permis de produire à
un coût raisonnable des composants miniaturisés[2].
De ce fait, un nouveau domaine de recherche s’est crée pour offrir des solutions
économiquement intéressantes et facilement déployables à la surveillance à distance et au
traitement des données dans les environnements complexes et distribués : les réseaux de
capteurs sans fil (RCSF) [5].
2. Définition d’un réseau de capteur sans fil
Un réseau de capteurs sans fil [11], (en anglais : Wireless Sensor Network - WSN), est un
type particulier des réseaux ad- hoc, composé d’un grand nombre des nœuds capables de
récolter et de transmettre des données environnementales d'une manière autonome.
3. Architecture de communication d’un RCSF
Les nœuds capteurs sont habituellement dispersés dans une zone de capture, chacun de
ces nœuds a la possibilité de collecter les données et de les router vers une ou plusieurs stations
de base ; point de collecte de données capturées. Elle peut communiquer les données collectées à
l’utilisateur final à travers un réseau de communication, éventuellement l’internet. L’utilisateur
peut à son tour utiliser la station de base comme passerelle, afin de transmettre ses requêtes au
réseau. Cette architecture est illustrée dans la figure2 [10].
9
Figure 1 : Architecture de communication d’un RCSF.
4. Définition d’un nœud capteur
Un capteur sans fil est un petit dispositif électronique capable de mesurer une valeur
physique environnementale (température, lumière, pression, etc.), et de la communiquer à un
centre de contrôle via une station de base [1]. Il a trois fonctions :
o La collecte d’information.
o Le traitement d’information.
o La communication d’information.
5. Composition d’un nœud capteur
Un nœud capteur est composé de quatre unités principales qui sont présentés dans la
figure 1 [10]:
Figure 2: Les composants d’un nœud capteur.
Unité de capteur
Capteur ADC
Unité de traitement
Processeur mémoire
Unité de communication
Unité d’énergie
10
Unité de capteur : composée de deux unités :
o Un dispositif de capteur physique qui prélève l’information de l’environnement local
o Un convertisseur analogique / numérique (ADC)
Unité de communication : composée d’un émetteur / récepteur (module radio) permettant la
communication entre les différents nœuds de réseau
Unité de traitement : Les données captées sont communiquées aux processeurs ou elles sont
stockées dans la mémoire.
Unité d’énergie : C’est la batterie qui n’est généralement ni rechargeable ni remplaçable.
6. Topologies des RCSFs
Il existe plusieurs topologies pour les réseaux de capteurs [11] :
6.1. Topologie en étoile:
La topologie en étoile est un système uni-saut. Tous les nœuds envoient et reçoivent
seulement des données avec la station de base. Cette topologie est simple et elle demande une
faible consommation d’énergie, mais la station de base est vulnérable et la distance entre les
nœuds et la station est limitée.
6.2.Topologie en toile (Mesh Network) :
La topologie en toile est un système multi-saut. La communication entre les nœuds et la
station de base est possible. Chaque nœud a plusieurs chemins pour envoyer des données. Cette
topologie a plus de possibilités de passer à l’échelle du réseau, avec redondance et tolérance aux
fautes, mais elle demande une consommation d’énergie plus importante.
6.3.Topologie hybride :
La topologie hybride est un mélange des deux topologies ci-dessus. Les stations de base
forment une topologie en toile et les nœuds autour d’elles sont en topologie étoile. Elle assure la
minimisation d’énergie dans les réseaux de capteurs.
7. Domaines d’application des RCSFs
7.1. Applications militaires: Déploiement sur un endroit stratégique ou difficile
d’accès, afin de surveiller toutes les activités des forces ennemies ou d’analyser le
terrain avant d’y envoyer des troupes (par la détection d’agents chimiques,
biologiques ou de radiations, par exemple) [11].
11
7.2. Applications liées à la sécurité : La détection des altérations dans la
structure d’un bâtiment, suite à un séisme ou au vieillissement, par des capteurs
intégrés dans les murs ou dans le béton [12].
7.3. Applications environnementales : Détections des fuites de produits
toxiques et alertes des utilisateurs dans un délai suffisamment court pour
permettre une intervention efficace [12].
7.4. Applications médicales : Surveillance permanente des patients et une
possibilité de collecter des informations physiologiques de meilleure qualité,
facilitant ainsi le diagnostic de maladies grâce à des micro-capteurs qui
pourront être ingérés ou implantés sous la peau [14].
7.5. Applications écologiques : L’intégration de plusieurs micro-capteurs dans
le système de climatisation et de chauffage des immeubles permet de réduire la
demande mondiale en énergie [12].
7.6. Applications de traçabilité et de localisation : Localisation des victimes
enterrées sous la neige en équipant les personnes susceptibles de se trouver
dans des zones à risque par des capteurs [14].
8. Caractéristiques et contraintes des RCSFs
La conception et la réalisation des réseaux de capteurs sans fil sont influencées par plusieurs
paramètres. Ces facteurs servent comme directives pour le développement des algorithmes et
protocoles utilisés dans les RCSFs [13].
8.1. Durée de vie du réseau :
C’est l’intervalle de temps qui sépare l’instant de déploiement du réseau de l’instant où
l'énergie du premier nœud s'épuise. Selon l’application, la durée de vie exigée pour un réseau
peut varier entre quelques heures et plusieurs années.
8.2.Ressources limitées :
En plus de l’énergie, les nœuds capteurs ont aussi une capacité de traitement et de
mémoire limitée. En effet, les industriels veulent mettre en œuvre des capteurs simples, petits et
peu coûteux qui peuvent être achetés en masse.
12
8.3. Bande passante limitée :
Afin de minimiser l’énergie consommée lors de transfert de données entre les nœuds, les
capteurs opèrent à bas débit. Typiquement, le débit utilisé est de quelques dizaines de Kb/s. Un
débit de transmission réduit n’est pas handicapant pour un réseau de capteurs où les fréquences
de transmission ne sont pas importantes.
8.4. Facteur d’échelle :
Le nombre de nœuds déployés pour une application peut atteindre des milliers. Dans ce
cas, le réseau doit fonctionner avec des densités de capteurs très grandes. Un nombre aussi
important de nœuds engendre beaucoup de transmissions inter nodales et nécessite que la station
de base soit équipée de mémoire suffisante pour stocker les informations reçues.
8.5. Topologie dynamique :
La topologie des réseaux de capteurs peut changer au cours du temps pour les raisons
suivantes :
Les nœuds capteurs peuvent être déployés dans des environnements hostiles (champ de
batail par exemple), la défaillance d’un nœud capteur est, donc très probable.
Un nœud capteur peut devenir non opérationnel à cause de l’expiration de son énergie.
Dans certaines applications, les nœuds capteurs et les stations de base sont mobiles.
8.6. Agrégation de données :
Dans les réseaux de capteurs, les données produites par les nœuds capteurs voisins sont
très corrélées spatialement et temporellement. Ceci peut engendrer la réception par la station de
base d’informations redondantes. Réduire la quantité d’informations redondantes transmises par
les capteurs permet de réduire la consommation d’énergie dans le réseau et ainsi d’améliorer sa
durée de vie. L’une des techniques utilisée pour réduire la transmission d’informations
redondantes est l’agrégation des données. Avec cette technique, les nœuds intermédiaires
agrègent l’information reçue de plusieurs sources. Cette technique est connue aussi sous le nom
de fusion de données.
9. Conclusion
Dans ce chapitre, nous avons présenté quelques généralités que nous suggérons utiles
pour bien comprendre les protocoles de routages dans les réseaux de capteurs sans fil. Nous
avons défini et décrit brièvement ce qu’est un réseau de capteur sans fil, son architecture de
communication, ses différentes topologies. Nous avons décrit le capteur, ses fonctionnalités et
ses différents composants. Puis nous avons abordé un peu les trames, et enfin nous avons cité les
13
quelques domaines d’applications des réseaux de capteurs sans fil, leurs caractéristiques et leurs
contraintes.
Dans le chapitre qui suit, nous allons mettre d’abord l’accent sur le routage et la
structuration virtuelle d’un réseau de capteur sans fils. La classification des protocoles de routage
sera aussi décrite, puis nous allons présenter quelques protocoles de routage plats et
hiérarchiques et nous finirons par une comparaison entre les différents protocoles abordés.
14
Chapitre 2
Les protocoles de routage dans les RCSFs
1. Introduction
Le routage est une méthode d’acheminement des informations vers une destination
donnée dans un réseau. Il est fondamental dans les réseaux de capteurs sans fil, vu qu’il n’existe
pas d’infrastructure qui gère les informations échangées entre les différents nœuds du réseau. En
effet, c’est à chaque nœud du réseau de jouer le rôle d’un routeur. Ainsi, tous les nœuds se
collaborent afin de router une information vers une certaine destination [2].
2. Contraintes de conception des protocoles de routage pour RCSF
Toute conception de protocole de routage implique l’étude des problèmes suivants [5]:
Minimiser la charge du réseau en optimisant le nombre d’envois et de réceptions des
paquets. Cette minimisation aboutit à une consommation énergétique minimale et une
longue durée de vie du réseau.
Offrir un support pour pouvoir effectuer des communications multi-sauts fiables.
Assurer un routage optimal si possible.
Offrir une bonne qualité concernant les temps de latence.
Auto-organiser le réseau ; ceci peut être nécessaire dans plusieurs cas : Un réseau
comportant un grand nombre de nœuds placés dans des endroits hostiles où la
configuration manuelle n’est pas faisable doit être capable de s’auto-organiser. Un autre
cas est celui où un nœud est inséré ou retiré (à cause d’un manque d’énergie ou destruction
physique).
3. Classification des protocoles de routages des RCSFs
En général, le routage dans les réseaux de capteurs peut être classé en deux types, selon la
structure du réseau [2] :
Le routage à plat (non hiérarchique) : dans ce type de routage, tous les nœuds ont
typiquement les mêmes rôles et fonctionnalités.
15
Le routage hiérarchique : il est réalisé à plusieurs niveaux dans le sens où la vision du
réseau est réduite en une vision locale dans chaque nœud. Certains nœuds peuvent jouer des
rôles particuliers dans le réseau afin de router les informations. les nœuds qui disposent d’une
ressource énergétique importante peuvent être utilisés pour traiter et envoyer les informations
tandis que les nœuds d’énergie basse peuvent être utilisés pour exécuter la capture
d’information dans la proximité de la cible. Ceci a pour résultat une prolongation de la vie du
réseau en entier.
4. Les protocoles de routage à plat
4.1. GSR (Global State Routing)
Le protocole GSR [2] utilise les idées du routage basées sur l’état des liens (Link State,
LS), et les améliore en évitant le mécanisme inefficace d’inondation des messages de routage.
Dans ce protocole, chaque nœud ni maintient : une liste de voisins Vi, une table de
topologie TTi, une table des nœuds suivants NEXTi (Next Hop), et une table de distance
Table_Di. La table de la topologie TTi, contient pour chaque destination, l’information de l’état
des liens telle qu’elle a été envoyée par la destination, et une estampille de l’information. Pour
chaque nœud destination j, la table NEXTi contient le nœud vers lequel les paquets destinés à j
seront envoyés. La table de distance contient la plus courte distance pour chaque nœud
destination.
Les messages de routage sont générés suivant les changements d’états des liens. Lors de
la réception d’un message de routage, le nœud met à jour sa table de topologie (représentée par
un graphe dans LS) et cela dans le cas où le numéro de séquence du message reçu est supérieur à
la valeur du numéro de séquence sauvegardé dans la table. Par la suite, le nœud reconstruit sa
table de routage et diffuse les mises à jour à ses voisins. Le calcul des chemins peut se faire avec
n’importe quel algorithme de recherche des plus courts chemins.
La principale modification de GSR sur l’algorithme LS traditionnel, est la façon de
diffusion des informations de routage qui circulent dans le réseau. Dans LS, si on détecte des
changements de topologie, les paquets d’états de liens sont générés et diffusés par inondation
dans tout le réseau. Par contre, GSR maintient la table - la plus récente - d’état des liens reçus à
travers les voisins, et l’échange uniquement avec ses voisins locaux, d’une façon périodique.
4.2. Le protocole MCFA (Minimum Cost Fordwarding Algorithm)
16
Le protocole MCFA [6] exploite le fait que la direction du routage est toujours connue
i.e. vers une station de base fixe. Dans cet algorithme, chaque nœud maintient le coût minimal
estimé de ce dernier vers la station de base afin de choisir dans le routage le chemin ayant le coût
minimal. Le protocole MCFA repose sur trois principaux buts :
L'optimalité: en acheminant les données sur des chemins à coût minimum.
La simplicité: faible consommation en mémoire, et absence d’identification de nœuds.
La scalabilité: le protocole peut être utilisé pour un grand nombre de nœuds grâce à sa
simplicité. La phase de construction des routes ne consomme qu'un message par capteur. Le
protocole MCFA se déroule en deux phases :
A. Calcul des coûts
Une solution simple pour la détermination des valeurs locales des coûts est d'utiliser
l'inondation. Initialement, le puits émet un message ADV(Advertisement) contenant un coût nul.
Tous les autres nœuds initialisent leur coût à une valeur infinie. Lorsqu'un nœud reçoit un
message ADV, il vérifie si la valeur reçue additionnée au coût du lien est plus petite que la
valeur locale. Dans ce cas, le nœud met à jour sa valeur locale et émet un nouveau message
ADV. Dans le cas contraire l’ADV sera rejeté.
Pour prendre en compte les contraintes d'énergie des capteurs, MCFA utilise une
méthode qui consomme moins de messages de contrôle. En effet, le problème de l'inondation est
la prise de décision en tenant en compte seulement des optimums locaux. Ce qui engendre
plusieurs émissions des messages ADV par le même nœud. Pour éviter cela, MCFA utilise un
mécanisme de backoff. Ce dernier permet de retarder la prise de décision sur la valeur locale du
coût, en attendant la valeur optimale globale. L'intervalle du backoff dépend du coût du lien de
réception : plus le coût est grand, plus on a de chance de recevoir une valeur plus optimale, donc
on doit attendre plus de temps.
B. Relais des paquets
Le relais dans MCFA n'utilise ni l’identification des nœuds, ni la table de routage.
Lorsqu'un paquet est émis par une source vers le puits, il contient le coût minimal local du nœud.
A la réception d'un paquet de donnée, le nœud vérifie si son coût local est égal au coût reçu
moins le coût du lien de réception. Dans ce cas, le nœud relaie le paquet en remplaçant la valeur
du coût par sa valeur locale.
17
4.3. SPIN (Sensor Protocol for Information via Negotiation)
Le protocole SPIN [3] permet de disséminer des informations sur le réseau de manière
ciblée. Le fonctionnement du protocole SPIN permet de réduire la charge du réseau par rapport
aux méthodes de diffusion traditionnelles telles que l’inondation ou l’algorithme de Gossiping
(Technique de dissémination d’information dans laquelle chaque nœud qui reçoit un paquet à
relayer, envoie le paquet reçu à un de ses voisins tiré aléatoirement).
Figure 3: Fonctionnement du protocole SPIN [4]
Le protocole SPIN utilise essentiellement trois types de paquets ADV/REQ/DATA. Un
nœud voulant émettre une donnée commence par envoyer un paquet ADV. Ce paquet ADV
consiste d’une méta-donnée sur les données à émettre. Les méta-données peuvent décrire
plusieurs aspects comme le type des données et la localisation de son origine. Les nœuds qui
reçoivent ce paquet vérifient si les données les intéressent. Si oui, ils répondent par un paquet
REQ. Le nœud qui a initié la communication envoie alors un paquet DATA pour chaque réponse
REQ reçue (voir la Figure 3). Un nœud peut parfaitement ne pas répondre aux messages ADV,
dans le but d’économiser son énergie.
4.4. Le protocol EAR (Eavesdrop And Register)
Une solution hybride pour la tolérance aux pannes est proposée dans le protocole
EAR[14]. Pour son concept préventif, EAR offre une meilleure conservation d'énergie et définit
plusieurs chemins de routage afin de garantir une fiabilité du transport et d'augmenter la durée de
vie du réseau. En outre, un mécanisme de recouvrement de pannes est implémenté. Le protocole
EAR supporte des réseaux de capteurs à collecteurs multiples (plusieurs nœuds puits). Chaque
nœud capteur génère un paquet RPT (Report) contenant des informations pour les intérêts et
préférences de l'utilisateur. Les paquets RPT peuvent être envoyés vers n'importe quel collecteur.
18
Cependant, pour chaque nœud intermédiaire le protocole de routage choisit le meilleur
chemin qui réduit la consommation d'énergie et la latence. Cette phase permet la construction de
l'arbre de routage contenant tous les chemins possibles pour la dissémination des données.
Chaque collecteur diffuse un message ADV (Advertisement) demandant des paquets RPT. Seuls
les nœuds voisins du collecteur reçoivent le message ADV puis enregistrent le chemin dans leur
table de routage ; sans propager le message ADV vers les autres nœuds, comme le montrent les
étapes a et b de la figure suivante. Les autres nœuds capteurs envoient une demande RREQ
(Route Request) cherchant un chemin vers le collecteur (étape c). Si un nœud, ayant déjà une
route stockée dans sa table, reçoit RREQ, il envoie un paquet RREP (Route Reply) à son nœud
voisin concerné par la demande (étapes d ; e). Le processus d'initialisation se termine quand
chaque nœud reçoit une réponse RREP suite à sa requête RREQ ; puis enregistre le chemin dans
sa table de routage.
Figure 4: Fonctionnement du protocole EAR
4.5. Directed Diffusion (DD)
Directed Diffusion [5] est un protocole de propagation de données, permettant d'utiliser
plusieurs chemins pour le routage d'information. Le puits diffuse un intérêt sous forme de
requête, afin d'interroger le réseau sur une donnée particulière. DD repose sur quatre éléments :
A. Nomination des données : L'adressage dans DD utilise un schéma attribut-valeur afin de
décrire les intérêts et les rapports de données.
B. Propagation des intérêts et établissement des gradients : Lorsqu'un puits requiert une donnée
du réseau, il propage un intérêt, contenant sa description ainsi que le débit d'information
19
désiré. Initialement, le puits spécifie un grand intervalle, dans un but d'exploration. Cela
permet d'établir les gradients (vecteurs représentant des intérêts) et de découvrir d'éventuelles
sources, sans pour autant encombrer le réseau.
Figure 5: Propagation des intérêts et établissement des gradients.
Propagation des intérêts : Afin de propager l'intérêt, DD emploie l'inondation globale du
réseau. Chaque nœud maintient localement un cache d'intérêt contenant les informations
suivantes:
La description de l'intérêt, en utilisant le schéma de nomination.
Un ensemble de gradients.
Etablissement des gradients : Lorsqu'un nœud reçoit un intérêt, il parcourt son cache :
Si le cache ne contient aucune entrée relative à l'intérêt reçu, une nouvelle entrée est
créée avec un gradient vers le voisin émetteur.
Dans le cas contraire, le nœud recherche un gradient vers le voisin émetteur, et met à
jour en conséquence l'entrée en question.
Après le traitement du cache, le nœud relaie l'intérêt vers ses voisins. La méthode la plus simple
est d'utiliser l'inondation.
C. Propagation des données :
Lorsque l'intérêt atteint les sources ciblées, les capteurs commencent la récolte
d'information. Pour un intérêt donné, un capteur calcule le débit le plus élevé et prélève les
données en conséquence. En consultant les gradients relatifs à l'intérêt, le nœud détermine les
prochains sauts vers les puits (chacun avec son propre débit).
Lorsqu'un nœud reçoit une donnée, il recherche un intérêt équivalent dans son cache. Si
aucune entrée n'est trouvée, le paquet est supprimé. Dans le cas contraire, en consultant la liste
des gradients, le nœud relaie la donnée vers ses voisins, suivant le débit de chacun d'eux.
20
D. Renforcement des chemins : on distingue deux types de renforcement :
Renforcement positif :
Lorsque le puits reçoit les premières données, il renforce le chemin vers le voisin
émetteur, en augmentant le débit de captage. Cela permet de clôturer la phase d'exploration, et
d'entamer la phase de récolte d'information. Le renforcement ne doit pas s'arrêter au niveau des
voisins du puits, mais doit se propager éventuellement jusqu'aux sources. Pour ce faire, lorsqu'un
nœud reçoit un message de renforcement, il consulte son cache d'intérêt. Si le débit spécifié dans
le message est plus grand que tous les autres débits des gradients présents, le nœud doit renforcer
un de ses voisins. Le voisin est choisi en utilisant le cache de données.
Figure 6: Renforcement des chemins.
Renforcement négatif :
Dans le cas de panne d'un lien (perte de paquet, débit réduit, etc.) le puits peut envoyer un
renforcement négatif sur le chemin en panne en spécifiant le débit de base (exploratoire), et en
procédant à un renforcement positif d'un chemin alternatif.
4.6. Rumour Routing (RR)
Le protocole Rumour Routing [5] essaie de trouver un compromis entre l'inondation des
intérêts et la propagation des données.
Des simulations basées sur la méthode de Monte-Carlo ont montré que la probabilité que
deux lignes se croisent au sein d'une région rectangulaire est 0.69.
Par conséquent, si on considère le puits et la source comme deux points, et en établissant
un nombre réduit de mi-chemins depuis la source et le puits, on aura une forte chance que deux
mi-chemins se joignent, créant ainsi un chemin complet entre la source et la destination, tout en
évitant l'inondation. La création de ces michemins se base sur la notion d'agent. Ce dernier est un
paquet avec une grande portée (TTL) qui traverse le réseau de nœud en nœud afin d'établir des
tables de relais. Il existe deux types d'agents :
21
A. Agents d'évènements :
Chaque nœud maintient une table de relais locale, qui contient, pour chaque intérêt, le
prochain saut vers le puits et vers la source, ainsi qu'une métrique qui représente le nombre de
saut vers chaque extrémité. Lorsqu'un nœud observe un nouvel évènement, il crée un nouvel
agent suivant une certaine probabilité. L'agent contient la table d'évènements parcourus au sein
du chemin ainsi que le nombre de sauts vers la source de chaque évènement. De plus, l'agent doit
transporter avec lui la liste des nœuds parcourus ainsi que leurs voisins directs. La source choisit
un voisin aléatoire et lui émet l'agent. Lorsqu'un nœud reçoit un agent, il effectue les opérations
suivantes :
Si l'agent contient un nouvel évènement, une nouvelle entrée dans la table locale est créée.
Le nœud met à jour sa table locale et/ou la table de l'agent pour les entrées communes,
suivant le nombre de sauts optimal : i.e. si l'agent possède une route plus courte vers un
certain évènement, le nœud met à jour sa table, et vice-versa. Cette méthode permet
d'optimiser des routes déjà établies par d'autres agents.
Si le nœud connaît des évènements non connus par l'agent, il ajoute les entrées
nécessaires dans la table de l'agent.
Le nœud choisit comme prochain saut un de ses voisins n'appartenant pas à la liste des
nœuds de l'agent, et modifie en conséquence sa table locale pour le prochain saut vers le
puits (i.e. le nœud choisi représente le prochain vers le puits).
Le nœud ajoute à la liste des nœuds parcourus son identificateur, ainsi que ceux de ses
voisins.
Le message est envoyé au nœud choisi.
Figure 7: Agents d'événements.
22
B. Agents de requêtes :
Lorsque le puits désire prélever une donnée du réseau, il consulte sa table locale pour une
route fraîche. Si aucune entrée n'est trouvée, il initialise un agent de requête. L'agent contient
seulement la liste des nœuds visités. Lorsqu'un nœud reçoit un agent de requête, il vérifie
l'existence d'un chemin dans sa table locale. Si ce n'est pas le cas, il choisit un voisin aléatoire et
lui transmet l'agent, tout en ajoutant son identificateur dans la liste transportée par l'agent.
5. Les protocoles de routage hiérarchiques
5.1. LEACH (Low Energy Adaptive Clustering Hierarchy)
Heinzelman et al.[2] ont proposé un algorithme de clustering distribué appelé LEACH
pour le routage dans les réseaux de capteurs homogènes. LEACH choisit aléatoirement les
nœuds cluster-heads et attribue ce rôle aux différents nœuds selon la politique de gestion Round-
Robin (c’est-à-dire tourniquet) pour garantir une dissipation équitable d’énergie entre les nœuds.
Dans le but de réduire la quantité d’informations transmises à la station de base, les cluster-heads
agrègent les données capturées par les nœuds membres qui appartiennent à leur propre cluster, et
envoient un paquet agrégé à la station de base.
LEACH est exécuté en deux phases : la phase « set-up » et la phase « steady-state »
suivant la Figure 3. Dans la première phase, les cluster heads sont sélectionnés et les clusters
sont formés, et dans la seconde phase, le transfert de données vers la station de base aura lieu.
Durant la première phase, le processus d’élection des cluster heads est déclenché pour choisir les
futurs cluster heads. Ainsi, une fraction prédéterminée de nœuds s’élisent comme cluster heads
selon le schéma d’exécution suivant : durant une période T, un nœud n choisit un nombre
aléatoire nb dont la valeur est comprise entre 0 et 1 (0 < nb < 1). Si nb est inférieure à une valeur
seuil alors le nœud n deviendra cluster head durant la période courante, sinon le nœud n devrait
rejoindre le cluster head le plus proche dans son voisinage.
Figure 8 : Formation de clusters dans LEACH
23
Les cluster heads formés dans LEACH sont groupés et organisés en une hiérarchie. La
consommation énergétique diminue lorsque le nombre de niveaux de l’hiérarchie augmente.
Avantages du protocole LEACH: Il augmente la durée de vie du réseau de capteurs
sans fils.
Inconvénients du protocole LEACH: LEACH suppose que tous les nœuds puissent
transmettre des données avec une grande puissance pour atteindre la station de base et que
chaque nœud a une puissance de calcul lui permettant de supporter différentes couches MAC.
Par conséquent, LEACH ne convient pas aux réseaux déployés dans de vastes régions. En outre,
LEACH choisit aléatoirement la liste des cluster heads et il ne pose aucune contrainte sur leur
distribution ainsi que sur leur niveau d’énergie. Ainsi, les cluster heads peuvent se concentrer
dans un même endroit et par conséquent, il pourrait exister des nœuds isolés (sans cluster head)
pouvant se déclarer. D’autre part, dans LEACH, l’agrégation des données est centralisée et est
exécutée périodiquement. Or, dans certains cas, la transmission périodique des données pourrait
ne pas être nécessaire, ce qui épuise rapidement l’énergie limitée des capteurs.
5.2. PEGASIS (Power-Efficient Gathering in Sensor Information Systems)
Lindsey et Raghavendra [2], ont proposé une version améliorée de LEACH appelée
PEGASIS. L’idée principale de PEGASIS est de former une chaîne entre les nœuds de sorte que
chaque nœud reçoive de et communique à un voisin proche. Les données collectées sont
transmises d’un nœud à un autre qui les agrège jusqu’à ce qu’elles arrivent à un nœud particulier
qui les transmet à la station de base. Les nœuds qui transmettent les données à la station de base,
sont choisis tour à tour selon une politique round-robin dans le but de réduire l’énergie moyenne
dépensée par un nœud durant une période (round). Contrairement à LEACH, PEGASIS évite la
formation des clusters et procure à un seul nœud dans la chaîne l’envoi de données à la station de
base.
PEGASIS peut prolonger de deux à trois fois la durée de vie d’un réseau de capteurs
relativement à LEACH en fonction du critère choisi pour évaluer la durée de vie d’un réseau i.e.
quand 1%, 20%, 50% ou 100% des nœuds épuisent leurs batteries. Un tel gain de performance
est réalisé par l’élimination du surcoût causé par le processus de formation de clusters dans
LEACH, et par la réduction du nombre de transmissions et de réceptions en agrégeant de
données. Bien que le surcoût du clustering soit évité, PEGASIS exige toujours un ajustement
dynamique de la topologie puisqu’un nœud devrait connaître le niveau d’énergie de ses voisins
24
avant de relayer ses données. Cependant, un tel ajustement de la topologie pourrait causer un
surcoût important en particulier dans les réseaux les plus utilisés. En outre, PEGASIS suppose
que tout nœud communique directement avec la station de base qui gère la topologie d’une
manière centralisée. Or, cette supposition est loin de la réalité car les capteurs communiquent
généralement en mode multi-sauts pour atteindre la station de base. D’autre part, PEGASIS
suppose que tous les nœuds maintiennent une table contenant les localisations de tous les autres
nœuds dans le réseau. En résumé, PEGASIS est adapté seulement aux capteurs sans fil dont les
nœuds sont immobiles. Son évaluation dans des environnements mobiles pourrait dégrader
considérablement ses performances.
Une variante de PEGASIS appelée Hierarchical PEGASIS a été conçue afin d’améliorer
PEGASIS. Dans cette variante, la chaîne est divisée en groupes de la sorte que chaque nœud
communique avec un seul nœud voisin de niveau plus bas de la hiérarchie. Les transmissions
simultanées en parallèle dans des groupes différents minimisent le délai de transmission.
5.3. TEEN (Threshold-sensitive Energy Efficient sensor Network protocol)
Manjeshwar et Agrawal [2] ont proposé une technique de clustering appelée TEEN pour
les applications critiques où le changement de certains paramètres peut être brusque.
L’architecture du réseau est basée sur un groupement hiérarchique à plusieurs niveaux où les
nœuds les plus proches forment des clusters. Puis ce processus de clustering passe au deuxième
niveau jusqu’à ce que la station de base soit atteinte. Après la formation des clusters, chaque
cluster-head transmet à ses membres deux seuils : un seuil Hard HT (hard threshold), qui est la
valeur seuil du paramètre contrôlé (surveillé) et un seuil Soft ST (soft threshold) représentant une
petite variation de la valeur du paramètre contrôlé. L’occurrence de cette petite variation ST
permet au nœud qui la détecte de la signaler à la station de base en transmettant un message
d’alerte. Par conséquent, le seuil Soft réduira le nombre de transmissions puisqu’il ne permet pas
la transmission s’il y a peu ou pas de variation de la valeur du paramètre contrôlé.
Au début, les nœuds écoutent le médium continuellement et lorsque la valeur captée du
paramètre contrôlé dépasse le seuil Hard, le nœud transmet l’information. La valeur captée est
stockée dans une variable interne appelée SV. Puis, les nœuds ne transmettront des données que
si la valeur courante du paramètre contrôlé est supérieure au seuil hard HT ou diffère du SV
d’une quantité égale ou plus grande que la valeur du seuil Soft ST.
25
Avantages du protocole TEEN : Puisque la transmission d’un message consomme plus
d’énergie que la détection des données, alors la consommation d’énergie dans TEEN est
moins importante que dans les protocoles proactifs ou ceux qui transmettent des données
périodiquement tels que LEACH.
Inconvénients du protocole TEEN : l’inconvénient principal de ce protocole est que, si
les seuils HT et ST ne sont pas reçus, les nœuds ne communiqueront jamais, et aucune
donnée ne sera transmise à l’utilisateur, ainsi la station de base ne connaît pas les nœuds qui
ont épuisé leur énergie. TEEN ne convient pas aux applications qui nécessitent des envois
périodiques de données.
5.4. APTEEN (Adaptive Threshold-sensitive Energy Efficient sensor
Network protocol)
APTEEN est proposé pour remédier aux limitations du protocole TEEN, c’est un
protocole hybride qui change la périodicité et les valeurs seuils utilisées dans TEEN selon les
besoins de l’utilisateur et le type d’application. Dans APTEEN, les cluster-heads transmettent à
leurs membres les paramètres suivants :
L’ensemble de paramètres physiques auxquels l’utilisateur est intéressé pour obtenir des
informations (A),
Les seuils : seuil Hard HT et seuil Soft ST,
Un Schedule TDMA permettant d’assigner à chaque nœud un intervalle fini de temps
appelé slot,
Un compteur de temps (CT) : c’est la période de temps maximum entre deux
transmissions successives d’un nœud.
Dans APTEEN, les nœuds surveillent en continu l’environnement. Ainsi, les nœuds qui
détectent une valeur d’un paramètre qui dépasse le seuil HT, transmettent leurs données. Une
fois qu’un nœud détecte une valeur qui dépasse HT, il ne transmet les données au cluster Head à
condition que la valeur de ce paramètre change d’une quantité égale ou supérieure à ST. Si un
nœud ne transmet pas de données pendant une période de temps CT, il devrait faire une capture
de données et les retransmettre.
Avantages du protocole APTEEN : Il offre une grande flexibilité qui permet à
l’utilisateur de choisir l’intervalle de temps CT, et les valeurs seuils HT et ST pour que la
consommation d’énergie soit contrôlée par la variation de ces paramètres.
26
Inconvénients du protocole APTEEN : Il nécessite une complexité supplémentaire
pour implémenter les fonctions de seuils et de périodes de temps CT. Ainsi, le surcoût et
la complexité associés à la formation des clusters à plusieurs niveaux par APTEEN sont
assez élevés.
5.5. VGA (Virtual Grid Architecture routing):
Certains auteurs ont proposé une approche de clustering pour maximiser la durée de vie
dans les réseaux de capteurs dont les nœuds sont immobiles ou se déplacent avec une faible
vitesse. Ils ont utilisé l’approche GPS-free pour construire des clusters fixes, disjoints, et
homogènes en taille avec des formes symétriques. La zone de déploiement des réseaux de
capteurs est divisée en une topologie virtuelle rectiligne contenant des petites zones ayant la
forme d’un carré, et dans chacune, un nœud est choisi comme cluster head. L’agrégation de
données est réalisée à deux niveaux : local et global.
L’agrégation locale est réalisée par l’ensemble des cluster heads appelés aussi Local
Aggregators (LAs), alors que l’agrégation globale est réalisée par un sous ensemble de LAs
appelés Master Aggregators (Mas)
5.6. CTLMN (Clustering Technique for Large multihop Mobile wireless
Networks)
Lin et Chu [2] proposent une technique pour un large réseau Ad hoc. La structure de
cluster est contrôlée par la distance égale au nombre de sauts. Cette technique repose sur la
manière dont les nœuds sont regroupés dans un cluster en utilisant le nombre maximum de sauts
R qui indique le rayon du cluster.
Chaque nœud contient les informations (i, Ci, di, ni) dites informations de cluster qui sont
respectivement : l’ID de nœud, l’ID de son cluster, le nombre de sauts à partir de CH, l’ID du
prochain nœud sur le chemin de cluster.
Le maintien du cluster se fait comme suit : lorsqu’un nœud se déplace au-delà de R, il
quitte son cluster et peut rejoindre un autre cluster s’il se retrouve à une distance égale à R sauts
du CH (du nouveau cluster). Si la distance entre deux CHs est inférieure ou égale à un nombre
prédéterminé de sauts D (Distance de cluster écartant), le CH qui a le plus grand ID est écarté, et
les nœuds dans le cluster écarté cherchent un autre cluster pour le rejoindre.
5.7. HEED (Hybrid, Eenergy-Efficient, Distributed approach)
27
Younes et Fahmy[5] ont proposé un algorithme de clustering distribué appelé HEED pour
les réseaux de capteurs. HEED ne fait aucune restriction sur la distribution et la densité des
nœuds. Il ne dépend pas de la topologie du réseau ni de sa taille mais il suppose que les capteurs
ont la possibilité de modifier leur puissance de transmission. HEED sélectionne les cluster-heads
selon un critère hybride regroupant l’énergie restante des nœuds et un second paramètre tel que
le degré des nœuds. Il vise à réaliser une distribution uniforme des cluster heads dans le réseau et
à générer des clusters équilibrés en taille. Son problème réside dans la détermination du nombre
optimal de clusters. De plus, HEED ne précise pas de protocole particulier à utiliser pour la
communication entre les cluster heads et le sink. A l’intérieur du cluster, le problème ne se pose
pas car la communication entre les membres du cluster et le cluster head est directe (à un saut).
D’autre part, avec HEED, la topologie en clusters ne réalise pas de consommation minimale
d’énergie dans les communications intra-cluster et les clusters générés ne sont pas équilibrés en
taille.
5.8. TTDD (Two-Tier Data Dissemination)
Dans le protocole TTDD [2], chaque nœud source crée une grille virtuelle sur le réseau.
Cette grille est par la suite utilisée par le protocole de routage pour acheminer les requêtes et les
données entre la source et le puits mobile.
Dans TTDD, un système de localisation (comme GPS) est utilisé pour que les nœuds
homogènes sachent leurs positions fixes. Une fois un événement est détecté dans le réseau, les
nœuds qui l’entourent traitent le signal de cet événement et un de ces nœuds devient la source et
génère les rapports de données. Ce nœud source crée virtuellement la grille pour le réseau afin de
préciser les nœuds de dissémination responsables de router les données vers le puits.
6. Conclusion
Nous avons décrit dans les sections précédentes quelques protocoles de routage non
hiérarchique et hiérarchiques dans les réseaux de capteur sans fil.
Dans les protocoles non hiérarchiques (plats), Lorsque le réseau visé est plus étendu, la
gestion des communications devient plus difficile. Chaque nœud doit stocker plus d’informations
concernant le réseau et ses voisins. Les exigences en taille des réseaux de capteurs, dues aux
déploiements généralement étendus, rendent le stockage des informations de topologie très
coûteux par rapport aux ressources disponibles dans ces dispositifs. De même, le surcoût dû aux
échanges additionnels de paquets de communications entre les nœuds devient plus important [2].
28
Ce qui constitue un objectif de minimisation dans le protocole MCFA, que nous allons
implémenter dans le chapitre suivant.
29
Chapitre 3
Implémentation du protocole MCFA
1. Introduction
La séparation entre système d’exploitation et applications dans le calcul conventionnel est
moins flagrant dans le monde des systèmes embarqués, où les applications utilisent
nécessairement du matériel particulier [2]. Pour le développement de notre application, nous
avons utilisé le langage NesC et le système d’exploitation TinyOS.
2. Les outils de simulation et d’implémentation
2.1. Définitions :
TinyOS est un système d’exploitation open source conçu pour des réseaux de capteurs
sans-fil. Il respecte une architecture basée sur une association de composants, réduisant la taille
du code nécessaire à sa mise en place. Cela s’inscrit dans le respect des contraintes de
mémoires qu’observent les réseaux de capteurs [15].Ses librairies, et ses applications sont
écrites en NesC, un nouveau langage pour le développement d'applications orientées
composants.
Le langage NesC est principalement dédié aux systèmes embarqués comme les réseaux
de capteurs sans fils. Il utilise l'extension ".nc" pour tous les fichiers sources : interfaces,
modules, et configurations. Sa syntaxe est proche du langage C, mais il supporte le modèle
concurrent de TinyOS ainsi que des mécanismes pour la structuration, le nommage et
l'assemblage de composants logiciels en des systèmes réseaux embarqués fiables. Son objectif
principal est de permettre aux concepteurs d'applications de construire des composants qui
peuvent être composés rapidement en des systèmes complets, concurrents, tout en permettant
une vérification profonde à la compilation[16].
2.2. Application NesC
Une application NesC consiste en un ou plusieurs composants assemblés pour former un
exécutable. Un composant, du point de vue programmation, est composé de plusieurs sections, il
offre et utilise des interfaces qui sont son unique point d’accès. Il existe deux types de
composants : modules et configurations.
30
Modules : sont des composants qui définissent le code de l’application en implémentant une
ou plusieurs interfaces.
Configurations : sont des composants qui assemblent les composants de l’application ; en
reliant les interfaces utilisées par des composants aux interfaces offertes par d’autres
composants. Les éléments connectés doivent être compatibles : "Interface" à "interface",
"command" à "command", "event" à "event" [16].
2.3. Interface
Elle définie un ensemble de fonctions appelées commandes (qui doivent êtres
implémentées par le composant qui offre cette interface), et un autre ensemble de fonctions
appelées événements (qui doivent êtres implémentées par le composant utilisant cette interface).
Les interfaces sont utilisées pour les opérations qui décrivent des interactions bidirectionnelles.
Pour qu’un composant puisse appeler les commandes d’une interface, il doit implémenter
les événements qui y sont définis. Un même composant pourrait offrir et utiliser et utiliser
plusieurs interfaces différentes ou plusieurs instances d’une même interface [16].
2.4. Modèle de concurrence
TinyOS exécute seulement un programme consistant d'un ensemble de composants requis
par l'application. Il existe deux chemins d'exécution : les tâches, et les "handlers" d'événements
matériels [16].
Les tâches : sont des fonctions dont l'exécution est différée. Une fois lancée, une tâche
s'exécute jusqu'à sa fin et ne peut pas interrompre une autre tâche.
Les "handlers" d'événements matériels : sont exécutés en réponse à des interruptions
matérielles (pression d’un bouton, changement d’état d’une entrée, …) [16], et ils
permettent de faire le lien entre ces dernières et les couches logicielles que constituent les
tâches. Ils sont prioritaires par rapport aux tâches et peuvent interrompre la tâche en cours
d’exécution ou un autre "handler"[15].
2.5. Outil d’intégration : Tossim
Tossim est un simulateur conçu et désigné pour simuler les réseaux de capteurs qui utilise la
plateforme TinyOS. Son but principal est de créer une simulation très proche de ce qui se passe dans ces
réseaux, dans le monde réel. TOSSIM est équipé aussi d’un simulateur graphique TinyViz. Ce dernier est
une application graphique qui permet d’afficher un aperçu de notre réseau de capteurs à tout instant,
ainsi que des divers messages qu'ils émettent [16].
31
3. Organigramme de MCFA
Figure 9 : Organigramme MCFA pour l’établissement des coûts de transmission.
Initialisation de la valeur
locale à une valeur infinie
Réception des ADV à
partir de puits et des autres nœuds
ADV stockés
pendant le temps de back -off
ADV rejeté
Valeur reçue+ Coût de lien
< Valeur locale
La valeur minimale
des ADV = la valeur optimale
globale
Comparer des
Valeurs ADVs
Mise à jour de la
valeur locale par la valeur
optimale globale
Emission d’un
nouveau ADV
Les autres
ADV sont rejetés
Non Oui
32
4. Résultats de la simulation
Le déploiement d’un réseau de capteurs nécessite une phase de tests avant sa mise en
place afin de s’assurer le bon fonctionnement du réseau. L’expérimentation réelle s’avère
quelques fois très coûteuse. Cependant, il existe une solution moins coûteuse, qui consiste à la
simulation à évènements discrets.
La simulation des réseaux de capteurs consiste principalement en la reproduction du
comportement des nœuds capteurs et des interactions entre eux. C’est une étape incontournable
pour l’évaluation des modèles d’application ou des protocoles de communication. De plus, la
simulation offre un gain considérable en temps, une flexibilité en permettant la variation des
paramètres et une meilleure visualisation des résultats.
Figure 10 : La simulation sous TinyViz
33
On peut voir dans la partie gauche tous les capteurs qui sont déplaçable dans l'espace. La
partie du haut rassemble toutes les commandes permettant d'intervenir sur la simulation.
On/off: met en marche ou éteint un capteur.
Delay: permet de sélectionner la durée au bout de laquelle se déclenche le Timer.
Play : permet de lancer la simulation où de la mettre en pause.
Les grilles affichent un quadrillage sur la zone des capteurs afin de pouvoir les situer
dans l'espace.
Clear : efface tout les messages qui avaient été affichés lors de la simulation
Le bouton de fermeture arrête la simulation et ferme la fenêtre.
Chaque onglet contient un plugin qui permet de visualiser la simulation de façon plus ou
moins détaillée.
En activant le plugin « debug messages », tout les messages de type debug apparaitront
dans l'onglet correspondant.
Le « plugin radio links » permet de visualiser graphiquement par des flèches, les
échanges effectués entre deux capteurs (unicast) ainsi que les messages émis par un
capteur à l'ensemble du réseau (broadcast).
La partie droite montre la structure des trames lors de l’envoie d’un message. La trame
est constituée des champs suivants:
Addr : C’est l’adresse du destinataire.
Type : Indique le type du protocole utilisé pour transmettre le message.
Group : Désigne le cluster à qui il appartient le nœud qui envoie le message.
Length : Indique la longueur de la trame, c’est le nombre de métrique constituant le
message.
Data : Ce champ est réservé aux informations à émettre.
CRC (Cyclic Redundancy Check) : Méthode de détection d’erreur redondante.
ACK : Permet l’acquittement des trames de donnée.
Time : Désigne le temps lors de l’envoie du message.
34
5. Conclusion
Dans ce chapitre, nous avons présenté brièvement les outils de développement de notre
protocole MCFA, puis son organigramme et nos résultats.
Le but principal de ce protocole est de minimiser le coût d’envoi. De ce fait, il utilise
l’inondation pour déterminer les valeurs locales des coûts de ses nœuds, cependant ça engendre
plusieurs émissions de messages ADV par le même nœud. Pour remédier à ce problème et pour
économiser de l’énergie, MCFA a introduit un nouveau mécanisme appelé « backoff ». Ce
dernier permet de retarder la prise de décision sur la valeur locale du coût, en attendant la valeur
optimale globale.
Problèmes rencontrés
La réalisation de ce projet n’a pas été du tout une tâche aisée, à cause de certains
problèmes qui nous ont empêchés de progresser au rythme avec lequel nous avons commencé.
Parmi ces problèmes on peut citer :
La charge du travail au deuxième semestre a été très élevée, du coup nous avons été
obligés de réaliser ce projet dans un temps très court. Néanmoins, ça nous a permis
d’apprendre à gérer davantage notre temps et de s’organiser devant une charge
importante du travail.
Manque de documentation sur le protocole que nous avons implémenté (MCFA).
D’ailleurs nous avons eu d’énormes difficultés pour trouver des paquets nécessaires pour
le fonctionnement de notre plateforme.
La plupart de la documentation sur les réseaux de capteurs sans fil est en anglais, du
coup on a mit du temps pour les traduire et les comprendre.
Les outils utilisés (TinyOs et le langage NesC) sont nouveaux pour nous, on les a pas
vus pendant notre cursus, du coup il nous fallait d’abord faire une autoformation pour se
familiariser avec TinyOs et NesC.
35
Conclusion générale
Dans ce projet nous avons traité le problème du routage dans les réseaux da capteurs sans
fil. Cet aspect est fondamental pour ce genre de réseau caractérisé par l’absence d’infrastructure.
Le routage se réalise en collaboration entre les différents nœuds du réseau. Un protocole de
routage doit prendre en compte les contraintes matérielles d’un capteur : une batterie faible, une
capacité de stockage modeste, une bande passante faible, un faible coût, etc.
Ce projet nous a permis d’élargir nos connaissances dans le domaine de réseau, en
général, et d’acquérir de nouvelles connaissances théoriques et pratiques dans les réseaux de
capteurs sans fil. En effet, il nous a fait découvert un nouveau système d’exploitation open
source « TinyOs » ainsi que le langage NesC.
La compréhension du fonctionnement des modèles TinyOS ainsi que le développement
sous NesC, nous a permis d’appréhender de manière plus efficace la mise en œuvre d'un RCSF.
En plus de ses avantages techniques, ce projet a été aussi bénéfique pour nous de point de
vu relationnel, organisation et gestion de travail. En effet, malgré les problèmes rencontrés et la
contrainte de temps, nous avons pu comme même réussir notre projet.
36
Bibliographie :
[1] LEHSAINI Mohamed. Diffusion et couverture basées sur le clustering dans les réseaux de
capteurs : application à la domotique. 2009.
[2] kamal BEYDOUN. Conception d’un protocole de routage hiérarchique pour les réseaux de
capteurs. Décembre 2009.Université de FRANCHE-COMPTE.
[3] W. Heinzelman, J. Kulik, and H. Balakrishnan. Adaptive protocols for information
dissemination in wireless sensor networks. 5th annual ACM/IEEE international conference on Mobile
computing and networking . August 1999, pp. 174 - 185.
[4] Kemal Akkaya, Mohamed Younis. « A survey on routing protocols for wireless sensor
networks ». Ad Hoc Networks. May 2005, Vol. 3, 3, pp. 325-349.
[5] Yacine CHALLAL. « Réseaux de capteurs sans fils : Systèmes intelligents pour le
transport ». Version1. Novembre 2008.
[6] Fan Ye, Alvin Chen, Songwu Lu, Lixia Zhang « A Scalable Solution to Minimum Cost
Forwarding in Large Sensor Networks ». Computer communication and networks 2001 p 304-309 Los
Angeles, CA 90095-1596
[7] Delye de Mazieux, V. Gauthier, M.Marot, M. Becker « Etat de l’art sur les réseaux de
capteurs », Rapport de recherche INT N_05001RST, UMR5157 SAMOVAR, Institut National des
Télécommunications, Evry, France.
[8] J. Zheng , L. Myung, « Will IEEE 802.15.4 make ubiquitous networking a reality ? », The
city college of CUNY, IEEE Communications Magazine, juin 2004.
[9] Adrien VAN DEN BOSSCHE, « Proposition d’une nouvelle méthode d’accès déterministe
pour un réseau personnel sans fil à fortes contraintes temporelles » THESE DOCTORAT de
L’UNIVERSITÉ de TOULOUSE II, juillet 2007.
[10] I. Akyildiz, W. Su, E. Cayirci, Y. Sankarasubramaniam. « A survey on sensor
Networks”, IEEE Communications Magazine, vol. 40, no. 8, pp. 102-114, Georgia Institute of
Technology, Atlanta, USA. Août 2002.
[12] K.Rahim « Techniques de conservation d’énergie pour les réseaux de capteurs sans fil ».
Thèse de doctorat. Septembre 2009.Institut National Polytechnique de Toulouse.
[13]M.Sofiane. « la consommation d’énergie dans les réseaux de capteurs sans fil ». Thèse de
recherche. 2007/2008.IFSIC-Rennes1.
[11] http://fr.wikipedia.org/wiki/R%C3%A9seau_de_capteurs_sans_fil.
[14] http://moodle.utc.fr/file.php/498/SupportWeb/co/Module_RCSF_96.html
[15] http://fr.wikipedia.org/wiki/TinyOS
[16] http://moodle.utc.fr/file.php/498/SupportWeb/co/Module_RCSF_81.html
Recommended