Allocation des ressources dans les réseaux cellulaires du futur : algorithmes et complexités

Mlika, Zoubeir (2019). « Allocation des ressources dans les réseaux cellulaires du futur : algorithmes et complexités » Thèse. Montréal (Québec, Canada), Université du Québec à Montréal, Doctorat en informatique.

Fichier(s) associé(s) à ce document :
[img]
Prévisualisation
PDF
Télécharger (19MB)

Résumé

Les réseaux cellulaires ont connu durant les dernières décennies des avancées technologiques considérables. Plusieurs générations de ces réseaux se sont succédé, et chacune offrait une gamme de plus en plus large d'applications de haute performance aux utilisateurs. La première et la deuxième générations, plus connues sous les sigles 1G et 2G, étaient spécialement conçues pour le transport de la voix. Les générations récentes sont dotées de la capacité de transporter des données; permettant ainsi un accès continu à Internet. Les exigences de la prochaine génération portent encore la barre plus haut avec un débit de transmission plus élevé (allant jusqu'à des dizaine de gigabits par seconde), un délai de latence plus réduit (moins d'une milliseconde) ainsi qu'une couverture et une disponibilité quasi-complète. Afin d'atteindre ces exigences, la prochaine génération adoptera plusieurs nouvelles technologies, telles que les antennes multiples à large échelle, la communication millimétrique, et les réseaux cellulaires denses hétérogènes (appelés Dense Cellular Networks ou simplement DCNs). Les réseaux DCNs se caractérisent par le déploiement de plusieurs stations de base de différentes caractéristiques (tailles, puissance, prix, etc.) avec des distances réduites entre elles. Dans cette thèse, nous proposons des algorithmes d'allocation de ressources dans les réseaux DCNs de la prochaine génération. Spécifiquement, nous étudions le problème d’ordonnancement et d'association des utilisateurs aux différentes stations de base ainsi que l'allocation des fréquences. Nous nous intéressons à (i) étudier la complexité computationnelle de ce problème en caractérisant sa NP-difficulté et (ii) proposer des algorithmes d'allocation de ressources avec des performances théoriques dans le pire cas (comme des algorithmes d'approximations ou des algorithmes compétitifs). Dans la première partie de cette thèse, nous étudions le problème d'association des utilisateurs aux stations de base sous les contraintes d'interférence et de qualité de service avec l'objectif de maximiser le nombre d'utilisateurs associés. Ce problème, à nos connaissances, n'a pas été étudié par d'autres chercheurs. Nous montrons la NP-difficulté du problème et nous proposons un algorithme d'approximation permettant de le résoudre efficacement. Ensuite, nous modélisons ce problème en utilisant la théorie des jeux. Ainsi, nous proposons un algorithme d'apprentissage totalement distribué. En second lieu, nous étudions le problème conjoint d'association des utilisateurs avec activation et désactivation des stations de base. L’objectif est de minimiser la consommation énergétique sous les contraintes de qualité de service des utilisateurs. Nous étudions la faisabilité de ce problème et nous montrons qu'il s'agit d'un problème NP-difficile. Nous proposons ensuite différentes solutions algorithmiques pour différents cas de qualité de service exigée. Dans la troisième partie de cette thèse, nous étudions le problème conjoint d'ordonnancement, d'association des utilisateurs et d'allocation de fréquences avec ou sans la récolte d'énergie. L’objectif est de maximiser le nombre d'utilisateurs satisfaits. Ce problème est résolu sous les contraintes de qualité de service et de délai contraignant. Dans le cas sans récolte d'énergie, nous étudions un cas spécial de ce problème et nous proposons un algorithme optimal pour le résoudre. Après, nous démontrons la NP-difficulté du problème dans le cas général et nous proposons un algorithme d'approximation avec un facteur d'approximation constant. Dans le cas avec récolte d'énergie, nous étudions la NP-difficulté du problème dans différents cas. Lorsque le problème appartient à la classe P, nous proposons un algorithme optimal pour le résoudre. Lorsque le problème est NP-difficile, nous proposons des algorithmes d'approximation ainsi que des algorithmes heuristiques. Ensuite, nous résolvons ce problème dans un scénario online. Nous proposons des algorithmes online compétitifs ainsi qu'un algorithme d'apprentissage incrémental et nous démontrons que son regret est sous-linéaire. Pour chaque problème étudié dans ce projet, nous présentons des résultats de simulations Monte Carlo afin d'illustrer les performances de nos solutions proposées. La dernière partie de cette thèse conclut le travail et présente différentes pistes de recherche pour le futur. _____________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Réseaux cellulaires denses hétérogènes, allocation de ressources, ordonnancement, association des utilisateurs, allocation de fréquences, récolte d'énergie, activation et désactivation des stations de base, interférence, capacité, délai, dates limites, complexité asymptotique, NP-difficulté, algorithmes optimaux, algorithmes gloutons, algorithmes compétitifs, algorithmes d'approximation, algorithmes d'apprentissage.

Type: Thèse ou essai doctoral accepté ()
Informations complémentaires: La thèse a été numérisée telle que transmise par l'auteur.
Directeur de thèse: Ajib, Wessam
Mots-clés ou Sujets: Réseaux de téléphonie mobile / Affectation des ressources / Réseaux cellulaires denses / Algorithmes
Unité d'appartenance: Faculté des sciences > Département d'informatique
Déposé par: Service des bibliothèques
Date de dépôt: 13 mars 2020 07:23
Dernière modification: 13 mars 2020 07:23
Adresse URL : http://archipel.uqam.ca/id/eprint/13315

Statistiques

Voir les statistiques sur cinq ans...