基于迭代剔除的SCMA多用戶檢測算法

朱翠濤，韋寧，汪漢新，李中捷

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

1 引言

面向5G的非正交多址技術比正交多址具有更高的可達容量，因此得到業界的廣泛關注[1-2]。SCMA[3-4]是一種非正交多址技術，具有獨特的編碼優勢。SCMA由低密度簽名序列碼分多址（LDS-CDMA, low density signature-code-division multiple access）發展而來[5]，不同于 LDS-CDMA的是，SCMA把調制與擴頻結合起來，直接把用戶發送的數據比特流映射成預定義稀疏碼本中的多維稀疏碼字。因此，SCMA獲得了LDS-CDMA中沒有的成形增益，其誤碼率性能也比LDS-CDMA好。然而，SCMA要正式成為5G選用的空口技術[6]，高效的多用戶檢測是要解決的關鍵技術之一。

利用SCMA碼字結構具有的稀疏特性，文獻[7]提出了一種基于消息傳播（MPA, message passing algorithm）的次優多用戶檢測算法，用來有效接近理論上最優的最大聯合后驗概率（MAP, maximum joint a posteriori probability）譯碼算法的性能。雖然MPA譯碼算法的復雜度遠小于MAP譯碼算法，但隨著用戶數的增加，MPA譯碼算法的復雜度呈指數增加，不利于應用于實際系統中。文獻[8]在 MPA的基礎上提出了MAX-Log MPA算法，利用雅克比公式變換到對數域，使 MPA算法中的指數運算消失，降低了復雜度。文獻[9]提出了基于部分邊緣化的MPA算法，在降低MPA算法復雜度的同時保證譯碼性能，但該算法所引入的重要參數取值需進一步探討。文獻[10]提出了串行干擾消除（SIC, successive interference cancellation）和基于串行干擾消除的MPA（SIC-MPA）2種譯碼算法，SIC算法復雜度較低，而譯碼性能較差，SIC-MPA算法的復雜度適中，譯碼性能較好，但這2種算法都需要在發送端改變原有編碼規則和多維調制星座圖設計的支持。文獻[11]給出了多種降低MPA譯碼算法復雜度的方法，ProjMPA、CMPA和 SelEXP-MPA，但只對ProjMPA進行了仿真分析，而且涉及多維調制星座圖和碼本的最優設計，譯碼性能有待驗證。文獻[12]提出了 WMPA譯碼算法，其原理是對 MPA算法進行加權處理，以加權取代了原 MPA算法的迭代運算，降低了算法的復雜度，再結合Turbo編碼，可以取得較好的譯碼性能。文獻[13]在MPA的基礎上，改變消息傳播的機制，以串行消息傳播取代原來的并行消息傳播，使消息的傳播更及時，加快了MPA算法的收斂速度，降低MPA算法所需的迭代次數。文獻[14]提出基于門限的MPA算法，根據碼字的可靠性，用戶被分成可靠用戶集和不確定用戶集，每次迭代過后都要對用戶消息的可靠性進行檢測并與門限值比較，若用戶消息的可靠性達到了門限的要求則對此用戶進行譯碼并將其放到可靠用戶集中，且不再對可靠用戶集里的用戶進行消息的更新，若用戶消息的可靠性達不到門限值的要求，則將此用戶放到不確定用戶集中，然后再對不確定用戶集中的所有用戶進行下一輪迭代，此方法雖然能夠降低譯碼的復雜度，但由于用戶消息的隨機性比較大，若門限值取值不恰當，則很難達到降低MPA算法復雜度的效果。SCMA與大規模MIMO技術相結合[15-16]，將進一步提高系統的頻譜資源利用率，但多用戶檢測將更加復雜，低復雜度的多用戶檢測方法顯得更加重要。

綜上分析，本文提出了基于迭代剔除的SCMA多用戶檢測算法，主要思想是利用SCMA編碼結構特點，算法邊迭代邊檢測出一部分用戶，而不是在算法迭代完畢后才將所有用戶統一檢測出。此算法的優勢在于隨著迭代次數的增加，每次迭代的復雜度逐步降低。算法的主要實現過程如下。首先對用戶的譯碼優勢進行分析并排序，然后在每一輪迭代后，找到譯碼可靠性高的前n個用戶直接進行譯碼并剔除，被剔除的用戶不再參與后續的迭代運算，則每一輪迭代過后，未譯碼的用戶數越來越少，所以隨著迭代次數的增加，此算法每一次迭代的復雜度也會隨著降低，并提出了2種迭代剔除策略：基于譯碼優勢用戶排序剔除策略和正交用戶分組剔除策略，前者每輪迭代剔除的用戶數可變，比較靈活，后者每輪迭代剔除的用戶數固定，但在剔除的用戶數相同時，后者的復雜度要低于前者。

2 系統與信號模型

假定一個擁有J個用戶共享K個時頻資源塊的上行SCMA系統，用戶 j( j = 1 ,2,… ,J )發送的數據比特流 bj被映射成K維碼字向量 xj， xj從長度為M的對應用戶碼本χj中取得，每個碼字都是包含N＜K個非零元素的K維稀疏向量。在非正交環境下，用戶數J要大于時頻資源塊數K，則系統過載率為：。用戶多路復用信號經過同步后，基站接收到的信號表示為

j對角元素構造的對角矩陣。那么，時頻資源塊k處接收到的信號為

SCMA系統的編碼結構可以用編碼指示矩陣F=( f1, f2,… ,fJ)來表示，其中，fj=(f1,j, f2,j,是用戶j的編碼指示向量，當時，表示用戶j占用時頻資源塊k。除了編碼指示矩陣外，也可利用因子圖表示SCMA系統的編碼結構，當變量節點 j與功能節點k相連時 fk,j= 1 ，否則fk,j= 0 ，一個因子圖與F矩陣對應關系的例子如圖1所示。分別用 df和 dc表示矩陣F中每一行和每一列元素為1的個數，則集合 ?j= { k | fk,j= 1 }和集合 ζk= { j | fk,j= 1 }分別表示用戶j占用的時頻資源塊集和占用時頻資源塊k的用戶集。因為SCMA碼字的稀疏特性，使每個時頻資源塊上實際疊加的用戶碼字個數要遠小于J，所以式(2)可以改寫為

圖1 SCMA編碼結構的因子圖與F矩陣對應關系

圖1 中，rk為功能節點，也表示時頻資源塊k，uj為變量節點，也表示用戶j。每個變量節點與 2個功能節點相連，表示每個用戶占用2個時頻資源塊；每個功能節點與3個變量節點相連，表示每個時頻資源塊同時被3個用戶占用。相應地，在F矩陣中，每一行代表一個時頻資源塊，每一列代表一個用戶的碼字結構，每一行中元素為1的位置表示占用此資源塊對應的用戶，每一列中元素為1的位置表示此用戶所占用的對應資源塊。

3 MPA譯碼算法及性能分析

理論上，最優的SCMA系統譯碼算法是MAP算法，但其復雜度高，難以將其應用于實際通信系統中。利用SCMA碼字所具有的稀疏特性，可以用次優的MPA算法來進行譯碼。MPA算法有2種消息傳播機制，即為并行消息傳播與串行消息傳播，并行消息傳播是指在每輪迭代過程中，先更新全部功能節點，再去更新所有變量節點，而串行消息傳播是更新一個功能節點，便去更新與這個功能節點相關的變量節點[17]，本文把基于這2種消息傳播的MPA算法分別記為PMPA和SMPA。如圖1中的因子圖所示，PMPA算法通過接收外部信息，先后更新功能節點集 R N{rk}與變量節點集 U N{uj}來改變用戶碼字的概率分布[18]，功能節點與變量節點的更新分別表示為

由式(4)和式(5)可知，在 PMPA 算法中，本輪迭代產生的新消息要等到下一輪迭代才會用上，而SMPA算法不是先后更新功能節點與變量節點，它更新一個功能節點便去更新與之相關的變量節點，使本輪迭代更新過的功能節點消息可被用于同一輪中其他功能節點的更新，SMPA算法中變量節點的更新與PMPA算法相同，不同的是SMPA算法中變量節點的更新緊接于每一個功能節點的更新之后，SMPA算法中功能節點的更新可以表示為

其中，lj＜和lj＞分別表示在用戶j之前和之后的用戶l。從式(7)可以看出，在本輪迭代更新部分功能節點時已經用到了本輪迭代更新過的變量節點的消息，顯然本輪更新過的變量節點消息比上一輪變量節點的消息要更可靠，即SMPA算法中的消息傳播更及時，使其收斂速度更快。

4 基于迭代剔除的多用戶檢測

受博弈論中迭代剔除劣勢理論和串行干擾消除算法的啟發，本文所提 RM-MPA算法把每一輪迭代后譯碼可靠的用戶檢測出來并剔除，使其不參與到下一輪的迭代，這樣，隨著算法迭代次數的增加，參與迭代的用戶數就越少，其復雜度就越來越低。此算法的核心問題有2個，一是如何確定本輪迭代中哪些用戶的譯碼可靠性高，可以不再參與多次迭代就能夠直接進行正確譯碼，這樣在將其剔除的同時，不會因為差錯傳播原理造成后譯碼用戶的譯碼錯誤；二是采取怎樣的剔除策略，才能在很好地降低復雜度的同時，保證譯碼的性能。下面，將對這些問題的實現過程進行詳細說明。

4.1 RM-MPA譯碼優勢用戶分析

本文所提 RM-MPA譯碼算法既適合用串行消息傳播機制，也能用并行消息傳播機制，但采用并行消息傳播機制的 RM-MPA算法要在迭代次數達到一定次數后才能進行用戶的譯碼和剔除操作，而采用串行消息傳播機制的 RM-MPA算法在第一次迭代過后就能進行用戶的譯碼和剔除。因為并行消息傳播機制收斂速度較慢，而且每輪迭代所有用戶的譯碼優勢相同，不存在譯碼優勢用戶問題，所以在迭代次數較低時，用戶的譯碼可靠性不高，不能直接進行譯碼和剔除。本文通過大量的仿真實驗也發現串行消息傳播機制更適合 RM-MPA算法，所以下面只對采用串行消息傳播機制的 RM-MPA算法進行分析。以)表示第t次迭代中時頻資源k上用戶 j進行消息更新時用到本次迭代中產生的外部消息個數，定義為

按照本文提出的RM-MPA算法中時頻資源被處理的先后順序，給每個時頻資源分配一個優勢等級，等級越高，其譯碼優勢就越大，譯碼的可靠性也就越高。例如，給時頻資源 k = 1 ,2,3,… , K 分配相應的優勢等級 lk= 1 ,2,3,… , K ，則用戶j的譯碼優勢等級為

如式(10)所示，按此方法求一個用戶的譯碼優勢等級只需要知道該用戶自身的碼字結構即可，比采用外部消息來比較用戶間的譯碼優勢更簡單。將RM-MPA算法中所有用戶按譯碼優勢等級進行降序排序，即可得出用戶譯碼可靠性的排序，進而剔除譯碼可靠用戶，再進行下一輪迭代。圖2是一個RM-MPA譯碼優勢用戶分析的例子。

圖2 RM-MPA譯碼優勢用戶分析

圖2 表示的是一個擁有4個時頻資源塊，6個用戶的SCMA系統的編碼指示矩陣F，其行和列分別表示時頻資源塊和用戶的編碼結構。可以看出，通過和 a 計算出來的譯碼優勢用戶排序j是相同的，而且用戶的譯碼優勢越大，其譯碼可靠性就越高。從圖2中也可直觀地看出，由于串行消息傳播機制本身特有的性質，使越靠后處理的時頻資源塊，其輸出的消息越可靠，所以在同一次迭代中占用的時頻資源塊越是靠后的用戶，其譯碼的可靠性也就越高。在此基礎上本文提出了2種迭代剔除策略。

4.2 迭代剔除策略

4.2.1 譯碼優勢用戶排序剔除策略

因為迭代剔除存在差錯傳播問題，所以每次迭代過后剔除用戶的譯碼可靠性越高越好，綜上分析，RM-MPA譯碼算法中用戶的譯碼優勢越大，其譯碼可靠性就越高。因此，可依據譯碼優勢從高到低對用戶進行排序，在每次迭代后對譯碼優勢用戶排序中的前n個用戶直接譯碼并剔除，假設K能被N整除。被剔除的n個用戶不再參與到后續的迭代過程，則每次迭代過后用戶數都相應地減少n個，若在最大迭代次數maxt 到來之前，所有的用戶數已被譯碼并剔除，表明算法不需要那么多次迭代運算，而在達到最大迭代次數maxt后，對剩余的所有未被譯碼的用戶統一進行譯碼。可以預見的是，每次迭代過后剔除的用戶數越多，譯碼算法整體的復雜度越低，但為了保證RM-MPA算法的譯碼性能，并考慮差錯傳播的影響，此剔除策略并不是最優的。因此，在此基礎上提出了正交用戶分組剔除策略。基于譯碼優勢用戶排序剔除的RM-MPA算法的具體步驟如下所示。

1) 初始化

2) 譯碼優勢用戶排序

3) 信息迭代更新

4) 用戶剔除

5) 剔除用戶譯碼

6) 剩余用戶譯碼

4.2.2 正交用戶分組剔除策略

在一個 SCMA系統中，若每個用戶占用一個數據流層，則最多能容納的用戶數為CNK個，相應地，F矩陣中用戶指示向量jf的個數最多也只有CNK個，若按向量間的正交性進行分組，這些用戶指示向量一共可以分成個向量組[19]，每組含有個向量，而且同組內的各個用戶指示向量 fj是相互正交的。每個用戶指示向量對應一個用戶，則同一組內的用戶都占用不同的正交時頻資源塊，即同一組內的用戶相互之間無干擾，所以把這種分組方式稱為正交用戶分組。若每組內的用戶個數相同，且組內所有用戶一起占用了所有的時頻資源塊，則稱為正交完全用戶分組，否則稱為正交非完全用戶分組。如圖2所示的K = 4 ,N = 2 ,J = 6 的指示矩陣F中，用戶指示向量fj的個數最多為 C24= 6 ，f1與 f6、f2與 f5、f3與 f4都是兩兩相互正交的列向量，則它們可以兩兩進行分組，一共可以分成 C13= 3 組，與它們相對應的用戶也可兩兩進行分組，即 u1與 u6為一組，u2與 u5為一組，u3與 u4為一組，一共分為 3個用戶組，組內的用戶相互正交。

在正交用戶分組的基礎上，正交用戶分組剔除策略的過程如下。在每次迭代過后隨機的選擇一個正交用戶組，對組內所有用戶直接譯碼并剔除。若是正交完全用戶分組，通過式(9)或式(10)可知，經過正交用戶分組后，每個正交用戶組內所有用戶的譯碼優勢之和是一樣的，即正交用戶組之間并沒有譯碼優勢問題，所以可以隨機檢測并剔除任意一個正交用戶組。基于正交用戶分組剔除的 RM-MPA算法的具體步驟和基于譯碼優勢用戶排序剔除的 RM-MPA算法的具體步驟相似，不同于譯碼優勢用戶排序剔除的是，正交用戶分組剔除不用執行算法的第2)步，而且第4)步中也不是剔除前n個譯碼優勢用戶，而是隨機的剔除任一個正交用戶組里所有的用戶。圖3是一個基于正交用戶分組剔除的 RM-MPA算法每次迭代的因子。

圖3 基于正交用戶分組剔除的RM-MPA算法因子

圖3 是一個擁有4個功能節點，6個變量節點的RM-MPA算法因子。RM-MPA譯碼算法的消息傳遞是沿著功能節點與變量節點間的實線傳遞的，實線越多要傳遞的消息越多，計算量也就越大。從圖3中可看出，執行用戶剔除操作之后，隨著迭代次數t的增加，因子圖中功能節點與變量節點之間的實線也相應的減少，所以隨著迭代次數的增加，基于正交用戶分組剔除的 RM-MPA譯碼算法每次迭代的復雜度依次降低。

4.3 復雜度分析

從PMPA與SMPA的譯碼過程中可知，這2種算法的復雜度主要來自功能節點的更新，變量節點與后驗概率的更新占整個算法復雜度的比重很小，所以本文主要從功能節點更新的復雜度上進行分析。在每次迭代中PMPA與SMPA在復雜度上唯一不同的是：SMPA的用戶碼字后驗概率的更新是PMPA中的fd倍，而后驗概率的更新只需要少數幾個加法運算。表1是幾種算法每一次迭代中功能節點更新的復雜度比較。

如表1所示，RM-MPA-URS與RM-MPA-OUGR分別表示基于譯碼優勢用戶排序剔除的 RM-MPA算法與基于正交用戶分組剔除的RM-MPA算法，n表示每次剔除的用戶數。RM-MPA-OUGR每次迭代的復雜度隨著迭代次數的每次增加都相應減少一個數量級，而RM-MPA-URS的復雜度與多個參數有關，即 Οt= f(t ,,K,N,M ,J )。式(11)和式(12)分別表示進行 tmax次迭代后，SMPA算法與RM-MPA-OUGR的復雜度。

表1 復雜度比較

從式(11)與式(12)的比較中可以發現，maxt 、M與fd越大，RM-MPA-OUGR復雜度增加得越少，而RM-MPA-URS的復雜度則介于這兩者中間，可權衡復雜度與譯碼性能，選擇適當的剔除策略配合RM-MPA譯碼算法。

5 仿真與分析

因為譯碼算法的收斂速率對迭代剔除機制的影響很大，特別是第一次迭代后用戶譯碼的可靠性越高越好。所以本文先比較了 PMPA、SMPA與RM-MPA算法的收斂性能，并對它們的譯碼性能進行比較分析。最后給出不同剔除策略下的RM-MPA算法的性能比較，同時也對基于正交用戶組剔除策略下串行消息傳播機制的 RM-MPA和并行消息傳播機制的RM-PMPA的性能進行比較，仿真的參數及其取值如表2所示。

表2 仿真參數及其取值

圖4是算法在不同信噪比（SNR, signal to noise ratio）下收斂速率的比較，縱軸為誤符號率（SER,symbol error rate），RM-MPA-URS1表示每次剔除前n=1個譯碼優勢用戶的RM-MPA算法。因為仿真的用戶數 J = 6，在 6次迭代后，RM-MPA-URS1中所有的用戶已被譯碼，所以只給出前6次迭代的RM-MPA-URS1算法的收斂曲線。

圖4 算法收斂速率比較

從圖4中可以看出，PMPA算法要在迭代次數達到 5次之后SER才趨于穩定，而 SMPA與RM-MPA算法只需要3次迭代，即采用串行消息傳播機制的RM-MPA算法的收斂速率與SMPA算法的收斂速率一樣，而且比PMPA算法的收斂速率更快。在迭代次數為 1時，SMPA算法與RM-MPA算法的SER一樣且比PMPA算法的SER低很多，所以RM-MPA算法采用與SMPA算法一樣的串行消息傳播機制效果更佳，而且采用串行消息傳播機制的 RM-MPA算法中存在譯碼優勢用戶，使每次迭代后RM-MPA算法中被剔除用戶的譯碼準確率更高。

圖5是PMPA算法和SMPA算法在不同迭代次數下的SER性能比較，在迭代次數一樣時，SMPA算法的SER要比PMPA算法低，并且迭代次數為3的SMPA算法已經很接近迭代次數為5的PMPA算法。從圖5也可看出，迭代次數越低，SMPA算法的優勢就越明顯，特別是一次迭代時SMPA的SER比PMPA的要低很多，說明了RM-MPA算法采用串行消息傳播機制更有優勢。因為 RM-MPA算法必須要保證每次迭代后被剔除用戶的譯碼可靠性，特別是第一次迭代后剔除的用戶的譯碼可靠性直接決定了整個算法的譯碼性能，而PMPA在第一次迭代后的譯碼性能比SMPA算法的差很多，而且并行消息傳播機制中所有用戶的譯碼優勢是一樣的，不存在譯碼優勢用戶。

圖5 PMPA算法與SMPA算法譯碼性能比較

圖6 是不同剔除策略的RM-MPA譯碼算法性能比較，URS1（user remove strategy 1）、URS2和OUGR（orthogonal user group removed）分別表示用戶剔除策略1、策略2和正交用戶分組剔除策略。URS1表示每次剔除前一個譯碼優勢用戶，即 1n= ，URS2表示每次剔除前個譯碼優勢用戶，URS1和URS2都屬于譯碼優勢用戶排序剔除策略。OUGR表示每次剔除一個正交用戶組，這里，每個正交用戶組里有個用戶，把 URS2每次剔除的用戶數設置成與OUGR相同，主要是為了方便與OUGR進行對比。將迭代次數都設置為3是因為由圖4可知，迭代次數為3時RM-MPA算法已收斂。從圖6中可看出：在譯碼優勢用戶排序剔除策略中，每次剔除的用戶數越多，其SER就越大，而且的譯碼優勢用戶排序剔除策略的性能要比正交用戶分組剔除策略的性能好，因為在剔除用戶數相同的情況下，前者剔除用戶的總譯碼可靠性要比后者高，但后者的復雜度更容易分析且遠遠低于前者，這是正交用戶分組剔除策略的優勢所在。所以可以在這2種剔除策略和參數n的取值中進行選擇，來達到復雜度與性能之間的平衡。

圖6 不同剔除策略的RM-MPA譯碼算法性能比較

圖7 是在正交用戶分組剔除策略下的RM-MPA與RM-PMPA算法性能比較，RM-PMPA表示采用并行消息傳播機制的RM-MPA算法。從圖7中可看出，迭代次數為3時，SMPA算法的SER要低于PMPA算法，SMPA算法在收斂速度上有優勢。但SMPA算法失去了PMPA算法能使用多個處理并行處理的優勢，會有一定的譯碼時延。而在RM-MPA譯碼算法中，迭代次數每增加一次，其復雜度便降低一個數量級，降低了譯碼時延的同時其譯碼可靠性也能夠得到保證。如圖7所示，在正交用戶分組剔除策略下，RM-MPA算法的譯碼性能仍能得到保障，但RM-PMPA的譯碼性能則很差，驗證了RM-PMPA算法要在迭代次數達到一定次數后才能進行用戶的譯碼和剔除操作，也說明RM-MPA算法更適于采用串行消息傳播機制，即迭代剔除機制更適于與收斂速度快的譯碼算法結合，才能更好地降低復雜度的同時有效保證譯碼性能。

圖7 譯碼性能比較

6 結束語

針對 SCMA系統中譯碼算法復雜度過高問題，本文提出了RM-MPA算法，此算法宜采用串行消息傳播機制，加快其收斂速度，在此基礎上提出了譯碼優勢用戶排序剔除和正交用戶組剔除2種迭代剔除策略，前者的譯碼性能更好，但其復雜度也比后者高。將 SCMA技術與大規模MIMO相結合，進一步提高系統的頻譜效率，在此系統下的低復雜度多用戶檢測是下一步研究的主要內容。