Méthodes probabilistes pour le routage dans les réseaux de capteurs sans fil

De Ensiwiki
Révision de 15 octobre 2009 à 08:32 par Altisenk (discussion | contributions) (Nouvelle page : {{Sujet ter | labo = [http://www-verimag.imag.fr/ Verimag] | titre = Méthodes probabilistes pour le routage dans les réseaux de capteurs sans fil | equipe = Synchrone | encadrants ...)

(diff) ← Version précédente | Voir la version courante (diff) | Version suivante → (diff)
Aller à : navigation, rechercher


Méthodes probabilistes pour le routage dans les réseaux de capteurs sans fil

Labo Verimag
Equipe Synchrone
Encadrants Karine.Altisen@imag.fr,Stephane.Devismes@imag.fr

Thème général

  • réseaux de capteurs sans fil
  • algorithmique distribuée
  • algorithmes probabilistes (méthode tabou, recuit simulé)
  • simulation

Compétences attendues

  • programmation orientée objets en Java
  • algorithmique 1A,
  • notions en probabilité (1A)

Contexte du travail

La technologie utilisant des réseaux de capteurs est en pleine expansion; ses applications sont très larges, de la détection de tremblement de terre au développement de services domotiques.

Les capteurs qui nous intéressent sont de petits appareils qui permettent de récolter des informations sur leur environnement (par exemple température) dans le but de les utiliser pour un service spécifique (émettre une alarme quand la température alentour est trop élévée). Situés à des distances raisonnables les uns des autres, ils sont capables d'échanger ces informations avec leur voisins proches, ce qui construit ainsi un réseau implicite sur lequel les données peuvent circuler.

La façon dont les données vont être acheminées d'un point à un autre du réseau est un problème crucial appelé routage : un protocole de routage calcule un chemin dans le réseau pour transférer les données de capteur en capteur jusqu'à atteindre la destination. Cet algorithme de recherche de chemin dans un graphe doit répondre à deux spécificités particulières des réseaux de capteurs sans fil. Premièrement, les communications dans un tel réseau ne sont pas fiables : le message peut être perdu à cause d'interferences (radio), il peut aussi ne pas être reçu parce que le capteur destinataire est à court de batterie. La structure du réseau est donc dynamique, ce qui implique qu'un chemin ne peut pas être calculé statiquement, une bonne fois pour toute. Deuxièmement, les capteurs ne peuvent communiquer qu'avec leurs voisins proches. Cela signifie que la structure globale du réseau ne leur est pas connue et qu'ils ne connaissent que les capteurs avec lesquels ils peuvent échanger. Trouver un chemin pour acheminer les données ne peut donc se faire que localement, capteur par capteur grâce à des algorithmes distribués.

Problème

Nous considérons dans ce travail un réseau composé de beaucoup de capteurs et d'un serveur appelé puits vers lequel les informations récoltées par les capteurs doivent être acheminées régulièrement. Il existe dans ce contexte trois approches usuelles pour le routage.

La technique de l'inondation (Flooding) consiste à acheminer les données systématiquement, sans utiliser aucune structure. Le chemin est calculé au fur et à mesure ; il peut l'être de façon déterministe auquel cas, le message à propager doit contenir aussi beaucoup d'informations de contrôle ; il peut être probabiliste mais l'arrivée du message à destination n'est alors pas garantie.

La technique du recouvrement (Overlay) calcule préalablement un table de routage pour chaque capteur et utilise cette table pour acheminer les information. L'inconvénient majeur est de maintenir ces tables dans un réseau dynamique.

La technique hybride mélange les deux techniques précédentes. Elle utilise la technique du recouvrement que le réseau est stable. Dès qu'il y a des modifications de la topologie, et en attendant un nouveau calcul des tables de routage, des techniques dérivées de l'inondation sont utilisées pour trouver un autre chemin.

Sujet

Dans des travaux précédents, l'article WSRABD07 a proposé un protocole de routage hybride utilisant deux stratégies :

  • calculer en largeur d'abord un arbre de racine le puits en utilisant le protocole décrit par HC92 puis acheminer les messages le long de cet arbre.
  • collecter des informations stockées dans les messages échangés, ce qui permettra de trouver un chemin de façon déterministe, en cas de changement de topologie du réseau.

L'inconvénient majeur de cette solution vient de la quantité d'informations de contrôle à mémoriser dans le message. Nous proposons d'améliorer cela en remplaçant les choix déterministes (permis grâce à la mémorisation de nombreuses informations) par des choix probabilistes utilisant des heuristiques d'optimisation classiques telles que les méthodes de recuit simulé ou les méthodes tabou. Ces deux heuristiques servent à approcher le minimum d'une fonction dont le domaine est très grand. Elles devront être adaptées au contexte distribué des réseaux de capteurs sans fil.

Résultats attendus

Le sujet de TER proposé consiste

  • à comprendre le problème étudié, et notamment les protocoles de routage en question en lisant quelques

articles ciblés,

  • puis à implémenter sur l'outil "sinalgo" un protocole de routage à base d'inondation probabiliste. sinalgo est un environnement de simulation pour tester et valider des algorithmes sur des réseaux. Les algorithmes y sont à développer en Java.

Le sujet pourra aller jusqu'à l'analyse des performances du protocoles (benchmarks issus de simulations et analyse de complexité).



Ce sujet fait partie du projet nationnal ARESA2 (Embedded Systems and Wireless Sensor Networks) qui implique à la fois des coopérations académiques et industrielles.


HC92 Shing-Tsaan Huang and Nian-Shing Chen. A self-stabilizing algorithm for constructing breadth-first trees. Inf. Process. Lett., 41(2):109--117, 1992.

WSRABD07 Thomas Watteyne, David Simplot-Ryl, Isabelle Aug\'e-Blum, and Mischa Dohler. On using virtual coordinates for routing in the context of wireless sensor networks. In 18th Annual International Symposium on Personal, Indoor and Mobile Radio Communications, Athens, Greece, September 3-7 2007. IEEE.