基于Homotopy算法的低复杂度多用户大规模MIMO信号检测方法

胡 哲，景小荣

(重庆邮电大学 通信与信息工程学院，重庆 400065)

0 前 言

大规模多输入多输出(multiple input multiple output，MIMO)技术作为下一代移动通信系统物理层关键候选技术之一，受到了国内外学者的广泛关注[1-2]。与小规模MIMO系统不同，大规模MIMO系统通过在基站部署上百根天线，同时给多个用户提供高质量的服务，但由于基站天线数的剧增，给上行多用户信号检测带来了严重的挑战[3]。

作为最优检测的最大似然(maximum likelihood，ML)算法，其复杂度随着发射天线数呈指数型增长，如此高的计算复杂度对于大规模MIMO系统来说是不切合实际的。为此，近几年国内外学者相继提出许多近似最优检测算法。其中，非线性检测有固定复杂度球形检测(sphere decoding，SD)算法[4]；禁忌搜索(tabu search)检测算法[5]和似然上升搜索(likelihood-ascent search ，LAS)算法[6]。文献[7]通过对传统置信传播(belief propagation，BP)算法进行改进，提出一种适合大规模MIMO系统的低复杂度信号检测算法。文献[8]提出基于消息近似传递(approximate message passing algorithm，AMP)算法的信号检测算法。

根据文献[3]，当基站天线数趋于无限时，线性检测算法，比如迫零(zero-forcing，ZF)检测算法和最小均方误差(minimum mean square error，MMSE)检测算法[9]，可取得接近ML算法的性能。然而，这2种算法中均涉及到均衡矩阵的求逆运算，其计算复杂度数量级到达O(K3)。为了避免对上述这2种算法的均衡矩阵进行求逆运算，国内外学者相继提出一系列以ZF或MMSE为基础的低复杂度信号检测算法。其中，文献[10]采用了Neumann级数展开来近似代替均衡矩阵的逆，但是，当Neumann级数展开阶数大于3时，该方法的计算复杂度数量级依然高达O(K3)。文献[11]提出了基于Richardson迭代的低复杂度信号检测算法；文献[12] 提出了一种使用共轭梯度(conjugate gradient，CG)方法的低复杂度近似最优信号检测算法。文献[13]则利用在上行多用户大规模MIMO系统中，当N/K较大时，MMSE均衡矩阵呈现主对角占优和对称正定的特性，采取高斯-赛德尔(Gauss-seidel，GS)迭代算法进行信号检测，从而避免MMSE均衡矩阵求逆运算。近来，还有学者提出一种基于切比雪夫对称连续超松弛迭代(chebyshev symmetrical successive over-relaxation iteration algorithm ，CSSOR) 的检测算法[14]，利用此算法也可避免MMSE均衡矩阵求逆运算，从而极大地降低了系统的运算复杂度。

在上述分析的基础上，本文针对多用户大规模MIMO上行链路，基于MMSE准则，运用Homotopy算法[15]求解线性方程组的思想，提出一种低复杂度的信号检测算法。该检测方法有效地避免MMSE均衡矩阵的求逆运算，极大地降低了上行多用户大规模MIMO信号检测的计算复杂度。

1 系统模型

考虑单小区多用户大规模MIMO系统上行链路。假设大规模MIMO基站配备N根天线，在同一时频资源块上为K个单天线用户提供服务，满足N≫K。假设K个用户与基站完全同步，H∈CN×K表示信道矩阵，于是，基站端接收信号y∈CN×1可表示为

y=Hx+n

(1)

(1)式中：x表示K个用户将待发送的信息比特流经过信道编码和m-QAM调制后，形成K×1维的发送符号矢量；n表示均值为0，方差为σ2的，N×1维的复高斯背景噪声矢量。

采用MMSE接收，K个用户的发送信号矢量估计值可表示为

(2)

(3)

观察(3)式，大规模MIMO信号检测的实质就是求解线性方程组(3)。在此基础上，文中提出一种适合多用户大规模MIMO系统的低复杂度信号检测算法，具体见下。

2 基于Homotopy算法的信号检测方法

将基于更新后的信号模型(3)式，首先给出基于Homotopy算法的线性方程组求解基本过程，然后将其推广到多用户大规模MIMO上行链路信号检测过程中。

(4)

(4)式中：M为一辅助矩阵，它仅为W的一部分；v(0)表示初始解向量。由方程(4)等于零，得如下Homotopy方程。

(5)

现将Homotopy方程的解向量表示成一无限序列的形式，即

(6)

将(6)式代入(5)式中得

(7)

然而，对于任意q∈[0,1]，(7)式中等式左边都是独立于q的。因此有

(8)

如果选择的M为可逆矩阵，从理论的角度来看，(8)式可等效为

(9)

(10)

然而，(10)式需要计算矩阵M矩阵的逆，其计算复杂度依然很高。于是，在这里我们试图利用线性方程组(8)的解来代替线性方程组(10)的解。如果选择M矩阵为一个易于求逆的三角矩阵，那么方程组(8)的求解可通过前后向迭代来获得，从而使计算复杂度得到大幅度降低。

基于上述目的，根据递推关系(10)式，(6)式可写成通用形式，即

(11)

初始化：

1.M=L；

2.v(0)=0；

4.n=2；

迭代：

5.whilen≤Tdo

7.n=n+1

8.end while

3 计算复杂度分析

以复数乘(complex multiplication，CM)作为计算复杂度的度量，对本文所提出的基于Homotopy算法的大规模MIMO信号检测方法的计算复杂度进行评估。

当M=L，v(0)=0时，根据方程(8)运用Homotopy算法可得

(12)

由以上分析，图1给出基于Cholesky分解[10]的MMSE算法、基于Neumann级数展开[10]的MMSE算法、基于Richardson的MMSE算法[11]和本文提出的基于Homotopy算法的信号检测方法的复杂度对比。图2给出文献基于CG的MMSE算法[12]、基于GS的MMSE算法[13]、基于CSSOR的MMSE算法[14]与本文提出的基于Homotopy算法的信号检测方法的复杂度对比。简明起见，文中分别用Cho-MMSE，Neu-MMSE，Hom-MMSE，Rich-MMSE，CG-MMSE，GS-MMSE和CSSOR-MMSE表示。

图1 本文算法与文献[10-11]算法计算复杂度对比

图2 本文算法与文献[12-14]算法计算复杂度对比

由图1可知，当T≥3时Neu-MMSE和Cho-MMSE算法计算复杂度远远大于本文提出的Hom-MMSE算法。这是由于，根据文献[10]，当T≥3时Neu-MMSE算法和Cho-MMSE算法的复杂度均达到O(K3)，而Hom-MMSE算法计算复杂度却在O(K2)，与文献[11]中Rich-MMSE算法相比，Hom-MMSE算法复杂度略高于Rich-MMSE算法，但本文方法性能却更优。

由图2可知，本文方法与文献[12]中CG-MMSE算法相比，整体复杂度都低于CG-MMSE算法，由此可看出，本文方法在计算复杂度方面的优势。与文献[13]中GS-MMSE算法相比，本文方法复杂度略高。与文献[14]中CSSOR-MMSE算法相比，本文方法复杂度则整体较低。由此表明，理论分析与实际仿真结果相互吻合。

4 数值仿真及结果分析

利用MATLAB软件对本研究提出的Hom-MMSE信号检测算法的性能进行仿真。与文献[11]相同，本文设定基站接收天线数为N=128，各用户信息比特经过1/2速率生成码字为[133°177°]的标准卷积码和16-QAM调制后，从各自的天线发送出去；然后基站端先对接收到的信号进行16-QAM解调，最后再采用Viterbi译码方法进行译码。

首先，考虑非相关瑞利衰落信道情况。图3给出当小区用户数K=16，M=L，v(0)=0时，本文方法与文献[10-11]中算法的BER性能对比，其中，SNR表示信噪比。从图3可看出，本文提出的Hom-MMSE算法经过T=3阶展开的性能已优于文献[10]中Neu-MMSE算法采用T=6阶级数展开的性能，以及文献[11]中Rich-MMSE算法经过T=6次迭代的性能；经过T=4阶展开已经基本收敛到Cho-MMSE算法性能，并且没有太大的性能损失。结合之前复杂度分析的结果，可以得出Hom-MMSE算法优于Neu-MMSE算法和Rich-MMSE算法的结论。

图3 本文算法与文献[10-11]算法BER性能对比

图4给出本文方法与文献[12-14]中算法的BER性能对比，从图4可看出，本文Hom-MMSE算法与CG-MMSE算法[12]、GS-MMSE算法[13]和CSSOR-MMSE算法[14]都是经过T=5阶展开或迭代就可以完全收敛到Cho-MMSE算法性能，但是本文算法整体收敛速度都快于CG-MMSE算法，相比GS-MMSE算法和CSSOR-MMSE算法虽然整体收敛速度略慢，但由之前分析知，本文算法的计算复杂度更低。由以上分析可得，相比以上算法，本文Hom-MMSE算法综合性能更优。

图4 本文算法与文献[12-14]算法BER性能对比

图5 不同初始解向量下Hom-MMSE算法的BER性能

其次，考虑更为一般的相关衰落信道情况。这里的相关信道参考的是文献[16]中指数相关信道模型，需要指出与文献[16]不同的是，由于本文中用户为单天线用户，所以仅考虑基站端接收天线之间的接收相关，并未考虑用户端的发射相关，ρ(0≤ρ≤1)表示相邻2个接收天线之间的相关系数。与文献[13]相同，图6表示在信道相关系数ρ=0.5的条件下，本文方法与文献[10-11]中算法的BER性能对比。从图6中可以看出， Hom-MMSE算法经过T=3阶展开的性能已优于Neu-MMSE算法[10]采用T=6阶级数展开的性能，以及Rich-MMSE算法[11]T=6次迭代的性能，经过T=4阶展开已经基本收敛到Cho-MMSE算法性能，并且没有太大的性能损失。这就说明本文提出的Hom-MMSE算法在相关信道条件下相比Neu-MMSE算法和Rich-MMSE算法[11]都具有明显的优势。

图6 相关信道条件下本文算法与文献[10-11]算法BER性能对比

图7给出在相关信道条件下，本文方法与文献[12-14]中算法的BER性能对比。从图7中可以看出， Hom-MMSE算法、GS-MMSE算法[13]和CSSOR-MMSE算法[14]都是经过T=5阶展开或迭代就可以基本收敛到Cho-MMSE[10]算法的性能，而CG-MMSE[12]算法则需要更多次迭代才能收敛到Cho-MMSE算法的性能，说明本文方法比CG-MMSE算法收敛速度更快。相比GS-MMSE算法和CSSOR-MMSE算法虽然整体收敛速度略慢，但由复杂度分析知，本文算法的计算复杂度较低。由此可得本文Hom-MMSE算法综合性能更优。

图8给出在不同初始解向量的相关信道条件下， Hom-MMSE检测方法的BER性能对比。从图8可看出，在估计解向量时，Hom-MMSE算法在T=3次之后的BER性能与Cho-MMSE算法性能基本完全重合，且算法趋于收敛。在0初始解向量时，则需要T=4次。进一步说明初始解向量对算法的收敛速度的影响。

图7 相关信道条件下本文算法与文献[12-14]算法BER性能对比

图8 不同初始解向量的相关信道条件下Hom-MMSE算法的BER性能

5 结束语

本文提出了一种基于Homotopy算法的低复杂度的信号检测方法，该方法避免了MMSE均衡矩阵求逆运算，使计算复杂度数量级由O(K3)降为O(K2)。通过与一些经典的检测算法(如：Cho-MMSE,Neu-MMSE)和一些新型的检测算法(如：Rich-MMSE,CG-MMSE,GS-MMSE,CSSOR-MMSE)进行对比，从计算复杂度和BER性能2个方面进行分析，得出本文Hom-MMSE算法的优势。并且分析了在相关信道条件下本文Hom-MMSE算法的优势依然存在。最后，本文还给出在选取不同初始解向量时，该方法的BER性能对比，得出初始解向量越接近实际解向量，该算法的收敛速度越快的结论。