Réseaux de capteurs

Claude ChaudetClaude.Chaudet@enst.fr

Claude Chaudet

Applications typiques¢Collecte statistique de données• Chaque élément du réseau envoie périodiquement

un résultat de mesure à un point de collecte

¢Mesure à la demande• Un centre de commande demande la mesure d'une

grandeur à un endroit du réseau• Les capteurs concernés renvoient le résultat de

mesure correspondant

¢Détection d'événement• Lorsqu'un événement survient (la température dépasse

un certain seuil...), chaque capteur concerné envoie une notification à un point de collecte

2

S

S

S

Claude Chaudet

Conséquence sur le trafic réseau

¢Schéma de communication• La plupart du trafic est convergeant

(schéma de communication de n vers 1)• Existence de trafic de 1 vers 1 (demande d'action, rapport d'une mesure,

de l'occurrence d'un événement)- Implique très souvent le point central (source ou destination)

¢Profil de trafic• Trafic périodique (n sources CBR ?)• Trafic unicast éventuellement prioritaire (événement, commande)

¢Contraintes• Bande passante nécessaire : assez faible (fonction de l'étendue du réseau)• Délai borné pour certains messages (différentiation de services ?)

3

Claude Chaudet

Axes R&D

¢Objectifs• Obtenir les informations requises (fréquence, valeur statistique, délai

d'obtention, ...)• Minimiser la consommation ⇒ maximiser la durée de vie du réseau / de

l'application

¢Optimisations "Réseaux"• Communiquer moins, plus efficacement• Routage, couche MAC, etc.

¢Optimisations "systèmes embarqués"• Algorithmique légère (TI MSP430F20xx : 200 µA par MIPS)• Manque de mémoire - traitement de l'information (statistiques)

4

Claude Chaudet

Les réseaux de capteurs sont des réseaux ad hoc

¢Réseaux à commutation de paquets

¢Réseaux sans-fil• Utilisation d'un médium radio, bande des 2,4 GHz• Protocoles d'accès au médium (ex : IEEE 802.15.4) semblables

¢Réseaux multi-sauts• Protocoles de routage nécessaire dans les noeuds• Réseaux auto-organisés : le point de décision central est éloigné de la

plupart des noeuds ≈ pas de point de décision central (éventuellement définition de politiques).

• Problématiques de synchronisation (horloge), etc.

5

Claude Chaudet

Les réseaux de capteurs ne sont pas des réseaux ad hoc...

¢Profil de trafic• Différent a priori, tout tourne autour d'un nombre limité de points centraux

(similaire à clients-serveur ; réseau derrière NAT ?)• Communication souvent uni-directionnelle ou sur invitation

¢Problématique n°1 : la durée de vie du réseau• Prioritaire (mais liée à) sur l'optimisation des performances (débit, etc.)

¢Moindre importance de l'identité des noeuds• Application collaborative• Importance forte de la localisation / datation des données• Modification des paradigmes de sécurité...

6

Claude Chaudet

Durée de vie du réseau

¢Le réseau doit assurer sa tâche aussi longtemps que possible

¢Les transmissions doivent être assez efficaces pour les contraintes des applications• Taux de pertes, délai, débit, etc.

¢Qu’est-ce que la durée de vie du réseau• Maximiser le délai avant que le premier capteur n’épuise sont énergie• Maximiser le délai avant que le dernier capteur n’épuise sont énergie• Maximiser le délai avant que le réseau ne soit déconnecté• Maximiser le délai avant que une zone ne soit plus surveillée• ...

7

Claude Chaudet

Anatomie d’un capteur typique

¢ Microcontroleur de faible puissance• 8 MHz

¢ Mémoire limitée• RAM : 10kB

• Flash : 48 kB + 1MB

¢ Horloge imprécise• Dérive ± 40ppm

¢ Interface radio faible performance• Bande des 2,4 GHz

• Débit max. : 250 kb/s

• Taille max. de trame : 127 Bytes

¢ Énergie consommée par la radio• Émission: 19.5 mA

• Réception: 21.8 mA

• Micro-controleur seul: 1.8 mA

• Capture: 54.5 µA

• Mode veille : 5.1µA

• Lecture flash : 4 mA

• Écriture flash : 20 mA

8

Capteur lumièrer

CapteurTempérature

Capteur Visible + IR

Antenne embarquéeInterface

radio

Micro-controleur

Flash USB Flash

Claude Chaudet

Bestiaire : explorer les spécifications

9

Vitesse µC RAM Flash Tx Radio Rx Radio Veille Lecture Flash Écriture Flash

Moteiv Tmote SkyXBow TelosB 8 MHz 10 kB 48 kB + 1MB 19.5 mA 21.8 mA 5.1 µA 4 mA 20 mA

Intel iMote2 13-416 MHz 256kB 32 MB + 32 MB 44 mA (13 MHz)66 mA (104 MHz)

44 mA (13 MHz)66 mA (104 MHz) 387 µA ? ?

Sun SPOT 400 MHz 1 MB 8 MB 40 mA 40 mA 33 µA ? ?

Autres nœuds capteurs (chiffres inconnus): SensLab (matériel identique Tmote Sky), WiseNET, Berkeley Picomotes, Wavenis Excelyo, ...

¢ Le compromis entre performance et consommation est identique sur tous les modèles• Recevoir une trame coûte toujours beaucoup d’énergie (CAN, extraction signal, ...)• L’écriture en mémoire flash aussi (effacement avant écriture)

Claude Chaudet

Comment réaliser une bonne application capteurs ?

¢Améliorer la durée de vie :• Émettre moins

- Compresser et filtrer les informations- Minimiser le surcoût- Réduire le trafic de contrôle

• Recevoir moins- Préférer les zones de faible densité- Émettre quand les voisins sont en

veille

• Limiter le stockage en flash

¢Composer avec les faibles capacités :• Éviter les traitements complexes

- Cryptographie, calculs complexes dans le réseau

- Au minimum, équilibrer la charge

• Limiter la taille des données manipulées- Tables de routage, cache de

données, ...

10

11

Couche MAC

Claude Chaudet

Limitations des couches inférieures (MAC et PHY)

¢Débit généralement faible• Un débit faible permet d’utiliser une modulation robuste et peu complexe =>

économe en énergie• Possibilité d’Ultra-Wide Band, mais pas dans les bandes libres “basses

fréquences” (868 MHz, 914 MHz, 2.4 GHz) : largeur de bande insuffisante.

• IEEE 802.15.4 : 250 kb/s dans la bande des 2.4 GHz

¢Limitation de la taille de trames• Limitation du fait du faible débit : ne pas occuper le canal trop longtemps

(~5 ms)• Limitation due au taux d’erreur-bit (valeur typique : 10-6)

• IEEE 802.14.5 : limite de la charge utile à 127 octets

12

Claude Chaudet

IEEE 802.15.4 : fonctionnement

¢Processus d'émission d'une trame (IEEE 802.15.4) :• Attente d'un temps aléatoire (backoff)

• Examen de l'état du médium (occupé / libre)

• Transmission de la trame

• [Optionnel] attente d'un temps t_ack

• [Optionnel] réception d'un acquittement

• Attente d'un temps LIFS ou SIFS (fonction de lalongueur de la trame précédente)

13

E

R

Légende : Émission d'une trame Examen du médium Réception d'une trame

Claude Chaudet

Consommation énergétiqueIEEE 802.15.4 sur TI CC2420

¢Examen de l'état du médium• Effectué une seule fois (CSMA/CA non slotté) ⇒ négligeable

¢Émission d'une trame (débit : 250 kb/s)

• ⇒ 992 µs + [ (taille données)/250000 ] µs à 19,5 mA ≈ [ (taille données)/250000 ] . 5,417.10 -12 + 5,373.10 -9 Ah

¢Réception de l'acquittement

• ⇒ 352 µs à 21,8 mA ≈ 2,13.10-9 Ah

14

Contrôle SeqPréamb. SFD PHR addresses charge utile FCS4 o 1 o 1 o 2 o 1 o ≤ 20 o ≤ 127 o 2 o

128 µs 32 µs 32 µs 64 µs 32 µs ≤ 640 µs ≤ 4064 µs 64 µs

Contrôle SeqPréamb. SFD PHR FCS4 o 1 o 1 o 2 o 1 o 2 o

128 µs 32 µs 32 µs 64 µs 32 µs 64 µs

Claude Chaudet

Consommation énergétiqueIEEE 802.15.4 sur TI CC2420

¢Pour une charge utile de longueur L bits :• Consommation par l'émetteur : ( 5,417 . L/250 + 7,5 ).10 -9 Ah• Consommation par le(s) récepteur(s) : ( 6,055 . L/250 + 7,9 ).10 -9 Ah

¢Réserve d'énergie : piles alcalines (2 Ah)

15Taille trame (octets)Taille trame (octets)

Capa

cité

(bits

)

Capa

cité

(nb

tram

es)

5e+07

1e+08

1.5e+08

2e+08

2.5e+08

3e+08

20 40 60 80 100 120

EmissionsReceptions

1e+09

2e+09

3e+09

4e+09

5e+09

6e+09

7e+09

8e+09

9e+09

20 40 60 80 100 120

EmissionsReceptions

Claude Chaudet

Lien entre consommation et densité¢Le coût d'une émission / réception est une fonction affine

du nombre de bits (L) transmis :• CE = αE.L + βE ; CR = αR.L + βR

¢Influences sur les protocoles MAC :• Une trame émise est reçue par tous les voisins (vérification du FCS avant

filtrage adresse MAC - cf. IEEE 802.15.4 - §7.5.6.2).

• Un réseau trop dense coûte très cher en performance (accès aléatoire) et en énergie.

16

1e+06

1e+07

1e+08

5 10 15 20 25 30 35 40 45 50

Emissions

Taille voisinage (clique)

Capa

cité

(nb

tram

es)

Claude Chaudet17

Limiter l’énergie consommée par la couche MAC

¢Idéalement, l’interface ne devrait être active quelors d’émissions ou de réceptions

¢Les solutions classiques engendrent un surcoût:• Stratégies de type CSMA/CA

- Requièrent un examen régulier du médium pour être prêt à recevoir ⇒ écoute inutile.

- Optimisations possibles (Filtrage dès réception de l’adresse) ne fonctionnent qu’une fois que l’en-tête MAC est décodée.

• Synchronisation entre nœuds (rendez-vous)- Imparfaite à cause des dérives d’horloge- Dérive de ±40 ppm => en moyenne 1 seconde toutes les 7 heures ou 1 trame

complète (127 bytes at 250 kb/s) toutes les 101,6 sec.

Claude Chaudet18

Preamble Sampling / Low Power Listening / B-MAC et protocoles apparentés

¢Les techniques de type Preamble sampling [1,2] sont de bons compléments aux approches sur rendez-vous :• L’émetteur envoie continuellement des préambules courts (par ex.

contenant l’adresse de destination, laissant des intervalles pour que ce dernier acquitte)

• Tout récepteur potentiel se réveille occasionnellement, examine le canal, capte un préambule. Le récepteur acquitte, les autres retournent en veille.

• Déporte la consommation de multiples récepteurs vers un seul émetteur

¢ [1] El-Hoiydi et al. — WiseMAC: an ultra low power MAC protocol for the downlink of infrastructure wireless sensor networks — ISCC 2004¢ [2] Polastre et al. — Versatile lowpower media access for wireless sensor network — SenSys 2004

Claude Chaudet19

Couplage preamble sampling / mises en veille

¢L’émetteur consomme moins d’énergie si accord préalable sur une date de rendez-vous• Les préambules multiples permettent de compenser la dérive d’horloge

• Si le récepteur se réveille le premier, il écoute jusqu’à entendre un préambule.

• Si l’émetteur se réveille le premier, il envoie des préambules jusqu’à ce qu’un d’entre eux ne soit acquitté.

Claude Chaudet20

Consommation espérée

¢Notations : • Dérive d’horloge : δ (IEEE 802.15.4 impose δ ≤ ± 40 ppm)

• Périodes de veille (s): Ts • Durée d’un préambule (s) : P• Coût énergétique (W):

ERx à la reception ; ETx à l’émission

¢Estimation de la désynchronisation (td) entre émetteur et récepteur• Distribuée uniformément sur [ Ts – Ts.δ ; Ts + Ts.δ ]• Si td < 0 ; le récepteur “gâche” une énergie td.ERx• Si td > 0 ; l’émetteur “gâche” une énergie � td

P⇥.ETx

10 5 0 5 10

Ove

rhea

d en

ergy

ts (Unit: P)

td.ERx � tdP

⇥.ETx

21

Couche Réseau

Claude Chaudet

Gestion énergétique et routage

¢Critères de sélection des routes peuvent être modifiés :• Optimisation des performances :

- Choisir les routes les plus courtes- Choisir les routes les moins chargées

• Optimisation de l'énergie- Choisir les routeurs auxquels il reste le plus d'énergie- Choisir les routes les moins denses

• ... où se situe le bon compromis entre toutes ces métriques ?

• Chemin vert : 3 émissions, 17 réceptions- 641,17 . 10-9 Ah

• Chemin rouge : 6 émissions, 13 réceptions- 599,68 . 10-9 Ah

22

A S

Claude Chaudet

L’acheminement de données dans les réseaux de capteurs

¢Deux approches principales (i.e. avec du code disponible):

¢Tiny OS : • Protocole CTP (Collection Tree Protocol), crée un arbre à partir du point de

collecte en se basant sur la métrique de l’espérance du nombre de transmissions (ETX)

¢Groupe IETF ROLL : solution plus complète couche 3• 6LowPAN => Adaptation d’IPv6 aux réseaux de capteurs• RPL => création de graphes acycliques dirigés (DAG) pour le routage• ICMPv6 => Transposition d’ICMP• CoAP => Version allégée de HTTP pour interrogation asynchrone de

capteurs

23

Claude Chaudet

Collection Tree Protocol [1]

¢But : créer un arbre de collecte de données efficace• Collecte uniquement (1 seule destination) • Ne nécessite pas d’adresses (anycast)• Création d’un arbre couvrant à partir de la (les) racine(s)

¢Création de l’arbre : algorithme du vecteur de distance• La racine envoie un paquet en diffusion (flooding)• Chaque noeud du réseau recevant une instance de ce paquet

- prend note qu’il existe plusieurs chemins vers la racine- les compare au moyen d’une métrique appelée ETX [2]

– ETX : espérance du nombre de transmissions- Sélectionne le meilleur parent- Renvoie le paquet en broadcast local

¢ [1] Gnawali et al., Collection Tree Protocol — ACM SenSys 2009¢ [2] De Couto et al. - A high-throughput path metric for multihop-wireless routing - Wireless Networks 11(4), 2005

24

ETX(a, b) =1

Dab ·Dba

Probabilité de succèsd’une transmission a->b

Claude Chaudet

Collection Tree Protocol - Améliorations

¢Mécanismes d’estimation de lien : vers du cross-layer• 4-bits link estimator combine des estimations de

- la couche physique (probabilité de décodage de chaque symbole)- la couche MAC (congestion, saturation du canal, etc.)- la couche réseau (qualité des routes, stabilité des routes, ...)

• Codé sur 4 bits (1 pour les couches physique & MAC ; 2 pour le routage)• Très bon taux de remise des paquets pour un coût raisonnable

¢Adaptation de la fréquence d’envoi des beacons en fonction de la dynamique du réseau• Si l’état (voisins, parents, etc.) change => fréquence rapide• En cas de stabilité => doubler l’intervalle à chaque fois• Mécanisme classique permettant d’économiser des ressources et de rester

réactif aux changements25

Claude Chaudet

Groupe IETF ROLL

¢Routing over Low power and Lossy Networks• https://datatracker.ietf.org/wg/roll/charter/

¢Définir une architecture de communication (couches hautes) complète pour des réseaux • Contraints en ressources (énergie, mémoire, calcul ...) • Avec une couche liaison peu fiable (IEEE 802.15.4, PLC)

- Débit faible ; taux de pertes élevé ; taille de trame réduite

• Intermittents - Duty cycling (mises en veille, qualité de lien, ...)

26

Claude Chaudet

Architecture ROLL

27

Application IPv6

IPv6

Ethernet

6LowPAN

CoAP

LANInternet

...

IEEE 802.15.4 RPL ; ICMPv6

CoAP

protocole applicatif d’interrogation des capteurs en mode requête-réponse.

6LowPAN

Adaptation d’IPv6 au contexte capteurs (taille trame, ...)

RPL

Routage arborescent dans le réseau de capteurs

Claude Chaudet

CoAP (Constrained Application Protocol)

¢Protocole permettant d’interroger les capteurs¢Mécanisme de requête-réponse de type REST• Client-serveur

- Interface unifiée

• Sans contexte - un échange est généralement une seule requête-réponse - pas de notion de session au niveau des serveurs => échanges rapides

• Caches possibles (si la réponse le permet) et transparents- Les requêtes concernent une donnée plutôt qu’un destinataire

¢Interface de type HTTP ¢Mécanisme de souscription et de push

28

Claude Chaudet

6LowPAN — IPv6 over Low power Wireless Personal Area Networks

¢Couche intermédiaire offrant une interface IPv6 à un réseau de capteurs

¢Adaptation de la taille des trames• Mécanisme de fragmentation / réassemblage

- IPv6 : taille minimale de paquet =1280 octets- IEEE 802.15.4 : taille maximale de trame =127 octets

• Mécanisme de compression des en-tête- En-tête MAC = 23 octets ; en-tête IPv6 = 40 octets ; en-tête UDP = 8 octets

¢Adaptation du Neighbor Discovery• Pas de neighbor sollicitation en multicast (pas efficace) pour déterminer le

préfixe du réseau

¢Et beaucoup d’autres adaptations... —> RFC 4944

29

Claude Chaudet

RPL — IPv6 Routing Protocol for Low power and Lossy Networks

¢Protocole de routage construisant un DODAG (Destination Oriented Directed Acyclic Graph)• Draft IETF

¢Capable de construire plusieurs DODAGs• Plusieurs destinations (racines)• Plusieurs métriques de construction du DODAG (fonction objective)• Maintient les routes vers la racine et optionnellement les routes vers les

feuilles

30

Claude Chaudet

RPL - Construction des routes vers la racine

¢Chaque nœud envoie régulièrement ou sur sollicitation un message d’information : DIO — DODAG Information Object• émis en broadcast local• Contient des informations sur le DODAG

- ID, version, mode de fonctionnement, ...- seule la racine peut définir / modifier ces informations

• Continent une valeur de rang, version discrète d’une distance à la racine

• Intervalle d’envoi croissant de façon exponentielle (trickle timer)

¢Un nœud connaît grâce aux DIO• Ses voisins (tout nœud duquel on reçoit un DIO)• Ses parents (tout nœud qui a un rang inférieur au sien d’au moins un seuil)• Son parent préféré offrant le meilleur chemin vers la racine

31

Voisinparent

parent préféré

Claude Chaudet

RPL - construction des routes descendantes

¢A priori seule la racine connaît les routes descendantes• Mode optionnel (storing) permettant à tous les nœuds de maintenir les

routes descendantes• Consomme beaucoup de mémoire

¢Repose sur l’envoi de messages Destination Advertisement Object (DAO) par les feuilles• Envoyé à la racine en mode non-storing• Envoyé à son ensemble de parents en mode storing

32

Claude Chaudet

Mais aussi...

¢Beaucoup d’attention portée sur le routage, à l’image des réseaux ad hoc• Quelle métrique utiliser (ETX, rapport signal à bruit, taux de pertes,

énergie, longueur de route...) ?• Mono-destination ou interconnexion totale ? • Utilisation d’adresses ?

¢De nombreux autres protocoles de routage adaptés au contexte des réseaux de capteurs• Protocoles réactifs, adaptations d’AODV

- 6LoWPAN Ad-Hoc On-demand Distance Vector Routing (LOAD)- Dynamic MANET On-demand for 6LoWPAN Routing (DYMO-low)- Hierarchical routing (HiLow)

33

34

Déploiement / planification

Claude Chaudet

Influence sur le déploiement¢Dans les PRN / réseaux ad hoc, résultats sur les densités

(déploiement aléatoire) nécessaires pour maintenir la connexité d'un réseau de n noeuds [1] :• Le nombre idéal de voisins est en Θ(log(n))• À moins de 0,074.log(n) voisins, la probabilité de déconnexion approche 1

lorsque n grandit• À plus de 5,1774.log(n) voisins, la probabilité de déconnexion approche 0

lorsque n grandit

¢Quelle performance espérer d'un réseau de capteurs ?• Consommation augmente avec le nombre de voisins...• Viser une densité minimale

35

[1] Feng Xue, P.R. Kumar — The Number of Neighbors Needed for Connectivity of Wireless Networks — Wireless Networks — 2004

Claude Chaudet

Contraintes définissant la couverture¢Application : obtention de mesure statistiques• Existence d'une corrélation entre les données

- Trop de mesures : transmission de données inutiles- Trop peu de mesures : échantillonnage imparfait

¢L'unité de capture définit la zone surveillée par le nœud• Exemple : comment déployer un réseau de capteurs pour détecter les feux

de forêt ?- Vitesse de propagation d'un feu : de 0,5 km/h à 6 km/h- Propagation de la chaleur : loi de Stefan-Boltzmann- Température de fonctionnement du capteur : ≤ 130 °C- Capteur directionnel ...

36

Claude Chaudet

Déploiement d'un réseau de capteurs

¢Un capteur peut mesurer une donnée ; quelle est la validité spatiale et temporelle de cette donnée ?• Ex : une mesure de température en intérieur est significative dans une

pièce, mais pas dans la piècevoisine

• Ex : une mesure de températureest valide à une date t mais pasà t + 10 minutes

¢Nécessité de bien caractériser l'application

37

200 °C

20 °C100 °C

Température dans une demi-pièce carrée de 2,8m x 2,8m + un dégagementde ventilation (droite) quelques instants après allumage d'un feu de methane(simulation)Source : Flometricshttp://www.flomerics.com

Claude Chaudet

Conclusion

¢Les réseaux de capteurs posent plusieurs challenges intéressants• Réseaux radio multisauts• Nœuds contraints (mémoire, ...)• Optimisation de l’énergie (durée de vie du réseau)

¢Solutions de compromis à toutes les couches• Communiquer peu, stocker peu, ...• Solutions les plus efficaces reposant souvent sur la collaboration inter-

couches (cross-layer)• Possibilité de récupération de l’énergie (soleil, vibrations,...)

¢Attention à l’application !• Comment corréler (ou ne pas corréler) les données ?

38