Systèmes d’information collaboratifs et auto-organisants pour réseaux de capteurs large-échelle

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.

Introduction générale aux réseaux de capteurs 

Les progrès significatifs en électronique de capture ont permis une nette amélioration des capteurs depuis une décennie. En effet, les premiers capteurs, de taille plus conséquente, étaient souvent placés loin de l’événement à percevoir, nécessitant souvent des techniques complexes de différentiation des cibles à observer par rapport au bruit environnant. Dorénavant, un RCsF est composé d’un nombre important de petits nœuds, lesquels sont déployés au cœur même du phénomène à observer, sinon à une distance très courte. La position des capteurs ne nécessite plus une étude préalable et n’a pas à être pré-déterminée. Ceci permet par exemple un déploiement chaotique sur des zones inaccessibles ou dévastées.

Deux grandes classes de réseaux Le déploiement de RCsF soulève un certain nombre de questions conceptuelles telles que l’auto-organisation, l’adaptabilité ou la dynamique de la topologie du réseau. Parmi les différentes caractéristiques d’un RCsF, la mobilité des nœuds dans le temps et dans l’espace scinde ces réseaux en deux grandes classes. Alors que des solutions se reposant sur la connaissance des coordonnées géographiques sont réalisables simplement dans un contexte de RCsF statique (cf. chapitres 2 et 3), elles deviennent irréalisables, ou très coûteuses en énergie, en présence de forte mobilité. De plus, toute application à fondement collaboratif repose sur la communication des participants. Pour cela, l’efficacité d’une solution dépend notamment du protocole de routage sous-jacent, de l’anonymat des nœuds, ou encore du modèle de déplacements de ceux-ci.

Contraintes physiques d’un capteur

Un capteur est composé de quatre unités de base, à l’instar de la représentation en figure 1.2 : un module de capture, un module de traitement, un module de communication et un module d’alimentation [ASSC02b, VDSJCJDM03]. Le module de capture, permettant la collecte de données issus de stimuli externes, est le plus souvent constitué de deux sous-composants : des capteurs classiques combinés à un convertisseur analogique-vers-numérique (ADC pour Analog-to-Digital Converter). Le signal analogique, généré par le phénomène observé perçu par les capteurs, est converti en un signal numérique par l’ADC et transmi au module de traitement. L’étude de ce module se trouve être hors du contexte de ce document. Le module de traitement est composé d’un processeur – ou Unité Centrale de Traitement (UCT, ou CPU pour Central Processing Unit) – généralement associé à un périphérique de stockage de taille réduite. Il exécute le processus permettant la collaboration des nœuds entre eux afin de mener à bien les tâches de capture dévolues. Il représente le principal support matériel utilisé dans ce manuscrit. Le module de communication permet de connecter les nœuds du réseau, quels que soient le support et le média utilisé par celui-ci. Le plus souvent, il est constitué principalement d’un périphérique de communication sans-fil de type Bluetooth, ZigBee ou même WiFi (cf. paragraphe 1.1.1). Il représente la principale source de consommation d’énergie et doit ainsi être largement pris en compte. Nous ne consacrons pas une étude approfondie de ce module dans ce document, mais toutes nos conceptions utilisent ce module et sont motivées par une limitation d’utilisation afin d’économiser l’énergie. Le module d’alimentation est quant à lui l’un des composants les plus importants d’un nœud. Il assure la durée de vie du capteur en approvisionnant en énergie tous les modules internes et externes du capteur. De même que pour le module de communication, toute conception de systèmes sur des RCsF doit prendre en compte l’utilisation de ce module. Nous cherchons dans toutes nos contributions à limiter son utilisation et ainsi améliorer la durée de vie du nœud capteur .

Interface de communication

Concernant les médias de communication sans-fil, les différentes alternatives communément admises sont fondées soit sur l’onde radioélectrique, l’optique ondulatoire (Laser) ou l’infrarouge. L’utilisation du Laser requiert une énergie minime mais exige un alignement des lignes de visée entre deux capteurs (récepteur unidirectionnel) et reste très sensible aux conditions atmosphériques environnantes. L’infrarouge, comme le Laser, ne nécessite pas d’antenne mais reste cependant très limité quant à la taille de la bande passante disponible. À cet égard,l’onde radioélectrique s’impose comme étant le support de communication le plus approprié pour la majorité des applications sur les RCsF. C’est le type de communication que nous considérons dans l’intégralité de ce document. Les modules d’émission et de réception sont, la plupart du temps, combinés sur un même périphérique de communication. Par la suite, pour représenter ce module de communication, nous utiliserons le néologisme transcepteur (contraction de transmetteur et récepteur, à l’instar des anglo-saxons utilisant couramment le néologisme transceiver issus de transmitter et receiver).

Les transcepteurs peuvent fonctionner dans quatre modes différents : émission, réception, en attente et éteint. Il est important de préciser qu’un transcepteur dans un état d’attente consomme environ autant que dans un état de réception [XHE01]. Il est donc préférable d’éteindre complètement le module lorsqu’il n’envoie, ni ne reçoit, de paquets. En outre, différents types de standard de communication existent et leurs utilisations varient selon les besoins des applications, en termes de bande passante, de distance de transmission, de robustesse du signal, etc. Alors que l’informatique classique regorge d’une profusion  de standards, il n’existe qu’un unique standard officiel adopté pour les RCsF : le WirelessHART [HAR07]. De nombreux standards sont pour autant utilisés très largement dans la communauté, à savoir le WiFi (IEEE 802.11x ), le Bluetooth (IEEE 802.15.1), le ZigBee (IEEE 802.15.4) ou encore, le futur prometteur Wibree (encore à l’état de draft IETF à ce jour). Chacun de ceux-ci possède leurs avantages et inconvénients propres. Le WiFi permet une large couverture de zone ainsi qu’un haut-débit de transmission de donnée. Cependant, la consommation d’énergie nécessaire à son utilisation l’exclut souvent lors d’une mise en œuvre réelle. Le Bluetooth et le ZigBee ont une consommation plus faible, mais également un débit et une zone de transception limités. Le premier permet des communications point-à-point tandis que ZigBee facilite la communication « un-vers-tous ».

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

Télécharger le rapport complet