Algorithmic methods for mono-objective and multi-objective optimization: Application to radio broadcasting networks
Méthodes algorithmiques pour l'optimisation mono-objectif et multi-objectif : application aux réseaux de radiodiffusion
Résumé
The purpose of my thesis is the dynamic construction of radio communication networks subject to multiple constraints and the optimal (if possible) use of the set of available frequencies at time t. This is an NP-Hard problem with important economical issues. I have designed and used original hybrid meta-heuristics for solving this kind of problems and providing the best possible QoS. Frequencies are rare and expansive therefore we can ask if a single frequency would not be enough, for a while, in order to cover the needs of a given geographical area. This would allow the use of the remaining frequencies for other applications. This is the principle of Single Frequency Networks (SFN) which necessitate the simultaneous optimization of transmission delays, of the allocated frequency and of their design. I have designed an original and e_cient software which performs these operations. We give experimental results for real benchmarks provided by TDF.
Ma thèse porte sur la configuration dynamique de réseaux de communication radio vérifiant un certain nombre de contraintes (ou objectifs) et l'utilisation, si possible optimale, de l'ensemble des fréquences disponibles à un instant donné. C'est un problème NP-difficile dont l'enjeu économique est important pour l'entreprise TDF. J'ai construit et mis en œuvre des méta-heuristiques hybrides originales pour résoudre ce type de problème et assurer la meilleure qualité de service (QoS) possible. Les fréquences étant une denrée rare et chère, on peut se demander si, pendant un certain temps, une seule fréquence ne suffirait pas pour couvrir les besoins d'un secteur géographique donné. Ceci permettrait d'utiliser les autres fréquences pour d'autres applications. C'est le principe de base des réseaux SFN (Single Frequency Network) qui nécessitent l'optimisation des délais de transmission, le regroupement de certains émetteurs pour construire un tel réseau et le choix de la fréquence à allouer. Du point de vue informatique, il s'agit de réaliser simultanément plusieurs optimisations. La structure d'un réseau SFN doit être ajustable au cours du temps. J'ai développé un logiciel qui réalise ces opérations, à savoir : - sélection des émetteurs pour construire des réseaux (i.e. plaques) SFN, - optimisation des écarts de transmission dans chaque SFN, - choix de la meilleure fréquence possible pour chaque SFN. Les performances de ces algorithmes sont comparées avec la QoS des plans de fréquences utilisés en France et des pays voisins. Les résultats obtenus sont encourageants.