Modélisation à l’aide de jeux quantitatifs

Théorie des jeux et réseaux de capteurs

Application au domaine de la sécurité

Nous avons évoqué la théorie des jeux au chapitre 3, en nommant certains outils de modélisation utilisés pour implémenter les méthodes de détection d’intrusion. Il semble utile à ce stade de fournir davantage d’éléments sur les liens qui rattachent cet outil à la sécurité des réseaux de capteurs sans fil. La théorie des jeux est un ensemble d’outils permettant l’analyse de situations données, les « jeux », où les décisions prises par chaque entité (ou « joueur ») se basent sur l’anticipation des décisions des autres joueurs. Ces outils servent dans un premier temps à modéliser le jeu étudié, et consistent ensuite à résoudre des problèmes tels que la recherche d’équilibres ou de solutions optimales dans le jeu.

La théorie des jeux est très fréquemment utilisée en économie. Elle intervient aussi régulièrement en politique, en biologie ou même en philosophie. Lui font appel, de manière plus ponctuelle, de nombreux autres domaines, dont l’informatique. Appliquée aux réseaux de capteurs, une étude classe la théorie des jeux selon trois approches : les performances énergétiques, la sécurité, et les jeux de poursuiteévasion [85].

Les jeux de poursuite-évasion impliquent un ensemble de joueurs mobiles qui tentent de « capturer » un second ensemble de nœuds, d’en optimiser le suivi ; les agents du second groupe, pour leur part, cherchent à éviter de se faire détecter. Les deux autres catégories parlent d’elles-mêmes : les jeux appliqués aux performances énergétiques recherchent des solutions optimales permettant de minimiser la consommation, que ce soit en agissant sur la topologie du réseau ou bien sur le comportement des nœuds [29].

En sécurité, bien entendu, les jeux opposent les capteurs « normaux » aux agents attaquant de l’extérieur ou bien (dans le cas de nœuds corrompus) de l’intérieur du réseau. Dans une seconde étude plus récente, les jeux de poursuite-évasion ne constituent qu’un élément d’une catégorie plus large regroupant les « applications » des capteurs (et comprenant aussi la collecte de données, par exemple). De même, les performances énergétiques ont été divisées en deux catégories, à savoir la gestion du réseau (ressources, énergie) et des communications (qualité de service, topologie, structure de routage) [114].

Jeux quantitatifs, tours de jeux

Notre approche se distingue des travaux existants, dans le sens où l’arrêt potentiel (dû à l’épuisement de la batterie) est inclus dans les contraintes du jeu, en parallèle aux valeurs de gain. Pour autant que nous sachions, les travaux portant sur des configurations similaires considèrent toutes les dimensions comme étant soit liées à l’énergie, soit au gain, et traitent uniquement des conjonctions d’atomes [26, 131]. Dans de tels cas, les algorithmes sont établis sur une même structure : l’objectif du jeu est décomposé selon les dimensions établies, et l’on cherche pour chacune de ces dimensions une stratégie gagnante à mémoire finie.

Ces stratégies sont ensuite combinées pour obtenir une stratégie globale pour le problème, qui elle peut éventuellement nécessiter une mémoire infinie. D’autres analyses [130] traitent d’objectifs plus complexes basés sur la combinaison d’objectifs portant sur le gain moyen, en utilisant les opérateurs somme, max et min. Dépassant le cadre de nos travaux, on trouve aussi l’étude de jeux comportant à la fois des conditions sur le gain et un objectif de parité (où pour remporter la victoire, un joueur a besoin d’accéder au gain maximum qui sera récolté à l’infini sur le chemin, infini lui aussi, qui représente le déroulement de la partie) [25].

Dans ce cas l’objectif de parité assure que le système se comporte de façon cohérente, tandis que le gain représente un but quantitatif plus concret. Les stratégies gagnantes pour ces jeux peuvent nécessiter une mémoire infinie, mais il est possible d’en obtenir une approximation exécutable avec une mémoire finie.

Ce type de jeux ne convient néanmoins pas parfaitement pour modéliser les réseaux de capteurs, car ils laissent de côté l’énergie, qui est un paramètre essentiel de notre contexte de travail. Nous cherchons donc à combiner plusieurs objectifs, qui portent à la fois sur une valeur de gain et sur l’énergie restante dans la batterie des capteurs. Traditionnellement, un jeu se déroule tour par tour : chaque joueur joue sur son tour, puis laisse jouer ses concurrents (ou ses alliés selon le cas) ; il nous faut également composer avec cette contrainte, par exemple en définissant des intervalles de temps au cours desquels chaque joueur possède une action à réaliser