Approches de type décomposition pour la gestion efficace de l'énergie dans les réseaux de capteurs sans fils

Energy is a major concern in wireless sensor networks (WSN). These devices are typically battery operated and provided with a limited amount of energy. As a consequence, the time during which sensors can monitor the interesting phenomena and communicate through wireless signals might be limited because of (sometimes) irreplaceable batteries. Additionally, it is very common for WSN to be used in remote or hostile environments which possibly makes necessary a random placement strategy (by using an airplane, a drone or a helicopter). Hence, the sensors location is not known a priori and approaches to efficiently use the energy are needed to answer to network topologies only known after sensors deployment. This thesis explores the use of column generation to efficiently use the energy in WSN. It is shown that column generation can be used as a general framework to tackle different problems in WSN design. Several versions of the problem and models for the operation of the WNS are adapted to be solved through column generation. These approaches take advantage of the natural way that column generation offers to consider different features of the WSN operation. Additionally, some computational improvements are proposed to keep the column generation method operating as an efficient exact approach. Hybrid strategies combining column generation with (meta)heuristic and exact approaches are considered and evaluated. The computational experiments demonstrate the efficiency of the proposed approaches and provide practitioners on WSN research with strategies to compute upper bounds to evaluate heuristic centralized and decentralized approaches. Finally, some future directions of research are provided based on the performance and adaptability of column generation to consider more sophisticated models and characteristics newly introduced in sensor devices.En el diseño de redes inalámbricas una de las principales preocupaciones es cómo hacer un uso eficiente de la energía. Estas redes están compuestas de sensores que son alimentados por una fuente externa de energía (batería) que tiene una capacidad limitada y, en muchos casos es irremplazable. Este hecho limita el tiempo durante el cual los sensores pueden realizar su trabajo de monitoreo a una zona y transmitir las señales percibidas. Por otro lado, en algunas aplicaciones ser requiere que los sensores estén ubicados en lugares de difícil acceso u hostiles, impidiendo su ubicación manual, lo que implica que el posicionamiento es aleatorio (p.ej. lanzados desde un helicoptero, un "dron" ó un avión). Dadas todas estas circunstancias, el uso de estrategias para optimizar el uso de energía es requerido. En esta tesis se explora el uso de modelos basados en redes para explicar el consumo de energía en una red de sensores inalámbricos y la técnica de generación de columnas como herramienta de solución para la optimización del uso de dicha energía. La técnica generación de columnas ofrece una herramienta de solución que puede usarse para representar con naturalidad la asignación y programación de la operación de los sensores. En este trabajo se proponen diferentes mejoras que permiten tomar ventaja de la la técnica de generación de columnas y mantener su eficiencia. Algunas estrategias híbridas que combinan el principio de la descomposición con metaheurísticas y métodos exactos son propuestas. Las propuestas fueron extensamente evaluadas y los experimentos computacionales confirman la eficacia de los métodos, proporcionando cotas superiores que pueden ser usados para evaluar el rendimiento de otros métodos centralizados y distribuidos. Finalmente, algunas direcciones de investigación son dilucidadas sobre la base de éste método y su uso como estrategia para atacar problemas más realistas que consideren las características de las redes de sensores inalámbricos del futuro.La gestion de l’énergie est une préoccupation majeure dans les réseaux de capteurs sans fil. Ces capteurs sont généralement alimentés par une batterie embarquant une quantité d’énergie finie. Par conséquent, le temps pendant lequel les capteurs peuvent surveiller une zone et communiquer par signaux radio est limité lorsqu’il n’est pas possible de remplacer leur batterie. En outre, les réseaux de capteurs sont parfois déployés dans des zones difficiles d’accès ou dans des environnements hostiles dans lesquels le placement des capteurs peut être considéré comme aléatoire (c’est le cas par exemple lorsque les capteurs sont largués d’un avion ou d’un hélicoptère). Ainsi, l’emplacement des capteurs n’est pas connu a priori et les approches pour utiliser efficacement l’énergie sont nécessaires. Cette thèse explore l’utilisation de la génération de colonnes pour optimiser l’utilisation de l’énergie dans les réseaux de capteurs sans fil. La génération de colonnes peut être vue comme un cadre général pour résoudre différents problèmes dans la conception et l’exploitation de ces réseaux. Plusieurs versions du problème et divers modèles sont proposés pour représenter leur fonctionnement, en utilisant notamment la génération de colonnes. Ces approches exploitent le caractère naturel de la génération de colonnes pour modéliser les différents aspects des réseaux de capteurs sans fil. Dans cette thèse, des contributions algorithmiques sont apportées afin de tirer le meilleur parti de la génération de colonnes au plan de l’efficacité computationnelle. Des stratégies hybrides combinant génération de colonnes et (méta)-heuristiques et donnant lieu à des méthodes exactes et approchées sont proposées et évaluées. Des tests numériques montrent l’efficacité des approches proposées et procurent des bornes supérieures qui peuvent être employées pour évaluer l’efficacité des méthodes centralisées et distribuées. Enfin, des perspectives sont dégagées concernant les performances et la portabilité de la génération de colonnes pour aborder des problèmes plus réalistes et tenir compte des caractéristiques des réseaux de capteurs sans fil du futur