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.