有傳輸速率中斷限制之多細胞協調式波束成型

Multicell Coordinated Beamforming with Rate Outage Constraint

李威錆(Li, Wei Chiang)

指導教授 ： 祁忠勇

國立清華大學/電機資訊學院/通訊工程研究所/博士(2015年)

摘要

在本論文中，我們在傳輸端只擁有通道分布資訊(channel distribution information, CDI)的假設下研究多輸入單輸出(multiple-input single-output, MISO)干擾通道(interference channel, IFC)之協調式波束成型(coordinated beamforming, CoBF)設計。此波束成型設計以數學公式定義成在傳輸速率中斷機率及功率預算限制下最大化事先定義之系統效用(system utility)的最佳化問題。因為複雜的中斷機率限制，此問題是一個非凸(nonconvex)且難以處理的數學問題。我們首先分析了此抑制中斷之協調式波束成型問題的複雜度，並證明了當系統效用為加權總和速率(weighted sum-rate)時，抑制中斷之協調式波束成型問題是本質上難解的，亦即NP難解(NP-hard)。此外，當系統效用為加權最小速率(weighted min-rate)時，此波束成型問題在除了所有傳輸端都只裝設單天線的情況外也是NP難解的。這些結果證實了有效率的近似方法對於此波束成型問題是絕對必要的，尤其是應用於大規模網路上。

由於以上的複雜度分析結果，我們接下來將焦點集中於高計算效率的演算法以求得高品質的近似解，例如抑制中斷之協調式波束成型問題的穩定點(stationary points)。具體而言，我們使用連續凸近似(successive convex approximation, SCA)的概念提出了一個稱為分散式連續凸近似(distributed SCA, DSCA)演算法的高斯-賽德爾(Gauss-Seidel)型分散式演算法來處理此波束成型問題。DSCA演算法是在文獻中第一個能求得此波束成型問題穩定點的多項式時間演算法。然而，由於DSCA演算法的計算複雜度是隨網路規模及傳輸天線數量的高次多項式成長，所以當問題的規模增大時，這個演算法還不是一個很實用的解法。

基於審慎的問題重構，我們使用最佳化方法中的分塊連續上界最小化(block successive upper bound minimization, BSUM)法，進一步提出了一個更有效率的高斯-賽德爾型分散式演算法，稱為分散式分塊連續上界最小化(distributed BSUM, DBSUM)演算法。此外，利用加權最小均方差(weighted minimum mean square error, WMMSE)重構問題，我們也提出了一個稱為分散式加權最小均方差(distributed WMMSE, DWMMSE)演算法的雅可比(Jacobi)型分散式演算法，此方法具有平行化結構，且可用於最佳化加權總和速率效用。這兩種方法都被驗證能以遠低於DSCA演算法的計算複雜度及較低的通訊負擔(communication overhead)收斂到原本NP難解問題的穩定點。為了進一步提供測量演算法效能的基準，我們也提出了一個基於多區塊從外近似(polyblock outer approximation)的放鬆近似(relaxed approximation)法。模擬結果顯示DBSUM演算法與DWMMSE演算法在效能上及計算效率上都遠優於DSCA演算法，且與效能基準比較的結果也展現出大有可為的近似效能。

關鍵字

協調式波束成型 ； 傳輸中斷機率 ； 凸優化 ； 分散式演算法 ； 複雜度分析

並列摘要

In this dissertation, we study the coordinated beamforming (CoBF) design in the multiple-input single-output (MISO) interference channel (IFC), assuming only channel distribution information (CDI) given a priori at the transmitters. The CoBF design is formulated as an optimization problem that maximizes a predefined system utility subject to constraints on the individual probability of rate outage and power budget. This problem is non-convex and appears difficult to handle due to the intricate outage probability constraints. We first conduct a complexity analysis of the outage constrained CoBF problem, and show that the outage constrained CoBF problem with the weighted sum-rate utility is intrinsically difficult, i.e., NP-hard. Moreover, the outage constrained CoBF problem with the weighted min-rate utility is also NP-hard except the case when all the transmitters are equipped with single antenna. These results confirm that efficient approximation methods are indispensable to the outage constrained CoBF problem, especially for the applications to large-scale networks.

Due to the complexity analysis results, we then focus on computationally efficient algorithms for obtaining high-quality approximate solutions, e.g., stationary points, of the outage constrained CoBF problem. Specifically, using the idea of successive convex approximation (SCA), we propose a Gauss-Seidel type distributed algorithm called the distributed SCA (DSCA) algorithm for handling the outage constrained CoBF problem. The DSCA algorithm is the first polynomial-time algorithm in the literature yielding stationary-point solution to the outage constrained CoBF problem. Nevertheless, the DSCA algorithm is not yet a practical solution when the problem size increases, since the computational complexity of the DSCA algorithm grows as a high-order polynomial of the network size and the number of transmit antennas.

Based on a judicious problem reformulation, we further propose, by leveraging on the block successive upper bound minimization (BSUM) method in optimization, a more efficient Gauss-Seidel type distributed algorithm, called distributed BSUM (DBSUM) algorithm. In addition, by exploiting a weighted minimum mean square error (WMMSE) reformulation, we also propose a Jocobi-type distributed algorithm, called distributed WMMSE (DWMMSE) algorithm, which can optimize the weighted sum-rate utility in a fully parallel manner. Both algorithms are shown to converge to the stationary points of the original NP-hard problems with much lower computational complexity and less communication overhead compared with the DSCA algorithm. To further provide a performance benchmark, a relaxed approximation method based on polyblock outer approximation is also proposed. Simulation results show that the DBSUM algorithm and the DWMMSE algorithm are significantly superior to the DSCA algorithm in both performance and computational efficiency, and can yield promising approximation performance by comparing with the performance benchmark.

並列關鍵字

coordinated beamforming ； outage probability ； convex optimization ； distributed algorithm ； complexity analysis

參考文獻

J. Lee, Y. Kim, H. Lee, B. L. Ng, D. Mazzarese, J. Liu, W. Xiao, and Y. Zhou, “Coordinated multipoint transmission and reception in LTE-advanced systems,” IEEE Commun. Mag., vol. 50, no. 11, pp. 44–50, Nov. 2012.

D. Gesbert, S. Hanly, H. Huang, S. S. Shitz, O. Simeone, and W. Yu, “Multi-cell MIMO cooperative networks: A new look at interference,” IEEE J. Sel. Areas Commun., vol. 28, no. 9, pp. 1380–1408, Dec. 2010.

L. Ventruino, N. Prasad, and X.-D. Wang, “Coordinated scheduling and power allocation in downlink multicell OFDMA networks,” IEEE Trans. Vehicular Tech., vol. 58, no. 6, pp. 2835–2848, July 2009.

H. Dahrouj and W. Yu, “Coordinated beamforming for the multicell multiantenna wireless system,” IEEE Trans. Wireless Commun., vol. 9, no. 5, pp. 1748–1759, May 2010.

L. Ventruino, N. Prasad, and X.-D. Wang, “Coordinated linear beamforming in downlink multi-cell wireless networks,” IEEE Trans. Wireless Commun., vol. 9, no. 4, pp. 1451–1461, Apr. 2010.