基于貪心策略的大規模MIMO系統信號檢測算法

陳發堂，易 潤，黃 菲

(重慶郵電大學 移動通信重慶市重點實驗室，重慶 400065)

基于貪心策略的大規模MIMO系統信號檢測算法

陳發堂，易 潤，黃 菲

(重慶郵電大學 移動通信重慶市重點實驗室，重慶 400065)

針對傳統球形譯碼性能和計算復雜度受到初始半徑及搜索策略制約的問題，提出了一種新的基于M算法的貪心策略球形譯碼檢測算法，對樹搜索的方法進行了改進，先將該層信號集合中的距離增量進行排序，然后選擇距離增量最小的M個點為信號點，這樣每一次選取的信號點相對該層都是局部最優的。仿真結果表明，相比于傳統球形譯碼檢測算法，當M為1時，該算法可以降低約30%的計算復雜度。使球形譯碼算法的效率得到了很大的提高，可以運用于大規模MIMO系統中。

信號檢測；球形譯碼；貪心策略；M算法

4G網絡是當前各地無線通信系統的主流網絡，信號檢測算法的性能和算法復雜度是整個無線通信系統的關鍵部分。然而，大規模MIMO的引入帶來系統容量和頻譜利用率大幅度增加的同時也給接收端檢測技術帶來更大的挑戰，信號檢測的算法復雜度呈指數級增長。這使得接收端準確恢復出發送端天線的信號面臨一個大的難題。因此，研究性能較好且算法復雜度適中的信號檢測算法是整個系統的關鍵。

目前已經提出了很多信號檢測算法，其中ML(最大似然)算法是檢測性能最優的算法，其本質是遍歷了所有可能發送信號符號的星座點，以距離接收信號最近的星座點作為發送信號，但算法復雜度太高。于是各種降低復雜度并保證性能不過分損失的信號檢測算法被提出。如ZF(迫零)算法、最小化均方誤差算法(MMSE)、QR分解算法等。

球形譯碼(SD)算法在性能和復雜度方面取得了很好的折中，它是一種能得到最大似然檢測性能的低復雜度檢測算法，通過設定一個以接收向量為中心的超球，僅搜索超球內的格點來找到最大似然解。球形譯碼算法的性能依賴于初始半徑的選擇，初始半徑選擇太大會導致樹搜索時有太多不必要的搜索點，導致時間復雜度的提高。初始半徑太小可能會導致在給定的多維球體內沒有解，導致性能的大幅度降低。所以要降低球形譯碼算法的復雜度和提高譯碼性能必須準確地設置搜索半徑。

文獻[1]提出的基于閾值的球形譯碼能夠有效降低復雜度，但對獲取半徑過程受到閾值的影響，其在低信噪比的情況采用MMSE方法獲取；文獻[2]給出了一種低復雜度球形譯碼，該算法采用固定閾值作為可靠性判斷標準，將ZF算法與球型譯碼算法相結合，但ZF算法性能較低；文獻[3]提出的蟻群球形譯碼有效降低了算法復雜度，但涉及到迭代和概率問題，實現過程繁瑣，不適用于大規模MIMO系統。文獻[4]提出了一種貪心搜索的策略求解TSP問題；文獻[5]提出了一種基于黃金分割的搜索半徑球形譯碼，減少了搜索格點；文獻[6-10]提出了對球形譯碼初始半徑和搜索樹進行改善來降低算法復雜度，但是都受到初始半徑的約束。針對球形譯碼存在的缺點，本文提出了一種基于M算法的貪心策略球形譯碼(SDBGS-M)算法。該算法是在球形譯碼檢測算法的基礎上改進樹搜索的方法而得到的。

該算法不需設置初始搜索半徑，不再像傳統球形譯碼算法那樣按照星座圖從左向右依次搜索，而是先將該層信號集合中的距離增量進行排序，然后選擇距離增量最小的M個點為信號點，這樣每一次選取的信號點相對該層都是局部最優的。從而大幅度降低了搜索復雜度，使球形譯碼算法的效率得到了明顯提高，能夠完全適用于大規模MIMO中。

1 系統模型

MIMO系統由圖1所示，發射端有M根天線，接收端有N根天線。編碼后的比特流映射到M維的傳輸符號矢量X∈OM，O表示發送信號星座點向量空間。

圖1 M×N的MIMO系統原理圖

經過平坦瑞利衰落的高斯白噪聲信道后，MIMO系統接收端信號可表示為

y=Hx+n

(1)

式(1)采用復數信號模型。其中，y=[y1,y2,…,yN]T是接收天線端的信號向量，x=[x1,x2,…,xM]T是發射天線端的發射信號，H為M×N的信道傳輸矩陣且滿足高斯分布；n為各項獨立同分布且均值為零、方差為σ2的高斯分布。

ML作為MIMO系統的最優檢測算法，就是使n達到最小。而ML本質上是在發送信號星座點矢量空間中尋找距離接收信號矢量最近的格點的問題，也就相當于整數域的最小二乘問題，即

(2)

2 球形譯碼

球形算法的基本思想是：首先計算出球形譯碼的初始搜索半徑ρ0，然后以接收信號矢量為球心，以ρ0為半徑的球體內進行搜索格點，記錄下搜索路徑的同時根據每一維信號柵格點中格點的距離增量更新搜索半徑ρ，循環往復，直到半徑ρ內沒有符號可以搜索，最后一次記錄的搜索路徑即為所求。

球形譯碼算法搜索前需先計算出初始搜索半徑ρ0，其半徑定義為

(3)

式中：n為接收信號的維數；σ2為高斯白噪聲方差；α為初始化半徑系數。

在球形譯碼算法中，把接收信號向量空間看作以y為中心的球，即

(4)

對H進行QR分解，可得

(5)

式(5)變為

(6)

將式(6)展開，可得

(7)

定義部分歐氏距離為

(8)

假設當前搜索的是第1層，則歐氏距離為

(9)

相鄰節點之間的部分歐氏距離之間的關系為

(10)

MIMO信號檢測問題可以看作是一個具有K層的樹，搜索所有葉子節點找出根節點和葉子節點之間最小的的歐氏距離[6]。

圖2是QPSK調制下球形譯碼的搜索樹。

圖2 QPSK調制下的球形譯碼算法的搜索樹

搜索時，從D=K層開始搜索，逐層向下搜索直到D=1，此時的部分歐氏距離如果小于初始半徑ρ0，則保存該條搜索路徑及根節點到該葉子節點的歐氏距離，并用此值替換初始半徑ρ0并重新開始搜索；算法采用的是深度優先搜索方式進行，按照信號的星座點順序，從左向右依次枚舉所有的星座點。顯然在這種方式下，半徑ρ收斂得很慢。

鑒于球形譯碼算法的缺點，本文提出一種基于貪心策略球形譯碼(SDBGS-M)算法，它對初始半徑不敏感，同時還能夠讓半徑ρ收斂更快，進一步減少搜索的信號點數，從而快速找到最優解。

3 基于貪心策略的球形譯碼檢測算法

貪心策略是指所求問題的整體最優解可以通過一系列局部最優的選擇而得到。貪心算法通常以自頂向下的方式進行，每作一次貪心選擇就將所求問題簡化為規模更小的問題。SDBGS算法遵循深度優先搜索的原則，但是在搜索過程中，不再按照星座圖從左向右依次搜索，而是選擇該層信號集合中距離增量最小的信號點，這樣每一次選取的信號點，相對該層都是局部最優的[11]。例如在搜索第D層信號時，首先計算之前第D+1層的信號XD+1相對于該層的星座點XD的距離增量值T(y(XKD + 1)D,RD,DXD)，然后按照從小到大的順序將其排序，選擇其中距離增量最小的M個信號點繼續向下搜索。詳細說明如下：

假設當前搜索的是第一層，則歐氏距離表示為

(11)

T(·)用來表示距離增量，把式(11)寫成分段式如下

(12)

從第K維開始，根據式(8)計算YK與XK之間的距離增量為

T(yK,RK,KX1),T(yK,RK,KX2),…,T(yK,RK,K·X2r)然后對其中的距離T(·)進行從小到大排序：

T(yK,RK,KXi1)

T(yK,RK,KXii)<…

(13)

其中，i1,i2,…,i2r∈2r。

選擇距離增量最小的M個T(yM,RM,MXi1)對應的Xi1作為第K維的信號點，進行向下搜索，下面的每一維在選取信號點時都按照這種方式進行，如果在某一維距離增量之和已經大于ρ，那么該維度上的其他信號點就不必搜索，回溯到上一維，繼續進行搜索。如果直到D=1時沿這條搜索路徑的距離增量和不大于ρ，那么保存下這條路徑，同時以此時的距離增量和去替換ρ值。

以QPSK調制為例，基于M算法的貪心策略球形譯碼算法的搜索樹如圖3和4所示，M的值分別為1和2，虛線圓圈里面的點是這次搜索中，離發送端最近的M個節點，即距離最小的M個星座點，每一次搜索都從距離增量中選取最小的M個星座點向下搜索，直到搜索結束。

圖3 QPSK調制下的SDBGS-M算法的搜索樹(M=1)

圖4 QPSK調制下的SDBGS-M算法的搜索樹(M=2)

4 仿真性能分析

本文通過仿真將SDBGS-M算法與SD算法在相同信道模型下的譯碼復雜度和誤碼率性能進行了比較。仿真中，M取值1或者2，譯碼復雜度以平均訪問的節點個數為度量。本文對QPSK、16QAM這2種調制方式和4×4、8×8這2種天線配置下的算法性能和復雜度進行比較，仿真參數如表1所示。

表1 仿真參數表

仿真參數取值天線配置4×4&8×8OFDM符號數14信號檢測算法SDBGS-M算法M1或2調制方式QPSK&16QAM帶寬20MHz無線信道噪聲0～20dB

圖5和圖6分別為4×4和8×8 MIMO系統下傳統信號檢測算法與SDBGS-M算法的誤碼率性能比較圖。可以看出，在相同信噪比和天線配置下，傳統球形譯碼算法和基于貪心策略的球形譯碼檢測算法的性能在高階調制下要低于低階調制；在相同信噪比和相同調制方式的配置下，多天線會增加系統的信噪比。其次由于SDBGS算法是深度優先搜索球形譯碼檢測算法的一個變形，其只是對搜索點進行了排序，然后選擇該層信號集合中距離增量最小的信號點向下搜索，所以SDBGS-M算法性能與SD算法差距不大，但算法復雜度要少很多。

圖5 4×4天線，不同調制方式下算法性能對比

圖6 8×8天線，不同調制方式下算法性能對比

圖7和圖8分別表示4×4和8×8 MIMO系統QPSK調制下的SD算法與SDBGS算法檢測復雜度比較。從圖可以看出，SDBGS-M算法的復雜度相比于傳統球形譯碼算法均有不同程度的降低。特別是在低信噪比區域，有很大的優勢，對于4×4天線和QPSK調制下，當SNR=0,M=1,2時，分別為169，119和70，SDBGS-1比球形譯碼算法的搜索點數減少了50個搜索點數，約占前者的1/3，SDBGS-1算法的檢測復雜度比傳統SD算法減少22%左右。對于8×8 QPSK系統能減少28%左右。因此，在高階調制下，基于貪心策略的球形譯碼檢測算法有非常高的系統增益。

圖7 4×4天線算法復雜度分析

圖8 8×8天線算法復雜度分析

基于貪心策略的球形譯碼算法有個缺點：在選擇符號之前必須首先計算出這一層所有星座點到接收符號的距離，選取最小值對應的符號，排序需要消耗一些時間，因此在實際項目中，選取M=1獲得更少的時間開銷。

圖9是兩種算法在4×4 MIMO系統中QPSK調制下譯碼過程的搜索半徑收斂示意圖。圖中曲線①是SDBGS-1的搜索半徑收斂曲線，曲線②是球形譯碼算法的搜索半徑收斂曲線，r是最優解的歐氏距離值，K是球形譯碼算法初始搜索半徑值，基于貪心策略的球形譯碼算法初始搜索半徑為無窮大。從圖中可以看出，基于貪心策略的球形譯碼算法的搜索半徑收斂速度明顯快于球形譯碼算法的收斂速度，這就是基于貪心策略的球形譯碼算法計算復雜度低于球形譯碼算法的本質原因。SDBGS-1算法相比傳統SD算法節省約30%的譯碼時間。

圖9 SD算法和SDBGS-1算法的搜索半徑收斂圖

基于貪心策略的球形譯碼算法的性能雖然沒有達到ML算法的性能，但該算法通過貪心策略選取局部最優點，加快了搜索半徑的收斂速度，從而減少了不必要的搜索點數，降低了計算復雜度。同時基于貪心策略的球形譯碼算法不需要提前計算出一個初始搜索半徑，因此該算法有效縮減了譯碼時間，大大降低了球形譯碼的復雜度。而且在低信噪比范圍內，隨著天線數和調制階數的增加，基于貪心策略的球形譯碼檢測算法的優越性越大。

5 小結

本文提出了一種基于貪心策略的球形譯碼檢測算法，它是深度優先的球形譯碼檢測中的一種變形。該算法對搜索點進行了排序，然后通過貪心策略選取局部最優點向下搜索，從而減少了不必要的搜索點數，加快了搜索半徑的收斂速度，降低了計算復雜度。仿真結果表明，特別是在低信噪比和高調制階數條件下，SDBGS算法檢測復雜度對比傳統球形譯碼有明顯優勢且容易實現，可以運用于大規模MIMO系統中。

[1] 陳發堂，梁濤濤，李小文.LTE-A系統中球形譯碼檢測算法研究[J].電子技術應用，2012(1)：85-89.

[2] 袁東東，仇潤鶴.基于LTE系統的一種低復雜度的球形譯碼算法[J].通信技術，2015，48(2)：151-155.

[3] 解志斌，鄒維辰，薛同思.一種低復雜度的MIMO系統球形檢測算法[J].船舶科學技術，2013，35(8)：28-33.

[4] 王秋芳，袁東鋒，梁道雷. 一種求解TSP的貪心遺傳算法[J]. 制造業自動化，2013，43(2)：162-168.

[5] FU W H，ZHAO C B，WEI W. Improved sphere decoding algorithm in TD-LTE system[C]// 2011 IEEE 3rd International Conference on Communication Software and Networks (ICCSN).[S.l.]：IEEE，2011：514-517.

[6] SHIM B，KANG I.On further reduction of complexity in tree pruning based sphere search[J].IEEE transactions on Communications，2010，2(58)：417-422.

[7] KIM M，KIM J. Applications of SDR exact-ML criterion to tree-searching detection for MIMO systems[C]//2014 8th International Conference on Signal Processing and Communication Systems (ICSPCS). [S.l.]：IEEE，2014：1-7.

[8] LI S P，WANG L，CHEN F C. Ordered sphere decoding detection algorithm for MIMO systems[C]//Control and Decision Conference. [S.l.]：IEEE，2012：3322-3325.

[9] MRINALEE S，GARG H-P，MATHUR G，et al. Improved radius selection in sphere decoder for MIMO System[C]//2014 International Conference on Computing for Sustainable Global evelopment. [S.l.]：IEEE 2014：161-165.

[10] Sonoda Y ，Hua-An Zhao ，Improved Sphere Decoding Algorithm with Low Complexity for MIMO Systems[C]//2014 IEEE/CIC International Conference on Communications in China (ICCC). [S.l.]：IEEE，2014： 11-15.

[11] SONODA Y，ZHAO H A. Improved sphere decoding algorithm with low complexity for MIMO systems[C]// 2014 IEEE/CIC International Conference on Communications in China (ICCC). [S.l.]：IEEE，2015：11-15.

責任編輯：許 盈

Signal detection algorithm based on greedy strategy in large-scale MIMO system

CHEN Fatang, YI Run, HUANG Fei

(ChongqingUniversityofPostsandTelecommunications，ChongqingKeyLabofMobileCommunicationsProtocol,
Chongqing400065,China)

In view of the problem that traditional sphere decoding performance and the computational complexity are restricted by the initial radius and the search strategy, a new greedy strategy sphere decoding detection algorithm based on M algorithm is presented in this paper and the tree search method is improved. Firstly, the distance increment of the signal set in the layer is ordered, and thenMpoints with incremental distance minimum are selected as signal points, so that each selected signal point is locally optimal in the layer. Simulation results show that, compared to the traditional sphere decoding algorithm, the computational complexity can be reduced about 30% by the algorithm when theMis 1. The efficiency of the sphere decoding algorithm is greatly improved and can be also used to the massive MIMO.

signal detection; sphere decoding; greedy strategy; M algorithm

陳發堂，易潤，黃菲. 基于貪心策略的大規模MIMO系統信號檢測算法[J].電視技術，2017，41(1)：27-31. CHEN F T，YI R，HUANG F. Signal detection algorithm based on greedy strategy in large-scale MIMO system [J].Video engineering，2017，41(1)：27-31.

TN915

A

10.16280/j.videoe.2017.01.006

重慶市教委科學技術研究項目(KJ1500428)

2016-05-24