Efficient Methods for Resource Allocation in Multi-Antenna Orthogonal Frequency-Division Multiple Access (OFDMA) Systems

Dans cette thèse, nous proposons une solution au problème d'allocation de ressources d'un système MISO (Multiple Input Multiple Output) – OFDMA (Orthogonal Frequency Division Multiplexing Access) supportant des usagers requérant un débit de transmission minimal. Ce problème peut être modélisé comme une optimisation non-linéaire mixte avec variables entières. Nous nous sommes intéressés dans cette thèse à diverses méthodes permettant la résolution d'un tel problème. La première approche étudiée utilise une méthode hors-ligne et permet d'obtenir une solution quasi-optimale qui peut être utilisée comme références pour évaluer la performance d'algorithmes heuristiques pouvant être réalises en temps réel. Pour ce faire, nous cherchons une allocation réalisable en se basant sur la solution optimale du problème dual. Nous obtenons la fonction duale et trouvons la solution à l'aide d'un algorithme itératif à sous-gradient. Cette solution permet d'obtenir une borne supérieure à la solution optimale. D'autre part, nous développons une heuristique basée sur la solution du problème dual pour obtenir une solution réalisable du problème primaire qui constitue une borne inferieure à la solution optimale. Ces bornes nous permettent d'établir que l'écart de dualité est petit pour les configurations étudiées et elles peuvent servir de référence pour l'évaluation de performances des algorithmes heuristiques. La formulation duale nous fournit aussi une meilleure compréhension du sujet en établissant un lien entre la réalisabilité de l'allocation de ressources et les débits minimaux requis par les usagers. Afin d'obtenir des méthodes de résolution plus pratiques pouvant être réalisées en temps réel, nous proposons deux heuristiques ayant une faible complexité et permettant d'atteindre des performances assez prés des performances optimales. Les performances ainsi obtenues sont légèrement moins bonnes que celles d'autres algorithmes qu'on retrouve dans la littérature, mais supportent une plus grande plage de valeurs de débit minimal tout en réduisant la complexité de l'algorithme d'allocation de ressources de plusieurs ordres de grandeur. L'écart entre la solution trouvée par ces algorithmes heuristiques et la borne supérieure duale est relativement faible. Par exemple, l'écart est de 10.7% en moyenne pour toutes les configurations étudiées. L'augmentation dans la plage de débits minimaux supportes compares avec les méthodes disponibles dans la littérature est de 14.6% en moyenne. Cette amélioration est obtenue en considérant les variables duals de contrainte de débits minimaux dans l'allocation de puissance aux usagers. L'algorithme heuristique proposé sélectionne un ensemble d'usagers pour chaque sous-porteuse, mais contrairement aux autres méthodes proposées précédemment, l'algorithme considère l'ensemble des usagers avec des contraintes de débits minimaux dans la réassignation des sous-porteuses pour s'assurer que le niveau de service requis est rencontre. Suite à la sélection des ensembles d'usagers, un problème d'allocation de puissance convexe est résolu. Des algorithmes permettant de résoudre efficacement et en un temps moindre les problèmes d'assignation des sous-porteuses aux usagers et d'allocation de puissance sont proposées dans cette thèse. Finalement, nous étudions aussi de quelle façon ces algorithmes peuvent être utilises pour résoudre le problème d'allocation de ressources dans une cellule utilisant la technologie LTE (Long Term Evolution)-Advanced. Les méthodes étudiées dans cette thèse font partie d'un nouvel ensemble d'algorithmes nécessaires pour supporter des applications temps réel à haut débit et a l'efficacité spectrale requise dans les prochains réseaux d'accès sans-fil de quatrième génération.

Abstract

In this dissertation, we solve the Resource Allocation (RA) problem of a Multiple Input Single Output (MISO) – Orthogonal Frequency Division Multiplexing Access (OFDMA) sys¬tem supporting minimum rates. This problem can be modelled as a non-linear Mixed Integer Program (NLMIP). We are interested in various kinds of methods to solve this problem. First, our focus is on an off-line method that gives near-optimal solutions that serve as benchmark for more practical methods. For this purpose, we propose a method based on the optimal solution of the dual problem. We obtain a dual function and solve the dual problem through subgradient iterations. Then, we find upper and lower bounds for the optimal solution and verify that the duality gap is small for the system configurations studied. Therefore, the dual optimal serves as a reference for any feasible solution produced by the heuristic methods. The dual formulation also gives a better insight into the problem, as it shows us the relation between the problem's feasibility and the minimum rate requirements. To obtain more practical methods, we propose two heuristics that have very low com-putational complexity and give performances not far from the optimal. We compare their performance against other methods proposed in the literature and find that they give a somewhat lower performance, but support a wider range of minimum rates while reducing the computational complexity of the algorithm by several orders of magnitude. The gap be¬tween the objective achieved by the heuristics and the upper bound given by the dual optimal is not large. For example, in our experiments this gap is 10.7% averaging over all performed numerical evaluations for all system configurations. The increase in the range of the sup¬ported minimum rates when compared with the method reported in the literature is 14.6% on average. This increase is achieved by considering the rate constraint dual variables in the user power allocation stage. The proposed heuristics select a set of users for each subcarrier, but contrary to other reported methods used to solve the throughput maximization problem, they consider the set of real-time (RT) users to ensure that their minimum rate requirements are met. Then, they solve a power allocation problem for fix subcarrier assignment, which is a convex problem that is simpler to solve. We use efficient algorithms for the subcarrier assignment and power allocation stages to solve the problem much quicker. Finally, we adapt the algorithms to solve the RA problem in a single cell using LTE (Long Term Evolution)–Advanced technology. The methods examined in this dissertation are part of the new set of algorithms needed to support the high rate applications and spectral efficiency required in the wireless access of upcoming 4G networks.