大规模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]算法，笔者提出的算法拥有更快的收敛速度、更好的检测性能和更低的计算复杂度。