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

應(yīng)用于空間調(diào)制的低復(fù)雜度A*檢測算法*

張德民，王與凡**,龍云波

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

針對A*檢測算法復(fù)雜度仍然較高的問題，提出了一種將接收天線重排序的檢測算法。在現(xiàn)有A*檢測算法的基礎(chǔ)上增加接收天線分層排序的處理過程，使A*檢測算法中最先選擇的節(jié)點所在的分支更有可能包含最優(yōu)路徑，更早地將不對的節(jié)點排除，大大減少樹搜索時需要訪問的節(jié)點數(shù)。所提算法能夠獲得近似最優(yōu)的檢測性能，同時，與最大似然檢測算法相比復(fù)雜度降低了73%～89%。

空間調(diào)制；接收天線；A*檢測；分層排序

1 引 言

空間調(diào)制(Spatial Modulation,SM)作為一種新的多輸入多輸出(Multiple Input Multiple Output,MIMO)技術(shù)，有效避免了MIMO技術(shù)存在的信道間干擾和天線間同步等問題，目前已在無線通信領(lǐng)域中獲得了廣泛關(guān)注[1]。SM中，任何傳輸周期內(nèi)只有一根發(fā)射天線被激活用來傳輸數(shù)據(jù)，剩余的天線不傳輸信息，而具體哪根天線被激活由輸入信息比特來確定，即激活天線本身攜帶傳輸信息。SM技術(shù)的這種特點使接收端不僅要檢測傳統(tǒng)星座調(diào)制符號，還要檢測激活天線索引。為降低SM系統(tǒng)的檢測復(fù)雜度，各種各樣的低復(fù)雜度檢測算法相繼被提出。

文獻(xiàn)[2]提出了一種分步檢測方案，即先估計激活天線索引，再檢測發(fā)射符號。這種分步檢測方案的固有缺陷是一旦天線索引檢測出錯則全部出錯，因此檢測性能較差。文獻(xiàn)[3]提出的最大似然檢測(Maximum Liklihood,ML)算法是目前公認(rèn)的檢測性能最好的算法，然而，由于ML算法對所有可能的點進(jìn)行窮舉搜索，其復(fù)雜度也是最高的。文獻(xiàn)[4]提出的兩種球形譯碼算法(Tx-SD和Rx-SD)與ML檢測算法相比，不僅能夠獲得近似最優(yōu)的性能，還有效降低了檢測復(fù)雜度。盡管如此，仍然不利于實際應(yīng)用。針對快速硬件處理，文獻(xiàn)[5]提出了一種基于開銷估計的快速檢測算法，將圖論中的A*算法理論引入到信號檢測中。為方便，本文將其稱為A*檢測算法。與常規(guī)SM-MIMO檢測僅取決于已經(jīng)遍歷的前一路徑的成本不同，A*檢測算法不僅考慮前一路徑的成本而且還考慮尚未訪問的子樹的估計成本來遍歷樹。該算法能夠減少硬件延遲的訪問次數(shù)，使其適合于硬件實現(xiàn)。

A*算法雖然在一定程度上減少了樹搜索時需要訪問的節(jié)點數(shù)(Number of Visited Nodes,NVN)，但是當(dāng)某分支第一層的節(jié)點度量值很小而最后幾層的節(jié)點度量值非常大，反之，其他分支第一層的節(jié)點度量非常大而最后幾層的節(jié)點度量值非常小時，NVN的減少量將非常低，復(fù)雜度也會比較高。這是因為在A*算法中，搜索層數(shù)r按照接收天線序號1～Nr的順序進(jìn)行遍歷。因此，本文提出將接收天線序列按照每根天線的平均度量值進(jìn)行降序排列后再遍歷各分支，使許多分支中節(jié)點度量值較大的點排到前幾層，這樣能使最先得到的最小k(t)所在的分支更有可能包含最優(yōu)路徑，更早地將不對的節(jié)點排除，能夠減少NVN，在一定層度上降低A*檢測算法的復(fù)雜度。所提算法不僅保留了A*檢測算法近似最優(yōu)檢測性能的特點，還進(jìn)一步降低了檢測復(fù)雜度。

2 系統(tǒng)模型

考慮一個具有Nt根發(fā)送天線、Nr根接收天線的SM系統(tǒng)，如圖1所示。

圖1 SM系統(tǒng)框圖Fig.1 System block diagram of SM

SM系統(tǒng)中，每一個比特流被分為兩部分，一部分用于選擇激活天線l，l∈{1,2,…,Nt}，長度為lbNt；另一部分用于選擇傳統(tǒng)符號s，假設(shè)采用M階星座調(diào)制，s∈{s1,s2,…,sM}，則該部分的比特長度為lbM。發(fā)送信號x是只有位置l處有符號，其余地方均為零的Nt×1維的向量，即x=[0,0,s,0,…,0]T。接收信號y用Nr×1維向量表示，可以寫成公式(1)的形式：

y=Hx+n。

(1)

式中：H是信道矩陣，n是Nr×1維復(fù)高斯白噪聲矢量。

SM系統(tǒng)中，最大似然檢測算法可以用公式(2)表示：

(2)

式中：yr表示y的第r行，hl,r表示hl的第r行，hl是信道矩陣H的第l列向量，‖·‖F(xiàn)表示范數(shù)。

3 A*檢測算法

在A*算法中，對于節(jié)點(r,t)，使用啟發(fā)式函數(shù)k(t)來確定在樹搜索中訪問節(jié)點的順序。k(t)可以被分解為兩個函數(shù)的和，即k(t)=g(r,t)+h(r,t)，這里t代表樹搜索中的分支號。以圖2為例，t=1,2,3,4；r表示第幾層，即r∈{1,2,…,Nr}，Nr表示接收天線數(shù)；g(r,t)是到當(dāng)前節(jié)點(r,t)的實際路徑成本；h(r,t)是從節(jié)點(r,t)到目標(biāo)的距離的容許啟發(fā)式估計。如果啟發(fā)式函數(shù)不高估從某個節(jié)點到目標(biāo)的距離，則該啟發(fā)式函數(shù)被稱為允許的。

圖2 樹搜索圖Fig.2 The map of tree search

將該算法應(yīng)用到有Nt根發(fā)送天線、Nr根接收天線的SM系統(tǒng)時，根據(jù)公式(2)有

(3)

PED0=0 。

(4)

式中：PEDr指當(dāng)前節(jié)點(r,t)到根節(jié)點的部分歐式距離，即當(dāng)前節(jié)點到根節(jié)點的累積路徑成本。從PED0=0開始，累積式(3)直到其達(dá)到最終成本PEDNr。圖2是收發(fā)天線數(shù)為2、采用QPSK調(diào)制的SM系統(tǒng)采用A*檢測算法的樹搜索過程圖，圖中的4個分支表示有4種發(fā)送向量(每根發(fā)送天線可以傳輸兩種符號)，圓圈中的數(shù)值即為當(dāng)前節(jié)點的部分歐式距離，A*算法中的初始節(jié)點對應(yīng)圖2中樹的根。目標(biāo)節(jié)點是樹中的任意葉節(jié)點，路徑成本函數(shù)g等于PED，剩余的h是子樹成本估計的廣義形式。將h(r,t)例示為下一層的成本，即

h(r,t)=yr+1-Hr+1,ls2。

(5)

A*算法的一般過程為：首先，將初始節(jié)點添加到優(yōu)先級隊列；其次，從隊列中選出具有最低k(t)的節(jié)點；第三，所選節(jié)點是否是目標(biāo)節(jié)點，如果是則退出算法，否則繼續(xù)下一步；第四，計算所選節(jié)點的鄰居節(jié)點的k、g和h值；第五，將鄰居節(jié)點排入優(yōu)先級隊列。結(jié)合圖2，應(yīng)用于SM的A*檢測算法的具體過程如下：

Step1 根據(jù)公式(4)初始化PED0=0。

Step2 求第一層中每一個檢測點的累積度量值，即執(zhí)行公式(3)，并將PED1的值賦給g(1,t)。

Step3 計算出h(1,1)=8,h(1,2)=1,h(1,3)=7，h(1,4)=2；執(zhí)行k(t)=g(r,t)+h(r,t);將第一層所有節(jié)點加入隊列，當(dāng)前隊列為{k(1)=12,k(2)=6,k(3)=9,k(4)=7}。

Step4 此時最小的k值是k(2)，但是此時還未到葉子節(jié)點，即h(1,2)不為零，因此還要繼續(xù)搜索。

Step5 搜索第二層的第二個節(jié)點，更新隊列，得到{k(1)=12,k(2)=8,k(3)=9,k(4)=7}；但是對應(yīng)的h(2,2)值不為零，繼續(xù)搜索。

Step6 此時隊列中最小的k值是k(4)，搜索第二層第四個節(jié)點，更新隊列，得到{k(1)=12,k(2)=8,k(3)=9,k(4)=10}；但是對應(yīng)的h(2,4)值不為零，繼續(xù)搜索。

Step7 此時隊列中最小的k值是k(2),搜索第三層第二個節(jié)點，此時最小的k值是k(2)，對應(yīng)的h(3,2)=0，該節(jié)點所在的分支即為最優(yōu)路徑，搜索結(jié)束。

4 提出的算法

本文提出的算法中，將接收天線索引按照其歐氏距離的期望Er(r=1,2,…,Nr)進(jìn)行降序排列，使許多分支中節(jié)點度量值較大的點排到前幾層，這樣能使最先得到的最小k(t)所在的分支更有可能包含最優(yōu)路徑，更早地將不對的節(jié)點排除，減少NVN。期望Er用下列公式表示：

(6)

與公式(2)將Nr根接收天線上的歐式距離累加求和不同，式(6)只用計算單獨層(即一根接收天線)上的歐氏距離，然后對M×Nt種情況求平均。當(dāng)采用QAM或PSK調(diào)制時，式(6)可以變成

(7)

圖3 排序后樹搜索圖Fig.3 The map of tree search after sorting

以圖3為例進(jìn)一步說明該算法具體檢測過程：首先畫出樹形搜索圖，由于第二層的平均度量值大于第一層，因此，將第二層調(diào)整到第一層，優(yōu)先搜索，此時接收天線順序為(2,1,3)；對排序后的接收天線利用A*檢測算法進(jìn)行樹搜索，找到最優(yōu)路徑點。

5 復(fù)雜度分析

本文中，算法的復(fù)雜度定義為執(zhí)行算法所需實數(shù)乘法的次數(shù)。假設(shè)SM系統(tǒng)有Nt根發(fā)送天線、Nr根接收天線，采用M階QAM調(diào)制。

ML檢測算法的計算復(fù)雜度[6]為C=6NtMNr。

A*檢測算法中，對于第一層節(jié)點，計算g(1,t)(t=1,2…,Nt×M)需要6×Nt×M次實數(shù)乘法；計算h(1,t)需要6×Nt×M次實數(shù)乘法。對于剩下所有層數(shù)的節(jié)點，由上面的分析可知，g(r,t)可以由g(r-1,t)+h(r-1,t)獲得，最后一層h(Nr,t)直接賦零值，因此只用考慮h(r,t)需要的乘法次數(shù)，即6×Nt×M×(Nr-2)。此外，由于并不是所有節(jié)點都被搜索到，因此實際搜索中的復(fù)雜度比6×Nt×M×(Nr-2)小。A*檢測算法的總復(fù)雜度C≤6NtMNr。

本文提出的算法在A*檢測算法的基礎(chǔ)上增加了預(yù)處理過程，考慮文獻(xiàn)[7]已給出，在采用MQAM或MPSK調(diào)制的SM系統(tǒng)中，計算式(6)需要2Nr次實數(shù)乘法。當(dāng)信道慢衰落、每一幀包含大量信息時，式(6)的計算復(fù)雜度是可以忽略不計的。因此，所提檢測算法的復(fù)雜度C≤2Nr+6NtMNr。盡管所提算法增加了預(yù)處理過程，但是由于在一定程度上降低了Nr的搜索空間，增加的2Nr與上式第二項的減少量相比微不足道，因此減少了NVN數(shù)，其復(fù)雜度相比原始A*檢測算法會在一定程度上降低。

由于所提算法和球形譯碼等算法一樣可以獲得近似最優(yōu)的性能，因此一并比較復(fù)雜度。圖4給出了收發(fā)天線數(shù)均為8、采用32QAM調(diào)制時，所提算法和其他算法的復(fù)雜度比較。結(jié)果表明，不同配置下本文所提算法的檢測復(fù)雜度均是所有算法中最低的。這是因為球形譯碼和ML算法僅僅根據(jù)每個節(jié)點的g值進(jìn)行樹搜索，而所提算法不僅根據(jù)每個節(jié)點的g值和h值進(jìn)行樹搜索，還對度量值大的接收天線所在的節(jié)點先搜索，更有可能最先搜索到最優(yōu)點并結(jié)束搜索。此外，信噪比較高時，噪聲對接收端信號檢測的影響越小。由于ML檢測算法在所有情況中都是全搜索，因此檢測復(fù)雜度不隨信噪比變化；但是提出的算法與ML不同，隨著信噪比的增加，不同節(jié)點到根節(jié)點的部分歐式距離的差值增大，進(jìn)行樹搜索時越容易找到最優(yōu)點并結(jié)束搜索。由此可見，所提算法的檢測復(fù)雜度與信噪比有關(guān)。從圖4可知，不同信噪比下，所提算法的復(fù)雜度與原始A*檢測算法相比可以降低8%～20%，與ML算法相比可降低73%～89%。

圖4 Nt=Nr=8、64QAM時算法復(fù)雜度比較Fig.4 Complexity comparison among algorithms with Nt=Nr=8 and 64QAM

圖5給出了收發(fā)天線數(shù)均為16、采用32QAM調(diào)制的SM系統(tǒng)中幾種檢測算法的復(fù)雜度比較。從圖中可以知道，當(dāng)信噪比為26 dB時，所提算法在原始A*檢測算法基礎(chǔ)上復(fù)雜度降低了近20%，與Tx-SD、Rx-SD和ML相比分別降低了近76%、83%、89%。對比圖4和圖5的仿真結(jié)果可以發(fā)現(xiàn)，當(dāng)接收天線數(shù)增大時，所提算法的檢測復(fù)雜度的降低量更顯著。

圖5 Nt=Nr=16、32QAM時算法復(fù)雜度比較Fig.5 Complexity comparison among algorithms with Nt=Nr=16 and 32QAM

6 仿真分析

為驗證提出算法的性能，本節(jié)對其進(jìn)行仿真分析。所有仿真的信道均為已知的平坦瑞利衰落信道，添加均值為零且獨立同分布的高斯白噪聲。

圖6顯示的是收發(fā)天線數(shù)均為8的SM系統(tǒng)中調(diào)制方式分別為4QAM、16QAM、64QAM時的檢測性能對比。由于所提算法在進(jìn)行樹搜索的過程中雖然排除了部分節(jié)點，但是并沒有將最優(yōu)點排除在外；此外，所提算法以最小的k(t)值確定最優(yōu)路徑，保證算法能夠獲得近似最優(yōu)的性能。因此,從圖中可以看出，所提算法能夠達(dá)到和A*檢測算法、球形譯碼算法、ML算法相近的性能。同時，當(dāng)采用不同的調(diào)制方式時，系統(tǒng)的檢測性能明顯不同，64QAM的性能最差，4QAM的性能最好。

圖6 不同調(diào)制方式下算法誤比特性能比較Fig.6 BER performance comparison in different modulation

為進(jìn)一步驗證算法應(yīng)用于SM系統(tǒng)的檢測性能，圖7給出了采用16QAM、在收發(fā)天線數(shù)均為8、16和32時的不同算法性能對比。從該仿真結(jié)果可以看出，天線數(shù)越大，系統(tǒng)性能越好。同時，對于每種天線數(shù)，所提算法都能獲得近似最優(yōu)的性能。

圖7 多激活天線下算法誤比特性能比較Fig.7 BER performance comparison in different activation antennas

7 結(jié) 論

本文針對SM系統(tǒng)下A*檢測算法復(fù)雜度仍然較高的問題，提出了一種對接收天線分層排序的低復(fù)雜度A*檢測算法。該算法在樹搜索之前對接收天線按照歐氏距離平均值降序排列，使最先選擇的節(jié)點所在的分支更有可能包含最優(yōu)路徑，大大減少NVN數(shù)。與ML算法和傳統(tǒng)A*檢測算法相比，所提算法不僅能夠獲得近似最優(yōu)的性能，還能在一定程度上降低檢測復(fù)雜度。下一階段將研究該算法在廣義空間調(diào)制或正交空間調(diào)制中的應(yīng)用。

[1] RENZO M I,HAAS H,GHRAYEB A,et al.Spatial modulation for generalized MIMO:challenges,opportunities,and implementation[J].Proceedings of the IEEE,2014,102(1):56-103.

[2] MESLEH R Y,HAAS H,SINANOVIC S,et al.Spatial modulation[J].IEEE Transactions on Vehicular Technology,2008,57(4):2228-2241.

[3] JEGANATHAN J, GHRAYEB A, SZCZECINSKI L. Spatial modulation:optimal detection and performance analysis[J].IEEE Communications Letters,2008，12(8)：545-547.

[4] YOUNIS A,SINANOVIC S,DI RENZO M,et al.Generalised sphere decoding for spatial modulation[J].IEEE Transactions on Communications,2013，61(7):2805-2815.

[5] KONG B Y，PARK I C. Fast detection for spatial modulation MIMO based on cost estimation[J].Electronics Letters,2016，52(8):671-673.

[6] RAJASHEKAR R,HARI K V S，HANZO L. Reduced-complexity ML detection and capacity-optimized training for spatial modulation systems[J].IEEE Transactions on Communications,2014，62(1)：112-125.

[7] LEE K. Doubly ordered sphere decoding for spatial modulation[J].IEEE Communications Letters,2015，19(5)：795-798.

ALowComplexityA*DetectionAlgorithmforSpatialModulation

ZHANG Demin,WANG Yufan,LONG Yunbo

(Chongqing Key Laboratory of Mobile Communications,Chongqing University of Posts and Telecommunications,Chongqing 400065,China)

In order to solve the high complexity problem of A*detection algorithm,a novel detection algorithm is proposed to order the

antennas. Based on the existing A*detection algorithms,it adds the hierarchical order process of received antennas,which is more likely to include the optimal path for the branch of the first selected node in the A*detection algorithm and exclude the wrong nodes earlier.The algorithm can greatly reduce the number of nodes that need to be accessed when the tree search is performed. The complexity is reduced by about 73%～89% compared with the maximum likelihood detection algorithm.

space modulation;receiving antenna;A*detection;hierarchical order

10.3969/j.issn.1001-893x.2017.12.013

張德民，王與凡,龍云波.應(yīng)用于空間調(diào)制的低復(fù)雜度A*檢測算法[J].電訊技術(shù)，2017,57(12):1422-1426.[ZHANG Demin,WANG Yufan,LONG Yunbo.A low complexity A*detection algorithm for spatial modulation[J].Telecommunication Engineering,2017,57(12):1422-1426.]

2017-03-29；

2017-05-27 Received date:2017-03-29；Revised date：2017-05-27

國家科技重大專項(2017ZX03001021-004)

444934935@qq.comCorrespondingauthor444934935@qq.com

TN929.5

A

1001-893X(2017)12-1422-05

張德民(1955—)，男，廣東梅州人，1988年于北京郵電大學(xué)獲碩士學(xué)位，現(xiàn)為重慶郵電大學(xué)教授、碩士生導(dǎo)師，主要研究方向為通信與信息系統(tǒng)；

Email:zhangdm@cqupt.edu.cn

王與凡(1993—)，女，湖北宜昌人，碩士研究生，主要研究方向為物理層和空間調(diào)制算法；

Email:444935936@qq.com

龍云波(1993—)，男，湖北鄂州人，碩士研究生，主要研究方向為物理層算法實現(xiàn)。

Email:lyb4080@163.com