2.3 Problème d'affectation de fréquences
(PAF)
La gestion efficace, du spectre de fréquences
disponibles, est d'une importance capitale pour les opérateurs des
systèmes de téléphonie cellulaire. Le coût
d'exploitation du réseau et par conséquent la marge de profit
dépendent en grande partie, de la capacité à
réutiliser de façon optimale les canaux.
Le principe fondamental de la téléphonie
cellulaire consiste à subdiviser l'espace desservi en un ensemble de
cellules ou zones géographiques, et à réutiliser, chaque
fois que les contraintes de compatibilité
électromagnétique le permettent, les mêmes canaux à
travers ces différentes cellules. Plus les canaux disponibles sont bien
utilisés, moins on investira pour de nouveaux équipements dans le
but d'éliminer des interférences potentielles, ou de pouvoir
desservir un plus grand nombre de clients.
Il y a quelques années, le problème
d'affectation de canaux se formulait comme un problème d'optimisation
avec pour objectif la minimisation du nombre de canaux distincts
utilisés ou la minimisation de la largeur de bande [Hale, 1981], [Hurley
et al, 1997]. Ces objectifs étaient appropriés parce qu'il
était encore possible d'assigner des fréquences sans engendrer
des interférences. Actuellement, il s'agit de trouver des solutions
acceptables en minimisant le niveau global d'interférence de
fréquences affectées. Dans ce cas on parle de problème
d'affectation de fréquences à spectre fixe (Fixed Spectrum
Frequency Assignment Problem FS-FAP). Le fait de garder les différents
types d'interférences, à un niveau minimal, conduit à un
faible taux de blocage des appels, une plus grande capacité en termes du
nombre de clients, une meilleure qualité de communication et des
économies en investissement pour de nouveaux équipements.
2.3.1 Problématique
Le problème d'allocation de fréquences (FS-FAP)
est classé dans la catégorie des problèmes NP-Complets
[Kunz, 1991], [Mathar et Mattfeldt, 1993]. Ce problème peut être
modélisé en un problème d'optimisation ayant la forme
suivante : étant donné une bande de fréquence [fmin,
fmax] subdivisée en un ensemble m de canaux (de même largeur
de bande z) numérotés de 1 à un nombre maximum m
donné, où m = (fmax
-fmin)/z et un ensemble de cellules auxquelles on doit
attribuer des fréquences, il s'agit de trouver une affectation qui
satisfait un ensemble de contraintes et qui minimise le niveau global
d'interférence des affectations de fréquences
proposées.
L'allocation de canaux, aux domaines cellulaires dans un
réseau radio mobile, est susceptible d'engendrer des
interférences radio de sources internes. Ces interférences
apparaissent entre deux canaux proches d'un point de vu spectral dans le
domaine fréquentiel et émettant à partir
d'émetteurs géographiquement proches. Les types
d'interférences internes considérées dans le
problème d'affectation de fréquences sont les suivantes :
Interférence co-cellule : représente
l'interférence entre deux canaux identiques alloués à la
même cellule.
Interférence co-canal : c'est l'interférence
entre deux cellules auxquelles on a alloué le même canal.
Typiquement, cette interférence décroît quand la distance
géographique entre les deux cellules croît;
Interférence du canal adjacent : c'est
l'interférence entre deux cellules adjacentes auxquelles on a
alloué des canaux proches l'un de l'autre dans le plan spectral.
Ces interférences peuvent être
représentées par une matrice appelée matrice de
compatibilités électromagnétiques C de taille m ×
m, oil n est le nombre de cellules dans un réseau. Les
éléments cij de la matrice indiquent la
contrainte de séparation spectrale des canaux alloués aux
cellules i et j. Les éléments diagonaux cii
de la matrice de la compatibilité représentent les
interférences co-cellules et les éléments non diagonaux
cij représentent soit les interférences
co-canal soit les interférences de canaux adjacents.
Du fait de la nature combinatoire du problème
d'affectation de fréquences, l'utilisation de méthodes de
recherche exactes "Hard Computing" s'avère inexploitable, en termes de
temps de calcul requis [Aardal et al, 1995], [Maniezzo et Montemanni, 1999]. De
ce fait, des techniques plus appropriées ont été
appliquées pour la résolution de ce problème. Ces
méthodes incluent la méthode de recherche par Tabou [Montemanni
et al, 2003], recuit simulé [Duque-Anton et al, 1993], algorithmes
génétiques [Crompton et al, 1994], réseaux de neurones
[Kunz, 1991], programmation dynamique [Shirazi et Amindavar, 2005], colonie de
fourmis [Alami et El Imrani, 2006], algorithmes culturels [Alami et El Imrani,
2007] et essaims particulaires [Benameur et al, 2009a].
Dans les paragraphes suivants, nous présenterons
l'implémentation d' algorithme d'optimisation discrète par
essaims particulaires (DPSO) adaptés à la résolution du
FS-FAP [Benameur et al, 2009b]. Les résultats de simulation, relatifs
aux différentes instances utilisées dans la littérature,
seront présentés et comparés ensuite avec d'autres
modèles.
| 
