RESOUDRE LE PROBLEME D’AFFECTATION DE FREQUENCES EN RESEAU MOBILE

Interférence Co-canal

         La réutilisation des fréquences augmente l‘efficacité du spectre du système cellulaire ; mais, il y a le risque d‘avoir l‘interférence due à l‘utilisation commune du même canal. Il peut se produire si le système n‘est pas bien planifié. Ce type d‘interférence est appelé interférence co-canal. L‘impact de la charge du trafic sur ce type d‘interférence est considérable. Sur la station interférente, la charge du trafic détermine le taux d‘occupation des fréquences interférentes et par conséquent agit sur le volume d‘interférence produit. Sur la station brouillée, la charge en trafic mesure l‘importance de la zone couverte, en d‘autres termes l‘intérêt que revêt la réduction des interférences sur la cellule. Le mécanisme d‘interférence sur canal adjacent est représenté dans la figure 1.1. La suppression totale d‘interférence co-canal est obtenue si on n‘utilisant pas la notion de réutilisation des fréquences, ce qui est en contradiction avec l‘idée entière des réseaux cellulaire. Donc, afin d‘obtenir une valeur tolérable d‘interférence co-canal, le planificateur du système doit tenir en compte la distance de réutilisation D. Le principe de D est représenté dans la figure 1.2. On appelle « motif » ou cluster le plus petit groupe de cellules contenant l’ensemble des canaux d’un opérateur une et une seule fois. La taille d’un motif N est le nombre de cellules de ce motif. Les centres des cellules utilisant la même fréquence qu’une cellule particulière sont situés sur un ensemble de cercles autour de celle-ci, appelés « couronnes ». Le rayon du plus petit cercle correspond à la distance de réutilisation D du réseau. Ce cercle comporte six (06) cellules, quelle que soit la taille du motif. Le premier exemple de la figure 1.2 illustre le concept de réutilisation de fréquences par deux (02) motifs à 3 cellules et la distance de réutilisation entre deux (02) cellules de ces motifs, les chiffres représentant les fréquences

Les techniques d’allocation de fréquences

        L‘allocation des fréquences est certainement l‘un des problèmes d‘ingénierie des réseaux radiomobiles les plus étudiés dans la littérature de ces 10 dernières années. Ceci donna lieu à une multitude de modèles et d‘algorithmes d‘affectation dont les différences sont principalement liées à la nature de l‘ingénierie adoptée et aux objectifs modélisés. On distingue principalement trois techniques d‘allocation de fréquences [Kat 96] qui se différencient par la manière dont les contraintes d‘interférences sont gérées (Voir figure 1.5) : le FCA (Allocation Fixe des Fréquences) [Yeu 00] [Hur 00] [Jai 96], l’DCA (Allocation Dynamique des Fréquences) [Cha 94] [Cha 96] [Che 96], et finalement l‘HCA (Allocation Hybride des Fréquences) [Taj 88]. Dans le schéma d‘allocation fixe des fréquences largement utilisé dans les réseaux GSM et DCS [Eis 02] , un ensemble nominal de fréquences est alloué à chaque cellule de façon permanente. Les appels écoulés par la station sont alors exclusivement portés par les fréquences de cet ensemble. Le principal avantage de l’FCA est sa simplicité d‘implémentation. En effet, à l‘arrivée d‘un appel, le choix de la fréquence à allouer se fait à un niveau local, vu que chaque cellule dispose de son propre pool de fréquences. L’FCA manque cependant de souplesse et s‘adapte mal aux variations du trafic. C‘est notamment le cas quand des cellules peu chargées occupent des fréquences sans les utiliser alors que d‘autres cellules sont saturées faute de ressources radio. La technique d‘allocation dynamique de fréquences est utilisée aussi bien par les réseaux DECT que CT2 [Jab 02] [Web 93]. Dans le schéma d‘allocation dynamique de fréquences, aucune allocation préalable des fréquences aux cellules n‘est effectuée. A l‘arrivée d‘un appel, le système recherche la meilleure fréquence à allouer. Ceci sous entend une gestion centrale des ressources radio et entraîne donc un trafic de signalisation supplémentaire. L‘allocation hybride des fréquences correspond à une fusion des deux techniques précédentes. Le spectre des fréquences disponible est divisé en un ensemble de fréquences fixes et un ensemble de fréquences dynamiques. Lors d‘un nouvel appel, les fréquences fixes sont utilisées de manière préférentielle aux fréquences dynamiques. Leur affectation aux différentes stations suit, par ailleurs, le même schéma que l’FCA. Les fréquences dynamiques quant à elles restent partagées par toutes les stations du réseau. Si à l‘arrivée d‘un nouvel appel sur une cellule les fréquences fixes de la station sont occupées, une fréquence dynamique est choisie suivant les mêmes mécanismes utilisés dans l’DCA.  Dans une allocation fixe, les canaux sont alloués au départ aux cellules de manière optimale. Ces raisons font qu‘en cas de fortes charges, FCA est meilleure, puisqu‘ elle permet d‘ écouler le maximum de trafic. Cependant, pour les faibles et moyennes charges, DCA utilise les canaux d‘une manière plus efficace, surtout s‘il y a des disparités dans le trafic des cellules, alors que FCA peut engendrer des blocages même s‘il existe des canaux libres dans le système. De plus, le mécanisme FCA engendre un nombre plus important de handoffs. En effet, lors d‘un transfert intercellulaire, le mobile -dans le cas de DCA- ne change pas de canal si les conditions d‘interférence le permettent, alors que pour FCA un changement de cellule entraîne un changement de canal. En conséquence, les pertes de handoff, dans le cas d‘une allocation fixe, sont beaucoup plus importantes, surtout dans un contexte micro-cellulaire où la procédure de changement de cellule est très sollicitée. Les performances de HCA sont proches de celles de DCA. Pour les mêmes raisons que celles mentionnées auparavant, HCA présente de bons résultats dans un système moyennement chargé, alors que pour les fortes charges l‘allocation fixe est meilleure.

Affectation de fréquences d’interférences minimum ( MI-FAP)

       Plusieurs heuristiques ont été proposées pour MI-FAP. Plusieurs auteurs ont appliqué avec succès les algorithmes génétiques et la recherche tabou. Dans le contexte du projet CALMA, Tiourine et al. [Tio 00] ont appliqué le recuit simulé et la recherche variable en arborescence. Un algorithme génétique a été proposé par Kapsalis[Kap 95]. Kolen aussi [Kol 99] a proposé un algorithme génétique avec croisement optimisé ; cela produit le meilleur fils de deux parents. Sa performance a été testé sur les instances du projet CALMA. Il a développé aussi d‘autres heuristique mais ces algorithmes ont été testés sur de petits réseaux [Kos 99]. Maniezo [Man 00] a appliqué une heuristique appelée FOURMIS basé sur l‘optimisation des colonies de fourmis. L‘algorithme a été testé sur les instances CALMA et Philadelphia. En plus il a proposé d‘autres algorithmes basés sur l‘approche pars recuit simulé. Le modèle de Hopfield est peut-être celui qui, parmi les différents modèles de réseaux de neurones, a été le plus utilisé pour résoudre ce type de problème. Parmi ces approches, on trouve le modèle de Kunz [Kun 91], Funabiki et Takefuji [Fun 92], kim [kim 97] et celui de Lochtie et Mehler [Loc 95]. Kunz a proposé le premier modèle Hopfield pour trouver la solution adéquate de FCA, il a pris en compte l‘interférence co-canal et l‘interférence co site. Cependant, le modèle proposé exige un grand nombre d‘itérations pour atteindre la solution finale. Funabiki et Takefuji [Fun 92] a proposé un autre réseau de neurone composé de neurones hystérésis de McCulloch Pitts. Quatre heuristiques ont été utilisées pour améliorer le taux de convergence. Les résultats montrent que la méthode obtient des résultats encourageants mais non favorables sur toutes les instances testées. Un modèle Hop-field amélioré a été proposé par Kim et al [kim 97]. Il a amélioré le temps d‘exécution et réduit le nombre d‘itérations. Lochtie et Mehler [Loc 95] ont aussi étudié MI-FAP avec un réseau de neurone. Des résultats expérimentaux ont été présentés avec quelques instances d‘un réseau réel (réseau cellulaire de 58 cellules). Smith et Palaniswami [Smi 97] ont utilisé une méthode de programmation non linéaire en nombres entiers. Ils ont appliqué un modèle de Hopfield d‘un réseau neurone au problème. Dans cette formulation, le poids de l‘interférence dépend de la distance entre les fréquences et les pénalités d‘interference. Smith et al. [Smi 98] ont appliqué le recuit simulée à un réseau réel sans fil point à point (ad-hoc). Les algorithmes génétiques sont appliqués aussi par Kim et al. [Kim 96] pour obtenir des plans de fréquences optimaux. Ils ont testé plusieurs opérateurs de croisement et de mutation pour deux instances de Philadelphia dans lesquels le spectre de fréquences disponibles est fixé à la meilleure borne inférieure de Gamst [Gam 86]. Lai et Coghill [Lai 96] ont aussi présenté une approche par l‘algorithme génétique. Cependant, leur modèle a été examiné sur deux instances. Crisan et Muhlenbein [Muh 98] ont appliqué un algorithme génétique qui utilise des opérateurs de croisement et de mutation avancé sur des instances réel de 670 et 5500 transmetteurs. Ngo et Li [Ngo 98] ont appliqué un algorithme génétique avec codage binaire spécial pour les contraintes de co-site. Smith [Smi 98] a présenté un algorithme génétique dans lequel le croisement est utilisé pour réduire les interférences co-canal et canal adjacent alors que l‘opérateur de la mutation est utilisé pour réduire l‘interférence co-site. Dorne et Hao [Dor 95] [Dor 96] ont appliqué la recherche évolutionnaire à plusieurs instances de réseaux de 300 sommets. L‘allocation de fréquences est représentée de telle façon que toutes les contraintes de co-site sont satisfaites. Dans [Dor 95], un opérateur de mutation a été défini qui est basé sur le changement de fréquences incompatibles, alors que dans [Dor 96] plusieurs méthodes ont été vérifiées pour satisfaire les contraintes co-site. Dans [Hao 96] les mêmes auteurs enquêtent sur la performance du croisement dans la recherche évolutionnaire. Hao et al [Hao 98] ont appliqué la recherche tabou pour résoudre des instances d‘un réseau réel de 600 transmetteurs. Dans leur formulation, ils ont essayé de minimiser la durée de l‘allocation de fréquences en résolvant MI-FAPs à plusieurs reprises. La longueur de la liste du tabou n‘était pas constante tous le temps mais elle a été variée pendant la recherche. Tous les algorithmes présentés dans les références de [Lan 89] [Cas 99] [Mon 03] [Cas 96] [Gos 09] [Pen 03] [Her 05] sont basées sur le principe de la recherche tabou. Les différences entre ces approches résident dans la représentation du mouvement, dans la définition du voisinage d‘un mouvement, et dans la façon de définir un mouvement tabou [Gou 11]. Par exemple La recherche Tabou a été appliquée par Castelino [Cas 96] pour trouver un plan de fréquences avec le minimum d‘interférence sur des instances de 726 sommets. Il a comparé ces résultats avec ceux d‘un algorithme génétique. Castelino [Cas 99], a utilisé une heuristique appelée tabu thresholding introduite par Glover [Glo 95] qui a été appliquée sur les mêmes instances. Finalement, Abril et al [Abr 00 ] ont appliqué un système multi agent basé sur un algorithme de FOURMIS qui utilise les données de réseaux GSM d‘un opérateur en Espagne, l‘algorithme a été comparé a une approche par recuit simulée. Pour le MI-FAP, plusieurs heuristiques ont été proposées par beaucoup de chercheurs dans divers applications. L‘algorithme génétique de Kolen [kol 99] fait partie des heuristiques prometteuse, il a été testé sur les instances CALMA. L‘inconvénient de cette technique est que le graphe d‘interférence ne devrait pas être trop grand ou devrait avoir une basse densité, autrement le croisement optimal ne peut plus être appliqué. Pour les réseaux de grande taille, les heuristiques moins sophistiquées pourraient être appliqués. Entre autre la recherche tabou, et les algorithmes de la recherche locale. Dans [Cas 96], La qualité des solutions des méthodes proposées est inconnue à cause de l‘absence de bornes inférieures de MI-FAP. Vu la dimension des instances de tests, c‘est acceptable de supposer qu‘aucune technique des méthodes exactes ne résolve jamais ces instances. Cependant, il est possible de dériver des bornes inférieures pour ces instances.

Conclusion générale

        L‘étude réalisée dans cette thèse a été consacrée au problème d‘allocation de fréquence dans les réseaux sans fils et plus particulièrement dans les réseaux cellulaires et les réseaux de radios cognitives, en prenant en compte la modélisation des phénomènes complexes de différentes natures présents dans ces réseaux. En effet, les différents services de ces réseaux exigent un niveau de qualité de service (QoS) à assurer. Cependant, la disponibilité des ressources radios n‘est pas nécessairement garantie tout le temps, et les utilisateurs mobiles peuvent ainsi subir une dégradation ou coupure du service. Un des principaux objectifs de cette thèse, a été donc d‘optimiser certains problèmes rencontrés dans ces réseaux. Ainsi, la première contribution a donc été de trouver une nouvelle approche pour résoudre le problème d‘allocation de fréquences dans un réseau cellulaire où les canaux sont alloués de façon permanente aux cellules (FCA). Cette approche utilise un algorithme Mémétique basé sur la combinaison de deux algorithme connu : ‗Algorithme Génétique‘ et ‗ la recherche Tabou‘. l‘algorithme proposé est une méthode de résolution permettant d‘améliorer la qualité de service en éliminant toutes les interférences dans ces réseaux. L‘adaptation de l‘algorithme mémétique pour la résolution de FAP dans un réseau cellulaire a considéré plusieurs propriétés. Le but étant l‘amélioration de certains critères de performance du système. Tous d‘abord, En raison de l‘importance des contraintes co-site, nous avons considéré ces contraintes dans l‘initialisation de la population. Les informations spécifiques du problème ont été utilisées efficacement dans les mécanismes de croisement et recherche tabou par le biais d‘un processus de recherche efficace dans les régions prometteuses de l‘espace de recherche. Nous avons conçu un mécanisme auto-adaptatif pour ajuster la valeur de la probabilité de croissement. L‘Opérateur de Boltzmann a été utilisée comme un mécanisme permettant de diversifier la population. Les résultats obtenus sont de très bonne qualité. En effet, la simulation montre que l‘algorithme proposé a donné de meilleurs résultats pour les différentes instances du problème étudié. Notre travail présente un bon point de vue de la gestion du spectre radio dans les réseaux cellulaires. La deuxième contribution a été de trouver une approche pour améliorer l‘utilisation de la ressource radio. Effectivement, Les ressources radios accessibles par les technologies existantes ne permettent pas de répondre à la demande. Afin de remédier le manque des fréquences, de nouveaux concepts de partage des ressources ont été proposés, comme l‘allocation dynamique d‘un canal radio à une nouvelle communication. La technologie la plus appropriée pour relever ce challenge est la radio cognitive. La méthode proposée également utilise pour ces réseaux une heuristique de recherche locale combinée avec un algorithme glouton en prenant en compte le contrôle de puissance. Cette proposition est basée sur le modèle de Peng [Pen 06], L‘approche proposée est une méthode de résolution permettant d‘améliorer la qualité de service en améliorant l‘utilisation spectrale. L‘inconvénient majeur de ce modèle réside dans leur simple modèle d’interférence, qui est basé sur le chevauchement de zones de couverture de deux stations de base (modèle binaire). Il ne tient pas compte les effets d’interférence de multiples transmissions qui se produisent simultanément sur un seul canal. La troisième contribution, été donc de proposer un modèle d‘interférence. Notre modèle réalise l’interaction entre l‘allocation de fréquences et le contrôle de puissance dans les réseaux de la radio cognitive. Tout d’abord, chaque utilisateur secondaire établit son ensemble de canaux disponibles sur lesquelles l’émetteur peut garantir sa transmission avec succès sans perturber les autres transmissions. L‘idée est de borner les puissances d’émission des émetteurs secondaires se partageant les canaux, tout en garantissant à la fois les exigences de qualité de service pour tous les utilisateurs du système. Deuxièmement, nous avons proposé un algorithme de contrôle de puissance basé sur une nouvelle métaheuristique inspirée par un algorithme naturel, appelé algorithme de luciole (firefly algorithm). Les résultats montrent une efficacité remarquable en termes de de temps de convergence. Avant d‘entamer un tel travail, nous avons d‘abord étudié les aspects essentiels caractérisant ces systèmes et les problématiques dans lesquelles ils sont développés.

Table des matières

Introduction Générale
1 Motivation
2 Contributions
3 Organisation de la thèse
Chapitre 1 Généralités sur le problème d’affectation de fréquences dans les réseaux cellulaires
1.1 Introduction
1.2 Les Interférences dans les systèmes cellulaires
1.2.1 Interférence Co-canal
1.2.2 Les interférences des canaux adjacents et Co-site
1.3 Présentation du problème
1.4 Formulation mathématique du FAP
1.5 Complexité du problème d‟allocation de fréquences
1.6 Les techniques d‟allocation de fréquences
Chapitre 2 Allocation fixe de fréquences
2.1 Introduction
2.2 Classification du problème d‟allocation de fréquences
2.2.1 Affectation de fréquences d‟ordre minimum (MO-FAP)
2.2.2 Affectation de fréquences de spectre minimum (MS-FAP)
2.2.3 Affectation de fréquences d‟interférences minimum (MI-FAP)
2.2.4 Affectation de fréquences de blocage minimum (MB-FAP)
2.3 Etat de l‟art
2.3.1 Affectation de fréquences d‟ordre minimum (MO-FAP)
2.3.2 Affectation de fréquences de spectre minimum (MS-FAP)
2.3.3 Affectation de fréquences d‟interférences minimum ( MI-FAP)
2.3.4 Affectation de fréquences de blocage minimum (MB-FAP)
2.4 Conclusion
Chapitre 3 Rappel de quelques Métaheuristiques et proposition d’un Algorithme Mémétique résolvant le FAP
3.1 Introduction
3.2 Généralités sur les métaheuristiques
3.2.1 Effet Lamarckianism contre Baldwinian
3.2.2 Diversification et minimum local
3.2.3 Le choix de voisinage pour l‟espace de recherche
3.3 Principales Métaheuristiques
3.3.1 Les approches de «recherche locale» ou trajectoire
3.3.1.1 La méthode du recuit simulé
3.3.1.2 La recherche tabou
3.3.2 Les approches «évolutionnaires» (ou popultion)
3.3.2.1 Les Algorithmes génétiques
3.3.2.2 Algorithme des lucioles
3.4 Les Algorithmes Mémétique
3.4.1 Algorithmes évolutionnaires+Recherche Locale=Algorithme Mémétique
3.4.2 Le modèle d‟un algorithme mémétique
3.5 Quelle méta heuristique utiliser
3.6 Proposition d‟un algorithme Mémétique pour le problème d‟affectation de fréquences
3.6.1 Les composants de l‟algorithme proposé
3.6.1.1 Représentation et mécanismes de sélection
3.6.1.2 Initialisation de la population
3.6.1.3 Opérateur de croisement
3.6.1.4 Opérateur de mutation et stratégie de remplacement
3.6.1.5 Principe de l‟algorithme Mémétique
3.6.2 Recherche Tabou
3.6.3 Fréquences libres
3.6.4 Critères d‟arrêt
3.6.5 Résultats expérimentaux
3.7 Conclusion
Chapitre 4 : Le problème d’allocation de fréquences dans les radios cognitives
4.1 Introduction
4.2 Formulation du problème
4.2.1 Description du système
4.2.2 Proposition de la Fonction d‟utilité globale
4.2.3 Un modèle de recherche locale pour le problème
4.2.4 La disponibilité des fréquences et les activités des utilisateurs primaires
4.3 L’algorithme proposé
4.3.1 Algorithme glouton
4.3.2 La recherche tabou
4.3.3 Algorithme de contrôle de puissance (power controle)
4.4 Résultats expérimentaux et discussions
4.4.1 Modèle de simulation et ses paramètres
4.4.2 Résultats et discussion
4.4 Conclusion
Chapitre 5 : Algorithme des Lucioles modifié pour le problème de contrôle de puissance et l’allocation de fréquences dans les radios cognitives
5.1 Introduction
5.1 Formulation de problème
5.1.1 Description du système et hypothèses de base
5.1.2 Les canaux libres pour les Sus
5.1.3 Fonction d‟utilité pour Sus
5.1.4 Existence d’équilibre de Nash
5.2 Proposition d‟un algorithme efficace pour le contrôle de puissance
5.3 Résultats et discussions d’expérimentation
5.3.1 Modèle de simulation et les paramètres
5.3.2 Fonctions Utilitaires du système
5.3.3 Résultats et discussion
Conclusion générale
Bibliographies

Télécharger le rapport complet