基于SCMA系統(tǒng)的多用戶檢測消息傳遞算法

張雪婉,葛文萍,吳 雄

(新疆大學(xué) 信息科學(xué)與工程學(xué)院,烏魯木齊 830046)

0 概述

正交多址接入一直在前幾代的電信系統(tǒng)中被廣泛應(yīng)用。為了滿足未來5G的眾多需求,IMT-2020推進(jìn)組提出了非正交多址接入[1]。在眾多非正交多址技術(shù)中[2],稀疏碼多址接入(Sparse Code Multiple Access,SCMA)[3]作為第五代(5G)移動通信系統(tǒng)的候選技術(shù)之一,引起了眾多研究者的注意。由低密度信號(Low Density Signal,LDS)[4-6]演進(jìn)而來的SCMA,將高維調(diào)制與稀疏擴(kuò)頻融合在一起,直接把比特數(shù)據(jù)流映射為預(yù)先設(shè)定碼本里的復(fù)數(shù)域多維碼字[7],用以解決海量連接的系統(tǒng)過載情況[8-9]。與OFDMA相比,SCMA可以實(shí)現(xiàn)150%、200%,甚至更多的設(shè)備連接數(shù)[10]。

目前,如何降低SCMA系統(tǒng)解碼的復(fù)雜度是SCMA面臨的重要挑戰(zhàn)之一[11]。在文獻(xiàn)[7]中基于SCMA碼本的稀疏性提到并行MPA算法。在此基礎(chǔ)上,文獻(xiàn)[8]提出一種基于對數(shù)域的并行MAX-LogMPA算法,該算法雖然檢測性能不如并行MPA算法,但卻大大降低了算法的復(fù)雜度,硬件實(shí)現(xiàn)更加容易。文獻(xiàn)[12]對并行MPA算法進(jìn)行了詳細(xì)的闡述以及仿真驗(yàn)證,證明了其是一種低復(fù)雜度且性能可以逼近最優(yōu)檢測器的優(yōu)良算法。另外,文獻(xiàn)[13-14]也提出一種串行的MPA算法,該算法與并行MPA算法相比,加快了檢測器的收斂速度,算法復(fù)雜度也有所降低。

針對以上不同策略的MPA多用戶檢測算法,本文結(jié)合串行MPA算法收斂速度快和并行MAX-Log MPA算法復(fù)雜度較低的優(yōu)點(diǎn),提出一種基于對數(shù)域的串行MAX-LogMPA算法。該算法可加快收斂速度,在保證BER性能的條件下其算法復(fù)雜度達(dá)到最低。

另外,考慮到現(xiàn)有研究大都采用基于并行MPA算法對SCMA系統(tǒng)進(jìn)行多用戶檢測,還沒有相關(guān)工作來對以上不同策略的MPA算法進(jìn)行統(tǒng)一的性能比較和總結(jié),本文對以上不同策略的MPA算法進(jìn)行詳細(xì)論述,并與最大似然(Maximum Likelihood,ML)算法進(jìn)行性能比較。

1 上行SCMA系統(tǒng)模型

假定一個上行多用戶SCMA通信系統(tǒng),J個用戶共享N個正交時頻資源K(J>K),并傳輸數(shù)據(jù)給同一個基站,其過載因子定義為λ=J/K。J=6,K=4的上行SCMA系統(tǒng)模型如圖1所示。

圖1 上行SCMA通信系統(tǒng)模型

SCMA編碼器定義為f:BlbM→X,x=f(b),其中X∈Ck,基數(shù)|X|=M。K維復(fù)數(shù)碼字x是具有N

圖2 矩陣F及因子圖的對應(yīng)關(guān)系

假定全部用戶時間同步,基站接收到的信號為全部用戶信號疊加,可以表示為:

(1)

其中,xj=[x1j,x2j,…,xkj]T表示第j個用戶發(fā)送的碼字,hj=[h1j,h2j,…,hkj]T表示第j個用戶的信道向量,n為高斯白噪聲且n～cN(0,σ2I)。

時頻資源k處接收到的信號為:

(2)

由于碼字xj是稀疏的,因此在時頻資源k處僅有較少的碼字沖突。

給定y為接收信號,并假定基站已經(jīng)獲取了信道矩陣H=(h1,h2,…,hj),則針對于X=(x1,x2,…,xj)的聯(lián)合最大后驗(yàn)概率檢測可以表示為:

(3)

(4)

如果假設(shè)每個碼字的發(fā)射概率都相等,那么最大后驗(yàn)概率檢測MAP就簡化成最大釋然檢測ML:

(5)

ML算法利用窮舉法搜索所有用戶以及各自碼本的可能組合,所以算法復(fù)雜度極高,這就限制了其在實(shí)際通信系統(tǒng)的應(yīng)用[14]。

2 消息傳遞算法

由于SCMA通信系統(tǒng)的碼字稀疏性特點(diǎn),基于和積算法[15]原理,次優(yōu)的基于迭代的低復(fù)雜度的MPA算法被提出[7]。作為SCMA系統(tǒng)中主流的多用戶檢測算法,MPA算法具有無法替代的優(yōu)勢。

2.1 并行MPA

圖3 并行MPA算法的消息傳遞過程

并行MPA一次迭代過程中的2個階段可以分別用數(shù)學(xué)公式表示為:

(6)

(7)

其中,t為迭代次數(shù),εk與ζj分別表示稀疏碼矩陣F第k行的非零位置集與第j列的非零位置集。

并行MPA達(dá)到預(yù)先設(shè)定的最大迭代次數(shù)tmax后,每一個用戶各自的碼字輸出概率可以表示為:

(8)

得到每個用戶各自的碼字概率以后,接下來就需要算出對數(shù)似然比(Log Likelihood Rate,LLR),每一個bit的LLR(bj,m)可表示為:

(9)

其中,m=1,2,…,lb(Q),Q為使用的調(diào)制進(jìn)制數(shù)。

最后,判決LLR(bj,m)得到bj,m,判決表達(dá)式:

(10)

與ML算法相比,該算法由于利用了SCMA的稀疏性這一特點(diǎn),節(jié)點(diǎn)之間的信息在遞送過程時,只考慮與自身相連的節(jié)點(diǎn),因此算法復(fù)雜度有所減低,性能接近ML算法。但該算法收斂速度較慢。

2.2 串行MPA

(11)

由式(11)可以看出,用戶節(jié)點(diǎn)的計算可以由資源節(jié)點(diǎn)計算得出,即資源節(jié)點(diǎn)與用戶節(jié)點(diǎn)的計算公式可以合二為一。

(12)

其中,[.]old與[.]new分別表示更新前后的消息。顯然Pt-1(xj)的置信度,[Pt-1(xj)]new比[Pt-1(xj)]old更準(zhǔn)確。例如k=1,k=2時,串行MPA算法的迭代過程如圖4所示。因?yàn)橛脩魎3對應(yīng)于2個資源節(jié)點(diǎn),在k=1計算完以后,由式(12)可知,用戶u3的置信度也隨之改變,當(dāng)進(jìn)行下次計算,即k=2時,參與運(yùn)算的用戶u3已經(jīng)是更新后的新消息。所以該算法在每次計算時同時伴隨用戶碼字消息的更新,為下一步的計算提供了更加可靠的置信度。

圖4 串行MPA算法的信息傳遞過程

(13)

綜合式(6)和式(13),可以得到串行 MPA多用戶檢測算法的資源節(jié)點(diǎn)消息更新公式為:

(14)

其中,i≠j,i∈εk,j∈εk。

串行 MPA多用戶檢測算法在每輪迭代過程中,更新后的消息馬上傳遞給后面的節(jié)點(diǎn),而不必等到下一輪迭代過程。顯然,這種串行策略對消息的更新是異步的,并且越靠后處理的資源節(jié)點(diǎn)消息更新越可靠。這樣一來,串行MPA進(jìn)行一次迭代相當(dāng)于并行MPA多次迭代的效果,改善了消息收斂特性。顯然,在較少迭代次數(shù)時,串行 MPA在誤碼率性能上的優(yōu)勢更能得到體現(xiàn)。

2.3 并行MAX-Log MPA

由于exp()以及連乘計算的復(fù)雜性,通過取對數(shù)的運(yùn)算,并采用max近似計算資源節(jié)點(diǎn)的信息更新,可以大幅度地降低計算的復(fù)雜度。該算法的計算公式如下:

因?yàn)?

(15)

所以,式(6)和式(7)可以改寫為:

(16)

(17)

達(dá)到預(yù)先設(shè)定的最大迭代次數(shù)tmax后,每一個用戶各自的碼字輸出概率可以表示為:

(18)

從式(15)和式(16)可以看出,節(jié)點(diǎn)在迭代更新的過程中,由于采用了max的近似計算,必將造成一部分的信息丟失,因此該算法的性能一定不如前2種算法。另外,從式(16)～式(18)可以發(fā)現(xiàn),通過取對數(shù)運(yùn)算,把乘法轉(zhuǎn)化為加法,在實(shí)際計算時,乘法器將減少,加法器增加,這樣將使算法復(fù)雜度降低。所以,該算法是以犧牲檢測性能來降低運(yùn)算復(fù)雜度,在誤碼率可以容忍的情況下,運(yùn)算復(fù)雜度使硬件的實(shí)現(xiàn)變得更加容易。

2.4 串行MAX-Log MPA

由2.2節(jié)對串行MPA的分析和2.3節(jié)對并行MAX-Log MPA的分析可知,串行MPA算法具有收斂速度快的優(yōu)點(diǎn),MAX-Log運(yùn)算可以降低復(fù)雜度。為了進(jìn)一步降低運(yùn)算復(fù)雜度,本文提出一種串行MAX-Log MPA算法。

對式(13)和式(14)取MAX-Log運(yùn)算,可以得到串行MAX-Log MPA多用戶檢測算法用戶碼字和資源節(jié)點(diǎn)消息更新公式:

(19)

(20)

該算法由于繼承了串行策略在收斂速度方面的優(yōu)勢,在每輪迭代過程中,更新后的消息能立刻傳遞給后面的節(jié)點(diǎn),用于下一資源節(jié)點(diǎn)的消息更新,而不必像并行MAX-Log MPA必須等到下一輪迭代過程,并且越靠后計算的資源節(jié)點(diǎn)消息更新越可靠。這樣平均下來,串行MAX-Log MPA進(jìn)行一次迭代相當(dāng)于并行MAX-Log MPA多次迭代的效果,在迭代次數(shù)較少時,串行MAX-Log MPA比并行MAX-Log MPA在誤碼率性能上更有優(yōu)勢。

3 算法復(fù)雜度分析

SCMA多用戶檢測算法的復(fù)雜度主要體現(xiàn)在迭代計算過程和迭代次數(shù)[8,13-14]。與并行MAX-Log MPA相比,本文算法是通過收斂所需要迭代次數(shù)的減少來進(jìn)一步降低計算復(fù)雜度。

以算法達(dá)到收斂所涉及的乘法器、加法器、exp運(yùn)算數(shù)目為標(biāo)準(zhǔn)分析復(fù)雜度。由理論分析可知,串行MPA比并行MPA在收斂速度上更有優(yōu)勢,在算法達(dá)到收斂,整個多用戶檢測過程所需的加法器、乘法器會相應(yīng)減少。同理,算法達(dá)到收斂,串行MAX-Log MPA比并行MAX-Log MPA所需的加法器、乘法器也會減少。另外,由文獻(xiàn)[10]可知,并、串MPA中的exp()運(yùn)算會增加大量的計算復(fù)雜度和消耗不少的存儲空間。由此可知,串行MAX-Log MPA既加快了收斂速度,又采用MAX-Log運(yùn)算消除了exp()運(yùn)算,其復(fù)雜度進(jìn)一步降低。

另外,為了對以上基于不同策略的MPA算法進(jìn)行復(fù)雜度分析,列出5種算法的復(fù)雜度,如表1所示。式中df表示作用于資源節(jié)點(diǎn)的用戶數(shù),dv表示作用于用戶節(jié)點(diǎn)的時頻資源數(shù)。

表1 不同策略實(shí)現(xiàn)的MPA算法以及最優(yōu)ML算法運(yùn)算復(fù)雜度

4 仿真分析

為了驗(yàn)證本文所提算法在上行SCMA通信系統(tǒng)的性能和分析基于不同策略實(shí)現(xiàn)的MPA算法的性能,將以上算法進(jìn)行比較仿真實(shí)驗(yàn)。仿真參數(shù)為用戶數(shù)J=6、擴(kuò)頻因子K=4、碼本尺寸M=4、過載率λ=150%,信道類型為加性高斯白噪聲AWGN。

4.1 收斂速度

圖5是信噪比為12 dB時,4種采用不同策略實(shí)現(xiàn)的MPA算法的收斂情況。由圖5可以看出,串行MPA和串行MAX-Log MPA多用戶檢測算法(3次達(dá)到收斂),其收斂速度比起并行MPA和并行MAX-Log MPA多用戶檢測算法(6次達(dá)到收斂)快上1倍。在迭代次數(shù)較小(1次、2次與3次)的情況下,串行MPA和串行MAX-Log MPA的誤碼率性能明顯優(yōu)于并行MPA和并行MAX-Log MPA,這是因?yàn)榇蠱PA和串行MAX-Log MPA可以立即把已更新的消息傳遞給后面的節(jié)點(diǎn),而不像并行MPA和并行MAX-Log MPA那樣必須等到下一輪的迭代,這就使得采用串行策略的算法可以更加充分地利用新信息,從而加快算法的收斂速度。另外,無論是并行MPA、串行MPA,還是并行MAX-Log MPA、串行MAX-Log MPA,在算法最終達(dá)到收斂后,并、串行MPA的最終誤碼率性能一致,并、串行MAX-Log MPA的最終誤碼率性能一致。這是因?yàn)闊o論哪種策略最終都能充分利用已更新的消息。

圖5 4種不同策略的MPA算法收斂速度

并、串MAX-Log MPA與并、串MPA相比,其誤碼率性能降低了約一個數(shù)量級。這是因?yàn)椴ⅰ⒋甅AX-Log MPA采用MAX近似計算節(jié)點(diǎn)之間的消息更新,會造成一部分信息的丟失,置信度降低,所以在最終算法到達(dá)收斂后,其誤碼率性能也會降低。由此可以看出,本文算法誤碼率性能與并行 MAX-Log MPA相當(dāng),但由于繼承了串行策略使其收斂速度加快了近1倍。

4.2 誤碼率性能對比

圖6為4種不同策略的MPA算法以及最優(yōu)ML算法誤碼率性能的比較,圖中誤碼率性能是不同策略的MPA算法達(dá)到收斂以后的誤碼率性能。由圖6可知,并、串行MAX-LogMPA兩者收斂后的誤碼率性能一樣,且隨信噪比的增大,誤碼率呈線性下降的趨勢。并、串MPA兩者的誤碼率性能較好,且誤碼率性能也完全一致,隨信噪比的增大,誤碼率呈指數(shù)下降的趨勢。最優(yōu)ML算法的誤碼率性能,在信噪比小于2 dB時還不如并、串MAX-Log MPA,信噪比小于4 dB。在信噪比大于4 dB時,ML算法的誤碼率優(yōu)勢開始顯現(xiàn)出來,在所有算法中誤碼率性能最優(yōu)。所以說,在環(huán)境很差的條件下,ML算法并不是最優(yōu)的。另外,并、串行MPA算法的誤碼率性能與最優(yōu)ML算法的誤碼率性能相近。

圖6 4種不同策略的算法誤碼率性能比較

4.3 算法復(fù)雜度對比

結(jié)合算法復(fù)雜度分析和3次迭代串行MPA、串行MAX-Log MPA,6次迭代并行MPA、并行MAX-Log MPA,可以得到圖7。從圖中可知,最優(yōu)ML算法復(fù)雜度最高,硬件難以實(shí)現(xiàn)。針對并、串MPA算法,由于串行MPA算法的收斂速度快,算法的復(fù)雜度相對于并行MPA算法更低。雖然并、串MPA算法的復(fù)雜度比ML算法降低了2倍～3倍,但算法復(fù)雜度依然保持在104的數(shù)量級,硬件實(shí)現(xiàn)并不容易。并、串MAX-Log MPA雖然誤碼率性能有所降低,但其算法復(fù)雜度卻是最低的,除了加法器和乘法器以外,也不存在特別復(fù)雜的函數(shù)運(yùn)算。另外,對比這5種算法,本文提出的基于對數(shù)域的串行MAX-LogMPA算法不但繼承了MAX-Log運(yùn)算低復(fù)雜度的特點(diǎn),又繼承了串行策略收斂速度快的特性,其算法復(fù)雜度比并行MAX-Log MPA更低,是5種算法中最低的,硬件實(shí)現(xiàn)也更加容易。

圖7 不同策略的算法運(yùn)算復(fù)雜度對比

5 結(jié)束語

本文對采用不同策略的MPA算法進(jìn)行闡述,并結(jié)合串行MPA算法和MAX-Log運(yùn)算兩者之間的優(yōu)點(diǎn),提出一種串行MAX-LogMPA算法。通過對收斂速度、誤碼率性能、算法復(fù)雜度3個方面的仿真實(shí)驗(yàn)對比,可以發(fā)現(xiàn):采用串行MPA與并行MPA的誤碼率性能一樣;并、串MAX-Log MPA兩者的誤碼率性能相對較差,算法復(fù)雜度低,硬件實(shí)現(xiàn)容易。綜合來看,串行MPA算法比并行MPA多用戶檢測算法更優(yōu)。串行MAX-LogMPA算法的算法復(fù)雜度進(jìn)一步降低,硬件實(shí)現(xiàn)更加容易。

[1] SOLDANI D,MANZALINI A.Horizon 2020 and beyond:on the 5G operating system for a true digital society[J].IEEE Vehicular Technology Magazine,2015,10(1):32-42.

[2] WANG Bichai,WANG Kun,LU Zhaohua,et al.Comparison study of non-orthogonal multiple access schemes for 5G[C]//Proceedings of IEEE International Symposium on Broadband Multimedia Systems and Broadcasting.Washington D.C.,USA:IEEE Press,2015:1-5.

[3] NIKOPOUR H,BALIGH H.Sparse code multiple access[C]//Proceedings of IEEE International Symposium on Personal Indoor and Mobile Radio Communications.Washington D.C.,USA:IEEE Press,2013:332-336.

[4] HOSHYAR R,WATHAN F P,TAFAZOLLI R.Novel low-density signature for synchronous CDMA systems over AWGN channel[J].IEEE Transactions on Signal Processing,2008,56(4):1616-1626.

[5] BEEK J V D,POPOVIC B M.Multiple access with low-density signatures[C]//Proceedings of IEEE Global Telecommunications Conference.Washington D.C.,USA:IEEE Press,2009:1-6.

[6] RAZAVI R,HOSHYAR R,IMRAN M A,et al.Information theoretic analysis of LDS scheme[J].IEEE Communications Letters,2011,15(8):798-800.

[7] TAHERZADEH M,NIKOPOUR H,BAYESTECH A,et al.SCMA codebook design[C]//Proceedings of IEEE Vehicular Technology Conference.Washington D.C.,USA:IEEE Press,2014:14-17.

[8] ZHANG Shunqing,XU Xiuqiang,LU Lei,et al.Sparse code multiple access:an energy efficient uplink approach for 5G wireless systems[C]//Proceedings of IEEE Global Telecommunications Conference.Washington D.C.,USA:IEEE Press,2014:4782-4787.

[9] AU K,ZHANG Liqing,NIKOPOUR H,et al.Uplink contention based SCMA for 5G radio systems[C]//Proceedings of IEEE Global Telecommunications Con-ference.Washington D.C.,USA:IEEE Press,2014:900-905.

[10] LU Lei,CHEN Yan,GUO Wenting,et al.Prototype for 5G new air interface technology SCMA and performance evaluation[J].China Communications,2015,12(s1):38-48.

[11] DU Yang,DONG Binhong,CHEN Zhi.Joint sparse graph-detector design for downlink MIMO-SCMA system[J].IEEE Journals & Magazines,2017,6(1):14-17.

[12] WU Yiqun,ZHANG Shunqing,CHEN Yan.Iterative multiuser receiver in sparse code multiple access systems[C]//Proceedings of IEEE International Conference on Communications.Washington D.C.,USA:IEEE Press,2015:2918-2923.

[13] DU Yang,DONG Binhong,CHEN Zhi,et al.A fast convergence multiuser detection scheme for uplink SCMA systems[J].IEEE Wireless Communications Letters,2016,5(4):388-391.

[14] 杜 洋,董彬虹,王顯俊,等.基于串行策略的SCMA多用戶檢測算法[J].電子與信息學(xué)報,2016,38(8):1888-1893.

[15] KSCHISCHANG F R,FREY B J,LOELIGER H A.Factor graphs and the sum-product algorithm[J].IEEE Transactions onInformation Theory,2001,47(2):498-519.