Recherche théorique sur la coloration de graphes – Application aux systèmes de communication radio 4G (LTE) dans son contexte
Jianding Guo sous la direction de Alexandre Caminada, Jean-Noël Martin et Laurent Moalic
The theoretical studies on optimization algorithms known as « No Free Lunch » have shown that problem features and algorithms are hugely linked. By studying the graph coloring problem, it is showed that graphs embed properties can be used to find new algorithm for class coloring counting, for constraint satisfaction, for infeasible subset search, etc. It is proposed to follow these works on several new directions such as the characterization of maximal cliques, the study of k-improper coloring, the use of constructive series to represent graphs, the parallelization of k-coloring class computation and the analysis of main heuristics on graphs. Concerning the application to radio communication networks, the work will emphasize on dimensioning, planning and analysis of LTE networks and optimization of the networks under traffic, technical and economical conditions. In the future, LTE is promising to be the main standard for Vehicle-to-Vehicle and Vehicle-to-Road high speed communications which is a major requirement for ITS (Intelligent Transport System). The main link between graph coloring and the 4G digital LTE network concerns resources allocation on frequency planning for OFDMA technology. The main problem is the dimensioning and the distribution of frequency resources to the resource blocks in the way of minimizing interference and maximizing the throughput.