基于加權分組串行調度改進的MPA算法

鄧 旭，朱立東

(電子科技大學 通信抗干擾技術國家級重點實驗室，四川 成都 611731)

0 引言

隨著全球經濟和信息交換的快速發展，如何對海量用戶進行準確檢測與識別、滿足人們日益增長的海量接入需求，具有很高的研究價值[1]。由于分割的正交信道間沒有交集，導致有限的信道容量中可容納的用戶數量相當受限，傳統的正交多址接入技術已經無法滿足日益增長的數據信息和海量用戶連接要求了，因此非正交多址接入(Non-Orthogonal Multiple Access，NOMA)技術成為人們研究的焦點。

對于NOMA，高性能的多用戶檢測是必須考慮的問題。消息傳遞算法(MPA)是一種置信傳播算法，通過因子矩陣的邊緣迭代傳遞消息進行更新直到算法收斂或達到最大迭代次數。但是該算法當用戶數增大時，其復雜度呈現指數增長，為此設計低復雜度的SCMA多用戶檢測算法變得尤為重要。近年來，低復雜度多用戶檢測算法已經成為熱點研究方向之一，目前已有大量的研究成果。傳統的MPA算法以并行方式更新消息，這會導致先更新的消息無法得到及時利用，需要中間變量將其存儲等待下一次迭代才能被利用。為解決這一問題，文獻[2]提出一種基于串行更新的消息傳遞算法(Shuffled MPA,S-MPA)，該算法能夠立即傳播在當前迭代中已經更新的消息，無需等到下一次迭代，該方式能加快算法的收斂速度，降低迭代次數，從而降低算法復雜度。然而這種算法初始條件下對于用戶的迭代更新順序是隨機的，無法保證最可靠的消息及時得到更新。在此基礎上，文獻[3]提出一種改進的基于串行調度的消息傳遞算法(Improved Serial Scheduling Based MPA,ISS-MPA)，該算法首先對變量節點的更新順序進行選擇，根據變量節點的權值大小確定各個變量節點的更新優先級，在此基礎上再根據S-MPA算法進行消息的迭代更新。由于增加了權值的計算，該算法增大了系統開銷，因此該算法是通過犧牲算法復雜度為代價來進行BER更新的。

文獻[4]提出了擴展的對數域Max-Log(Extended Max-Log,EML)MPA算法，該算法基于截短消息的思想避免了直接使用M維消息進行消息傳遞，這樣的方式能較好地在BER性能和算法復雜度上獲取平衡。為了進一步降低BER，文獻[5]提出了另一種消息截取方式，即基于動態網格的消息傳遞算法(Dynamic Trellis Based MPA,DT-MPA)。在每次迭代過程中，首先將各個列對應的符號值進行排序，只需將前i個網格點的值保留下來參與消息的迭代即可，仿真結果表明該算法可以獲得比EML算法更低的復雜度。

文獻[6]提出了一種殘差輔助的消息傳遞算法(Residual-aided MPA,R-aided MPA)。該算法利用變量節點消息更新前后的差異作為衡量標準，殘差值越大表明其優先級越高，優先更新殘差值最大的節點消息，從而加快譯碼的收斂速度，提高MPA迭代算法的收斂性。文獻[7]提出了一種基于邊緣選擇的消息傳遞算法(Edge Selected MPA,ES-MPA)，該算法只選取信道質量較好的部分邊緣進行資源節點到用戶節點的更新，質量較差的邊緣將被視為干擾并利用高斯近似的方法進行計算，該算法可以在不降低BER性能的同時保證算法復雜度的降低。此外，文獻[8]提出一種基于部分邊緣化的消息傳遞算法(Partial Marginalization MPA,PM-MPA)，該算法首先預設一個迭代次數閾值，當迭代次數小于閾值時按照并行的MPA算法進行消息的迭代更新，反之只有前面m個元素參與消息的更新迭代，從一定程度上降低算法的復雜度，但與此同時也帶來了較大的BER性能損失。文獻[9]提出一種基于球形譯碼的檢測算法(Sphere Decoding MPA,SD-MPA)，該算法首先通過高斯噪聲的分布特性選定圓形半徑 ，然后在進行資源節點更新過程中只有半徑范圍內的疊加星座點參與消息的迭代，從而可以在誤碼性能和復雜度上獲取平衡。

根據前文介紹可知，降低MPA算法計算復雜度的算法主要分為基于串行調度和并行調度的MPA多用戶檢測算法。相比于并行調度的MPA算法，串行調度的MPA算法能在保證系統誤碼率的前提下加快系統的收斂速度，然而串行調度的MPA算法增加了處理時延。因此本文結合串行MPA算法和并行MPA算法的優勢，提出一種改進的MPA算法，進一步降低計算復雜度。

1 SCMA系統模型

SCMA系統由J個用戶和K個正交的資源塊組成，其中SCMA系統的用戶數大于資源塊數，即K

(1)

如果J個用戶同步發送數據，則接收端收到的多路復用信號可表示為：

(2)

式中，第j個用戶的信道有效矩陣為hj，n表示信道噪聲，服從高斯白噪聲n～CN(0,N0I)。

當接收信號y和信道矩陣H=[h1,h2,…,hJ]T已知時，假設用X=(x1,x2，…,xJ)表示J個用戶的碼字，則MAP檢測算法可表示為：

(3)

由于各個用戶發送的數據是相互獨立的，所以SCMA系統中各個碼字間也具有獨立性，結合貝葉斯準則可以進一步將式(3)改寫為：

(4)

第k個資源塊上非零碼字組合可以用Xk,ξk=(Xξk,1,Xξk,2,…,Xξk,dr)來表示，則式(4)可以改寫為：

(5)

最終可以將式(5)改寫為：

(6)

由式(6)可以看出，MAP檢測就是根據已知接收信號進行窮舉從而得到最大的概率組合，該算法的計算復雜度為O(MJ)。隨著用戶數量的增長，該算法的計算復雜度將呈現指數型上升，這給SCMA接收機的設計帶來了很大的挑戰，要求對較低復雜度的SCMA多用戶檢測方案進行研究。

在眾多算法中，MPA算法是一種次優的多用戶檢測算法。該算法在保證BER性能的前提下可以將計算復雜度降低至O(Mdr)，其工作原理是根據因子圖迭代地更新和傳遞邊上的信息，直到最大迭代次數。假設Rrk→uj(xj)表示因子圖中資源節點rk到用戶節點uj的更新消息，Uuj→rk(xj)表示因子圖中用戶節點uj到資源節點rk的更新消息。

步驟1：對資源節點進行消息更新。鑒于第k個資源塊，可得：

(7)

式中，k=1,2,…,K，t=1,2,…,Nitmax。ξk為因子矩陣F第k行非零元素的集合。

步驟2：對用戶節點進行消息更新。鑒于第j個用戶，可得：

(8)

其中，j=1,2,…,J，t=1,2,…,Nitmax。ζj為因子矩陣F第j列非零元素的集合。

當達到最大迭代次數Nitmax時，軟判決輸出結果可得：

(9)

2 低復雜度檢測算法

2.1 分組串行調度MPA算法

串行調度MPA算法(Serial Scheduling MPA，SS-MPA)和并行調度MPA算法(Parallel Scheduling MPA，PS-MPA)的最大區別是SS-MPA算法可以在同一次迭代中依次更新資源節點的消息和用戶節點的消息，而PS-MPA算法則是在本輪迭代中無法使用已經更新的消息，必須等待下一輪才可以被使用。

雖然SS-MPA更新方式已經加快了MPA檢測器的收斂速度，但是串行調度方式一次迭代過程所消耗的時間較長，即MPA檢測時常將會增大，為了降低SS-MPA算法檢測帶來的較大時延問題，在此引入分組的概念，將J個用戶分成N組，組與組之間并行執行，這樣可以大大降低檢測時間。這種檢測方式也可以稱為分組的SS-MPA(Group of SS-MPA，G-SS-MPA)。

G-SS-MPA算法的核心思想是將J個用戶節點分成N組。組內的用戶節點基于串行調度的方式更新節點消息，組與組之間基于并行調度的方式更新節點消息，G-SS-MPA算法一次迭代過程示意圖如圖1所示。從圖中可以明顯看到3個組之間并行化執行，組內的節點串行更新節點消息，由此進一步降低檢測帶來的時延問題。

圖1 G-SS-MPA算法平均分為3組時的一次迭代過程Fig.1 An iterative process when the G-SS-MPA is evenly divided into 3 groups

一般情況下都是將所有用戶節點進行平均分組，每組將會有Jn=J/N個用戶節點。對于(n-1)·JN+1≤j≤nJN,n=1,2,…,N的用戶節點，可以將式(7)改寫為：

(10)

式中，當G=1時，G-SS-MPA算法為標準的PS-MPA算法；當G=J時，G-SS-MPA算法為標準的SS-MPA算法。

2.2 基于加權串行調度MPA 算法

本節介紹有關加權串行調度MPA算法(Weight Variable Node SS-MPA，WVN-SS-MPA)，它是在SS-MPA的基礎上，對用戶節點的更新順序進行調整，根據用戶節點的權值大小優先選擇權值大的節點進行更新。

定義用戶節點的權值為βj(j=1,2,…J)，其表示連接到用戶節點uj處的資源節點權值之和；資源節點權值為αk(k=1,2,…,K)，其表示資源節點rk的權值，由此可以得到：

(11)

從式(11)可以看出，若βj權值越大，說明與用戶節點uj連接的資源節點還沒有達到收斂狀態，此時應當優先選擇這些對應的資源節點進行更新。如果存在多個用戶節點的權值相同，則說明對應的資源節點的優先級一樣，此時可以隨機選擇任意一個資源節點進行消息更新。

如圖2所示，選擇用戶權值節點最大對應的用戶節點，由于初始階段所有用戶節點權值都為0，則可以隨機選取一個用戶節點。假設選取用戶節點u1及其相連的資源節點r2和r4，將資源節點r2和r4的權值α2和α4自增1，并且與r2和r4的變量節點權值都自增1，緊接著將β1從集合中去除，即Ω=Ω-β1。剩下的用戶節點都按照該過程不斷選取，最終可以得到用戶節點權值更新的順序為：1→3→5→2→4→6。從算法角度看，WVN-SS-MPA算法是在SS-MPA算法的基礎上添加了權值計算來確定變量節點的更新順序，所以WVN-SS-MPA算法的加法運算數目會變得更多，增加了系統計算復雜度。

圖2 WVN-SS-MPA算法變量節點順序選擇更新示意圖Fig.2 WVN-SS-MPA algorithm variable node sequence selection update diagram

2.3 基于球面解碼的MPA算法

目前有關降低PS-MPA算法計算復雜度主要從減少M或者dr著手，但是很少有人涉及從整體Mdr的角度降低該算法的計算復雜度。本節提出的SD-MPA算法通過減少SCPs的數量來降低MPA檢測的復雜度，它首先對資源節點上的碼字信息進行篩選，設置一個合理的半徑，在半徑范圍內的星座點才參與迭代，大于半徑范圍的點全部去除。其中半徑r的確定可以通過高斯噪聲的分布特性，從而在誤碼性能和計算復雜度上保持平衡。

在PS-MPA譯碼過程中，由于一個資源塊上一共有Mdr個SCPs，則rk資源塊上的星座點集合可以表示為：

Φ(k)=(φk(1),φk(2),…,φk(Mdr))，

(12)

此時將第k個資源塊的接收信號改寫為：

(13)

由于高斯噪聲nk的隨機性，所以接收信號星座點不會和任意一個SCP重疊，則二者之間的歐氏距離可以表示為：

(14)

如果φk(ζ)為發送正確的SCP，則當前φk(ζ)的等價形式為：

(15)

結合式(14)～(15)可以得到：

(16)

在實際情況下nk服從AWGN分布，均值為0，方差為σ2。但是由于接收到的信號可能處于多個候選的SCPs中心，很難通過接收信號的星座點來判斷正確發送的疊加碼字組合。

從表1可以看出，置信區間(-2σ,2σ)在可以保證圓形區域內有95.4%的可信信息，當半徑r→∞時，SD-MPA算法即為PS-MPA算法。在給定球形譯碼半徑的前提下，置信度較高的SCPs和發送信號星座點之間的歐氏距離滿足：

(17)

表1 置信區間與概率間關系Tab.1 Relationship between confidence interval and probability

3 基于加權分組串行調度的改進MPA算法

3.1 算法描述

根據第2節介紹可知，降低MPA算法計算復雜度的方法主要有減少迭代次數Niter、降低碼本大小M、降低行重因子df或是整體降低每次參與迭代點數Mdr[14]。但是通過減少迭代次數Niter和降低每次參與迭代點數Mdr二者結合考慮的方式來降低MPA算法復雜度卻很少有人涉及，在此選出具有典型代表的G-SS-MPA和SD-MPA算法，發揮二者的優勢從整體上來降低算法復雜度，為此設計了基于加權分組串行調度的改進MPA算法(Improved Group of WVN-MPA,IG-WVN-MPA)。

步驟1：根據2.1節的分析可知分組數越多G-SS-MPA算法的性能越好，因此考慮可以將G-SS-MPA代替SS-MPA來降低算法復雜度。然后又根據2.2節的分析可知對用戶節點的更新順序進行調整可以提高系統的BER性能。因此在初始階段，在G-SS-MPA算法中加入權值大小排序，根據式(11)確定所有用戶節點的待更新順序。

步驟3：對用戶節點進行更新。鑒于第j(n-1)·JN+1≤j≤nJN,n=1,2,…，N)個用戶節點，可將式(10)改寫為：

(18)

步驟4：對用戶節點進行更新。鑒于第j{j=(n-1)JN+1,(n-1)JN+2,3，…,nJN}個用戶，根據式(10)進行更新。

當達到最大迭代次數Nitmax時，根據式(11)軟判決輸出結果。

具體有關IG-WVN-MPA算法如算法1所示。

算法1 IG-WVN-MPA多用戶檢測算法

輸入：

1)接受信號y，噪聲功率N0，信道H

2)各用戶碼本CB

3)最大迭代次數Nitmax

輸出：Q(xj)

1:根據式(11)計算變量節點的權值，并按降序將變量節點進行排序

4: whilet≤Nitmaxdo

5: forn=1,2,…,Ndo

6: forj=(n-1)JN+1,(n-1)JN+2,3，…,nJNdo

7: fork∈ζjdo

8:

9:

10: end for

11: end for

12: forj=(n-1)JN+1,(n-1)JN+2,3，…,nJN

13:

14: end for

15:end for

16:t=t+1

17:end while

18:forj=1,2,…Jdo

19:

20:end for

3.2 算法復雜度分析

表2展示了不同調度算法的復雜度對比。由表中可以看出SS-MPA、G-SS-MPA和WVN-SS-MPA算法的加法運算、乘法運算、指數運算復雜度一樣。不難看出，WVN-SS-MPA算法是在SS-MPA算法的基礎上得到的，相比于SS-MPA算法只多增加了權值的計算，但是這部分權值計算幾乎可以忽略不計。因此該算法是以犧牲少量算法復雜度為代價,在VN-SMPA算法的基礎上進行了BER性能的優化。而G-SS-MPA算法是SS-MPA算法的一個變形，當G=6時，G-SS-MPA算法等價為SS-MPA算法；而當G=1時，G-SS-MPA算法等價為PS-MPA算法。

表2 不同調度算法復雜度對比Tab.2 Comparison of complexity of different scheduling algorithms

此外通過前面分析可以明顯看出串行調度算法的收斂速度要比并行調度算法快，即在相同條件下串行調度算法的復雜度要比并行調度算法低。但是可以將其中的SD-MPA算法融入至串行調度算法中，由提出的新算法可以看出相比于串行調度算法，其加法運算和乘法運算中每次參與迭代點數Mdr降低至|Φ*(k)|(一般情況下|Φ*(k)|=Mdr/3[15])，由此進一步降低算法復雜度。

3.3 仿真結果分析

本節將通過仿真對比PS-MPA、SS-MPA、G-SS-MPA、WVN-SS-MPA與本文所提出的IG-WVN-MPA算法，從BER性能和復雜度等方面進行分析比較，仿真中各參數的設置如表3所示。

表3 仿真參數Tab.3 Simulation parameters

本文的Rayleigh信道參數如表4所示[16]。

表4 Rayleigh信道參數Tab.4 Rayleigh channel parameters

圖3展示了不同條件下IG-WVN-MPA算法的性能對比。由圖中可以明顯看出，隨著G和R的增大，IG-WVN-MPA算法的性能在不斷提升。這是因為G的增大意味著串行調度更新的頻率就會越高，算法收斂速度也會變快，系統性能隨之提高。而R的增大意味著置信區域在不斷變大，迭代過程中丟失的信息逐漸變少，最終譯碼輸出的結果精確度不斷提高，則系統性能也跟著提升。此外還可以看到IG-WVN-MPA算法在G=6和R=4σ條件下性能最優，而在G=2和R=2σ條件下性能最差。與此同時隨著Eb/N0的增大，G的變化對于所提算法的影響在逐漸增大，而R的變化對所提算法的影響在逐漸變小。

圖3 不同G和R條件下的IG-WVN-MPA 算法BER性能對比Fig.3 BER performance comparison of IG-WVN-MPA algorithm under differentG andR conditions

圖4展示了PS-MPA算法、串行調度MPA算法和所提算法在不同條件下的BER性能曲線對比，從圖中可以明顯看出WVN-SS-MPA算法的性能最好，IG-WVN-MPA算法在G=6,R=4σ條件下與WVN-SS-MPA的性能一樣好，在G=6,R=3σ條件下的IG-WVN-MPA算法性能次之，PS-MPA算法的性能最差，可以明顯看出串行調度MPA算法的性能比并行調度的MPA算法性能要好，與前面的分析中相一致。而IG-WVN-MPA性能要比WVN-SS-MPA略差一些是因為該算法中減少了每次參與迭代的碼本數目，這將導致譯碼端無法正確判別出這些丟失的碼本信息，最終導致性能上的缺失。IG-WVN-MPA算法通過犧牲一部分系統性能來加快算法的收斂速度，這樣的算法思想與前文的分析一致。此外可以看出，當迭代次數達到5時，各算法的BER性能基本一樣，且比迭代次數為1時提升了1 dB左右的增益。也就是說隨著迭代次數的增大各算法的BER性能會越來越好，這是因為迭代次數的增大使得接收端的判決結果更加準確可靠，當各算法經過足夠多的迭代次數后，都能充分利用所有更新的消息，最終性能上會保持基本一致。

圖4 不同MPA算法BER性能對比Fig.4 Comparison of BER performance of different MPA algorithms

圖5為不同MPA算法BER性能隨迭代次數的變化關系，可以明顯看出，迭代次數的增大對于各MPA算法來說性能會變得更好，并最終達到收斂狀態。

圖5 不同MPA算法BER性能與迭代次數的關系Fig.5 Relationship between BER performance and iteration times of different MPA algorithms

這是因為當迭代次數增大時接收端的判決結果更加準確可靠，從而整體性能會不斷提高；而當迭代次數達到一定時，其消息都已經收斂，最終所有的算法在相同Eb/N0下擁有同等的BER性能。此外，也可以看到WVN-SS-MPA算法只需要2次迭代即可收斂，而IG-WVN-MPA算法、SS-MPA算法和G-SS-MPA算法分別需要3次迭代、3次迭代和4次迭代基本上可以收斂，然而性能最差的PS-MPA算法需要6次迭代才能夠達到收斂。

圖6顯示了6次迭代的PS-MPA、4次迭代的G-SS-MPA、3次迭代的SS-MPA、2次迭代的WVN-SS-MPA算法和3次迭代的IG-WVN-MPA算法的復雜度比較。從圖中可以明顯看出，IG-WVN-MPA算法所需的乘法和加法運算次數最少，這進一步驗證了IG-WVN-MPA算法的低復雜度算法特性。具體來說與6次迭代的PS-MPA、4次迭代的G-SS-MPA、3次迭代的SS-MPA和2次迭代的WVN-SS-MPA算法相比分別節省了76.9%、75%、66.7%和50.1%乘法運算，以及分別節省了90.9%、75.8%、67.7%和51.6%加法運算。因此IG-WVN-MPA算法在誤碼性能和復雜度上提供了更優的折中方案。

圖6 不同MPA算法計算復雜度比較Fig.6 Comparison of computational complexity of different MPa algorithms

4 結束語

本文研究了SCMA低復雜度多用戶檢測方法，系統分析了SCMA多用戶檢測算法的研究現狀，然后分別從串行調度MPA和并行調度MPA入手，重點介紹了G-SS-MPA、WVN-SS-MPA、RD-MPA和SD-MPA幾種典型的算法，從算法原理、復雜度分析和性能對比分析的角度進行論述。從整體上看，算法的改進主要圍繞降低迭代次數、碼本大小、行重因子以及聯合考慮碼本大小和行重因子來進行。然而對于聯合三者來考慮降低復雜度卻很少有人涉及，本文結合G-SS-MPA、WVN-SS-MPA和SD-MPA的優勢，設計了IG-WVN-MPA算法。該算法在誤碼性能和復雜度上可以實現比較好的平衡，通過犧牲少量誤碼性能來進一步降低算法的復雜度。