Seminar
Date : Nov. 15, 2018, 2 p.m. - Room :Amphi Garcia
Méthode exacte 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, Maître de conférences - LIRMM Montpellier |
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 présentons une approche exacte pour résoudre le problème. Celle ci est basée sur une modélisation PL (Programmation Linéaire) en génération de colonnes où le problème auxiliaire est résolu par une approche PPC (Programmation Par Contraintes) par l’utilisation judicieuse de variables de graphes.