Recherche Tabou Robuste pour l'allocation de fréquences

1. Problematique : depuis le demarrage des reseaux cellulaires (2G, 3G, 3.5G), les operateurs configuraient manuellement la gestion des parametres reseau. Avec l'apparition des reseaux 4G/LTE, la notion de Self-Organizing Network (SON) a vu le jour. Les SON introduisent des fonctions avancees de parametrage automatique du reseau en fonction de la demande. Grâce a cette technologie, les operateurs peuvent desormais ameliorer la flexibilite et les performances du reseau en reduisant les couts d'exploitation. Notre objectif est de proposer des solutions algorithmiques pouvant s'appliquer au SON. 2. Methodologie : le probleme d'allocation de frequences est NP-difficile car il s'agit d'un probleme de coloration de graphe. En raison de la complexite du probleme, nous utilisons la methode de Recherche Tabou qui permet de proposer des solutions non optimales mais dont le potentiel de trouver rapidement des solutions de qualite a ete prouve sur plusieurs problemes combinatoires difficiles. Trois variantes de la methode Tabou sont proposees : algorithme Tabou Simple (TS), algorithme Tabou degradee Dernier Voisin (TDV) et algorithme Tabou degradee Meilleur Voisin (TMV). Pour chacun des cas, une serie de tests sera presentee. Les donnees utilisees proviennent d'un reseau reel GSM/UMTS. 3. Contribution : nous avons tente d'apporter des reponses aux questions sur la selection spatiale (ou optimiser) et la selection temporelle (quand optimiser) des stations du reseau a optimiser. De plus, compte tenu de l'incertitude sur les donnees d'entree, nous avons mis au point une methode d'optimisation robuste qui prend en compte des scenarios qui proviennent d'une journee de trafic. Un scenario est une distribution de la demande en trafic a un moment donne de la journee. Plusieurs scenarios nous permettent d'analyser differentes situations vis-a-vis des performances du reseau. Nous avons mesure les performances des 3 variantes en considerant les memes scenarios et nous les avons comparees a une approche non robuste.