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）