Minimization of energy consumption of sensor networks in target coverage applications.

Les réseaux de capteurs sans fil (WSN) se composent de petits nœuds de capteurs dotés de microcontrôleurs intégrés, de radios à faible consommation, de batteries et de capteurs utilisés pour surveiller les conditions environnementales telles que la température, la pression, l'humidité et les vibrations. De nos jours, ces réseaux sont utilisés dans un large éventail d'applications militaires, sanitaires, domestiques, urbaines, industrielles et environnementales. Les applications de couverture de cibles sont celles où plusieurs points d’intérêt appelés cibles doivent être surveillés en permanence par des nœuds de capteurs. Dans la plupart des applications de couverture de cibles, les nœuds de capteurs ont une ressource d'énergie limitée et il est donc essentiel de gérer efficacement leur consommation d'énergie afin de prolonger la durée de vie du réseau. Une approche commune pour résoudre ce problème consiste à alterner le fonctionnement des nœuds de capteurs entre le mode actif et le mode veille. Le problème de former des sous-ensembles de nœuds de capteurs qui seront activés successivement pendant des durées définies tandis que les autres nœuds seront en veille, afin de maximiser la durée de vie du réseau, est NP-difficile et appelé MLCP (Maximum Lifetime Coverage Problem). Dans cette thèse, notre objectif est de proposer de nouvelles heuristiques pour le MLCP tout en considérant des hypothèses plus réalistes sur la durée de vie et la consommation énergétique des nœuds de capteurs. Tout d'abord, nous proposons deux heuristiques gloutonnes en supposant que les nœuds de capteurs n'ont pas nécessairement la même durée de vie. La première heuristique est basée sur une méthode adaptative tandis que la seconde utilise l’idée de liste noire, ce qui permet d’optimiser la gestion des cibles critiques, c’est-à-dire qui sont couvertes par un nombre minimal de capteurs. Ensuite, en considérant que l'énergie consommée par les nœuds de capteurs mis en veille n'est pas négligeable, nous proposons une troisième heuristique gloutonne qui prend en compte l'énergie résiduelle des nœuds de capteurs dans le choix des nœuds à activer. Puis, nous proposons une approche récurrente pour les réseaux réguliers. Nous étudions ensuite une famille d'instances difficiles du MLCP, à savoir la sous-famille des réseaux réguliers consitués par les anneaux de taille impaire. Nous proposons pour cette sous-classe, une approche analytique permettant d’obtenir des solutions efficaces dont nous conjecturons l’optimalité. Enfin, nous développons un système de surveillance de la pollution atmosphérique et de détection d'incendie basé sur un réseau de capteurs sans fil et nous évaluons le gain en termes de durée de vie du réseau lorsqu'un algorithme pour le MLCP est intégré dans un tel système.Wireless Sensor Networks (WSN) consist of tiny sensor nodes with embedded microcontrollers, low power radios, battery cells and sensors which are used to monitor environmental conditions such as temperature, pressure, humidity, and vibration. Today, these networks are used in a wide range of military, health, domestic, urban, industrial and environmental applications. Target coverage applications are those where several points of interest called targets must be continuously monitored by sensor nodes. In most target coverage applications, sensor nodes have a limited amount of energy and it is therefore critical to efficiently manage their energy consumption in order to extend the network lifetime. A common approach to tackle this problem is to alternate the operation of sensor nodes between active and sleep mode. The scheduling of appropriate subsets of sleep/active sensor nodes in order to maximize the network lifetime is an NP-hard problem called Maximum Lifetime Coverage Problem (MLCP). In this thesis, we aim at proposing new heuristics to the MLCP, while considering more realistic assumptions on lifetime and energy consumption of sensor nodes. Firstly, we propose two greedy heuristics with the assumption that the sensor nodes do not necessarily have the same lifetime. The first heuristic is based on an adaptive method while the second uses the idea of blacklist, which allows to optimize the management of least covered targets called critical targets. Secondly, by considering that the energy consumed by sensor nodes put in sleep mode is not negligible, we propose a third greedy heuristic that takes into account the remaining energy of the sensor nodes in the choice of the nodes to activate. Then, we propose a recurring approach for regular networks. We then study a family of hard instances of the MLCP, namely the sub-family of regular networks composed of odd-sized rings. We propose for this subclass, an analytical approach to obtain effective solutions which we conjecture optimality. Finally, we develop a system for air pollution monitoring and fire detection based on a wireless sensor network and we evaluate the network lifetime gain when an algorithm for the MLCP is integrated in such a system