Les problèmes d'optimisation dans les réseaux de capteurs

 

Un réseau de capteurs / microcapteurs est un ensemble coopérant de noeuds capteurs utilisant des communications sans fil dans le cadre d'un réseau ad-hoc. Chaque noeud comporte un capteur permettant d'observer un phénomène se produisant à proximité. Cette technologie de micro-capteurs a ouvert de nouvelles perspectives applicatives variées dans de nombreux domaines (militaires, domotiques, environnementales, etc.). Cependant, son exploitation reste difficile et pose beaucoup de problèmes. Les difficultés se situent au niveau algorithmique, localisation, déploiement, collecte/fusion de données, ainsi que la couverture et la réduction de la consommation d'énergie pour maximiser la durée de vie du réseau. En effet, la seule source d’énergie d’un nœud capteur est sa batterie à durée de vie déterminée. Et le réseau doit assurer ses fonctions avec la quantité d’énergie dont il dispose sans l’intervention de l’opérateur qui l’a déployé.


J'ai proposé 2 méthodes centralisées de planification des périodes de réveil des capteurs. Dans le premier cas, il s'agit de construire des ensembles non-disjoints de capteurs capables de surveiller l'intégralité des cibles et de planifier leurs réveils successifs. Le problème peut se formuler sous forme d'un programme linéaire avec un nombre de variables qui augmente de manière exponentielle avec le nombre de capteurs et de cibles. Pour faire face à un nombre croissant de variables, j'utilise une méthode de génération de colonnes, qui nécessite la résolution d'un programme auxiliaire en nombre entiers. Ce problème auxiklaire est résolu, soit de manière exacte avec un algorithme type Branch and Bound , soit avec une heuristique gloutonne. Les résultats obtenus avec l'heuristique sont comparés à ceux obtenus avec la méthode exacte sur des instances de réseaux comportant entre 50 et 200 capteurs, et entre 30 et 120 cibles. Dans la quasi-totalité des cas testés, l'heuristique fournit une durée de vie égale à la durée de vie optimale.


Je me suis intéressée également au cas où les ensembles de capteurs doivent être disjoints. Pour ce cas de figure, j'ai développé une méthode heuristique de construction en parrallèle des différents ensembles. La répartition des différents capteurs dans les ensembles est guidée par la résolution d'un problème d'affectation linéaire. J'ai également proposé une méthode itérative qui permet, à partir de la borne fournie par l"heuristique, de trouver une solution optimale du problème. Cette méthode nécessite la résolution d'un problème en nombre entiers. J'ai ainsi pu vérifier, sur plusieurs configurations de capteurs et de cibles, la pertinence des résultats obtenus avec l'heuristique, comparitivement à l'optimum.