Planification du réseau d'accès pour l'amélioration de la rentabilité de l'infrastructure d'un réseau FTTN

Étant donné l'offre de nouveaux services de réseau comme la télévision haute définition sur le protocole IP (Internet Protocol), de nouvelles architectures et technologies devraient être planifiées et introduites dans le réseau d'accès afin d'améliorer le taux d'accès. La meilleure solution est d'étendre le réseau de fibre jusqu'à l'abonné. Cependant, celle-ci est très coûteuse et ne peut être largement déployée de nos jours. Une alternative intéressante est la technologie FTTN (Fiber-to-the-node) qui réduit la portion de réseau utilisant le cuivre. Dans ce mémoire, on commence par présenter un modèle de programmation mathématique de réseau d'accès dans le but d'améliorer la rentabilité de l'infrastructure d'un réseau FTTN. Ce modèle consiste à trouver le nombre et la localisation des noeuds, et sélectionner les chemins qui seront utilisés d'un noeud à chaque point de demande. Le problème a des contraintes qui limitent la capacité des noeuds et la distance entre chaque point de demande et le noeud qui le dessert. Le but est de minimiser la somme du coût des paires de cuivre à installer et du coût d'installation des noeuds. Par la suite, la complexité du problème est analysée. Nous montrons que des instances du problème de grande taille ne peuvent être résolues de manière exacte dans un temps raisonnable, car le problème est NP-difficile. Nous proposons donc une heuristique basée sur la recherche taboue dans le but de trouver de bonnes solutions dans un temps raisonnable. Les résultats obtenus en utilisant l'heuristique taboue proposée sont comparés avec une borne inférieure obtenue en relâchant des contraintes du modèle mathématique. Celle-ci est calculée en utilisant le résolveur commercial CPLEX qui utilise l'algorithme d'évaluation et séparation. Des tests effectués avec des exemplaires du problème générés de façon aléatoire montrent que l'heuristique proposée donne des résultats satisfaisants. En effet, la moyenne des écarts est de 0,34 et le temps d'exécution est raisonnable.

Abstract

Considering the introduction of new Internet Protocol (IP) services, new architecture and network technologies should be designed and introduced for the access network to improve the access rate. Actually, the best solution is to extend the fiber network and use the fiber-to-the-home (FTTH) architecture. However, this solution is still too costly and cannot be widely deployed. An interesting alternative is the fiber-to-the-node (FTTN) architecture, which reduces the copper portion of the access network. In this document, an integer mathematical programming model is proposed for the access network design in order to improve the profitability of the FTTN infrastructure. It consists in finding the number and the location of the nodes, and selecting the way each point of demand will be connected with the node that is assigned to serve it. The problem has constraints that limit the nodes capacity and the distance between each point of demand and the node that is assigned to serve it. The goal is to minimise the cost of deploying the copper links and the cost of setting the nodes. The problem complexity will then be analysed. We show that large problem instances cannot be solved to the optimum in a reasonable amount of time because the problem is NP-hard. Next, we propose a heuristic based on the tabu search to find good solutions. The results of the tabu heuristic are compared to a lower bound found by solving a relaxed version of the model with CPLEX that uses the branch-and-bound algorithm. The heuristic was tested with randomly generated instances of the problem. The results show that the proposed heuristic finds good quality solutions.