基于主動禁忌搜索的稀疏碼多址接入技術(shù)低復雜度檢測算法

彭小洹，賴 恪，潘志鵬,雷 菁

(國防科技大學 電子科學學院，湖南 長沙 410073)

0 引言

第六代移動通信(6G)已經(jīng)展開了研究,與5G相比，6G具有更高的頻譜效率和更大的系統(tǒng)容量。傳統(tǒng)的正交多址技術(shù)(Orthogonal Multiple Access,OMA)已經(jīng)無法滿足需求[1-3]，非正交多址接入技術(shù)(Non-Orthogonal Multiple Access,NOMA)通過在發(fā)送端允許多用戶共享相同的時頻空資源，在接收端進行多用戶檢測，能有效地提高系統(tǒng)吞吐量和接入用戶數(shù)，被認為是未來6G系統(tǒng)的關(guān)鍵技術(shù)之一[4-5]。

一般而言，NOMA技術(shù)可以分為功率域NOMA(Power-Domain NOMA,PD-NOMA)以及碼域NOMA(Code-Domain NOMA,CD-NOMA)兩大類[6-7]，而本文所探討的稀疏碼多址接入(Sparse Code Multiple Access,SCMA)正是CD-NOMA方案的典型代表。SCMA最早由Nikopour等人在低密度簽名(Low Density Signature,LDS)基礎(chǔ)上提出[8]。在 SCMA 中，對比特進行 QAM 調(diào)制和擴頻的兩個步驟由一個碼書映射步驟所代替，這一過程中比特被直接映射成為復數(shù)域的多維符號。 SCMA 用戶的碼書是指該用戶比特對應的多維稀疏符號向量的集合。作為區(qū)分，不同的用戶擁有各自獨特的碼書，利用碼書設計過程中多維星座的成型增益，SCMA 可以獲得相比 LDS 更佳的性能[9]。

SCMA檢測算法是 SCMA 技術(shù)的核心。 Hoshyar 等人最早提出使用 MPA 算法來對稀疏結(jié)構(gòu)的 LDS 系統(tǒng)進行多用戶檢測，獲得了近似 ML 的優(yōu)異檢測性能[10]，這一方法被直接移植到 SCMA 的檢測中。 MPA 算法的基本思想是通過外消息在系統(tǒng)抽象出來的稀疏因子圖的變量節(jié)點和校驗節(jié)點之間迭代傳遞，收斂得到一個用于判定符號的概率值。雖然 SCMA 技術(shù)通過碼字在頻域的稀疏擴展可以極大地降低 MPA 算法的計算復雜度，但是其實現(xiàn)復雜度仍然非常高，尤其在復用的用戶數(shù)df較大和調(diào)制階數(shù)M較高時， MPA 的復雜度會呈指數(shù)增加。具體而言， MPA檢測復雜度為O(TMdf)，其中T表示算法迭代次數(shù)。因此，設計創(chuàng)新的算法和結(jié)構(gòu)來降低計算成本成為后續(xù)研究 SCMA 的學者們的主要方向之一。

為了降低SCMA接收機的復雜度，一般從碼本大小、迭代次數(shù)、行重因子以及每次迭代參與點數(shù)四方面入手。文獻[11-12]提出了一系列擴展對數(shù)域Max-Log (Extended Max-Log,EML)算法，基本思想是根據(jù)其對置信度參與迭代的符號進行截斷，從而降低參與每輪迭代的符號個數(shù)。為了使MPA可以以更快的速度收斂，文獻[13]提出了一種基于串行更新的消息傳遞算法。該算法能夠在當前迭代中立即傳播已更新的消息，從而加快收斂速度，減小迭代次數(shù)，達到降低復雜度的目的。另外，從降低行重的角度來看，文獻[14]提出了一種基于邊選擇的消息傳遞算法(Edge Selected MPA,ES-MPA)，該算法利用接收端已知的信道狀態(tài)信息，只選擇信道質(zhì)量較好的部分邊來更新從資源節(jié)點到用戶節(jié)點的消息，而剩下的邊所傳遞的信息則是利用高斯近似的方法來計算。同時，為了補償信息損失，更新高斯模型的均值作為反饋，從而保證在降低復雜度的同時幾乎不損失誤碼性能。為了降低MPA的搜索空間，文獻[12]提出了一種基于動態(tài)閾值的消息傳遞算法(Dynamic Threshold-based MPA,DT based-MPA)，該算法的核心思想是為在不同的信噪比下挑選不同數(shù)量疊加星座點參與資源節(jié)點迭代更新過程。另外，文獻[15]提出了一種基于列表球形解碼(List Sphere Decoding,LSD)的消息傳遞算法，該算法只在給定半徑的超球面內(nèi)搜索出候選列表集，然后將此列表集中的點參與資源節(jié)點更新的迭代過程，由此降低了復雜度，但該算法的半徑不能依據(jù)高斯噪聲動態(tài)變化?？梢钥吹?，目前多數(shù)的SCMA譯碼算法均是基于MPA進行簡化的。為此，本文引入主動禁忌搜索算法[16-17]，從而規(guī)避了MPA的使用，相較于傳統(tǒng)的基于MPA的簡化算法，本文所提算法具有如下優(yōu)勢：① 本文所提算法具有參數(shù)調(diào)整靈活的特點；② 本文所提算法不依賴于MPA，可以大幅度降低SCMA的檢測復雜度，同時獲得良好的性能。

1 SCMA信號模型

圖1 典型SCMA系統(tǒng)框圖Fig.1 System model of conventional SCMA

在經(jīng)過 SCMA 編碼器后，不同用戶的稀疏碼字便會映射到K個物理資源(如 OFDM 子載波)上。假設接收信號為y=[y0,y1,…,yK-1]T，信道增益hk=[h0,k,h1,k,…,hK-1,k]T，以及噪聲向量v=[v0,v1,…,vK-1]T。接收信號是所有用戶經(jīng)過各自信道后疊加而成的，可以寫成

(1)

(2)

從式(2)可以看出，在一個物理資源上，每一個用戶j都會受到來自其他J-1個用戶的干擾。

類似于 LDPC 碼， SCMA 碼字的低密度結(jié)構(gòu)也可以用因子圖來有效刻畫。用一個長度為K的二進制列向量fj中的“0”和“1”來分別表示用戶j的碼書中零元素和非零元素的位置。那么，用戶和資源之間的關(guān)系就可以用一個K×J的稀疏的因子圖矩陣F=[f1,f2,…,fJ]來表示[18]。

(3)

式中，F(xiàn)的行表示資源，列表示用戶。例如F中的第k行j列個元素fk,j，表示第j個用戶在第k個資源上傳輸數(shù)據(jù)。

2 基于主動禁忌搜索的SCMA檢測算法

2.1 主動禁忌搜索

禁忌搜索(Tabu Search，TS)最早由美國工程院院士 Glover 教授在 1989 年提出，它是一種全局優(yōu)化算法，一經(jīng)提出就受到廣泛關(guān)注，并陸續(xù)在組合優(yōu)化、生產(chǎn)調(diào)度以及機器學習等諸多領(lǐng)域獲得成功的應用。之后，Glover、 Faigle 等學者針對禁忌搜索的收斂性展開了一系列數(shù)學上的理論研究。同時，還有許多學者針對禁忌搜索性能和效率的平衡問題展開了一些算法的實際應用和改進研究。

TS的基本思想是迭代地從當前解移動到其相鄰的解。與其他啟發(fā)式搜索算法不同的是，TS算法加入了禁忌列表，其限制了已經(jīng)出現(xiàn)的解在有限的禁忌周期T內(nèi)不能再作為下一次移動的對象，從而保證了搜索解的多樣性，使其能夠跳出局部最優(yōu)解，更容易獲得全局最優(yōu)。然而，簡單的 TS 算法在實際使用中主要有以下3點要求難以滿足：① 根據(jù)不同的任務確定合適的禁忌周期T；② 算法參數(shù)對于不同問題求解的魯棒性；③ 采用最小計算復雜度的算法來搜索歷史狀態(tài)。為此，學界提出了主動TS(Reactive TS,RTS)以解決上述問題。

在 RTS 中，禁忌周期T能夠在搜索過程中通過相應的反饋機制來動態(tài)決定。具體而言，算法起始時T=1，當有明顯表征顯示需要增加解的多樣性(Diversification)時使T增加，而當這種表征消失時則減小以增加解的集中性。一般而言，是否需要多樣性的表征，可以用當前訪問的解狀態(tài)出現(xiàn)的重復次數(shù)來衡量。RTS在搜索過程中所有的歷史搜索狀態(tài)都會被存儲下來。算法每執(zhí)行一步，就會檢查當前解狀態(tài)在之前搜索中是否出現(xiàn)過，出現(xiàn)的頻率如何，然后據(jù)此來決定T是增加還是減小。

因此， RTS 的禁忌周期在搜索過程中不是固定的，而是根據(jù)搜索空間的局部結(jié)構(gòu)來動態(tài)決定的。對于一個“非均勻”搜索空間(指搜索空間中不同區(qū)域的統(tǒng)計性質(zhì)有較大差異)而言，固定禁忌周期顯然不再合適，此時 RTS 更適合解決此類問題。

2.2 基于主動禁忌搜索的SCMA檢測算法

SCMA多用戶檢測器的目標在于利用y和H的先驗知識估計出。根據(jù) ML準則，有

(4)

式中，γ(X)=XHHHHX-2R(yHHX)定義為 ML 代價函數(shù)。

步驟一：初始化參數(shù)

令g(m)為m次迭代后得到的最優(yōu)解向量，lreq為相鄰兩個重復解向量之間的平均步長(或者迭代次數(shù))。P為最大禁忌周期，表示如果在一次迭代中某一移動被標記為禁忌狀態(tài)(即禁忌列表中對應元素為P)，則在未來的P次迭代內(nèi)，該移動會一直保持禁忌狀態(tài)。二元標志位lflag∈{0, 1}用來指示算法在當前迭代是否達到了局部最優(yōu)，主要應用于算法的終止準則中。

算法開始前需要通過 MMSE 等方法獲得初始解向量x(0)，然后設置g(0)=x(0),lreq= 0,P=P0，禁忌矩陣T中元素全部置零。同時，分別計算yMF?HHy和R?HHH。

步驟二：鄰域搜索

初始化lflag= 0，為方便表達，定義f(m)?Rx(m)-yMF，e=z(m)(u,v)-x(m)。則對于給定解向量x(m)，其所有dvJN個鄰域向量z(m)(u,v),u=1,2，…,dvJ,v=1,2，…,N的 ML 代價函數(shù)可以計算如下

φ(z(m)(u,v))=(x(m)+e)HR(x(m)+e)-2R((x(m)+e)HyMF)=

φ(x(m))+2R(eHRx(m))+eHRe-2R(eHyMF)=

φ(x(m))+2R(eH(Rx(m)-yMF))+eHRe=

φ(x(m))+2R(eHf(m))+eHRe=

(5)

(u1,v1)=argminu,v(u,v)。

(6)

目前為止，所求的最佳移動(u1,v1)能否執(zhí)行，還需要依賴其實際 ML 代價值以及相應的禁忌狀態(tài)。只有滿足如下任意兩個條件之一，則表示上述移動是被允許的。

γ(z(m)(u1,v1))<γ(g(m)),

(7)

T((u1-1)M+q,v1)=0,

(8)

若條件(7)和(8)均無法滿足，則意味著移動(u1,v1)應該處于禁忌狀態(tài)并且不滿足特赦條件。此時，算法根據(jù)等效 ML 函數(shù)尋找次優(yōu)移動，即

(9)

然后,再次對移動(u2,v2)進行條件(7)和(8)的判斷。若仍然判斷為禁忌狀態(tài)，則繼續(xù)次優(yōu)(u3,v3)，直至找到滿足上述條件的移動。當發(fā)現(xiàn)所有dvJN個移動均標記為了禁忌狀態(tài)，則將禁忌表中所有元素減去它們的最小值，總會有一個移動的禁忌值為 0。令(u′,v′)為滿足條件的有最小等效 ML 代價的移動，則求得的相應的解向量為：

x(m+1)=z(m)(u′,v′)。

(10)

注意式(5)最后一行，表示x(m+1)的獲得可以迭代地求得γ(z(m+1)(u,z))，進而開始下一輪迭代。

步驟三：檢查解的重復次數(shù)，動態(tài)改變禁忌周期

對步驟二所得解向量進行重復性分析。方法是通過比對該解向量的 ML 代價值與歷史搜索解向量的 ML 代價列表，找出最近出現(xiàn)的重復解向量并更新平均重復距離lrep，同時調(diào)整禁忌周期P=P+ 1。若禁忌周期P已經(jīng)有l(wèi)p>βlrep,β>0次迭代沒有發(fā)生改變，則令P=max(1,P-1)。同時，若γ(x(m+1))<γ(g(m))，則

T((u′-1)M+q′,v′)=T((u′-1)M+q″,v″)=0，

(11)

g(m+1)=x(m+1)，

(12)

否則，

T((u′-1)M+q′,v′)=T((u′-1)M+q″,v″)=P+1，

(13)

lflag =1,g(m+1)=g(m)。

(14)

該步驟根據(jù)解向量的重復頻率，動態(tài)改變禁忌周期P，恰好體現(xiàn)出算法“主動禁忌”的含義。

步驟四：更新禁忌矩陣

更新禁忌矩陣中所有移動的禁忌值，即

T(r,s) = max{T(r,s) - 1, 0}，

(15)

式中，r=1,2,…,dvJM,s=1,2,…,N。同時,

(16)

式中,Ru′是指矩陣R的第u′列。若步驟四中的終止條件未被觸發(fā)，則算法重復步驟二～步驟四，直至滿足算法終止條件。

步驟五：算法終止準則

結(jié)合信號模型和調(diào)試經(jīng)驗，給出如下3個算法終止條件。只要滿足3個條件任意一個則終止算法，輸出最終解向量：

① (搜索步長條件)當搜索步長(即迭代次數(shù))超過算法設定最大迭代次數(shù)Tmax時，算法終止；

② ( ML 代價條件)當算法獲得的當前最優(yōu)解向量g(m)的 ML 代價值γ(x)滿足

γ(g(m))<Θi，

(17)

式中，Θi為設定的算法閾值，且lflag=1時，算法終止。算法閾值根據(jù)經(jīng)驗可進一步定義為：

(18)

式中，σ2為噪聲功率，ri為閾值控制參數(shù)；

③ (解向量重復條件)若當前搜索獲得的最優(yōu)解向量的重復頻率R達到設定的最大重復頻率Rrep時，算法終止。

算法的具體流程如圖2所示。

圖2 SCMA-RTS 檢測算法流程圖Fig.2 Flow chart of SCMA-RTS detection algorithm

2.3 基于外迭代禁忌搜索的SCMA檢測算法

在實際應用中，單純地由某一初始解向量出發(fā)，進行單次 RTS 搜索難以在算法性能和復雜度之間取得較好的平衡。一方面，算法對于初始解向量的取值十分敏感，若取值不合適，即使采用了禁忌準則， RTS 也需要經(jīng)歷較長的搜索路徑才能找到最佳解向量，此時算法復雜度甚至高于 MPA 檢測;另一方面，單次 RTS 搜索在較高信噪比時，十分容易出現(xiàn)誤碼平層。基于上述兩方面考慮，在 SCMA-RTS的基礎(chǔ)上進一步提出基于外迭代的 RTS 檢測算法，其基本思想是通過選取不同的初始向量進行多次 RTS 搜索，以拓寬 RTS 搜索區(qū)域、提升檢測性能，同時通過合適的迭代退出條件來保證算法復雜度。

IRTS算法主體仍然是 RTS，不同之處在于在外圍加入了循環(huán)迭代機制。通過相應的初始向量選取方法得到搜索起始向量后， IRTS 開始進行 RTS 運算，并得到該次搜索的最佳解向量。此時，算法判斷解向量是否滿足外迭代退出條件。如果滿足，則輸出相應的解向量作為最后輸出結(jié)果；否則，再次生成一個不同的初始向量進行 RTS 搜索，重復此操作直至滿足外迭代退出條件。

3 仿真結(jié)果及分析

作為啟發(fā)式算法， RTS 和 IRTS 涉及的參數(shù)對算法 BER 和復雜度性能有重要影響。本節(jié)對所提出的 RTS 和 IRTS 檢測算法進行仿真驗證，考察其誤碼率和復雜度性能，并給出了算法相關(guān)參數(shù)的敏感性分析，相關(guān)的仿真參數(shù)如表1所示。

表1 仿真參數(shù)

3.1 誤碼率與復雜度對比

選取如表1所示的基準參數(shù)，對 RTS 和 IRTS 兩種算法的BER性能和復雜度進行仿真分析，其結(jié)果如圖 3和圖 4所示。

由圖 3可以看出， RTS 相比 Log-MPA有大約2 dB的性能損失。并且隨著信噪比的增大，其BER 開始出現(xiàn)誤碼平層,其原因在于隨著信噪比的增加，基于 ML 代價值的搜索空間中局部最優(yōu)解的數(shù)量大量增加，而考慮到復雜度的影響，所以無法使用更長的搜索路徑來避免所有的局部最優(yōu)。通過分析如表2所示的不同信噪比下平均搜索步長Ti的值,可以得出一致的結(jié)論?？梢钥吹诫S著信噪比的增加，所需要的Ti也隨之增加，與之對應地，BER 曲線隨之下降。但是到Eb/N0= 14 dB 后，Ti的值由于算法結(jié)構(gòu)和參數(shù)的限制不再增大，由此導致算法 BER 曲線開始偏離原來的趨勢，而出現(xiàn)誤碼平層。對應到復雜度曲線，這一現(xiàn)象則是在高信噪比區(qū)域復雜度系數(shù)收斂的原因。值得注意的是，即使隨著信噪比增加復雜度有所增加，但是其加法操作數(shù)和乘法操作數(shù)最大仍然分別只有 Log-MPA 的 10% 和 30%。這一比例在低信噪比時更低。

而IRTS在提高RTS檢測性能的同時，較好地解決了誤碼平層的問題。從圖中可以看出， IRTS 相比 Log-MPA 僅有 0.5 dB 左右的性能損失，相比 RTS 有 1.5 dB左右的性能提升，同時消除了誤碼平層。背后的原理在于外迭代機制的引入，使得算法能夠在信噪比較高時，選擇若干個初始解向量開始搜索，搜索區(qū)域變大，因而克服了原本從單一初始向量出發(fā)陷入循環(huán)的問題。從表3可以看出， IRTS 在相同信噪比下的內(nèi)迭代次數(shù)相比 RTS 略有減少，而外迭代次數(shù)隨信噪比增加呈現(xiàn)先增加后減小的趨勢。這是閾值參數(shù)選取和算法結(jié)構(gòu)共同導致的結(jié)果。另一方面，基于隨機干擾的 IRTS 也由于外迭代的引入帶來了額外的復雜度。相比 RTS， IRTS所需的加法和乘法操作數(shù)幾乎是 RTS 的3倍，但是仍然遠低于 Log-MPA。相比其他低復雜度算法， RTS/IRTS 主要有以下優(yōu)點：① 算法參數(shù)魯棒性高，對不同信道、不同規(guī)模碼書的 SCMA 系統(tǒng)均能夠有較好的檢測性能；② 通過閾值控制參數(shù)ri和ro， IRTS 可以方便地根據(jù)需要來選擇更低的復雜度或者更加優(yōu)異的性能；③ 沒有 MPA 算法中指數(shù)型復雜度階數(shù)，因而在處理M或者df較大的 SCMA 系統(tǒng)時，更具有復雜度上的優(yōu)勢。

圖3 RTS 和 IRTS 的 BER 性能Fig.3 BER performance comparison between RTS and IRTS

圖4 RTS 和 IRTS 的復雜度性能Fig.4 Computational complexity comparison between RTS and IRTS

表2 RTS 在不同信噪比下的平均搜索步長

表3 IRTS 在不同信噪比下的平均搜索步長

3.2 參數(shù)敏感性分析

3.2.1 RTS參數(shù)敏感性分析

本節(jié)針對不同參數(shù)對于RTS以及IRTS算法BER性能的影響進行敏感性分析。

如圖 5所示，在信噪比較低時，算法對于最大搜索步長有良好的魯棒性，其 BER性能基本不發(fā)生變化。而在Eb/N0≥ 12 dB 時，隨著Timax的增大， BER 性能將隨之改善,但相應地，復雜度也隨之增加。這是因為隨著信噪比的提高，更寬松的搜索步長限制能夠使 RTS 有可能以更長的搜索路徑為代價找到全局最優(yōu)解。同時，注意到Timax≥70時， BER曲線基本趨于平緩，這是因為隨著搜索過程的進行，其他終止條件開始起主要作用?；诖丝蛇x擇Timax=70作為基準參數(shù)值。

圖5 Timax對 BER 的影響Fig.5 Impact of Timax on BER

圖 6展示了不同信噪比下，內(nèi)閾值控制參數(shù)ri對算法 BER 和復雜度性能的影響。從圖中可以看出，隨著ri的增加，算法 BER 性能惡化明顯；相反地，復雜度系數(shù)卻大幅下降。這是因為RTS 算法 ML 代價終止條件指出，當所得解的 ML 代價值小于內(nèi)閾值時即終止搜索。而ri的增加即內(nèi)閾值Θi的增大，意味著放寬了上述 ML 終止條件，使得部分ML 代價值較大的局部最優(yōu)解被當做全局最優(yōu)解輸出，從而導致性能變差。同時，寬松的終止條件也導致了更短的搜索步長，因而其算法復雜度也隨之下降。

圖6 ri對 BER 的影響Fig.6 Impact of ri on BER

3.2.2 IRTS參數(shù)敏感性分析

圖 7展示了不同信噪比下Tomax對算法 BER 和復雜度系數(shù)的影響，可以看出，在Tomax≤4時，隨著Tomax增加， BER 性能隨之改善，而復雜度也隨之明顯增大。注意到，當Tomax=4時， BER 性能基本達到收斂，而相應的復雜度也相對穩(wěn)定。因此，可以選取Tomax=4作為最大外迭代次數(shù)參數(shù)基準值。

圖7 IRTS 中Tomax對 BER 的影響Fig.7 Impact of Tomax on BER in IRTS

IRTS通過對歷史解向量施加一定維度di的隨機干擾，使得算法能夠在充分利用歷史搜索信息的基礎(chǔ)上，盡可能地跳出當前局部搜索區(qū)域，以獲得全局最優(yōu)解。圖8展示了不同信噪比下di對于算法 BER的影響，可以看出，隨著干擾維度的增加， BER 性能略微改善。這是因為干擾維度的增加，意味著有更大幾率跳出當前解的搜索范圍，而更廣的搜索范圍將獲得更優(yōu)的檢測性能。因此，選取干擾維度di=4作為基準參數(shù)比較合適，此時算法 BER 性能較好、復雜度較低。

圖8 di對 BER 的影響Fig.8 Impact of di on BER in IRTS

4 結(jié)束語

本文提出一類基于主動禁忌搜索思想的 SCMA 檢測算法，包括 RTS 和 IRTS。RTS 檢測算法是一種全局性鄰域搜索算法，它通過引入禁忌表，并且設置規(guī)則動態(tài)地改變每個歷史界的禁忌周期，保證了搜索解的多樣性，使其能夠跳出局部最優(yōu)解，更容易獲得全局最優(yōu)。 SCMA 的 RTS 檢測算法大體包括初始化參數(shù)、鄰域搜索、檢測解的重復次數(shù)、更新禁忌矩陣和判斷算法終止條件等5個步驟。而實踐中發(fā)現(xiàn)，單次 RTS 搜索盡管能夠取得極低的檢測復雜度，但是 BER 性能損失較大。

為此，本文在 RTS 檢測算法的基礎(chǔ)上繼續(xù)提出了基于外迭代的 RTS 檢測算法(IRTS)，將單次 RTS 搜索作為內(nèi)迭代，然后引入外迭代機制來進行多次 RTS 搜索。采用基于隨機干擾的初始向量選取策略，使得算法既能夠拓寬搜索區(qū)域、提升檢測性能，也能夠充分利用歷史搜索信息。仿真結(jié)果表明，通過合適的參數(shù)選取， RTS 能夠以 2 dB 左右的 BER損失，帶來只有 Log-MPA 操作數(shù) 10% 左右的低操作復雜度。而 IRTS 則通過引入外迭代，解決了 RTS 中誤碼平層的問題。雖然其復雜度相比 RTS 有所增加，但性能顯著提升，相比 Log-MPA 只有 0.5 dB 左右的損失。同時，通過恰當?shù)膮?shù)選取，RTS 和 IRTS 可以方便地調(diào)節(jié)復雜度性能和 BER 性能，具有相當?shù)膽脠鼍斑m應性。