Planification globale des réseaux mobiles de la quatrième génération (4G)

Dans le contexte actuel où l'information est la clé du succès, peu importe le domaine où l'on se place, les réseaux de télécommunications sont de plus en plus sollicités. D'énormes quantités d'informations circulent sur les réseaux à chaque seconde. Il est primordial d'assurer la disponibilité de ces réseaux afin de garantir la transmission de ces données en toutes circonstances. Le problème de la planification des réseaux de télécommunications consiste à déterminer, parmi un ensemble de sites potentiels, ceux à utiliser afin de couvrir une zone géographique donnée. Il convient également de choisir les équipements à installer sur ces sites et de faire le lien entre eux en fonction de certaines contraintes bien définies. Depuis des dizaines d'années, plusieurs auteurs se sont penchés sur la résolution de ce problème dans le but de minimiser le coût d'installation du réseau. Ces auteurs se sont intéressés à divers aspects du problème sans le considérer dans sa globalité. Certaines études ont été effectuées récemment sur la planification globale des réseaux mobiles. Les auteurs se sont intéressés aux réseaux de la troisième génération et ont proposé un modèle pour résoudre le problème de façon globale. Cependant, ils n'ont pas pris en compte la tolérance du réseau aux pannes qui pourraient survenir. Cette thèse propose un cadre de planification globale pour les réseaux de la quatrième génération (la nouvelle génération des réseaux mobiles). La survivabilité du réseau est prise en compte dans cette étude. Le travail a été effectué en trois phases. Dans la première phase, un modèle global incluant la tolérance aux pannes a été conçu pour la planification des réseaux 4G (WiMAX) et résolu de manière optimale avec un solveur mathématique, en utilisant la programmation linéaire en nombres entiers. L'objectif du modèle consiste à minimiser le coût du réseau, tout en maximisant sa survivabilité. Afin de montrer la pertinence de la résolution globale, le modèle a été comparé à un modèle séquentiel avec les mêmes contraintes. Le modèle séquentiel consiste à subdiviser le problème en trois sous-problèmes et à les résoudre successivement. Un modèle global qui n'intègre pas les contraintes de fiabilité a également été conçu afin de vérifier l'effet des pannes sur le réseau. Les résultats obtenus par le modèle global proposé sont, en moyenne, 25% meilleurs que ceux des deux autres modèles. Le problème de planification globale des réseaux et le problème de survivabilité des réseaux de télécommunications sont deux problèmes NP-difficiles. La combinaison de ces deux problèmes donne un problème encore plus difficile à résoudre que chacun des problèmes pris séparément. La méthode exacte utilisée dans la première phase ne peut résoudre que des instances de petite taille. Dans la deuxième phase, nous proposons une métaheuristique hybride afin trouver de "bonnes solutions" en un temps "raisonnable" pour des instances de plus grande taille. La métaheuristique proposée est une nouvelle forme d'hybridation entre l'algorithme de recherche locale itérée et la méthode de programmation linéaire en nombres entiers. L'hybridation de ces deux méthodes permet de bénéficier de leurs avantages respectifs, à savoir l'exploration efficace de l'espace de recherche et l'intensification des solutions obtenues. L'intensification est effectuée par la méthode exacte qui calcule la meilleure solution possible à partir d'une configuration donnée tandis que l'exploration de l'espace est faite à travers l'algorithme de recherche locale itérée. Les performances de l'algorithme ont été évaluées par rapport à la méthode exacte proposée lors de la première phase. Les résultats montrent que l'algorithme proposé génère des solutions qui sont, en moyenne à 0,06% des solutions optimales. Pour les instances de plus grande taille, des bornes inférieures ont été calculées en utilisant une relaxation du modèle. La comparaison des résultats obtenus par l'algorithme proposé avec ces bornes inférieures montrent que la métaheuristique obtient des solutions qui sont, en moyenne à 2,43% des bornes inférieures pour les instances qui ne peuvent pas être résolues de manière optimale, avec un temps de calcul beaucoup plus faible. La troisième phase a consisté à la conception d'une métaheuristique multi-objectifs pour résoudre le problème. En effet, nous essayons d'optimiser deux objectifs contradictoires qui sont le coût du réseau et sa survivabilité. L'algorithme proposé permet d'offrir plus d'alternatives au planificateur, lui donnant ainsi plus de flexibilité dans la prise de décision.

Abstract

In the current context where information is the key to success in any field where one stands, telecommunications networks are increasingly in demand. Huge amounts of information circulates on the networks every second. It is essential to ensure the availability of these networks to ensure the transmission of these data at any time. The problem of planning of telecommunication networks is to determine, from a set of potential sites, those to be used to cover a given geographical area. One should also choose the equipment to be installed on these sites and to link them according to certain well-defined constraints. For decades, several authors have focused on solving this problem in order to minimize the cost of network installation. These authors were interested in various aspects of the problem without considering it in its entirety. Some studies have recently been performed on the global planning of mobile networks. The authors were interested in the third generation networks. They proposed a model to solve the problem entirely, without breaking it down into sub-problems. However, they did not take into account the fault tolerance of network. This thesis proposes a global planning framework for the fourth generation (4G) networks (the new generation of mobile networks). The survivability of the network is taken into account in this study. The work was conducted in three phases. In the first phase, a global model including survivability has been designed for the planning of 4G (WiMAX) networks and solved optimally with a mathematical solver using the integer linear programing method. The objective of the model is to minimize the network cost while maximizing its survivability. To show the relevance of the global resolution, the model was compared to a sequential model with the same constraints. The sequential model is to divide the problem into three sub-problems and solve them successively. A global model which does not include survivability constraints has also been designed to test the effect of failures on the network. The results show that the proposed model performs on average 25% better than the two other models. The problem of global network planning and the problem of survivability of telecommunications networks are two NP-hard problems. The combination of these two problems provides a problem even more difficult to solve than each problem taken separately. The exact method used in the first phase can only solve small instances. In the second phase, we propose a hybrid metaheuristic to find `good solutions' in a `reasonable time' for instances of larger size. The proposed metaheuristic is a new form of hybridization between the iterated local search algorithm and the integer linear programing method. The hybridization of these two methods can benefit from their respective advantages, namely the efficient exploration of the search space and the intensification of the solutions obtained. The intensification is performed by the exact method that calculates the best possible solution from a given configuration while the exploration of the search space is made through the iterated local search algorithm. The performance of the algorithm have been evaluated with respect to the exact method given in the first phase. The results show that the proposed algorithm generates solutions that are on average 0,06% of the optimal solutions. For the larger instances, the lower bounds are calculated using a relaxation of the model. The comparison of the results obtained by the proposed algorithm with the lower bounds show that the metaheuristic obtains solutions that are on average 2,43% from the lower bounds, for the instances that cannot be solved optimally, within a much less computation time. The third phase involved the design of a multi-objective metaheuristics to solve the problem. Indeed, we try to optimize two conflicting objectives which are the cost of network and its survivability. The proposed algorithm allows us to offer more alternatives to the planner, giving him (her) more exibility in the decision making process.