杜　洋　董彬虹　王顯俊　黨冠斌　高鵬宇（電子科技大學(xué)通信抗干擾技術(shù)國(guó)家級(jí)重點(diǎn)實(shí)驗(yàn)室成都611731）

?

基于串行策略的SCMA多用戶檢測(cè)算法

杜洋*董彬虹王顯俊黨冠斌高鵬宇
（電子科技大學(xué)通信抗干擾技術(shù)國(guó)家級(jí)重點(diǎn)實(shí)驗(yàn)室成都611731）

稀疏碼多址接入（SCMA）作為一個(gè)前景廣闊的5 G無(wú)線空口技術(shù)，能夠滿足海量連接的需求。針對(duì)現(xiàn)有SCMA通信系統(tǒng)都是基于并行策略的消息傳遞算法（MPA）進(jìn)行多用戶檢測(cè)，存在信息收斂速度不理想的問(wèn)題，該文提出一種串行策略的多用戶檢測(cè)算法。該算法以資源節(jié)點(diǎn)為序，按串行方式依次進(jìn)行消息更新與傳遞，保證更新的消息能夠立即進(jìn)入當(dāng)前迭代過(guò)程，改善了消息傳遞的收斂速度，相比并行策略的多用戶檢測(cè)算法，降低了算法復(fù)雜度；同時(shí)，充分利用消息間相互關(guān)聯(lián)的特點(diǎn)，融合消息傳遞步驟，降低了存儲(chǔ)器的要求。理論與仿真結(jié)果表明，該算法在誤比特率（BER）性能與算法復(fù)雜度之間可以達(dá)到較理想的平衡。

稀疏碼多址接入；多用戶檢測(cè)；消息傳遞算法；串行策略

1　引言

目前，全球第4代（4G）移動(dòng)通信網(wǎng)絡(luò)建設(shè)方興未艾，面向2020年及未來(lái)的第5代（5G）移動(dòng)通信的研究已在全世界范圍內(nèi)開(kāi)啟［1］。與4G相比，5G需提供更高的頻譜效率以及更多的用戶連接數(shù)。為解決這些需求，5G就需要高效的多址接入技術(shù)，而這些多址接入技術(shù)正經(jīng)歷著從正交多址到非正交多址技術(shù)的演變［2，3］。

碼分多址接入（Code Division Multip le Access，CDMA）［4，5］是當(dāng)前以及未來(lái)物理層中一類極具潛力的空口技術(shù)。作為一種特殊的CDMA，低密度信號(hào)（Low Density Signature，LDS）的CDMA技術(shù)已經(jīng)被提出來(lái)，用以解決海量連接的系統(tǒng)過(guò)載情況［68］-。最近幾年，LDS-CDMA技術(shù)進(jìn)一步發(fā)展，將高維調(diào)制與稀疏擴(kuò)頻融合在一起，直接把比特?cái)?shù)據(jù)流映射為預(yù)先設(shè)定碼本里的復(fù)數(shù)域多維碼字，演進(jìn)為性能更好的稀疏碼多址接入（Sparse Code Multip leAccess，SCMA）技術(shù)［911］-。然而，SCMA要正式成為5G選用的空口技術(shù)，有兩個(gè)關(guān)鍵技術(shù)亟需解決，即性能優(yōu)異的稀疏碼本設(shè)計(jì)與高效的多用戶檢測(cè)。前者已經(jīng)作為一個(gè)優(yōu)化問(wèn)題在文獻(xiàn)［12］中進(jìn)行了次優(yōu)多階段設(shè)計(jì)。因此，本文研究重點(diǎn)是高效的多用戶檢測(cè)技術(shù)。

文獻(xiàn)［13，14］基于SCMA碼本的稀疏性，提出了一種基于消息傳遞算法（M essage Passing A lgorithm，MPA）［6，15］的次優(yōu)多用戶檢測(cè)算法，用以有效地接近聯(lián)合最優(yōu)的最大后驗(yàn)概率算法的性能。文獻(xiàn)［16］基于部分邊緣化的方法，提出了一種改進(jìn)的MPA多用戶檢測(cè)算法，在犧牲一定誤比特率（Bit Error Rate，BER）性能的條件下，算法復(fù)雜度得到降低。綜上所述，現(xiàn)有SCMA多用戶檢測(cè)算法的研究都是基于并行策略，即每輪迭代過(guò)程中，所有資源節(jié)點(diǎn)先同時(shí)進(jìn)行消息更新，然后所有用戶節(jié)點(diǎn)同時(shí)進(jìn)行消息更新。這種策略的多用戶檢測(cè)算法，更新的消息只能等到下輪迭代過(guò)程才能傳遞出去，消息傳遞的收斂性并非最佳，因此，并不一定是最優(yōu)算法。

針對(duì)上述問(wèn)題，本文基于SCMA因子圖中資源節(jié)點(diǎn)消息的串行更新，提出了一種高效的多用戶檢測(cè)算法。具體說(shuō)，本文算法不同于現(xiàn)有算法，每輪迭代過(guò)程中已更新的消息可以馬上得到傳遞，從而改進(jìn)了消息的收斂速度，提高了BER性能，降低了算法復(fù)雜度。除此之外，本文算法在迭代過(guò)程中把中間變量直接融入資源節(jié)點(diǎn)消息更新過(guò)程中，節(jié)省了部分存儲(chǔ)空間。理論分析與仿真結(jié)果表明，本文算法在BER性能與復(fù)雜度上提供一個(gè)較好的平衡。

本文內(nèi)容安排如下：第2節(jié)給出了SCMA系統(tǒng)模型；第3節(jié)詳細(xì)闡述了新提出的基于串行策略的多用戶檢測(cè)算法；第4節(jié)給出仿真驗(yàn)證結(jié)果；最后總結(jié)全文。

2　系統(tǒng)模型

2.1上行SCM A系統(tǒng)概述

假定一個(gè)上行多用戶SCMA通信系統(tǒng)，J個(gè)用戶共享K個(gè)正交時(shí)頻資源（J>K），并傳輸數(shù)據(jù)給同一個(gè)基站，其過(guò)載因子定義為λ=J/K 。6個(gè)用戶共享4個(gè)正交時(shí)頻資源的上行SCMA模型如圖1所示。SCMA編碼器定義為K維復(fù)數(shù)碼字x是具有N

假定全部用戶時(shí)間同步，基站接收到的信號(hào)為全部用戶信號(hào)疊加，可以表示為

圖1　上行SCMA通信系統(tǒng)模型（J=6，K=4，λ=150%）

圖2　 SCMA碼的因子圖及其矩陣

時(shí)頻資源k處接收到的信號(hào)為

由于碼字jx是稀疏的，所以在時(shí)頻資源k處僅有較少的碼字沖突。

MAP算法需要窮盡搜索所有的用戶以及各自碼本的可能組合，因此復(fù)雜度極高，且隨著用戶數(shù)J的增加而呈指數(shù)級(jí)增長(zhǎng)，這就限制了其在實(shí)際通信系統(tǒng)中的運(yùn)用。

2.2原始消息傳遞算法

置信度傳播算法是一種利用因子圖模型來(lái)求解概率推理問(wèn)題的有效技術(shù)，并且它非常適合于低密度的因子圖中進(jìn)行迭代運(yùn)算。因此，根據(jù)SCMA通信系統(tǒng)碼字的稀疏特性，基于置信度傳播算法的原則，提出一種次優(yōu)的基于碼字MPA多用戶檢測(cè)算法，即原始MPA算法。原始MPA算法將復(fù)雜的信號(hào)處理過(guò)程分解為多個(gè)相對(duì)簡(jiǎn)單的迭代步驟，各個(gè)步驟之間以信息概率為基礎(chǔ)，要求軟信息盡可能無(wú)損失地在因子圖上傳遞，每一次迭代過(guò)程包括兩個(gè)步驟（如圖3），即步驟1，同時(shí)更新因子圖中全部資源節(jié)點(diǎn)kc到用戶節(jié)點(diǎn)ju的消息步驟2，同時(shí)更新因子圖中所有用戶節(jié)點(diǎn)ju到資源節(jié)點(diǎn)kc的消息

原始MPA一次迭代過(guò)程中的兩個(gè)步驟可以分別用數(shù)學(xué)公式表示為

圖3　原始MPA算法一次迭代過(guò)程示意圖

式中，t為迭代次數(shù)，kξ與jζ分別表示稀疏矩陣F第k行的非零位置集與第j列的非零位置集。

原始MPA達(dá)到預(yù)先設(shè)定的最大迭代次數(shù)maxt后，每一個(gè)用戶各自的碼字輸出概率可以由式（6）估計(jì)。

3　本文提出的多用戶檢測(cè)算法

原始MPA是現(xiàn)階段SCMA通信系統(tǒng)普遍采用多用戶檢測(cè)算法，雖然它可以有效地接近MAP算法的性能，但不一定是最優(yōu)的算法。原始MPA的消息傳輸機(jī)制是采用并行策略，在每輪迭代過(guò)程中，所有的資源節(jié)點(diǎn)與用戶節(jié)點(diǎn)都是同時(shí)處理與傳遞消息。這在實(shí)際工程應(yīng)用中，不僅會(huì)占用大量的硬件資源，而且還需要大容量的存儲(chǔ)器保存中間變量。另外，原始MPA的消息傳遞的收斂性并非最佳，需要多次迭代才能正確檢測(cè)，故它有較大的檢測(cè)復(fù)雜度。

3.1基于串行策略的多用戶檢測(cè)算法

為了解決上述問(wèn)題，本節(jié)提出一種基于串行策略的MPA多用戶檢測(cè)算法，它能夠在BER性能與復(fù)雜度之間取得更好的平衡。本文算法對(duì)資源節(jié)點(diǎn)按照串行的方式進(jìn)行信息的更新，其一次迭代過(guò)程如圖4所示。這種處理方法保證了已更新的消息可以及時(shí)得到傳遞，而不像原始MPA那樣，更新的消息只能等到下輪迭代過(guò)程才能傳遞出去，從而改進(jìn)了消息的收斂特性。

圖4　本文算法一次迭代過(guò)程示意圖

綜合式（4）與式（9），可以得到基于串行策略的MPA多用戶檢測(cè)算法的資源節(jié)點(diǎn)消息更新公式為

基于串行策略的MPA多用戶檢測(cè)算法的具體過(guò)程如表1所示。

基于串行策略的MPA多用戶檢測(cè)算法在每輪迭代過(guò)程中，更新的消息馬上就可以傳遞給后面的節(jié)點(diǎn)，而不必等到下輪迭代過(guò)程。顯然，這種串行策略對(duì)消息的更新是異步的，并且越靠后處理的資源節(jié)點(diǎn)消息更新就越可靠。這樣平均下來(lái)，基于串行策略的MPA多用戶檢測(cè)算法進(jìn)行一次迭代相當(dāng)于原始MPA多次迭代的效果，改善了消息收斂特性。顯然，在較少迭代次數(shù)時(shí)，本文算法在BER性能上的優(yōu)勢(shì)更能得到體現(xiàn)。但由于本文算法的消息更新采用串行策略，所需迭代次數(shù)減少，每輪迭代所需時(shí)間卻增長(zhǎng)，即會(huì)產(chǎn)生一定程度的時(shí)延。

表1　基于串行策略的MPA多用戶檢測(cè)算法

3.2復(fù)雜度分析

SCMA多用戶檢測(cè)算法的復(fù)雜度主要體現(xiàn)在迭代過(guò)程與迭代次數(shù)。本文算法是通過(guò)收斂所需迭代次數(shù)的減少來(lái)降低計(jì)算復(fù)雜度。

本文復(fù)雜度將以算法中所涉及的乘法器數(shù)目為標(biāo)準(zhǔn)進(jìn)行分析，因此本文算法復(fù)雜度為

式中，fd表示作用于資源節(jié)點(diǎn)的用戶數(shù)。

同理，原始MPA與PM-based MPA的復(fù)雜度分別如式（12）與式（13）計(jì)算。

式中，vd表示作用于用戶節(jié)點(diǎn)的時(shí)頻資源數(shù)。

式中，m與sR表示PM-based MPA的指定參數(shù)。

4　仿真結(jié)果

為了驗(yàn)證本文所提基于串行策略的MPA多用戶檢測(cè)算法在上行SCMA通信系統(tǒng)的性能，分別將其與原始MPA以及PM-based MPA進(jìn)行了比較仿真實(shí)驗(yàn)。在仿真中，各參數(shù)設(shè)置如表2所示。

表2　仿真參數(shù)

4.1收斂速度

圖5為顯示了本文算法、原始MPA與PM-based MPA的收斂情況。由圖5可知，PM-based MPA的BER性能在相同迭代次數(shù)下，都遠(yuǎn)差于本文算法。同時(shí)，從圖5可以看出，本文算法在較小迭代次數(shù)（即1，2與3次）情況下，本文算法的BER性能明顯優(yōu)于原始MPA。這是因?yàn)楸疚乃惴梢粤⒓窗岩迅碌南鬟f給后面的節(jié)點(diǎn)，而不像原始MPA那樣必須等到下一輪迭代，這就使得本文算法可以更加充分地利用新鮮信息，從而收斂速度加快。從圖5也可以看出，隨著迭代次數(shù)的增加，本文算法與原始MPA在BER性能上的差距越來(lái)越小，并且最終達(dá)到穩(wěn)定，趨于相同值。這是因?yàn)閮煞N算法最終都能充分利用了已更新的消息。值得注意的是，本文算法2次迭代的BER性能幾乎可以無(wú)差別地達(dá)到其最佳性能，這說(shuō)明了本文算法的收斂性很快。

4.2 BER性能

圖6為顯示了本文算法、原始MPA與PM-based MPA的BER性能對(duì)比情況。從圖6可以看出，在相同迭代次數(shù)下，本文算法的BER性能都優(yōu)于原始MPA。在時(shí)，2次迭代原始MPA的BER值為而本文算法2次迭代的BER值為性能好了一個(gè)數(shù)量級(jí)。從圖6也可以看出，在時(shí)，相對(duì)于6次迭代的PM-based MPA，本文算法2次迭代就有0.7 dB增益。同時(shí)，我們可以由圖6得到，本文算法2次迭代的BER性能就優(yōu)于6次迭代的PM-based MPA，并且?guī)缀鯚o(wú)差別地達(dá)到原始MPA的6次迭代的性能。

4.3復(fù)雜度對(duì)比

結(jié)合3.2節(jié)的復(fù)雜度分析，可以得出4.2節(jié)中提及的2次迭代本文算法、6次迭代原始MPA以及6次迭代PM-based MPA的乘法器數(shù)目分別為10968，32256，26208。相對(duì)于原始MPA，本文算法在可忽略BER性能損失下，節(jié)約了66.0%的乘法器。同時(shí)，與PM-based MPA對(duì)比，本文算法不僅BER性能有較大增益，并且節(jié)約了58.2%的乘法器。因此，本文算法在BER性能與復(fù)雜度上提供了很好的平衡。

5　結(jié)束語(yǔ)

本文針對(duì)上行SCMA通信系統(tǒng)，以因子圖中的資源節(jié)點(diǎn)消息串行更新為基礎(chǔ)，提出了一種信息收斂速度快的多用戶檢測(cè)算法。相對(duì)于原始MPA與PM-based MPA，本文算法在算法復(fù)雜度明顯降低情況下，還能取得較理想的BER性能，并且節(jié)省了部分存儲(chǔ)空間。因此，本文算法是一種實(shí)用價(jià)值較高的上行SCMA多用戶檢測(cè)算法。

圖5　各種算法的收斂速度

圖6　各種算法的BER性能對(duì)比

［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］許耀華，胡艷軍.基于擬生態(tài)優(yōu)化算法的CDMA多用戶檢測(cè)方法［J］.電子與信息學(xué)報(bào)，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］王宇，李少謙，李樂(lè)民.多業(yè)務(wù)蜂窩CDMA系統(tǒng)的干擾與容量分析［J］.電子與信息學(xué)報(bào)，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，F(xiàn)REY 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年生，博士生，研究方向?yàn)槊嫦虻?代移動(dòng)通信的新型多址技術(shù)及無(wú)線通信抗干擾技術(shù).

董彬虹：女，1972年生，研究員，博士生導(dǎo)師，研究方向?yàn)闊o(wú)線通信關(guān)鍵技術(shù)研究.

王顯?。耗?，1993年生，碩士生，研究方向?yàn)槊嫦虻?代移動(dòng)通信的新型多址技術(shù).

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；網(wǎng)絡(luò)出版：2016-05-09

杜洋yangdu1988@gm ail.com

華為創(chuàng)新研究計(jì)劃（YB 2015040056），國(guó)家自然科學(xué)基金（61201126），新世紀(jì)優(yōu)秀人才支持計(jì)劃（NCET-11-0058），四川省青年科技基金（2012JQ 0020），國(guó)家級(jí)重點(diǎn)實(shí)驗(yàn)室基金（150C02006）