Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Application de Concepts de Routage Géographique au Routage par Gradient: une Ét

Application de Concepts de Routage Géographique au Routage par Gradient: une Étude Qualitative Thomas Watteyne∗†, Isabelle Augé-Blum∗and Mischa Dohler† ∗CITI Laboratory, INSA Lyon, France. prénom.nom@insa-lyon.fr †France Télécom R&D, Meylan, France. prénom.nom@orange-ft.com Abstract— Les réseaux de capteurs sans ﬁl connaissent un fort engouement ces dernières années, à la fois dans le monde 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’une phase 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. INTRODUCTION Les Réseaux de Capteurs sans ﬁl (Wireless sensor networks – 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âches complé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 un remplace- ment 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 inter- connectés par un ensemble d’épines dorsales. Le routage se fait alors de maniè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 ap- parition/disparition de noeuds) et l’endormissement de certains noeuds pour éviter de sur-utiliser leurs batteries. Ces formes d’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 de réseaux de capteurs, une auto- organisation 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 de routage 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 saut, selon l’approche utilisée. Dans la partie II, nous présentons l’état de l’art concernant le routage géographique et le routage par gradient. Dans la partie III nous montrons que les concepts de routage géo- graphique peuvent s’appliquer au routage par gradient. Nous mettons ensuite en évidence une faille de la règle de la main droite, et nous proposons une solution. Enﬁn, nous concluons dans la partie III. II. ETAT DE L’ART Le routage dans les WSN pose de nombreux déﬁs. Utiliser un plan d’adressage global semble peu efﬁcace, à cause du grand nombre de noeuds. Celui-ci supposerait l’échange de messages de contrôle de conﬂit d’adresses, sur des liens de faible bande passante et entre des noeuds à énergie limitée. Nous sommes en présence d’un modèle de communication "sources multiples - destination unique". Un ensemble de noeuds situés à proximité l’un de l’autre peuvent simultané- ment détecter un même évènement (e.g. le départ d’un feu de forêt), un mécanisme d’agrégation de données est donc nécessaire. Fig. 1. Le routage géographique avide s’arrête à s. La règle de la main droite choisit le chemin s-y-z-d. Le disque plein représente la portée de communication de s. Les cercles en pointillés sont centrés en d, ils permettent de voir la distance relative des noeuds à d. Les segments relient des noeuds capables de communiquer entre eux. A. Le routage géographique Dans un protocole de routage géographique, un noeud est supposé connaître sa position géographique, celle de ses voisins et celle du noeud destination. La connaissance du voisinage est périodiquement mise à jour à l’aide de messages HELLO échangés entre noeuds voisins. Dans une approche avide (greedy geographic forwarding), le noeud le plus proche de la destination, parmi les noeuds voisins, est choisi comme prochain saut. Comme métrique de proximité, il est possible d’utiliser la distance euclidienne, ou la projection sur une ligne entre le noeud courant et la destination. Cependant, [5] met en évidence une faille du routage géo- graphique avide, illustrée Fig. 1. Lorsque le noeud s reçoit une alarme, il n’existe pas de noeud voisin de s plus proche que lui de d. Avec une approche avide, le routage s’arrête à s et le message est perdu. GPSR [5] propose la règle de la main droite comme solution. Dans celle-ci, lorsque s ne trouve pas de noeud voisin plus proche que lui de la destination, il trace une ligne virtuelle entre lui et la destination d, et fait tourner cette ligne vers la droite, centrée sur s. Le premier noeud rencontré (ici y) est élu noeud de prochain saut. Le chemin retenu est s-y-z-d. GPSR utilise le routage géographique avide, couplé à la règle de la main droite. B. Le routage par gradient Le routage géographique suppose que tous les noeuds connaissent leur position. Une solution basée sur le GPS peut être trop coûteuse, d’autant plus que le nombre de noeuds à équiper est très grand. Pour répondre à ce problème, le routage par gradient (ou Gradient Based Routing – GBR) [10] associe une hauteur à chaque noeud. Cette hauteur peut par exemple être le nombre de sauts qui sépare le noeud du puits. Pour obtenir une certain efﬁcacité en énergie, l’énergie résiduelle d’un noeud peut être couplée au nombre de sauts du puits comme hauteur. La description qui suit peut être généralisée à n puits. L’association noeud-hauteur se fait lors d’une phase d’initialisation: (1) le puits envoie un message contenant une hauteur courante de 0, (2) chaque noeud qui entend ce message initialise sa hauteur à hauteur courante+1 et retransmet le message avec cette nouvelle hauteur comme hauteur courante [8]. On suppose qu’à la ﬁn de cette initialisation, tout noeud connaît sa hauteur, ainsi que celle de son 1-voisinage. Celle- ci pourra être apprise par un envoi périodique de messages de type HELLO. Durant le fonctionnement, les noeuds envoient leur message au noeud voisin le plus "bas". Ce routage avide (i.e. le message sera transmis selon le chemin de plus forte pente) présente beaucoup de similitudes avec le routage géographique. Pour conclure la présentation de l’état de l’art, les routages géographique et par gradient semblent bien adaptés aux réseaux de capteurs. En effet, il ne requièrent qu’une informa- tion locale du réseau pour l’établissement de routes globales. Dans le routage géographique, il n’y a pas de phase d’auto- organisation explicite. Pour le routage par gradient, [8] propose un protocole localisé d’adaptation des hauteurs des noeuds en cas de changement de topologie (mobilité, arrivé/départ de noeuds). III. PROPOSITIONS Dans cette partie, nous montrons que les concepts de routage géographique peuvent facilement s’appliquer au routage par gradient. Nous mettons ensuite en évidence une faille de la règle de la main droite, aussi bien dans le routage géographique que dans le routage par gradient. Nous proposerons une solution générale, et nous l’appliquons au routage géographique et au routage par gradient. A. Application de concepts de routage géographique au routage par gradient Le routage par gradient présente beaucoup de similitudes avec le routage géographique. On peut en effet directement appliquer le protocole de routage géographique avide au routage par gradient car, dans les deux mécanismes de routage, chaque noeud contient une métrique de proximité à la source. Par contre, la notion de droite n’a pas de sens dans le cas de routage par gradient. On ne peut donc appliquer directement la règle de la main droite au routage par gradient. En routage géographique, la règle de la main droite consiste à contourner une zone sans noeud. Cette règle permet une avancée transversale uploads/Geographie/ routage-geographique.pdf