TU Darmstadt / ULB / TUbiblio

Energy-Efficient Distributed Multicast Beamforming Using Iterative Second-Order Cone Programming

Bornhorst, Nils (2015)
Energy-Efficient Distributed Multicast Beamforming Using Iterative Second-Order Cone Programming.
Technische Universität Darmstadt
Dissertation, Erstveröffentlichung

Kurzbeschreibung (Abstract)

In multi-user (MU) downlink beamforming, a high spectral efficiency along with a low transmit power is achieved by separating multiple users in space rather than in time or frequency using spatially selective transmit beams. For streaming media applications, multi-group multicast (MGM) downlink beamforming is a promising approach to exploit the broadcasting property of the wireless medium to transmit the same information to a group of users. To limit inter-group interference, the individual streams intended for different multicast groups are spatially separated using MGM downlink beamforming. Spatially selective downlink beamforming requires the employment of an array of multiple antennas at the base station (BS). The hardware costs associated with the use of multiple antennas may be prohibitive in practice. A way to avoid the expensive employment of multiple antennas at the BS is to exploit user cooperation in wireless networks where multiple single-antenna users act as relays and take over the role of antenna elements in a virtual distributed antenna array.

In both downlink beamforming and distributed relay beamforming, several approaches to design the transmit beams exist. In many scenarios, minimizing the transmit power has a higher priority than maximizing throughput. This is the case, e.g., in downlink beamforming, when operators aim at reducing their operational expenditures and their carbon footprint, or in distributed beamforming when users are only willing to cooperate when the battery consumption of their devices is kept at a minimum level. Then, the transmit beams are designed as the solution of a quality-of-service-constrained (QoS-constrained) power minimization problem. The goal of this optimization approach is to minimize the total transmitted power (at the BS or at the relays) while guaranteeing a predefined QoS at the destination users. In many scenarios with a high relevance in practice such as MGM downlink beamforming and MU peer-to-peer (MUP2P) relay beamforming, the QoS-constrained power minimization problem is a nonconvex optimization problem which cannot be solved optimally in polynomial time. In state-of-the-art methods, the nonconvex problem is therefore approximated by a convex one which is easier to solve. As the number of users increases, however, these approximations become more and more inaccurate leading to severe performance degradation and problem infeasibility.

In this dissertation, we therefore propose a novel framework of iterative optimization schemes where a convex approximation of the original problem is successively improved. In each iteration of the proposed schemes, a convex approximation of the original problem is solved and then adapted to the solution obtained in this iteration. We prove that by this means, the approximate solution is improved from iteration to iteration. In this way, an approximate solution which is much closer to the optimal solution of the original problem than in state-of-the-art methods is usually obtained. Moreover, the convex approximation may be infeasible in state-of-the-art methods even if the original problem is feasible. The proposed iterative scheme is therefore extended such that it can also be used to find a feasible initial approximation of the original problem. Simulations results reveal that in relay beamforming scenarios with a moderate to a large number of destination users, the proposed scheme substantially outperforms state-of-the-art methods in terms of total transmitted relay power and problem feasibility. In MGM downlink beamforming scenarios with a large number of users, the proposed technique achieves the same performance as the state-of-the-art methods at a substantially reduced computational complexity.

Several extensions of this basic iterative convex approximation technique are proposed in this dissertation: The feasibility search is extended to an admission control scheme where a minimum number of destination users is determined for which service has to be denied in case of shortage of spectral resources. Furthermore, a non-trivial extension of our iterative method is proposed to maintain its applicability in the case where only limited information about the state of the channels in the network is available. Finally, a complexity reduction is proposed to turn the proposed algorithms into computational efficient ones which are suitable for real time application in practice.

Due to its wide-ranging applicability, we also consider filter-and-forward (FF) relay beamforming where the relays are equipped with finite impulse response (FIR) filters and single-carrier (SC) transmission over frequency selective channels is performed. In this scenario, the signal received at the destination nodes is contaminated by inter-symbol interference (ISI). Using the FIR filters at the relays, the frequency selective channels are equalized to some extent such that the ISI at the destination nodes can be mitigated. In previous works, the FF relay networks have been assumed to be perfectly synchronized. Perfect timing synchronization is, however, not possible in MU FF relay networks as there exists no single point of reference. This synchronization issue has barely been addressed in the literature. In this dissertation, we consider FF beamforming in asynchronous MUP2P and MGM relay networks and extend the FF scheme by incorporating individual adaptive decoding delays at the destinations. Using these decoding delays, the destination users can individually adapt to the different link delays in the asynchronous network and thereby mitigate residual ISI. We again consider the QoS-constrained power minimization problem where now the filter coefficients at the relays, which are continuous variables, and the individual decoding delays at the destinations, which are discrete variables, are jointly optimized. This optimization problem is a nonconvex mixed-integer programming (MIP) problem which is generally hard to solve optimally. We propose (i) a customized branch-and-cut (BnC) method yielding a lower bound on the total transmitted relay power as a benchmark and (ii) a low-complexity deflation algorithm providing an approximate solution for implementation in practice. The deflation method is based on the proposed iterative convex approximation approach mentioned above. Our simulation results show that the approximate solution obtained using the proposed deflation scheme is close to optimal and outperforms the solutions obtained by state-of-the-art schemes which do not make use of adaptive decoding delays.

Typ des Eintrags: Dissertation
Erschienen: 2015
Autor(en): Bornhorst, Nils
Art des Eintrags: Erstveröffentlichung
Titel: Energy-Efficient Distributed Multicast Beamforming Using Iterative Second-Order Cone Programming
Sprache: Englisch
Referenten: Pesavento, Prof. Marius ; Haardt, Prof. Martin ; Klein, Prof. Anja ; Schöps, Prof. Sebastian
Publikationsjahr: 2015
Datum der mündlichen Prüfung: 12 Dezember 2014
URL / URN: http://tuprints.ulb.tu-darmstadt.de/4387
Kurzbeschreibung (Abstract):

In multi-user (MU) downlink beamforming, a high spectral efficiency along with a low transmit power is achieved by separating multiple users in space rather than in time or frequency using spatially selective transmit beams. For streaming media applications, multi-group multicast (MGM) downlink beamforming is a promising approach to exploit the broadcasting property of the wireless medium to transmit the same information to a group of users. To limit inter-group interference, the individual streams intended for different multicast groups are spatially separated using MGM downlink beamforming. Spatially selective downlink beamforming requires the employment of an array of multiple antennas at the base station (BS). The hardware costs associated with the use of multiple antennas may be prohibitive in practice. A way to avoid the expensive employment of multiple antennas at the BS is to exploit user cooperation in wireless networks where multiple single-antenna users act as relays and take over the role of antenna elements in a virtual distributed antenna array.

In both downlink beamforming and distributed relay beamforming, several approaches to design the transmit beams exist. In many scenarios, minimizing the transmit power has a higher priority than maximizing throughput. This is the case, e.g., in downlink beamforming, when operators aim at reducing their operational expenditures and their carbon footprint, or in distributed beamforming when users are only willing to cooperate when the battery consumption of their devices is kept at a minimum level. Then, the transmit beams are designed as the solution of a quality-of-service-constrained (QoS-constrained) power minimization problem. The goal of this optimization approach is to minimize the total transmitted power (at the BS or at the relays) while guaranteeing a predefined QoS at the destination users. In many scenarios with a high relevance in practice such as MGM downlink beamforming and MU peer-to-peer (MUP2P) relay beamforming, the QoS-constrained power minimization problem is a nonconvex optimization problem which cannot be solved optimally in polynomial time. In state-of-the-art methods, the nonconvex problem is therefore approximated by a convex one which is easier to solve. As the number of users increases, however, these approximations become more and more inaccurate leading to severe performance degradation and problem infeasibility.

In this dissertation, we therefore propose a novel framework of iterative optimization schemes where a convex approximation of the original problem is successively improved. In each iteration of the proposed schemes, a convex approximation of the original problem is solved and then adapted to the solution obtained in this iteration. We prove that by this means, the approximate solution is improved from iteration to iteration. In this way, an approximate solution which is much closer to the optimal solution of the original problem than in state-of-the-art methods is usually obtained. Moreover, the convex approximation may be infeasible in state-of-the-art methods even if the original problem is feasible. The proposed iterative scheme is therefore extended such that it can also be used to find a feasible initial approximation of the original problem. Simulations results reveal that in relay beamforming scenarios with a moderate to a large number of destination users, the proposed scheme substantially outperforms state-of-the-art methods in terms of total transmitted relay power and problem feasibility. In MGM downlink beamforming scenarios with a large number of users, the proposed technique achieves the same performance as the state-of-the-art methods at a substantially reduced computational complexity.

Several extensions of this basic iterative convex approximation technique are proposed in this dissertation: The feasibility search is extended to an admission control scheme where a minimum number of destination users is determined for which service has to be denied in case of shortage of spectral resources. Furthermore, a non-trivial extension of our iterative method is proposed to maintain its applicability in the case where only limited information about the state of the channels in the network is available. Finally, a complexity reduction is proposed to turn the proposed algorithms into computational efficient ones which are suitable for real time application in practice.

Due to its wide-ranging applicability, we also consider filter-and-forward (FF) relay beamforming where the relays are equipped with finite impulse response (FIR) filters and single-carrier (SC) transmission over frequency selective channels is performed. In this scenario, the signal received at the destination nodes is contaminated by inter-symbol interference (ISI). Using the FIR filters at the relays, the frequency selective channels are equalized to some extent such that the ISI at the destination nodes can be mitigated. In previous works, the FF relay networks have been assumed to be perfectly synchronized. Perfect timing synchronization is, however, not possible in MU FF relay networks as there exists no single point of reference. This synchronization issue has barely been addressed in the literature. In this dissertation, we consider FF beamforming in asynchronous MUP2P and MGM relay networks and extend the FF scheme by incorporating individual adaptive decoding delays at the destinations. Using these decoding delays, the destination users can individually adapt to the different link delays in the asynchronous network and thereby mitigate residual ISI. We again consider the QoS-constrained power minimization problem where now the filter coefficients at the relays, which are continuous variables, and the individual decoding delays at the destinations, which are discrete variables, are jointly optimized. This optimization problem is a nonconvex mixed-integer programming (MIP) problem which is generally hard to solve optimally. We propose (i) a customized branch-and-cut (BnC) method yielding a lower bound on the total transmitted relay power as a benchmark and (ii) a low-complexity deflation algorithm providing an approximate solution for implementation in practice. The deflation method is based on the proposed iterative convex approximation approach mentioned above. Our simulation results show that the approximate solution obtained using the proposed deflation scheme is close to optimal and outperforms the solutions obtained by state-of-the-art schemes which do not make use of adaptive decoding delays.

Alternatives oder übersetztes Abstract:
Alternatives AbstractSprache

Mehrnutzer-Downlink-Beamforming (engl. multi-user downlink beamforming, MU downlink beamforming) erreicht eine hohe spektrale Effizienz bei gleichzeitig reduzierter Sendeleistung, indem mehrere Nutzer mit raumselektiven Sendebeams räumlich voneinander getrennt werden, anstatt sie im Zeit- oder Frequenzbereich voneinander zu trennen. Für Streaming-Medienanwendungen ist Mehrgruppen-Multicast-Downlink-Beamforming (engl. multi-group multicast downlink beamforming, MGM downlink beamforming) ein vielversprechender Ansatz, die Broadcasting-Eigenschaft des Mobilfunkkanals auszunutzen, um eine Gruppe von Nutzern mit der gleichen Information zu versorgen. Um Interferenz zwischen den Gruppen zu begrenzen, werden mittels MGM-Downlink-Beamforming die individuellen Streams, die für verschiedene Multicast-Gruppen vorgesehen sind, räumlich voneinander getrennt. Für Downlink-Beamforming ist es erforderlich, an der Basisstation (BS) ein Array von mehreren Antennen einzusetzen. Die dafür notwendige Hardware kann in der Praxis unerschwinglich sein. Eine Möglichkeit, den teuren Einsatz mehrerer Antennen an der BS zu umgehen, ist das Ausnutzen von Nutzerkooperation in drahtlosen Netzwerken. Dabei fungieren mehrere Nutzer, die jeweils nur mit einer einzigen Antenne ausgestattet sind, als Relays und übernehmen die Rolle von Antennenelementen in einem virtuellen und verteilten Antennen-Array.

Sowohl in Downlink-Beamforming als auch in verteiltem Relay-Beamforming existieren mehrere Ansätze, die Sendebeams zu entwerfen. In vielen Szenarien wird der Minimierung der Sendeleistung eine höhere Priorität eingeräumt als der Maximierung des Datendurchsatzes. Dies ist beispielsweise in Downlink-Beamforming der Fall, wenn die Mobilfunkanbieter ihre Betriebskosten und ihren CO2-Fußabdruck senken möchten. Ein anderes Beispiel ist, wenn in verteiltem Beamforming die Nutzer nur bereit sind zu kooperieren, sofern der Akkuverbrauch ihrer Geräte dabei minimal gehalten wird. In solchen Szenarien werden die Sendebeams als die Lösung eines Leistungsminimierungsproblems mit Quality-of-Service-Nebenbedingungen (QoS-Nebenbedingungen) entworfen. Ziel dieses Optimierungsansatzes ist es, die Gesamtsendeleistung (an der BS bzw. an den Relays) zu minimieren und gleichzeitig eine vordefinierte QoS an den Nutzern zu gewährleisten. In vielen Szenarien mit hoher praktischer Relevanz, wie beispielsweise MGM-Downlink-Beamforming oder MU-Peer-to-Peer-Relay-Beamforming (MUP2P-Relay-Beamforming), ist das Leistungsminimierungsproblem mit QoS-Nebenbedingungen ein nichtkonvexes Optimierungsproblem, dessen optimale Lösung nicht in polynomieller Zeit gefunden werden kann. In Verfahren, die dem Stand der Technik entsprechen, wird das nichtkonvexe Problem daher mit einem konvexen Problem approximiert, das sich einfacher lösen lässt. Mit einer wachsenden Zahl an Nutzern werden diese Approximationen jedoch sehr ungenau, was zu erheblichen Einbußen in der Leistungsfähigkeit und Zulässigkeit der Verfahren führt.

In dieser Dissertation schlagen wir daher ein neues System von iterativen Optimierungsverfahren vor, bei denen eine konvexe Approximation des ursprünglichen Problems sukzessive verbessert wird. In jeder Iteration der vorgeschlagenen Verfahren wird eine konvexe Approximation des ursprünglichen Problems gelöst und anschließend an die in dieser Iteration ermittelte Lösung angepasst. Wir beweisen, dass auf diese Weise die angenäherte Lösung von Iteration zu Iteration verbessert wird. Eine angenäherte Lösung, die deutlich näher an der optimalen Lösung des ursprünglichen Problems ist als in Verfahren, die dem Stand der Technik entsprechen, wird dadurch ermittelt. Ferner kann die konvexe Approximation in Verfahren, die dem Stand der Technik entsprechen, unzulässig werden, selbst wenn das ursprüngliche Problem zulässig ist. Das vorgeschlagene iterative Verfahren wird daher derart erweitert, dass es auch eingesetzt werden kann, um eine zulässige Initialapproximation des ursprünglichen Problems zu finden. Simulationsergebnisse zeigen, dass das vorgeschlagene Verfahren in Relay-Beamforming-Szenarien mit einer mittleren bis großen Anzahl an Senkeknoten die Verfahren, die dem Stand der Technik entsprechen, deutlich übertrifft hinsichtlich Gesamtsendeleistung und Problemzulässigkeit. In MGM-Downlink-Beamforming-Szenarien mit einer großen Anzahl an Nutzern erzielt das vorgeschlagene Verfahren bei deutlich reduziertem Rechenaufwand die gleiche Leistungsfähigkeit wie die Verfahren, die dem Stand der Technik entsprechen.

Mehrere Erweiterungen dieser grundlegenden iterativen konvexen Approximationsmethode werden in dieser Dissertation vorgeschlagen: Die Zulässigkeitssuche wird zu einem Admission-Control-Verfahren erweitert. Dabei wird eine minimale Zahl an Nutzern ermittelt, denen der Dienst verwehrt werden muss, wenn es nicht möglich ist, alle Nutzer des Netzwerkes zu bedienen. Außerdem schlagen wir eine nicht-triviale Erweiterung unseres iterativen Verfahrens vor, um es auch in dem Fall anwenden zu können, wenn nur eingeschränkte Informationen über den Zustand der Kanäle des Netzwerkes vorhanden sind. Schließlich wird eine Verringerung des Rechenaufwands vorgeschlagen, um die vorgeschlagenen Algorithmen in recheneffiziente Algorithmen zu überführen, die für die praktische Anwendung in Echtzeit geeignet sind.

Wegen seiner weitreichenden Anwendbarkeit betrachten wir zudem Filter-and-Forward-Relay-Beamforming ((FF)-Relay-Beamforming). Dabei sind die Relays mit Finite-Impulse-Response-Filtern (FIR-Filtern) ausgestattet und es erfolgt Einträgerübertragung (engl. single-carrier transmission, SC transmission) über frequenzselektive Kanäle. In diesem Szenario ist das Signal, das die Senkeknoten empfangen, mit Intersymbolinterferenz (ISI) kontaminiert. Mittels der FIR-Filter an den Relays wird der Einfluss der frequenzselektiven Kanäle bis zu einem gewissen Grad ausgeglichen, so dass die ISI an den Senkeknoten abgeschwächt werden kann. In vorherigen Arbeiten wurde angenommen, dass die FF-Relaynetzwerke perfekt synchronisiert sind. Perfekte zeitliche Synchronisierung ist jedoch in MU-FF-Relaynetzwerken nicht möglich, da kein gemeinsamer Bezugspunkt existiert. Dieser Synchronisierungsaspekt wurde in der Literatur bislang kaum berücksichtigt. In dieser Dissertation betrachten wir FF-Beamforming in asynchronen MUP2P- und MGM-Relaynetzwerken und erweitern das FF-Verfahren, indem wir individuelle adaptive Dekodierverzögerungen an den Senkeknoten einsetzen. Diese Dekodierverzögerungen können an den Senkeknoten individuell an die unterschiedlichen Verbindungsverzögerungen in dem asynchronen Netzwerk angepasst werden. Dadurch wird verbleibende ISI abgeschwächt. Wir betrachten wieder das Leistungsminimierungsproblem mit den QoS-Nebenbedingungen. Diesmal werden jedoch die Filterkoeffizienten an den Relayknoten, die kontinuierliche Variablen sind, und die individuellen Dekodierverzögerungen an den Senkeknoten, die diskrete Variablen sind, gemeinsam optimiert. Dieses Optimierungsproblem ist ein nichtkonvexes gemischt-ganzzahliges Programm (engl. mixed-integer program, MIP), dessen optimale Lösung sich im Allgemeinen nur schwer finden lässt. Wir schlagen zwei Lösungsansätze vor: (i) ein individuell angepasstes Branch-and-Cut-Verfahren (BnC-Verfahren), welches eine untere Grenze der Gesamtsendeleistung der Relays als Vergleichsgröße liefert, und (ii) einen Deflationsalgorithmus mit geringer Komplexität, der eine näherungsweise Lösung für die Implementierung in der Praxis bietet. Das Deflationsverfahren basiert auf dem vorgeschlagenen iterativen konvexen Approximationsansatz, der oben erwähnt wurde. Unsere Simulationsergebnisse zeigen, dass die mit dem vorgeschlagenen Deflationsverfahren erhaltene näherungsweise Lösung nah an der optimalen Lösung ist. Außerdem übertrifft das Ergebnis des Deflationsverfahrens die Lösungen von Verfahren, die dem Stand der Technik entsprechen und sich adaptive Dekodierverzögerungen nicht zunutze machen.

Deutsch
Freie Schlagworte: Beamforming, Relay Networks, Multicasting, Convex Optimization, Second-Order Cone Programming, Mixed-Integer Programming, Asynchronous Relay Networks, Adaptive Decoding Delays
URN: urn:nbn:de:tuda-tuprints-43870
Sachgruppe der Dewey Dezimalklassifikatin (DDC): 600 Technik, Medizin, angewandte Wissenschaften > 620 Ingenieurwissenschaften und Maschinenbau
Fachbereich(e)/-gebiet(e): 18 Fachbereich Elektrotechnik und Informationstechnik
18 Fachbereich Elektrotechnik und Informationstechnik > Institut für Nachrichtentechnik > Nachrichtentechnische Systeme
18 Fachbereich Elektrotechnik und Informationstechnik > Institut für Nachrichtentechnik
Hinterlegungsdatum: 01 Mär 2015 20:55
Letzte Änderung: 01 Mär 2015 20:55
PPN:
Referenten: Pesavento, Prof. Marius ; Haardt, Prof. Martin ; Klein, Prof. Anja ; Schöps, Prof. Sebastian
Datum der mündlichen Prüfung / Verteidigung / mdl. Prüfung: 12 Dezember 2014
Export:
Suche nach Titel in: TUfind oder in Google
Frage zum Eintrag Frage zum Eintrag

Optionen (nur für Redakteure)
Redaktionelle Details anzeigen Redaktionelle Details anzeigen