Le Routage dans les RCSF

Agrégation de données
Comment économiser l’énergie?

WSN
Pourquoi l’agrégation de données
 Le coût (consommation de l’énergie) de transmission des données est
jusqu’à 70% par rapport au coût général dans un capteur
 Les réseaux de capteurs sont denses, ce qui implique que deux noeuds
voisins peuvent capter la même information

Utilisation de mécanisme d’agrégation

 Remplacer les lectures individuelles par une vue collaborative sur une
zone
 Utilisation de fonctions d’agrégat :
• MAX
• MIN
• MOYENNE
 Moins de messages émis
 Économie d’énergie
3

1
 WSN
l’agrégation de données
 Exemple: sans agrégation => 18 messages

WSN
l’agrégation de données
 Exemple: avec agrégation => 7 messages

WSN
Techniques d’agrégation

2
 WSN
Stratégies de Routage

 Stratégies de Routage:
Power efficiency
 Node T is the source node
that senses the
phenomena.
 PA is the available power
 α is the energy required to
transmit a data packet
through the
related link.

WSN
Stratégies de Routage
 Stratégies de Routage: Power efficiency

WSN
Stratégies de Routage
 Data centric
• Le sink diffuse des requêtes
• Les sensors diffusent les mesures
• Exemple d’attribut:
 Requête (interest) : qui ont la [ Température > 45° ]
 Réponse: seuls les sensors vérifiant cette condition répondent

3
Étude de scénarios applicatifs (1/7)

 2 scénarios précis
• « Mesures sur une zone d’intérêt »
• « Détection et positionnement d’une cible active »

 Évaluation des besoins

• Quantité d’informations échangées
• Puissance de calcul nécessaire
• Quantité de mémoire nécessaire au traitement

10

Étude de scénarios applicatifs

 Exemple de réseau de capteurs : « Mesures sur une
zone d’intérêt

(1,8) (8,8)

(5,6)
Simple répéteur (1,5)
(8,4)
(11,3)
(4,2)
Capteur/Répéteur
(source de données)
Station de base (puits de données) (0,0)

Type de nœuds Identifiants des nœuds = position géographique

11

Étude de scénarios applicatifs

 Application 1 : "Mesures sur une zone d'intérêt"

• La station de base • Le point (7,7) n'est pas à
(0,0) veut connaître portée radio de la station
(7,7) la température en (7,7) de base
(7,7) • La station de base émet
(1,5) "temp(7,7)?"
• Le répéteur (1,5) reçoit la
?(7,7) requête

• (1,5) n'est pas à • Le capteur (5,6) va

proximité de (7,7) participer au calcul de la
• (1,5) ré-émet (8,8) température, car il est près
(7,7) (7,7)
(5,6) "temp(7,7)?" dans la (5,6) de (7,7)
(1,5) "bonne direction", vers • (5,6) fait également
(5,6) participer (8,8) au calcul en
• Le capteur (5,6) lui envoyant la requête
reçoit la requête • (8,8) reçoit la requête

12

4
Étude de scénarios applicatifs

 Application 1 : "Mesures sur une zone d'intérêt"

• (8,8) va participer au • (5,6) calcule la valeur en (7,7)
calcul de la en faisant une moyenne
(8,8) température, car il est pondérée
(7,7) (7,7)
(5,6) près de (7,7) (5,6) • (5,6) génère une réponse et
• (8,8) transmet sa (1,5) l'envoie à (4,2) pour ne pas
valeur locale de épuiser (1,5)
(4,2)
température à (5,6) • (4,2) reçoit la requête
• (5,6) reçoit la valeur
de (8,8)

• (4,2) ré-émet le
résultat à (0,0)
(7,7) • (0,0) reçoit le résultat

(4,2)
(0,0)

13

Étude de scénarios applicatifs

 Application 2 : "Positionnement d'une cible active"

• On cherche à • La cible émet une
Cible connaître la position trame en mode «
instantanée d'une diffusion locale »
cible mobile active • infos : cohérence
temporelle, numéro
de cible, puissance
d'émission

• Les nœuds du • Dans un deuxième

voisinage estiment la temps, les mêmes
distance avec la cible nœuds routent ces
• Ils émettent chacun mêmes infos vers la
une trame en mode station de base
direct vers la cible
• infos : cohérence
temporelle, numéro
de cible, distance,
coordonnées locales

14

Mise en évidence de 5 modes de transmission

 « Multi-sauts (acquitté) »

 « Inondation »

 « Saut unique acquitté »

 « Saut unique non acquitté »  « Diffusion locale »

15

5
 WSN
Stratégies de Routage
 Location awareness

• Localisation absolue (GPS)

 Nécessite d’un module de réception GPS: coûteux

• Localisation relative
 Découverte de voisinage
 Basée sur la puissance des signaux reçus

• Formation des clusters

 Pour l’agrégation de données
 Pour la synchronisation de mise en veille:
• Un sensors (leader) reste toujours actif
• Se charge de l’activation des autre

16

WSN
Le routage dans les RCSF
 Les protocoles de routage au sein des WSN sont influencés par un
facteur déterminant à savoir :
• la minimisation de la consommation d'énergie sans une perte
considérable de l'efficacité.

 Chaque nœud joue le rôle de source et de relais.

 La défaillance énergétique d'un capteur peut changer

significativement la topologie du réseau et imposer une
réorganisation coûteuse de ce dernier.

17

WSN
Le routage dans les RCSF
 La propagation et la délivrance des données dans un RCSF
représentent la fonctionnalité la plus importante du réseau.
 Elle doit prendre en considération toutes les caractéristiques des
capteurs afin d'assurer les meilleures performances du système :
durée de vie, fiabilité, temps de réponse, ... etc.

 Vu la spécificité des RCSF, un nombre important de recherches sont

orientées vers une violation du découpage en couches protocolaires
indépendantes, et introduisent la notion de cross layer optimisation.

 Par exemple, en utilisant des mécanismes d'agrégation, les routeurs

intermédiaires doivent accéder à la donnée afin d'établir des
résumés des lectures de la région

18

6
 WSN
Le routage dans les RCSF
Les méthodes employées par les protocoles de routage peuvent être
classifiées suivant plusieurs critères

Classification des protocoles de routage

19

WSN
Le routage dans les RCSF
Topologie du réseau (organisation des capteurs dans le réseau)
Il existe deux principales topologies dans les protocoles de routage pour
les RCSF.

 Topologie plate : tous les nœuds possèdent le même rôle. Les

nœuds sont semblables en termes de ressources.

 Topologie hiérarchique : afin d'augmenter la scalabilité du

système, les topologies hiérarchiques ont été introduites en divisant
les nœuds en plusieurs niveaux de responsabilité. L'une des
méthodes les plus employées est le clustering, où le réseau est
partitionné en groupes appelés "clusters". Un cluster est constitué
d'un chef (cluster-head) et de ses membres.

20

WSN
Le routage dans les RCSF
Etablissement de la route
Les protocoles de routage peuvent être séparés en trois catégories : les
protocoles proactifs, les protocoles réactifs et les protocoles hybrides.
 Protocole proactif : Ces protocoles de routage essaient de
maintenir les meilleurs chemins existants vers toutes les destinations
possibles au niveau de chaque nœud du réseau. Les protocoles de
routage proactifs maintiennent à jour les tables de routage avant de
commencer la transmission
• Les routes sont sauvegardées mêmes si elles ne sont pas utilisées.
• Chaque nœud du réseau maintient une table de routage pour toutes les
destinations indépendamment de l'utilité des routes.
• Les protocoles proactifs sont adaptés aux applications qui nécessitent
un prélèvement périodique des données.
• Les capteurs peuvent se mettre en veille pendant les périodes
d'inactivité, et n'enclencher leur dispositif de capture qu'à des instants
particuliers.

21

7
 WSN
Le routage dans les RCSF
 Protocole réactif : Ces protocoles (dits aussi, les protocoles de
routage à la demande) créent et maintiennent des routes selon les
besoins.
• Lorsque le réseau a besoin d'une route, une procédure de découverte
de route est lancée.
• Ce type de protocoles est pratique pour des applications temps réel où
les capteurs doivent réagir immédiatement à des changements soudains
des valeurs captées.
• En effet, un prélèvement périodique des données aurait été inadapté
pour ce type de scénarios.
 Protocole hybride : Ces protocoles combinent les deux idées des
protocoles proactifs et réactifs. Ils utilisent un protocole proactif pour
apprendre le proche voisinage (par exemple le voisinage à deux ou à
trois sauts), ainsi, ils disposent de routes immédiatement dans le
voisinage. Au-delà de la zone du voisinage, le protocole hybride fait
appel à un protocole réactif pour chercher des routes.

22

WSN
Le routage dans les RCSF
 Address-Centric
(AC) Routing

Chaque source envoi ses données au sink d’une façon

indépendante
Nombre total de transmission : 3 + 3 + 2 = 8.

 Data-Centric (DC)
Routing

Dans ce cas une arbre d’aggrégation des données est formée. A chaque nœud on
attend que tous ses fils aient envoyé leurs données et on fait l’aggrégation des
données pour l’envoyer au parent.
Nombre total de transmission : 5 (vs. 8 for AC) 23

Exemples des protocoles de routages

WSN
dans les RCSF

Propagation et discussion (flooding and gossiping):

 Dans la propagation, chaque capteur recevant un paquet de
données le renvoi à tous ses voisins.
 Ce processus continue jusqu'à ce que le paquet arrive à destination
ou jusqu’à ce que le nombre maximum de sauts pour le paquet soit
atteint.
 le gossiping est une version légèrement améliorée du flooding où le
nœud récepteur envoi le paquet à un voisin choisi aléatoirement.

1st broadcast 2nd broadcast 3rd broadcast Final state

Flooding 24

8
Exemples des protocoles de routages
WSN
dans les RCSF
Les protocoles à topologie plate
(Exemple : SPIN & Directed Diffusion)
SPIN(Sensor Protocols for Information via Negotiation), (par Heinzelman et al.)
reposant sur un modèle de négociation afin de propager l'information dans un
réseau de capteurs)
Le but de SPIN est de pallier aux problèmes de l'inondation, qui sont :
 L'implosion due à la duplication inutile des réceptions d'un même message.
 Le chevauchement lié au déploiement dense des capteurs. En utilisant
l'inondation, les capteurs d'une zone émettrons tous la même donnée (ou
presque).
 L'ignorance des ressources, car l'inondation ne prend pas en considération
les ressources des nœuds.

25

WSN
Les protocoles à topologie plate
SPIN (Sensor Protocols for Information via Negociation),
Ces trois problèmes affectent grandement la durée de vie et les
performances du réseau. Pour les résoudre, SPIN adopte deux
principes :

 La négociation : pour éviter le problème d'implosion, SPIN précède

l'émission d'une donnée par sa description, en utilisant la notion de
méta-données. Le récepteur aura le choix par la suite d'accepter la
donnée ou non. Ce mécanisme permet aussi de régler le problème
de chevauchement.

 L'adaptation aux ressources : d'une manière continue, les nœuds

contrôlent leur niveau d'énergie. Le protocole SPIN accommode son
exécution suivant l'énergie restante du capteur, et modifie en
conséquence le comportement du nœud.

26

WSN
Les protocoles à topologie plate
Fonctionnement de SPIN
Les communications dans SPIN se font en trois étapes :
 Lorsqu'un nœud veut émettre une donnée, il émet d'abord un message ADV
(ADV: mécanisme de publicité de données) contenant une description de la
donnée en question.
 Un nœud recevant un message ADV, consulte sa base d'intérêt (n’a pas
déjà reçu la donnée). S'il est intéressé par cette information, il émet un
message REQ vers son voisin.
 En recevant un message REQ, l'émetteur transmet à l'intéressé la donnée
sous forme d'un message DATA.
 Lorsque le nœud s'aperçoit que son énergie est descendu sous un certain
seuil, il change son mode de fonctionnement, et ne répond à aucun
message ADV.

27

9
 WSN
Les protocoles à topologie plate
Fonctionnement de SPIN

28

WSN
Directed Diffusion (Diffusion dirigée)

Directed Diffusion (DD) 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. Il se base sur le modèle
publish/subscribe.

 DD repose sur quatre éléments :

1. nomination des données
2. propagation des intérêts et établissement des gradients
3. propagation des données
4. renforcement des chemins.

29

WSN
Directed Diffusion
1- 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.
Exemple : Nomination des données
 Par exemple, dans une application de Type = GetTemperature
Zone = [100, 100, 120, 120]
protection de forêts, une requête Interval = 10 ms
peut être effectuée sous cette forme : Durartion = 1 mn

Une réponse d'un capteur pourra

Type = GetTemperature
être formulée ainsi : Location = (110, 115)
Temperature = 32
Timestamp = [Link]

30

10
 WSN
Directed Diffusion
2-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
&
 le débit d'information désiré.

Initialement, le puits spécifie un grand intervalle, dans un but d'exploration

Cela permet d'établir les gradients et de découvrir d'éventuelles sources,
sans pour autant encombrer le réseau.

31

WSN
Directed Diffusion
Propagation des l'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.

Définition : Gradient
Un gradient est un vecteur représentant l'intérêt. Il est caractérisé par
une direction et une amplitude :
• la direction est modélisée par le voisin émetteur de l'intérêt
• et l'amplitude est représentée par le débit de données.
En plus, chaque entrée contient un champ limitant la durée de validité
du gradient.

32

WSN
Directed Diffusion
Méthode : 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.

33

11
 WSN
Directed Diffusion
3 - 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 noeud
relaie la donnée vers ses voisins, suivant le débit de chacun d'eux.
Remarque : Evitement des boucles
Avant de relayer une donnée à ses voisins, un noeud utilise son cache de
données. Ce cache enregistre les données récemment émises par les voisins.
Cela évite la création de boucles, en supprimant les données déjà rencontrées.
34

WSN
Directed Diffusion
4- Renforcement des chemins
a) 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
35

WSN
Directed Diffusion
b) 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.

36

12