166 Pages
English

Suboptimal resource allocation for multi-user MIMO-OFDMA systems [Elektronische Ressource] / von Tarcisio Ferreira Maciel

Gain access to the library to view online
Learn more

Description

Suboptimal Resource Allocationfor Multi-User MIMO-OFDMA SystemsVom Fachbereich 18Elektrotechnik und Informationstechnikder Technischen Universität Darmstadtzur Erlangung der Würde einesDoktor-Ingenieurs (Dr.-Ing.)genehmigte DissertationvonM.Sc. Tarcisio Ferreira Macielgeboren am 15.05.1977 in Fortaleza, BrasilienReferent: Prof. Dr.-Ing. Anja KleinKorreferent: Prof. Dr.-Ing. Martin HaardtTag der Einreichung: 14. April 2008Tag der mündlichen Prüfung: 22. September 2008D 17Darmstädter DissertationDarmstadt 2008iiiAcknowledgmentsThisthesiswaspreparedintheperiodoftimebetweenApril2005andSeptember2008,during which I have been with the Communications Engineering Lab at the Instituteof Telecommunications of the Technische Universität Darmstadt.I would like to thank Prof. Dr.-Ing. Anja Klein for her support, incentive, guidance,and valuable suggestions and comments during the supervision of my studies, whichhave decisively contributed to the elaboration of this work.I also thank Prof. Dr.-Ing. Martin Haardt from the Technishe Universität Ilmenau fortaking the time to be on my dissertation committee and evaluate my work.Moreover, I thank Prof. Dr.-Ing. Dr. h.c. Willmut Zschunke from the TechnischeUniversität Darmstadt for his support and Prof. Dr.-Ing. habil. Dr.-Ing. E.h. PaulWalter Baier from Technische Universität Kaiserslautern for reviewing parts of thisthesis.

Subjects

Informations

Published by
Published 01 January 2008
Reads 39
Language English
Document size 1 MB

Suboptimal Resource Allocation
for Multi-User MIMO-OFDMA Systems
Vom Fachbereich 18
Elektrotechnik und Informationstechnik
der Technischen Universität Darmstadt
zur Erlangung der Würde eines
Doktor-Ingenieurs (Dr.-Ing.)
genehmigte Dissertation
von
M.Sc. Tarcisio Ferreira Maciel
geboren am 15.05.1977 in Fortaleza, Brasilien
Referent: Prof. Dr.-Ing. Anja Klein
Korreferent: Prof. Dr.-Ing. Martin Haardt
Tag der Einreichung: 14. April 2008
Tag der mündlichen Prüfung: 22. September 2008
D 17
Darmstädter Dissertation
Darmstadt 2008iii
Acknowledgments
ThisthesiswaspreparedintheperiodoftimebetweenApril2005andSeptember2008,
during which I have been with the Communications Engineering Lab at the Institute
of Telecommunications of the Technische Universität Darmstadt.
I would like to thank Prof. Dr.-Ing. Anja Klein for her support, incentive, guidance,
and valuable suggestions and comments during the supervision of my studies, which
have decisively contributed to the elaboration of this work.
I also thank Prof. Dr.-Ing. Martin Haardt from the Technishe Universität Ilmenau for
taking the time to be on my dissertation committee and evaluate my work.
Moreover, I thank Prof. Dr.-Ing. Dr. h.c. Willmut Zschunke from the Technische
Universität Darmstadt for his support and Prof. Dr.-Ing. habil. Dr.-Ing. E.h. Paul
Walter Baier from Technische Universität Kaiserslautern for reviewing parts of this
thesis. My acknowledgments also to the colleagues and to the administrative staff at
the Communications Engineering Lab.
I would like to acknowledge the scholarship suport of DAAD and CAPES-Brazil.
Finally, I would like to thank my family for their love and support. I especially thank
my wife Patrícia, who stood by me at all times.
Darmstadt, September 2008.
Tarcisio F. Macielv
Kurzfassung
Von zukünftigen drahtlosen Kommunikationssystemen wird erwartet, dass sie
verschiedenste Datendienste zuverlässig zur Verfügung stellen, wobei diese Dienste
Raten im Bereich von wenigen kbit/s bis zu mehreren Mbit/s fordern. Wegen
der hohen Kosten für Funkfrequenzen müssen diese Systeme außerdem besonders
effizient bezüglich der Spektrumsnutzung sein. Die Anwendung von Orthogonal
Frequency Division Multiple Access (OFDMA) und Multiple Input Multiple Output
(MIMO)basiertenVerfahrenwirdalsbesondersvielversprechendangesehen,umdiesen
Anforderungen zu genügen.
Auf der einen Seite sind MIMO-OFDMA Systeme sehr flexibel und besitzen eine
hohe spektrale Effizienz. Auf der anderen Seite ist die Zuweisung der Funkressourcen
aufgrund der erheblichen Anzahl von Sub-Trägern und der Berücksichtigung
der räumlichen Komponente besonders komplex. Die optimale Zuweisung der
Funkressourcen, die die Summenrate des Systems maximiert, ist meist zu komplex
für praktische Anwendungen. Daher werden suboptimale und effiziente Verfahren zur
Funkressourcenzuweisung mit geringer Komplexität benötigt, die den Mobilstationen
die verfügbaren Frequenz-, Zeit- und Raumressourcen des Systems zuteilen.
Diese Arbeit befasst sich mit suboptimalen Verfahren zur Funkressourcenzuweisung
mit dem Ziel, die Summenrate des Systems zu maximieren. Um ein effizientes
Verfahren zur Funkressourcenzuweisung mit akzeptabler Komplexität zu entwerfen,
wird das ursprüngliche Problem der Summenratenmaximierung des Systems neu
formuliert, wobei es in vier Unterprobleme zerlegt wird. Diese sind das Space
Division Multiple Access (SDMA)-Gruppierungsproblem, das Vorkodierungsproblem,
das Leistungszuweisungsproblem und das Ressourcenvergabeproblem. Für jedes dieser
Unterprobleme werden verschiedene existierende und neu vorgeschlagene Algorithmen
angewendet, die alle die Maximierung der Summenrate des Systems zum Ziel haben.
Durch die Kombination dieser Algorithmen entstehen suboptimale Verfahren zur
Funkressourcenzuweisung, die jedoch äußerst effizient arbeiten.
Für das SDMA-Gruppierungsproblem werden vier neue SDMA-Algorithmen
vorgestellt: ein Algorithmus basiert auf konvexer Optimierung und drei
Greedy-Algorithmen basieren auf einfachen heuristischen Ansätzen. Die
vorgeschlagenen Algorithmen erzeugen die SDMA-Gruppen anhand von räumlichen
Korrelationseigenschaften und Kanalgewinnen der Mobilstation und benötigen keine
Vorkodierung oder Leistungszuweisung. Es wird gezeigt, dass die vorgestellten
Algorithmen bezüglich der mittleren Summenrate genauso gute Ergebnisse liefern
wie einige existierende SDMA-Algorithmen, wobei sie beachtlich niedrigeren
Rechenaufwand als die existieren Verfahren benötigen.
Zur Lösung des Vorkodierungsproblems werden zwei existierende Algorithmen
angewendet. Für das Leistungszuweisungsproblem wird ein neuer iterativer Soft
Dropping Algorithm (SDA) vorgeschlagen, der nachträglich mit Generalized Eigen-
Precoding (GEP) kombiniert wird und zu einem neuen Algorithmus führt, dervi Kurzfassung
Vorkodierung und Leistungszuweisung vereint. Des Weiteren wird die Konvergenz
dieses neuen Algorithmus gezeigt. Eine besondere Eigenschaft ist, dass der
SDA und damit auch der Algorithmus, der Vorkodierung und Leistungszuweisung
vereint, entweder zur Maximierung der Summenrate oder zur Sicherstellung
von Dienstgütekriterien (QoS-Kriterien) an der Mobilstation mit Hilfe einfacher
Parametereinstellungen genutzt werden können. Des Weiteren wird bei den
Algorithmen zur Vorkodierung und Leistungszuweisung ein neuer Sequential Removal
Algorithm (SRA) vorgeschlagen, der es ermöglicht, Mobilstationen aus SDMA-
Gruppen zu entfernen, wenn dies die Summenrate erhöht.
Um das Ressourcenvergabeproblem zu lösen, werden Algorithmen vorgestellt und
verglichen, die entweder getrennte oder gemeinsame SDMA-Gruppierung und
Ressourcenvergabe verwenden. Es wird gezeigt, dass die getrennte Vergabe
der Ressourcen zu den SDMA-Gruppen genauso gute Ergebnisse bezüglich der
Maximierung der Summenrate des Systems liefert wie die gemeinsame Verarbeitung
der SDMA-Gruppierung und der Ressourcenvergabe, wobei der getrennte Ansatz
deutlich einfacher ist. Des Weiteren werden durch die Algorithmen zur
Ressourcenvergabe verschiedene Kriterien zur Priorisierung von Mobilstationen oder
SDMA-Gruppen berücksichtigt, und es wird gezeigt, dass durch geschickte Anpassung
der Prioritätskriterien die Fairness zwischen den Mobilstationen bezüglich ihres
Durchsatzes maßgeblich erhöht werden kann, ohne dabei die Summenrate des Systems
nennenswert zu reduzieren.
Es zeigt sich, dass die neuen suboptimalen Verfahren zur Funkressourcenzuweisung,
die durch die Kombination der vorgeschlagenen Algorithmen entstehen, einen
erheblichen Teil der maximal erreichbaren Summenrate des Systems erzielen, wobei
ihr Rechenaufwand beachtlich niedriger ist als der eines optimalen Verfahrens. Die
vorgestellten Verfahren zur Funkressourcenzuweisung ereichen über 90% der mittleren
Summenrate, die mit einem Exhaustive Search Verfahren für die SDMA-Gruppierung,
das die Summenrate maximiert, erzielt wird.vii
Abstract
Future wireless communication systems are expected to reliably provide data services
with rate requirements ranging from a few kbit/s up to some Mbits/s and, due to the
high costs of frequency spectrum, these systems also need to be extremely efficient in
terms of the spectrum usage. In particular, the application of transmission schemes
based on Orthogonal Frequency Division Multiple Access (OFDMA) and on Multiple
Input Multiple Output (MIMO) is considered as a promising solution to meet these
requirements.
On the one hand, MIMO-OFDMA systems are flexible and spectrally efficient. On the
other hand, the considerably large number of subcarriers and the inclusion of the space
dimension make the Resource Allocation (RA) in such systems very complex. In fact,
the optimum RA that maximizes the sum rate of the system is often too complex for
practicalapplication and, consequently, suboptimalratherefficientandlow-complexity
RA strategies are required in order to allocate the frequency, time, and space resources
of the system to the Mobile Stations (MSs).
This thesis deals with suboptimal RA strategies in the downlink of MIMO-OFDMA
systems aiming at the maximization of the sum rate. In order to solve the problem of
maximizingthesumratewithaffordablecomplexity,anewformulationfortheproblem
is proposed which divides it into four subproblems, namely the Space Division Mul-
tiple Access (SDMA) grouping problem, the precoding problem, the power allocation
problem, and the resource assignment problem. For each subproblem, several existing
or newly proposed algorithms are applied, which are also oriented towards the maxi-
mization of the sum rate of the system. Through the combination of these algorithms,
new suboptimal rather efficient RA strategies are obtained.
For the SDMA grouping problem, four new SDMA algorithms are proposed: one al-
gorithm based on convex optimization and three greedy algorithms based on simple
heuristics. The proposed algorithms build the SDMA groups based only on the spatial
correlation and channel gain of the MSs and depend neither on precoding nor on power
allocation. The proposed algorithms are shown to perform as good as some existing
SDMA algorithms in terms of the achieved average sum rate and to have considerably
lower computational complexity than the existing ones.
For the precoding problem, two existing algorithms are adopted. For the power allo-
cation problem, a new iterative Soft Dropping Algorithm (SDA) is proposed, which is
subsequently combined with Generalized Eigen-Precoding (GEP) into a new iterative
joint precoding and power allocation algorithm. Moreover, the proof for the conver-
gence of the joint precoding and power allocation algorithm is provided. In particular,
theSDAand,consequently,thejointprecodingandpowerallocationalgorithmcanpur-
sueeitherthemaximizationofthesumrateortheprovisionofQualityofService(QoS)
to the MS by means of a simple parameter setting. Also as part of the precoding and
power allocation algorithm, a new Sequential Removal Algorithm (SRA) is proposed,
which might remove MSs from SDMA groups as to enhance the sum rate.viii Abstract
For the resource assignment problem, algorithms performing either separated or joint
SDMA grouping and resource assignment are proposed and compared. For the max-
imization of the sum rate of the system, it is shown that a sequential assignment
of resources to SDMA groups performs as good as assignment algorithms performing
joint SDMA grouping and resource assignment while being considerably more simple.
Moreover, different criteria to prioritize MSs or SDMA groups are considered by the
assignment algorithms, and it is shown that by adopting a suitable priority criterion
the throughput fairness among the MSs can be considerably improved at the expense
of only small reductions of the average sum rate of the system.
The new suboptimal RA strategies that result from the combination of the proposed
algorithms are shown to obtain a considerable fraction of the maximum achievable
sum rate of the system with computational costs considerably lower than that of an
optimum RA. Indeed, the proposed RA strategies achieve over 90% of the average sum
rate obtained by an RA strategy performing an Exhaustive Search (ES) for the SDMA
group that maximizes the sum rate.ix
Contents
Acknowledgments iii
Kurzfassung v
Abstract vii
1 Introduction 1
1.1 Resource Allocation in MIMO-OFDMA Systems . . . . . . . . . . . . . 1
1.1.1 Key Technologies . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.2 Scenario Description . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.3 Resource Allocation Problem . . . . . . . . . . . . . . . . . . . 2
1.2 Framework for Suboptimal Resource Allocation Strategies . . . . . . . 5
1.3 State-of-the-Art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4 Open Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.5 Contents and Contributions of the Thesis . . . . . . . . . . . . . . . . . 19
2 Multi-User MIMO-OFDMA System Modeling and Resource
Allocation Problem Formulation 23
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2.1 Overall Scenario and Assumptions . . . . . . . . . . . . . . . . . 23
2.2.2 Frame Structure and Resource Definition . . . . . . . . . . . . . 25
2.2.3 Channel Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.2.4 Channel State Information Models . . . . . . . . . . . . . . . . 30
2.3 Optimization Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3 Resource Allocation in MIMO-OFDMA Systems: Single Resource 41
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.2 SDMA Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.2.1 Grouping Metric . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.2.2 Grouping Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 50
3.2.3 SDMA Algorithm Definition . . . . . . . . . . . . . . . . . . . . 56
3.3 Precoding and Power Allocation Algorithms . . . . . . . . . . . . . . . 60
3.3.1 Precoding Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 60
3.3.2 Power Allocation Algorithm . . . . . . . . . . . . . . . . . . . . 64
3.3.3 Sequential Removal Algorithm . . . . . . . . . . . . . . . . . . . 67
3.3.4 Precoding and Power Allocation Algorithm Definition . . . . . . 68
3.4 Resource Allocation Strategy Definition . . . . . . . . . . . . . . . . . . 73
3.5 Performance and Complexity of the Resource Allocation Strategies. . . 74
3.5.1 System and Resource Allocation Strategy Parameters . . . . . . 74x Contents
3.5.2 Performance with Different Amounts of Channel State
Information at the Transmitter . . . . . . . . . . . . . . . . . . 77
3.5.3 Performance with Block Channel State Information at the
Transmitter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
3.5.4 PerformancewithSecond-orderChannelStateInformationatthe
Transmitter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
3.5.5 Performance with Erroneous Block Channel State Information
at the Transmitter . . . . . . . . . . . . . . . . . . . . . . . . . 85
3.5.6 Impact of the Sequential Removal Algorithm on the Performance 87
3.5.7 Impact of the Parameter β on the Performance . . . . . . . . . 90
3.5.8 Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . . 93
3.5.9 Fairness Analysis Considering Different MS Priority Criteria . . 98
3.5.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
4 Resource Allocation in MIMO-OFDMA Systems: Multiple
Resources 107
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
4.2 Grouping & Assignment Algorithm . . . . . . . . . . . . . . . . . . . . 109
4.2.1 Group Priority . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
4.2.2 SDMA and Assignment Algorithms . . . . . . . . . . . . . . . . 111
4.2.2.1 Separated Grouping and Assignment . . . . . . . . . . 111
4.2.2.2 Joint Grouping and Assignment . . . . . . . . . . . . . 117
4.3 Precoding and Power Allocation Algorithms . . . . . . . . . . . . . . . 118
4.3.1 Precoding Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 118
4.3.2 Power Allocation Algorithm . . . . . . . . . . . . . . . . . . . . 118
4.3.3 Precoding and Power Allocation Algorithm Definition . . . . . . 119
4.4 Resource Allocation Strategy Definition . . . . . . . . . . . . . . . . . . 120
4.5 Performance of the Resource Allocation Strategies . . . . . . . . . . . . 121
5 Conclusions 131
Appendix 133
A.1 Complexity of some mathematical operations and functions . . . . . . . 133
List of Acronyms 135
List of Symbols 143
Bibliography 145
Lebenslauf 155