Etablissement
Ecole Nationale Supérieure d'informatique
Affiliation
Département de Post-Graduation
Auteur
DAOUDI, Asma
Directeur de thèse
Benatchba Karima (Professeur)
Co-directeur
Bessedik Malika (Maitre de conférence)
Filière
Informatique
Diplôme
Doctorat
Titre
Résolution du problème d’affectation de fréquences multi objectifs dynamique en utilisant plusieurs approches biomimétiques
Mots clés
T-coloration, métaheuristique évolutionnaire, affectation de fréquences, MI- PAF et MO- PAF.
Résumé
Résumé : Depuis quelques années, les études portant sur le problème d’affectation de fréquences (PAF ) se sont multipliées. Ceci est dû essentiellement à la vaste implémentation des réseaux de la téléphonie sans-fil (par exemple les réseaux GSM) et des communications satellites. En effet, alors que le nombre de fréquences possibles est fini, la demande augmente sans cesse. Les transmetteurs doivent attribuer une fréquence à chaque téléphone portable. Sachant qu’un transmetteur ne peut utiliser une fréquence que pour un seul téléphone, et afin d'éviter les interférences, deux transmetteurs proches, i.e. ayant une zone d'émission commune, doivent utiliser des fréquences différentes. Cette situation peut se modéliser par un graphe. Chaque transmetteur est représenté par un sommet, et deux sommets sont reliés par une arête quand les deux transmetteurs ont une zone d'émission commune. En outre, il existe une bijection intuitive entre une fréquence et une couleur. Aussi pour des raisons technologiques, la gamme de fréquences pour chaque transmetteur n'est pas nécessairement la même ce qui a conduit à de nouvelles variantes du problème de la coloration des graphes comme la coloration par listes où une liste de couleurs permises est affectée à chaque sommet. Dans le cas d’existence des solutions valides pour un PAF, le souci était de pénaliser l’utilisation des fréquences. Donc, le nombre des différentes fréquences utilisées est minimisé. Cet objectif remonte à l’introduction des téléphones mobiles en 1970, dont les fréquences se vendaient par unité et étaient trop chères. Il s’agit du modèle MO-PAF. Le modèle précédent n’utilise les interférences que pour interdire certains choix des fréquences. Le modèle MI-PAF utilise une matrice de pénalité pour introduire une fonction objective qui minimise la somme des pénalités causées par le choix des fréquences. Le MO-PAF et le MI- PAF diffèrent seulement dans la fonction objective. On propose dans ce travail de résoudre le PAF en combinant les deux fonctions objectif précédentes en utilisant une métaheuristique évolutive .Une étude empirique faisant varier les différents paramètres de l’algorithme sera faite. Pour évaluer notre travail, nous proposons aussi de comparer les résultats obtenus avec ceux des travaux relatifs au même problème.
Statut
Vérifié