Broadcast, énergie et réseaux de capteurs Guillaume Chelius citi, Insa de Lyon – ares, inria

Broadcast, énergie et réseaux de capteurs

• Guillaume Chelius CITI, Insa de Lyon – ARES, INRIA

• Eric Fleury CITI, Insa de Lyon – ARES, INRIA

• Thierry Mignon UMR CNRS 5030

Réseaux de capteurs ?

• C’est quoi ?

• Un réseau de nœuds sans fils dédiés à une application

• Pourquoi faire ?

• Acquérir des données et les transmettre à une station de traitement

• Quel domaine ?

• Militaire :
• Surveillance de zones sensibles, détection…
• Civile: Détection de feu de foret, surveillance d’entrepôts chimiques…

Comparaison senseurs / ad hoc !

Principaux défis

• Energie

• MAC, routage, transport

• Compromis fusion de données / clusterisation

• Durée de vie d’un réseaux de senseurs

• i.e., combien de temps remplie-t’il sa mission ?

• Densité  passage à l’échelle

• Pour le moment, pas de meilleures solutions génériques

• orienté application

Où part cette énergie ?

• Par ordre décroissant :

• Radio (Communication)
• Protocoles (MAC, routage)
• CPU (calcul, agrégation)
• Acquisition

• E.g., 1 octet transmis == 11000 cycles

Modèle

• Énergie en communication :

• Sur des courtes distances Et ≈ Er

• Multi sauts permet de réduire le facteur dû à la perte de propagation rk

Problème

• Trouver un schéma de broadcast qui minimise la consommation énergétique globale du réseau.

• NP complet

BIP : Broadcast Incremental Power

• Un ½ model

• Wireless Multicast advantage

PRIM de retour !

• PRIM : Pij reste inchangé

• BIP Pij := Pij – P(i)

• Node i is already in the tree.
• Incremental cost power

BIP (continue)

• Algo centralisé !

• Non optimal

• Ratio MST entre 6 et 12

• Ratio BIP enter 13/6 et 12

• Ne prend pas en compte la réception !

• Concentre le trafic sur qcq noeuds

Bornes inférieures pour la diffusion ?

• On prend en compte l’émission et la réception

• Assignation de puissance

• On veut minimiser :

Quelques définitions

• Une couverture de A est un ensemble de disques

• L’union des disques de R contient A
• Tout compacte du plan n’intersecte qu’un nombre fini de disques de R
• On appel émetteurs les points Pi de R

• Si Pi et Pj sont deux émetteurs de R , Pi peut transmettre à Pj si

Quelques définitions (cont)

• La couverture R de A est

• Centralisée si il existe au moins un émetteur qui peut transmettre à tous les autres émetteurs
• Connexe si tous les émetteurs peuvent transmettre à tous les autres émetteurs

Constantes et coût

• e est le coût relatif d’émission en W/m2

• λ est le coût de réception en W/m2 par individu

• ρ est le nombre d’individu par m² dans la région A

• r = λ ρ, est le coût de réception relatif en W/m2

•  = e + r est le coût complet relatif du modèle en W/m2

Question

Recouvrement périodique

• Recouvrement R indicé par I est périodique si

• Il existe un ensemble fini J  I et deux vecteur u, v de R²
• Si Pj +mu +nv = Pj’ alors j=j’ et (m,n) = (0,0)

Coût d’un recouvrement périodique

• Compact B de R² tel que

• Et B et B + mu + nv disjoints

• Le coût relatif de R vaut

Quelques exemples

• Couverture périodique

• Couverture périodique connexe

• Couverture centralisée

• Couverture centralisée

2 ou 3  lemmes

• Soit R une couverture non centralisée de A. On appel lien, tout ensemble de disques L tel que L R est une couverture centralisée de A.

• Lemme 1

• Soit R une couverture non centralisée de A de coût relatif  et  > 0. Il existe un lien de R tel que coût(L R ) <  + 

2 ou 3  lemmes (cont)

• Lemme 2

• Il existe une séquence de disque Dn dont les intérieures sont disjoints deux à deux tel que Lim n+ Aire(Dn) = Aire(A)

Principal résultat (Théorème)

• Le coût relatif de toute couverture d’une région A est plus grand que . Si A est borné il est strictement supérieur.

• Pour tout ε>0, il existe une couverture connexe de A ayant un coût relatif entre  et + ε

• Il existe une couverture connexe du plan avec une un coût relatif de 

Application ?

• Coût en réception associé à une émission

• Proportionnel à l’aire couverte par l’émission

• Approprié pour opération de mesure

• Applicable si on place les senseurs

• Aire(A)  Card(A)

• Borne inf atteignable…

Conclusion

• Limitations du modèle

• Niveaux de puissance continus et non discrets
• Densité de nœuds et non distribution

• Avancées

• Émission/réception
• Stratégie de placement
• Couverture pour des réseaux de senseurs
• Diffusion

• Prise en compte de plusieurs rayons discrets

Perspectives

• Percolation continue

• Modèle poissonnien booléen
• Réémission

• Algo distribués

• Reconfigurable

Durée de vie…

• Durée de vie limité des batteries

•  maximiser la durée de vie du réseau !

• i.e., l’instant ou

• Le premier noeud tombe en panne
• Une certaine fraction tombe en panne
• Perte de la couverture / connectivité

• Assurer une consommation répartie de l’énergie au sein du réseau…

Notion de durée de vie

• Minimiser la consommation globale d’énergie

• Maximiser la période avant le premier mort

• minimiser le max des arêtes (minimax)
• PRIM marche très bien ! (optimal)

• Maintenir la couverture de la zone