Optimisation de l'allocation de ressources dans un réseau de télécommunications par coloration impropre de graphes

Dans cette thèse, nous traitons le problème d'allocation de ressources pour les réseaux de télécommunications, dont le développement ne cesse de s'intensifier tant la demande en transmission de données est élevée à travers le monde. Malheureusement, ces ressources sont limitées et il devient de plus en plus difficile de satisfaire les besoins des utilisateurs, d'où l'intérêt de mettre en oeuvre des méthodes mathématiques adaptées à cette problématique. De telles techniques ont été développées depuis l'apparition des premiers réseaux dans les années 1970, mais l'évolution de la technologie sans fil et l'amélioration des puissances de calculs informatiques nécessitent de constamment mettre à jour les modèles utilisés, ainsi que les méthodes pour les résoudre; cette thèse s'inscrit dans cette dynamique. Nous proposons ici un nouveau modèle d'assignation de canaux qui suppose l'existence d'une entité capable de centraliser les données recueillies au niveau des usagers, à l'échelle métropolitaine. En particulier, nous proposons de maximiser le nombre d'usagers pouvant être connectés simultanément au réseau. Nous verrons en quoi ce modèle est nouveau mais tout à fait réaliste compte tenu des modèles existants. L'un des aspects originaux de cette thèse est le fait de remettre la théorie des graphes au goût du jour pour traiter ce problème d'affectation. Les notions de stabilité et de coloration impropre sont en effet intimement liées à ce problème. Nous verrons également qu'une généralisation de la fonction de Lovasz permet de dériver une borne supérieure sur l'objectif, plus serrée que la relaxation linéaire du modèle en nombres entiers associé. La théorie des graphes est un outil de modélisation très puissant, intimement liée à l'algorithmique inhérente aux problèmes combinatoires complexes. Nous verrons comment prendre à contre-pied l'explosion combinatoire de ce problème NP-difficile sans compromettre la qualité des solutions obtenues, en généralisant les notions de degré et de degré de saturation d'un sommet, à la base des heuristiques de coloration les plus populaires. Les algorithmes développés seront analysés théoriquement via les notions de complexité, de garantie et de plus petit graphe sous-optimal, mais aussi numériquement: ceux-ci seront comparés aux méthodes d'affectation classiques, à savoir la réutilisation de fréquence fractionnée. Enfin, nous étendrons le modèle proposé sur un horizon de temps, et traiterons le problème lorsque les données ne sont pas entièrement connues à l'avance mais apparaissent au fur et à mesure. En résumé, réseaux de télécommunications, théorie des graphes, algorithmique et explosion combinatoire sont les ingrédients principaux de cette thèse: il s'agit bel et bien de recherche opérationnelle!