Planification radio dans le réseau GSM

Historique

Durant des siècles, l’homme s’est contenté de la parole ou des écrits comme seuls moyens de communication entre deux personnes éloignées d’une distance importante. En 1982, lors de la Conférence Européenne des Postes et Télécommunications (CEPT) que fut créé le Groupe Spécial Mobile (GSM). En 1985, la Commission Européenne annonce l’imposition de la norme issue du GSM. En 1987, le choix est arrêté sur la transmission numérique AMR. En 1989, les travaux du Groupe Spécial Mobile « GSM » sont transférés au comité « SMG » de l’Européen Télécommunication Standards Institute (ETSI), qui poursuit les tâches de normalisations. Notons que c’est cette comité qui mettra au point le module d’identité d’abonné SIM. Le groupe « GSM » change alors de signification : de « Groupe Spécial Mobiles » il devient « Global System for Mobile communications » En 1991 fût réalisé la première communication entre un mobile et un abonné fixe. Les premiers terminaux sont représentés au Salon Télécom à Genève cette même année.

Puis on assiste à l’ouverture des systèmes d’essai à Paris. Et c’est en 1992 que fût ouvert le système GSM ITINERIS de France Telecom, rejoint plus tard par SFR du groupe Cegetel et par Bouygues Telecom (1994). L’explosion du marché des mobiles, sa croissance soutenue et l’apparition de nouveaux services amènent les réseaux GSM actuels à leur limite. Le débit de 9,6 kb/s, défini à l’origine, est insuffisant pour couvrir les nouveaux besoins de transferts de données et constitue un frein à la diffusion de contenus multimédias. Les premières applications WAP (norme permettant l’affichage de pages Web sur les Mobiles) sur réseau sans fil souffrent encore de temps de connexion et de réponse trop long, surtout quand les appels sont facturés à la durée. De plus, la qualité de service est encore insuffisante et la fiabilité des communications doit être améliorée. Les nouvelles normes de téléphonie hauts débits, tels GPRS, EDGE et UMTS devraient résoudre ces problèmes et bouleverser à terme les possibilités.

Le concept cellulaire [10]

Au début de la téléphonie mobile, le but était d’atteindre une grande surface avec une seule antenne puissante, située de préférence sur une grande tour. Avec ce système il était impossible de réutiliser les fréquences sur la surface couverte par l’antenne et par conséquent le nombre d’usagers était limité. Le concept cellulaire a beaucoup apporté dans le design des réseaux pour résoudre le problème de l’encombrement du trafic et pour permettre à l’opérateur d’utiliser les fréquences à disposition avec plus d’efficacité. Avec ce concept nous admettons qu’une cellule sert une surface beaucoup plus petite à l’aide d’une station de base. Le nombre de canaux alloué à une station représente seulement une portion de tous les canaux alloués au système complet. Un canal est en général composé d’une fréquence. Les stations voisines les unes des autres ont droit à des canaux différents pour qu’elles ne s’empiètent pas. Par contre nous pouvons utiliser des canaux (fréquences) identiques si deux cellules sont suffisamment éloignées l’une de l’autre. Ceci permet ainsi de résoudre le problème de l’encombrement, ou en d’autres termes un plus grand nombre d’utilisateurs pourra faire usage du téléphone cellulaire simultanément. Plus le nombre de cellules est grand pour une surface donnée, plus le nombre d’utilisateurs pourra être grand également. La puissance d’émission doit être adaptée à la dimension de la cellule. A la campagne les cellules sont de dimension plus importante étant donnée le faible nombre d’utilisateurs. La planification des fréquences consiste à attribuer des fréquences (canaux) à des cellules. Nous pouvons utiliser un même ensemble de canaux pour des cellules suffisamment éloignées. On parle alors de « réutilisation de fréquences ».

Principe d’algorithme génétique

Les algorithmes génétiques sont des algorithmes itératifs de recherche globale dont le but est d’optimiser une fonction prédéfinie appelée le critère ou fonction coût (fitness en anglais). Pour réaliser cet objectif, l’algorithme travaille en parallèle sur un ensemble de points représentant les solutions potentielles du problème. Cet ensemble est appelé population. Chaque point la constituant est appelé individu ou chromosome. Un chromosome est une représentation ou un codage d’une solution d’un problème donné. Le chromosome est constitué d’un ensemble d’éléments appelés gènes pouvant prendre plusieurs valeurs appelées allèles appartenant à un alphabet non nécessairement numérique. Dans les algorithmes de base un allèle a pour valeur <<0>> ou <<1>>, un chromosome est donc une chaine binaire de longueur finie. Le but est donc de chercher la meilleure combinaison de ces éléments, qui donne lieu à la meilleure fonction cout. A chaque itération ou génération, est créée une nouvelle population en utilisant des parties des meilleurs éléments de la génération précédentes, ainsi que des parties innovatrices à l’occasion. Bien qu’utilisant le hasard, les algorithmes génétiques ne sont pas purement aléatoires. Ils exploitent efficacement l’information obtenue précédemment pour avoir les meilleurs individus pour chaque population. A partir d’une première population de chromosome de taille fixe, créée soit d’une manière aléatoire, soit par des heuristiques ou méthodes spécifiques au problème, soit encore par mélange de solutions aléatoire et heuristique, les algorithmes génétiques génèrent de nouveaux individus de telle sorte qu’ils soient plus performants que leurs prédécesseurs. Le processus d’amélioration d’une population donnée s’effectue par l’utilisation d’opérateurs génétiques qui sont la sélection, le croisement et la mutation.

L’opérateur de sélection

La sélection choisit et détermine quels membres ou individus d’une population survivent et se reproduisent. Cette sélection est déterminée en fonction des valeurs de la fonction coût. Intuitivement cette fonction peut être envisagée comme une mesure de profit, d’utilité ou encore de qualité, que l’on souhaite maximiser. Sélectionner des chromosomes en fonction des valeurs de leurs fonctions coût revient à donner aux individus dont la valeur est plus grande une probabilité plus élevée de produire un ou plusieurs descendants dans la prochaine génération et de contribuer ainsi à l’évolution de la solution. L’opérateur de sélection peut être mis en oeuvre sous forme algorithmique de différentes façons :

•Soit d’une manière déterministe ; il s’agit de garder un certain nombre d’individus jugés bons d’après leurs fonction coût et de rejeter le reste. Parmi ce type de méthodes, on peut citer la sélection par tournoi qui consiste à choisir k individus aléatoirement, l’individu sélectionné est le vainqueur du tournoi c’est-à-dire celui qui possède la meilleur performance, donc il y aurait autant de tournoi que d’individu à sélectionner.

•Soit d’une manière stochastique en utilisant la technique de la roulette biaisée pour laquelle chaque individu de la population occupe face de la roue proportionnelle à sa fonction cout. Cependant, aucune sélection n’est parfaite, le risque de favoriser un individu ou un petit nombre d’individus constitue un véritable inconvénient. En effet si un chromosome est très supérieur à la moyenne, il constituera presque exclusivement la population suivante ce qui nous fait perdre l’âme des algorithmes génétiques à savoir la diversité, d’où risque de convergence prématurée. Pour éviter ce genre d’excès une des solutions possible constituerait à procéder a un changement d’échelle de la fonction coût. On s’arrange pour que les fonctions coût minimum et maximum aient des valeurs données en adoptant un changement d’échelle statique ou dynamique, linéaire ou exponentiel. La sélection ne permet pas d’explorer de nouveaux points (de nouvelles possibilités) dans l’espace des solutions admissibles. En ce sens, rien de nouveau n’est testé. L’introduction d’un nouvel espace de recherche se fait via les processus de mutation et de croisement qui d’un point de vue algorithmique, peuvent être considérés comme des mécanismes servant à changer localement les solutions ou a les combiner.

Dans le cadre de cette étude, nous nous sommes intéressées au problème d’affectation des fréquences dans le réseau cellulaire de deuxième génération. A travers ce projet de fin d’étude, nous avons développé un outil d’optimisation permettant de donné un plan de fréquences optimale dans le réseau GSM basé sur les algorithmes génétiques. Pour évaluer les performances de notre algorithme, nous avons considéré le réseau cellulaire de l’opérateur MOBILIS pour la ville de Maghnia. En effet, nous nous sommes servi des positions des sites et le nombre de fréquence allouées pour chaque cellule du réseau de Maghnia. Les résultats obtenus (zéro Co-BCCH) montrent clairement l’efficacité et la robustesse de l’approche utilisée. Comme perspectives de ce travail, d’autres approches d’affectation des fréquences basées sur différentes heuristiques (algorithme de tabou …) peuvent être développées. Il est aussi envisageable de comparer notre outil développé avec des logiciels spécialisés dans ce type de problème à l’instar du logiciel Atoll (Wireless Network Engineering Software), ceci va nous permettre de valider l’approche utilisée. Enfin ce travail nous a été très enrichissant. Il nous a permis de toucher de prés une partie très importante dans la planification des réseaux GSM. Nous souhaitons que le présent travail satisfasse ses lecteurs.