基于動態因子圖更新率的SCMA檢測算法

賈志豪，孫 君

(南京郵電大學 通信與信息工程學院，江蘇 南京 210003)

0 引 言

隨著物聯網和移動互聯網技術的迅速發展，面對大規模機器通信的應用場景，在有限頻譜資源條件下，正交多址技術已經不能滿足種類繁多的物聯網業務和海量設備接入，有必要提出新型的多址技術。稀疏碼分多址(SCMA)作為一種重要的非正交多址技術，在相同資源映射配置以及系統負載條件下，相比于其他多址技術，能夠提供更好的鏈路性能。

SCMA上行鏈路系統傳輸過程中，發送端將編碼比特直接映射為復數多維碼字，多個用戶碼字在信道上疊加傳輸，接收端的信號檢測變得十分困難。最大后驗概率算法作為最優的檢測準則可以區分疊加的用戶信號，但是由于復雜度非常高，無法得到實際應用。消息傳遞算法(MPA)作為接近最優的SCMA多用戶檢測方案，利用碼字的稀疏特性，能夠接近MPA譯碼性能并且大幅度降低譯碼復雜度，但是隨著接入用戶數目的不斷增多，傳統的MPA算法仍然具有較高的計算復雜度。針對此問題，國內外專家學者們提出了一系列改進算法。文獻[6]提出了球形解碼的檢測算法，根據噪聲方差大小計算圓形半徑區域內的合成星座點(SCP)，舍去部分較遠的合成星座點，通過選擇合理的球形解碼半徑動態平衡系統誤碼率性能和計算復雜度。文獻[7-8]提出了基于部分邊緣化消息傳遞算法(PM-MPA)，迭代一定次數后確定部分用戶的碼字信息，以犧牲部分誤碼率為代價，降低了計算復雜度。文獻[9]提出了基于加權系數的MPA檢測算法，通過對合成星座點分配不同的權值系數，有效加快消息的收斂速度。文獻[10]提出了串行更新策略的算法(SMPA)，保證更新的消息能夠立即進入當前迭代，加快消息的收斂速度，降低了算法復雜度。文獻[11-12]中改進串行調度的MPA檢測方案，進一步加快了串行調度策略的收斂速度。文獻[13]通過刪支規則，將原始因子圖轉換為多個子圖并行迭代更新，降低了計算復雜度，但是需要針對不同的系統預先設定不同的子圖方案，系統性能較差。該文提出一種基于動態因子圖更新率的消息傳遞算法(DFT-MPA)，通過對因子圖不同分支上信息的收斂程度進行判斷，動態選擇收斂程度較高的分支不再參與后續迭代更新，減少了更新分支的數目，有效降低了計算復雜度。

1 系統模型

1.1 SCMA上行鏈路系統概述

SCMA上行鏈路通信系統如圖1所示，

J

個用戶共享

K

個資源塊，用戶發送的數據比特流被映射成

K

維碼字，每個碼字都為包含

N

個非零元素的

K

維稀疏向量，其中用戶數

J

大于時頻資源塊數

K

，系統過載率為

λ

=

J/K

。多路用戶信號經過同步后，基站端接收到的信號可以表示為：

(1)

其中，=(

x

1,,

x

2,,…,

x

,)表示碼字向量，=(

h

1,,

h

2,,…,

h

,)表示信道向量，

diag

()表示以向量為對角元素構造的矩陣，=(

n

1,,

n

2,,…,

n

,)表示高斯噪聲，且服從

N

(0,

σ

I

)分布。

圖1 SCMA上行鏈路系統框圖

SCMA系統中因子圖用來描述用戶和資源塊的連接關系，以

J

=6，

K

=4系統為例，因子圖分支連接資源節點(RN)與用戶節點(UN)，可以反映消息的迭代傳播過程，每個用戶節點連接2個資源節點，每個資源節點與3個用戶節點相連，連接關系如圖2所示。

圖2 SCMA系統因子圖

1.2 原始消息傳遞算法

原始消息傳遞算法(MPA)是一種置信度傳播算法，作為接近最優的SCMA多用戶檢測方案，用因子圖模型來回歸概率推理問題，消息在資源節點和用戶節點之間更新，經過多次迭代后，計算每個用戶碼字的概率信息。

在SCMA上行鏈路通信系統中，接收端MPA算法首先初始化先驗概率，然后對資源節點和用戶節點的消息值迭代更新，迭代過程分為兩步：資源節點到用戶節點消息的更新和用戶節點至資源節點消息的更新，更新過程相互依賴，達到設定最大迭代次數后，則根據多次迭代后的結果進行解碼判決。具體可分為以下三個步驟：

步驟1：初始化參數，假設每個用戶發送的碼字概率相等：

(2)

(3)

(4)

式中，表示碼字向量，

ξ

/j

表示除節點

j

以外所有與資源節點

k

相連的用戶節點集合，

ζ

/k

表示除節點

k

之外所有與用戶節點相連的資源節點集合。步驟3：當達到最大迭代次數

T

，計算每個用戶的碼字概率:

(5)

2 文中提出的算法

MPA算法消息沿著因子圖分支傳遞更新，在檢測過程中，存在部分因子圖分支上的碼字信息少量迭代后就不再變化，但是每次迭代仍然會更新所有分支的消息，產生了大量的冗余計算。針對上述問題，該文提出一種基于動態因子圖更新率的消息傳遞算法(DFT-MPA)，根據更新率衡量相鄰迭代因子圖分支上信息的變化程度，停止更新收斂程度較高的分支，動態調整因子圖結構，減少了迭代過程中更新分支的數目，可以有效降低計算復雜度。

對因子圖中連接資源節點和用戶節點的分支分類，所有分支集合劃分為兩類，更新集合|

B

(

t

)|和收斂集合|

B

(

t

)|，如式(7)所示。對應因子圖中在資源節點與用戶節點之間的連線分別為實線和虛線(見圖3)，實線表示資源節點和用戶節點之間的消息可以互相更新，虛線表示該分支只存在用戶節點對資源節點進行更新，但資源節點不再對用戶節點更新，在MPA算法初始迭代中|

B

(

t

)|=

Kd

，|

B

(

t

)|=0，分支集合之間的關系如(6)所示。|

B

(

t

)|+|

B

(

t

)|=

Kd

(6)

(7)

圖3 動態因子圖示意圖

(9)

(10)

算法具體步驟如下：

輸入：接收信號

y

，信道矩陣，噪聲功率

σ

，最大迭代次數

T

，門限值

T

輸出：用戶比特值LLR

while (

t

≤

T

)if(

t

=1)

end if

if(1<

t

≤

T

)

將滿足收斂條件的分支添加到收斂集合|

B

(

t

)|

end if

t

=

t

+1

end if

for

j

=1:

J

End for

3 仿真結果

本節在SCMA上行鏈路系統中進行仿真，比較分析了DFT-MPA、MPA和PM-MPA算法的BER性能，收斂速度和計算復雜度。具體仿真參數設置如表1所示。

表1 仿真參數設置

如圖4所示，仿真給出DFT-MPA算法隨著門限值大小變化的BER曲線。在固定SNR情況下，DFT-MPA算法的BER性能隨著門限值的增加呈下降趨勢，當門限值較小時，相比原始MPA算法的性能損失較少，當門限值較大時，BER性能損失較大。因此，DFT-MPA算法通過調整門限值能滿足不同的通信質量要求。

圖4 門限值與BER性能

3.1 BER性能對比

圖5為不同算法在6次迭代下的BER性能對比，其中PM-MPA算法的性能最差，PM-MPA算法隨機選擇部分用戶進行檢測，以犧牲性能為代價，一定程度上降低了復雜度，DFT-MPA算法在門限值為0.1的BER性能較好，相比原始MPA算法僅有0.1 dB的性能損失，門限值為0.3時，大約有0.6 dB的性能損失，門限值為0.5時，大約有0.8 dB的性能損失，其曲線接近于PM-MPA算法。DFT-MPA算法由于迭代過程中部分分支消息更新受損，導致BER性能的下降，可以通過調整門限值實現不同的BER性能，滿足不同通信場景需求。

圖5 不同算法BER性能對比

3.2 收斂速度對比

圖6為不同算法在SNR=13 dB下的收斂速度對比，其中PM-MPA和DFT-MPA算法在門限值為0.5和0.3下的收斂速度較快，3～4次迭代后達到收斂，DFT-MPA算法在門限值為0.1下，與原始MPA算法的收斂速度相同，5～6次迭代后收斂，隨著門限值的增加，算法的BER性能逐漸降低，但是收斂速度卻越來越快，算法可以調節門限值實現不同的收斂速率。

圖6 不同算法收斂速度對比

3.3 復雜度分析

表2 不同算法復雜度比較

圖7 不同算法復雜度對比

圖7為不同算法在SNR=8 dB下的復雜度對比，主要比較算法的乘法(Multiplication)和加法數目(Additon)。其中原始MPA算法乘法次數為32 256次，PM-MPA算法乘法次數為19 479次，DFT-MPA算法在門限值為0.1,0.3,0.5時，乘法次數分別為19 385次，15 676次，12 741次，分別相當于原始MPA算法復雜度的60.1%，48.6%，39.5%，DFT-MPA算法能夠通過調整門限值不同程度地降低復雜度。

4 結束語

針對MPA算法存在計算復雜度較高的問題，提出了一種基于動態因子圖更新率的消息傳遞算法(DFT-MPA)，利用更新率衡量迭代前后因子圖分支上信息的變化程度，選擇收斂程度高的分支加入到收斂集合中，停止該分支的消息更新，動態調整原始因子圖結構，當所有分支加入收斂集合或達到最大迭代次數，則完成迭代輸出譯碼，算法通過減少消息分支更新數目，降低計算復雜度。仿真結果表明，DFT-MPA算法能夠有效平衡復雜度與BER性能，滿足不同場景的性能需求。