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