陳發(fā)堂，易 潤，黃 菲

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

基于貪心策略的大規(guī)模MIMO系統(tǒng)信號檢測算法

陳發(fā)堂，易 潤，黃 菲

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

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

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

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

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

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

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

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

1 系統(tǒng)模型

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

圖1 M×N的MIMO系統(tǒng)原理圖

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

y=Hx+n

(1)

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

ML作為MIMO系統(tǒng)的最優(yōu)檢測算法，就是使n達(dá)到最小。而ML本質(zhì)上是在發(fā)送信號星座點矢量空間中尋找距離接收信號矢量最近的格點的問題，也就相當(dāng)于整數(shù)域的最小二乘問題，即

(2)

2 球形譯碼

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

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

(3)

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

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

(4)

對H進行QR分解，可得

(5)

式(5)變?yōu)?/p>

(6)

將式(6)展開，可得

(7)

定義部分歐氏距離為

(8)

假設(shè)當(dāng)前搜索的是第1層，則歐氏距離為

(9)

相鄰節(jié)點之間的部分歐氏距離之間的關(guān)系為

(10)

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

圖2是QPSK調(diào)制下球形譯碼的搜索樹。

圖2 QPSK調(diào)制下的球形譯碼算法的搜索樹

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

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

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

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

假設(shè)當(dāng)前搜索的是第一層，則歐氏距離表示為

(11)

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

(12)

從第K維開始，根據(jù)式(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)對應(yīng)的Xi1作為第K維的信號點，進行向下搜索，下面的每一維在選取信號點時都按照這種方式進行，如果在某一維距離增量之和已經(jīng)大于ρ，那么該維度上的其他信號點就不必搜索，回溯到上一維，繼續(xù)進行搜索。如果直到D=1時沿這條搜索路徑的距離增量和不大于ρ，那么保存下這條路徑，同時以此時的距離增量和去替換ρ值。

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

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

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

4 仿真性能分析

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

表1 仿真參數(shù)表

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

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

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

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

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

圖7 4×4天線算法復(fù)雜度分析

圖8 8×8天線算法復(fù)雜度分析

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

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

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

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

5 小結(jié)

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

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

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

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

[4] 王秋芳，袁東鋒，梁道雷. 一種求解TSP的貪心遺傳算法[J]. 制造業(yè)自動化，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.

責(zé)任編輯：許 盈

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

陳發(fā)堂，易潤，黃菲. 基于貪心策略的大規(guī)模MIMO系統(tǒng)信號檢測算法[J].電視技術(shù)，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

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

2016-05-24