Recherche Tabou Robuste pour l'allocation de fréquences

National audience1. Problématique : depuis le démarrage des réseaux cellulaires (2G, 3G, 3.5G), les opérateurs configuraient manuellement la gestion des paramètres réseau. Avec l'apparition des réseaux 4G/LTE, la notion de Self-Organizing Network (SON) a vu le jour. Les SON introduisent des fonctions avancées de paramétrage automatique du réseau en fonction de la demande. Grâce à cette technologie, les opérateurs peuvent désormais améliorer la flexibilité et les performances du réseau en réduisant les coûts d'exploitation. Notre objectif est de proposer des solutions algorithmiques pouvant s'appliquer au SON. 2. Méthodologie : le problème d'allocation de fréquences est NP-difficile car il s'agit d'un problème de coloration de graphe. En raison de la complexité du problème, nous utilisons la méthode de Recherche Tabou qui permet de proposer des solutions non optimales mais dont le potentiel de trouver rapidement des solutions de qualité a été prouvé sur plusieurs problèmes combinatoires difficiles. Trois variantes de la méthode Tabou sont proposées : algorithme Tabou Simple (TS), algorithme Tabou dégradée Dernier Voisin (TDV) et algorithme Tabou dégradée Meilleur Voisin (TMV). Pour chacun des cas, une série de tests sera présentée. Les données utilisées proviennent d'un réseau réel GSM/UMTS. 3. Contribution : nous avons tenté d'apporter des réponses aux questions sur la sélection spatiale (où optimiser) et la sélection temporelle (quand optimiser) des stations du réseau à optimiser. De plus, compte tenu de l'incertitude sur les données d'entrée, nous avons mis au point une méthode d'optimisation robuste qui prend en compte des scénarios qui proviennent d'une journée de trafic. Un scénario est une distribution de la demande en trafic à un moment donné de la journée. Plusieurs scénarios nous permettent d'analyser différentes situations vis-à-vis des performances du réseau. Nous avons mesuré les performances des 3 variantes en considérant les mêmes scénarios et nous les avons comparées à une approche non robuste