大規模MIMO系統中的改進CG迭代算法

劉 剛，婁增進，林勤華，郭 漪

(西安電子科技大學 綜合業務網理論及關鍵技術國家重點實驗室，陜西 西安 710071)

大規模多入多出(Multiple Input Multiple Output，MIMO)技術是未來移動通信系統[1]重要的組成部分，它不僅使得通信系統更加可靠，還可以提高通信系統的容量[2]。然而在5G、B5G/6G系統中，天線陣列中將會放置上萬個天線單元，使得大規模多入多出系統接收端的計算復雜度難以承受[3]。采用超大型天線陣列的分組和控制技術，可以將超大規模天線陣列拆分成多個組別[4-5]，以減少陣列中天線單元的數目，使得傳統信號檢測算法能夠得以應用[6]。

在大規模多入多出信號檢測領域已有大量的研究成果，分別研究了計算復雜度、檢測性能、算法收斂速度、能效以及頻譜效率等。文獻[7]中提出了一種基于雅可比的迭代算法，文獻[8]中提出了一種基于理查森算法的檢測算法，相比最小均方誤差算法，它們的計算復雜度低，但存在收斂速度慢的弊端。BAKULIN等[9]對線性方程進行了變換，避開了高維矩陣求逆運算，從而降低了計算復雜度，但它需要12次迭代才能取得較好的性能。文獻[10]中提出了共軛梯度(Conjugate Gradient，CG)算法，它利用矩陣梯度搜索方法，避免了矩陣求逆運算，但是矩陣梯度計算帶來了較高的復雜度，同時檢測性能不佳。文獻[11]中提出了一種基于諾伊曼級數展開的檢測算法，它采用級數展開近似矩陣求逆運算，但是當展開階數大于等于3時，計算復雜度會高于矩陣求逆運算。文獻[12]中提出了利用松弛因子加速迭代的算法，GAO等[13]提出了一種最優松弛因子的超松弛迭代算法，NING等[14]提出了改進對稱超松弛迭代算法，經由數次迭代即可得到較好的檢測性能，但是算法性能受收發天線數目的影響很大，從而限制了它的適用場景。JIN等[15]提出了一種基于牛頓迭代的信號檢測算法，能夠取得較好的檢測精度和較快的收斂速度，得到了廣泛應用，但是該算法涉及過多的矩陣乘法運算，導致計算復雜度較高。CHATAUT[16]基于近似消息傳遞(Approximate Message Passing，AMP)算法，提出了一種低復雜度檢測算法，能夠取得良好的檢測性能，但是它通常需要6～8次迭代才能接近最小均方誤差(Minimum Mean Square Error，MMSE)算法的性能，收斂速度受限。

基于上述情況，筆者提出了一種改進的共軛梯度迭代算法，它能夠在較少迭代次數、較低計算復雜度情況下達到理想的檢測性能。仿真結果表明，該算法僅需3次迭代，即可接近最小均方誤差檢測性能。

1 理論基礎

1.1 系統模型

設多入多出系統包含N個接收天線、K個發射天線，N?K，如圖1所示。

多入多出系統接收信號可以表示為

y=Hx+n，

(1)

對接收信號進行最小均方誤差檢測，可得

(2)

若令b=HHy表示最小均方誤差算法的匹配濾波器，A=(HHH+σ2Ik)-1表示最小均方誤差濾波矩陣，則式(2)可以重寫為

(3)

這里，A-1的計算復雜度為O(K3)[17]。

1.2 幾種常用的迭代法

迭代法的基本思想是將A分解成A=P+Q的形式[15]，其中P是非奇異矩陣。

(1) 牛頓迭代算法以其良好的檢測性能，在實際中得到了廣泛應用。令X0是A-1的初始估計，則第k次牛頓迭代可以寫成如下形式[15]：

Xk=Xk-1(2I-AXk-1) 。

(4)

當滿足‖I-AX0‖<1時，實現收斂。因為牛頓迭代法為二次收斂，所以它的計算復雜度僅取決于迭代次數。文獻[15]指出牛頓迭代法在k次迭代后的結果與基于諾伊曼級數展開方法中2k-1次迭代的結果相同。因此，在相同的系統配置下，牛頓迭代法要比其他的迭代方法具有更快的收斂速度。

(2) 共軛梯度迭代算法是一種矩陣梯度搜索算法，它充分結合了最速下降法和共軛特性，通過最小化殘差來實現。

首先定義殘差向量為

r(k)=Ax(k-1)-b。

(5)

之后計算方向向量：

(6)

定義迭代步長：

(7)

從而得到更新的解向量，即

x(k)=x(k-1)+α(k)d(k)。

(8)

共軛梯度迭代算法是一種在理論上通過有限步迭代即可得到解的檢測算法。與牛頓迭代算法相比，它不需要已知二階導數信息，計算復雜度大幅度下降；同時它不需要存儲矩陣信息，從而使空間復雜度得到降低。與最速下降法相比，共軛梯度迭代算法利用共軛信息加速了算法收斂。筆者在共軛梯度迭代算法的基礎上，通過優化初始值來提高算法的收斂速度和檢測精度。

2 改進的共軛梯度迭代檢測算法

基于傳統共軛梯度迭代算法，首先將理查森迭代算法的初始矩陣X0=αI作為牛頓迭代算法的初始矩陣進行一次迭代，之后將牛頓迭代算法一次迭代的結果作為共軛梯度迭代算法的初始矩陣繼續迭代。通過如上操作，顯著地降低了算法的復雜度，提高了算法的收斂速度，具體算法如下所示。

算法改進的共軛梯度迭代算法。

輸入：H，y，σ2，K，N。

輸出：x。

① 初始化：

②A=HHH+σ2I，b=HHy，α=1/(K+N)，

③x0=2αb-α2Ab，r0=b-Ax0，p0=r0

(x0為牛頓迭代算法一次迭代后的結果，r為殘差向量)

④ 迭代開始

⑤ fork=0，1，…，ndo

⑥ ifp0=0 then

⑦ returnx

⑧ end

x=xn。

上述算法中，α是最優松弛因子，I是維度為K×K的單位矩陣。下面對算法進行分析。

由于A=HHH+σ2I是厄米特正定矩陣，其上三角部分和下三角部分互為共軛對稱矩陣，所以矩陣A又可寫為

A=D-L-LH，

(9)

其中，D由A的主對角線元素構成，-L是A的嚴格上三角部分，而-LH是-L的共軛轉置，即A的嚴格下三角部分。

在迭代算法中，常用的矩陣求逆初值主要有兩類：一類是雅可比算法的初值X0=D-1，另一類是理查森算法的初值X0=αI。當多入多出系統發送和接收天線的數目變為無窮大時，根據隨機矩陣理論，最小均方誤差檢測算法濾波矩陣的最小和最大特征值將保持穩定，并各自收斂到[17]

(10)

在這種情況下，信道硬化現象異常明顯，如圖2所示。此時，濾波矩陣的非對角線元素幾乎可以忽略，即A可以近似為對角線元素，有D≈A=NI。

結合雅可比迭代檢測算法的迭代矩陣

BJ=D-1(L+LH) ，

(11)

可以得到如下形式的雅可比算法迭代矩陣：

BJ=D-1(L+LH)=I-D-1A=I-A/N。

(12)

由式(10)和式(12)，可以得到BJ的特征值為

(13)

由此可以計算BJ的譜半徑為

ρ(BJ)=max|λ(BJ)|=(1+(K/N)1/2)2-1 。

(14)

同理，對于理查森算法，對應迭代矩陣的形式如下所示：

BR=I-αA。

(15)

最優松弛參數的值通常設置為

(16)

由式(15)和式(16)，以及結合式(10)，可以將準最優松弛參數寫成

(17)

由此可進一步得到理查森算法迭代矩陣的譜半徑：

(18)

把式(14)和式(18)進行對比分析，可得

ρ(BR)<2(K/N)1/2<2(K/N)1/2+K/N=ρ(BJ) 。

(19)

對于迭代算法來說，迭代矩陣的譜半徑與算法收斂速度為負相關關系[18]。所以，理查森算法的收斂速度更快。

牛頓迭代算法和其他迭代算法是正相關關系。在迭代算法中，當初始矩陣X0=αI時，比X0=D-1時收斂速度更快。相應地，在牛頓迭代算法中，以X0=αI作為初始迭代矩陣，也可以達到比以X0=D-1作為初始迭代矩陣時更快的收斂速度。因此，文中選取X0=αI作為改進算法的初值。

將矩陣求逆初值X0=αI代入牛頓迭代算法公式，做一次迭代可以得到

(20)

3 復雜度分析

表1對比了筆者提出的算法與傳統牛頓(Newton)迭代算法、基于諾伊曼(Neumann)級數展開檢測算法以及文獻[16]算法的計算復雜度。

表1 文中算法與其他幾種算法的復雜度比較

圖3比較了天線規模為32×256時幾種算法的計算復雜度。從圖3可以看出，文中算法相比于基于諾伊曼級數展開的檢測算法以及傳統牛頓迭代算法，復雜度低了很多。需要特別指出的是，上述幾種算法因為避免了矩陣求逆運算，計算復雜度均要低于最小均方誤差算法。

筆者提出算法的計算復雜度的計算過程如下：

b=HHy運算涉及的計算復雜度為NK；初始值x0=2αb-α2Ab運算過程包含了常數與向量的乘法運算2αb，復雜度為K；矩陣和向量之間的乘法運算Ab，復雜度為K2；常數與向量之間的乘法運算α2(Ab)，復雜度為K。而對于r0=b-Ax0中兩個矩陣之間的乘法運算Ax0，計算復雜度為K2。所以，文中算法在初始化部分的計算復雜度為2K2+(N+2)K。

這里以32×256多入多出系統為例。文中算法、傳統牛頓迭代算法、基于諾伊曼級數展開檢測算法、文獻[16]算法要實現接近最小均方誤差算法性能，需要的迭代次數分別為3次、4次、7次、8次，計算復雜度依次為8K2+282K、4 096K2+4 097K、5K3+256K2+256K、2 048K。

可以看出，基于諾伊曼級數展開的算法的復雜度達到了5K3+256K2+256K，即O(K3)級別。文獻[16]中的算法由于不需要矩陣求逆計算，計算復雜度為2 048K，但其收斂速度相對較慢，需要8次迭代才能達到理想的性能。文中算法基于共軛梯度迭代算法，較牛頓迭代算法的計算復雜度有很大降低，同時有著更快的收斂速度，僅需3次迭代即可達到目標性能。由圖3可以明顯看出，其計算復雜度也低于文獻[16]算法的。

當發送和接收天線數目為64×1 024時，同樣可以計算出文中算法、牛頓迭代算法、基于諾伊曼級數展開算法、文獻[16]中算法所需的計算復雜度分別為8K2+1 050K、16 384K2+16 385K、5K3+1 024K2+1 024K、8 192K。所得結論與之前相一致。

4 仿真分析

為了驗證所提改進算法的檢測性能，使用 MATLAB 軟件進行仿真驗證。采用誤比特率作為檢測性能的評估參數，對算法的檢測性能進行蒙特卡羅仿真實驗。仿真參數設置如下：調制方式為64QAM，信道為瑞利衰落信道。系統利用大型天線陣列分組和控制技術，將超大規模天線陣列拆分成若干小組，每一小組天線規模為32×256或64×1 024。

圖4給出了文中算法、文獻[16]算法與經典共軛梯度迭代算法誤碼率性能的比較。文中算法雖然以經典共軛梯度迭代算法作為主體，但文中算法的誤碼率性能明顯優于共軛梯度迭代算法的。當文中算法在迭代次數為3時，誤碼率性能就已經接近最小均方誤差算法的。而文獻[16]中的改進近似消息傳遞算法，需要8次迭代才能接近最小均方誤差算法的檢測性能，且根據第3節的分析可知，此時的計算復雜度高于文中算法的。

圖5為文中算法、文獻[16]算法與目前收斂速度較快且檢測性能較好的傳統牛頓迭代算法以及應用廣泛的基于諾伊曼級數展開檢測算法的誤碼率性能比較。可以明顯看出，文中算法在收斂速度上優于另外3種算法，僅需3次迭代，檢測性能就可以逼近最小均方誤差算法。同時，在計算復雜度方面，由上一節的分析可知文中算法相較其他算法更具有優勢，從而驗證了文中算法的優越性。

5 結束語

為了解決大規模多入多出系統信號檢測復雜度高、收斂速度慢等問題，基于共軛梯度迭代算法，筆者提出了一種改進的共軛梯度迭代算法。該算法以共軛梯度迭代算法為基礎，首先將理查森迭代算法的初始矩陣作為牛頓迭代算法的初始矩陣進行一次迭代，之后將迭代結果作為共軛梯度迭代算法的初始矩陣繼續迭代。仿真結果以及理論計算表明，相比目前應用廣泛的傳統牛頓迭代算法和基于諾伊曼級數展開的檢測算法、文獻[16]算法，筆者提出的算法擁有更快的收斂速度、更好的檢測性能和更低的計算復雜度。