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



Yüklə 445 b.
tarix26.10.2017
ölçüsü445 b.
#13979


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 :
    • 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 EtEr

  • 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



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



Yüklə 445 b.

Dostları ilə paylaş:




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©muhaz.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin