HAL Id: tel-00795211
https://tel.archives-ouvertes.fr/tel-00795211
Submitted on 27 Feb 2013
HAL is a multi-disciplinary open access archive for the deposit and dissemination of sci- entific research documents, whether they are pub- lished or not. The documents may come from
L’archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d’enseignement et de
Conception de Mecanismes Inter-couches dans les Systemes MIMO Multi-cellulaires
Subhash Lakshminarayana
To cite this version:
Subhash Lakshminarayana. Conception de Mecanismes Inter-couches dans les Systemes MIMO Multi- cellulaires. Autre. Supélec, 2012. Français. �NNT : 2012SUPL0020�. �tel-00795211�
TH` ESE DE DOCTORAT
SP´ ECIALIT´ E: T´ el´ ecommunications
Ecole doctorale “Sciences et Technologies de l’Information, des´ T´el´ecommunications et des Syst`emes”
Pr´esent´ee par :
SUBHASH LAKSHMINARAYANA
Sujet:
Conception de Mecanismes Inter-couches dans les Systemes MIMO Multi-cellulaires
(Cross Layer Design in MIMO Multi-cell Systems)
Soutenue le 6 dec 2012 devant les membres du jury:
M. Pierre Duhamel, CNRS/Sup´elec Examinateur, Pr´esident du Jury M. Eduard Jorswieck, Dresden University of Technology Rapporteur
M. Dirk Slock, Eurecom Rapporteur
M. Slawomir Stanczak, Technische Universit¨at Berlin Examinateur M. Thomas Bonald, Telecom ParisTech Examinateur
M. M´erouane Debbah, Sup´elec Examinateur,
Encadrant de Th`ese
M. Mohamad Assaad, Sup´elec Examinateur,
Encadrant de Th`ese
Contents
1 Introduction 2
1.1 Motivation and Technological Challenges . . . 2
1.2 Outline and Contributions . . . 5
1.3 Publications . . . 9
2 Theory 10 2.1 Useful Results from Probability and Matrix Analysis . . . 10
2.2 Introduction to Random Matrix Theory . . . 12
2.3 Overview of Results from Stochastic Control Theory . . . 14
2.3.1 LQG Control . . . 15
2.3.2 H∞ Control . . . 16
2.4 Overview of results from Stochastic Network Optimization . . . . 17
2.4.1 Concept of Lyapunov Stability . . . 18
3 Beamforming Design and Traffic Flow Control 21 3.1 Introduction . . . 22
3.2 System Model . . . 23
3.3 Algorithm Design . . . 25
3.4 Part I: Interference Management - Multi-cell Beamforming . . . . 26
3.4.1 Introduction to Multi-cell Beamforming Design . . . 26
3.4.2 Beamforming Design Algorithm Description . . . 28
3.4.3 ROBF Algorithm - Discussion . . . 32
3.4.4 ROBF Algorithm Analysis . . . 32
3.4.5 Numerical Results for the ROBF Algorithm . . . 35
3.5 Part II: Flow Controller Design and Queue Stability . . . 38
3.5.1 Motivation for the Flow Controller . . . 38
3.5.2 Flow Controller Design . . . 40
3.5.3 Numerical Results for the Flow Controller . . . 41
3.6 Conclusion . . . 42
Contents
3.7 Appendices . . . 43
3.7.1 Proof of the Fixed Point Equation . . . 43
3.7.2 Computation of ¯δ . . . 46
3.7.3 Proof of Lemma 1 . . . 48
3.7.4 Feasibility Conditions . . . 49
3.7.5 Convergence proof of the Downlink SINR . . . 55
4 Energy Efficient Design in MIMO Multi-cell Systems with Time Average QoS Constraints 56 4.1 Introduction . . . 57
4.2 System Model . . . 59
4.3 Achievable QoS Region . . . 61
4.4 Energy Efficient Decentralized Beamforming Design . . . 62
4.4.1 Perfect CSI Case . . . 65
4.5 Delayed Queue-length Information Exchange . . . 71
4.6 The Case with Channel Estimation . . . 72
4.7 Numerical Results . . . 75
4.8 Conclusion . . . 79
4.9 Appendices . . . 79
4.9.1 Performance Bounds for the DBF Algorithm . . . 79
4.9.2 Performance with Delayed Queue-length Exchange . . . . 82
5 Decentralized Scheduling Policies 86 5.1 Introduction . . . 86
5.2 System Model . . . 88
5.3 Existing Approaches . . . 90
5.3.1 Maximum Weight based Scheduling Algorithm . . . 90
5.3.2 CSMA based Scheduling Algorithm . . . 90
5.4 FCSMA Algorithm Description . . . 93
5.5 FCSMA with Dynamic Traffic Splitting Algorithm . . . 96
5.6 Fading Channels . . . 98
5.7 Conclusion . . . 99
5.7.1 Future Directions . . . 99
5.8 Appendices . . . 100
5.8.1 Proof of Proposition 6 . . . 100
5.8.2 Proof of Theorem 9 . . . 102
5.8.3 Proof of the Fading Channel Scenario . . . 109
Contents
6 Conclusions & Outlook 111
6.1 Future Directions . . . 113 6.1.1 CSI feedback and Queuing Stability for MIMO Multi-cell
Networks . . . 113 6.1.2 Delay Efficient Algorithms . . . 114 6.1.3 Opportunistic Resource Allocation Strategies for Cogni-
tive Heterogeneous Networks . . . 114 6.1.4 Optimal Transmission Techniques with Energy Harvesting 115
Bibliography 116
Abstract
Future wireless communication systems are expected to see an explosion in the wireless traffic which is mainly fueled by mobile video traffic. Due to the time varying and bursty nature of video traffic, wireless systems will see a wider range of fluctuations in their traffic patterns. Therefore, traditional physical layer based algorithms which perform resource allocation under the assumption that the transmitters are always saturated with information bits, might no longer be efficient. It is, thus, important to design dynamic resource allocation algorithms which can incorporate higher layer processes and account for the stochastic nature of the wireless traffic.
The central idea of this thesis is to develop cross-layer design algorithms between the physical and the network layer in a multiple input multiple output (MIMO) multi-cell setup. Specifically, we consider base stations (BSs) equipped with multiple antennas serving multiple single antenna user terminals (UTs) in their respective cells. In contrast to the previous works, we consider the ran- domness in the arrival of information bits and hence account for the queuing at the BSs. With this setup, we develop various cross-layer based resource allo- cation algorithms. We incorporate two important design considerations namely decentralized design and energy efficiency. In particular, we focus on developing decentralized beamforming and traffic flow controller design, energy efficient de- sign under time average QoS constraints and decentralized scheduling strategy in a multi-cell scenario. To this end, we use tools from Lyapunov optimization, random matrix theory and stochastic control theory.
Abstract (French)
Les pr´evisions relatives trafic de donn´ees au sein des syst`emes de communica- tions sans-fil sugg`erent une croissance exponentielle, principalement aliment´ee par l’essor de transferts vid´eo mobiles. Etant donn´e la nature soudaine et fluctu- ante des demandes de transfert vid´eo, il faut d`es `a pr´esent r´efl´echir `a de nouveaux algorithmes d’allocation de ressources performants. En effet, les algorithmes en couche physique traditionnels, qui r´ealisent de l’allocation de ressources sous l’hypoth`ese classique que les transmetteurs sont toujours satur´es avec des bits d’information, risquent `a l’avenir de s’av´erer inefficients. Pour cette raison, les algorithmes de demain se doivent d’ˆetre dynamiques, dans le sens o`u ils seront capables de prendre en compte la nature stochastique des fluctuations du trafic de donn´ees et qu’ils int´egreront des informations issus de processus de couches sup´erieures.
L’id´ee centrale de cette th`ese est de d´evelopper des algorithmes, travaillant avec des informations issues de la couche PHY et de la couche NET, dans un sc´enario Multi-cells et MIMO (Multiple Inputs, Multiple Outputs).Plus parti- culi`erement, nous consid´erons un r´eseau de stations de base (BS) ´equip´es avec plusieurs antennes, charg´es de servir plusieurs terminaux mobiles ´equip´es d’une seule antenne (UT) dans leurs cellules respectives. Ce qui nous diff´erencie des travaux pr´ec´edents, c’est que nous tenons compte de l’al´ea avec lequel des demandes de transferts peuvent arriver et que, pour cette raison, nous mod´elisons la formation de queue de donn´ees au niveau des stations de base.
Dans cette disposition, nous d´eveloppons plusieurs algorithmes multicouches, r´ealisant de l’allocation de ressources d´ecentralis´ee, et ce, dans une optique d’efficacit´e ´energ´etique. En particulier, il s’agit ici de r´ealiser des algorithmes r´ealisant du beamforming de fa¸con d´ecentralis´ee et capables de contrˆoler des fluctuations de trafic, des algorithmes optimisant l’efficacit´e ´energ´etique sous une contrainte de qualit´e de service moyenne, des algorithmes de planification d´ecentralis´es dans des sc´enarios multi-cellulaires. Dans cette perspective, nous choisissons de recourir non seulement `a des outils d’optimisation de la th´eorie
Contents
de Lyapunov, mais ´egalement `a la th´eorie des matrices al´eatoires et `a la th´eorie du contrˆole stochastique.
R´ esum´ e
Introduction
Dans ce manuscrit, nous pr´esentons une description g´en´erale d’un probl`eme multi-couches dans un contexte MIMO multi-cellules. En particulier, nous iden- tifions les motivations principales et les d´efis technologiques qui accompagnent ces probl`emes classiques. Enfin, nous abordons les contributions scientifiques principales, apport´ees dans le cadre de cette th`ese.
Motivations et d´ efis technologiques
Durant la derni`ere d´ecennie, la demande pour des transmissions de donn´ees sans fil a fortement augment´e et les pr´evisions sugg`erent une augmentation de type exponentielle dans le futur [1]. Dans ce contexte, plusieurs techniques ont ´et´e propos´ees pour r´epondre `a ce besoin croissant, dont deux techniques importantes, abord´ees lors de cette th`ese : la densification du r´eseau sans fil et des techniques multi-antennes. Nous allons, dans cette partie, aborder ces deux techniques plus en d´etail.
Une ´etude des diff´erentes techniques, d´evelopp´ees au cours des 50 derni`eres ann´ees pour permettre d’augmenter les d´ebits de transmissions de donn´ees dans les r´eseaux sans fil, montrent que les gains les plus ´elev´es en termes d’efficacit´e spectrale peuvent ˆetre obtenu via une densification du r´eseau [2], i.e. par une r´eduction de la taille des cellules. Cela am`ene, intrins`equement, au concept de small cells networks (SCNs, r´eseaux de petites cellules litt´eralement) [3, 4], qui est principalement bas´e sur l’id´ee d’un d´eploiement dense de stations de base (BS) auto-organis´ees, peu coˆuteuses financi`erement et ´energ´etiquement, situ´ees plus pr`es des utilisateurs qu’elles doivent servir. La r´eduction de distance entre les transmetteurs et les r´ecepteurs permettant alors d’obtenir deux avantages : une meilleure qualit´e de lien de transmission, ainsi qu’une meilleure r´eutilisation spatiale des ressources spectrales, le tout `a une consommation ´energ´etique plus
Contents
faible. Cependant, le concept de SCNs apporte son lot de d´efis technologiques non r´esolus, tels que le traitement d’interf´erences, l’organisation du trafic, la disposition optimale des cellules, la gestion du handover dans ce contexte, des questions de s´ecurit´e, l’infrastructure backhaul, etc. . . Pour une ´etude d´etaill´ee de l’´etat de l’art sur les techniques li´ees aux SCNs, nous invitons le lecteur `a se r´ef´erer `a [3, 4].
D’autre part, les gains potentiellement offerts par de telles techniques sont depuis longtemps admis dans la litt´erature [5] et sont parfois pour la plupart d´ej`a impl´ement´es `a l’heure actuelle [6]. Le concept de MIMO a par exemple d´ej`a
´
et´e introduit dans plusieurs travaux tels que [7, 8]. Les techniques MIMO offrent des gains en terme de puissance, permettent une qualit´e de lien plus ´elev´ee et permettent ´egalement une augmentation significative du d´ebit, en multiplexant plusieurs flux de data dans un seul et mˆeme resource block.
Pour ces raisons et puisque ces techniques joueront probablement un rˆole majeur dans les r´eseaux futurs, nous consid´ererons, dans le cadre de cette th`ese, un mod`ele multi-cellules MIMO.
La majeure partie des travaux r´ecents abordant le concept de MIMO sont bas´es sur des consid´erations de couche physique et ont tendance `a ignorer des aspects li´es aux couches sup´erieures (par exemple, les dynamiques du trafic, le control des flux, etc. . . ). Les probl`emes pr´ec´edents sont pos´es comme des probl`emes d’optimisation statiques, qui assument que les transmetteurs sont toujours satur´es avec des bits d’information `a envoyer au r´ecepteur et ont donc tendance `a oublier les aspects dynamiques du trafic. Cependant, dans les r´eseaux cellulaires du futur, les variations ressenties au niveau du trafic peu- vent s’av´erer tr`es significatives, comme expliqu´e dans [9, 10]. Ce r´esultat est principalement dˆu `a la demande croissante et r´ecente de transferts data af- fili´es `a la vid´eo, qui varie au cours du temps en bursts difficilement pr´evisibles.
Dans ce sc´enario, une pr´e-allocation de ressources simplement bas´ee sur des con- sid´erations de couche physique peut aboutir `a une sous-utilisation des ressources disponibles. Un exemple parlant s’av`ere ˆetre un sc´enario dans lequel chaque BS pr´e-alloue certaines ressources `a ses utilisateurs, mais ne poss`ede pas d’information sur leurs r´eels besoins de transmission (en particulier si leur buffer est vide ou plein `a cet instant). Cette sous-utilisation combin´ee avec le nombre croissant de souscripteurs mobiles implique directement que la capacit´e offerte par util- isateur soit compromise. Cons´equence directe de cela ´etant que les r´eseaux pourraient `a l’avenir ne plus ˆetre capables de satisfaire la demande croissante d’un nombre croissant d’utilisateurs. Pour cette raison, les r´eseaux cellulaires du futur vont devoir prendre en compte les aspects dynamiques et stochastiques
Contents
du trafic dans leurs algorithmes d’allocations. Des gains significatifs peuvent ˆ
etre obtenus en partageant l’information au niveau de plusieurs couches et en r´ealisant une optimisation multi-couches.
Pour ces raisons, nous consid´erons dans cette th`ese un sc´enario multi-cells MIMO, qui impl´emente des aspects dynamiques au niveau du trafic. En partic- ulier, on consid`ere que les sch´emas repr´esentant les arriv´ees dans les buffers des BS sont mod´elis´es al´eatoirement et on ´etudie alors la stabilit´e des queues de pa- quets, le contrˆole des flux de trafic et l’optimisation de l’allocation de ressources dans ce contexte MIMO multicellulaire.
Par le pass´e, de nombreux travaux ont cherch´e `a traiter du probl`eme de la stabilit´e des queues de paquets dans les r´eseaux sans fil. L’id´ee principale est bas´ee sur les travaux remarquables de Tassiulas et Emphremendis [11], qui ont introduit le r´esultat de maximum weighted based scheduling , garantissant une optimalit´e en termes de d´ebits. Par la suite, ces travaux ont ´et´e g´en´eralis´es dans diff´erents papiers [12, 13, 14, 15]. Cependant, la majeure partie des travaux mentionn´es pr´ec´edemment simplifient la fa¸con de mod´eliser la couche physique, rendant souvent l’impl´ementation en pratique peut r´ealiste, voire impossible.
En particulier, ils mod´elisent l’interf´erence en admettant que deux liens ne peu- vent transmettre `a un mˆeme moment si l’un des liens est `a port´ee du second.
Il s’agit alors de d´efinir un ensemble de liens susceptibles de transmettre au mˆeme moment, sans g´en´erer de conflits. Cependant un tel mod`ele suppose que l’on consid`ere un sch´ema de transmission o`u les canaux sont orthogonalement r´epartis. Les r´ecentes avanc´ees dans les domaines de power control, beamform- ing et traitement d’interf´erence permettent aujourd’hui `a plusieurs utilisateurs de transmettre en utilisant le mˆeme resource block. Dans ce contexte, il semble important de consid´erer des aspects stochastiques au niveau de la fa¸con dont sont mod´elis´es les trafics. C’est l’enjeu principal de cette th`ese, `a savoir ˆetre capable de prendre en compte des aspects al´eatoires de mod´elisation du trafic dans des mod`eles technologiques r´ecents de r´eseaux MIMO multicellulaires.
Les designs d’algorithmes propos´es dans cette th`ese traitent ´egalement deux probl`emes d’´egale importance, souvent r´ef´er´es comme design d´ecentralis´e et ef- ficacit´e ´energ´etique.
Design d´ecentralis´e multi-couches: Etant donn´e le nombre massif de BS d´eploy´ees dans des mod`eles SCNs, une entit´e centralis´ee qui g`ere la co- ordination des diff´erentes BS est pour l’instant improbable. Pour rendre ce design impl´ementable en pratique aujourd’hui, les SCNs doivent fonc- tionner de fa¸con d´ecentralis´ee. Cela suppose donc que chaque cellule doit mettre en pratique son processus d’optimisation en utilisant l’information
Contents
disponible localement, ainsi qu’un nombre limit´e d’informations obtenues via un ´echange avec d’autres cellules distantes. Au mˆeme moment, nous devons nous assurer qu’un processus d´ecentralis´e ne d´et´eriore pas trop la performance globale de notre syst`eme. Pour cette raison une question que nous posons dans cette th`ese porte sur l’optimisation d´ecentralis´ee des SCNs. En particulier, nous formulerons nos algorithmes d’optimisation de telle sorte `a obtenir une bonne performance en limitant les ´echanges d’information n´ecessaires entre des cellules distantes.
Efficacit´e ´energ´etique de notre algorithme: L’explosion du trafic est sus- ceptible d’ˆetre accompagn´e d’une augmentation drastique de la consom- mation ´energ´etique au niveau de notre r´eseau, qui peut ˆetre interpr´et´e en termes d’indice carbone [16]. Cr´eer un design ´energ´etiquement efficace est donc important dans le sens o`u il r´eduira alors les coˆuts de fonction- nement associ´es aux SCNs [17]. Il s’agit donc d’ˆetre capable de cr´eer des designs dans lesquels on cherche `a minimiser la consommation ´energ´etique du r´eseau en maintenant une qualit´e de service (QoS) ad´equate pour les utilisateurs, le tout, dans un contexte mulitcellulaire MIMO.
Nous allons `a pr´esent d´etailler l’organisation de cette th`ese et les principales contributions apport´ees.
Organisation et contributions
Le mod`ele suivant, d´etaill´e en figure 1, est celui que nous avons consid´er´e dans l’int´egralit´e des sc´enarios abord´es dans cette th`ese.
Ce mod`ele repr´esente un sc´enario multicellulaire, dans lequel chaque BS doit servir ses utilisateurs dans ses cellules respectives. Chaque BS est par ailleurs
´
equip´ee d’antennes multiples et chaque UT ne poss`ede qu’une seule antenne. Les BS poss`edes des queues d´edi´ees utilis´ees comme buffers pour stocker les paquets des utilisateurs qu’elles sont suppos´ees servir. Le trafic est mod´elis´e par des arriv´ees de paquets au niveau du r´eseau, directement int´egr´ees dans les queues de chaque BS, afin de pouvoir servir les utilisateurs plus tard. Les BS ont un objectif consistant `a servir les utilisateurs en partageant les ressources allou´ees `a leurs utilisateurs de telle sorte `a stabiliser leurs queues. Nous consid´erons donc le probl`eme de stabilisation de queues, bas´ees sur les hypoth`eses pr´ec´edentes et bas´es sur diff´erentes connaissances possibles de l’´etat du canal (Channel State Information, CSI). De plus, ´etant donn´e que les ´echanges d’information entre BSs est coˆuteux, nous formulons des algorithmes d’allocation qui consid`erent
Contents
Cell1 Cell2
BS1 BS2
UT UT UT UT
Q Q Q Q
Network
1,1 2,K
1,1
1,K 2,1
1,K 2,1 2,K
Figure 1: Sch´ema de mod`ele coh´erent dans un contexte multicellulaire MIMO.
Chaque BS est alors ´equip´ee de queues utilis´ees comme buffers pour stocker les paquets des utilisateurs qu’elles doivent servir.
Contents
des ´echanges d’information possibles, mais en nombre limit´e.
Etant donn´e la formulation de mod`ele pr´ec´edente, nous pouvons alors poser
diff´erents probl`emes d’allocation de ressources et ´etudier diverses solutions d´ecentralis´ees.
La th`ese est alors divis´ee en trois parties. Premi`erement, dans le chapitre 2, nous pr´esentons un ´etat de l’art des r´esultats d´ej`a disponibles pour des probl`emes similaires, qui seront utilis´es dans cette th`ese. Dans le chapitre 3, nous traitons le cas d’un probl`eme joint de contrˆole de trafic et de traitement d’interf´erence dans des r´eseaux multicellulaires MIMO. Nous consid´erons un contrˆoleur de flux connect´e `a un grand nombre de BS, dont la mission est de r´eguler le trafic et les arriv´ees dans les queues de chaque BS. Le trafic doit ensuite ˆetre transmis via une transmission sans fil d’une BS vers l’utilisateur appropri´e. Les BSs r´ealisent pour cela du beamforming coordonn´e multicellu- laire MIMO, afin de transmettre efficacement leurs donn´ees. Le nombre de bits envoy´es et liquid´es dans la queue de chaque BS d´epend alors du SINR entre la BS et l’utilisateur consid´er´e. Ce qui am`ene `a prendre en compte deux aspects alors essentiels :
Le contrˆoleur de flux doit alors ajuster ses d´ecisions de r´egulation en prenant en compte la connaissance partielle ou compl`ete `a propos du CSI relative aux liens sans fils entre les BSs et les utilisateurs.
Les BSs doivent r´ealiser un beamforming coordonn´e multicellulaire, en limitant les ´echanges d’informations entre BSs.
La premi`ere hypoth`ese repose principalement sur le fait que le contrˆoleur de flux est connect´e `a un grand nombre de small cells BSs and ne peut tenir compte de toutes les conditions et ´evolutions des canaux au niveau de toutes les BSs. Le deuxi`eme permet au design SCNs de pouvoir ˆetre impl´ement´e sans n´ecessiter pour autant une infrastructure de backhaul trop importante.
Le chapitre 3 est divis´e en deux parties. Dans la premi`ere partie, on d´eveloppe un mod`ele r´eduit de beamforming multicellulaire. Dans lequel les BSs n’ont be- soin d’´echanger que les statistiques associ´ees aux dynamiques des canaux entre eux, plutˆot qu’un CSI instantan´e. Th´eoriquement, la performance d’un tel al- gorithme correspond exactement `a celle acquise par un algorithme centralis´e (avec un ´echange en temps r´eel des CSI instantan´es), lorsque le nombre de BSs et d’utilisateurs augmente `a l’infini. Pour cette raison, nous d´ecidons donc de recourir `a des outils de th´eorie des matrices al´eatoires (Random Matrix Theory, RMT). Dans la seconde partie, nous nous interessons `a un probl`eme de contrˆole de flux coupl´e avec un design de beamforming d´ecentralis´e comparable `a celui d´ecrit dans la partie pr´ec´edente. Plus particuli`erement, on d´eveloppe dans ce
Contents
cadre, un contrˆoleur de flux H∞ capable de r´eguler le trafic au niveau des BSs et conscient des dynamiques li´ees aux CSI entre les BSs et les utilisateurs. Les r´esultats de cette section ont ´et´e publi´es dans les articles suivants :
[J1] S. Lakshminaryana, J. Hoydis, M. Debbah and M. Assaad, ”Asymp- totic Analysis of Distributed Multi-cell Beamforming,” submitted toIEEE Transactions on Signal Processing,2012
[J2] S. Lakshminarayana, M. Assaad and M. Debbah, ”H∞ Control Based Scheduler for the Deployment of Small Cell Networks,” to appear inEl- sevier Performance Evaluation Journal, Special Issue of selected papers from WiOpt 2011 (accepted for publication)
[C1] S. Lakshminarayana, M. Assaad and M. Debbah, ”H∞ Control Based Scheduler for the Deployment of Small Cell Networks,”9th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wire- less Networks (WiOpt’11), Princeton, USA, 2011
[C2] S. Lakshminaryana, J. Hoydis, M. Debbah and M. Assaad, ”Asymp- totic Analysis of Distributed Multi-cell Beamforming,” IEEE Interna- tional Symposium on Personal, Indoor and Mobile Radio Communica- tions, (PIMRC’10), Istanbul, Turkey, 2010
Dans le chapitre 4, nous nous int´eressons plus sp´ecifiquement `a la conception d’algorithmes ´energ´etiquement efficients, via la question : Dans un r´eseau mul- ticellulaire MIMO, ´etant donn´e une contrainte moyenne de qualit´e de service (QoS) pour les utilisateurs, quelle est l’´energie minimale permettant de satis- faire cette contrainte ? La contrainte de QoS ici consid´er´ee est la diff´erence entre la moyenne de la puissance de signal moyenne par unit´e de temps et la moyenne de la puissance de l’interf´erence par unit´e de temps, que l’on contraint d’ˆetre sup´erieur `a une valeur pr´ed´efinie. L’int´erˆet principal de consid´erer des crit`eres de QoS moyenn´es par unit´e de temps repose sur le fait qu’il apporte de la flexibilit´e pour allouer dynamiquement nos ressources sur diff´erents canaux `a fading dont on connait les statistiques, compar´e `a des designs o`u l’on poss´ederait une connaissance instantan´ee des contraintes de QoS. Il peut ´egalement aboutir
`
a une r´eduction en moyenne de la consommation ´energ´etique de notre r´eseau.
D’un point de vue pratique, l’int´erˆet principal de consid´erer des contraintes de QoS moyennes repose sur le fait que des applications classique de services de donn´ees (partage de fichier, t´el´echargement vid´eo,. . . ) permet certaines flexi- bilit´es et accepte facilement certains d´elais.
Contents
On d´efinit, tout d’abord, l’ensemble faisable, satisfaisant la contrainte de QoS, par l’ensemble de toutes les contraintes de QoS moyennes pouvant ˆetre atteintes par une strat´egie d’allocation. Pour cela, on mod´elise les contraintes comme des queues et on consid`ere alors le probl`eme consistant `a stabiliser ces queues, tout en minimisant la consommation ´energ´etique du r´eseau. L’optimisation utilise une optimisation bas´ee sur la technique de Lyapunov [13], qui permet de formuler un probl`eme de contrˆole dynamique, visant `a minimiser la consomma- tion ´energ´etique. L’approche consid´er´ee met en œuvre une s´erie d’optimisations statiques qui doivent ˆetre r´esolus pour chaque p´eriode de temps. Ce probl`eme peut ˆetre reformul´e comme un probl`eme semi-definite programming (SDG). A chaque instant, la solution au probl`eme d’optimisation offre le vecteur de beam- forming optimal `a chaque instant. Notre algorithme permet alors de consid´erer un design d´ecentralis´e dans lequel les BSs peuvent reconstruire et approcher le vecteur de beamforming optimal en utilisant une information locale r´eduite `a propos du CSI local. L’´echange d’information entre BS se r´esumerait alors `a un
´
echange d’information sur leurs longueurs de queues respectives. Dans ce con- texte, nous apportons une comparaison de performance entre notre algorithme d´ecentralis´e et le probl`eme centralis´e avec connaissance totale : on montre alors que l’´ecart de consommation ´energ´etique entre la strat´egie d´ecentralis´ee et la strat´egie optimale sont acceptables. Par la suite, nous caract´erisons la perfor- mance de nos algorithmes dans des cas o`u l’information ´echang´ee s’av`ere ˆetre d´elay´ee : il s’av`ere que la contrainte de QoS peut ´egalement ˆetre atteinte, mais que le d´elai affecte cependant la performance en terme d’efficacit´e ´energ´etique, la r´eduisant jusqu’`a une valeur constante.
Les r´esultats de cette question peuvent ˆetre trouv´es dans les articles suivants :
[J3] S. Lakshminaryana, M. Assaad and M. Debbah, ”Energy Efficient Cross- Layer Design in MIMO Multi-cell Systems,”to be submitted
[C3] S. Lakshminaryana, M. Assaad and M. Debbah, ”Energy Efficient Cross- Layer Design in MIMO Multi-cell Systems,”to be submittedInterna- tional Conference on Acoustics, Speech, and Signal Processing (ICASSP’13), 2013
Dans le chapitre 5, nous consid´erons un probl`eme d’allocation d´ecentralis´e dans un sc´enario consistant en deux BSs devant servir leur utilisateur respectif (un utilisateur pour une BS). L’objective dans ce contexte est de stabiliser les queues pour un flux de trafic en arriv´ee au niveau des queues connu. On ad- met que ce flux de trafic permet de garantir la stabilit´e des queues rendant le
Contents
probl`eme r´ealisable. Nous proposons, ainsi, un algorithme appel´e Fast CSMA (Carrier Sense Multiple Access) bas´e sur un algorithme d´ecentralis´e, mod´elisant l’interf´erence via un crit`ere de SINR. Dans notre algorithme, les BSs, doivent seulement ´echanger un bit de donn´ees entre elles. D’une part, on peut remarquer que l’application directe de l’algorithme FCSMA dans un mod`ele `a interf´erence bas´ee sur le SINR ne permet pas d’atteindre une bonne performance. Cepen- dant, en combinant cet algorithme avec une r`egle de s´eparation dynamique du trafic, la performance obtenue redevient correcte. L’aspect innovant de cet al- gorithme repose alors sur la nature d´ecentralis´ee de l’op´eration et la possibilit´e de l’appliquer `a des sc´enarios de canaux `a ´evanouissement.
Les r´esultats de cette section peuvent ˆetre trouv´es dans l’article suivant : [C2] S. Lakshminarayana, B. Li, M. Assaad, A. Eryilmaz and M. Debbah, ”A
Fast-CSMA Based Distributed Scheduling Algorithm under SINR Model”
IEEE International Symposium on Information Theory (ISIT’12), Cam- brigde, MA, USA, 2012
La th`ese se conclue avec un chapitre 6, qui r´esume quelques-uns des r´esultats majeurs de cette th`ese et propose un aper¸cu des travaux futurs.
Autres publications r´ealis´ees dans le cadre de cette th`ese :
[C3] S. Lakshminarayana, M. Debbah and M. Assaad, ”Asymptotic Analy- sis of Downlink Multi-cell Systems with Partial CSIT”, IEEE Interna- tional Symposium on Information Theory (ISIT’11), St-Petersburg, Rus- sia, 2011
Conclusion et travaux futurs
Les pr´evisions envisagent une explosion du trafic de donn´ees au sein des r´eseaux sans fils du futur, ce qui aura pour cons´equence d’accroitre de fa¸con significa- tive la pression g´en´er´ee dans la gestion de la capacit´e au sein des r´eseaux d´ej`a existants. Pour cette raison, de nombreux chercheurs du domaine acad´emique, autant que du domaine industriel, ont cherch´e ces derni`eres ann´ees `a ´elaborer des techniques, qui permettront au r´eseau actuel d’encaisser au mieux cette explosion de la demande.
Cette th`ese se concentre principalement sur un contexte multicellulaire MIMO.
La plupart des algorithmes d´ej`a existants, cherchent `a optimiser des crit`eres purement affili´es `a des consid´erations de couche physique. Ils r´ealisent une allo- cation de ressources, de fa¸con statique et ne prennent pas en compte la nature stochastique du trafic. Dans la mˆeme p´eriode, des travaux se sont attach´es `a
Contents
´
etudier des probl`emes de stabilit´e de queues au niveau des r´eseaux. Cependant, dans la majorit´e de ces travaux, la mod´elisation au niveau de la couche physique est simplifi´ee, rendant le mod`ele peu r´ealiste et difficilement impl´ementable en pratique. Pour cette raison, il est n´ecessaire de concevoir de nouveaux algo- rithmes qui peuvent prendre en compte `a la fois la nature stochastique du trafic, mais ´egalement des aspects r´ealistes en terme de couche physique, tels que le fading, le path loss, l’interf´erence, une connaissance imparfaite du CSI, du contrˆole de puissance, des technologies MIMO,etc. . . Cette th`ese propose quelques algorithmes prenant en compte ces deux consid´erations, en gardant `a l’esprit que les algorithmes devront fonctionner de fa¸con d´ecentralis´ee et devront ˆ
etre ´energ´etiquement efficaces.
Nous r´esumons, `a pr´esent, bri`evement les r´esultats principaux de cette th`ese et mettons en ´evidence les possibles limites et/ou extension de notre mod`ele et des algorithmes qui y sont associ´es.
Dans le chapitre 3, nous avons formul´e un algorithme de beamforming avec un overhead de taille r´eduite, en employant des outils de la th´eorie des ma- trices al´eatoires. En utilisant une analyse asymptotique, nous avons prouv´e l’optimalit´e de la strat´egie de beamforming `a overhead r´eduit. Dans un sc´enario MIMO, nous avons ´egalement mis en ´evidence les sets de strat´egies faisables en termes de SINR, dans un r´eseau cellulaire MIMO, en utilisant des outils d’analyse de syst`emes larges. Nos r´esultats montrent qu’un ´echange d’information
`
a une ´echelle de temps proche de celle des dynamiques du canal permet d’atteindre de bonne performance en pratique. Une am´elioration envisag´ee consiste `a car- act´eriser les fluctuations en termes de SINR per¸cu en downlink, dans un syst`eme
`
a dimensions finies. Pour tenir compte des fluctuations du SINR autour de la valeur vis´ee, il est possible de r´esoudre le probl`eme en utilisant un algorithme ROBF et en consid´erant une valeur plus ´elev´ee pour le SINR que la valeur pr´ec´edemment voulue.
Plus tard dans ce chapitre, nous d´eveloppons un contrˆoleur de flux pour syst`emes MIMO multicellulaires en utilisant un contrˆole H∞, qui peut fonction- ner sans connaissance des CSI associ´es aux diff´erents liens sans fils du syst`eme.
Nous voudrions souligner que dans notre solution, nous avons d´ecoupl´e les probl`emes de beamforming et de contrˆole de flux en deux parties distinctes.
Cependant, une m´ethode meilleure consisterait `a r´ealiser l’optimisation con- jointe du contrˆoleur de flux et du probl`eme de beamforming (comme par ex- emple dans [13], qui apporte un exemple d’algorithme optimisant `a la fois le probl`eme de beamforming et le contrˆoleur de flux, dans un r´eseau SISO et un mod`ele d’interf´erence conflictuel bas´e sur un graphe). Cette distinction peut
Contents
ˆ
etre per¸cue dans notre travail comme un sacrifice volontaire de performance, permettant de rechercher alors une solution au probl`eme ´equivalent d´ecentralis´e.
Dans le chapitre 4, nous avons consid´er´e le probl`eme visant `a minimiser la consommation ´energ´etique d’un r´eseau soumis `a une contrainte de QoS `a long terme dans un contexte de r´eseau MIMO multicellulaire. Nous avons montr´e que des contraintes de QoS moyennes permettent d’atteindre de meilleurs r´esultats en termes d’efficacit´e ´energ´etique, compar´e au probl`eme ´equivalent dans lequel les contraintes de QoS seraient donn´ees instantan´ement `a chaque instant. Une future direction possible pourrait consister `a trouver le vecteur de beamforming optimal associ´e `a un probl`eme de transmission devant satisfaire une contrainte de QoS moyenn´ee en temps (et de la forme log(1+SINR) ) et renvoie ainsi
`
a un probl`eme r´ealiste de stabilisation de queue. L’application de technique d’optimisation Lyapunov `a ce probl`eme aboutit `a un probl`eme de maximisation de d´ebit moyen, dans un sc´enario MIMO multicellulaire, connu pour ˆetre un probl`eme non-convexe. Une extension ´egalement possible consisterait `a r´ealiser l’optimisation conjointe appliqu´ee au feedback CSI (optimiser la formation de canal durant chaque time slot et optimiser le nombre de bits allou´es au feedback dans le cas d’une quantification pour le feedback) et du probl`eme de beamform- ing.
Finalement, dans le chapitre 5, nous avons d´evelopp´e un algorithme d’allocation distribu´e bas´e sur la technologie FCSMA, dans un sc´enario de canaux interf´er´es et une interf´erence bas´ee sur le SINR. Pour des raisons de mall´eabilit´e, nous avons consid´er´e un mod`ele sym´etrique. Des g´en´eralisations possibles de cet al- gorithme FCSMA dans un cas g´en´eral de r´eseau ont ´et´e mentionn´ees `a la fin du chapitre 5.
Nous apportons finalement des conclusions g´en´erales d´eriv´ees de cette th`ese.
Durant cette th`ese, nous avons tent´e d’incorporer des consid´erations r´ealistes telles que des flux de trafic et des gestions de queues dans des syst`emes multicel- lulaires MIMO. D’un point de vue couche physique, nos travaux apportent un aper¸cu basique de la fa¸con dont il est possible de g´erer l’aspect stochastique du trafic et de maintenir une stabilit´e acceptable au niveau des queues de syst`emes MIMO. Nous montrons que les am´eliorations en termes de performance sont obtenues en r´ealisant une optimisation de notre syst`eme de fa¸con multi-couche, plutˆot que de r´ealiser une optimisation classiquement purement bas´ee sur la couche physique (nos r´esultats montrent une am´elioration en termes d’efficacit´e
´
energ´etique). Nos travaux contribuent ´egalement `a prendre en compte des as- pects de d´ecentralisation au niveau de nos algorithmes d’optimisation, qui per- mettent d’atteindre des performances sensiblement ´equivalentes `a celles obtenus
Contents
avec des optimisations centralis´ees. Nos travaux soul`event finalement des ques- tions ouvertes sur la fa¸con dont l’optimisation de probl`emes purement associ´es
`
a la couche physique (tels que le fading, le path loss l’interf´erence, une connais- sance imparfaite du CSI, technologies MIMO. . . ) peuvent ˆetre g´er´e au niveau du r´eseau.
Nous concluons finalement cette th`ese en donnant quelques id´ees possible de poursuites de travaux.
Travaux futurs
Feedback CSI et stabilit´ e de queues dans un r´ eseau MIMO multicellulaire
Une des limitations fondamentales dans la performance des syst`emes sans fils consiste en l’cquisition du CSI. En particulier, les sch´emas de feedback CSI ont longtemps ´et´e ´etudi´es dans le contexte multi-utilisateur MIMO [18, 19] (feed- back num´erique et analogique) avec l’objectif de maximiser certaines m´etriques telles que le d´ebit moyen ergodique. Dans cette th`ese, nous avons essay´e de mettre en relation la notion de stabilit´e de queues avec des techniques de trans- mission utilisant des antennes multiples. Un extension ´evidente de nos travaux consisterait `a mettre en relation le probl`eme de stabilit´e de queues avec celui de l’acquisition d’un feedback CSI. Les questions suivantes se posent alors. Com- ment ´evolue la r´egion de stabilit´e des queues avec le taux moyen de feedback CSI
? Etant donn´e un d´ebit moyen de feedback CSI, quand et avec quelle pr´ecision les UTs peuvent-ils transmettre leur feedback CSI aux BSs ?
Un autre probl`eme int´eressant consisterait `a concevoir un syst`eme g´erant conjointement les feedbacks CSI et les techniques de transmissions, capable d’une certaine performance avec un nombre de feedbacks CSI r´eduits. Dans ce but, une direction int´eressante serait d’exploiter la corr´elation temporelle inh´erente aux processus stochastiques associ´es aux canaux. La plupart des travaux utilisent des processus i.i.d. pour mod´eliser l’´evolution des canaux au cours du temps. Ce mod`ele a ´et´e un choix populaire en raison de sa simplicit´e, permettant de r´eduire drastiquement la complexit´e de l’analyse des syst`emes dans lequel il est consid´er´e. Mais, ce mod`ele est insuffisant, car il ne permet pas de prendre en compte la corr´elation temporelle inh´erente aux canaux. On peut, cependant, mod´eliser ce ph´enom`ene, en recourant `a des canaux de Markov [20]. La m´emoire inh´erente aux canaux peut aider `a r´eduire le besoin de feed- backs CSI, compar´e `a des mod`eles i.i.d. Le probl`eme d’optimisation conjointe
Contents
peut alors ˆetre mod´elis´e et r´esolu via des des processus de d´ecision Markoviens (litt´eralement, Markov Decision Processes, MDPs), comme explicit´e dans les travaux [21, 22].Un autre sc´enario int´eressant consiste `a optimiser le feedback CSI en consid´erant un mod`ele de canaux qui admet un corr´elation temporelle mais est non-stationnaire, qui peut ˆetre acquis via des techniques telles que des algorithmes d’apprentissage.
Algorithmes efficaces en termes de d´ elais
Les nouvelles applications telles que le vid´eo streaming, les appels vid´eos et les jeux en ligne demandent de bonnes garanties en termes de performance de d´elais.
La conception d’algorithmes capables de contenir le d´elai dans des proportions acceptables, pour des r´eseaux sans fils a sollicit´e ´enorm´ement d’attention ces derni`eres ann´ees [23, 24]. Il est bien connu que l’utilisation d’antennes multi- ples apporte des degr´es de libert´e suppl´ementaires. Une question int´eressante serait alors de savoir comment exploiter ces degr´es suppl´ementaires pour offrir une meilleure performance en termes de d´elais. Il est ´egalement possible de poser le probl`eme de l’exploitation d’antennes multiples pour g´erer un trafic sous une contrainte de d´elai (ce qui est primordial dans certaines applications multim´edia).
Strat´ egies d’allocation opportunistes pour des r´ eseaux cog- nitifs h´ et´ erog` enes
Les id´ees d´evelopp´ees dans cette th`ese peuvent ˆetre ´etendues aux sc´enarios de r´eseaux cognitifs h´et´erog`enes [25, 26, 27]. La notion de r´eseaux cognitifs h´et´erog`enes se rapporte `a un r´eseau sans fils classique auquel on superpose une densification d’autres cellules (par exemple des femtocellules), capable de prendre en compte les variations de son environnement de fa¸con intelligente et de r´ealiser, en cons´equence, une allocation de ressources dynamique. Dans de tels r´eseaux, on esp`ere ˆetre capable de g´erer l’allocation de ressource entre les femtocellules et les macrocellules , grˆace `a une adaptation dynamique du r´eseau, par rapport aux changement ressentis de son environnement. Dans un tel sc´enario, on peut alors se poser les questions suivantes. Etant donn´e une contrainte de QoS pour les utilisateurs associ´es `a des macrocellules, quel est le niveau maximal d’utilit´e pouvant ˆetre atteint et garantissant la coexistence des transmetteurs-r´ecepteurs cognitifs ? De fa¸con ´equivalente, combien de liens cognitifs transmetteurs-r´ecepteurs peuvent ˆetre actifs `a un mˆeme instant, sans perturber les transmissions des utilisateurs associ´es aux macrocellules ? Ces
Contents
probl`emes peuvent ˆetre formul´es comme des probl`emes d’optimisation stochas- tiques et il est possible de recourir aux outils d’optimisation de Lyapunov, afin d’en d´eduire des algorithmes efficaces dans ce contexte. Ce sc´enario s’av`ere particuli`erement int´eressant, dans le sens o`u les aspects symm´etriques des flux de donn´ees des utilisateurs macrocellulaires, l’aspect stochastique du trafic, et les ´etats des diff´erents canaux, vont offrir un multiplexage statistique, qui con- stituera une opportunit´e permettant aux utilisateurs cognitifs de coexister. Les paires de transmetteurs-r´ecepteurs cognitifs peuvent ainsi utiliser de fa¸con op- portuniste les ressources disponibles, en garantissant `a chacun une bonne qualit´e de service.
Notations
CN×M the set of complex-valuedN×M matrices RN×M the set of real-valuedN×M matrices
CN,RN short form forCN×1 andRN×1(column vectors)
X matrix
X(i, j) (i, j) entry ofX tr(X) trace of the matrixX rank(X) rank of the matrixX XT transpose of the matrixX
XH complex conjugate transpose of the matrixX IM identity matrix of sizeM
diag(x1, ..., xM) diagonal matrix with the elementsxi along its main diagonal
CN(m,R) complex Gaussian distribution with meanmand covariance matrixR
−−→a.s. almost sure convergence
E[X] expectation of a random variableX aN bN aN−bN −−→a.s. 0
x column vector
xi ith element of the column vector C,R the spaces of complex and real numbers
(x)+ max(x,0)
ρ(X) spectral radius of matrixX X≤Y element wise inequality log(x) natural logarithm
Nt, K → ∞ Nt, K ∈N+,the following condition onNtandK, 0<lim infK→∞NKt ≤lim supK→∞NKt <∞.
S \x the remaining set when memberxis removed
0 vector of zeros
Acronyms
BS base station CS central station
CSI channel state information CSMA carrier sense multiple access CTMC continuous time Markov chain FCSMA fast CSMA
e.s.d. empirical spectral distribution
ICT information and communication technology i.i.d. independent and identically distributed LHS left hand side
LQG linear quadratic Gaussian MAC multiple access channel MIMO multiple input multiple output MISO multiple input single output MMSE minimum mean square error QoS quality of service
OFDM orthogonal frequency division multiplexing RHS right hand side
RMT random matrix theory
Rx receiver
SCN small cell networks SNR signal to noise ratio
SINR signal to interference noise ratio SOCP second order conic programming SDP semi-definite programming Tx transmitter
UT user terminal
Chapter 1
Introduction
In this chapter, we present a general description of the problem of cross-layer design in multiple input multiple output (MIMO) multi-cell systems. In partic- ular, we identify the main motivation and the technological challenges behind this problem. Finally, we describe the main contributions presented in this thesis.
1.1 Motivation and Technological Challenges
During the last decade, there has been an ever increasing demand for wireless data services and it is expected to increase exponentially in the future as well [1]. While many different techniques have been proposed to cope up with the increasing data rate demand, the two important techniques which are relevant to this thesis are the concepts of network densification and multiple antenna techniques. We will now describe these two factors in greater detail.
A study of various techniques that have been developed over the last 50 years to enable higher data rates in wireless communication systems shows that the biggest gains in the efficiency of spectrum utilization has been due to network densification [2], i.e., shrinking of cell sizes. This leads to the concept of small cell networks (SCNs) [3, 4] which is based on the idea of a very dense deployment of self-organizing, low-cost, low-power base stations (BSs), bringing them closer to the user terminals (UTs) they serve. The reduction in distance between the transmitter and the receiver creates the dual benefit of higher link qualities and better spatial reuse. It also implies reduction in the amount of power transmitted. However, the reduction of cell sizes imposes numerous technical challenges in the design of such SCNs. Some of the technical issues faced in the implementation of SCNs are the problems of interference management, traffic
1.1. Motivation and Technological Challenges
scheduling, optimal cell size planning, call handover issues, security, backhaul infrastructure etc. For a detailed survey on the SCN deployment and design challenges in SCNs, the reader can refer to [3, 4].
On the other hand, the gains of using multiple antennas at the transmitter and receiver have been well understood in literature [5] and has already become a part of the current day cellular systems [6]. The concept of MIMO systems was first introduced in the seminal works of [7, 8]. MIMO techniques can pro- vide power gains, improve the link reliability, and increase the throughput by multiplexing several independent data streams in the same resource block.
The aforementioned factors motivate us to consider in this thesis, a MIMO multi-cell setup as they are expected to play a key role in the design of next generation cellular systems.
Most of the prior works on the design of MIMO systems are based on phys- ical layer considerations and tend to ignore the higher layer process (e.g. traffic dynamics, flow control etc). The problems are posed as static optimization prob- lems which assume that the transmitter is always saturated with information bits to be sent to the receiver and tend to ignore the stochastic nature in the traffic patterns. However, future cellular networks are expected to experience a much wider range of fluctuations in their traffic patterns [9, 10]. This is mainly a result of the increased multimedia related traffic which tends to be time vary- ing and bursty nature. In this scenario, pre-allocation of resources based only on physical layer considerations can lead to underutilization of resources. For example, consider a scenario in which the BS pre-allocates certain resources to a UT during a given time slot but has no information to transmit (because it user’s buffer might be empty). The underutilization combined with the increas- ing number of mobile subscribers implies that the capacity of the present day wireless networks is significantly stressed. As result, cellular networks designed with traditional physical layer optimization based approaches might not be able to support the demands of the large number of UTs. Therefore, future cellular networks require dynamic resource allocation algorithms, which can take into account the stochastic nature of the traffic patterns. Significant gains can be obtained by sharing information across the layers and optimizing the design from a cross-layer perspective.
Motivated by the aforementioned considerations, in this thesis, we consider the design aspects in MIMO multi-cell scenario while incorporating the dynamic nature of cellular traffic. In particular, we consider the randomness in traffic arrival patterns and hence account for queuing of information bits at the BS.
We deal with issues such as queuing stability, traffic flow control and cross-layer
1.1. Motivation and Technological Challenges
based optimization of the system parameters in MIMO multi-cell networks.
There have been many works in the past which deal with the issue of queuing stability in wireless networks. The main idea is based on the seminal work of Tassiulas and Emphremedis [11], which introduced the celebrated result of max- imum weight based scheduling with throughput optimality1guarantees. Subse- quently, this theory has been generalized in many different works [12, 13, 14, 15].
However, most of the aforementioned works simplify the modeling of the physi- cal layer, often making it unrealistic for practical implementation. In particular, they assume a conflict graph based interference model at the physical layer, in which two links cannot transmit simultaneously if one link is within the trans- mission range of the other. The task is then to schedule a set of non-conflicting links for transmission. However, the conflict graph based interference model can only account for orthogonal channel access schemes. Advances in physical layer techniques like multiple antenna based technologies, power control, beam- forming and interference alignment allow cellular UTs to share and coexist over the same time/frequency resource blocks. Hence, it is important to consider the randomness of traffic patterns with advanced physical layer models. This is indeed the main idea of this thesis. The work in this thesis attempts to develop a cross-layer design framework in MIMO multi-cell networks.
The design algorithms developed in this thesis are coupled with two issues which are of paramount importance in the design of future cellular networks, namely decentralized design and energy efficiency.
Issue of decentralized cross-layer design: Owing to the sheer number of SCN BSs which are planned to be deployed, a centralized entity coordinat- ing all the SCN transmissions would be impossible. To make the design practically viable, the SCNs must function in a decentralized manner.
This implies that each cell should optimize its performance relying mainly on the locally available information and limited amount of additional side information exchanged between the neighboring cells. At the same time, it must be ensured that the decentralized operation of the cells does not significantly deteriorate the overall system performance. Thus, one of the key question we address in this thesis is the decentralized design of SCNs.
In particular, we formulate our cross-layer design algorithms with reduced information exchange between the cells which provide a good overall sys- tem performance.
Issue of energy efficient cross-layer design: The second concern addressed
1A scheduling policy is said to be throughput optimal if it achieves any throughput (subject to network stability) that is achievable by any other scheduling strategy.
1.2. Outline and Contributions
in this thesis is the problem of energy-efficient transmissions. The explo- sion in wireless traffic is likely to cause a substantial increase in informa- tion and communication technology (ICT) related carbon emissions [16].
Energy efficient deisgn is also important because it can lead to significant reduction in the cost of operating the network [17]. Therefore, the second important aspect we consider in our cross-layer design algorithms is the issue of minimizing energy expenditure subject to quality of service (QoS) constraints for the users, in MIMO multi-cell networks.
We will now proceed to list the basic outline and the main contributions of the thesis.
1.2 Outline and Contributions
The system set-up which is common to all the scenarios considered in this thesis is provided in Figure 1.1.
The set up consists of a multi-cell scenario. Each cell has a BS serving the UTs in its respective cell. The BSs are equipped with multiple antennas and the UTs have a single antenna each. The BSs have dedicated queues to buffer the packets of the UTs they serve. The traffic arrives from the network into the queues present at the BS, where they can be buffered before being transmitted over the wireless medium. The BSs have to perform the task of resource shar- ing among the UTs with the objective of stabilizing the queues. We consider the queue-length stabilization problem under various assumptions on channel state information (CSI) knowledge at the BS. Additionally, since information exchange between the BSs is costly, we formulate the resource allocation algo- rithms with limited information exchange between them.
With the above system set up, we formulate a number of resource allocation problems and provide decentralized solutions. The thesis is divided into three main parts.
First, in Chapter 2, we present some background of the existing results which will be used in this thesis.
In Chapter 3, we deal with the joint problem of traffic flow control and interference management in MIMO multi-cell networks. We consider a flow controller connected to a large number of BSs, which regulates the traffic arrival into the queues present at the BSs. The traffic in turn has to be transmitted over the wireless medium. The BSs perform coordinated multi-cell beamforming in order to efficiently transmit their data over the wireless medium. The number of bits departing from the queues is a function of the achieved SINR. The two
1.2. Outline and Contributions
Cell1 Cell2
BS1 BS2
UT UT UT UT
Q Q Q Q
Network
1,1 2,K
1,1
1,K 2,1
1,K 2,1 2,K
Figure 1.1: System setup consisting of a multi-cell scenario. Every BS is equipped with queues to buffer the packets of the UTs they serve.
1.2. Outline and Contributions
important design considerations in Chapter 3 are the following:
The flow controller must take the flow control decisions in order to ensure the stability of the queues while being oblivious to the CSI of the wireless link between the BSs and the UTs.
The BSs must perform the joint multi-cell beamforming with limited in- formation exchange between them.
The first design consideration arises from the fact that the flow controller is typically connected to a large number of small cell BSs and hence cannot keep track of the channel conditions of all the BSs. The second design consideration is important in order to enable SCNs to be operational with limited backhaul infrastructure.
Chapter 3 is divided into two parts. In the first part, we develop a reduced overhead multi-cell beamforming design algorithm in which the BSs need to exchange only the channel statistics among themselves rather than the instan- taneous CSI. We theoretically prove that the performance of such an algorithm exactly matches that of a centralized algorithm (with instantaneous CSI ex- change), when the number of antennas at the BSs and number of UTs grow large. To this end, we use tools from random matrix theory (RMT). In the second part, we address the problem of traffic flow control coupled with the decentralized beamforming design developed in the previous part. Specifically, we develop a H∞ control based flow controller which regulates the traffic ar- rival into the queues present at the BS while being oblivious to the wireless CSI between the BS and the UTs.
In Chapter 4, we address the following question. In a MIMO multi-cell sys- tem, given certain time average quality of service (QoS) constraints for the users, what is the minimum energy required to satisfy them. We first characterize the feasible QoS region, which is the set of all time average QoS constraints that can be successfully met by an appropriate policy. We then formulate the problem as a stochastic optimization problem and use tools from Lyapunov optimization to develop a dynamic beamforming solution. The above approach leads to a series of static optimization problems which must be solved during each time slot.
We reformulate the static optimization problem as a semi-definite programming (SDP) problem. The solution to the optimization problem provides the optimal beamforming vector design at each instant. Our formulation naturally leads to the decentralized design in which the BSs can formulate the optimal beam- forming vectors using only the locally available CSI. The BSs would only have to exchange the limited information among them. We incorporate the case of
1.2. Outline and Contributions
delayed information exchange and examine its performance with respect to the optimal solution.
In Chapter 5, we consider a decentralized scheduling problem in scenario consisting of two BSs serving their respective UTs (one UT per BS). The design objective in this case is to stabilize the queues for a given traffic arrival rate (which lies inside the stability region). Specifically, we develop an algorithm called theFast CSMA(carrier sense multiple access) based distributed schedul- ing algorithm under an SINR based interference model. In our algorithm, the BSs only have to exchange one bit information among them. First, we note the direct application of FCSMA algorithm to an SINR based interference model achieves low performance. We then combine the FCSMA algorithm with a dy- namic traffic splitting rule and charectarize the performance of our algorithm.
The novelty of our algorithm lies in the decentralized nature of the operation and its applicability to fading channel scenario.
The thesis is concluded in Chapter 6 which summarizes some of the main results and provides an outlook to future work.
1.3. Publications
1.3 Publications
The following publications have been produced in the course of this thesis:
Journals
[J1] S. Lakshminaryana, M. Assaad and M. Debbah, ”Energy Efficient Cross- Layer Design in MIMO Multi-cell Systems,”to be submitted
[J2] S. Lakshminaryana, J. Hoydis, M. Debbah and M. Assaad, ”Asymp- totic Analysis of Distributed Multi-cell Beamforming,” submitted toIEEE Transactions on Signal Processing,2012
[J3] S. Lakshminarayana, M. Assaad and M. Debbah, ”H∞ Control Based Scheduler for the Deployment of Small Cell Networks,” to appear inEl- sevier Performance Evaluation Journal, Special Issue of selected papers from WiOpt 2011 (accepted for publication)
Conferences
[C1] S. Lakshminaryana, M. Assaad and M. Debbah, ”Energy Efficient Cross- Layer Design in MIMO Multi-cell Systems,”to be submittedInterna- tional Conference on Acoustics, Speech, and Signal Processing (ICASSP’13), 2013
[C2] S. Lakshminarayana, B. Li, M. Assaad, A. Eryilmaz and M. Debbah, ”A Fast-CSMA Based Distributed Scheduling Algorithm under SINR Model”
IEEE International Symposium on Information Theory (ISIT’12), Cam- brigde, MA, USA, 2012
[C3] S. Lakshminarayana, M. Debbah and M. Assaad, ”Asymptotic Analy- sis of Downlink Multi-cell Systems with Partial CSIT”, IEEE Interna- tional Symposium on Information Theory (ISIT’11), St-Petersburg, Rus- sia, 2011
[C4] S. Lakshminarayana, M. Assaad and M. Debbah, ”H∞ Control Based Scheduler for the Deployment of Small Cell Networks,”9th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wire- less Networks (WiOpt’11), Princeton, USA, 2011
[C5] S. Lakshminaryana, J. Hoydis, M. Debbah and M. Assaad, ”Asymp- totic Analysis of Distributed Multi-cell Beamforming,” IEEE Interna- tional Symposium on Personal, Indoor and Mobile Radio Communica- tions, (PIMRC’10), Istanbul, Turkey, 2010
Chapter 2
Theory
In this chapter, we provide some necessary background which will be of use in developing the algorithms in this thesis. Specifically, we provide results from the fields of probability and RMT, stochastic control theory and stochastic network optimization.
2.1 Useful Results from Probability and Matrix Analysis
We first present some basic results related to matrices.
Lemma 1. ([28]) For two matricesXandY,if0≤X≤Y1thenρ(X)≤ρ(Y).
Theorem 1. (Rayleigh-Ritz Theorem [29]) Let A ∈ CN×N be a Hermitian matrixλmax(A)be the maximum eigenvalue, then,
λmax(A) = max
x∈CN\{0}
xHAx xHx
= max
x∈CN,||x||2=1 xHAx
Lemma 2. ([30], (2.2)) LetAbe a Hermitian invertible matrix of size N×N, then for any vectorx∈CN and scalar τ∈Cfor which A+τxxH is invertible,
xH(A+τxxH)−1= xHA−1 1 +τxHA−1x.
Next, we present some standard definitions and results from probability theory.
1Recall that for matrices,X≤Ystands for element wise inequality.
2.1. Useful Results from Probability and Matrix Analysis
Lemma 3. (Markov’s inequality, [31], (5.31)) LetX be a nonnegative random variable and >0.Then,
P(X≥)≤ 1 E[X].
In particular, for an arbitrary random variable X and some integerk, P(|X| ≥)≤ 1
kE[|X|k].
Lemma 4. (Holder’s inequality, [31],(5.35)) For X, Y two arbitrary random variables andp, q >1, satisfying 1p+1q = 1,
E[|XY|]≤(E[|X|p])1/p(E[|Y|q])1/q.
In particular, for two sets {x1, . . . , xN}and{y1, . . . , yN} of complex numbers, X
i
|xiyi| ≤ X
i
|xi|p
!1/p
X
i
|xi|q
!1/q
.
We now deal with infinite sequencesX1(ω), X2(ω), . . . of random variables defined on a probability space (Ω,F, P).
Definition 1. (Almost sure convergence). The sequence of random variables (Xn)n≥1 converges almost surely toX, if
P
lim sup
n→∞
|Xn−X|= 0
= 1.
This is denoted by Xn
−−→a.s. X.
In order to prove the almost sure convergence of a sequence of random variables (Xn)n≥1 to some constant X, one often relies on the combination of Markov’s inequality and the Borel-Cantelli lemma which we state in the fol- lowing.
Lemma 5. Borel Cantelli Lemma ([31], Theorem 4.3): Let (An)n≥1 be a se- quence of sets,An∈ F for some probability space(Ω,F, P).IfP
nP(An)≤ ∞, thenP(lim supnAn) = 0.
Lemma 6. ([32], Lemma 2.6) Let (AN)N≥1,AN ∈ CN×N be a sequence of matrices and (xN)N≥1, xN ∼ CN(0,N1IN) ∈ CN, be a sequence of random vectors independent of(AN)N≥1.Considerm≥2.Then there exists a constant Cm independent ofN andAsuch that
E
xHNANxN − 1
Ntr(AN)
m
≤ Cm
Nm/2||AN||m.
2.2. Introduction to Random Matrix Theory
This implies by the Markov inequality and the Borel Cantelli lemma for||AN||<
∞, that
xHNANxN − 1
Ntr(AN)−−−−→a.s.
N→∞ 0.
Lemma 7. ([30], Lemma 2.6) Letz ∈C+ with v = Im(z) and A andB are N×N matrices with Bbeing Hermitian, τ∈R, andq∈CN, then
|tr (B−zI)−1−(B+τqqH−zI)−1)A
| ≤ ||A||
v .
Lemma 8. ([33], Lemma1) Let(an)n≥1,(¯an)n≥1,(bn)n≥1and(¯bn)n≥1denote four infinite sequences of complex random variables. If an a¯n and bn ¯bn. Then,
If|an|,|¯bn|and/or |¯an|,|bn|are bounded almost surely, then, anbn ¯an¯bn.
If|an|,|¯bn|−1 and/or |¯an|,|bn|−1 are bounded almost surely, then, an
bn
a¯n
¯bn.
2.2 Introduction to Random Matrix Theory
We will now provide a brief introduction to RMT.
Definition 2. For a Hermitian N ×N matrix X, we denote the empirical spectral distribution (e.s.d.) byFX, which is defined forx∈Ras
FX(x) = 1 N
N
X
j=1
1λj≤x(x)
where {λ1, . . . , λN} are the eigenvalues ofX and1λj≤x is then indicator func- tion whose value is equal to 1 if the eigenvalueλj is less thanx,0 otherwise.
The relevant aspect of largeN×N Hermitian matrices is that their random e.s.d. FX converges, asN → ∞towards a nonrandom distributionF,
FX−F−−−−→a.s.
N→∞ 0.
This functionF, if it exists, will be called the limit spectral distribution (l.s.d.) ofX.
In general, it is tedious to work directly with the distribution functions of the eigenvalues of random matrices. Infact, for many of the matrix models, it is difficult to prove the convergence of the e.s.d. to a limiting distribution.
In order to overcome this, we now introduce the concept of Stieltjes transform which is a powerful tool in the analysis of random matrices.
2.2. Introduction to Random Matrix Theory
Definition 3. We denote the Stieltjes transform of the e.s.dFX of the matrix X bymX(z) which is defined as
mFX(z) = Z
R 1
λ−zdFX(λ).
The Stieltjes transform based approach greatly simplifies the study of large dimensional random matrices. The intuition is the following. For a Hermitian matrixX,
mFX(z) = Z
R 1
λ−zdFX(λ)
= 1
Ntr(Λ−zIN)−1
= 1
Ntr(X−zIN)−1
whereΛis the diagonal matrix consisting of eigen values of the matrixX.Work- ing with Stieltjes transform simplifies to working with the matrix (X−zIN)−1. From matrix inversion lemmas and several fundamental matrix identities, it is then rather simple to derive limits of traces N1tr(X−zIN)−1.For many matrix models, it is easier to show that the Stieltjes transformmFX of the e.s.d. of the matrixX converges almost surely to a functionm, which is itself the Stieltjes transform of a distribution functionF, i.e.,
mFX−m−−−−→a.s.
N→∞ 0.
To specify the exact link between the distribution functions and their Stieltjes transform, we state the following theorem.
Theorem 2. Let{FN}be a set of bounded real functions such thatlimx→−∞FN(x) = 0.Then for allz∈C+,
lim
N→∞mFN(z) =mF(z)
if and only if there existsF such thatlimx→−∞F(x) = 0and|FN(x)−F(x)| →0 for allx∈R.
Theorem 2 implies that the convergence of the Stieltjes transformmFN(z) to mF(z) ensures the convergence of the distribution functions and vice versa.
This justifies the use of Stieltjes transform in the analysi
