0 引言

    復雜的多條射頻鏈路與天線間同步技術應用于大規模多輸入多輸出^[1](Massive Multi-input Multi-output，Massive MIMO)系統,導致系統的硬件實現難度大并且運算復雜度高。空間調制^[2](Spatial Modulation，SM)技術是一種利用激活發送天線的序號和調制符號共同表示發送信息的新型傳輸方案,可完全消除空間多路MIMO系統中接收信號間的相互干擾,具有較高的傳輸速率，被認為是一種新型的低復雜度與節能的多輸入多輸出(MIMO)傳輸方案，近年來受到業界的廣泛關注，關于SM^[3]系統低復雜度的檢測算法相繼被提出。文獻[4]采用先對激活天線索引估計再對發送符號檢測。這種方案檢測性能較差，一旦天線索引檢測出錯則全部出錯。文獻[5]提出的是最大似然檢測算法，但由于ML算法窮舉遍歷所有可能的點，它的復雜度也非常高。文獻[6]提出的Tx-SD、Rx-SD兩種球形譯碼算法與最大似然檢測算法相比有近似最優的性能并減少了檢測復雜度，但是不利于硬件實現。

    為了平衡好復雜度和檢測性能之間的關系，本文將A-Star算法理論引入到信號檢測中。A-Star算法不僅考慮上一個路徑的成本還考慮未搜索子樹的估計成本。該算法減少了硬件訪問次數，非常適合硬件實現。該檢測算法先將接收天線序列按度量值從大到小排序，再遍歷各子樹，這種方案將度量值小的節點排列到后幾層，能夠較早地排除有錯節點，使所選分支盡可能包括最優路徑。提出的算法在減少復雜度的同時，還能保證A-Star算法近似最優的檢測性能。

1 系統模型

    假定發送天線為N_u根，接收天線為N_v根通過準靜態頻率平坦衰落信道進行通信的多天線SM系統可以被建模為如圖1所示，SM的基本思想是將待發送的信息分為兩部分，一部分用于選擇激活發送天線的序號，另一部分用于選擇調制符號^[7]。M是調制符號集合中元素總數大小，激活發送天線攜帶log₂N_u個比特信息，調制符號攜帶log₂M個比特信息，所以發送天線每次能有效地傳輸m=log₂N_u+log₂M個比特。l_u表示激活發送天線的序號，并且l_u∈{1，2，…，N_u}，S_u表示發送的調制符號，且S_u∈{S₁，S₂，…，S_M}。

2 A-Star算法

    在A-Star算法樹搜索中，訪問節點(v，u)的順序通過啟發式函數k(u)確定。啟發式函數k(u)可分為初始節點到(v，u)節點實際路徑成本g(v，u)和從節點(v，u)到目標成本函數h(v，u)，即k(u)=g(v，u)+h(v，u)。接收天線數用N_v表示，樹搜索中的分支號為u，在樹搜索圖2中，u∈{1，2，3，4}；層號用v表示，v∈{1，2，…，N_v}。

    把A-Star算法應用于根接收天線和根發送天線的空間調制系統中，結合式(3)得：

    根節點與目前節點(v，u)的累積路徑成本表示為P_v，從式(5)開始P₀=0，通過累積式(4)最終累積到P_Nr。圖2為2根收發天線、采用QPSK調制的SM系統通過A-Star算法的樹搜索過程圖。4種發送向量分別用圖2中的4個分支表示，當前節點的部分歐幾里得距離(簡稱歐氏距離)用搜索樹中灰色圈的數值表示，搜索樹的根為A-Star算法初始節點。P_v等于初始節點到(v，u)節點的實際路徑成本g(v，u)，h(v，u)為目標成本。式(6)中a(v，u)代表當前節點的成本a_v+1，l，是信道矩陣A的元素。

    A-Star算法結合圖2從搜索樹第一層開始執行以下步驟，具體過程如下：

    (1)根據式(5)，把P₀初始化為0。

    (2)根據式(4)，計算出第一層中各個檢測點的累積成本值，令P₁=g(1，u)。

    (3)通過圖2可得出h(1，1)=e，h(1，2)=f，h(1，3)=g，h(1，4)=h；執行啟發式函數k(u)=g(v，u)+h(v，u)，則當前隊列k(u)為k(1)=a+e，k(2)=b+f，k(3)=c+g，k(4)=d+h。

    (4)通過比較k(u)判斷出此時最小的值，若此時最小點目標成本值不等于0，則表明還沒到到葉子節點，所以需要繼續搜索。

    (5)上一步確定了第一層最小節點，接著對最小節點的第二層的下一節點進行搜索，并更新隊列k(u)。但是此時的最小點目標成本值不為0，所以還需要繼續搜索。若此時最小點的值為0，該分支為最優路徑，結束搜索。

3 分層排序A-Star算法

    本文提出的分層排序A-Star算法先計算出接收天線索引的歐氏距離期望E_r(r=1，2，…，Nv)，然后對其進行降序排列，使分支中節點度量值較小的點排到后幾層，這樣能排除有錯的節點，使所選分支盡可能包括最優路徑，能夠極大縮小所需訪問節點數。期望E_r可表示為如下公式：

    式(7)只是運算了一根接收天線上的歐氏距離，再求M×N_u種情況的平均值。當使用正交幅度調制或相移鍵控調制時，式(7)可表示為表達式(8)。

    將各接收天線索引的歐氏距離期望值Er降序排列，然后把排序后的接收天線索引序列作為搜索層數序列，假設平均度量值排序為如圖3所示，畫出樹形搜索圖。結合A-Star算法對排序后的接收天線進行樹搜索，找到最優路徑。

4 復雜度和性能分析

4.1 復雜度分析

    本文運算復雜度用算法過程中實數乘法運算數量來衡量。假設SM系統采用M階正交幅度調制方式，發送天線和接收天線分別為N_u根和N_v根。ML算法可能發射向量的總數是N_uM，需要6N_v次實乘，因此ML算法的計算復雜度C=6N_uMN_v^[8]。A-Star算法計算第一層節點的g(l，u)和h(l，u)都需要6×N_u×M次實數乘法；若是除第一層之外所有層數的節點只需要考慮h(l，u)，乘法次數為6×N_u×M×(N_v-2)。此外，因為并不是都能遍歷到所有節點，所以實際遍歷的復雜度為6×N_u×M×(N_v-2)。

    本文提出的方案是在A-Star算法的基礎上增加了分層排序預處理過程， SM系統中式(7)在多進制數字相位調制或多進制正交幅度調制情況下，復雜度C=2Nv。當每一幀有大量數據或信道慢衰落時，式(7)可以忽略計算復雜度，因此提出的檢測算法復雜度C≤2N_v+6N_uM(N_v-2)。雖然本文算法添加了分層排序預處理過程，但是N_v的搜索空間降低了，復雜度中增加的2N_v與6N_uM(N_v-2)的減少量相比是微不足道的，因此減少了所需訪問節點數，與A-Star檢測算法相比復雜度降低了。

    為了進一步比較本文提出的算法與ML算法、TX_SD算法、RX_SD算法^[9]和A-Star算法的計算復雜度，本文計算了SM系統在N_u=N_v=8、調制方式為64QAM時和在N_u=N_v=16、調制方式為32QAM時幾種不同算法的復雜度，其結果分別如圖4和圖5所示。

    從圖4和圖5中可以看出，在SM系統中，ML檢測算法在所有情況下都是全搜索的，所以ML算法的計算復雜度極高。當調制方式為64QAM、N_u=N_v=8時，本文算法的計算復雜度約為ML算法計算復雜度的4%，與TX_SD算法、RX_SD算法和A-Star算法相比分別降低了近55%、42%、20%。對比圖4和圖5仿真結果，發現接收天線數量增加時，本文提出的算法復雜度顯著降低。

4.2 性能分析

    本節在不同參數下的SM系統中對本文的算法進行仿真，在仿真中，信道模型均為瑞利衰落信道，噪聲為加性高斯白噪聲。圖6的仿真系統參數為N_u=N_v=8，4QAM、16QAM、64QAM調制。當采用不同的調制方式時，系統的檢測性能明顯不同，性能最好的是4QAM，性能最差的是64QAM。

    圖7仿真的系統參數為16QAM調制下，N_u=N_v分別取8、16和32。仿真結果表明，隨著天線數的增加，本文提出的算法都能獲得近似最優的性能，同時表明隨著天線數的增加，系統性能也越好。

5 結論

    在空間調制系統中，ML最優檢測算法需要同時遍歷可能發送的調制符號組合和激活天線組合，計算復雜度較高，不利于硬件實現。針對此問題，本文提出了一種基于A-Star算法分層排序的低復雜度算法，首先對接受天線進行分層并排序，然后根據排序結果改變樹搜索結構并排除錯的節點，使所選分支盡可能包括最優路徑。理論分析和仿真結果表明，該算法極大地縮小了接收端的搜索范圍，實現了計算復雜度與系統性能的優化，具有較高的工程應用價值。

參考文獻

[1] 王奔，張文彬，趙洪林.空間調制信號的低復雜度球形譯碼算法[J].哈爾濱工業大學學報，2017，49(5)：22-30.

[2] XIAO L，YANG P，FAN S，et al.Low-complexity signal detection for large-scale quadrature spatial modulation systems[J].IEEE Communications Letters，2016，20(11)：2173-2176.

[3] RENZO M D，HAAS H.Transmit-diversity for spatial modulation(SM)：towards the design of high-rate spatially-modulated space-time block codes[C].IEEE International Conference on Communications.IEEE，2011：1-6.

[4] RAJASHEKAR R，HARI K V S，HANZO L.Antenna selection in spatial modulation systems[J].IEEE Communications Letters，2013，17(3)：521-524.

[5] NTONTIN K，RENZO M D，PEREZ-NEIRA A，et al.Performance analysis of multistream Spatial Modulation with maximum-likelihood detection[C].Global Communications Conference.IEEE，2013：1590-1594.

[6] YEONG L H，WOONG P Y，MIN K J，et al.A low complexity sphere decoding algorithm based on double ordering for generalized spatial modulation[C].Symposium of the Korean Institute of Communications and Information Sciences，2016.

[7] NTONTIN K，RENZO M D，PEREZ-NEIRA A I，et al.A low-complexity method for antenna selection in spatial modulation systems[J].IEEE Communications Letters，2013，17(12)：2312-2315.

[8] MEN H，JIN M.A low-complexity ML detection algorithm for spatial modulation systems with PSK constellation[J].IEEE Communications Letters，2014，18(8)：1375-1378.

[9] WANG B，ZHANG W，ZHAO H，et al.Low complexity sphere decoding algorithm for spatial modulation signals[J].Journal of Harbin Institute of Technology，2017，49(5)：22-30.

作者信息:

王華華，陳東風，馬  昶，亢  成

（重慶郵電大學 通信與信息工程學院，重慶400065）