Ent?te

Logo du LIFL

Depuis le 1er janvier 2015 le LIFL et le LAGIS forment le laboratoire CRIStAL

  1. Formation doctorale

Thèse de

Nicolas Gouvy

jeudi 19 septembre 2013
Amphithéâtre de l'IRCICA

Routage géographique efficace dans un réseau de capteurs et d'actionneurs

Directeur de Thèse : M. David SIMPLOT- RYL, Mme Nathalie MITTON Rapporteurs : Mme Isabelle GUERIN LASSOUS, M. Marcelo DIAS DE AMORIM Membres : M. Wilfrid PERRUQUETTI, M. Antoine GALLAIS

Cette thèse se positionne dans le contexte des réseaux sans fil multisauts tels les réseaux de capteurs ou les réseaux de capteurs/actionneurs ou encore de robots mobiles. Ces réseaux sont composés d’entités (nœuds) indépendantes (c.-à-d. les robots) possédant des capacités limitées en termes de taille mémoire, de capacité de calcul et sont soumis à des contraintes énergétiques fortes (ces composants reposent sur des batteries). Ils communiquent exclusivement par voie radio, il n’y a donc aucune infrastructure fixe. Pour pouvoir relayer les messages d’un robot à une station de base, on utilise des protocoles dits « de routage » qui ont en charge de déterminer quel robot doit relayer le message, de façon locale et distribuée, sans connaissance globale du réseau.

Nous nous sommes basés sur CoMNet, le premier protocole de routage géographique utilisant la mobilité contrôlée tout en garantissant la connexité de celui-ci. CoMNet va, à chaque routage, relocaliser le prochain saut selon un schéma de relocalisation prédéfini de manière à adapter la topologie du réseau à son trafic, et ce afin d’économiser de l’énergie. Le fait de bouger les noeuds va certes adapter la topologie, mais aussi modifier les possibilités de routages de ce noeud, ses voisins ayant changé. En réponse à ce problème, nous avons proposé MobileR (Mobile Recursivity). MobileR va, à chaque étape du routage, essayer d’anticiper sur plusieurs sauts pour choisir le prochain nœud. Le paquet sera alors transmis, au premier nœud du chemin qui minimise ce ratio.

Le principe même de relocaliser les nœuds apporte son lot de nouveaux problèmes. Ainsi, dans les réseaux de capteurs, il y a souvent plusieurs nœuds sources qui détectent un même événement et vont émettre des messages à router vers l’unique station de base. Les chemins de routage de ces différents messages sont physiquement proches – vu qu’ils sont liés à un même événement – et ce d’autant plus qu’on se rapproche de la station de base. Ces chemins vont finir par se croiser, et le nœud de croisement va sans cesse être relocalisé par chacun des chemins. C’est pourquoi j’ai proposé le protocole de routage PAMAL (PAth Merging ALgorithm). En effet, PAMAL détecte ces intersections et va arrêter ces oscillations parasites. De plus PAMAL va provoquer une fusion physique des chemins de routage en amont du nœud d’intersection et une agrégation de paquets en aval.

La mobilité contrôlée permet aussi d’envisager de nouvelles solutions à des anciens problèmes. Le protocole GRR (Greedy Routing Recovery) propose ainsi un mécanisme de récupération pour augmenter le taux de délivrance des messages dans les réseaux de capteurs/actionneurs avec obstacle(s). En effet, aucun des protocoles de routage reposant sur des actionneurs n’implémente un procédé pour contourner les obstacles ou les zones de faible densité où le routage glouton simple est impossible. Le routage échoue alors quand un nœud n’a plus de voisin plus proche de la destination que lui-même. C’est pourquoi GRR va, quand le routage glouton simple de proche en proche échoue, appliquer un nouveau schéma de relocalisation qui va permettre de contourner l’obstacle tout en restaurant le routage glouton. L’obstacle va ainsi être circonvenu en relocalisant des nœuds tout autour. Ainsi, les routages suivants seront gloutons.

Ours

UMR 8022 - Laboratoire d'Informatique Fondamentale de Lille - Copyright © 2012 Sophie TISON - Crédits & Mentions légales

Page respectant XHTML et CSS.

Pour tout commentaire / Comments and remarks : webmaster