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

(重慶郵電大學(xué) 移動(dòng)通信技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室，重慶 400065)

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

張德民，王與凡**,龍?jiān)撇?/p>

(重慶郵電大學(xué) 移動(dòng)通信技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室，重慶 400065)

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

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

1 引 言

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

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

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

2 系統(tǒng)模型

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

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

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

y=Hx+n。

(1)

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

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

(2)

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

3 A*檢測(cè)算法

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

圖2 樹(shù)搜索圖Fig.2 The map of tree search

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

(3)

PED0=0 。

(4)

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

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

(5)

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

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

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

Step3 計(jì)算出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é)點(diǎn)加入隊(duì)列，當(dāng)前隊(duì)列為{k(1)=12,k(2)=6,k(3)=9,k(4)=7}。

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

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

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

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

4 提出的算法

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

(6)

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

(7)

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

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

5 復(fù)雜度分析

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

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

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

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

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

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

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

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

6 仿真分析

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

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

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

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

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

7 結(jié) 論

本文針對(duì)SM系統(tǒng)下A*檢測(cè)算法復(fù)雜度仍然較高的問(wèn)題，提出了一種對(duì)接收天線分層排序的低復(fù)雜度A*檢測(cè)算法。該算法在樹(shù)搜索之前對(duì)接收天線按照歐氏距離平均值降序排列，使最先選擇的節(jié)點(diǎn)所在的分支更有可能包含最優(yōu)路徑，大大減少NVN數(shù)。與ML算法和傳統(tǒng)A*檢測(cè)算法相比，所提算法不僅能夠獲得近似最優(yōu)的性能，還能在一定程度上降低檢測(cè)復(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

張德民，王與凡,龍?jiān)撇?應(yīng)用于空間調(diào)制的低復(fù)雜度A*檢測(cè)算法[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

國(guó)家科技重大專(zhuān)項(xiàng)(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)師，主要研究方向?yàn)橥ㄐ排c信息系統(tǒng)；

Email:zhangdm@cqupt.edu.cn

王與凡(1993—)，女，湖北宜昌人，碩士研究生，主要研究方向?yàn)槲锢韺雍涂臻g調(diào)制算法；

Email:444935936@qq.com

龍?jiān)撇?1993—)，男，湖北鄂州人，碩士研究生，主要研究方向?yàn)槲锢韺铀惴▽?shí)現(xiàn)。

Email:lyb4080@163.com