Description
Date depot: 1 janvier 1900
Titre: Optimisation de la couverture d'un réseau de télécommunications par des boucles SDH
Directeur de thèse:
Philippe CHRÉTIENNE (LIP6)
Directeur de thèse:
Pierre FOUILHOUX (LIPN)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
La conception de réseaux de télécommunications est une problématique
cruciale pour les compagnies qui offrent des services informatiques aux
entreprises de hautes technologies. Enormément de moyens ont été investis
durant les dernières décennies pour permettre des communications
informatiques internes et des accès au réseau internet à des quartiers
d'affaires dans les grandes agglomérations. Ces réseaux ont naturellement
respectées des critères de qualité élevés: utilisation massive de fibres
optiques, réservation d'une ressources spécifique à un seul client,
électronique de haute sécurité,... D'autre part, ces réseaux ont
systématiquement respecté des exigences topologiques fortes,
principalement pour mettre en place une fiabilité réelle, c'est-à-dire la
résistance aux pannes en cas de rupture d'un câble: ce qui a poussé à
l'utilisation d'une topologie de boucles SDH.
Néanmoins l'absence de réelle concurrence durant ces décennies n'a pas
permis l'émergence d'une réflexion sur l'optimisation de ces réseaux.
Ainsi les raccordements et le placement des réseaux dépend essentiellement
de l'historique des commandes de racccordement des nouveaux clients. La
conjoncture économique actuelle amène ces entreprises à se soucier
d'optimiser leurs réseaux.
Une première étude menée sur cette problématique a permis de faire émerger
plusieurs problèmes d'optimisation combinatoire nouveaux. En particulier,
l'étude menée durant cette thèse s'intéressera au problème suivant. Etant
donné un graphe représentant un réseau câblé en fibres optiques sur une
agglomération, on considère parmi les sommets du graphe des clients qui
doivent être reliés par des boucles (technologie SDH) passant par des
sommets concentrateurs (home node). Ces boucles correspondent à des fibres
optiques associées à une technologie fixée par la demande spécifique des
clients. Ainsi les boucles doivent relier certains sous-ensembles de
clients dans la limite de capacité induite par la technologie
correspondante. De plus, la somme des capacités des boucles passant par un
même câble est limitée par la capacité totale du câble. Ce problème se
ramène en fait au problème du VRP (Vehicle Routing Problem) avec des
contraintes de capacité particulière. Ce problème connait depuis quelques
années un regain d'intérêt notable grâce à de nouvelles formulations
mathématiques en programmation linéaire en nombres entiers. L'objectif
premier de ces travaux sera d'étudier une approche polyèdrale dédiée à ce
nouveau problème.
Doctorant.e: Questel Aurelien Charles