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 auxiliaire 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 parallè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, comparativement à l'optimum.
Les travaux de thèse de A.K. Idrees que j'ai co-encadré traitent eux aussi du problème de couverture et d'efficacité énergétique dans un réseau de capteurs sans fil. Nous avons étudié des protocoles d’optimisation distribués avec l’objectif de prolonger la durée de vie du réseau. Pour résoudre le problème, nous avons proposé de nouvelles approches articulées en deux phases. Dans un premier temps, la région à surveiller est divisée en petites sous-régions en utilisant le concept de la méthode diviser pour mieux régner. Ensuite, l’un de nos protocoles d’optimisation distribués est exécuté par chaque nœud capteur dans chaque sous-région, afin d’optimiser la couverture et la durée de vie du réseau. Nous proposons trois protocoles distribués qui combinent, chacun, deux techniques efficaces : l'élection d’un nœud leader dans chaque sous-région, suivie par la mise en œuvre par celui-ci d’un processus d’ordonnancement d’activité des nœuds capteurs de sa sous-région. Cet ordonnancement est porté par la formulation et la résolution de programmes linéaires. Pour les deux premiers protocoles, il s’agit de minimiser simultanément la non couverture ou la sur-couverture d’un ensemble de points particuliers. Pour le troisième protocole, le nouveau modèle propose repose sur la couverture du périmètre de chacun des capteurs. Nous avons effectué plusieurs simulations en utilisant le simulateur à événements discrets OMNeT++ pour valider l’efficacité de nos protocoles proposés. Nous avons pris en considération les caractéristiques d’un capteur Medusa II pour la consommation d’énergie et le temps de calcul. En comparaison avec deux autres méthodes existantes, nos protocoles ont la capacité d’augmenter la durée de vie du réseau de capteurs et d’améliorer les performances de couverture.
La plupart des travaux présents dans la littérature considère des réseaux de capteurs homogènes avec les mêmes caractéristiques (même batterie, même portée de couverture, même capacité de calcul,...). En réalité, un réseau peut contenir des capteurs hétérogènes. Notamment, le niveau d’énergie initial de la batterie et la consommation d’énergie peut varier d’un capteur à l’autre.
Il existe aussi des applications pour lesquelles les besoins en couverture peuvent être réduits. On parle alors de α-couverture pour α ∈ ]0, 1]. La couverture complète, c’est-à-dire la couverture de toutes les cibles, correspond au cas particulier α = 1. Suivant les besoins de l’application, différentes stratégies d’α-couverture sont envisageables.
Dans la thèse de R. Haj Mansour, nous souhaitons proposer plusieurs modèles d’optimisation et des heuristiques de résolution pour ces différents cas (hétérogénéité et couverture partielle) en utilisant des outils de modélisation et de résolution issus de la programmation linéaire. Les premiers travaux réalisés durant la première année concernent la couverture totale dans un réseau hétérogène. Nous avons formulé un programme linéaire mixte en nombres entiers qui permet d’obtenir un nombre maximal d’ensembles couvrants dans ce cas, et nous avons développé une méthode de résolution approchée reposant sur un algorithme génétique pour traiter les problèmes de grande taille.
Les travaux réalisés durant la deuxième année concernent la couverture partielle dans un réseau hétérogène. Nous avons formulé un programme linéaire en nombres entiers pour résoudre le problème de la couverture partielle dans un réseau hétérogène. Ce programme permet de générer un nombre maximal d’ensembles couvrants partiels non-disjoint avec des durées d’activation fixe. A la différence des autres approches proposées, notre modèle inclut une nouvelle contrainte qui force un taux minimal de couverture pour chacune des cibles sur la durée de vie total du réseau. En couverture partielle, chaque cible n’est pas couverte en continu, nous avons cherché une planification/ordonnancement des ensembles couvrants afin de distribuer au mieux les périodes de couverture et de non couverture de chacune des cibles. Ce problème de planification a été formulé et résolu à partir d’un algorithme génétique .
Notre challenge pour la troisième année de thèse est de généraliser notre modèle à des ensembles couvrants connectés à durée d’activation variable.