基于動態(tài)因子圖更新率的SCMA檢測算法

賈志豪，孫 君

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

0 引 言

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

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

1 系統模型

1.1 SCMA上行鏈路系統概述

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

J

個用戶共享

K

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

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系統為例，因子圖分支連接資源節(jié)點(RN)與用戶節(jié)點(UN)，可以反映消息的迭代傳播過程，每個用戶節(jié)點連接2個資源節(jié)點，每個資源節(jié)點與3個用戶節(jié)點相連，連接關系如圖2所示。

圖2 SCMA系統因子圖

1.2 原始消息傳遞算法

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

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

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

(2)

(3)

(4)

式中，表示碼字向量，

ξ

/j

表示除節(jié)點

j

以外所有與資源節(jié)點

k

相連的用戶節(jié)點集合，

ζ

/k

表示除節(jié)點

k

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

T

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

(5)

2 文中提出的算法

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

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

B

(

t

)|和收斂集合|

B

(

t

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

B

(

t

)|=

Kd

，|

B

(

t

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

B

(

t

)|+|

B

(

t

)|=

Kd

(6)

(7)

圖3 動態(tài)因子圖示意圖

(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 仿真結果

本節(jié)在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性能逐漸降低，但是收斂速度卻越來越快，算法可以調節(jié)門限值實現不同的收斂速率。

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