Application de Concepts de Routage Géographique au Routage par Gradient: une Étude Qualitative
Thomas Watteyne?† , Isabelle Augé-Blum? and Mischa Dohler†
Laboratory, INSA Lyon, France. pré[email protected] † France Télécom R&D, Meylan, France. pré[email protected]
? CITI

Abstract— Les réseaux de capteurs sans ?l connaissent un fort engouement ces dernières années, à la fois dans lemonde académique et dans le monde industriel, grâce notamment, au grand nombre d’applications envisagées, et à l’apparition de solutions commerciales viables. A cause de leurs contraintes propres, des mécanismes de routage spéci?ques ont été proposés. Le routage géographique et le routage par gradient sont des candidats intéressants pour les réseaux de capteurs, puisqu’ils ne requièrent qu’unephase d’auto-organisation minimale. Dans cet article, nous montrons que les concepts du routage géographique sont applicables au routage par gradient. Nous mettons en évidence une faille dans la règle de la main droite, et nous proposons une solution sous la forme d’un protocole appliqué au routage géographique et par gradient.

I. I NTRODUCTION Les Réseaux de Capteurs sans ?l (Wireless sensornetworks – WSN) connaissent un fort engouement ces dernières années. Les applications de tels réseaux sont multiples, allant de la défense et la surveillance, à la santé et les maisons intelligentes [1]. Les WSN sont composés d’un nombre potentiellement très grand (plusieurs milliers) de ces petits objets communicants, déployés dans la zone à couvrir. Chaque capteur est capable d’effectuer trois tâchescomplémentaires: mesure d’une valeur physique, traitement de ces mesures, et communication par voie hertzienne. Les capteurs sont des objets communicants limités en terme de bande passante, de puissance de calcul, de mémoire disponible et d’énergie embarquée. Le déploiement est la plupart du temps aléatoire et peut être réalisé dans des zones dangereuses (on ne peut alors pas compter sur unremplacement de batterie). Dans les WSN, une structure peut être créée entre les capteurs. Des protocoles d’auto-organisation pour les réseaux ad-hoc [2]–[4] s’appuient sur une phase d’auto-organisation où une structure virtuelle est créée. Les noeuds sont regroupés en clusters, avec un chef pour chacun. Ces chefs sont interconnectés par un ensemble d’épines dorsales. Le routage se fait alors demanière hiérarchique en suivant le chemin noeud source ? chef de cluster ? épine dorsale ? chef de cluster ? noeud destination. Une fois la structure construite, un certain nombre de mécanismes permettent de prendre en compte le changement de topologie (par mouvement et apparition/disparition de noeuds) et l’endormissement de certains

noeuds pour éviter de sur-utiliser leurs batteries. Ces formesd’auto-organisation explicite – i.e. avec une phase d’auto-organisation importante avant fonctionnement normal du réseau – semblent peu adaptées aux réseaux de capteurs. Dans ces protocoles, les mécanismes de maintien de la structure supposent l’échange périodique de messages de signalisation. Or ceux-ci sont coûteux en énergie, et réduisent la durée de vie des capteurs. Pour certaines applications deréseaux de capteurs, une autoorganisation implicite est préférable. Dans celle-ci, le réseau s’organise en s’appuyant sur une métrique extérieure ou une phase d’organisation minimale. Nous nous intéressons dans ce document au routage géographique et au routage par gradient. Il s’agit des deux grandes classes de routage s’appuyant sur une phase d’auto-organisation implicite. Dans les protocoles deroutage utilisant le concept de routage géographique [5], un noeud élit parmi ses voisins le noeud qui est le plus proche géographiquement de la destination comme noeud de prochain saut. Dans une approche utilisant le routage par gradient [6]–[9], une métrique est rattachée à chaque noeud. Un noeud élit parmi ces voisins le noeud qui a la plus grande/petite métrique comme noeud de prochain…