Autostabilisation - Définition

Introduction

L'autostabilisation, ou auto-stabilisation, est la propriété d'un système réparti, composé de plusieurs machines capables de communiquer entre elles, qui consiste, lorsque le système est mal initialisé ou perturbé, à retourner automatiquement à un fonctionnement correct en un nombre fini d'étapes de calcul. Elle a été définie par Edsger Dijkstra en 1974. Essentiellement analysée en informatique théorique, l'autostabilisation vise des applications dans les domaines où l'intervention d'un humain pour rétablir le système après une défaillance est impossible ou dans lesquels il est préférable de s'en passer : les réseaux informatiques, les réseaux de capteurs et les systèmes critiques, tels que les satellites.

Une application possible : les réseaux de capteurs

Schéma de principe d'un réseau de capteurs.

Un réseau de capteurs sans fil est un ensemble de petites machines autonomes, les capteurs. Chaque capteur possède un microprocesseur, une petite quantité de mémoire vive, une batterie, un émetteur-récepteur de radio et un ou plusieurs instruments de mesure : thermomètre, hygromètre, etc. Le but d'un tel réseau est de rassembler automatiquement les mesures effectuées par les capteurs individuels pour en déduire un résultat global. Parmi les applications, les réseaux de capteurs peuvent être déployés dans une forêt pour avertir en cas d'incendie, dans une zone de conflit pour détecter la présence d'ennemis, ou dans un biotope afin d'observer des animaux sans les perturber. Les capteurs étant limités à des processeurs rudimentaires, leur puissance de calcul est limitée. De plus, leurs batteries sont réduites et la consommation en énergie augmente avec la portée des transmissions radio, ce qui limite la distance de leurs communications. En effet, comme les capteurs sont surtout utilisés dans les endroits difficiles d'accès, il n'est généralement pas prévu d'intervenir sur eux pour remplacer la batterie. En général, l'information en provenance des capteurs est récupérée par une station de base (schéma ci-contre) qui possède une plus grande puissance de calcul et de transmission. En règle générale, les capteurs sont fixes : on les pose à un endroit donné et ils ne peuvent pas se déplacer.

Un réseau de capteurs, pour être utile, doit être autonome. Les capteurs doivent s'échanger leurs informations et effectuer leurs traitements sans jamais nécessiter d'intervention. Or, de nombreuses perturbations du système peuvent se produire. Par exemple, un capteur peut tomber en panne, ou de nouveaux capteurs peuvent être déployés dans la zone. L'autostabilisation est une des solutions permettant de s'assurer que le réseau de capteurs récupère automatiquement de ces perturbations.

Capteurs Sun SPOT.

Des algorithmes autostabilisants peuvent résoudre les problèmes de base spécifiques aux réseaux de capteurs, en particulier le multiplexage temporel (les capteurs s'accordent sur des créneaux pendant lesquels un seul d'entre eux émet), la communication par diffusion orientée (une méthode de routage adaptée aux réseaux de capteurs), et le fonctionnement en dépit du fait que certains capteurs peuvent être périodiquement coupés du reste du réseau. De même, des solutions autostabilisantes adaptées aux réseaux de capteurs existent pour des problèmes classiques tels que la coloration de graphe, le calcul d'un stable maximum ou d'un arbre couvrant, ou encore la synchronisation d'horloges.

Il existe également des réseaux de capteurs mobiles, dans lesquels les capteurs sont posés sur des agents capables de se déplacer. Ceci donne une nouvelle façon d'observer des animaux sauvages sans perturber leur comportement en installant les capteurs non plus dans le biotope, mais sur les animaux eux-mêmes. Les conditions nécessaires et suffisantes pour résoudre le problème du comptage autostabilisant, qui consiste à déterminer le nombre de capteurs présents dans le système, ont été établies dans ce cadre. Cette problématique rejoint celle des protocoles de populations, qui avait été formulée séparément, et qui consiste à considérer le système comme un ensemble d'agents à mémoire très limitée qui se déplacent aléatoirement, capables de s'échanger des informations lorsqu'ils se rencontrent.