動(dòng)態(tài)選擇消息更新的SCMA多用戶檢測(cè)算法

謝 歡 胡艷軍 蔣 芳

(安徽大學(xué)計(jì)算智能與信號(hào)處理教育部重點(diǎn)實(shí)驗(yàn)室，安徽合肥 230039)

1 引言

第五代移動(dòng)通信(5G)[1]被提出以滿足更高的業(yè)務(wù)要求，非正交多址技術(shù)(Non-orthogonal Multiple Access，NOMA)[2]頻譜效率較高，因此成為5G的一個(gè)備選方案。作為NOMA技術(shù)的一種，從低密度信號(hào)(Low Density Signature，LDS)[3]發(fā)展來的稀疏碼多址接入(Sparse Code Multiple Access，SCMA)[4]技術(shù)，可利用碼字的稀疏性得到較高的接入量。因?yàn)榻邮盏氖歉饔脩舸a的疊加信號(hào)，所以要進(jìn)行多用戶檢測(cè)。由于碼字是稀疏的，因此可用消息傳遞算法(Message Passing Algorithm，MPA)[5]進(jìn)行檢測(cè)。

但MPA的高計(jì)算復(fù)雜度限制了SCMA技術(shù)的實(shí)際應(yīng)用。影響復(fù)雜度的因素有算法的迭代次數(shù)、碼本大小、系統(tǒng)因子圖中的分支數(shù)等。文獻(xiàn)[6]通過簡化星座圖來減小碼本大小。文獻(xiàn)[7- 8]在每次迭代中將節(jié)點(diǎn)消息的更新順序重新編排，越靠后更新的節(jié)點(diǎn)消息越有效，因此減少了迭代次數(shù)。文獻(xiàn)[9-10]根據(jù)信道條件差異，將信道條件差的分支近似為高斯噪聲，同時(shí)添加反饋機(jī)制來彌補(bǔ)性能的下降，通過減少分支來降低復(fù)雜度。文獻(xiàn)[11]提出了一種基于動(dòng)態(tài)因子圖的MPA檢測(cè)器，因子圖中置信度較高的分支從當(dāng)前迭代開始將不參與消息傳遞。文獻(xiàn)[12]提出了一種部分邊緣化的MPA(Partial Marginalization-Message Passing Algorithm，PM-MPA)，迭代結(jié)束前將部分用戶數(shù)據(jù)先解出來，在后續(xù)迭代中再解出剩余用戶數(shù)據(jù)，犧牲了一部分性能的同時(shí)帶來了復(fù)雜度下降的收益。

以上文獻(xiàn)中算法的節(jié)點(diǎn)更新方法基本一致，各節(jié)點(diǎn)將其概率分布狀態(tài)傳遞給相鄰節(jié)點(diǎn)，從而改變相鄰節(jié)點(diǎn)的概率分布狀態(tài)。所有節(jié)點(diǎn)消息更新后，進(jìn)入下一輪節(jié)點(diǎn)消息更新。當(dāng)所有節(jié)點(diǎn)的碼字消息概率收斂后迭代結(jié)束，接著進(jìn)行軟解碼。因?yàn)槊看蔚滤写a字消息，所以復(fù)雜度較高。基于實(shí)驗(yàn)的研究發(fā)現(xiàn)，一些節(jié)點(diǎn)比其他節(jié)點(diǎn)收斂快[8]，意味著各碼字消息的收斂速度不同。針對(duì)這一特點(diǎn)，為降低算法復(fù)雜度，本文提出了一種動(dòng)態(tài)選擇消息更新的檢測(cè)算法DSM-MPA(Dynamically Select Message-Message Passing Algorithm，DSM-MPA)。不同于文獻(xiàn)[8]，本文算法在單次迭代中，不再更新因子圖中的所有節(jié)點(diǎn)消息，只選擇更新收斂較慢的節(jié)點(diǎn)消息，通過減少消息更新次數(shù)來降低算法復(fù)雜度。消息若收斂快，則其概率變化量小而接近收斂值，可直接用于軟解碼。仿真結(jié)果表明，選擇合適的比重因子，相比較于原始MPA，本文算法的復(fù)雜度明顯下降，同時(shí)誤比特率(Bit Error Rate，BER)性能基本不變。在實(shí)際應(yīng)用中可降低上行鏈路接收機(jī)設(shè)計(jì)復(fù)雜度，同時(shí)保證性能。

本文其余部分安排如下：第2節(jié)簡述SCMA系統(tǒng)模型及MPA算法；第3節(jié)給出本文的改進(jìn)算法；第4節(jié)對(duì)仿真結(jié)果進(jìn)行性能比較分析；最后第5節(jié)給出結(jié)論。

2 系統(tǒng)模型

2.1 SCMA系統(tǒng)模型

假定有J個(gè)用戶共享K個(gè)資源塊(J>K)，則該系統(tǒng)的過載系數(shù)定義為λ=J/K。對(duì)于每個(gè)用戶j，其比特?cái)?shù)據(jù)與此用戶碼本χj中的SCMA碼一一對(duì)應(yīng)，χ的維度是K。碼本中的SCMA碼表示為xj。K維SCMA碼中非零元素個(gè)數(shù)為N，N

接收信號(hào)可寫為：

(1)

其中，xj=[x1jx2j...xKj]T為用戶j的SCMA碼，hj=[h1jh2j...hKj]T為用戶j的信道條件向量，n是高斯白噪聲，n～CN(0,σ2I)，y=[y1y2...yK]T是接收端從K個(gè)資源塊中檢測(cè)到的信號(hào)。

由接收信號(hào)y和信道條件H=[h1h2...hJ]T，就可通過最大后驗(yàn)概率估計(jì)算法(Maximum A Posteriori, MAP)來檢測(cè)用戶數(shù)據(jù)X=[x1x2...xJ]，如式(2)：

(2)

2.2 原始MPA

圖1 SCMA系統(tǒng)模型Fig.1 Model of SCMA system

(3)

(4)

其中，t表示第t次迭代，ξk是與資源塊k連接的用戶序號(hào)集合，ζj是用戶j所占用的資源塊序號(hào)集合，xjm∈[xj1xj2...xjM]T為用戶j碼本中第m個(gè)碼字。yk為資源塊k上檢測(cè)的信號(hào)，σ是噪聲的標(biāo)準(zhǔn)差，hk,p和xk,p分別是資源塊k與用戶間的信道條件向量和用戶碼。

圖2 MPA算法示意圖，實(shí)線表示來自其他邊緣的先驗(yàn)概率，虛線表示邊緣上消息的更新Fig.2 Scheme diagram of MPA. The solid line indicates the prior probability from other edges. The dashed line indicates the update of the message at the edge

MPA達(dá)到最大迭代次數(shù)T后，各用戶碼字xjm出現(xiàn)的概率Q(xjm)用式(5)來計(jì)算：

(5)

3 本文提出的算法

原始MPA迭代更新所有碼字消息，直到每個(gè)碼字消息收斂。所以，MPA算法復(fù)雜度較高。實(shí)際上，有些碼字消息可以更快地接近收斂值，對(duì)這些消息繼續(xù)更新，所得的概率值變化量小。因此，可以有選擇地更新收斂較慢的消息，提前結(jié)束更新收斂快的消息。因?yàn)橥顺龈碌南⒁呀咏諗?，所以可直接用于軟解碼。在保持性能的同時(shí)，通過減少消息更新次數(shù)來降低計(jì)算復(fù)雜度。

3.1 動(dòng)態(tài)選擇消息更新的MPA

針對(duì)以上問題，本文提出了一種動(dòng)態(tài)選擇消息更新的MPA。在保持BER性能與原始MPA基本相同的情況下，可明顯降低算法復(fù)雜度。

算法基本思想是：第一次迭代更新所有碼字消息；從第二次迭代開始，對(duì)參與此次迭代的消息，用式(6)來計(jì)算迭代前后消息的差值Dt(xjm)：

(6)

若差值小，則表明此消息的變化量較小，收斂速度較快。將所有Dt(xjm)值按大小排序，選出差值最小的Nit個(gè)碼字消息。這Nit個(gè)碼字消息將被判為收斂最快，在后續(xù)迭代中將不更新。定義R為比重因子，被判為差值最小的消息數(shù)Nit，用式(7)來計(jì)算：

Nit=R·Nat

(7)

(8)

(9)

(10)

算法過程如表1。

表1 動(dòng)態(tài)選擇消息更新的MPA算法

續(xù)表1

3.2 復(fù)雜度分析

本文算法與原始MPA[9]以及PM-MPA[12](m和Rs是算法中的參數(shù))可用表2來比較復(fù)雜度，以算法執(zhí)行的加法和乘法次數(shù)為衡量標(biāo)準(zhǔn)。

4 仿真結(jié)果與分析

為了驗(yàn)證本文算法在上行SCMA無線通信系統(tǒng)中的性能，將本文算法與原始MPA以及PM-MPA進(jìn)行了仿真比較實(shí)驗(yàn)。仿真參數(shù)如表3所示。

表2 復(fù)雜度比較

表3 仿真參數(shù)

4.1 性能分析

在圖3中，最上面的五條曲線是原始MPA，PM-MPA(m=3，Rs=2)以及本文算法(前兩者算法曲線用實(shí)線表示，本文算法用虛線表示)在Eb/N0取8dB時(shí)的收斂情況；最下面五條曲線是各算法在Eb/N0取10dB時(shí)的收斂情況。本文算法取R=0.2和0.3時(shí)，收斂性與原始MPA和PM-MPA一致，迭代6次后收斂。本文算法R取0.4時(shí)，3次迭代后大多消息已不再更新，因此相比于原始MPA會(huì)提前收斂。但R取值比較大時(shí)，判為收斂快的消息中有很多未達(dá)到收斂條件。提前停止更新這些消息，會(huì)使后面軟解碼誤差較大，造成BER性能大幅下降。由圖3、圖4可知，當(dāng)信道條件較差(Eb/N0≤8dB)，噪聲對(duì)消息傳遞的干擾較大，為保證BER性能，R取值應(yīng)該小(R<=0.2)；當(dāng)信道條件較好(Eb/N0≥8dB)時(shí)噪聲小，對(duì)消息傳遞的干擾小，少數(shù)迭代后趨于收斂的消息多，所以R可取較大值(R>=0.2)。但為保障BER性能，R取值應(yīng)小于0.3。

圖3 各算法收斂速度Fig.3 Convergence rate of various algorithm

比重因子R取值若越小(R<=0.2)，對(duì)于迭代中被判為收斂快的消息，其前后迭代的差值就越小。因此，這些消息的概率分布也更容易趨于穩(wěn)態(tài)。這些不更新的消息越接近收斂，其他消息更新得到的收斂值與原始MPA的就更接近。因此，圖4中本文算法BER性能會(huì)與原始MPA更接近。反之，R取值越大(R>=0.2)，收斂快的消息中不滿足收斂條件的就越多。停止更新這些消息會(huì)使其他消息難以收斂到原始MPA的值，消息可靠性就越低，BER性能將越差。

圖4 各算法性能Fig.4 Performance of various algorithm

圖4中各算法迭代次數(shù)都為T=6。在BER=1.0×10-3時(shí)，取R=0.2，每次迭代中被判為收斂快的消息數(shù)較少。前面提到，R取值越小(R<=0.2)，這些消息的概率分布更接近穩(wěn)態(tài)，可直接傳遞給其他消息的后續(xù)更新，對(duì)其他消息收斂到原穩(wěn)定值影響小。因此，所有消息的最終概率分布接近于原始MPA。所以，此時(shí)本文算法BER性能基本和原始MPA一致；和PM-MPA算法相比，本文算法有0.5dB左右的增益。因?yàn)镻M-MPA是直接提前解特定用戶的數(shù)據(jù)，此用戶消息可能依然與穩(wěn)定值相差較遠(yuǎn)，已收斂消息的準(zhǔn)確性不如本文算法。因此，選擇合適的R，本文算法的BER性能要優(yōu)于PM-MPA算法。R取0.3和0.4時(shí)，由于R取值較大，本文算法的性能損失較多，相比原始MPA分別下降了0.7dB和1.2dB。

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

由表2中各算法復(fù)雜度可知，比重因子R取值越大，本文算法相比于其他兩種，復(fù)雜度就越低。由圖3、圖4可知，為有效地降低算法復(fù)雜度，同時(shí)保障BER性能，取比重因子R=0.2，迭代次數(shù)T=6。結(jié)合表2，如表4所示，原始MPA、PM-MPA(m=3，Rs=2)及本文(R=0.2)算法所執(zhí)行的加法次數(shù)分別為18144次、14688次和11156次；執(zhí)行的乘法次數(shù)分別為32256次、26496次和19834次。本文算法相比于原始MPA，加法次數(shù)減少了約38.5%，乘法次數(shù)減少了約38.5%。PM-MPA為保障解碼性能，提前解出的用戶節(jié)點(diǎn)數(shù)是很有限的，相比于本文算法可以降低的復(fù)雜度有限。與PM-MPA相比，本文算法的加法次數(shù)減少了約24.0%，乘法次數(shù)減少了約25.1%。綜上所述，參數(shù)R取0.2比較合理。此時(shí)，BER性能基本與原始MPA一致，優(yōu)于PM-MPA，同時(shí)復(fù)雜度都明顯低于這兩種算法。

表4 各算法復(fù)雜度比較

5 結(jié)論

原始MPA每次迭代會(huì)更新所有碼字消息，直到所有碼字消息概率收斂后迭代結(jié)束，因此復(fù)雜度較高。為降低復(fù)雜度，針對(duì)不同碼字消息概率的收斂速度不同，本文提出了一種動(dòng)態(tài)選擇消息更新的DSM-MPA算法。在當(dāng)次迭代中找出收斂最快的碼字消息，這些消息將不再更新，通過減少消息更新次數(shù)來降低復(fù)雜度。選擇合適的比重因子，可使BER性能基本與原始MPA一致，并且復(fù)雜度更低；和PM-MPA相比，不僅復(fù)雜度較低，且性能也有優(yōu)勢(shì)。所以，本文算法在SCMA系統(tǒng)的應(yīng)用中優(yōu)勢(shì)明顯，可降低接收機(jī)設(shè)計(jì)復(fù)雜度，同時(shí)可以保持性能。但該算法仍存在一些不足，如比重因子R的選擇固定。當(dāng)信道條件變化時(shí)，每次迭代中選出的不更新的消息，就帶有隨機(jī)和波動(dòng)性。有些消息實(shí)際并未收斂或接近收斂，這將給解碼帶來較大誤差。因此，可設(shè)定硬性的收斂判定條件，以更有效地選擇已收斂的消息不更新?？蓮浹a(bǔ)由隨機(jī)和波動(dòng)性帶來的性能損失，并可適應(yīng)信道變化。