郝樹良，劉 海，范 彬，張新蘋，姚 穩(wěn)（重慶郵電大學(xué)，重慶400065）

1 概述

目前，4G移動通信建設(shè)方興未艾，5G移動通信研究已全面開啟［1］。與4G相比，5G需要提供更高的頻譜效率，支持更多的終端接入。為應(yīng)對這些需求，5G需要更先進的多址接入技術(shù)。稀疏碼分多址接入（SCMA）［2］技術(shù)作為非正交多址接入技術(shù)的候選方案之一，展現(xiàn)出了優(yōu)越的過載性能，為5G多址技術(shù)候選方案之一［3-4］。

SCMA是由低密度擴頻碼分（LDS——Low Density Spreading）［5-6］接入技術(shù)衍生而來。與 LDS 不同，SCMA編碼器是由正交振幅調(diào)制（QAM）映射器和符號級擴頻聯(lián)合而成，可以直接將用戶的數(shù)據(jù)比特映射為多維復(fù)域的碼字。SCMA系統(tǒng)采用精細設(shè)計的星座圖來獲得更高的整形與編碼增益，從而實現(xiàn)其系統(tǒng)性能增益要優(yōu)于LDS系統(tǒng)。SCMA要想成為未來5G選用的空口技術(shù)，有2個關(guān)鍵技術(shù)需要解決，一個是性能優(yōu)異的稀疏碼本設(shè)計，另一個是高效的多用戶檢測技術(shù)［7］。對于SCMA的碼本設(shè)計，文獻［8］已經(jīng)進行了次優(yōu)多階設(shè)計。本文重點討論接收端的多用戶檢測技術(shù)。

在接收端，SCMA系統(tǒng)采用的是具有較低復(fù)雜度的消息傳遞算法（MPA）［9］進行多用戶檢測。但是，在迭代次數(shù)過多，用戶量增大，以及系統(tǒng)對分集增益需求更高的場景下，MPA算法的復(fù)雜度會急劇增大。針對MPA算法復(fù)雜度較高的問題，文獻［10］提出了一種基于對數(shù)域的MPA，該算法在原始MPA算法的基礎(chǔ)上通過從指數(shù)域到對數(shù)域的轉(zhuǎn)換降低了一定的復(fù)雜度。文獻［11］基于部分邊緣化，提出了一種改進的MPA多用戶檢測算法，該算法在犧牲一定誤比特率（BER）性能的情況下，使得算法的復(fù)雜度得到降低。文獻［12-13］提出的次優(yōu)的MPA多用戶檢測算法，更有效地接近最大后驗算法（MAP）的性能。以上對于MPA算法的研究主要集中在每次迭代中的算法優(yōu)化，并且每個碼字的判決都需要經(jīng)過固定次數(shù)的迭代后才能進行。文獻［14］利用了在不同時隙的碼字收斂情況的不同，其需要的迭代次數(shù)也就不同，提出了一種基于避免冗余迭代的MPA檢測算法，該算法通過屏蔽冗余的迭代降低檢測復(fù)雜度。

本文提出了一種基于動態(tài)因子圖縮減的MPA（DFGR-MPA——Dynamic Factor Graph Reduction-MPA）檢測算法，該算法根據(jù)每個變量節(jié)點（VN——Variable Nodes）的碼字概率的收斂率把VN分為已完成迭代VN和未完成迭代的VN。定義碼字概率的收斂率為碼字當(dāng)前迭代概率和前一次迭代概率的差與前一次迭代概率的比值。已完成迭代的VN不再參與后續(xù)的迭代并從因子圖中除去，未完成迭代的VN與其相關(guān)功能節(jié)點（FN——Function Nodes）重構(gòu)成新的因子圖并完成后續(xù)迭代。這樣不僅避免了已完成迭代VN的冗余迭代，還降低了后續(xù)迭代檢測的復(fù)雜度。理論分析與仿真結(jié)果表明，DFGR-MPA檢測算法能夠保證在一定BER性能前提下實現(xiàn)一定程度復(fù)雜度的降低。

2 系統(tǒng)模型

SCMA系統(tǒng)的調(diào)制器可以定義為log2(M)個比特到K維復(fù)數(shù)域碼字的映射，其中M為碼本的維度，K為碼本中每個碼字向量的長度。所有的碼字向量都具有稀疏性，即每個碼字有N(N＜K)個非零元素。圖1為SCMA上行鏈路系統(tǒng)。該系統(tǒng)中，有J=6個用戶的數(shù)據(jù)流疊加在K=4個載波上，然后通過無線信道傳輸?shù)酵粋€基站上去，其負載率為150%（λ=J/K，通常情況下λ≥1）。

SCMA系統(tǒng)的接收端接收到所有用戶的疊加信號，可以表示為：

圖1 J個用戶、K個資源塊的SCMA上行鏈路系統(tǒng)

式中：

y——接收機接收的所有用戶的疊加信號，y=（y1，..，yK）T

xj——用戶 j的數(shù)據(jù)比特映射的碼字符號，xj=（x1，j，…，xK，j）T

hj——用戶j的信道向量，hj=（h1，j，…，hK，j）T

n——均值為0，方差為σ2的高斯噪聲向量，其中n=（n1，..，nK）T

第k個載波承載的接收信號yk可以用式（2）表示：

若該系統(tǒng)使用MAP算法需要遍歷所有用戶及其各自碼字的組合，因此復(fù)雜度非常高，且隨著用戶的增長呈指數(shù)型增長，因此SCMA系統(tǒng)并不采用MAP算法。由于SCMA系統(tǒng)碼本的稀疏特性，SCMA系統(tǒng)延續(xù)采用了LDS系統(tǒng)的MPA檢測算法。相比于MAP算法，MPA具有較低的檢測復(fù)雜度。

為了研究接收信號和每個用戶之間的關(guān)系，可以用因子圖矩陣F=(f1,...,fj)表示，其中 fj為用戶節(jié)點（變量節(jié)點）j的二進制指示向量。當(dāng)且僅當(dāng)Fk,j=1時，變量節(jié)點vj與功能節(jié)點fk相連。本文中用到的因子矩陣如式（3）所示。根據(jù)SCMA的碼本特點，多個用戶傳輸?shù)拇a字復(fù)用在同一資源塊上，并且多個資源塊上攜帶同一個用戶的碼字。因子圖可以對用戶與資源塊之間的關(guān)系進行更好地表示，此外，因子圖的引入為后續(xù)分析多用檢測算法提供方便。圖2為本文中用到的用戶與資源塊之間對應(yīng)關(guān)系的因子圖，該因子圖對應(yīng)的為文獻［15］公開的四維碼本。

圖2 SCMA系統(tǒng)的因子圖

3 多用戶檢測算法

3.1 原始MPA算法

3.1.1 原始MPA算法的詳細過程

MPA算法的核心思想是通過FN與VN的消息傳

步驟2：更新功能節(jié)點fk到變量節(jié)點vj傳遞的概率消息如式（4）所示。

步驟3：更新變量節(jié)點vj到功能節(jié)點fk的概率消息，如式（5）所示。

步驟4：當(dāng)?shù)螖?shù)達到預(yù)設(shè)的最大迭代次數(shù)Tmax后，每個用戶碼字的輸出概率可以用式（6）表示：

式（7）表示最后輸出軟判決信息，bxj,i=0表示變量節(jié)點vj第i個比特為0的碼字；LLRi,j表示變量節(jié)點vj第i個比特的軟判決輸出，其中1≤i≤log2M。

3.1.2 原始MPA算法存在問題

在原始MPA算法中，雖然設(shè)置了最大迭代次數(shù)Tmax，但是不同的用戶在不同時隙下需要的迭代次數(shù)并不相同。圖3所示為在原始MPA算法下，6個用戶在Eb/N0值為2 dB時的某個碼字概率的收斂情況對比，其中最大迭代次數(shù)Tmax的值為8。從圖3中可以看出，不同用戶具有不同的截止收斂點。用戶2在迭代次數(shù)t=2時已經(jīng)完成收斂，則剩余的Tmax-t=6次迭代被稱為冗余迭代；用戶1、3、4、5在迭代次數(shù)t=3時已經(jīng)完成了收斂，有5次冗余迭代；用戶6在迭代次數(shù)t=4時完成收斂，有4次冗余迭代。冗余迭代的存在是MPA檢測算法復(fù)雜度過高的原因之一。

圖3 MPA算法下6個用戶的碼字概率收斂對比

3.2 基于動態(tài)因子圖縮減的MPA

3.2.1 DFGR-MPA算法理論分析

DFGR-MPA針對原始MPA存在的不同VN存在不同冗余迭代問題進行了改進。DFGR-MPA在每次迭代結(jié)束前需要根據(jù)每個VN的碼字概率的收斂情況判斷該節(jié)點是否進行后續(xù)迭代，若部分VN已經(jīng)達到收斂則不再進行后續(xù)迭代，則剩余的VN需要繼續(xù)完成相同的過程直到達到迭代停止條件為止。DFGRMPA中用戶的碼字概率是否收斂是根據(jù)其所有碼字概率的收斂率wt(xj)為度量進行判定。若該值小于預(yù)先設(shè)定的閾值hD(0≤hD≤1)，則稱該用戶的碼字概率已經(jīng)達到目標(biāo)收斂。收斂率wt(xj)的定義如式（8）所示。

該過程可以理解為每次迭代結(jié)束后，都要對此次迭代前的因子圖進行縮減，剩余未達到目標(biāo)收斂的VN和其相關(guān)聯(lián)的邊重構(gòu)出一張只包括需要更新狀態(tài)節(jié)點的因子圖用來下次迭代。由于因子圖都是根據(jù)每個用戶節(jié)點的碼字概率收斂情況進行動態(tài)地縮減，所以該算法被稱為動態(tài)因子圖縮減MPA算法。

DFGR-MPA在迭代過程中通過動態(tài)地縮減因子圖的方法減少與迭代無關(guān)的FN和VN是一種降低復(fù)雜度的方式［13］。圖4更加直觀地表示了使用DFGRMPA算法迭代檢測的復(fù)雜度降低。假設(shè)變量節(jié)點v1和v3在T1次迭代后已經(jīng)完成概率的目標(biāo)收斂，則v1和v3不再進行后續(xù)迭代，那么與變量節(jié)點v1和v3以及其相關(guān)聯(lián)的邊（圖中用虛線表示）在因子圖中縮減出去，不再參與迭代；用戶v1和v3結(jié)束迭代后，功能節(jié)點f2的度由3降為1，f1和 f3的度有3降為2，這使得系統(tǒng)在T1+1次迭代時的復(fù)雜度大大降低。

圖4 DFGR-MPA算法的復(fù)雜度下降分析

基于動態(tài)因子圖縮減的MPA多用檢測算法具體過程如表1所示。其中Φt和Ψt為構(gòu)成第t次迭代時因子圖的FN和VN的集合。

3.2.2 復(fù)雜度分析

原始MPA算法需要計算出所有可能的信道系數(shù)與碼字組合，即hk,mxk,m的值，該運算需要涉及到2MKdf次加法和4MKdf次乘法；在FN的消息更新時，MPA的每個節(jié)點需要(2df+1)Mdf-1次加法，(df+2)Mdf-1次乘法以及Mdf-1次指數(shù)運算；在VN進行消息更新時，MPA的每個節(jié)點需要(dv-2)次加法。DFGR-MPA與原始MPA算法復(fù)雜度的不同之處主要在VN更新的環(huán)節(jié)，因為該環(huán)節(jié)需要計算出每次迭代的收斂率，對于每個VN來說，每次迭代需要額外的2M乘法以及M次比較算法。DFGR-MPA在不同的迭代中，其參與迭代的FN和VN的數(shù)目不同。表2為MPA和DFGR-MPA的復(fù)雜度對比，其中ADD、MUL、EXP以及CMP分別表示加法運算、乘法運算、指數(shù)運算和比較運算，df和dv分別表示原始MPA算法中作用于功能節(jié)點的變量節(jié)點數(shù)和作用于變量節(jié)點的功能數(shù)，dfk,t和dvj,t分別表示DFGR-MPA算法中第t次迭代中作用于功能節(jié)點k的變量節(jié)點數(shù)和作用于變量節(jié)點j的功能節(jié)點數(shù)表示DFGR-MPA算法在當(dāng)前時隙下迭代的最大次數(shù)。

表1 基于動態(tài)因子圖縮減的MPA多用戶檢測算法

表2 MPA和DFGR-MPA的復(fù)雜度

4 仿真結(jié)果

為了驗證本文所提出的基于動態(tài)因子圖縮減的DFGR-MPA算法具有良好的系統(tǒng)性能，將其與次優(yōu)的原始MPA算法進行比較仿真實驗。在仿真中，各參數(shù)設(shè)置如表3所示，使用的碼本為華為公司在文獻［15］公開的4維碼本。

表3 仿真參數(shù)

4.1 BER性能

圖5顯示的是本文算法DFGR-MPA與原始MPA算法的BER性能對比情況。從圖5中可以看出，DFGR-MPA的閾值hD越大，其BER性能就越差；DFGRMPA的hD為0.01的BER性能與迭代次數(shù)Tmax為5的原始MPA算法性能幾乎一致，在Eb/No的值為10 dB時，前者BER值為1.69×10-3，后者BER值為1.63×10-3，兩者BER性能差值為5×10-5；閾值hD為0.6的DFGRMPA算法的BER性能與迭代次數(shù)Tmax為3的原始MPA算法性能相近。

4.2 復(fù)雜度對比

圖6 為DFGR-MPA在不同Eb/No下的平均迭代次數(shù)。從圖6中得出，3個不同閾值下的DFGR-MPA的平均迭代次數(shù)都要比迭代次數(shù)Tmax為5次的原始MPA要低。DFGR-MPA的最低迭代次數(shù)可以達到2.6次。這恰恰說明了DFGR-MPA能夠通過降低迭代次數(shù)實現(xiàn)復(fù)雜度的降低。

在仿真過程中進行數(shù)據(jù)統(tǒng)計，并根據(jù)表2就能很容易得出DFGR-MPA與MPA的復(fù)雜度關(guān)系。為了更直觀地比較2種算法復(fù)雜度的關(guān)系，采用復(fù)雜度降低比（CCRR）來度量，其定義為式（9）。在上文中已經(jīng)提到，DFGR-MPA算法需要一定比較運算，由于該運算的復(fù)雜度較低，本文已將其忽略。圖7為DFGR-MPA與原始MPA的CCRR曲線。從圖7中可以看出，DFGR-MPA的CCRR值要比原始MPA高，其中閾值hD為0.60的DFGR-MPA最大CCRR值為58.5%，最低為23.0%。從圖5中得知，閾值hD為0.60的DFGR-MPA算法的BER性能和迭代次數(shù)Tmax為3的原始MPA近乎相同，但前者相比后者有較高的CCRR，這恰恰證明了DFGR-MPA降低復(fù)雜度的有效性。

圖6 DFGR-MPA在不同Eb/No下的平均迭代次數(shù)

圖7 DFGR-MPA相對于與原始MPA的CCRR

5 結(jié)論

本文SCMA上行鏈路系統(tǒng)，以現(xiàn)有的MPA檢測算法為基礎(chǔ)，提出了一種動態(tài)因子圖縮減的多用戶檢測算法，相比原始MPA，本文算法在算法復(fù)雜度明顯降低的情況下，還能獲得理想的BER性能。本文算法的思想不僅可以應(yīng)用到原始MPA算法上，還可以應(yīng)用到對數(shù)域MPA算法上，其復(fù)雜度的優(yōu)勢更佳。