Wednesday 26
Constraint programming and artificial intelligence
Simon de Givry
› 11:30 - 12:00 (30min)
› Bât A - TD 45
Méthodes exactes de résolution du problème de maximisation de durée de vie d'un réseau de capteurs avec prise en compte de contraintes de connectivité
Eric Bourreau  2, 1, *@  , Marc Sevaux  2@  , Fabian Castaño  2, 3  , André Rossi  2  , Nubia Velasco  3  
2 : Université de Bretagne Sud - Lab-STICC  (UBS/Lab-STICC)  -  Website
Université de Bretagne Sud [UBS], CNRS : UMR6285
BP 92116 - 56321 Lorient cedex -  France
1 : Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier  (LIRMM)  -  Website
Université Montpellier II - Sciences et techniques, CNRS : UMR5506
CC 477, 161 rue Ada, 34095 Montpellier Cedex 5 -  France
3 : Universidad de los Andes, Departamento de Ingeniería Industrial  (UA)
* : Corresponding author

 

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.

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.


Online user: 1