TU Darmstadt / ULB / TUprints

Joint Downlink Beamforming and Discrete Resource Allocation Using Mixed-Integer Programming

Cheng, Yong (2014)
Joint Downlink Beamforming and Discrete Resource Allocation Using Mixed-Integer Programming.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

[img]
Preview
Text
Joint Downlink Beamforming and Discrete Resource Allocation Using Mixed-Integer Programming.pdf - Accepted Version
Copyright Information: CC BY-NC-ND 2.5 Generic - Creative Commons, Attribution, NonCommercial, NoDerivs .

Download (1MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Joint Downlink Beamforming and Discrete Resource Allocation Using Mixed-Integer Programming
Language: English
Referees: Pesavento, Prof. Dr. Marius ; Ulbrich, Prof. Dr. Stefan
Date: 3 January 2014
Place of Publication: Darmstadt
Date of oral examination: 13 December 2013
Abstract:

Multi-antenna processing is widely adopted as one of the key enabling technologies for current and future cellular networks. Particularly, multiuser downlink beamforming (also known as space-division multiple access), in which multiple users are simultaneously served with spatial transmit beams in the same time and frequency resource, achieves high spectral efficiency with reduced energy consumption. To harvest the potential of multiuser downlink beamforming in practical systems, optimal beamformer design shall be carried out jointly with network resource allocation. Due to the specifications of cellular standards and/or implementation constraints, resource allocation in practice naturally necessitates discrete decision makings, e.g., base station (BS) association, user scheduling and admission control, adaptive modulation and coding, and codebook-based beamforming (precoding).

This dissertation focuses on the joint optimization of multiuser downlink beamforming and discrete resource allocation in modern cellular networks. The problems studied in this thesis involve both continuous and discrete decision variables and are thus formulated as mixed-integer programs (MIPs). A systematic MIP framework is developed to address the problems. The MIP framework consists of four components: (i) MIP formulations that support the commercial solver based approach for computing the optimal solutions, (ii) analytic comparisons of the MIP formulations, (iii) customizing techniques for speeding up the MIP solvers, and (iv) low-complexity heuristic algorithms for practical applications.

We consider first joint network topology optimization and multi-cell downlink beamforming (JNOB) for coordinated multi-point transmission. The objective is to minimize the overall power consumption of all BSs while guaranteeing the quality-of-service (QoS) requirements of the mobile stations (MSs). A standard mixed-integer second-order cone program (MISOCP) formulation and an extended MISOCP formulation are developed, both of which support the branch-and-cut (BnC) method. Analysis shows that the extended formulation admits tighter continuous relaxations (and hence less computational complexity) than that of the standard formulation. Effective strategies are proposed to customize the BnC method in the MIP solver CPLEX when applying it to the JNOB problem. Low-complexity inflation and deflation procedures are devised for large-scale applications. The simulations show that our design results in sparse network topologies and partial BS cooperation.

We study next the joint optimization of discrete rate adaptation and downlink beamforming (DRAB), in which rate adaptation is carried out via modulation and coding scheme (MCS) assignment and admission control is embedded in the MCS assignment procedure. The objective is to achieve the maximum sum-rate with the minimum transmitted BS power. As in the JNOB problem, a standard and an extended MISOCP formulations are developed, and analytic comparisons of the two formulations are carried out. The analysis also leads to efficient customizing strategies for the BnC method in CPLEX. We also develop fast inflation and deflation procedures for applications in large-scale networks. Our numerical results show that the heuristic algorithms yield sum-rates that are very close to the optimal ones.

We then turn our attention to codebook-based downlink beamforming. Codebook-based beamforming is employed in the latest cellular standards, e.g., in long-term evolution advanced (LTE-A), to simplify the signaling procedure of beamformers with reduced signaling overhead. We consider first the standard codebook-based downlink beamforming (SCBF) problem, in which precoding vector assignment and power allocation are jointly optimized. The objective is to minimize the total transmitted BS power while ensuring the prescribed QoS targets of the MSs. We introduce a virtual uplink (VUL) problem, which is proved to be equivalent to the SCBF problem. A customized power iteration method is developed to solve optimally the VUL problem and hence the SCBF problem. To improve the performance of codebook-based downlink beamforming, we propose a channel predistortion mechanism that does not introduce any additional signalling overhead or require modification of the mobile receivers. The joint codebook-based downlink beamforming and channel predistortion (CBCP) problem represents a non-convex MIP. An alternating optimization algorithm and an alternating feasibility search algorithm are devised to approximately solve the CBCP problem. The simulation results confirm the efficiency of the channel predistortion scheme, e.g., achieving significant reductions of the total transmitted BS power.

We study finally the worst-case robust codebook-based downlink beamforming when only estimated channel covariance matrices are available at the BS. Similar to the DRAB problem, user admission control is embedded in the precoding vector assignment procedure. In the robust codebook-based downlink beamforming and admission control (RCBA) problem, the objective is to achieve the maximum number of admitted MSs with the minimum transmitted BS power. We develop a conservative mixed-integer linear program (MILP) approximation and an exact MISOCP formulation of the RCBA problem. We further propose a low-complexity inflation procedure. Our simulations show that the three approaches yield almost the same average number of admitted MSs, while the MILP based approach requires much more transmitted BS power than the other two to support the admitted MSs.

The MIP framework developed in this thesis can be applied to address various discrete resource allocation problems in interference limited cellular networks. Both optimal solutions, i.e., performance benchmarks, and low-complexity practical algorithms are considered in our MIP framework. Conventional approaches often did not adopt the exact discrete models and approximated the discrete variables by (quantized) continuous ones, which could lead to highly suboptimal solutions or infeasible problem instances.

Alternative Abstract:
Alternative AbstractLanguage

Mehrantennensignalverarbeitung ist als eine der Schlüsseltechnologien für moderne und zukünftige Mobilfunknetze weit verbreitet. Insbesondere das Multiuser Downlink Beamforming (auch bekannt als Space-Division Multiple Access), bei dem mehrere Teilnehmer mit räumlichen Sendestrahlenbündeln (oder Sende Beams) in derselben Zeit- und Frequenzressource gleichzeitig bedient werden, erreicht eine hohe spektrale Effizienz bei gleichzeitig reduzierter Sendeleistung. Um das Potential von Multiuser Downlink Beamforming in der Praxis nutzbar zu machen, soll der optimale Beamforming Entwurf gemeinsam mit der Netzwerkressourcenvergabe durchgeführt werden. Aufgrund der Spezifikationen in Mobilfunkstandards und/oder Einschränkungen bei der Implementierung erfordert die Ressourcenvergabe diskrete Entscheidungen wie z.B. die Basisstationszuordnung (BS Zuordnung), das Scheduling der Teilnehmer und die Zugangskontrolle, adaptive Modulation und Kodierung sowie Codebuch-basiertes Beamforming (Vorkodierung).

Diese Dissertation legt den Schwerpunkt auf die gemeinsame Optimierung von Multiuser Downlink Beamforming und diskreter Ressourcenvergabe in modernen zellularen Mobilfunknetzen. Die Probleme, die in dieser Arbeit untersucht werden, beinhalten sowohl kontinuierliche als auch diskrete Entscheidungsvariablen und werden daher als gemischt ganzzahlige Programme (engl. mixed-integer programs, MIPs) formuliert. Ein systematisches MIP Rahmenwerk wird entwickelt, um die Probleme anzugehen. Es besteht aus den folgenden vier Komponenten: (i) den MIP Formulierungen, die den Ansatz unterstützen, optimale Lösungen mittels kommerzieller Software-Lösern zu berechnen (Leistungsfähigkeits-Benchmarks), (ii) verschiedener analytische Leistungsfähigkeitsuntersuchungen, (iii) der individuellen Anpassung der Verfahren, um die MIP Löser zu beschleunigen, und (iv) heuristische Algorithmen, die insbesondere für den Einsatz in praktischen Anwendungen eine geringe Rechenkomplexität aufweisen.

Zunächst betrachten wir die simultane Optimierung, Netzwerktopologie und Multi-Cell Downlink Beamformings (JNOB) für Coordinated Multi-Point Übertragung. Ziel ist es, den gesamten Leistungsverbrauch aller BSs zu minimieren und gleichzeitig die Anforderungen an die Service-Qualität (engl. Quality-of-Service, QoS) der mobilen Teilnehmer (MSs) zu gewährleisten. Eine herkömmliche Mixed-Integer Second-Order Cone Program Formulierung (MISOCP Formulierung) sowie eine erweiterte MISOCP Formulierung werden entwickelt, die beide das Branch-and-Cut Verfahren (BnC Verfahren) unterstützen. Analysen zeigen, dass die erweiterte Formulierung engere kontinuierliche Relaxierungen zulässt (und somit einen geringere Rechenaufwand), als die der herkömmlichen Formulierung. Es werden darüber hinaus effektive Strategien entwickelt, um das BnC Verfahren in den Software-Lösern CPLEX für die Anwendung des JNOB Problems individuell anzupassen. Rechengün- stige Inflations- und Deflationsverfahren werden für groß dimensionierte Anwendungen entwickelt. Die Simulationen zeigen, dass unser Entwurf im Ergebnis dünn besetzte Netzwerktopologien und Teil BS Kooperation hervorbringt.

Wir untersuchen als Nächstes die gemeinsame optimierte diskrete Ratenanpassung und das Downlink Beamforming (DRAB), bei dem die Ratenanpassung mittels Modulations- und Kodierungsverfahrenzuweisung (engl. Modulation and Coding, MCS Zuweisung) erfolgt. Bei diesem Ansatz ist die Teilnehmerauswahl auf natürliche Weise in MCS Zuweisung eingebettet. Ziel ist es, die maximale Summenrate mit einem Minimum an abgestrahlter BS Leistung zu erreichen. Wie für das JNOB Problem, werden eine herkömmliche und eine erweiterte MISOCP Formulierung entwickelt, und anschließend analytische Vergleiche angestellt. Die Analyse führt auch zu effizienten Anpassungsstrategien für das BnC Verfahren in CPLEX. Wir entwickeln außerdem schnelle Inflations- und Deflationsverfahren für die Anwendung in groß dimensionierten Netzwerken. Unsere numerischen Ergebnisse zeigen, dass die heuristischen Algorithmen Summenraten liefern, die sehr nahe an den optimal möglichen Summenraten liegen.

Wir richten unsere Aufmerksamkeit dann auf den Codebuch-basierten Downlink Beamformer Entwurf. Codebuch-basiertes Beamforming kommt in den neuesten Mobilfunkstandards zum Einsatz, z.B. in Long Term Evolution Advanced (LTE-A), um die Signalisierung des gewählten Beamformers zu vereinfachen. Wir betrachten als Erstes das herkömmliche Codebuch-basierte Downlink Beamforming Problem (SCBF Problem), bei dem die Zuweisung der Precodingvektoren und die Sendeleistung gemeinsam optimiert werden. Ziel ist es, die Gesamtsendeleistung der BS zu minimieren, während die vorgegebenen QoS Anforderungen der MSs einzuhalten sind. In unserem Ansatz greifen wir auf ein Virtuelles Uplink Problem (VUL Problem) zurück, welches mathematisch equivalent zu dem betrachteten SCBF Problem ist. Ein individuell angepasstes Potenzverfahren wird entwickelt, um das Optimum des VUL Problems, und somit das des SCBF Problems, zu finden. Um die Leistungsfähigkeit des Codebuch-basierten Downlink Beamformings zu verbessern, schlagen wir ein Kanalvorverzerrungsverfahren vor, das ohne zusätzliche Signalisierung oder Modifizierung der mobilen Empfänger eingesetzt werden kann. Das gemeinsame Codebuch-basierte Downlink Beamforming- und Kanalvorverzerrungs Problem (CBCP Problem) stellt ein nicht-konvexes MIP dar. Ein alternativer Optimierungsalgorithmus und ein alternatives Zulässigkeitsverfahren werden entwickelt um das CBCP Problem näherungsweise zu lösen. Die Simulationsergebnisse bestätigen die Effizienz des Kanalvorverzerrungsschritts. So wird numerisch gezeigt, dass sich mit dem Verfahren eine erhebliche Reduzierung der Gesamtsendeleistung der BS erreichen lässt.

Wir untersuchen zuletzt das robuste Codebuch-basierte Worst-Case Downlink Beamforming wobei angenommen wird, dass sich die Kanalinformation an der BS lediglich auf geschätzte Kanalkovarianzmatrizen beschränkt. Ähnlich wie bei dem DRAB Problem ist die Teilnehmerauswahl in die Auswahl der Precodingvektoren eingebettet. In dem robusten Codebuch-basierten Downlink Beamforming und Zugangskontroll Problem (RCBA Problem) ist es das Ziel, die maximale Anzahl an ausgewählten MSs bei minimaler Sendeleistung der BS zu erreichen. Wir entwickeln eine konservative Mixed-Integer Linear Program Approximierung (MILP Approximierung) des RCBA Problems, sowie eine exakte MISOCP Umformulierung. Ferner entwickeln wir ein recheneffizentes Inflationsverfahren für das RCBA Problem. Unsere Simulationen zeigen, dass die drei Ansätze nahezu die gleiche durchschnittliche Anzahl an zugelassenen MSs erzielen, wobei die BS bei dem MILP-basierten Ansatz dafür jedoch wesentlich mehr Sendeleistung aufwenden muss, als bei den anderen beiden Ansätzen.

Das MIP Rahmenkonzept, das in dieser Dissertation entwickelt wird, kann auf eine Vielzahl von diskreten Ressourcenvergabeproblemen in Interferenz begrenzten Mobilfunknetzen angewendet werden. Sowohl optimale Leistungsfähigkeits-Benchmarks als auchpraxistaugliche Algorithmen mit geringer Komplexität werden in unserem MIP Rahmenwerk berücksichtigt. Herkömmliche Ansätze haben sich oftmals nicht mit den exakten diskreten Modellen auseinandergesetzt, sondern die diskreten Variablen mit kontinuierlichen angenähert, was zu hochgradig suboptimalen Lösungen oder unzulässigen Probleminstanzen führen kann.

German
Uncontrolled Keywords: Multiuser downlink beamforming, Discrete resource allocation, Mixed-integer programming
Alternative keywords:
Alternative keywordsLanguage
Downlink-Beamforming, Diskreter Ressourcenvergabe, Mixed-Integer-ProgrammierungGerman
URN: urn:nbn:de:tuda-tuprints-37411
Classification DDC: 600 Technology, medicine, applied sciences > 600 Technology
600 Technology, medicine, applied sciences > 620 Engineering and machine engineering
Divisions: 18 Department of Electrical Engineering and Information Technology
18 Department of Electrical Engineering and Information Technology > Wireless Sensor Networks
18 Department of Electrical Engineering and Information Technology > Institute of Computer Engineering > Peer-to-Peer Systems Engineering
Date Deposited: 15 Jan 2014 13:41
Last Modified: 09 Jul 2020 00:35
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/3741
PPN: 386312494
Export:
Actions (login required)
View Item View Item