L’optimisation bayésienne au service de l’amélioration des performances du WiFi

Le WiFi est la technologie privilégiée pour nous relier sans fil à Internet. Présente à la maison ou au travail, elle fait également de plus en plus partie des services offerts par les lieux publics. Elle se déploie en installant des points d’accès (ou AP pour access point), qui transmettent les informations venues d’Internet à leurs utilisateurs grâce à des ondes électromagnétiques émises à une certaine puissance d’émission. Pour limiter les interférences, le WiFi oblige les AP à être « polis » : avant d’émettre, chaque AP se doit d’écouter son canal radio, et de reporter son émission si la puissance reçue y est supérieure à un seuil appelé la sensibilité. Lorsqu’un AP reporte son émission parce qu’un autre occupe le canal, les deux sont dits « en conflit » et leurs performances s’en trouvent impactées.

Des performances dégradées sont souvent signe d’un nombre important de conflits au sein du réseau, mais les éliminer n’est pas simple. Face à la diversité des topologies possibles et de la complexité inhérente à la propagation des signaux, il est difficile de décrire les performances des AP en fonction de leurs paramètres (puissance et sensibilité), si bien qu’encore aujourd’hui, les paramètres des AP sont maintenus constants ou mis à jour selon des algorithmes très simples.

Ainsi, Anthony Bardou, et Thomas Begin, tous deux membres du LIP, proposent INSPIRE, un algorithme distribué déployable sur chaque AP. Basé sur des processus gaussiens, INSPIRE permet à chaque AP de se construire, par essai-erreur, une représentation de ses performances en fonction de ses paramètres, qui s’affine à chaque nouveau test grâce au théorème de Bayes. Dans un souci d’altruisme, chaque AP interagit avec les AP présents dans son voisinage proche et cherche à maximiser leurs performances en leur recommandant des valeurs pour leurs paramètres.

Ces échanges de recommandations conduisent chaque AP à recevoir plusieurs configurations de ses propres paramètres pour effectuer son prochain test. Chaque AP agrège alors les configurations reçues en un consensus obtenu par médiane marginale. Les chercheurs montrent que, sous certaines hypothèses de régularité, le consensus ainsi calculé est optimal dans le pire cas, une garantie théorique appelée minimax optimal.

INSPIRE parvient à identifier des zones dans l’espace des configurations où les performances sont les plus élevées, et concentre ses futures requêtes dans ces zones. Il obtient alors rapidement des performances significativement meilleures que l’existant, comme le montrent les résultats suivants (obtenus par simulation sur deux topologies), qui comparent les performances d’INSPIRE à celles de la configuration par défaut des topologies (DEFAULT) ou d’autres stratégies d’optimisation.

Ces travaux proposent un algorithme capable de se construire, par requêtes successives, une représentation des performances du réseau en fonction de certains paramètres-clés. Cette faculté permet de proposer une méthode distribuée offrant des garanties théoriques d’optimalité dans le pire cas, sans faire d’hypothèses coûteuses sur les topologies réseaux considérées. Les résultats obtenus en simulant plusieurs topologies attestent de l’efficacité d’INSPIRE, qui dépasse significativement les performances des stratégies constituant l’état de l’art.