La semaine dernière, au cours du Symposium on Discret Algorithms 2011 organisé par l'Association of Computing Machinery et la Society for Industrial and Applied Mathematics, Keren Censor-Hillel, un étudiant chercheur post-doctorant au Computer Science and Artificial Intelligence Laboratory du Massachusetts Institute of Technology (MIT) et Hadas Shachnai, professeur agrégé en informatique au Technion Israel Institute of Technology, ont présenté leurs travaux de recherche consacrés à la réduction des goulets d'étranglement qui peuvent avoir lieu dans les réseaux ad hoc. Leurs travaux auront probablement des conséquences très importantes dans le développement futur de réseaux de capteurs ad hoc, lesquels sont destinés à être largement utilisés dans les décennies à venir. Alors que les contraintes de coût et les besoins en énergie des processeurs continuent à baisser, il est devenu possible de les intégrer en grand nombre dans des capteurs de faible puissance. Ceux-ci pourraient être utilisés pour surveiller à peu près n'importe quoi, depuis l'activité sismique d'un volcan à la circulation routière.

Par nature, les réseaux ad hoc ne sont gérés par aucun appareil de contrôle, comme un routeur par exemple. En effet, chaque noeud d'extrémité se comporte lui-même comme un routeur, assurant le transfert des données qui lui parviennent ou en générant pour son plus proche voisin. Le design typique des réseaux ad hoc fait que chaque noeud d'extrémité choisit au hasard un autre noeud pour y faire passer ses données. Cette approche vise à garantir que le trafic est réparti uniformément sur tous les noeuds. Et si un noeud tombe en panne, un autre peut prendre le relais. Le problème de cette approche, ce sont les goulets d'étranglement qui se créent lorsqu'un petit nombre de nodes d'extrémité sont chargés de véhiculer l'ensemble du trafic.

Une découverte encourageante mais gourmande

L'algorithme développé par Keren Censor-Hillel et Hadas Shachnai répartit le trafic pour empêcher les engorgements. Dans leur approche, un noeud choisit alternativement un autre noeud au hasard pour chaque donnée qui doit être transportée. Dans le tour intermédiaire, le noeud dirige le trafic non pas au hasard, mais vers un noeud avec lequel il n'a pas récemment communiqué. Pour Alessandro Panconesi, professeur d'informatique à l'Université Sapienza de Rome et expert en analyse des réseaux, cet algorithme apporte « une contribution intéressante » au problème. « Essentiellement, un noeud de ce réseau peut se réveiller et commencer à fonctionner à l'aide de cet algorithme, et si chaque noeud de ce réseau agit de la même manière, cela apporte des capacités de communication à l'ensemble du réseau, » a-t-il commenté dans un communiqué.

Celui-ci émet cependant une réserve : dans sa forme actuelle, cet algorithme est encore trop complexe pour fonctionner avec des outils de calcul simples. Parce que les équipements composant les réseaux ad hoc ont une puissance de calcul limitée et que la durée de vie de leur batterie est restreinte, ils exigent des protocoles réseau très simples. « L'algorithme est très gourmand en termes de quantité d'information à échanger,» a-t-il estimé. Néanmoins, selon lui, la simplification de cet algorithme est tout à fait possible.