Proposition de sujet de stage

Collecte de données dans les réseaux de capteurs

Encadrement

Vincent Boudet, Sylvain Durand (LIRMM / Projet Algorithmique et Performances des Réseaux)

Mots clés

Capteurs, énergie, heuristiques, approximation.

Le problème

La gestion de l'énergie est un problème crucial dans le déploiement des réseaux de capteurs. Nous nous intéressons à la problématique de collecte de données et cherchons à maximiser la "durée de vie" du réseau. Une des solutions généralement adoptée pour collecter des données est la construction d'une épine dorsale (backbone) i.e. d'un ensemble dominant connexe. Pour tenter de maximiser la durée de vie du réseau, un des objectif peut être alors de chercher un ensemble de q backbones tels qu'un capteur appartienne à au plus p backbones.

Ce problème est bien sûr difficile. Les question que nous nous poserons sont :

Existence de l'ensemble de backbones ?
Conditions minimales pour qu'une solution réalisable existe ?
Construction de cet ensemble ?
Résultats d'approximation pour des instances particulières (contraintes relachées, topologie imposée, ...)
Cas distribué (chaque capteur n'a qu'une vision locale du réseau) ?