基于消息传递的大规模多用户MIMO低复杂度的检测算法

王琼，叶伟，吉明明

（重庆邮电大学通信与信息工程学院，重庆 400065）

研究与开发

基于消息传递的大规模多用户MIMO低复杂度的检测算法

王琼，叶伟，吉明明

（重庆邮电大学通信与信息工程学院，重庆 400065）

针对大规模多用户多输入多输出（MIMO）系统中基站端检测复杂度高的问题，提出了一种低复杂度、基于强制收敛的变量节点全信息高斯消息传播迭代检测（VFI-GMPID-FC）算法。首先对传统的GMPID算法进行改进，得到VFI-GMPID算法，VFI-GMPID算法的检测性能逼近最小均方误差检测（MMSE）算法，但复杂度要大大低于MMSE算法。然后结合强制收敛思想和VFI-GMPID，提出VFI-GMPID-FC算法，进一步降低算法复杂度，提升检测效率。最后通过仿真结果表明，所提算法在保证检测性能的同时，能有效地降低算法的复杂度。

大规模多用户MIMO；高斯消息传递迭代检测；强制收敛；低复杂度

1 引言

现代无线通信对数据传输速率要求不断提高，多用户MIMO（multiple input multiple output，多输入多输出）系统作为其关键技术之一，现已被许多国际标准纳入其中。但为了追求更高的数据传输速率，多用户MIMO技术不断发展，并逐渐发展成大规模多用户MIMO系统，该系统中基站端的天线数量达到了成百上千个，这吸引了越来越多的用户关注[1-3]。

在大规模多用户MIMO系统中，由于用户数量增加、基站接收天线数量巨大、接收信号复杂和信道矩阵维度巨大等原因，基站端的检测复杂度高、效率低，因此低复杂度信号检测算法成为研究的热点。众所周知，MMSE算法是在高斯信号源的情况下表现最佳的线性检测算法。然而，由于它存在着大规模的矩阵求逆计算使得复杂度很高，难以运用于实际工程。为了避免矩阵求逆，一些经典的迭代算法，如雅可比算法、理查德森算法、诺伊曼级数和高斯—赛德尔算法被应用于MMSE算法中来降低其复杂度[4]。虽然这些算法在一定程度上提高了检测效率，但是它们是以牺牲检测性能为代价的，在许多情况下无法满足可靠性的要求。

近年来，为了使系统在满足检测性能的同时提高检测效率，研究者们不断地寻求低复杂度和性能更优的检测算法。基于图形检测的消息传递算法由于其低复杂度和优良的检测性能，被许多学者运用到MIMO系统的检测当中。其消息传递算法一般分为两类：一类是高斯置信度传播（Gaussian belief propagation，GaBP）算法[5-7]，另一类是高斯消息传播迭代检测（Gaussian message passing iterative detection，GMPID）算法[8-15]。这两类算法都是高效的高斯图模型的分布式算法，特别是GMPID算法，其广泛地运用在符号间干扰信道均衡和现代信道编码解码当中，如Turbo码和低密度奇偶校验码（low density check code，LDPC）。参考文献[16,17]证明了图形结构中的因子图具有树型结构，消息传递算法中均值和方差分别收敛于真实边际均值和近似边际方差。然而，如果因子图中存在着环路，消息传递算法中的均值和方差可能无法收敛。

本文首先针对GMPID算法收敛分析难的问题，通过改变变量节点的消息传输规则，改进了GMPID算法，得到了VFI-GMPID（variable node full information Gaussian message passing iterative detection，变量节点全信息高斯消息传播迭代检测）算法。然后对算法输出的估计值和均方误差进行收敛分析，并分析算法的复杂度，证明在用户数量与基站天线数量之比小于时，VFI-GMPID算法收敛于MMSE算法。为了进一步提高VFI-GMPID算法检测效率，结合强制收敛思想[18]优化VFI-GMPID算法，提出了VFI-GMPID-FC（variable node full information Gaussian message passing interactive detection based on forced convergence，变量节点全信息高斯消息传播迭代检测）算法。最后通过仿真验证VFI-GMPID算法收敛性，比较VFI-GMPID算法和VFI-GMPID-FC算法与MMSE算法在不同的信噪比下误码率的差异性。

2 系统模型

假定在大规模多用户MIMO系统中用户端有K个单天线用户，基站端有M根天线。上行链路中，多个用户向基站端同时发送各自的信号。如果无线信道是准静态的平坦衰落，信息传输过程中引入的是可加性高斯白噪声，且在接收端正确地获取信道的状态信息，对于某一时刻，基站接收信号可以表示为：

系统模型写成矩阵形式为：

基站端的多用户检测任务就是从所接收的信号矢量y中估计用户发送的信号矢量x。本文中假设基站端已知H，只考虑简单真实的大规模多用户MIMO系统，因为其复杂的情况可以从真实情况中扩展得到。

3 VFI-GMPID算法

3.1 算法原理

VFI-GMPID是一种基于因子图模型的算法。大规模多用户MIMO系统因子图模型如图1所示。

图1 大规模多用户MIMO系统因子图模型

图2 因子节点消息更新传递过程

更新过程可以看成一个多址接入的过程。因子节点接收变量节点所传来的消息，利用更新公式计算更新后的消息，再把更新后的消息传回给变量节点。第 m个因子节点的消息更新计算式为：

变量节点消息更新传递过程如图3所示。

图3 变量节点消息更新传递过程

变量节点消息更新可以看成广播过程。第k个变量节点的消息更新计算式为：

算法达到设定的迭代次数，输出为：

当M和K比较大时，大规模多用户MIMO系统模型因子图是完全图，则变量节点和因子节点之间的环路非常多。这时VFI-GMPID算法与原始的GMPID算法都存在着在消息传递过程中无法收敛的问题。本文提出的 VFI-GMPID算法和原始的GMPID算法相比，在变量节点的消息更新式（4）上有所不同。GMPID算法由于传输的是外信息，其结构性非常复杂，很难对其进行理论收敛性分析。而本文所提出的VFI-GMPID算法在因子节点传输给变量节点消息是全部的、完整的信息，而不仅仅是外信息。这使其结构性变得简单，让理论收敛分析变成了可能。当M非常大且K＜M时，VFI-GMPID算法和原始的GMPID算法中变量节点接收的消息之间的差异可以忽略不计，所以其在大规模多用户MIMO系统中不会导致性能显著损失。

3.2 收敛性分析

要对 VFI-GMPID算法进行收敛性分析就必须先对MMSE算法进行分析。MMSE算法对信号源估计值如下：

其中，V包含对每一个信号源的估计误差，具体而言协方差矩阵V中的对角线上的元素vkk是表示对xk的估计误差值。当K→∞时，由参考文献[21]可得：

其中：

下面将从两个方面对 VFI-GMPID算法进行收敛性分析，一方面对输出的收敛性分析，证明其收敛于MMSE算法的均方误差；另一方面对k收敛分析，证明其收敛于MMSE算法的估计值于。对于的收敛分析如下。

根据式（3）和式（4）可得：

当用户数量K与接收天线数量M非常大时，由卡方分布特性，式（13）可以近似等效于：

其中，s-1相对于M-K可以忽略，比较式（10）与式（16）可以得出，收敛于MMSE算法的均方误差。

其中，D为HTH的对角矩阵。

根据式（3）和式（4）可得：

根据经典迭代算法[22]可知，要使式（22）中 e∗收敛，必须有谱半径，即：

当式（22）收敛时可以看出，式（22）与式（6）有相同的收敛值，这说明VFI-GMPID的输出信号估计值收敛于MMSE的信号估计值，即收敛于。

由上述分析可知，对于大规模多用户MIMO

3.3 算法复杂度分析

通过式（6）可以看到，传统的MMSE算法的矩阵求逆运算的复杂度为O( K3)，矩阵乘法计算的复杂度为O( MK)，则MMSE算法的复杂度为，这个计算复杂度在天线数量非常大时是非常高的。而上述的VFI-GMPID算法的复杂度主要是在消息的更新计算当中，为其中Niter为设置的迭代次数。通过复杂度分析可以得到，在大规模多用户MIMO系统中，VFI-GMPID算法相比于MMSE算法具有较低的复杂度。

4 VFI-GMPID-FC算法

为了进一步提高VFI-GMPID的检测效率，本文结合强制收敛的思想，提出了 VFI-GMPID-FC算法。强制收敛原理是消息在传递过程中会收敛于一个确定的值，但是节点的收敛速度是不固定的，因此人为给定一个门限值，当其变化速率低于这个门限值时，则停止此节点的后续消息更新过程。其本质就是挑出某些节点并停止其后续的消息更新过程，以此来降低算法的复杂度。强制收敛思想可以运用于 VFI-GMPID算法中来降低计算复杂度。在消息更新的过程中，VFI-GMPID算法中变量节点和因子节点的强制收敛速度是不固定的。对于因子节点的消息更新过程，引入两个门限值 λe与 λv。当消息传递过程中，因子节点消息满足式（24）或式（25），则停止因子节点对应的消息成分更新：

在节点消息成分停止更新后，其后面的迭代过程将保持固定的消息输出值。

VFI-GMPID-FC算法步骤描述如下。

步骤 1 输入信道矩阵H、接收矢量y、门限值λe和λv、迭代次数Niter。

步骤3 利用式（3）计算因子节点的消息，并利用式（24）和式（25）判断哪些节点停止更新消息，把停止更新的节点加入停止更新列表。

步骤4 利用式（4）计算变量节点的消息。

5 仿真分析

大规模多用户MIMO系统应用中，基站端的天线数量一般要大于用户数量。所以仿真模型采用基站端的接收天线数量为600，单天线用户数量为100，用户与基站天线的比值。用户天线到基站天线之间的信道增益 hij服从独立同分布，且服从均值为 0、方差为 1的复高斯分布。采用16QAM调制，用户发送的信号服从独立同分布，且服从均值为0、方差为1的复高斯分布。Niter为迭代次数，MSE为检测算法输出的信号源估计值与实际的信号值之间的平均均方误差。

本文所提出的VFI-GMPID算法的MSE收敛分析如图4所示。从图4中可以看出，当M=600、时，VFI-GMPID算法在一定的信噪比情况下，随着迭代次数的增加，其平均均方误差不断减小，则其检测性能也在不断地提升，并且不断逼近MMSE的平均均方误差。当Niter=7时，与MMSE算法相比，VFI-GMPID算法的平均均方误差值与达到10-4时所需的信噪比相差0.95 dB。

图4 VFI-GMPID算法的MSE收敛分析

图5是在不同迭代次数下，VFI-GMPID算法与参考文献[11]中所改进的检测性能较好的简化期望近似消息传递算法（approximate message passing simplified by expection propagation，AMP-EP）、MMSE算法的误码率（bit error rate，BER）比较。VFI-GMPID算法的检测性能随着迭代次数的增加不断提高，并且误码率逼近于MMSE算法。当Niter=7时，与 MMSE相比，VFI-GMPID算法的误码率与达到10-4时所需的信噪比相差0.55 dB，与AMP-EP算法相差0.32 dB。结合图4和图5可以看出，本文所提出算法有实际运用的可行性。

为了分析VFI-GMPID-FC算法中强制收敛门限值λe和λv对其检测性能和复杂度的影响。统计的大规模多用户MIMO系统中运用VFI-GMPID-FC算法，对于不同的λe和λv，在信噪比为5 dB、迭代次数为7、检测20 000次符号时，因子节点停止消息更新的平均数量与不同算法的仿真运行时间。图6（a）为只设定λ，统计因子节点中停止消息(t )的

e平均个数。图 6（b）为只设定 λv，统计因子节点中停止消息(t )的平均个数。

图5 VFI-GMPID不同迭代次数下误码率

不同算法运行时间见表1。从表1中可以看出，VFI-GMPID和AMP-EP算法在相同条件下仿真运行时间相差不多，因为两者的计算复杂度都是在量级。而VFI-GMPID-FC算法因为引入了门限，其仿真运行时间明显下降，说明其能有效地降低复杂度。

图7为不同改进算法在迭代次数为7的情况下与 MMSE算法在不同信噪比的误码率比较。VFI-GMPID-FC算法设置合适的门限值，其性能相比于VFI-GMPID算法在较低信噪比没有性能的太大损失，在较高信噪比端有一定的损失。当误差率达到10-4时，VFI-GMPID-FC算法相比于VFI-GMPID算法所需的信噪比要高1.3 dB，相比于AMP-EP算法要高0.95 dB。结合表1和图7可以得到，对于VFI-GMPID-FC算法来说，门限值设置过低，停止节点更新的数量较少，起不到降低复杂度的作用；而门限值设置过高，将有太多的节点停止更新，影响算法的检测性能。所以选择合适的门限值才能在不影响检测性能的情况下，起到降低复杂度的作用。

图6 两种门限值平均停止节点数

表1 不同算法运行时间

图7 VFI-GMPID-FC算法性能比较

6 结束语

本文主要研究大规模多用户MIMO系统低复杂度的检测算法技术。由于传统的MMSE算法存在着矩阵求逆，复杂度高，不适用于大规模多用户MIMO系统。本文根据消息传递算法的原理，提出了一种低复杂度的VFI-GMPID-FC算法。首先对GMPID改进，得到了VFI-GMPID算法。该算法在大规模多用户 MIMO系统中时，设置合适的迭代次数，其误码率与MMSE算法相当，复杂度却大大降低。之后结合强制收敛思想对 VFI-GMPID算法进行优化，提出了VFI-GMPID-FC算法，进一步地降低了 VFI-GMPID算法的复杂度。仿真结果表明，当VFI-GMPID-FC算法设置合适的门限值时，能够在保证检测性能的同时，又具有较低的复杂度，非常适用于大规模多用户MIMO系统。

[1] RUSEK F, PERSSON D, LAU B K, et al. Scaling up MIMO: opportunities and challenges with very large arrays[J]. Signal Processing Magazine IEEE, 2012, 30(1): 40-60.

[2] 毕奇, 谢伟良, 陈鹏, 等. LTE多天线技术发展趋势[J]. 电信科学, 2014, 30(10): 1-7. BI Q, XIE W L, CHEN P, et al. Progress and trends of multiple antennas technology in LTE network[J]. Telecommunications Science, 2014, 30(10): 1-7.

[3] 阳析, 金石. 大规模 MIMO系统传输关键技术研究进展[J].电信科学, 2015, 31(5): 28-35. YANG X, JIN S. Overview of key technologies of transmissionin massive MIMO system[J]. Telecommunications Science, 2015, 31(5): 28-35.

[4] 周将运. Massive MIMO系统的检测算法研究[D]. 成都: 电子科技大学, 2015. ZHOU J Y. Research on detection algorithms for massive MIMO systems[D]. Chengdu: University of Electronic Science and Technology of China, 2015.

[5] MOALLEMI C C, VAN ROY B. Convergence of min-sum message passing for quadratic optimization[J]. IEEE Transactions on Information Theory, 2009, 55(5): 2413-2423.

[6] WEISS Y, FREEMAN W T. Correctness of belief propagation in gaussian graphical models of arbitrary topology[J]. Neural Computation, 2001, 13(10): 2173.

[7] SU Q, WU Y C. Convergence analysis of the variance in gaussian belief propagation[J]. IEEE Transactions on Signal Processing, 2014, 62(19): 5119-5131.

[8] GUO Q, PING L. LMMSE turbo equalization based on factor graphs[J]. IEEE Journal on Selected Areas in Communications, 2008, 26(2): 311-319.

[9] MONTANARI A, PRABHAKAR B, TSE D. Belief propagation based multi-user detection[C]//Allerton Conference on Communication, May 22, 2006, Monticello, USA. [S.l.:s.n.], 2006: 1-9.

[10] ABBAS S M, FAN Y Z, CHEN J, et al. Low complexity belief propagation polar code decoder[C]//2015 IEEE Workshop on Signal Processing Systems (SiPS), October 14-16, 2015, Hangzhou, China. New Jersey: IEEE Press, 2015: 1-6.

[11] WU S, KUANG L, NI Z, et al. Low-complexity iterative detection for large-scale multiuser MIMO-OFDM systems using approximate message passing[J]. IEEE Journal of Selected Topics in Signal Processing, 2014, 8(5): 902-915.

[12] YOON S, CHAE C B. Low-complexity MIMO detection based on belief propagation over pairwise graphs[J]. IEEE Transactions on Vehicular Technology, 2014, 63(5): 2363-2377.

[13] YUE Z, GUO Q, XIANG W. Complex Gaussian belief propagation algorithms for distributed iterative receiver[C]//2014 IEEE 25th Annual International Symposium on Personal, Indoor, and Mobile Radio Communication (PIMRC), September 2-5, 2014, Washington, USA. New Jersey: IEEE Press, 2014: 1908-1912.

[14] HAN K, HU J, CHEN J, et al. A high performance massive MIMO detector based on log-domain belief-propagation[C]// International Conference on Asic, November 3-6, 2015, Chengdu, China. New Jersey: IEEE Press, 2015: 1-4.

[15] YUAN Z, ZHANG C, WANG Z, et al. An Auxiliary Variable-aided hybrid message passing approach to joint channel estimation and decoding for MIMO-OFDM[J]. IEEE Signal Processing Letters, 2017(99): 1.

[16] KSCHISCHANG F R, FREY B J, LOELIGER H A. Factor graphs and the sum-product algorithm[J]. IEEE Transactions on Information Theory, 2001, 47(2): 498-519.

[17] LOELIGER H A. An introduction to factor graphs[J]. IEEE Signal Processing Magazine, 2004, 21(1): 28-41.

[18] CHOI B J, SUNWOO M H. Simplified forced convergence decoding algorithm for low power LDPC decoders[C]//2014 IEEE Asia Pacific Conference on Circuits and Systems (APCCAS), November 17-20, 2014, Ishigaki, Japan. New Jersey: IEEE Press, 2014: 663-666.

[19] LIU X, SIMEONE O, ERKIP E. Energy-efficient sensing and communication of parallel Gaussian sources[J]. IEEE Transactions on Communications, 2012, 60(12): 3826-3835.

[20] KAFEDZISKI V. Rate allocation for transmission of two Gaussian sources over multiple access fading channels[J]. IEEE Communications Letters, 2012, 16(11): 1784-1787.

[21] VERDU S. Multiuser detection[M]. Cambridge: Cambridge University Press, 1998.

[22] AXELSSON O. Iterative solution methods[M]. Cambridge: Cambridge University Press, 1994.

A low complexity detection algorithm for large scale multiuser MIMO based on message passing

WANG Qiong, YE Wei, JI Mingming
School of Communication and Information Engineering, Chongqing University of Posts and Telecommunications, Chongqing 400065, China

According to the problem of high complexity of base station detection in large scale multiuser multiple input multiple output (MIMO) system, a low complexity multiuser variable node full information Gaussian message passing iterative detection algorithm based on forced convergence (VFI-GMPID-FC) was proposed. Firstly, the traditional Gaussian message passing iterative detection (GMPID) algorithm was improved to obtain VFI-GMPID algorithm, the detection performance of the VFI-GMPID algorithm approximates the minimum mean square error detection (MMSE) algorithm, but the complexity was considerably less than the MMSE algorithm. Then, the VFI-GMPID-FC algorithm was proposed to reduce the complexity of the algorithm and improve the detection efficiency. Finally, the simulation results show that the proposed algorithm can effectively reduce the algorithm complexity while ensuring the detection performance.

large scale multiuser MIMO, Gaussian message passing iterative detection, forced convergence, low complexity

TN911

：A

10.11959/j.issn.1000-0801.2017213

王琼（1971-），女，重庆邮电大学通信与信息工程学院正高级工程师、硕士生导师，主要研究方向为移动通信。

叶伟（1992-），男，重庆邮电大学通信与信息工程学院硕士生，主要研究方向为大规模MIMO系统中信号检测技术。

吉明明（1992-），男，重庆邮电大学通信与信息工程学院硕士生，主要研究方向为非正交多址接入技术。

2017-05-10；

：2017-06-29