Résumé
On considère un réseau de capteurs sans fils déployé dans une zone où un ensemble de cibles statiques doit être surveillé. Chaque capteur est muni d'une batterie non rechargeable, et peut être actif ou pas (un capteur non actif ne consomme pas d'énergie). Un capteur actif couvre toutes les cibles situées dans son périmètre de couverture (dont le rayon est connu), de plus il peut communiquer avec d'autres capteurs dans un périmètre de communication (dont le rayon est connu). Une base de réception est déployée sur la zone afin de recueillir l'information collectée. Le réseau de capteurs cesse de remplir sa fonction dès qu'une cible n'est plus couverte par un capteur actif. L'objectif du problème est de décider, à tout instant, de l'état de chaque capteur (inactif, relais ou surveillance), de manière à couvrir toutes les cibles et assurer la connectivité à la base, tout en cherchant à maximiser la durée de vie du réseau.</p> <p align="JUSTIFY">Nous proposons trois approches exactes pour résoudre le problème. Celles ci sont basées sur une modélisation PL en génération de colonnes. Le problème auxiliaire est résolu dans un premier temps par un PL pur (avec Gurobi), puis dans un second temps par une décomposition de Benders. Enfin, une approche PPC (Programmation Par Contraintes) est proposée. Des benchmarks sont proposés.