一種低復雜度SCMA多用戶檢測算法

朱翠濤，吳 蓓

(中南民族大學 智能無線通信湖北省重點實驗室，湖北 武漢 430074)

稀疏碼多址接入(Sparse Code Multiple Access，SCMA)，是應(yīng)5G需求設(shè)計產(chǎn)生的一種非正交多址技術(shù)。其非正交疊加的碼字個數(shù)可以成幾倍大于使用的資源塊個數(shù)，從而大大提高了頻譜利用率。為了使稀疏碼多址接入成為更具競爭力的空口技術(shù)，需要解決的關(guān)鍵問題是性能優(yōu)良的碼本設(shè)計及低復雜度的多用戶檢測算法。筆者研究的重點在于多用戶檢測算法。

利用稀疏碼多址接入碼字的稀疏結(jié)構(gòu)[1]，基站能夠通過低復雜度的消息傳遞算法(Message Passing Algorithm，MPA)實現(xiàn)接近最大后驗概率檢測和最大似然檢測。然而，在多用戶情況下，各用戶的發(fā)送信號在接收端疊加[2]，隨著用戶數(shù)的增加，消息傳遞算法譯碼的復雜度將呈指數(shù)增長。為了減少復雜度，文獻[3]提出了線性濾波高斯近似置信傳播算法，迭代地消除干擾。文獻[4-5]提出了邊選擇高斯近似算法，將信道質(zhì)量作為邊選擇的標準，對部分邊使用高斯近似。文獻[6]基于天線和子載波，結(jié)合了最大似然和高斯近似兩種檢測方法。文獻[7]基于滑行窗口，選擇活躍用戶參與信號檢測和信道譯碼，而部分不活躍用戶將干擾近似為高斯隨機變量。文獻[8]中提出了一種低復雜度的高斯近似算法，將不連續(xù)消息近似為連續(xù)高斯分布消息，使復雜度從指數(shù)增長降為線性增長。文獻[9]基于最小化相對熵，通過在非正交多址接入系統(tǒng)中使用高斯近似的方法降低復雜度，該方法同樣適用于稀疏碼多址接入系統(tǒng)。

綜上所述，在上行稀疏碼多址接入系統(tǒng)中，為了進一步降低多用戶檢測算法的復雜度，提出了一種基于部分資源塊高斯近似的多用戶檢測算法。此算法中，稀疏碼多址接入因子圖將變成動態(tài)且更為稀疏的因子圖，通過合理選擇資源塊個數(shù)n來降低檢測的復雜度。

1 系統(tǒng)與信號模型

在上行稀疏碼多址接入系統(tǒng)中，假設(shè)有J個用戶，K個時頻資源塊，過載因子可以表示為λ=J/K。每個用戶都有不同的碼本，Xj為第j個用戶的碼本，M是碼本中碼字個數(shù)(即碼本大小)，bj是二進制信息。對于每一個用戶j(j=1,2,…,J)，編碼比特流bj通過編碼器映射為碼本中的碼字xj。稀疏碼多址接入碼字的稀疏性，可以通過兩類碼字非零位置的集合表示。Rj為第j個用戶占用資源塊的集合，F(xiàn)k為第k個資源塊上分布用戶的集合，對應(yīng)每列和每行非零元素的數(shù)量分別為dJ和dR。

不同用戶信號非正交疊加，經(jīng)過信道傳輸后，基站在第k個時頻資源塊上的接收信號可以表示為

(1)

式中，hk,j表示時頻資源塊k上用戶j的信道系數(shù)，nk表示在時頻資源塊k上所疊加的加性高斯白噪聲。

2 消息傳遞算法性能分析

由于稀疏碼多址接入碼字具有稀疏性，因此可以利用消息傳遞算法[10]對稀疏碼多址接入系統(tǒng)中多用戶進行檢測，從而降低檢測算法的復雜度。稀疏碼多址接入的結(jié)構(gòu)可以用指示矩陣和因子圖來表示，如圖1所示。一般地，在因子圖中有兩類節(jié)點，方形代表資源節(jié)點rk，也表示時頻資源塊k，圓形代表用戶節(jié)點uj，也表示用戶j。而在指示矩陣中，行代表時頻資源塊，列代表用戶。fk,j=1，表示第k個資源塊和第j個用戶相連。

圖1 稀疏碼多址接入指示矩陣和因子圖關(guān)系

消息傳遞算法的檢測過程可以分為3步:

(1)計算初始概率,即

(2)

(2)消息迭代更新，更新資源節(jié)點和用戶節(jié)點,即

(3)

(4)

式中，～xj表示符號xj的邊緣概率;l∈Fk/j,表示在第k個資源塊上分布的用戶集合Fk中除去用戶j以外的其余用戶;m∈Rj/k,表示第j個用戶所占用的資源塊集合Rj中除去資源塊k以外的其余資源塊。

(3)在達到最大迭代次數(shù)tmax后，計算用戶各碼字輸出概率,即

(5)

基于并行調(diào)度策略的消息傳遞算法，對所有消息以并行的方式進行更新[11]，導致收斂速度慢。因此可以串行更新消息，已更新的消息在同一次迭代過程中及時參與其他節(jié)點的消息更新，從而有效地提高收斂速度。串行消息傳遞算法(Serial Message Passing Algorithm，SMPA)中資源節(jié)點更新可以表示為

(6)

雖然串行消息傳遞能加快收斂速度，但是消息傳遞算法的復雜度問題并未得到解決。從原始消息傳遞算法檢測過程來看，復雜度主要來自于資源節(jié)點更新[12]，其總的乘法計算量約為tmaxKMdR。為了降低復雜度，最有效的方法就是減小參數(shù)tmax以及dR。而從因子圖的結(jié)構(gòu)來看，如果只有部分邊參與到資源節(jié)點給用戶節(jié)點更新中，其余邊傳遞的消息近似為高斯分布，那么通過合理選擇，就可以在復雜度和性能之間進行靈活調(diào)節(jié)，從而應(yīng)用到多種場合中?；诖耍P者提出了基于部分資源塊高斯近似的消息傳遞算法(Partially Gaussian Approximation-Message Passing Algorithm，PGA-MPA)。

3 基于部分資源塊高斯近似的消息傳遞算法

PGA-MPA算法的基本思想是對部分資源塊使用加權(quán)消息傳遞算法，而剩下的資源塊使用高斯近似消息傳遞算法。另外，每次迭代后剔除1個用戶，這樣不但能保證誤碼率(Symbol Error Rate，SER)性能，還能有效降低多用戶檢測復雜度。此算法需要解決三個關(guān)鍵問題：一是選擇哪部分消息近似為高斯變量，二是如何進行高斯近似，三是選擇怎樣的用戶進行剔除。

下面將進行具體介紹。

3.1 資源塊優(yōu)勢等級分析

通過大量實驗發(fā)現(xiàn)，在稀疏碼多址接入系統(tǒng)中，基于消息傳遞算法對部分資源塊進行高斯近似時，資源塊存在譯碼優(yōu)勢等級。按照時頻資源塊被處理的先后順序，給每個時頻資源塊分配一個優(yōu)勢等級，例如給時頻資源塊k分配的優(yōu)勢等級依次為1,2,3,…，K。優(yōu)勢等級越高，表示譯碼優(yōu)勢越大，譯碼的可靠性越高。于是，選擇譯碼優(yōu)勢等級較高的n個資源塊進行消息加權(quán)，剩下的譯碼優(yōu)勢等級較低的資源塊進行高斯近似。

假設(shè)有6個用戶，4個時頻資源塊。當n=4時，所有資源塊在資源節(jié)點更新時進行消息加權(quán)；當n=0時，相當于在資源節(jié)點更新時對所有外部消息進行高斯近似?；诓糠仲Y源塊的高斯近似則介于兩者之中。當n=3時，表示有3個優(yōu)勢等級較高的資源塊進行消息加權(quán)，剩下的一個資源塊進行高斯近似。同理可得，當n取值為2和1時，表示分別有優(yōu)勢等級較高的兩個資源塊和一個資源塊進行消息加權(quán)，剩下的資源塊進行高斯近似。

3.2 基于高斯近似的消息傳遞算法

圖2 高斯近似的資源節(jié)點更新示意圖

在一次迭代過程中，當資源節(jié)點進行更新時，資源節(jié)點利用用戶節(jié)點傳來的消息更新對應(yīng)的用戶節(jié)點。若將這些外部消息視作干擾，則干擾和噪聲項[13]可以近似為高斯分布。

圖2所示是高斯近似的資源節(jié)點更新過程，其中同一資源塊上疊加的用戶數(shù)dR=3。在因子圖中，當資源塊k對用戶j傳遞消息時，在連接到同一資源塊的所有用戶邊中，只有一條邊ek,j傳遞消息，而對其余邊傳遞的消息近似為高斯分布，因此用戶有效邊數(shù)d=1。式(1)可以改寫為

(7)

假設(shè)信道系數(shù)hk,j服從獨立同分布的高斯分布，均值為0，方差為1;噪聲nk為加性高斯噪聲，均值為0，方差為σ2。將干擾噪聲項近似為高斯分布，其中Zk,j～Ν(μΖk,j,σZk,j)。

為了提高性能，可以使均值參與迭代。將當前迭代中更新的均值作為反饋信息用在下一次迭代中，并且參與資源節(jié)點的更新過程，方差則保持初始值不變，不進行迭代更新。因此，在第t次迭代過程中，均值和方差分別為

(8)

(9)

于是，基于均值迭代的資源節(jié)點更新為

(10)

由于接收信號與疊加碼字組合之間的關(guān)系，可以用歐氏距離表示。距離越短，代表疊加碼字組合越靠近接收信號，正確解的概率越大。因此，通過加權(quán)因子改變初始概率[14]，越靠近接收信號，獲得的初始概率越大，從而提高正確譯碼率。

首先，將初始概率按照從大到小的順序進行排序，劃分為Q個集合，相同集合分配相同的加權(quán)因子，不同集合分配不同的加權(quán)因子。疊加碼字的概率值越大，就會獲得越大的加權(quán)因子，其滿足下式：

(11)

然后，將初始概率與相應(yīng)的加權(quán)因子αq相乘，使得越靠近接收信號，獲得越大的初始值。根據(jù)式(2)，初始概率的計算為

Φk=αq·Φk。

(12)

3.3 聯(lián)合資源塊和用戶優(yōu)勢等級

為了進一步降低算法的復雜度，聯(lián)合資源塊和用戶優(yōu)勢等級，根據(jù)資源塊優(yōu)勢等級排序以及用戶碼字結(jié)構(gòu)，可以得到用戶優(yōu)勢等級。將譯碼優(yōu)勢用戶進行降序排列，在每次迭代后對譯碼優(yōu)勢等級較高的用戶直接譯碼并剔除[15]。

圖3 每次迭代剔除1個用戶

如圖3所示，有6個用戶，4個時頻資源塊。根據(jù)圖1中稀疏碼多址接入因子矩陣的結(jié)構(gòu)，從上至下，依次給每行時頻資源塊分配1,2,3,4，總共4個優(yōu)勢等級，那么根據(jù)每列中用戶占用資源塊的集合，即非零元素的位置，就可以計算出每個用戶的優(yōu)勢等級。例如用戶1的非零元素集合R1={2，4}，則用戶優(yōu)勢等級為資源塊優(yōu)勢等級2和4相加，結(jié)果為6；用戶2的非零元素集合R2={1，3}，則用戶優(yōu)勢等級為資源塊優(yōu)勢等級1和3相加，結(jié)果為4。同樣的方法，計算出其余4個用戶的優(yōu)勢等級分別為3,7,5,5。于是，按照優(yōu)勢等級的降序排序，第1次迭代剔除的是用戶4，第2次迭代剔除的是用戶1，后面依次剔除用戶5、用戶6、用戶2以及用戶3。在6次迭代后所有用戶都被譯碼。

原始消息傳遞算法的復雜度主要在于資源節(jié)點更新，且主要與tmaxKMdR有關(guān)?；诓糠仲Y源塊高斯近似的消息傳遞算法降低了與復雜度相關(guān)的重要參數(shù)dR，即單個資源塊上所疊加的用戶數(shù)，進行消息加權(quán)的資源塊個數(shù)n(1≤n

表1為兩種算法的復雜度比較，其中Οt=f(t,n,M,dR,K)。在每次迭代過程中，資源節(jié)點進行更新時，連接到同一資源塊的用戶有效邊數(shù)1≤d≤dR，并且隨著每次迭代剔除一位用戶，復雜度將越來越小。與此同時，改變消息調(diào)度策略以及引入加權(quán)因子能提升收斂速度，從而進一步減少迭代所需次數(shù)tmax。

表1 復雜度比較

筆者提出算法的主要改進在于降低了最大迭代次數(shù)tmax以及參數(shù)dR。由于限制了這兩個關(guān)鍵因素，因此有效地降低了復雜度。針對5G海量連接的需求，當承載用戶數(shù)量越大時，基于部分資源塊高斯近似的消息傳遞算法在降低計算復雜度上的優(yōu)勢將更為明顯。

4 仿真與分析

對提出算法的誤碼率性能和收斂速度進行仿真分析。仿真中所用碼本為華為公司給出的6×4碼本，以及文獻[16]中提出的基于網(wǎng)格編碼調(diào)制的子集分割碼本。參數(shù)設(shè)置為：碼本大小M=4，時頻資源塊數(shù)K=4，用戶數(shù)J=6，每個用戶占用時頻資源塊數(shù)dJ=2，每個時頻資源塊上疊加用戶數(shù)dR=3。

圖4 不同算法的誤碼率性能比較

圖5 未改變碼本時誤碼率性能比較

圖4為在3次迭代下，原始消息傳遞算法、串行消息傳遞算法以及全部高斯近似消息傳遞算法(Gaussian Approximation-Message Passing Algorithm，GA-MPA)的譯碼性能情況。從圖4中可以看出，在迭代次數(shù)相同時，串行消息傳遞算法的誤碼率性能優(yōu)于原始消息傳遞算法，說明基于串行消息傳遞機制要比基于并行消息傳遞機制更有優(yōu)勢。串行消息傳遞算法并不能降低復雜度，所以在串行消息傳遞機制的基礎(chǔ)上，可以結(jié)合高斯近似的方法，進一步降低復雜度。另外，由于全部高斯近似不能充分利用外部消息，誤碼率性能較差，因此采用部分高斯近似方法。

圖5為在3次迭代下，原始消息傳遞算法、全部高斯近似消息傳遞算法以及部分高斯近似消息傳遞算法的譯碼性能情況。從圖5中可以看出，采用部分高斯近似算法時誤碼率性能得到了改善，但是曲線的收斂情況仍然不是很好。為了進一步改善檢測性能，改變?nèi)A為公司提出的碼本，采用基于網(wǎng)格編碼調(diào)制的子集分割碼本，在不增加功率和頻帶利用率的條件下，降低系統(tǒng)的誤碼率。

圖6 改變碼本時誤碼率性能比較

圖7 收斂速率比較

圖6為在改變碼本情況下的譯碼性能情況。從圖6中可以看出，誤碼率性能得到了明顯的提升，尤其是當信噪比升高時，性能提升更為明顯。原始消息傳遞算法因為在資源節(jié)點更新時有效利用了所有節(jié)點的消息，所以性能最好。部分高斯近似比全部高斯近似性能好，并且隨著進行消息加權(quán)的資源塊個數(shù)n的增加，誤碼率性能越來越好，越接近原始消息傳遞算法。

圖7為在采用子集分割碼本情況下不同算法的收斂速率比較，其中信噪比為12dB。由于每次迭代后將剔除一位優(yōu)勢等級較高的用戶，而6次迭代后所有用戶都被譯碼，因此只給出部分高斯近似前6次迭代的收斂曲線。從圖7中可以看出，原始消息傳遞算法在迭代次數(shù)達到5次后誤碼率才趨于穩(wěn)定，全部高斯近似算法也需要迭代5次。隨著n的不同，部分高斯近似算法需要的迭代次數(shù)也不同。當n=1時，需要3次迭代；當n=2時，同樣需要3次迭代；當n=3時，只需要2次迭代。n越大，達到收斂時迭代次數(shù)越低，并且都小于其他兩種算法所需迭代次數(shù)。另外，在迭代次數(shù)為1時，部分高斯近似算法在n=3的情況下要比原始消息傳遞算法的誤碼率小。隨著迭代次數(shù)的增加，原始消息傳遞算法的誤碼率減小，性能更好。降低計算復雜度會在一定程度上帶來性能損失，但是筆者提出的算法能夠在誤碼率性能損失不大的情況下，極大程度地降低檢測復雜度，并且能根據(jù)實際需要，通過改變參數(shù)n選擇算法的誤碼率性能與計算復雜度。

5 結(jié)束語

針對多用戶檢測算法復雜度高的問題，筆者提出一種基于部分資源塊高斯近似的多用戶檢測算法。此算法在資源節(jié)點更新時對部分譯碼優(yōu)勢等級較低的資源塊使用高斯近似，并且聯(lián)合資源塊和用戶優(yōu)勢等級，在每次迭代后剔除譯碼優(yōu)勢等級較高的用戶，通過合理設(shè)置資源塊個數(shù)，能夠保證譯碼性能，降低譯碼復雜度。高斯近似尤其適用于承載大量用戶的系統(tǒng)中，因此如何在多天線稀疏碼多址接入系統(tǒng)中使用高斯近似來降低多用戶檢測的復雜度，將是下一步研究的主要內(nèi)容。