Anaïs Vergne présente ses travaux sur la topologie algébrique appliquée aux réseaux de capteurs

(3/4) Notre série de présentation des quatre thèses lauréates du programme Futur et Ruptures de l’Institut Mines-Télécom se poursuit avec Anaïs Vergne. Ses travaux, menés à Télécom ParisTech, répondent au problème d’économie d’énergie dans les réseaux de capteurs. D’autre part, des applications aux réseaux cellulaires de nouvelle génération en sont dérivées : auto-configuration, ajustement au trafic utilisateur, et rétablissement après un désastre.

Titre de la thèse
Topologie algébrique appliquée aux réseaux de capteurs

Résumé
La qualité de service attendue d’un réseau de capteurs est sa topologie. Cette dernière comprend à la fois sa connectivité, i.e. si tous les capteurs sont reliés entre eux ou non, et sa couverture, i.e. si chaque zone d’un espace donné est « couverte » par un capteur ou non. Or le déploiement aléatoire de ce type de réseau ne permet pas de vérifier de manière immédiate sa topologie. La topologie algébrique fournit une description mathématique de celle-ci. Un réseau de capteurs est alors représenté par un complexe simplicial pour lequel il est possible de calculer son nombre de composantes connexes, et son nombre de trous de couverture, caractérisant sa topologie.

En partant de cette représentation pour les réseaux de capteurs, nous nous sommes intéressés au problème d’économie d’énergie. En effet, les capteurs sont déployés en masse au sein d’un réseau afin d’en garantir la topologie. Mettre en veille certains capteurs de manière aléatoire économiserait l’énergie, mais pourrait compromettre la qualité de service du réseau. Nous proposons un algorithme qui permet de savoir quels capteurs mettre en veille sans altérer la qualité de service du réseau. Il s’agit donc d’un algorithme de réduction pour complexes simplicaux sans modification de sa topologie. Nous utilisons la représentation par complexes simpliciaux non seulement pour calculer la topologie du réseau, mais aussi pour avoir un ordre optimisé pour la mise en veille des capteurs. La configuration finale obtenue est optimale : tous les capteurs conservés sont nécessaires au maintien de la qualité de service du réseau. Puis, le calcul de la complexité de l’algorithme a conduit à l’étude de la taille de la plus grande clique d’un graphe géométrique aléatoire. Nous avons obtenu son comportement asymptotique presque sûr dans chacun des trois régimes de percolation du graphe.

Dans un second temps, nous nous sommes intéressés à l’utilisation de la représentation par complexes simpliciaux et de notre algorithme de réduction pour les réseaux cellulaires. En effet, ceux-ci partagent avec les réseaux de capteurs le fait d’avoir la couverture comme qualité de service. Nous proposons trois algorithmes dérivés qui répondent à trois problématiques spécifiques des réseaux cellulaires du futur. Tout d’abord, le premier algorithme permet la configuration des réseaux cellulaires auto-organisés (réseaux bénéficiant de la technologie SON) avec la planification automatique des fréquences attribuées à chaque cellule. Le second sert à l’optimisation de ces mêmes réseaux en prenant en compte non seulement la topologie du réseau mais aussi son trafic utilisateur. Enfin, le dernier algorithme permet le rétablissement d’un réseau cellulaire endommagé par une catastrophe naturelle grâce à l’ajout de nouveaux nœuds. Ceux-ci sont ajoutés selon un processus ponctuel répulsif, dont la simulation est inédite pour les réseaux, qui permet d’obtenir une couverture homogène. Enfin, l’utilisation de l’algorithme de réduction permet d’atteindre un résultat optimal.

Lire les 3 autres billets présentant les thèses lauréates du programme Futur et Ruptures
(1/4) Amine Ben Salem présente ses travaux sur les nanofils photoniques
(2/4) Olivier Morillot présente ses travaux sur la reconnaissance de textes manuscrits
(4/4) Xuran Zhao présente ses travaux sur la réduction de dimensionnalité multivue pour la biométrie multimodale

En savoir + sur le programme Futur et Ruptures