基于串行策略的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）