Auto-Organisation Efficace en Energie pour Réseaux de Capteurs une approche transversale Thomas Watteyne 4 novembre 2008

Auto-Organisation Efficace en Energie pour Réseaux de Capteursune approche transversale

Thomas Watteyne4 novembre 2008

2/30T. Watteyne, Auto-Organisation Efficace en Energie pour RdC

Réseaux de Capteurs

Internet

Domaines d’application: monitoring environnemental, maison intelligente, surveillance industrielle, RdC urbains…

• mesure d’une valeur physique• traitement de cette valeur• communication sans-fil

Similaires aux réseaux ad hoc• pas d’infrastructure fixe• topologie changeante• communication multi-sauts

Différents des réseaux ad hoc• système embarqué: puissance de

calcul, mémoire et énergie limitées• pas de mobilité des nœuds • flux de trafic convergeant

(convergecast)

• grand nombre de nœuds• faible trafic


Auto-organisation, Efficacité en énergie

« Self-Organization can be defined as the emergence of system-wide behavior from local interaction between individual entities »

C. Bettstetter

Efficacité en Energie

?

radio96%

capteurs4%

micro-controlleur<1%

Noeud Actif

actif endormi0.0001

0.001

0.01

0.1

1

10

100

17.075

0.001

Courant (mA)


Plan

Accès au Medium• Etat de l’Art• Proposition : 1-hopMAC

Routage• Routage géographique• Proposition : 3rules et Coordonnées Virtuelles

Intégration des Propositions et Etudes Expérimentales• Sense&Sensitivity

Conclusions et Perspectives

1

2

3

4

5/30

S

A

B

C

T. Watteyne, Auto-Organisation Efficace en Energie pour RdC

Etat de l’ArtArbitrer l’accès au medium partagé:

• Efficacité en Energie• Qualité de Service (délai, fiabilité)• Equité• Capacité du réseau

PHY

MAC

routage

Ordonnancement Synchronisation de périodes actives

Echantillonnage de préambule

TSMP,PisterSMAC,Sohrabi

RdC Urbains

période d’écoute≥ période d’écoute

DATA

DATA

émetteur S

récepteur A

récepteur B

récepteur C

réveil donn

ées

Synchronisation (énergie, bande passante)

Adaptation aux changements de topologie

Résistance à la charge du réseau


Notre proposition: 1-hopMAC• extension de l’échantillonnage de préambule• découverte des voisins à la demande (≠ paquets Hello)

déco

uver

te

réveil

donn

ées

1-hopMAC v1But: identifier le voisin avec la plus petite métrique

S

A [0.1]

B [0.2]C [0.6]

1-hopMAC v2But: identifier tous les voisins

S

A

BC

7/30

1-hopMAC v1Idée:

• le voisin de plus petite métrique répond en premier

• après la première réponse, le nœud initiateur arrête d’écouter

S

A

BC

réveil

donn

ées

S

métrique βA=0.1

métrique βB=0.2

métrique βC=0.6

D

ACK0.2×D

Problème:

• probabilité de collision avec le premier message (≠ ALOHA)

dxA xB

NACK

0.6×D


ACK0.1×D

8/30

1-hopMAC v1


3 étapes:

• probabilité en fonction de D et xfirst=min(xi)

• densité de probabilité de xfirst

• probabilité en fonction de D

Probabilité de collision si• βi uniformément réparties• xi proportionnel à βi

9/30

Uniformément distribuées

pas nécessairement uniformément

distribués

x=D.β1/4

x=D.β1/3

x=D.β1/2

x=D.β1/1

prob

abili

té d

e co

llisi

on a

vec

le p

rem

ier

mes

sage

Taille de la fenêtre de contention

1-hopMAC v1Métrique du nœud i

fonctiontemps d’attente


x=D.β1/1

x=D.β1/2

x=D.β1/3

x=D.β1/4

x=D.β1/2.3-40%


Plan





1

2

3

4


Routage Géographique

mode glouton

mode face?

grap

he p

lana

ire

GF

G,

Sto

jmen

ović

Pour les domaines d’application considérés:• grand nombre de nœuds pas d’état (stateless)• faible charge pas de maintien continu de structure

Routage géographique est une solution adaptée


Notre proposition: routage 3rules

• Garantit la délivrance sur un graphe arbitraire stable

Idée: enregistrer la séquence de nœuds traversés dans le paquet

• version localisée de recherche en profondeur d’abord

1. ne jamais envoyer deux fois le même message au même nœud;

2. renvoyer un message à un voisin que s’il n’a aucun autre voisin avec qui il n’a jamais communique;

3. renvoyer le message vers le voisin qui m’a envoyé le message en dernier.

jamais 1er choix 2nd choix

simula

tion


Planarisation Localisée: Robustesse

• Toutes les techniques de planarisation localisées (e.g. transformée de Gabriel) échouent sous des hypothèse réalistes;

• les graphes ne sont pas planaires, GFG ne garantit plus la délivrance.

lorsque les nœuds ne connaissent pasparfaitement leur position

lorsque les zones de communicationradio ne sont pas circulaires

simulation

simulation

14/30

positions virtuelles initiales(liens entre nœuds voisins)

positions virtuelles après que 100 messages ont

traversé le réseau

positions virtuelles après que 500 messages ont

traversé le réseau

Coordonnées Virtuelles• Les nœuds ne connaissent pas leur position géographique.• Coordonnées Virtuelles représentent la position topologique.• Initialisation

• nœuds : choisissent position [x,y] aléatoirement• puits : choisit [0,0]

• A chaque trame émise• nœuds : mise à jour au barycentre des voisins• puits : reste à [0,0]

positions géographiquesdes nœuds


15/30

GFG


Coord. Virtuelles - Convergence [1/2]

routage 3rules sur positions virtuelles

1.10

GFG sur positions réelles (i.e.

localisation parfaite des nœuds)

simulation

longueurchemin trouvé

longueurplus court chemin



Preuve : les coordonnées virtuelles s’alignent

0 messages sent 100 300,000500


Coord. Virtuelles - Efficacité

15 ans × 2 messages/jour/nœud × 100 nœuds ≈ 1 million messages 63.3% de consommation en moins

simulationsimulation


Coord. Virtuelles - Robustesse

temps

simulation

200 nœuds aléatoirement

déployés60 nœuds

aléatoirement détruits 60 nœuds

aléatoirement déployés


Plan





1

2

3

4


Intégration des PropositionsCross-layering routage 3rules et Coordonnées Virtuelles 1-hopMAC v2 (liste complète de voisins)

WSN430(développé au CITI)

réveil données

Coordonnées Virtuelles du nœud A

Décisionde routage


68 intérieur+ 18 extérieur

86 nœuds

nœud puits

nœud puits

10mhttp://senseandsensitivity.rd.francetelecom.com/

envoi toutes les 7.5 minutes

en moyenne


Stabilité des liens radio entre voisins

expérimentation

Puissance d’un lienfortement corrélé avecProbabilité de succès

Liens représentatifs:écart-type moyen de la puissance est de 1.04

(en dBm, sur 120 liens)


Impact sur le voisinage

expérim

entation


Robustesse de la Solution de Routage [1/4]

expé

rimen

tatio

n



expérimentatio

n



expérimentatio

n



expé

rimen

tatio

n


Plan





1

2

3

4

29/30

An

alys

e, S

imu

latio

n, E

xpér

imen

tatio

n


Conclusions

• échantillonnage de préambule est la technique d’accès au médium la plus efficace

• découverte de voisinage entièrement à la demande

1-hopMAC

• Routage géographique adapté aux RdC• problème de robustesse avec

coordonnées réelles

routage 3rules sur Coordonnées Virtuelles

Observations expérimentales montrent la dynamique du graphe de connectivité.

gran

d no

mbr

e de

nœ

uds,

faib

le tr

afic

30/30

Aborder la couche MAC avec un angle autre que l’énergie:• Qualité de Service (latence, fiabilité)• Comparaison des différentes approches sur ces nouveaux critères


PerspectivesPHY

MAC

routage

• Coordonnées Hybrides, utiles à la fois pour l’application (positionnement géographique) et pour le routage (positionnement topologique)

• redéfinir les Coordonnées Virtuelles dans un espace de contraintes différent (e.g. chemin à énergie minimale, zones interdites, QoS, multi-chemins etc.)

• Effort de proposition de nos résultats:• IETF ROLL, routage dans les RdC

• Prise en compte des résultats suivants:• IEEE802.15.4, nouvelles fonctionnalités offertes par le matériel

Cross-layering avec la couche matérielle.• IETF 6LoWPAN, utilisation de IPv6 dans un réseau IEEE802.15.4

Maturité des solutions ? Impact et adaptation.


PublicationsBrevets

• Thomas Watteyne, Abdelmalik Bachir, Mischa Dohler, Dominique Barthel, Isabelle Augé-Blum "A low-energy adaptive cross-layer communication protocol for avoiding 1-hop neighborhood knowledge ," juin 2006 (international).

• Thomas Watteyne, Mischa Dohler, Isabelle Augé-Blum, Stéphane Ubéda "Using Centroid Transformation on Virtual Coordinates to Route in Wireless Sensor Networks," septembre 2007 (France).

Revue Internationale

• Mischa Dohler, Thomas Watteyne, Fabrice Valois, Jia-Liang Lu "Kumar’s, Zipf’s and Other Laws: How to Structure a Large-Scale Wireless Network ?," Annals of Telecommunications, vol.63, number 5-6, pp.239-251, 4 June 2008.

Chapitres de Livres

• Thomas Watteyne, Mischa Dohler, Isabelle Augé-Blum, Dominique Barthel "Beyond localization: communicating using virtual coordinates," Book chapter accepted for inclusion in "Localization Algorithms and Strategies for Wireless Sensor Networks", Guoqiang Mao and Baris Fidan Eds., to be published by IGI Global in 2008.

• Isabelle Augé-Blum, Fei Yang, Thomas Watteyne "Real-Time communications in Wireless Sensor Networks," Book chapter accepted for inclusion in "Handbook of Research on Next Generation Networks and Ubiquitous Computing", Samuel Pierre Ed., to be published by IGI Global in 2008.

Contribution IETF

• Mischa Dohler, Thomas Watteyne, Tim Winter Eds. "Urban WSNs Routing Requirements in Low Power and Lossy Networks," IETF Internet-Draft, Networking Working Group ROLL, June 2008.

Conférences Internationales (9)

• DCOSS’08 (work-in-progress), GLOBECOM’07, PIMRC’07 (2 papiers), European Wireless’07, BodyNets’07, IWWAN’06, InterSense’06, MASCOTS’05.

Tutoriels donnés en Conférences Internationales

• VTC 2008-Fall (demi-journée, 7 participants), WPMC’08 (journée entière, 32 participants).

Liste alphabétique des co-auteurs: Isabelle Augé-Blum, Abdelmalik Bachir, Dominique Barthel, Mischa Dohler, Jia-Liang Lu, David Simplot-Ryl, Stéphane Ubéda, Fabrice Valois, Tim Winter, Fei Yang.

32/30

Analyse, Simulation, Expérimentation• Analyse

• Outils statistiques• Chaines de Markov

• Simulation (GTSNetS) • Simulateur à événements discrets• Passage à l’échelle• Modèles de propagation, capteur, environnement physique

• Expérimentation• Environnement de développement Think


com

plém

enta

rité

EM2420 WSN430(développée au CITI)

33/30

S

A

B

C


Echantillonnage de Préambule

émetteur S

récepteur A

récepteur B

récepteur C

période d’écoute≥ période d’écoute

DATA

DATA

micro-trame• décompte• adresse destination

Echantillonnage de préambule à micro-trames• préambule découpé• micro-trame: décompte et adresse destination


Comparaison analytique entre MACs

35/30

S

…

S

…S

…

B

A

C

Réseau à faible trafic: inefficacité en énergie ?


Découverte de voisinage

S

A B

C

Etat de l’art• envoi périodique de paquets Hello (couche routage)• écoute du canal et maintien de tables de voisinage


1-hopMAC v2 [1/2]

but: donner le temps à tous les nœuds de répondre en ouvrant des fenêtres de

contention successives

Canal occupé, réponse envoyée à la prochaine fenêtre de contention

Dernière fenêtre libre, envoi des données

S

A

BC


1-hopMAC v2 [2/2]

Durée totale de contention CT vs. durée d’une fenêtre CW

pour 5 voisins

Nombre de fenêtres de contention

Nombre de voisins

CW CT

3 9ms 31ms

4 10ms 46ms

5 14ms 62ms

6 17ms 74ms

7 16ms 88ms

8 19ms 103ms

9 22ms 118ms

analyse

durée d’une fenêtre de contention, CW

du

rée

to

tale

de

co

nte

ntio

n,

CT


Etat de l’ArtTrouver un chemin multi-sauts en un nombre de sauts réduit (élongation)

PHY

MAC

routage

routage par inondation

routage hiérarchique routage géographique

?

!


Routage Hiérarchique

Clustering• grouper les nœuds• nœud leader par

cluster• maintien de la structure

Dé

bit

no

rma

lisé

du

ré

sea

u

Nombre de Clusters

analyse


Planarisation du Graphe

graphe non planaire

• liens ne se croisent pas

• GFG garantit la délivrance

transformée de Gabriel(localisée)

graphe planaire associé

but: retirer « logiquement » les liens qui se croisent.


Planarisation du Graphe

• GFG échoue lorsque le graphe n’est pas planaire

D

H

G F

E

D

H

G F

E

graphe non-planaireGraphe planaire associe


Coordonnées Réelles et Virtuelles

Coordonnées Réelles

CoordonnéesVirtuelles

• représentent les positions géographiques des nœuds

• problème des hypothèses non réalistes pour le routage

• représentent les positions topologiques des nœuds

• utilisables pour le routage (3rules; GFG non utilisable)

Un nœud: • choisit ses coordonnées virtuelles aléatoirement au démarrage;• met à jour ses coordonnées virtuelles à chaque envoi.

les coordonnées virtuelles convergent (i.e. l’élongation des chemins tend vers 1)


Utilisation de puits multiples [1/2]


Utilisation de puits multiples [2/2]



Preuve (étape 2): est-ce que ces coord. virtuelles s’alignent correctement ?

real

coo

rd.

virt

ual c

oord

.


Observations de Propagation

Documents

Auto-Organisation Efficace en Energie pour Réseaux de Capteurs une approche transversale Thomas Watteyne 4 novembre 2008