基于時間相關性的梯度追蹤多用戶檢測算法

蔣 芳, 楊雅情, 鄭國梁, 王 翊, 許耀華,*, 吳香情

(1. 安徽大學計算智能與信號處理教育部重點實驗室, 安徽 合肥 230601;2. 安徽省物聯網頻譜感知與測試工程技術研究中心, 安徽 合肥 230601)

0 引 言

根據物聯網市場研究機構IoT Analytic預測:隨著物聯網產業的發展,通信網絡中部署的物聯網節點數量到2025年將達到215億臺,大規模機器類型通信(massive machine type communication, mMTC)會成為未來移動通信系統的重要應用場景。區別于人對人通信,mMTC面向控制類物聯網,如遠程抄表、環境監測、設備控制以及大型基礎設施監控等,數據流以上行通信為主,且具有短包突發性特征。同時為了滿足5G通信系統對于時延、信令開銷以及接入效率的需求,免調度的非正交多址(grant-free non-orthogonal multiple access, GF-NOMA)接入技術在mMTC中被廣泛研究。與長期演進(long term evolution, LTE)系統不同,GF-NOMA系統需要在接收端辨別用戶的數據和活躍性。基于mMTC零星、突發性業務特征,其數據幀結構具有稀疏特性,因此可以使用壓縮感知(compressed sensing, CS)的信號重建技術對設備的活躍性和數據進行聯合檢測。Abebe等人利用機器類型設備在一幀信號內活躍狀態的結構性對子空間追蹤(subspace pursuit, SP)算法進行了改進,提出了結構化迭代支撐檢測(structured iterative support detection, SISD)算法,降低了誤符號率(symbol error rate, SER)。文獻[20]利用一幀信號內活躍設備的短持續性,結合正交匹配追蹤(orthogonal matching pursuit, OMP)算法設計了基于結構匹配追蹤的動態多用戶檢測(structured matching pursuit-based dynamic multi-user detection, SMP-MUD)算法,在每次迭代挑選1個活躍設備并使用最小二乘法計算估計信號值。文獻[22]首先利用信號的塊稀疏特性,結合閾值設置對SP算法進行了改進,通過選擇合適的閾值提升了數據檢測的準確性;其次,引入了機器學習的方法優化迭代終止條件,為多用戶檢測算法的研究提供了有意義的參考。以上基于CS的多用戶檢測,在數據檢測階段大多使用最小二乘法,需要對等效信道矩陣進行求逆,產生了較高的計算復雜度。

對基于CS的多用戶檢測算法而言,算法的計算復雜度不僅與信號值估計有關,還與迭代次數有關。基于CS的多用戶檢測算法中的每次迭代需要完成兩個目標:設備的活躍性鑒別和活躍設備的發送數據檢測。如果一次迭代能夠檢測出多個設備的活躍性并恢復這些設備的發送數據,勢必能更快地完成檢測。文獻[23]利用活躍設備在一幀信號內的相鄰時隙間具有時間相關性,設計了動態的CS多用戶檢測(dynamic CS-based multi-user detection, DCS-MUD)算法,每個時隙的初始支撐集都來自前1個時隙的檢測結果,提高了設備活躍性鑒別的效率。文獻[24]基于DCS-MUD算法框架,使用質量評估參數對獲取的支撐集進行評估,剔除了錯誤索引,進一步提升了多用戶檢測的SER性能。文獻[25]利用Dice系數匹配準則和最小二乘法提出了一種改進稀疏度自適應匹配的多用戶檢測算法,當相鄰迭代殘差信號比值大于閾值時使用大步長挑選多個設備,當相鄰迭代殘差信號比值小于閾值時使用小步長精確逼近。文獻[26]通過自適應閾值輔助策略,在每次迭代時至少挑選1個活躍設備,之后再通過最小二乘法計算估計信號值。文獻[27]通過設置最優索引數目,利用廣義正交匹配追蹤(generalized orthogonal matching pursuit,GOMP)算法,在每次迭代時挑選最優索引數目個數的活躍設備加入支撐集。

為降低基站端多用戶檢測復雜度,本文結合了時間相關性特征和梯度追蹤(gradient pursuit, GP)算法,提出了相關性輔助的GP多用戶檢測(correlation-assisted multi-user detection, CAGP-MUD)算法。在設備的活躍性檢測階段,利用活躍設備在相鄰時隙間的時間相關性,減少單個時隙內的迭代次數;在活躍設備的發送數據恢復階段,采用GP算法避免由最小二乘導致的矩陣求逆。隨后,在CAGP-MUD算法框架內引入決策衰弱的思想,增加每次迭代挑選出的活躍設備數目,進一步降低了單個時隙內的迭代次數,從而提高收斂速度,可被稱之為相關性輔助的組梯度追蹤多用戶檢測(correlation-assisted group gradient pursuit multi-user detection, CAGGP-MUD)算法。提出的算法分別從避免矩陣求逆和減少迭代次數兩個角度,有效降低了復雜度,而GP算法的引入仍能保證算法的收斂性。因此,CAGP-MUD算法和CAGGP-MUD算法以較小的精度代價,換取了復雜度的有效降低。

1 系統模型

假設一個單基站(base station, BS)的上行免調度NOMA系統,覆蓋個設備用戶。為簡化系統模型,只考慮每個設備用戶配置單根天線的情況。根據mMTC的數據流特征,在一幀信號的持續時間內,僅有個設備處于有數據包發送的活躍狀態,其他設備均處于休眠狀態。活躍設備將其發送數據利用星座圖進行符號映射,休眠狀態的設備不發送數據。

因采用免調度機制,基站端首先要根據接收信號對設備的活躍性進行鑒別。為了對所有設備用戶的發送符號數據進行統一表示,對傳統的星座圖進行了擴充,定義一個新的星座圖={∪0}。當第個設備為活躍設備,則其發送的數據經星座圖映射后表示為符號數據?;當第個設備為靜默設備,沒有數據包發送,該設備發送的符號數據可表示為=0。進行星座擴充后,無論設備用戶是否活躍,都有?。

根據可壓縮接入理論,設備的發送數據經由長度為的擴頻碼擴頻到個子載波信道上。所有活躍設備的發送數據都采用相同的方式擴頻到這個子載波信道上。考慮到NOMA系統的特征,子載波信道數?設備用戶數。BS的接收信號可表示為

(1)

式中：表示設備在第個子信道的信道增益系數;=[,,…,]是高斯白噪聲,滿足0均值,方差為。式(1)可以改寫為

=+

(2)

式中:

定義為等效信道矩陣;=[,,…,]。

2 基于時間相關性的GP-MUD算法

2.1 CAGP-MUD算法

如前文所述,多用戶檢測算法的計算復雜度不僅與信號估計有關,還與迭代次數有關。為了降低多用戶檢測算法的復雜度,本文首先提出了CAGP-MUD算法,利用活躍設備的時間相關性特征減少多用戶檢測的迭代次數,利用GP算法降低發送數據恢復時的計算復雜度。

文獻[23]指出,活躍設備有很大概率連續傳輸數據。因此,一幀信號持續時間內大部分活躍設備在相鄰兩個時隙的活躍性保持不變。在實際的通信場景下,會有少量設備在一幀信號持續時間內隨機地接入或離開信道。因此,在幀結構上本文使用和文獻[23]一致的混合稀疏模型,該模型認為在一幀信號持續時間內,大部分設備的活躍性保持不變,少部分設備的活躍性發生改變。混合稀疏模型把活躍性不發生改變的活躍設備稱為公共活躍用戶,將其索引的集合稱為公共活躍用戶支撐集;活躍性發生改變的活躍設備稱為動態活躍用戶,其索引的集合稱為動態活躍用戶支撐集。假設第時隙的活躍設備索引集合為,=∪。而第+1時隙的活躍設備索引+1=∪+1。因此,前一時隙檢測出的活躍用戶支撐集包含著大量有效的信息,完全可以用作下一時隙初始的支撐集。CAGP-MUD算法就是利用相鄰兩時隙間設備活躍狀態的相關性避免每個時隙都從空集開始檢測設備的活躍性,減少了從第二時隙往后的迭代次數。

目前大部分基于貪婪類算法的壓縮感知多用戶檢測方法,在發送數據的恢復階段都采用最小二乘計算,該階段執行一個信道等效矩陣的偽逆運算,大規模應用時復雜度較高。CAGP-MUD算法結合GP框架,利用梯度下降法計算每次迭代的更新方向。

CAGP-MUD算法的具體細節如算法1所示。

算法1 CAGP-MUD算法輸入 活躍設備數目:K;接收信號:y1,y2,…,yJ;等效信道矩陣:A輸出 活躍設備及設備數據:x^i-11,x^i-12,…,x^i-1J初始化 Γ^=?,j=1,2,…,Jforj=1:Jdoi=1r0j=yjε=infΓij=Γ^whileε>thresholddoΓij=Γi-1j∪argmax|gj|2,wheregj=AHr(i-1)jdij=-gΓij,gΓij?gjcij=AΓijdijaij=〈rij,cij〉cij22x^iΓij=x^i-1Γij+aijdij

rij=ri-1j-aijcijε=rij2-ri-1j2i=i+1endwhileifΓij0≥KΓij={取x^iΓij中幅度最大的K個索引}endifΓ^=Γijx～i-1j,Γ^=x^i-1Γ^endfor

在CAGP-MUD算法的初始,會進行信息初始化,令初始活躍用戶支撐集為空集。

首先,CAGP-MUD算法需要計算當前迭代的梯度值。梯度可表示為

(3)

(4)

在CAGP-MUD算法中,使用梯度下降法計算每次迭代的更新方向。當前迭代的更新方向為梯度的負方向

(5)

接著,CAGP-MUD算法需要更新每次迭代的估計信號值:

(6)

在CAGP-MUD算法的迭代執行過程中,需要對支撐集進行修剪。因為在單個時隙的內循環中,每執行一次迭代,支撐集會增加一個活躍設備的索引,當迭代次數大于某一數值后,支撐集規模大于活躍設備數目,此時支撐集中必定包含了錯誤的索引。此外,由于利用了活躍設備狀態的時間相關性,每個時隙支撐集的初值來自于前一時隙的結果,該初始支撐中不僅包含對當前時隙有效的公共活躍支撐,也包含不屬于當前時隙的錯誤支撐。因此,算法1需要使用活躍設備數目對支撐集進行修剪。

2.2 CAGGP-MUD算法

CAGP-MUD算法結合了GP框架和一幀信號持續時間內相鄰時隙間設備活躍狀態的相關性,有效降低了多用戶檢測算法的計算消耗。但是CAGP-MUD算法在每次迭代中只挑選一個活躍設備,挑選出所有活躍設備需要的迭代次數較多。為了減少單個時隙的迭代次數,本文在CAGP-MUD的基礎上,結合決策衰弱策略,設計了CAGGP-MUD算法。利用決策衰弱思想,引入衰弱系數對最大梯度值進行衰弱,記為max||,并以此作為閾值。每次迭代挑選梯度信息大于該閾值的所有原子。相比于設定額定閾值的其他多用戶檢測算法,CAGGP-MUD算法利用每次迭代的最大梯度值和衰弱系數,動態設定閾值,沿負梯度方向一次挑選出多個活躍用戶,減少了總的迭代次數。

CAGGP-MUD算法的具體細節如算法2所示。在活躍設備的鑒別階段,CAGGP-MUD算法按照式(3)計算所有設備用戶的梯度,根據計算結果,挑選梯度大于閾值的所有個設備,將設備索引加入到如下支撐集中：

(7)

(8)

算法2 CAGGP-MUD算法輸入 活躍設備數目:K;基站接收信號:y1,y2,…,yJ;系統等效信道矩陣:A輸出 活躍設備及設備數據:x^i-11,x^i-12,…,x^i-1J初始化 Γ^=?,j=1,2,…,Jforj=1:Jdoi=1r0j=yjε=infΓij=Γ^whileε>thresholddogj=AHr(i-1)jΓij=Γi-1j∪{p:|gj,p|≥αmax|gj|}ifi=1dij=-gΓijcij=AΓijdijelsewij=AΓijgΓijvij=-〈cij,wij〉/cij22dij=gΓij+vijdi-1jcij=wij+vijci-1jendifaij=〈rij,cij〉/cij22x^iΓij=x^i-1Γij+aijdijifΓij0≥K

Γij={取x^iΓij中幅度最大的K個索引}endifrij=ri-1j-aijcijε=rij2-ri-1j2i=i+1endwhileΓ^=Γijx～i-1j,Γ^=x^i-1Γ^endfor

3 算法分析和仿真結果

3.1 復雜度分析

同文獻[30]保持一致,采用每種算法的乘法浮點次數表示其復雜度。

CAGP-MUD和CAGGP-MUD兩種算法都利用了時間相關性,即從第二個時隙開始,當前時隙的初始支撐集來自于前一個時隙的檢測結果。因此,在一幀信號的檢測過程中,兩種算法都在第一個時隙將支撐集的初始值設置為空集,需要遍歷所有設備的梯度才能挑選出活躍設備。從第二個時隙開始,可以利用前一個時隙的支撐集作為當前時隙支撐集的初始值,只需并入新的設備索引并通過支撐集裁剪對錯誤索引進行剔除。在進行復雜度計算時,按照第一時隙和其他時隙分別計算。

第一時隙中,CAGP-MUD算法的更新方向為梯度方向,由于選擇了梯度方向作為每次迭代的更新方向,省去了更新方向計算。因此,CAGP-MUD算法的每次迭代需對步長、信號值和殘差進行計算。復雜度表示為

=

(9)

式中：表示迭代次數,下標1表示第一時隙。而CAGGP-MUD算法需要根據式(8)重新計算更新方向,增加了額外的復雜度消耗,執行共計+2+次浮點運算。在第一時隙,CAGGP-MUD算法的復雜度為

=

(10)

其他時隙中,兩種算法的支撐集初始值均被賦值為前一時隙檢測的結果。CAGP-MUD算法的計算復雜度表示為

+

(11)

CAGGP-MUD算法的計算復雜度同樣增加了相應的更新方向消耗

+2

(12)

式中：表示迭代次數,下標表示對應的時隙。將第一時隙和其他時隙的復雜度累加,得到各算法總的計算復雜度為

(13)

(14)

(15)

綜合以上不同算法的復雜度算式,可以發現當系統內總的設備數量、活躍設備數量、占用的子載波信道數、幀長度保持一致時,多用戶檢測算法的計算消耗取決于迭代次數。

3.2 仿真結果及分析

在第31節中,論文分析了3種算法的計算復雜度,給出了總的復雜度算式。為了直觀地表示不同算法的計算復雜度對比,對這3種同類算法進行了仿真實驗。實驗參數設置如下:總設備數量=200,其中活躍設備數量=20,占用的子載波信道數=100,一幀信號內總的時隙數=7,衰弱參數=09,信噪比分別取SNR=5 dB和SNR=10 dB。

根據復雜度分析的結論,迭代次數越多復雜度越高,且其分布具有隨機性。因此,論文進行了1 000幀檢測,取其平均迭代次數,結果如圖1所示。DCS算法與CAGP-MUD算法在所有時隙均具有相近的迭代次數,而CAGGP-MUD算法在所有時隙的迭代次數均明顯減少。這是因為前兩者采用了相同的基于時間相關性的活躍設備檢測方法,且每次迭代僅挑選出一個活躍設備。CAGGP-MUD算法由于采用了衰弱策略,一次迭代能夠挑選出多個活躍設備,有效降低了迭代次數。在信噪比為5 dB和10 dB時分別進行實驗,可以看出,DCS算法和CAGP-MUD算法在低信噪比時迭代次數相比高信噪比時有所增加,但CAGGP-MUD算法的迭代次數保持不變。這是因為DCS算法和CAGP-MUD算法在低信噪比下進行活躍設備檢測時,會反復將某些設備選擇和剔除,導致迭代次數變多。而CAGGP-MUD算法每次迭代挑選出多個活躍設備后,再根據信號估計值的大小進行支撐集修剪,優化了活躍設備的選擇,減少了某些設備被反復迭代的情況,即使在低信噪比下仍能保持較少的迭代次數。此外,從圖1可以看出,這3種算法在第一個時隙需要迭代的次數明顯多于其他時隙,符合論文對于該類算法復雜度分析的結論。這一實驗結果也進一步驗證了文獻[25]的觀點,即利用一幀信號中相鄰時隙間設備所具有的時間相關性可以減少從第二時隙開始的其他時隙的迭代次數。

圖1 不同算法完成1 000次實驗每個時隙需要的平均迭代次數對比圖Fig.1 Comparison of the average iterations required for each slot to complete 1 000 experiments with different algorithms

圖1僅展示了迭代次數,不能完整地表示出各個算法的實際計算消耗,因此在迭代次數實驗的基礎上計算了各算法完成一次實驗的總復雜度,并繪制了如圖2所示的量化對比圖。為了不失一般性,增加了與SMP算法、基于梯度下降的梯度追蹤MUD(gradient descent-based gradient pursuit MUD, GDGP-MUD)算法和基于多步擬牛頓法的梯度追蹤MUD(multi-step quasi-Newton MUD, MSQN-MUD)算法的對比。圖2的結果顯示,在6種比較算法中,本文提出的 CAGP-MUD算法和CAGGP-MUD算法計算復雜度較低。與SMP算法相比,CAGP-MUD算法的計算復雜度僅為SMP算法的15.4%,CAGGP-MUD算法甚至低至SMP算法的11.5%;與DCS算法相比,CAGP-MUD算法的計算復雜度約為DCS算法的33%,CAGGP-MUD算法甚至低至DCS算法的24.6%。由此可見,所提出的兩種算法結合了時間相關性特征和GP,從降低迭代次數和避免矩陣求逆運算兩個角度,降低了多用戶檢測的復雜度。而CAGGP-MUD算法則通過引入衰弱策略,進一步降低了計算復雜度。

圖2 不同算法計算消耗對比圖Fig.2 Comparison of computational cost of different algorithms

圖3給出了各算法在不同信噪比條件下的SER對比情況,其他實驗參數同上文一致。從圖3可以看出,CAGP-MUD算法和CAGGP-MUD算法在低信噪比的環境下SER性能接近或略優于DCS算法,但是在高信噪比的環境下檢測精度有所損失。圖3中普通最小二乘法(ordinary least squares, OLS)曲線代表理想狀態下最小二乘法的檢測精度。也就是說,提出的算法以有限的檢測精度代價換取了復雜度的有效降低。

圖3 不同算法SER性能對比圖Fig.3 Comparison of SER performance of different algorithms

圖4給出了不同活躍設備數情況下CAGP-MUD算法、CAGGP-MUD算法與DCS算法的SER性能對比圖。CAGGP-MUD算法利用決策衰弱,以每次迭代的梯度值乘以衰弱系數作為動態閾值,相比于設定額定閾值的方法,即使活躍設備數目較低也不會限制CAGGP-MUD算法的應用。

圖4 活躍設備數變化時算法的SER性能對比圖Fig.4 SER performance comparison with the number of active devices

圖5給出了衰弱參數對CAGGP-MUD算法的SER性能影響的對比圖。當信噪比較小時,衰弱參數的取值對精度影響不大,而當信噪較大時,取較大的衰弱參數會使得SER精度提升。在實際操作中,當系統中噪聲較大時,可采用較小的衰弱參數來加快檢測。隨著信噪比逐漸增大,衰弱參數對CAGGP-MUD算法SER 性能的影響越來越大。因此,當系統中的噪聲較小時,需選用較大的衰弱參數。

圖5 衰弱參數α對CAGGP-MUD算法的SER性能影響對比圖Fig.5 Comparison of the weakening influence parameter α on the SER performance of CAGGP-MUD algorithm

圖6給出了當SNR=10 dB時,CAGGP-MUD算法每次迭代挑選的活躍設備個數隨衰弱參數變化的對比圖,縱坐標為1 000次實驗及所有時隙的迭代次數的平均值。從圖6可以看出,衰弱參數越小,CAGGP-MUD算法每次迭代挑選出的活躍設備數越多,尤其是在前幾次迭代中,這種影響更加明顯。當迭代次數超過5以后,衰弱參數對每次迭代挑選的活躍設備數的影響降低;當迭代次數超過9以后,衰弱參數的改變對每次迭代挑選的活躍設備數幾乎沒有影響。

圖6 衰弱參數α對每次迭代挑選出的活躍設備數的影響對比圖Fig.6 Comparison of weakening influence parameters α on the number of active devices selected in each iteration

4 結束語

本文分析了mMTC中基于壓縮感知的多用戶檢測算法的復雜度問題,結合活躍設備的時間相關性特征和梯度追蹤算法,提出了CAGP-MUD算法。算法將前一時隙使用梯度追蹤挑選并裁剪后的支撐集賦值給當前時隙作為初始支撐集,通過多次梯度計算更新支撐集并估計活躍設備的信號值。該算法有效降低了多用戶檢測的復雜度,但每次迭代僅挑選出一個活躍設備。進一步,在CAGP-MUD算法框架內引入了決策衰弱策略,提出了CAGGP-MUD算法。CAGGP-MUD算法使用衰弱參數對每次迭代的梯度最大值進行衰弱,并將其作為閾值,挑選梯度信息大于閾值的所有設備,將其索引加入支撐集,通過一次迭代挑選出多個活躍設備,更快地完成檢測。實驗結果表明,CAGP-MUD算法和CAGGP-MUD算法降低了多用戶檢測算法的復雜度。