基于改進(jìn)共軛梯度的大規(guī)模多輸入多輸出預(yù)編碼

白鶴 劉紫燕 張杰 萬(wàn)培佩 馬珊珊

摘 要：針對(duì)大規(guī)模多輸入多輸出（Massive MIMO）系統(tǒng)下行鏈路預(yù)編碼實(shí)現(xiàn)復(fù)雜、線性預(yù)編碼矩陣求逆困難等問(wèn)題，提出一種基于對(duì)稱(chēng)逐步超松弛預(yù)處理共軛梯度法（SSOR-PCG）的低復(fù)雜度預(yù)編碼算法。該算法在共軛梯度（PCG）算法的基礎(chǔ)上，采用對(duì)稱(chēng)逐步超松弛分裂（SSOR）算法對(duì)矩陣進(jìn)行預(yù)處理以降低矩陣的條件數(shù)，達(dá)到提高預(yù)編碼算法收斂速度、降低復(fù)雜度的目的。仿真結(jié)果表明：與PCG算法相比，所提出的SSOR-PCG預(yù)編碼算法運(yùn)行時(shí)間縮短約88.93%，在信噪比為26dB時(shí)已收斂;與迫零預(yù)編碼算法相比，所提算法迭代2次即可獲得與迫零預(yù)編碼算法相近的系統(tǒng)容量性能，復(fù)雜度降低約一個(gè)數(shù)量級(jí)，誤碼率降低約49.94%。

關(guān)鍵詞： 大規(guī)模多輸入多輸出;線性預(yù)編碼;共軛梯度;對(duì)稱(chēng)逐步超松弛

中圖分類(lèi)號(hào)：TP391.9

文獻(xiàn)標(biāo)志碼：A

Abstract：To solve the problems of high complexity of precoding and difficulty of linear matrix inversion in downlink Massive Multi-Input Multi-Output （Massive MIMO） system， a precoding algorithm based on low-complexity Symmetric Successive Over Relaxation Preconditioned Conjugate Gradient （SSOR-PCG） was proposed. Based on preconditioned Conjugate Gradient Precoding? （PCG） algorithm， a Symmetric Successive Over Relaxation （SSOR） algorithm was used to preprocess the matrix to reduce its condition number， accelerating the convergence speed and the decreasing the complexity. Simulation results demonstrate that compared with PCG algorithm， the proposed algorithm has running time of around 88.93% shortened and achieves convergence when the Signal-to-Noise Ratio （SNR） is 26dB. Furthermore， compared to zero-forcing precoding algorithm， the proposed algorithm requires only two iterations capacity-approaching performance，the overall complexity is reduced by one order of magnitude， and the bit error rate is decreased by about 49.94%.Key words： Massive Multi-Input Multi-Output （Massive MIMO）; linear precoding; conjugate gradient; Symmetric Successive Over Relaxation （SSOR）

0 引言

大規(guī)模多輸入多輸出（Massive Multi-Input Multi-Output， Massive MIMO）技術(shù)作為5G的關(guān)鍵技術(shù)之一，由于其具有容量大、頻譜效率高等特點(diǎn)而受到學(xué)者廣泛關(guān)注[1]。預(yù)編碼技術(shù)不僅可以提高信道容量、降低誤碼率和簡(jiǎn)化接收機(jī)，還能滿足用戶對(duì)高速率數(shù)據(jù)傳輸?shù)男枨螅瑢?duì)提升5G系統(tǒng)性能起到重要作用。

線性預(yù)編碼算法[2]因其算法復(fù)雜度低且容量性能接近非線性預(yù)編碼算法而被廣泛使用，其基本原理是發(fā)射端在已知信道狀態(tài)信息（Channel State Information， CSI）的前提下對(duì)發(fā)送信號(hào)進(jìn)行線性預(yù)處理，消除用戶間干擾，便于接收端信號(hào)檢測(cè)，提高系統(tǒng)容量。傳統(tǒng)線性預(yù)編碼算法主要包括迫零（Zero Forcing， ZF）預(yù)編碼、最小均方誤差（Minimum Mean Squared Error， MMSE）預(yù)編碼以及匹配濾波器（Matched Filter， MF）預(yù)編碼等[3]。隨著天線數(shù)目的不斷增加，線性預(yù)編碼算法求逆困難，系統(tǒng)復(fù)雜度呈指數(shù)形式增長(zhǎng)。

為了解決線性預(yù)編系統(tǒng)復(fù)雜度高等問(wèn)題，研究者以ZF算法矩陣求逆重點(diǎn)研究如何降低預(yù)編碼算法實(shí)現(xiàn)復(fù)雜度。文獻(xiàn)[4]采用紐曼級(jí)數(shù)（Neumann Series， NS）方法對(duì)矩陣進(jìn)行求逆，該方法從工程應(yīng)用角度來(lái)說(shuō)更易實(shí)現(xiàn);但其復(fù)雜度高于直接對(duì)矩陣進(jìn)行逆運(yùn)算。文獻(xiàn)[5]采用理查德森算法（Richardson Method， RM）來(lái)降低預(yù)編碼實(shí)現(xiàn)的復(fù)雜度，該算法通過(guò)迭代運(yùn)算代替矩陣求逆，可以有效降低系統(tǒng)復(fù)雜度;但是其收斂速度取決于松弛因子的選取。隨著天線數(shù)目的不斷增加，下行信道矩陣信道向量漸進(jìn)正交，文獻(xiàn)[6]利用正定Hermitian矩陣的特性，提出基于高斯賽德?tīng)枺℅auss-Seidel， GS）算法的預(yù)編碼方案。該算法以迭代方式逐漸近似ZF預(yù)編碼的系統(tǒng)容量性能，不需要矩陣求逆。

文獻(xiàn)[7]采用對(duì)稱(chēng)逐次超松弛（Symmetric Successive Over Relaxation， SSOR）算法將正定Hermitian矩陣分解為對(duì)角陣、嚴(yán)格的上三角陣和嚴(yán)格的下三角陣，通過(guò)對(duì)稱(chēng)的方式計(jì)算逐步超松弛（Successive Over Relaxation，SOR）算法，有效提高了算法收斂速率，降低了系統(tǒng)復(fù)雜度。為了解決線性預(yù)編碼矩陣求逆困難、算法復(fù)雜度高等問(wèn)題，本文提出一種基于改進(jìn)共軛梯度（Conjugate Gradient Precoding， PCG）算法的SSOR-PCG預(yù)編碼算法，該算法在CG算法的基礎(chǔ)上，采用SSOR分裂算法對(duì)矩陣進(jìn)行預(yù)處理來(lái)降低矩陣運(yùn)算的條件數(shù)，以達(dá)到提高預(yù)編碼算法收斂速度、降低系統(tǒng)復(fù)雜度的目的。

1 大規(guī)模多輸入多輸出系統(tǒng)模型

搭建一個(gè)單小區(qū)多用戶大規(guī)模多輸入多輸出下行鏈路系統(tǒng)模型，假設(shè)該模型工作在FDD模式，基站端配備M根天線，接收端配備K根天線，其中MK。假設(shè)接收端的用戶均為單天線用戶且滿足等功率分配條件，基站端可以獲得完全信道狀態(tài)信息[8]。則下行鏈路接收信號(hào)y可以表示為：

其中： y∈RK*1為K個(gè)用戶獲得的總接收信號(hào);hK∈RM*1為從基站端到用戶K的信道矢量;n～CN（0，IK）為AWGN噪聲。x～RM*1為基站端M根天線的發(fā)送信號(hào)，可以表示為：

由于信道矩陣具有漸進(jìn)正交性，文獻(xiàn)[10]已經(jīng)證明當(dāng)基站端天線數(shù)目接近于無(wú)窮時(shí)，ZF預(yù)編碼的系統(tǒng)容量無(wú)限趨近臟紙預(yù)編碼（Dirty Paper Precoding，DPC）的系統(tǒng)容量。ZF預(yù)編碼算法通常需要對(duì)預(yù)編碼矩陣W進(jìn)行逆運(yùn)算求解，由于大規(guī)模多輸入多輸出系統(tǒng)中基站端天線數(shù)目龐大，導(dǎo)致ZF預(yù)編碼矩陣的求逆過(guò)程十分復(fù)雜，其計(jì)算復(fù)雜度描述為O（K3）。

2.2 共軛梯度預(yù)編碼算法

共軛梯度法（Conjugate Gradient， CG）的基本思想是將共軛法與最速下降方法相結(jié)合，使用已知的梯度方向構(gòu)建共軛方向，并沿方向搜素目標(biāo)函數(shù)的最小值。共軛梯度算法具有二次終止性，不需要進(jìn)行矩陣存儲(chǔ)操作，既能改善最速下降法收斂速度慢的缺點(diǎn)，又能解決牛頓法需要計(jì)算Hesse矩陣逆的問(wèn)題。

文獻(xiàn)[11]指出大規(guī)模多輸入多輸出系統(tǒng)中信道矩陣H是滿秩矩陣，當(dāng)且僅當(dāng)q是一個(gè)零向量時(shí)qH的值才為零。對(duì)于所有的非零向量q，都滿足qPqH>0，因此矩陣P是Hermitian正定矩陣，在大規(guī)模多輸入多輸出系統(tǒng)中可以采用CG算法求解方程組Pt=s的解。

2.3 SSOR-PCG預(yù)編碼算法

雖然CG算法相較于ZF算法復(fù)雜度更低，但是當(dāng)Hermitian正定矩陣的條件數(shù)取值較大時(shí)，CG算法的迭代次數(shù)會(huì)增多，因此可以使用PCG算法以達(dá)到減小迭代次數(shù)的目的。PCG算法的基本思想為：通過(guò)對(duì)Hermitian正定矩陣P進(jìn)行預(yù)處理來(lái)減少系數(shù)矩陣的條件數(shù)，從而提高CG算法的收斂速度[12]。

PCG算法的重點(diǎn)是如何選擇合適的預(yù)處理矩陣C。通常預(yù)處理矩陣的選擇需要滿足以下幾個(gè)條件：

1）預(yù)處理矩陣C應(yīng)該為對(duì)稱(chēng)正定矩陣;

2）預(yù)處理矩陣C應(yīng)該與Hermitian正定矩陣P具有相似性;

3）預(yù)處理Hermitian正定矩陣的特征值應(yīng)該盡量集中，即cond（）≈1盡可能小;

4）預(yù)處理后的線性方程應(yīng)易于求解。

利用SSOR分裂算法將Hermitian正定矩陣P分裂為以下三部分：

其中：BJ=D-1（L+LH）為雅克比（Jacobi）迭代算法的迭代矩陣; ρ（BJ）為Jacobi迭代矩陣的譜半徑。由2.2節(jié)可知P=HHH，在快速變化的時(shí)變信道中P值不是恒定的，因此需要不斷計(jì)算最優(yōu)松弛因子ωopt的值。通常需要執(zhí)行兩次SOR算法才能獲得最佳ωopt值，在大規(guī)模多輸入多輸出通信系統(tǒng)中計(jì)算其最優(yōu)松弛因子十分困難，鑒于此，有學(xué)者提出通過(guò)簡(jiǎn)單數(shù)學(xué)變換來(lái)確定松弛因子的近似最優(yōu)值。對(duì)于瑞利衰落信道矩陣H而言，P=HHH+ζIK的對(duì)角線元素pkk（k=1，2，…，K）服從2M自由度卡方分布[14]。 根據(jù)文獻(xiàn)[15]，通過(guò)切比雪夫不等式變換，得到：

式（18）中當(dāng)M的取值接近無(wú)窮大時(shí)，式（1-ε）M < pkk < （1+ε）M的值近似為1。大規(guī)模多輸入多輸出系統(tǒng)中基站配備的M根天線可以近似表示為pkk，因此對(duì)角矩陣D-1可以近似表示為I/M，式（17）可以變?yōu)椋焊鶕?jù)隨機(jī)矩陣的相關(guān)理論，當(dāng)M和K的值足夠大且M/K的值接近固定時(shí)，矩陣P的最大譜半徑，即其最大奇異值可以表示為：

由式（22）可知，最優(yōu)松弛因子的近似最優(yōu)值opt僅取決于大規(guī)模多輸入多輸出系統(tǒng)中基站的天線數(shù)M和移動(dòng)端用戶數(shù)K。由文獻(xiàn)[16]可知只有當(dāng)0<ω<2時(shí)，SSOR算法才具有收斂性，其中最優(yōu)松弛因子范圍滿足1<ω<2，即用戶數(shù)與天線數(shù)的比值位于[0.051，0.171]。由于SSOR算法較SOR算法而言對(duì)松弛因子變化不敏感，所以SSOR算法采用最優(yōu)松弛因子的近似最優(yōu)值就可以確保獲得良好的系統(tǒng)性能。

3.2 復(fù)雜度分析

根據(jù)2.3節(jié)SSOR-PCG算法偽代碼可知，獲取αk需要1×K的rTk和K×1的rk相乘，以及1×K的mTk、K×K的C-1P和K×1的mk相乘，因此計(jì)算αk需要K2+2K次乘法;同理，計(jì)算tk+1需要K次乘法;計(jì)算rk需要K2+K次乘法;計(jì)算bk需要2K次乘法;計(jì)算mk+1需要K次乘法。綜上所述，SSOR-PCG算法每迭代一次需要O（2K2+7K）的復(fù)雜度。

根據(jù)式（2）、（3）可知，大規(guī)模多輸入多輸出系統(tǒng)中x的獲取需要M×K的H和K×1的s相乘，因此計(jì)算x需要MK次乘法;同理，x與歸一化因子β相乘需要M次乘法。綜上所述，SSOR-PCG算法復(fù)雜度為（2K2+7K）i+MK+M。文獻(xiàn)[17]表明CG預(yù)編碼算法每迭代1次需要執(zhí)行2K2+10K次乘法，其算法復(fù)雜度為（2K2+10K）i+MK+M。表1為不同迭代次數(shù)下ZF算法、CG算法和SSOR-PCG算法的復(fù)雜度。表2是三種不同預(yù)編碼算法的運(yùn)行時(shí)間。實(shí)驗(yàn)結(jié)果表明，ZF預(yù)編碼算法復(fù)雜度約為3個(gè)數(shù)量級(jí)，且算法運(yùn)行時(shí)間最短。CG預(yù)編碼算法和SSOR-PCG預(yù)編碼算法復(fù)雜度約為2個(gè)數(shù)量級(jí)，同ZF預(yù)編碼算法相比，復(fù)雜度降低約1個(gè)數(shù)量級(jí)。在算法復(fù)雜度數(shù)量級(jí)相同的情況下，本文所提SSOR-PCG預(yù)編碼算法相較于CG算法運(yùn)行時(shí)間縮短約88.93%。

4 仿真結(jié)果及分析

[5] TRIFAN R， ENESCU A. MU-MIMO precoding performance conditioned by inter-user angular separation[C]// Proceedings of the 2018 International Symposium on Electronics and Telecommunications. Piscataway： IEEE， 2018： 1-4.

[6] FENG M， XU Y. Low-complexity linear precoding for pilot contamination mitigation in multi-cell massive MIMO systems[C]// Proceedings of the 2017 International Symposium on Intelligent Signal Processing and Communication Systems. Piscataway： IEEE， 2017： 807-811.

[7] LU Z， NING J， ZHANG Y， et al. Richardson method based linear precoding with low complexity for massive MIMO systems[C]// Proceedings of the IEEE 81st Vehicular Technology Conference. Piscataway： IEEE， 2015： 1-4.

[8] NAM J， ADHIKARY A， AHN J， et al. Joint spatial division and multiplexing： opportunistic beamforming， user grouping and simplified downlink scheduling[J]. IEEE Journal of Selected Topics in Signal Processing， 2014， 8（5）： 876-890.

[9] JU M， QIAN J， LI Y， et al. Comparison of multiuser MIMO systems with MF， ZF and MMSE receivers[C]// Proceedings of the 2013 IEEE Third International Conference on Information Science and Technology. Piscataway： IEEE， 2013： 1260-1263.

[10] QIN X， YAN Z， HE G. A near-optimal detection scheme based on joint steepest descent and Jacobi method for uplink massive MIMO systems[J]. IEEE Communications Letters， 2016， 20（2）： 276-279.

[11] XIE T， HAN Q， XU H， et al. A low-complexity linear precoding scheme based on SOR method for massive MIMO systems[C]// Proceedings of the IEEE 81st Vehicular Technology Conference. Piscataway： IEEE， 2015： 1-5.

[12] 曲樺， 梁靜， 趙季紅， 等. 基于SOR-PCG的低復(fù)雜度信號(hào)檢測(cè)算法研究[J]. 電視技術(shù)， 2016， 40（8）： 99-102， 117. （QU H， LIANG J， ZHAO J H， et al. Study on low-complexity signal detection based on successive over relaxation-preconditioned conjugate gradient method [J]. Video Engineering， 2016， 40（8）： 99-102， 117.）

[13] XIE T， DAI L， GAO X， et al. Low-complexity SSOR-based precoding for massive MIMO systems[J]. IEEE Communications Letters， 2016， 20（4）： 744-747.

[14] 楊偉茜. Massive MIMO系統(tǒng)中低復(fù)雜度預(yù)編碼算法研究[D]. 贛州： 江西理工大學(xué)， 2018：41-48. （YANG W Q. Research on low-complexity precoding algorithm in Massive MIMO system[D]. Ganzhou： Jiangxi University of Science and Technology， 2018：41-48.）

[15] 朱慶浩. 大規(guī)模MIMO系統(tǒng)預(yù)編碼算法的研究與優(yōu)化[D]. 贛州： 江西理工大學(xué)， 2018：27-30. （ZHU Q H. Research and optimization of precoding algorithm for large-scale MIMO systems[D]. Ganzhou： Jiangxi University of Science and Technology， 2018：27-30.）

[16] 張弛. 大規(guī)模MIMO系統(tǒng)低復(fù)雜度預(yù)編碼算法研究[D]. 南京： 東南大學(xué)， 2018：20-35. （ZHANG C. Research on low-complexity precoding algorithm of large-scale MIMO system[D]. Nanjing： Southeast University， 2018：20-35.）

[17] 任彥. 大規(guī)模MIMO預(yù)編碼算法的研究[D]. 成都： 西南交通大學(xué)， 2017：30-42. （REN Y. Research on large-scale MIMO precoding algorithm[D]. Chengdu： Southwest Jiaotong University， 2017：30-42.）

[18] 李婉婉. 大規(guī)模天線系統(tǒng)中的預(yù)編碼及相關(guān)技術(shù)研究[D]. 成都： 電子科技大學(xué)， 2018：14-16. （LI W W. Research on precoding and related technologies in large-scale antenna systems[D]. Chengdu： University of Electronic Science and Technology of China， 2018：14-16.）