Déploiement et Ordonnancement de Réseaux de Capteurs Sans Fil pour le Suivi de la Pollution de l'Air

Wireless sensor networks (WSN) are widely used in environmental applications where the aim is to sense a physical phenomenon such as temperature, humidity, air pollution, etc. In this context of application, the use of WSN allows to understand the variations of the phenomenon over the monitoring region and therefore be able to make adequate decisions regarding the impact of the phenomenon. Due to the limitations of its traditional costly monitoring methods in addition to its high spatial and temporal variability, air pollution is considered as one of the main physical phenomena that still need to be studied and characterized. In this thesis, we consider three main applications regarding the use of WSN for air pollution monitoring: 1) the construction of real-time air quality maps using sensor measurements; 2) the detection of pollution threshold crossings; and 3) the correction of physical models that simulate the pollution dispersion phenomenon. All these applications need careful deployment and scheduling of sensors in order to get a better knowledge of air pollution while ensuring a minimal deployment cost and a maximal lifetime of the deployed sensor network. Our aim is to tackle the problems of WSN deployment and scheduling while considering the specific characteristics of the air pollution phenomenon. We propose for each application case a new efficient approach for the deployment of sensor and sink nodes. We also propose a WSN scheduling approach that is adapted to the case of physical models’ correction. Our optimization approaches take into account the physical nature of air pollution dispersion and incorporate real data provided by the existing pollution sensing platforms. As part of each approach, we use integer linear programming to derive optimization models that are well adapted to solving small and medium instances. To deal with large instances, we propose heuristic algorithms while using linear relaxation techniques.Besides our theoretical works on air pollution monitoring, we design from scratch and deploy in the Lyon city a cost-effective energy-efficient air pollution sensor network. Based on the characteristics of our monitoring system in addition to real-world air pollution datasets, we evaluate the effectiveness of our deployment and scheduling approaches and provide engineering insights for the design of WSN-based air pollution monitoring systems. Among our conclusions, we highlight the fact that the size of the optimal sensor network depends on the degree of the variations of pollution concentrations within the monitoring region.Les réseaux de capteurs sans fil (RCSF) sont largement utilisés dans les applications environnementales où l’objectif est de détecter un phénomène physique tel que la température, l’humidité, la pollution de l’air, etc. Dans ce contexte d’application, l’utilisation de RCSF permet de comprendre les variations du phénomène et donc être en mesure de prendre des décisions appropriées concernant son impact. En raison des limitations de ses méthodes de suivi traditionnelles et de sa grande variabilité spatiale et temporelle, la pollution de l'air est considérée comme l'un des principaux phénomènes physiques qui restent à étudier et à caractériser. Dans cette thèse, nous considérons trois applications concernant l’utilisation de RCSF pour le suivi de la pollution de l’air : la cartographie en temps réel de la qualité de l’air, la détection de dépassements de seuils des polluants et la correction de modèles physiques qui simulent le phénomène de dispersion de la pollution. Toutes ces applications nécessitent de déployer et d’ordonnancer minutieusement les capteurs afin de mieux comprendre la pollution atmosphérique tout en garantissant un coût de déploiement minimal et en maximisant la durée de vie du réseau. Notre objectif est de résoudre les problèmes de déploiement et d'ordonnancement tout en tenant compte des caractéristiques spécifiques du phénomène de la pollution de l’air. Nous proposons pour chaque cas d'application une approche efficace pour le déploiement de noeuds capteurs et puits. Nous proposons également une approche d’ordonnancement adaptée au cas de la correction de modèles physiques. Nos approches d'optimisation prennent en compte la nature physique de la pollution atmosphérique et intègrent les données réelles fournies par les plateformes existantes de suivi de la qualité de l’air. Dans chacune de nos approches d’optimisation, nous utilisons la programmation linéaire en nombres entiers pour concevoir des modèles d’optimisation adaptés à la résolution de petites et moyennes instances. Pour traiter les grandes instances, nous proposons des heuristiques en utilisant des techniques de relaxation linéaire.Outre nos travaux théoriques sur le suivi de la pollution atmosphérique, nous avons conçu et déployé dans la ville de Lyon un réseau de capteurs de pollution économe en énergie. Sur la base des caractéristiques de notre système et des jeux de données de la pollution atmosphérique, nous avons évalué l’efficacité de nos approches de déploiement et d’ordonnancement. Nous présentons et discutons dans cette thèse les résultats d'évaluation de performances ainsi que des lignes directrices pour la conception de systèmes de suivi de la pollution de l’air. Parmi nos principales conclusions, nous soulignons le fait que la taille optimale du réseau de capteurs dépend du degré de variation des concentrations de pollution dans la région de déploiement