基于串行策略的SCMA多用户检测算法

杜　洋　董彬虹　王显俊　党冠斌　高鹏宇（电子科技大学通信抗干扰技术国家级重点实验室成都611731）



基于串行策略的SCMA多用户检测算法

杜洋*董彬虹王显俊党冠斌高鹏宇
（电子科技大学通信抗干扰技术国家级重点实验室成都611731）

稀疏码多址接入（SCMA）作为一个前景广阔的5 G无线空口技术，能够满足海量连接的需求。针对现有SCMA通信系统都是基于并行策略的消息传递算法（MPA）进行多用户检测，存在信息收敛速度不理想的问题，该文提出一种串行策略的多用户检测算法。该算法以资源节点为序，按串行方式依次进行消息更新与传递，保证更新的消息能够立即进入当前迭代过程，改善了消息传递的收敛速度，相比并行策略的多用户检测算法，降低了算法复杂度；同时，充分利用消息间相互关联的特点，融合消息传递步骤，降低了存储器的要求。理论与仿真结果表明，该算法在误比特率（BER）性能与算法复杂度之间可以达到较理想的平衡。

稀疏码多址接入；多用户检测；消息传递算法；串行策略

1　引言

目前，全球第4代（4G）移动通信网络建设方兴未艾，面向2020年及未来的第5代（5G）移动通信的研究已在全世界范围内开启［1］。与4G相比，5G需提供更高的频谱效率以及更多的用户连接数。为解决这些需求，5G就需要高效的多址接入技术，而这些多址接入技术正经历着从正交多址到非正交多址技术的演变［2，3］。

码分多址接入（Code Division Multip le Access，CDMA）［4，5］是当前以及未来物理层中一类极具潜力的空口技术。作为一种特殊的CDMA，低密度信号（Low Density Signature，LDS）的CDMA技术已经被提出来，用以解决海量连接的系统过载情况［68］-。最近几年，LDS-CDMA技术进一步发展，将高维调制与稀疏扩频融合在一起，直接把比特数据流映射为预先设定码本里的复数域多维码字，演进为性能更好的稀疏码多址接入（Sparse Code Multip leAccess，SCMA）技术［911］-。然而，SCMA要正式成为5G选用的空口技术，有两个关键技术亟需解决，即性能优异的稀疏码本设计与高效的多用户检测。前者已经作为一个优化问题在文献［12］中进行了次优多阶段设计。因此，本文研究重点是高效的多用户检测技术。

文献［13，14］基于SCMA码本的稀疏性，提出了一种基于消息传递算法（M essage Passing A lgorithm，MPA）［6，15］的次优多用户检测算法，用以有效地接近联合最优的最大后验概率算法的性能。文献［16］基于部分边缘化的方法，提出了一种改进的MPA多用户检测算法，在牺牲一定误比特率（Bit Error Rate，BER）性能的条件下，算法复杂度得到降低。综上所述，现有SCMA多用户检测算法的研究都是基于并行策略，即每轮迭代过程中，所有资源节点先同时进行消息更新，然后所有用户节点同时进行消息更新。这种策略的多用户检测算法，更新的消息只能等到下轮迭代过程才能传递出去，消息传递的收敛性并非最佳，因此，并不一定是最优算法。

针对上述问题，本文基于SCMA因子图中资源节点消息的串行更新，提出了一种高效的多用户检测算法。具体说，本文算法不同于现有算法，每轮迭代过程中已更新的消息可以马上得到传递，从而改进了消息的收敛速度，提高了BER性能，降低了算法复杂度。除此之外，本文算法在迭代过程中把中间变量直接融入资源节点消息更新过程中，节省了部分存储空间。理论分析与仿真结果表明，本文算法在BER性能与复杂度上提供一个较好的平衡。

本文内容安排如下：第2节给出了SCMA系统模型；第3节详细阐述了新提出的基于串行策略的多用户检测算法；第4节给出仿真验证结果；最后总结全文。

2　系统模型

2.1上行SCM A系统概述

假定一个上行多用户SCMA通信系统，J个用户共享K个正交时频资源（J>K），并传输数据给同一个基站，其过载因子定义为λ=J/K 。6个用户共享4个正交时频资源的上行SCMA模型如图1所示。SCMA编码器定义为K维复数码字x是具有N

假定全部用户时间同步，基站接收到的信号为全部用户信号叠加，可以表示为

图1　上行SCMA通信系统模型（J=6，K=4，λ=150%）

图2　 SCMA码的因子图及其矩阵

时频资源k处接收到的信号为

由于码字jx是稀疏的，所以在时频资源k处仅有较少的码字冲突。

MAP算法需要穷尽搜索所有的用户以及各自码本的可能组合，因此复杂度极高，且随着用户数J的增加而呈指数级增长，这就限制了其在实际通信系统中的运用。

2.2原始消息传递算法

置信度传播算法是一种利用因子图模型来求解概率推理问题的有效技术，并且它非常适合于低密度的因子图中进行迭代运算。因此，根据SCMA通信系统码字的稀疏特性，基于置信度传播算法的原则，提出一种次优的基于码字MPA多用户检测算法，即原始MPA算法。原始MPA算法将复杂的信号处理过程分解为多个相对简单的迭代步骤，各个步骤之间以信息概率为基础，要求软信息尽可能无损失地在因子图上传递，每一次迭代过程包括两个步骤（如图3），即步骤1，同时更新因子图中全部资源节点kc到用户节点ju的消息步骤2，同时更新因子图中所有用户节点ju到资源节点kc的消息

原始MPA一次迭代过程中的两个步骤可以分别用数学公式表示为

图3　原始MPA算法一次迭代过程示意图

式中，t为迭代次数，kξ与jζ分别表示稀疏矩阵F第k行的非零位置集与第j列的非零位置集。

原始MPA达到预先设定的最大迭代次数maxt后，每一个用户各自的码字输出概率可以由式（6）估计。

3　本文提出的多用户检测算法

原始MPA是现阶段SCMA通信系统普遍采用多用户检测算法，虽然它可以有效地接近MAP算法的性能，但不一定是最优的算法。原始MPA的消息传输机制是采用并行策略，在每轮迭代过程中，所有的资源节点与用户节点都是同时处理与传递消息。这在实际工程应用中，不仅会占用大量的硬件资源，而且还需要大容量的存储器保存中间变量。另外，原始MPA的消息传递的收敛性并非最佳，需要多次迭代才能正确检测，故它有较大的检测复杂度。

3.1基于串行策略的多用户检测算法

为了解决上述问题，本节提出一种基于串行策略的MPA多用户检测算法，它能够在BER性能与复杂度之间取得更好的平衡。本文算法对资源节点按照串行的方式进行信息的更新，其一次迭代过程如图4所示。这种处理方法保证了已更新的消息可以及时得到传递，而不像原始MPA那样，更新的消息只能等到下轮迭代过程才能传递出去，从而改进了消息的收敛特性。

图4　本文算法一次迭代过程示意图

综合式（4）与式（9），可以得到基于串行策略的MPA多用户检测算法的资源节点消息更新公式为

基于串行策略的MPA多用户检测算法的具体过程如表1所示。

基于串行策略的MPA多用户检测算法在每轮迭代过程中，更新的消息马上就可以传递给后面的节点，而不必等到下轮迭代过程。显然，这种串行策略对消息的更新是异步的，并且越靠后处理的资源节点消息更新就越可靠。这样平均下来，基于串行策略的MPA多用户检测算法进行一次迭代相当于原始MPA多次迭代的效果，改善了消息收敛特性。显然，在较少迭代次数时，本文算法在BER性能上的优势更能得到体现。但由于本文算法的消息更新采用串行策略，所需迭代次数减少，每轮迭代所需时间却增长，即会产生一定程度的时延。

表1　基于串行策略的MPA多用户检测算法

3.2复杂度分析

SCMA多用户检测算法的复杂度主要体现在迭代过程与迭代次数。本文算法是通过收敛所需迭代次数的减少来降低计算复杂度。

本文复杂度将以算法中所涉及的乘法器数目为标准进行分析，因此本文算法复杂度为

式中，fd表示作用于资源节点的用户数。

同理，原始MPA与PM-based MPA的复杂度分别如式（12）与式（13）计算。

式中，vd表示作用于用户节点的时频资源数。

式中，m与sR表示PM-based MPA的指定参数。

4　仿真结果

为了验证本文所提基于串行策略的MPA多用户检测算法在上行SCMA通信系统的性能，分别将其与原始MPA以及PM-based MPA进行了比较仿真实验。在仿真中，各参数设置如表2所示。

表2　仿真参数

4.1收敛速度

图5为显示了本文算法、原始MPA与PM-based MPA的收敛情况。由图5可知，PM-based MPA的BER性能在相同迭代次数下，都远差于本文算法。同时，从图5可以看出，本文算法在较小迭代次数（即1，2与3次）情况下，本文算法的BER性能明显优于原始MPA。这是因为本文算法可以立即把已更新的消息传递给后面的节点，而不像原始MPA那样必须等到下一轮迭代，这就使得本文算法可以更加充分地利用新鲜信息，从而收敛速度加快。从图5也可以看出，随着迭代次数的增加，本文算法与原始MPA在BER性能上的差距越来越小，并且最终达到稳定，趋于相同值。这是因为两种算法最终都能充分利用了已更新的消息。值得注意的是，本文算法2次迭代的BER性能几乎可以无差别地达到其最佳性能，这说明了本文算法的收敛性很快。

4.2 BER性能

图6为显示了本文算法、原始MPA与PM-based MPA的BER性能对比情况。从图6可以看出，在相同迭代次数下，本文算法的BER性能都优于原始MPA。在时，2次迭代原始MPA的BER值为而本文算法2次迭代的BER值为性能好了一个数量级。从图6也可以看出，在时，相对于6次迭代的PM-based MPA，本文算法2次迭代就有0.7 dB增益。同时，我们可以由图6得到，本文算法2次迭代的BER性能就优于6次迭代的PM-based MPA，并且几乎无差别地达到原始MPA的6次迭代的性能。

4.3复杂度对比

结合3.2节的复杂度分析，可以得出4.2节中提及的2次迭代本文算法、6次迭代原始MPA以及6次迭代PM-based MPA的乘法器数目分别为10968，32256，26208。相对于原始MPA，本文算法在可忽略BER性能损失下，节约了66.0%的乘法器。同时，与PM-based MPA对比，本文算法不仅BER性能有较大增益，并且节约了58.2%的乘法器。因此，本文算法在BER性能与复杂度上提供了很好的平衡。

5　结束语

本文针对上行SCMA通信系统，以因子图中的资源节点消息串行更新为基础，提出了一种信息收敛速度快的多用户检测算法。相对于原始MPA与PM-based MPA，本文算法在算法复杂度明显降低情况下，还能取得较理想的BER性能，并且节省了部分存储空间。因此，本文算法是一种实用价值较高的上行SCMA多用户检测算法。

图5　各种算法的收敛速度

图6　各种算法的BER性能对比

［1］THOMPSON J，GE X，WU H C，et al.5 G w ireless comm un ication systems:prospects and challenges［J］.IEEE Commun ications M agazine，2014，52（2）:62-64.doi:10.1109/ MCOM.2014.6815889.

［2］WANG P，XIAO J，and LIP.Com parison of orthogonal and nonorthogonal approaches to futurew ireless cellular system s［J］.IEEE Vehicular Technology Magazine，2006，52（3）:4-11. doi:10.1109/MVT.2006.307294.

［3］DA I L L，WANG B C，YUAN Y F，et al.Non-orthogonal m ultip le access for 5 G:solutions，challenges，opportun ities，and future research trends［J］.IEEE Communications Magazine，2015，53（9）:74-81.doi:10.1109/MCOM.2015. 7263349.

［4］许耀华，胡艳军.基于拟生态优化算法的CDMA多用户检测方法［J］.电子与信息学报，2006，28（11）:2111-2115.

XU Y H and HU Y J.Research of ecologic system optim ization algorithm s for multi-user detection in CDMA communication system s［J］.Journal of Electronics& Information Technology，2006，28（11）:2111-2115.

［5］王宇，李少谦，李乐民.多业务蜂窝CDMA系统的干扰与容量分析［J］.电子与信息学报，2002，24（12）:1785-1792.

WANG Y，LI S Q，and LI L M.Interference and capacity analysis for multi-service cellular CDMA system s［J］.Journal of Electronics&Information Technology，2002，24（12）: 1785-1792.

［6］HOSHYAR R，WATHAN F P，and TAFAZOLLI R.Novel low-density signature for synchronous CDMA system s over AWGN channel［J］.IEEE Transactions on Signal Processing，2008，56（4）:1616-1626.doi:10.1109/TSP.2007.909320.

［7］BEEK J V D and BALIGH B M.Multiple access w ith lowdensity signatures［C］.IEEE Global Telecommunications Conference，Honolulu，USA，2009:1-6.doi:10.1109/ GLOCOM.2009.5425243.

［8］RAZAVIR，HOSHYAR R，IMRAN M A，et al.Inform ation theoretic analysis of LDS scheme［J］.IEEE Communications Letters，2011，15（8）:798-800.doi:10.1109/LCOMM.2011. 061011.102098.

［9］NIKOPOUR H and BALIGH H.Sparse codem ultip le access［C］.IEEE Personal Indoor and Mobile Radio Communications，London，UK，2013:332-336.doi:10.1109/ PIMRC.2013.6666156.

［10］ZHANG S Q，XU X Q，LU L，et al.Sparse code m ultip le access:an energy efficient uplink app roach for 5 G w ireless systems［C］.IEEE Global Telecommunications Con ference，Austin，USA，2014:4782-4787.doi:10.1109/GLOCOM.2014. 7037563.

［11］AU K，ZHANG L Q，N IKOPOUR H，et al.Up link contention based SCMA for 5 G radio system s［C］.IEEE G lobal Telecommunications Con ference Workshops，Austin，USA，2014:900-905.doi:10.1109/GLOCOMW.2014.7063547.

［12］TAHERZADEH M，NIKOPOUR H，BAYESTECH A，et al. SCMA codebook design［C］.IEEE Vehicular Technology Conference Fall，Vancouver，CAN，2014:14-17.doi: 10.1109/VTCFall.2014.6966170.

［13］WANG B，WANG K，LU Z，et al.Com parison study of nonorthogonal multiple access schemes for 5 G［C］.IEEE Broadband Multimedia System s and Broadcasting，Ghent，BEL，2015:1-5.doi:10.1109/BMSB.2015.7177186.

［14］WU Y，ZHANG S，and CHEN Y.Iterativem ultiuser receiver in sparse code multip le access［C］.IEEE International Conference on Communications，London，UK，2015: 2918-2923.doi:10.1109/ICC.2015.7248770.

［15］KSCHISCHANG F，FREY B，and LOELIGER H.Factor graphs and the sum-product algorithm［J］.IEEE Transactions on Inform ation Theory，2001，47（2）:498-519.doi:10.1109/ 18.910572.

［16］MU H，MA Z，ALHAJI M，et al.A fixed low com plexity message pass detector for up-link SCMA system［J］.IEEE W ireless Communications Letters，2015，4（6）:585-588.doi: 10.1109/LWC.2015.2469668.

杜洋：男，1988年生，博士生，研究方向为面向第5代移动通信的新型多址技术及无线通信抗干扰技术.

董彬虹：女，1972年生，研究员，博士生导师，研究方向为无线通信关键技术研究.

王显俊：男，1993年生，硕士生，研究方向为面向第5代移动通信的新型多址技术.

Multiuser Detection Scheme for SCMA System s Based on Serial Strategy

DU Yang DONG Binhong WANG X ian jun DANG Guanbin GAO Pengyu
（National Key Laboratory ofScience and Technology on Communications，University ofElectronic Science and Techno logy of China，Chengdu 611731，China）

Sparse Code Mu ltip le Access（SCMA）is a p rom ising air-interface technology for 5 G w ireless communication networks，which can enab le massive connectivity.The existing mu ltiuser detection schemes are based on a parallelmessage updating for Message Passing A lgorithm（MPA），thus it is not efficient in term s of convergence.In this paper，an efficient mu ltiuser detection scheme for uplink SCMA is p roposed based on serial updating of function nodes，m essages.Com pared to the existing detection schemes，the p roposed scheme accelerates the convergence due to that the updated m essages can join the belief propagation imm ed iately in current iteration，which avoids being used in the next iteration.Furthermore，the p roposed scheme can reduce the storage burden，which fusesmessage passing p rocess on the basis of the relationship between messages.Numerical results show that the p roposed scheme can offer a good trade-off between comp lexity and Bit Error Rate（BER）performance.

Sparse Code M u ltip le Access（SCM A）；M u ltiuser detection；M essage Passing A lgorithm（M PA）；Serial updating

s:Huawei H IRP P roject（YB 2015040056），The National Natural Science Foundation of China（61201126），New Century Excellent Talents in University（NCET-11-0058），Sichuan Youth Science and Technology Fund（2012JQ 0020），Open Research Fund of the National Laboratory（150C02006）

TN 929.5

A

1009-5896（2016）08-1888-06

10.11999/JEIT 151259

2015-11-09；改回日期：2016-03-28；网络出版：2016-05-09

杜洋yangdu1988@gm ail.com

华为创新研究计划（YB 2015040056），国家自然科学基金（61201126），新世纪优秀人才支持计划（NCET-11-0058），四川省青年科技基金（2012JQ 0020），国家级重点实验室基金（150C02006）