Défis intrinsèques aux réseaux de capteurs

Depuis l’apparition des premiers calculateurs au début du siècle dernier, l’évolution des systèmes informatiques a été jalonnée de grandes étapes de miniaturisation. En effet, l’apparition du transistor, suivie de la puce micro-électronique, des ordinateurs personnels, des ordinateurs transportables, puis de poche sont autant de révolutions qui ont marqué ce processus de progression. À l’aube du XXIe siècle, certains téléphones portables sont plus puissants que les ordinateurs de bureau commercialisés à la fin des années 1980. Désormais, les systèmes électroniques de taille réduite sont omniprésents dans notre environnement.

A contrario de cette quête de diminution de la taille des composants, et a fortiori de celle des machines dites intelligentes, l’évolution de l’informatique a nécessité, pour sa part, un accroissement sans pareil des besoins, en terme de puissance de calcul et de stockage pour le traitement de l’information et la communication. Les systèmes centralisés sont arrivés logiquement à leur limite intrinsèque et l’apparition des réseaux communicants a permis d’atteindre une puissance de calcul comparable aux super-calculateurs pour un coût minime. Par la suite, la nécessité du partage d’informations à distance et l’évolution des mœurs de notre société vers une hyper-communication a permis la démocratisation de ces systèmes dit répartis. Ces systèmes permettent de distribuer les puissances de calcul et de stockage parmi un nombre grandissant d’entités participantes. De l’ordre de la dizaine au moment de la démocratisation du réseau Internet, à la fin des années 1980, ces systèmes répartis atteignent désormais communément la centaine de millions de participants avec la popularisation des systèmes pair-à pair, tels que Napster [Nap08], Skype [Sky08], ou autres BitTorrent [Bit08].

Le désir de miniaturisation, jumelé avec les technologies de ces systèmes communicants à calculs répartis, a fait récemment éclore un ensemble de nouveaux systèmes dit d’informatique diffuse ou embarquée. La réduction des entités électroniques se trouvant face à une limitation physique des composants, la distribution de la puissance au sein d’un système dit collaboratif a permis de pallier cette limitation. Equipés d’un périphérique de communication sans-fil, les éléments de ces nouveaux systèmes peuvent donc être aisément déployés, sans nécessiter d’infrastructure matérielle coûteuse, encombrante et pénible à mettre en place et à entretenir. La restriction concernant la puissance et le déploiement s’écartant, la réduction de taille des entités physiques s’est intensifiée permettant de voir apparaître des ordinateurs plus petits qu’une pièce d’un centime d’Euro. Ces nouveaux micro-ordinateurs, qui sont au cœur de notre étude, se situent actuellement à la frontière avec un nouveau domaine émergent : celui des nano-technologies.

Réseaux de capteurs En parallèle, les applications de surveillance, de protection et d’observation de notre environnement se sont accrues ces dernières années, aussi bien dans le milieu médical qu’écologique ou militaire. Malheureusement, l’intervention humaine n’est pas réalisable dans tous les lieux d’investigation. Les années 2000 ont alors vu la naissance de «poussières intelligentes», ensemble de plate-formes matérielles miniaturisées couplées avec un module d’acquisition de données permettant de capter et de collecter des stimuli ou événements issus de l’environnement local de ce capteur. Les faibles possibilités technologiques d’un capteur unique ne lui permettent pas d’avoir une utilité propre, mais la mise en réseau d’un grand nombre de ceux-ci ouvre des opportunités de progrès et de fonctionnement palpitantes. L’intérêt des communautés issues de la recherche et de l’industrie pour ces réseaux de capteurs sans fil (RCsF) s’est accru par la potentielle fiabilité, précision, flexibilité, faible coût ainsi que la facilité de déploiement de ces systèmes. Les caractéristiques des RCsF permettent d’envisager un grand nombre d’applications d’observation répartie dans l’espace. Ces dernières peuvent se déployer dans de nombreux contextes : observation de l’environnement naturel (pollution, inondation, . . . ), suivi d’écosystèmes (surveillance de niches d’oiseaux, croissance des plantes, . . . ), militaire (télésurveillance de champs de bataille, détection d’ennemis, . . . ), biomédical et surveillance médicale (détection de cancer, rétine artificielle, taux de glucose, diabètes, . . . ), etc. La spontanéité, l’adaptabilité du réseau et la dynamicité de sa topologie dans le déploiement des RCsF soulèvent de nombreuses questions encore ouvertes. L’une des limitations contraignantes de ces réseaux est la faible ressource énergétique des capteurs due essentiellement à leur taille minimaliste et leur indépendance filaire. Cette contrainte doit être considérée comme la préoccupation de premier ordre dans la conception et le déploiement d’un RCsF.

Auto-organisation Compte tenu du nombre potentiellement important de capteurs participants et de leurs ressources réduites, il apparaît indispensable de développer des solutions entièrement décentralisées, répartissant la charge entre les participants et permettant de passer à l’échelle en terme de nombre d’entités déployées. Par conséquent, dans le contexte des RCsF, l’approche collaborative dans la conception de systèmes dédiés apparaît nécessaire. En effet, ces derniers sont la plupart du temps développés dans un cadre applicatif précis afin d’optimiser la consommation d’énergie locale et globale, dans le but d’optimaliser la durée de vie du réseau. Enfin, cet ensemble de capteurs devant être capable de délivrer un service sans nécessiter d’intervention extérieure (humaine ou matérielle), la collaboration doit être conçue de manière auto-organisante. Cette dernière notion a pour optique l’émergence d’un comportement général et global du système, à partir d’acteurs indépendants et possédant uniquement des informations restreintes et locales du système. Ainsi, la charge est répartie sur l’ensemble du système, et l’augmentation du nombre de participants n’entraîne pas la formation de goulot d’étranglement, ni de point de défaillance critique (par l’unicité du serveur), couramment observés sur les systèmes communicants dit centralisés.

Limitations des systèmes existants Depuis leur récente apparition, les RCsF ont connu une effusion d’intérêt permettant en quelques années de réunir un ensemble de connaissances considérable. Nombreuses sont les applications déployées fournissant des services fondés sur un RCsF de nos jours. Par exemple, nous pouvons citer la surveillance de zone sécurisée, ou la domotique . Malheureusement, la grande majorité des résultats scientifiques et techniques dans ce domaine a été développée dans un contexte applicatif. À ce jour, encore très peu de travaux présentent des analyses fondamentales et/ou théoriques des RCsF. Une modélisation générique communément admise, permettant d’explorer les enjeux et les limitations de ce domaine, manque toujours à cette communauté en plein essor.

Défis intrinsèques aux réseaux de capteurs

Alors qu’un grand nombre d’applications met en œuvre des RCsF, ces derniers possèdent plusieurs restrictions inhérentes à prendre en compte dans leur conception, qu’ils soient statiques ou mobiles. En plus du fait qu’un capteur souffre de limitations locales, telles qu’une faible puissance de calcul, une réserve d’énergie limitée et une bande passante de communication réduite, il faut également prendre en compte des aspects globaux du système. Nous nous présentons ci-après un ensemble de défis à considérer d’un point de vue global lors du développement d’une application [AKK04].

Consommation énergétique

Un capteur sans-fil est le plus souvent équipé d’une source énergétique de faible capacité (i.e. moins de 0,5 Ah pour 1,2 V) [ASSC02b]. Dans de nombreux contextes applicatifs, le renouvellement des ressources énergétiques est simplement impossible. La durée de vie d’un capteur, et par conséquent celle du réseau, est donc étroitement liée à celle de son module d’alimentation (communément nommé, par abus de langage, sa batterie).

La gestion et la conservation d’énergie tiennent une place d’autant plus primordiale. C’est essentiellement pour cette raison que la contrainte énergétique est considérée comme étant celle de premier ordre par la communauté. Les travaux de recherche se focalisent sur la conception de protocoles et d’algorithmes à faible consommation pour les RCsF. D’un autre côté, dans le contexte des réseaux mobiles ad hoc (dénotés MANET pour Mobile Ad-hoc NETwork), la consommation d’énergie représente un facteur de conception d’autant moins contraignant que les ressources peuvent être remplacées ou renouvelées par l’utilisateur. Dans ces réseaux, l’accent est donc mis plus sur la qualité de service (QoS) que sur la faible consommation. Dans les RCsF mobiles qui peuvent s’apparenter aux MANET, les protocoles sont souvent conçus spécifiquement pour une application, afin d’optimiser notamment l’efficacité en terme de consommation d’énergie.

La fonction principale d’un nœud d’un RCsF est de détecter des événements, d’effectuer quelques traitements rapides sur les données collectées et de transmettre ses résultats. La consommation d’énergie d’un capteur peut donc être classifiée selon trois axes, quelque soit le contexte de mobilité : la capture, le traitement des données et la communication. Celles-ci sont traitées indépendamment ci-dessous. La durée de vie d’un capteur est liée à sa réserve d’énergie et à la façon dont celle-ci est utilisée [HCB00]. Mais, fréquemment, la disparition d’un nœud, dont l’énergie est épuisée, n’implique pas la mort du réseau dans son ensemble. Ainsi, certains algorithmes dans un contexte statique n’hésitent pas à sacrifier quelques nœuds en épuisant l’intégralité de leur réserve sur une période donnée pour augmenter significativement la durée de vie globale du RCsF [MVG+06]. Par contre, ces algorithmes doivent assurer que la perte de ces nœuds continue cependant de garantir la condition de connexité du RCsF . À l’inverse, en présence de mobilité, le plus souvent, un capteur est embarqué sur chaque unité mobile. La perte d’un capteur entraîne alors la disparition d’une des unités dans le système. Ainsi, ce type d’heuristique est souvent peu utilisé dans ce contexte.

Capture de données 

Le module de capture et ses éléments varient fortement en fonction de l’application considérée. Par conséquent, leur consommation d’énergie dépend étroitement de celle-ci. Par exemple, pour une application médicale de surveillance de diabète, des capteurs sont placés sur des patients à risque et relèvent périodiquement le taux de glycémie. Une capture sporadique (i.e. une fréquence de capture relativement faible) peut souvent amener à une consommation plus réduite qu’avec un contrôle d’événements permanent. Cependant, ce dernier est nécessaire dans le cas d’un suivi de trajectoire d’objets. En sus de la fréquence de capture, la complexité de la détection d’événements joue également un rôle primordial dans la détermination de la dépense énergétique. Par exemple, un fort bruit ambiant entraîne souvent des captures inexactes, et en augmentera donc la complexité.

Communication sans-fil 

Des trois classes de consommation d’énergie, la plus gourmande est celle de la communication. Elle comprend à la fois la transmission et la réception de données. Il est également important de prendre en compte, non seulement la dépense énergétique en mode actif du transcepteur, mais également la consommation due à l’initialisation du circuit électronique de transception. Dans un contexte de RCsF statique, il est possible d’éteindre régulièrement le transcepteur afin d’économiser de l’énergie. Dans un contexte à forte mobilité, la mise en veille est plus difficile en raison des messages périodiques émis pour détecter continuellement son voisinage de communication direct. En effet, après chaque extinction du transcepteur, le temps de démarrage, de l’ordre de la centaine de micro-secondes entraîne un coût non-négligeable. Par conséquent, étant donné que le temps de transmission d’un message de petite taille est très court, l’alternance marche/arrêt n’est pas toujours efficace sur un RCsF mobile.

Traitement des données 

Comparativement au module communication, la consommation issue du traitement des données est bien moindre. En se basant sur la théorie de la diffusion Rayleigh et de l’affaiblissement de l’onde en fonction de la distance, le coût énergétique pour transmettre 1 kilo-octet sur une distance de 100 mètres est approximativement le même que celui pour exécuter 3 millions d’instructions sur un processeur a 100 MIPS/W (millions d’instructions par seconde et par watt) [PK00]. Par conséquent, le traitement local des données est crucial pour réduire la consommation d’énergie d’un RCsF à routage multi-saut. Dans un routage sur une infrastructure réseau fixe (capteurs immobiles), l’agrégation de messages et la construction d’arbres de diffusion nécessitent un traitement local plus important, mais dont l’économie d’énergie est non négligeable. À l’inverse, dans un contexte mobile, ce type de mécanisme n’est pas réalisable, mais l’agrégation reste possible par l’instauration d’un délai de retransmission. Durant ce délai, tous les messages reçus seront agrégés avant d’être transmis d’un bloc à la destination.

Table des matières

Introduction
Objectifs de cette thèse
Organisation du document
Contributions
Liste des publications
1 Introduction générale aux réseaux de capteurs
1.1 Contraintes physiques d’un capteur
1.1.1 Interface de communication
1.2 Défis intrinsèques aux réseaux de capteurs
1.2.1 Consommation énergétique
1.2.2 Tolérance aux défaillances
1.2.3 Couverture et connexité
1.3 Différents aspects de ces réseaux
1.3.1 Déploiement des nœuds
1.3.2 Modèle de données
1.3.3 Hétérogénéité
1.3.4 Critères d’évaluation
1.3.5 Agrégation des données
1.4 Ouverture et positionnement
PARTIE I : Réseaux de capteurs statiques
2 Suivi et identification de trajectoires sur un réseau de capteurs binaires
2.1 Introduction
2.2 État de l’art succinct
2.3 Modélisation du système
2.3.1 Localisations et mouvements
2.3.2 État du système
2.3.3 L’observateur
2.4 Identification d’objets et suivi de trajectoire
2.4.1 Le problème MOTI
2.4.2 Un résultat d’impossibilité
2.5 Conditions de résolubilité de MOTI
2.5.1 Caractérisation d’infaillibilité
2.5.2 Un algorithme de génération du graphe des états SG
2.5.3 Caractérisation de MOTI
2.6 Une condition suffisante rendant MOTI P-résoluble (a priori)
2.7 Contraindre le mouvement des objets en temps réel avec un observateur actif
2.7.1 Algorithme simple avec omniscience
2.7.2 Algorithme sans connaissance du graphe des états
2.8 Algorithmes répartis large-échelle sans observateur
2.8.1 Vers une utilisation a posteriori
2.9 Conclusion
3 Structure générique multi-couches à faible consommation
3.1 Introduction
3.2 Prérequis du système
3.3 La collection *-cast
3.4 Le cœur de SOLIST
3.4.1 Une structure multi-couche
3.4.2 Structure de couche : LIGH-t-LAYER
3.4.3 Relier les mondes : les points d’entrées
3.4.4 Résumé des prérequis
3.5 La collection *-cast dans SOLIST
3.5.1 Anycast
3.5.2 Broadcast
3.5.3 k-cast
3.6 Évaluation des performances
3.6.1 Environnement de simulation
3.6.2 Présentation des algorithmes de comparaison
3.6.3 Fiabilité de SOLIST
3.6.4 Consommation d’énérgie
3.7 Comparatif de travaux relatifs
3.8 Conclusion
PARTIE II : Réseaux de capteurs mobiles
4 Modèles de calcul pour réseaux de capteurs mobiles
4.1 Contexte général
4.2 Protocoles de population
4.2.1 Fonctionnalités de bases
4.2.2 Formalisation du modèle
4.2.3 Exemples de protocoles de population
4.2.4 Puissance du modèle
4.2.5 Travaux connexes
4.3 Protocoles de communauté
4.3.1 Motivation
4.3.2 Formalisation du modèle
4.3.3 Puissance du modèle
4.3.4 Travaux connexes
4.4 Conclusion
5 Prise en compte de la mobilité dans les protocoles de population
5.1 Motivation
5.2 Mobilité avec les protocoles de population et de communauté
5.2.1 Les modèles MAPP et MAPC
5.2.2 Pertinence du modèle
5.2.3 Analyse fondamentale de la convergence
5.3 Impact des modèles de mobilité sur la vitesse de convergence
5.3.1 Echantillon des distributions de probabilité sur Λ
5.3.2 Estimation en temps discret : les modèles de rencontre
5.3.3 Estimation en temps continu : modèles d’inter-rencontre
5.4 Une borne inférieure optimale de la vitesse de convergence
5.5 À propos de la pertinence du modèle de RWP
5.6 Conclusion
6 Équivalence des protocoles épidémiques et de population
6.1 Les protocoles épidémiques
6.1.1 Historique des protocoles épidémiques
6.1.2 Protocole épidémique générique
6.1.3 Deux grandes classes de protocoles épidémiques
6.2 Motivation
6.3 Une classification des protocoles épidémiques
6.3.1 Entre synchronisme et asynchronisme
6.3.2 Puissances des classes de protocoles épidémiques
6.4 Combler le fossé entre les protocoles épidémiques et de population
6.4.1 Equivalence entre les protocoles de population et de asyncPENA
6.4.2 Equivalence entre les protocoles de communauté et de PENI
6.4.3 Un impact potentiel pour les deux domaines
6.5 Optimalité du RPS en terme de vitesse de convergence
6.6 Conclusion
Conclusion

Lire le rapport complet