Note publique d'information : Le travail présenté dans cette thèse traite des problèmes d'affectation de fréquences
(FAP) qui se produisent dans les systèmes de communication par satellite utilisant
la technologie SDMA. Ces systèmes se composent d'un satellite et d'une zone de service
de taille fixe dans laquelle sont répartis des utilisateurs. L'objectif est alors
de servir un maximum d'utilisateur en fréquence dans cette zone de service. Cependant,
l'affectation ne doit pas violer les contraintes d'interférence qui apparaissent lorsque
deux utilisateurs utilisent une même fréquence ou lorsqu'ils se partagent une même
plage de fréquence. Deux types d'interférences sont considérés dans cette étude :
les interférences binaire et cumulative. Pour chacune d'elles, les problèmes d'affectation
de fréquence de type mono-porteuse (une fréquence par utilisateur) et multi-porteuses
(plusieurs fréquences par utilisateur) sont traités. Le problème de l'affectation
bidimensionnelle est aussi abordé et nous proposons des modèles de Programmation Linéaire
en Nombre Entiers (PLNE) pour le résoudre. Au niveau des méthodes de résolution, nous
utilisons des algorithmes gloutons, des modèles de PLNE pour le problème de type mono-porteuse.
En outre, un algorithme de déplacement continu de faisceau est conçu pour améliorer
les solutions en résolvant un problème d'optimisation continu non linéaire. Concernant
le problème de type multi-porteuses, nous le ramenons à un problème d'ordonnancement
et celui-ci est résolu à l'aide de la PLNE et la Programmation Par Contraintes (PPC).
Il est par ailleurs montré que les résultats issus de la PPC sont meilleurs que ceux
de la PLNE. De plus, en transformant les interférences cumulatives en interférences
binaires, la méthode d'ordonnancement avec les contraintes induites par les cliques
donne de bien meilleurs résultats. Nous considérons également un problème industriel
dans lequel de nombreuses contraintes apparaissent ce qui rend le problème très complexe
et insoluble avec des méthodes exactes. Face à ce constat, deux algorithmes gloutons
sont réalisés et leurs résultats sont comparés.
Note publique d'information : In this thesis, we consider frequency assignment problems arising from an SDMA satellite
communication system which consists of a satellite and a number of users distributed
inside a fixed sized service area. The objective is to assign a given number of frequency
carriers to as many users as possible. This assignment should not violate the incurred
interference constraints. Two types of interference are considered i.e. binary and
cumulative interference. For each of them, single carrier and multiple carrier frequency
assignment models are taken into account. We also propose an Integer Linear Programming
(ILP) formation to deal with 2-dimensional frequency-time assignments which is more
complicated and harder to solve. Single carrier FAPs are solved by greedy algorithms
and ILP. A Beam Moving algorithm is devised to further improve the solutions by solving
a non-linear optimization problem. Multiple carrier FAPs are modeled as scheduling
problem and ILPs. We show that the scheduling model solved through constraint programming
methods offers superior performance than the proposed ILP. It is worth noting that,
by transforming the cumulative interference into binary interference, scheduling method
together with clique-induced constraints yields much better results. A frequency assignment
problem that incorporates the specifications and constraints provided by the industry
is also considered. These requirements render the resource allocation problem highly
complex. This complexity and the fact that frequency assignment plans must be recomputed
frequently in order to cope for user mobility yield classic optimization tool such
as ILP impractical. According to this, two greedy algorithms are devised and tested.
paprika.idref.fr
data.idref.fr
Documentation
