大規(guī)模MIMO系統(tǒng)中的改進(jìn)CG迭代算法

劉 剛，婁增進(jìn)，林勤華，郭 漪

(西安電子科技大學(xué) 綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710071)

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

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

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

1 理論基礎(chǔ)

1.1 系統(tǒng)模型

設(shè)多入多出系統(tǒng)包含N個(gè)接收天線、K個(gè)發(fā)射天線，N?K，如圖1所示。

多入多出系統(tǒng)接收信號可以表示為

y=Hx+n，

(1)

對接收信號進(jìn)行最小均方誤差檢測，可得

(2)

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

(3)

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

1.2 幾種常用的迭代法

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

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

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

(4)

當(dāng)滿足‖I-AX0‖<1時(shí)，實(shí)現(xiàn)收斂。因?yàn)榕ｎD迭代法為二次收斂，所以它的計(jì)算復(fù)雜度僅取決于迭代次數(shù)。文獻(xiàn)[15]指出牛頓迭代法在k次迭代后的結(jié)果與基于諾伊曼級數(shù)展開方法中2k-1次迭代的結(jié)果相同。因此，在相同的系統(tǒng)配置下，牛頓迭代法要比其他的迭代方法具有更快的收斂速度。

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

首先定義殘差向量為

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

(5)

之后計(jì)算方向向量：

(6)

定義迭代步長：

(7)

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

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

(8)

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

2 改進(jìn)的共軛梯度迭代檢測算法

基于傳統(tǒng)共軛梯度迭代算法，首先將理查森迭代算法的初始矩陣X0=αI作為牛頓迭代算法的初始矩陣進(jìn)行一次迭代，之后將牛頓迭代算法一次迭代的結(jié)果作為共軛梯度迭代算法的初始矩陣?yán)^續(xù)迭代。通過如上操作，顯著地降低了算法的復(fù)雜度，提高了算法的收斂速度，具體算法如下所示。

算法改進(jìn)的共軛梯度迭代算法。

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

輸出：x。

① 初始化：

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

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

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

④ 迭代開始

⑤ fork=0，1，…，ndo

⑥ ifp0=0 then

⑦ returnx

⑧ end

x=xn。

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

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

A=D-L-LH，

(9)

其中，D由A的主對角線元素構(gòu)成，-L是A的嚴(yán)格上三角部分，而-LH是-L的共軛轉(zhuǎn)置，即A的嚴(yán)格下三角部分。

在迭代算法中，常用的矩陣求逆初值主要有兩類：一類是雅可比算法的初值X0=D-1，另一類是理查森算法的初值X0=αI。當(dāng)多入多出系統(tǒng)發(fā)送和接收天線的數(shù)目變?yōu)闊o窮大時(shí)，根據(jù)隨機(jī)矩陣?yán)碚摚钚【秸`差檢測算法濾波矩陣的最小和最大特征值將保持穩(wěn)定，并各自收斂到[17]

(10)

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

結(jié)合雅可比迭代檢測算法的迭代矩陣

BJ=D-1(L+LH) ，

(11)

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

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

(12)

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

(13)

由此可以計(jì)算BJ的譜半徑為

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

(14)

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

BR=I-αA。

(15)

最優(yōu)松弛參數(shù)的值通常設(shè)置為

(16)

由式(15)和式(16)，以及結(jié)合式(10)，可以將準(zhǔn)最優(yōu)松弛參數(shù)寫成

(17)

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

(18)

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

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

(19)

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

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

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

(20)

3 復(fù)雜度分析

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

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

圖3比較了天線規(guī)模為32×256時(shí)幾種算法的計(jì)算復(fù)雜度。從圖3可以看出，文中算法相比于基于諾伊曼級數(shù)展開的檢測算法以及傳統(tǒng)牛頓迭代算法，復(fù)雜度低了很多。需要特別指出的是，上述幾種算法因?yàn)楸苊饬司仃嚽竽孢\(yùn)算，計(jì)算復(fù)雜度均要低于最小均方誤差算法。

筆者提出算法的計(jì)算復(fù)雜度的計(jì)算過程如下：

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

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

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

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

4 仿真分析

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

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

圖5為文中算法、文獻(xiàn)[16]算法與目前收斂速度較快且檢測性能較好的傳統(tǒng)牛頓迭代算法以及應(yīng)用廣泛的基于諾伊曼級數(shù)展開檢測算法的誤碼率性能比較?？梢悦黠@看出，文中算法在收斂速度上優(yōu)于另外3種算法，僅需3次迭代，檢測性能就可以逼近最小均方誤差算法。同時(shí)，在計(jì)算復(fù)雜度方面，由上一節(jié)的分析可知文中算法相較其他算法更具有優(yōu)勢，從而驗(yàn)證了文中算法的優(yōu)越性。

5 結(jié)束語

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