<  Back to the Polytechnique Montréal portal

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

Romain Montagné

PhD thesis (2016)

[img]
Preview
Download (3MB)
Cite this document: Montagné, R. (2016). Optimisation de l’allocation de ressources dans un réseau de télécommunications par coloration impropre de graphes (PhD thesis, École Polytechnique de Montréal). Retrieved from https://publications.polymtl.ca/2112/
Show abstract Hide abstract

Abstract

RÉSUMÉ : 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!----------ABSTRACT : Since the 1970's wireless networks have constantly been striving to meet consumers increasing demands, while the necessary resources (electromagnetic frequencies) are becoming increasingly scarce. In this thesis, we address the problem of allocating a channel to a maximum number of mobiles, in order to maximize the number of users that are simultaneously connected to the network. This is a typical assignment problem, for which operations research provides the adequate tools. We propose a new model based on the existence of a calculator capable of dealing with data at a metropolitan scale. Although ambitious, this scheme remains realistic given the latest developments of cloud computing and virtualization technologies. Most importantly, part of the originality of this model is its link with graph theory. We will see how the concepts of stability and improprer weighted coloring are intimately related to the channel assignment problem. Also, we will show how a generalization of Lovasz's function can be used to derive an upper bound on the objective function, tighter than the linear relaxation of the associated integer model. As one knows, a graph theory approach is often related to combinatorics and its difficulties, namely the combinatorial explosion of any NP-hard problem. We will see how to cope with this aspect, at the crossroads between fundamental and applied research. In particular, we will generalize the concepts of degree and saturation degree of a vertex, which are essential components of most of the popular vertex coloring heuristics. The proposed algorithms are analyzed both theoretically - through computational complexity, performance guarantee and smallest suboptimal graphs -, and numerically: a set of test results are reported in which the heuristics are compared to classical allocation techniques based on fractional frequency reuse. Last but not least, the model is extended over a rolling horizon and on-line algorithms are proposed to tackle the problem when data is not known in advance but appears iteratively. In summary, wireless networks, graph theory, algorithms and combinatorial explosion are the main ingredients to this thesis, which definitely lies in the scope of operations research.

Open Access document in PolyPublie
Department: Département de mathématiques et de génie industriel
Dissertation/thesis director: Alain Hertz and François Gagnon
Date Deposited: 13 Jul 2016 13:28
Last Modified: 27 Jun 2019 16:48
PolyPublie URL: https://publications.polymtl.ca/2112/

Statistics

Total downloads

Downloads per month in the last year

Origin of downloads

Repository Staff Only