Routage dynamique dans les réseaux de capteurs : on progresse !

Quel protocole faut-il mettre en place pour établir et maintenir dynamiquement les arbres de collecte qui acheminent les données des capteurs sans fil au contrôleur et vis versa. Les derniers travaux de l’IETF.

Après avoir consolidé les besoins et contraintes caractéristiques du déploiement de réseaux de capteurs sans fil dans des environnements domestiques, urbains et industriels, les travaux du groupe ROLL (routing over low power and lossy networks) de l’Internet Engineering Task Force (IETF) portent désormais sur la spécification d’un protocole de routage dynamique capable de prendre en compte ces besoins et contraintes exprimés sous forme de métriques qui font également l’objet d’un travail de caractérisation.

Vers l’établissement dynamique d’arbres de collecte

Les arbres de collecte [1] sont l’une des composantes fondamentales des applications exploitant les ressources de réseaux de capteurs. Ces arbres sont utilisés pour acheminer les données collectées par des capteurs vers un ensemble de contrôleurs qui vont ensuite les traiter et, le cas échéant, transmettre de nouvelles informations (commande, configuration) vers les capteurs en exploitant les mêmes structures arborescentes.Les discussions engagées au sein du groupe ROLL portent en particulier sur une contribution [2] qui propose un protocole capable d’établir et de maintenir dynamiquement de telles structures. L’algorithme utilisé est de type « distance vectorielle » et utilise un mécanisme de balisage pour transmettre de proche en proche les informations topologiques caractéristiques des arbres de collecte.La figure 1 ci-dessous décrit la manière dont un nœud N se raccorde à un arbre en fonction des balises qu’il a reçues de ses voisins.

Le tableau suivant décrit le contenu des balises reçues par le noeud N et envoyées par ses voisins A, B et C :

Emetteur	Contenu de la balise (extraits)
A	Arbre flottant Profondeur de l’arbre = 2
B	Arbre non flottant Profondeur de l’arbre = 2
C	Arbre non flottant Profondeur de l’arbre = 3

Tableau 1 : Exemples de contenus de balises.

La formation d’arbres de collecte s’appuie sur les principes suivants :

Le protocole localise le point de sortie le plus proche (e.g. le point d’accès au réseau Internet) sur la base des informations véhiculées dans des balises, dont le format correspond à une extension des messages RA (Router Advertisement) et RS (Router Solicitation) utilisés par le protocole de découverte de voisins pour IPv6 (« Neighbor Discovery for IPv6« , [3]). Cette extension permet de minimiser l’overhead introduit par la volumétrie du trafic caractéristique du protocole de routage.
Le protocole de routage permet en outre à chaque routeur de décider à quel arbre il va se rattacher selon les informations consignées dans les balises.

Un arbre est dit « non flottant » lorsqu’il est connecté à un backbone (e.g. l’un des routeurs du réseau de capteurs est raccordé au réseau Internet). La profondeur d’un arbre se définit par le nombre maximal de nœuds qui doivent être traversés pour atteindre la racine de l’arbre depuis n’importe quel nœud rattaché à l’arbre. Chaque nœud va donc déterminer la valeur de sa profondeur en fonction de la valeur de la profondeur du nœud parent auquel il est connecté (le nœud parent étant le nœud par lequel il peut atteindre la racine de l’arbre). Dans l’exemple de la figure 1, N va se raccorder sur le nœud B parce que (1) l’arbre est non flottant et (2) le niveau de profondeur est plus faible que celui du nœud C.Le principe de formation des arbres de collecte répond ainsi à trois lois fondamentales :

Un nœud qui n’est pas rattaché à un arbre non flottant est la racine de son propre arbre (flottant), et la profondeur d’un tel arbre est de 1.
Un nœud rattaché à un arbre peut se déplacer à n’importe quel moment pour se rapprocher de la racine de l’arbre, de façon à réduire la valeur de sa profondeur. Par contre, un nœud ne doit pas se déplacer de telle sorte que la valeur de sa profondeur augmente (i.e. qu’un nœud ne doit pas s’éloigner de la racine de l’arbre auquel il est rattaché).
Un nœud peut se détacher de l’arbre de collecte auquel il est rattaché à n’importe quel moment pour se raccorder à un autre arbre de collecte. Une nouvelle greffe n’a de sens que lorsqu’elle améliore un ou plusieurs paramètres de connectivité (plus grande bande passante, plus faible profondeur, etc.), qui constituent donc autant de métriques susceptibles d’être prises en compte par le protocole de routage.

Quelles métriques de routage ?

Les réseaux de capteurs sans fil se distinguent en particulier par un nombre de composants pouvant atteindre plusieurs milliers d’unités qui disposent de faibles ressources énergétiques. Le calcul et la sélection de routes au sein de tels environnements doivent donc prendre en compte de telles contraintes. Celles-ci devront être exprimées sous la forme de métriques qui peuvent être classées en deux catégories :

Les métriques caractéristiques de l’état des nœuds du réseau ;
Les métriques caractéristiques de l’état des liens du réseau.

Le tableau 2 ci-dessous présente un résumé de l’inventaire actuel [4].

Métriques noeud
Ressource mémoire	L’une des principales contraintes de nature à affecter la stabilité du routage dans un réseau de capteurs sans fil.
Ressource CPU	Les applications actuelles des réseaux de capteurs indiquent une sollicitation moyenne du CPU de l’ordre de 10 %, tandis que la technologie embarquée est de plus en plus performante.
Energie résiduelle	Lorsque la valeur de cette métrique est faible, le nœud ne devrait pas être pris en compte comme élément de routage, d’où la nécessité d’un routage à contraintes de nature à sélectionner des routes traversant des éléments capables de récupérer de l’énergie (alimentation par batterie solaire, par exemple) plutôt que des éléments qui ne fonctionnent que sur accus. Quitte à ce que les routes sélectionnées soient plus longues (en termes de nœuds traversés).
Etat de surcharge	La surcharge d’un nœud est de nature à affecter le temps de convergence, ce qui peut se révéler incompatible avec certains trafics. La métrique correspondante pourrait être équivalente à l’utilisation du bit « overload » dans le protocole IS-IS [5].
Agrégat de données	Lorsque les données d’une application donnée peuvent être agrégées afin de réduire le volume de trafic acheminé dans le réseau de capteurs, la durée de vie de certains éléments du réseau (ceux alimentés par accus, typiquement) peut ainsi être prolongée. De telles applications sont souvent caractérisées par des flux majoritairement unidirectionnels et prédictibles, tels que la collecte de données mesurant la pollution atmosphérique à heures fixes.
Métriques liens
Bande passante	Exprimée en bits ou paquets par seconde, cette métrique doit refléter la bande passante effectivement disponible.
Latence	Cette métrique va de pair avec la métrique « bande passante ».
Fiabilité	Dans les réseaux de capteurs, la fiabilité des liens est souvent affectée par des phénomènes d’interférences. L’échelle de temps peut varier de quelques millisecondes à plusieurs jours selon la nature de l’interférence (e.g. intervention humaine) et la métrique peut être exprimée en termes de taux d’erreur paquet ou bit.
Couleur	Métrique affectée de manière statique et susceptible de refléter une politique de routage différente selon le type de trafic, par exemple.

Tableau 2 : Métriques de routage pour les réseaux de capteurs.

Compte tenu de leur nature, la plupart des métriques décrites dans ce tableau nécessitent d’être mises à jour d’une manière dynamique, de façon à ce que les décisions de routage soient toujours adaptées.De façon à maîtriser l’impact de ces mises à jour sur la stabilité du routage (fréquence de diffusion des messages de mise à jour, notamment), le protocole de routage devra s’appuyer sur des algorithmes de calcul déclenchés selon des seuils multiples (reflétant la diversité des échelles de temps associées à chacune de ces métriques). En outre, la manipulation de plusieurs métriques impose de s’assurer de la cohérence des mécanismes de calcul de leurs valeurs.

Prochaines étapes

Le meeting IETF de juillet prochain sera l’occasion pour le groupe ROLL de soumettre une version consolidée de la spécification des métriques (avec publication du RFC dans la foulée), tandis que la spécification du protocole de routage devrait conduire à la publication du RFC correspondant dans le courant du premier semestre de l’année prochaine. Le chemin vers la standardisation est encore long, mais le travail bénéficie d’une collaboration active et efficace des principaux acteurs du marché (industriels, fournisseurs de services et opérateurs) !Par Christian Jacquenet, France Télécom ITNPS/NAD

Notes

[1] Levis, P., et al., « Collection Tree Protocol », http://www.tinyos.net/tinyos-2.x/doc/html/tep123.html, Février 2007.[2] Thubert P, et al., “LLN Routing Fundamentals”, draft-thubert-roll-fundamentals-01.txt, Work in Progress, Avril 2009.[3] Narten, T. et al., “Neighbor Discovery Protocol for IPv6”, RFC 4861, Septembre 2007.[4] Kim, M., et al. “Routing Metrics used for Path Calculation in Low Power and Lossy Networks”, draft-mjkim-roll-routing-metrics-03.txt, Work in Progress, Mars 2009.[5] Oran, D., et al., “OSI IS-IS Intra-Domain Routing Protocol”, RFC 1142, Février 1990.