基于加權(quán)分組串行調(diào)度改進(jìn)的MPA算法

鄧 旭，朱立東

(電子科技大學(xué) 通信抗干擾技術(shù)國(guó)家級(jí)重點(diǎn)實(shí)驗(yàn)室，四川 成都 611731)

0 引言

隨著全球經(jīng)濟(jì)和信息交換的快速發(fā)展，如何對(duì)海量用戶(hù)進(jìn)行準(zhǔn)確檢測(cè)與識(shí)別、滿(mǎn)足人們?nèi)找嬖鲩L(zhǎng)的海量接入需求，具有很高的研究?jī)r(jià)值[1]。由于分割的正交信道間沒(méi)有交集，導(dǎo)致有限的信道容量中可容納的用戶(hù)數(shù)量相當(dāng)受限，傳統(tǒng)的正交多址接入技術(shù)已經(jīng)無(wú)法滿(mǎn)足日益增長(zhǎng)的數(shù)據(jù)信息和海量用戶(hù)連接要求了，因此非正交多址接入(Non-Orthogonal Multiple Access，NOMA)技術(shù)成為人們研究的焦點(diǎn)。

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

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

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

根據(jù)前文介紹可知，降低MPA算法計(jì)算復(fù)雜度的算法主要分為基于串行調(diào)度和并行調(diào)度的MPA多用戶(hù)檢測(cè)算法。相比于并行調(diào)度的MPA算法，串行調(diào)度的MPA算法能在保證系統(tǒng)誤碼率的前提下加快系統(tǒng)的收斂速度，然而串行調(diào)度的MPA算法增加了處理時(shí)延。因此本文結(jié)合串行MPA算法和并行MPA算法的優(yōu)勢(shì)，提出一種改進(jìn)的MPA算法，進(jìn)一步降低計(jì)算復(fù)雜度。

1 SCMA系統(tǒng)模型

SCMA系統(tǒng)由J個(gè)用戶(hù)和K個(gè)正交的資源塊組成，其中SCMA系統(tǒng)的用戶(hù)數(shù)大于資源塊數(shù)，即K

(1)

如果J個(gè)用戶(hù)同步發(fā)送數(shù)據(jù)，則接收端收到的多路復(fù)用信號(hào)可表示為：

(2)

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

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

(3)

由于各個(gè)用戶(hù)發(fā)送的數(shù)據(jù)是相互獨(dú)立的，所以SCMA系統(tǒng)中各個(gè)碼字間也具有獨(dú)立性，結(jié)合貝葉斯準(zhǔn)則可以進(jìn)一步將式(3)改寫(xiě)為：

(4)

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

(5)

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

(6)

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

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

步驟1：對(duì)資源節(jié)點(diǎn)進(jìn)行消息更新。鑒于第k個(gè)資源塊，可得：

(7)

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

步驟2：對(duì)用戶(hù)節(jié)點(diǎn)進(jìn)行消息更新。鑒于第j個(gè)用戶(hù)，可得：

(8)

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

當(dāng)達(dá)到最大迭代次數(shù)Nitmax時(shí)，軟判決輸出結(jié)果可得：

(9)

2 低復(fù)雜度檢測(cè)算法

2.1 分組串行調(diào)度MPA算法

串行調(diào)度MPA算法(Serial Scheduling MPA，SS-MPA)和并行調(diào)度MPA算法(Parallel Scheduling MPA，PS-MPA)的最大區(qū)別是SS-MPA算法可以在同一次迭代中依次更新資源節(jié)點(diǎn)的消息和用戶(hù)節(jié)點(diǎn)的消息，而PS-MPA算法則是在本輪迭代中無(wú)法使用已經(jīng)更新的消息，必須等待下一輪才可以被使用。

雖然SS-MPA更新方式已經(jīng)加快了MPA檢測(cè)器的收斂速度，但是串行調(diào)度方式一次迭代過(guò)程所消耗的時(shí)間較長(zhǎng)，即MPA檢測(cè)時(shí)常將會(huì)增大，為了降低SS-MPA算法檢測(cè)帶來(lái)的較大時(shí)延問(wèn)題，在此引入分組的概念，將J個(gè)用戶(hù)分成N組，組與組之間并行執(zhí)行，這樣可以大大降低檢測(cè)時(shí)間。這種檢測(cè)方式也可以稱(chēng)為分組的SS-MPA(Group of SS-MPA，G-SS-MPA)。

G-SS-MPA算法的核心思想是將J個(gè)用戶(hù)節(jié)點(diǎn)分成N組。組內(nèi)的用戶(hù)節(jié)點(diǎn)基于串行調(diào)度的方式更新節(jié)點(diǎn)消息，組與組之間基于并行調(diào)度的方式更新節(jié)點(diǎn)消息，G-SS-MPA算法一次迭代過(guò)程示意圖如圖1所示。從圖中可以明顯看到3個(gè)組之間并行化執(zhí)行，組內(nèi)的節(jié)點(diǎn)串行更新節(jié)點(diǎn)消息，由此進(jìn)一步降低檢測(cè)帶來(lái)的時(shí)延問(wèn)題。

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

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

(10)

式中，當(dāng)G=1時(shí)，G-SS-MPA算法為標(biāo)準(zhǔn)的PS-MPA算法；當(dāng)G=J時(shí)，G-SS-MPA算法為標(biāo)準(zhǔn)的SS-MPA算法。

2.2 基于加權(quán)串行調(diào)度MPA 算法

本節(jié)介紹有關(guān)加權(quán)串行調(diào)度MPA算法(Weight Variable Node SS-MPA，WVN-SS-MPA)，它是在SS-MPA的基礎(chǔ)上，對(duì)用戶(hù)節(jié)點(diǎn)的更新順序進(jìn)行調(diào)整，根據(jù)用戶(hù)節(jié)點(diǎn)的權(quán)值大小優(yōu)先選擇權(quán)值大的節(jié)點(diǎn)進(jìn)行更新。

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

(11)

從式(11)可以看出，若βj權(quán)值越大，說(shuō)明與用戶(hù)節(jié)點(diǎn)uj連接的資源節(jié)點(diǎn)還沒(méi)有達(dá)到收斂狀態(tài)，此時(shí)應(yīng)當(dāng)優(yōu)先選擇這些對(duì)應(yīng)的資源節(jié)點(diǎn)進(jìn)行更新。如果存在多個(gè)用戶(hù)節(jié)點(diǎn)的權(quán)值相同，則說(shuō)明對(duì)應(yīng)的資源節(jié)點(diǎn)的優(yōu)先級(jí)一樣，此時(shí)可以隨機(jī)選擇任意一個(gè)資源節(jié)點(diǎn)進(jìn)行消息更新。

如圖2所示，選擇用戶(hù)權(quán)值節(jié)點(diǎn)最大對(duì)應(yīng)的用戶(hù)節(jié)點(diǎn)，由于初始階段所有用戶(hù)節(jié)點(diǎn)權(quán)值都為0，則可以隨機(jī)選取一個(gè)用戶(hù)節(jié)點(diǎn)。假設(shè)選取用戶(hù)節(jié)點(diǎn)u1及其相連的資源節(jié)點(diǎn)r2和r4，將資源節(jié)點(diǎn)r2和r4的權(quán)值α2和α4自增1，并且與r2和r4的變量節(jié)點(diǎn)權(quán)值都自增1，緊接著將β1從集合中去除，即Ω=Ω-β1。剩下的用戶(hù)節(jié)點(diǎn)都按照該過(guò)程不斷選取，最終可以得到用戶(hù)節(jié)點(diǎn)權(quán)值更新的順序?yàn)椋?→3→5→2→4→6。從算法角度看，WVN-SS-MPA算法是在SS-MPA算法的基礎(chǔ)上添加了權(quán)值計(jì)算來(lái)確定變量節(jié)點(diǎn)的更新順序，所以WVN-SS-MPA算法的加法運(yùn)算數(shù)目會(huì)變得更多，增加了系統(tǒng)計(jì)算復(fù)雜度。

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

2.3 基于球面解碼的MPA算法

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

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

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

(12)

此時(shí)將第k個(gè)資源塊的接收信號(hào)改寫(xiě)為：

(13)

由于高斯噪聲nk的隨機(jī)性，所以接收信號(hào)星座點(diǎn)不會(huì)和任意一個(gè)SCP重疊，則二者之間的歐氏距離可以表示為：

(14)

如果φk(ζ)為發(fā)送正確的SCP，則當(dāng)前φk(ζ)的等價(jià)形式為：

(15)

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

(16)

在實(shí)際情況下nk服從AWGN分布，均值為0，方差為σ2。但是由于接收到的信號(hào)可能處于多個(gè)候選的SCPs中心，很難通過(guò)接收信號(hào)的星座點(diǎn)來(lái)判斷正確發(fā)送的疊加碼字組合。

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

(17)

表1 置信區(qū)間與概率間關(guān)系Tab.1 Relationship between confidence interval and probability

3 基于加權(quán)分組串行調(diào)度的改進(jìn)MPA算法

3.1 算法描述

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

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

步驟3：對(duì)用戶(hù)節(jié)點(diǎn)進(jìn)行更新。鑒于第j(n-1)·JN+1≤j≤nJN,n=1,2,…，N)個(gè)用戶(hù)節(jié)點(diǎn)，可將式(10)改寫(xiě)為：

(18)

步驟4：對(duì)用戶(hù)節(jié)點(diǎn)進(jìn)行更新。鑒于第j{j=(n-1)JN+1,(n-1)JN+2,3，…,nJN}個(gè)用戶(hù)，根據(jù)式(10)進(jìn)行更新。

當(dāng)達(dá)到最大迭代次數(shù)Nitmax時(shí)，根據(jù)式(11)軟判決輸出結(jié)果。

具體有關(guān)IG-WVN-MPA算法如算法1所示。

算法1 IG-WVN-MPA多用戶(hù)檢測(cè)算法

輸入：

1)接受信號(hào)y，噪聲功率N0，信道H

2)各用戶(hù)碼本CB

3)最大迭代次數(shù)Nitmax

輸出：Q(xj)

1:根據(jù)式(11)計(jì)算變量節(jié)點(diǎn)的權(quán)值，并按降序?qū)⒆兞抗?jié)點(diǎn)進(jìn)行排序

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 算法復(fù)雜度分析

表2展示了不同調(diào)度算法的復(fù)雜度對(duì)比。由表中可以看出SS-MPA、G-SS-MPA和WVN-SS-MPA算法的加法運(yùn)算、乘法運(yùn)算、指數(shù)運(yùn)算復(fù)雜度一樣。不難看出，WVN-SS-MPA算法是在SS-MPA算法的基礎(chǔ)上得到的，相比于SS-MPA算法只多增加了權(quán)值的計(jì)算，但是這部分權(quán)值計(jì)算幾乎可以忽略不計(jì)。因此該算法是以犧牲少量算法復(fù)雜度為代價(jià),在VN-SMPA算法的基礎(chǔ)上進(jìn)行了BER性能的優(yōu)化。而G-SS-MPA算法是SS-MPA算法的一個(gè)變形，當(dāng)G=6時(shí)，G-SS-MPA算法等價(jià)為SS-MPA算法；而當(dāng)G=1時(shí)，G-SS-MPA算法等價(jià)為PS-MPA算法。

表2 不同調(diào)度算法復(fù)雜度對(duì)比Tab.2 Comparison of complexity of different scheduling algorithms

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

3.3 仿真結(jié)果分析

本節(jié)將通過(guò)仿真對(duì)比PS-MPA、SS-MPA、G-SS-MPA、WVN-SS-MPA與本文所提出的IG-WVN-MPA算法，從BER性能和復(fù)雜度等方面進(jìn)行分析比較，仿真中各參數(shù)的設(shè)置如表3所示。

表3 仿真參數(shù)Tab.3 Simulation parameters

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

表4 Rayleigh信道參數(shù)Tab.4 Rayleigh channel parameters

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

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

圖4展示了PS-MPA算法、串行調(diào)度MPA算法和所提算法在不同條件下的BER性能曲線對(duì)比，從圖中可以明顯看出WVN-SS-MPA算法的性能最好，IG-WVN-MPA算法在G=6,R=4σ條件下與WVN-SS-MPA的性能一樣好，在G=6,R=3σ條件下的IG-WVN-MPA算法性能次之，PS-MPA算法的性能最差，可以明顯看出串行調(diào)度MPA算法的性能比并行調(diào)度的MPA算法性能要好，與前面的分析中相一致。而IG-WVN-MPA性能要比WVN-SS-MPA略差一些是因?yàn)樵撍惴ㄖ袦p少了每次參與迭代的碼本數(shù)目，這將導(dǎo)致譯碼端無(wú)法正確判別出這些丟失的碼本信息，最終導(dǎo)致性能上的缺失。IG-WVN-MPA算法通過(guò)犧牲一部分系統(tǒng)性能來(lái)加快算法的收斂速度，這樣的算法思想與前文的分析一致。此外可以看出，當(dāng)?shù)螖?shù)達(dá)到5時(shí)，各算法的BER性能基本一樣，且比迭代次數(shù)為1時(shí)提升了1 dB左右的增益。也就是說(shuō)隨著迭代次數(shù)的增大各算法的BER性能會(huì)越來(lái)越好，這是因?yàn)榈螖?shù)的增大使得接收端的判決結(jié)果更加準(zhǔn)確可靠，當(dāng)各算法經(jīng)過(guò)足夠多的迭代次數(shù)后，都能充分利用所有更新的消息，最終性能上會(huì)保持基本一致。

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

圖5為不同MPA算法BER性能隨迭代次數(shù)的變化關(guān)系，可以明顯看出，迭代次數(shù)的增大對(duì)于各MPA算法來(lái)說(shuō)性能會(huì)變得更好，并最終達(dá)到收斂狀態(tài)。

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

這是因?yàn)楫?dāng)?shù)螖?shù)增大時(shí)接收端的判決結(jié)果更加準(zhǔn)確可靠，從而整體性能會(huì)不斷提高；而當(dāng)?shù)螖?shù)達(dá)到一定時(shí)，其消息都已經(jīng)收斂，最終所有的算法在相同Eb/N0下?lián)碛型鹊腂ER性能。此外，也可以看到WVN-SS-MPA算法只需要2次迭代即可收斂，而IG-WVN-MPA算法、SS-MPA算法和G-SS-MPA算法分別需要3次迭代、3次迭代和4次迭代基本上可以收斂，然而性能最差的PS-MPA算法需要6次迭代才能夠達(dá)到收斂。

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

圖6 不同MPA算法計(jì)算復(fù)雜度比較Fig.6 Comparison of computational complexity of different MPa algorithms

4 結(jié)束語(yǔ)

本文研究了SCMA低復(fù)雜度多用戶(hù)檢測(cè)方法，系統(tǒng)分析了SCMA多用戶(hù)檢測(cè)算法的研究現(xiàn)狀，然后分別從串行調(diào)度MPA和并行調(diào)度MPA入手，重點(diǎn)介紹了G-SS-MPA、WVN-SS-MPA、RD-MPA和SD-MPA幾種典型的算法，從算法原理、復(fù)雜度分析和性能對(duì)比分析的角度進(jìn)行論述。從整體上看，算法的改進(jìn)主要圍繞降低迭代次數(shù)、碼本大小、行重因子以及聯(lián)合考慮碼本大小和行重因子來(lái)進(jìn)行。然而對(duì)于聯(lián)合三者來(lái)考慮降低復(fù)雜度卻很少有人涉及，本文結(jié)合G-SS-MPA、WVN-SS-MPA和SD-MPA的優(yōu)勢(shì)，設(shè)計(jì)了IG-WVN-MPA算法。該算法在誤碼性能和復(fù)雜度上可以實(shí)現(xiàn)比較好的平衡，通過(guò)犧牲少量誤碼性能來(lái)進(jìn)一步降低算法的復(fù)雜度。