张新贺, 吴金隆, 门宏志, 金明录

(1. 大连理工大学信息与通信工程学院, 辽宁 大连 116024;

2. 辽宁科技大学电子与信息工程学院, 辽宁 鞍山 114051)



基于二进制二次规划全局最优性条件的GSSK系统的检测算法

张新贺1,2, 吴金隆1, 门宏志1, 金明录1

(1. 大连理工大学信息与通信工程学院, 辽宁 大连 116024;

2. 辽宁科技大学电子与信息工程学院, 辽宁 鞍山 114051)

摘要：广义空间位移键控(generalized space shift keying, GSSK)技术作为大天线技术和绿色通信技术相融合的优选方案受到了业界的广泛兴趣,其特点是在每一时刻只激活几根天线发送已知信号,利用激活天线的序号来传递信息。基于最大似然(maximum likelihood, ML)准则的GSSK检测器,当天线数较多时,其计算量太大,给实际应用带来困难,为此人们热衷于研究简化的次优检测算法。给出了一种基于二进制二次规划全局最优性条件的GSSK系统的检测算法。该算法首先利用最优判决准则判断发送信息,然后根据已判断出的发送信息来确定发送天线的组合,进而得到发送的二进制比特流。仿真结果表明,所提出的新算法在性能上优于已有的正交匹配追踪(orthogonal matching pursuit, OMP)、凸超集松弛(convex superset relaxation, CSR)等次优检测算法,复杂度又低于ML算法,在性能和复杂度之间得到较好的折中。

关键词：广义空间位移键控; 二进制二次规划; 全局最优性条件; 检测算法

0引言

随着移动用户对通信需求的飞速增长,迫切需要更高的数据速率、更高的频谱利用率和更低的实现复杂度的宽带通信技术来满足无线通信的需求。多天线多输入多输出(multiple input multiple output,MIMO)技术,可以实现更高频谱利用率的宽带无线通信。但是MIMO技术存在信道间干扰(inter-channel interference,ICI)、天线间同步(inter-antenna synchronization,IAS)和多射频链路的问题,这就增加了接收端检测和解调的难度。

空间调制(space modulation,SM)[1-5]是最近提出的一种新的MIMO传输技术,较好地克服了原MIMO技术的一些缺陷。其主要特点是在每一时刻只有一根天线被激活用于发送数据,将发送天线在天线阵列中的序号也作为一种新的“调制方式”来传输数据,这样可以避免信道间干扰和天线间同步问题,因此降低了接收端解调的难度。但是在接收端最大似然(maximum likelihood, ML)最优检测需要遍历搜索被激活的天线序号和天线发送的符号,复杂度较高。空间位移键控(space shift keying, SSK)[6-7]是SM的一种简化形式,它只利用天线序号来传递信息,而发送的信号是已知的信号。为了提高传输速率,在发送端可以激活多根天线,称为广义空间位移键控(generalized space shift keying, GSSK)[8-11]。因为在被激活的天线上发送相同的信号,在接收端只需检测发送天线的序号,无需判断天线发送的符号,复杂度较SM有所降低。另外,目前大天线技术和绿色通信技术受到业界的广泛兴趣,而GSSK技术作为这两个技术融合的优选方案受到了业界的广泛关注[2]。

与一般的MIMO系统一样,广义空间位移键控的最优解调也是基于ML准则的算法,但是其计算量会随着天线数量的增加呈现指数型增长趋势[12],给实际应用带来困难,特别大天线情形下更是如此，因此人们热衷于研究低复杂度的次优检测算法。传统的破零(zero forcing,ZF)、最小均方误差(minimum mean square error,MMSE)等算法的计算复杂度很低,但是性能有限。最近，很多次优检测算法被提出,以期获得较好的检测性能,如:正交匹配追踪(orthogonal matching pursuit,OMP)算法[13]、凸超集松弛(convex superset relaxation,CSR)算法[14]、半定松弛(semidefinite relaxation,SDR)算法[14]等。但是上述算法在性能与ML算法仍存在一定差距。

与上述算法的思路不同,本文从另一个角度提出一种基于二进制二次规划全局最优性条件的GSSK次优检测算法,该算法在性能上均优于上述次优检测算法,与ML性能基本相当。

本文余下内容安排如下:第1节介绍GSSK系统模型;第2节简要介绍二进制二次规划问题;在第3节给出基于二进制二次规划的GSSK系统的检测算法;第4节对仿真结果进行分析;最后在第5节给出本文的结论。

1系统模型

假设MIMO系统的发送天线数为NT,接收天线数为NR,每一时刻激活天线数为nt,GSSK系统模型如图1所示。

图1　GSSK系统模型

表1　GSSK映射表

因为GSSK系统也是一个MIMO系统,假设信道为平坦瑞利衰落信道,且信道增益在一个符号周期内保持不变,则接收信号可表示为

y=Hx+n

(1)

式中，y=[y1,y2,…,yNR]T为NR维接收信号矢量,x=[x1,x2,…,xNT]T为NT维发送信号矢量,由于每一时刻只激活nt根天线,因此x矢量中包括nt个“1”,NT-nt个“0”。H是NR×NT维的信道增益矩阵,每个元素hi,j为独立同分布的零均值、单位方差的复高斯随机变量;n=[n1,n2,…,nNR]T是均值为0,方差为σ2的加性复高斯白噪声矢量。

下面考虑式(1)的ML检测问题,其准则可以表示为

(2)

式中,M为发送信号矢量集合。

因为xi的取值只有1和0两种可能,因此式(2)的优化问题可以转化为二进制二次规划问题。

即

(3)

将式(3)实数化处理,得

(4)

式中，Re(·)，Im(·)分别表示取其实部和虚部。因此式(2)的最大似然检测准则可表示为等价的二进制二次规划问题:

(5)

2二进制二次规划问题

由第1节知道,GSSK信号的ML检测问题可看成二进制二次规划问题。本节给出二进制二次规划全局最优性条件和最优性判决准则。根据文献[15],利用最优性判决准则可以在较小的计算开销下,求得部分最优解。为此,先介绍二进制二次规划全局最优条件。

2.1二进制二次规划全局最优性条件

考虑如下一般二进制二次规划优化问题:

(6)

式中，x=[x1,x2,…,xn]T；Q为n×n维的对称矩阵；c∈Rn。

可以证明,x为问题(6)的全局最优解的最优性必要条件为[15-16]:

XQXe+Xc≤diag(Q)e

式中，X=diag(x)=diag(x1,x2,…,xn),e=[1,1, …,1]T,diag(Q)为n×n维的对角矩阵,对角线元素为qii。上式的分量形式为

(7)

式中，ei=[0,…,0,1,0,…,0]T,第i个元素为1,其他元素都为0。

2.2最优性判决条件

本节推导最优性判决准则。考虑如下的二进制二次规划优化问题,即

(8)

它与式(6)的最优问题完全等价,因此直接利用式(6)的最优性条件,可以得到式(8)的最优性条件为

其分量形式为

(9)

(10)

(11)

因此,可得到如下判决准则[16]:

(12)

算法的具体实现,可以采用多次迭代的方法。不失一般性,考虑第1次迭代的情况,按先后顺序逐一判断第1根到第NT根发送天线的信息码。若ri不满足判决准则(12),则跳过第i根发送天线,继续判断第i+1根发送天线,直到遍历所有NT根发送天线为止。此时可以得到部分最优解,然后将其作为已知条件对问题(8)进行迭代反馈。以上迭代过程循环进行,直到无法检测出新的信息码为止。

3基于二进制二次规划的GSSK检测算法

为了便于算法描述,令nd表示通过最优判决准则检测出的+1的个数,nu表示通过最优判决准则没有检测出来的个数。

算法描述如下:

第2步:利用第1步求得的部分全局最优解来确定式(5)的解,即发送信号矢量,分以下3种情况进行讨论。

情况 1利用最优性判决准则判决出NT根发送天线的信息。

(1) 若nd>nt,则将已经检测出的|ri-Si|值最小的nd-nt个+1改判为-1。若该向量包含在M中,则判定为发送信号矢量;否则进行ML检测确定发送信号矢量。

(2) 若nd=nt,如果该向量包含在M中,则判定为发送信号矢量;否则进行ML检测确定发送信号矢量。

(3) 若nd

情况 2利用最优性判决准则判决出部分发送天线的信息。

(1) 若nd>nt,则将已经检测出的|ri-Si|值最小的nd-nt个+1改判为-1,其他NT-nd个元素判为-1。若该向量包含在M中,则判定为发送信号矢量;否则进行ML检测确定发送信号矢量。

(2) 若nd=nt,将没有检测出来的元素均判为-1。如果该向量包含在M中,则判定为发送信号矢量;否则进行ML检测确定发送信号矢量。

(3) 若nd

①如果nu+nd≥nt,将已经判决出的+1、-1信息作为部分最优解,将集合M中包含此部分最优解的向量构成一个新的集合,然后在新集合中进行小规模ML检测判断发送信号矢量。

例:设式(5)的部分全局最优解为x=[+1,-1,*,*,*]T,其中*表示没有判决出来。此时新的可能的发送矢量集合为{(+1,-1,+1,-1,-1), (+1,-1,-1,+1,-1), (+1,-1,-1,-1,+1)},在这一集合中进行小规模ML检测判断发送信号矢量。

②如果nu+nd

情况 3利用最优性判决准则没有判决出任何发送天线的信息。

此时采用ML检测确定发送信号矢量。

第3步根据第2步求得的发送信号矢量,确定激活天线序号,反映射后得到发送二进制比特流。

由于本算法是基于二进制二次规划(binaryquadraticprogramming,BQP)的检测算法,因此下文将该算法称为BQP算法。

4仿真结果及分析

为了验证BQP算法的有效性,本节将该算法与ML算法、OMP算法、CSR算法进行了比较,并分析了算法的复杂度。

4.1仿真结果

为了从误码率角度更直观地体现BQP算法的有效性,在NT=16,nt=4,NR=16(以下简写为16-16-4)和NT=16,nt=8,NR=16(以下简写为16-16-8)两种情况下,将BQP算法与ML算法、OMP算法、CSR算法进行比较,仿真曲线如图2所示。图中,横坐标为信噪比(signal-to-noise ratio, SNR),纵坐标为误码率(bit error rate, BER)。仿真时,每帧发送长度为100 000。

图2　BQP算法与ML、OMP、CSR算法误码率性能的比较

从图2给出的仿真曲线可看出,在相同SNR下,BQP算法比OMP算法和CSR算法的误码率低,与ML算法的性能基本相当。

4.2复杂度分析

以下给出几种GSSK检测算法的复杂度分析。

(1) ML检测算法

(2)OMP检测算法

根据文献[13]中的NCS检测算法和文献[17]中的信号恢复的OMP算法,首先应该对信道增益矩阵H的每一列进行归一化处理,然后采用OMP算法进行稀疏重构,算法的复杂度主要取决于文献[17]中的步骤2,大约为O(NTNRnt)。

(3)CSR检测算法

根据文献[14]中的CSR检测算法,即

(13)

(4) 本文提出的BQP算法

图3　BQP算法第2步实数乘法次数占ML算法的百分比

从图3中可看出,在低信噪比时,算法第2步的实数乘法次数占ML算法的比例较低。随着信噪比的增加,该比例会随之增加,主要是由于满足最优判决准则的二进制信息码的概率随信噪比的增加而降低(判决概率见定理)。当信噪比达到一定程度时,算法第2步的运算量维持在恒定值。从图3中可看出,在信噪比为10 dB时,16-16-4、16-16-8两种情况下算法第2步实数乘法次数占ML算法的比例分别为62%和51%。假设信道增益矩阵H在整个传输过程中保持不变,则无需计算R。因此BQP算法的运算量等于计算r的实数乘法次数加上算法第2步的实数乘法次数。在上述两种情况下,BQP算法的实数乘法次数分别占ML算法的64%和51%。表2给出了信噪比为10dB时两种情况下BQP算法和ML算法运算量的比较。

表2　BQP和ML算法复杂度的比较

表3给出了BQP算法与OMP算法、CSR算法、ML算法复杂度的比较。其中BQP算法的复杂度中的p为表2中给出的百分比。当p<1时,BQP算法的复杂度低于ML算法,高于CSR算法、OMP算法。当p>1时,BQP算法的复杂度高于ML算法。

表3　BQP与OMP、CSR、ML算法复杂度的比较

综上所述,BQP算法的复杂度取决于最优判决和部分ML检测。当最优判决完全失败时,BQP算法做了无用功,后续的ML检测规模没有变小,总的运算量高于ML算法(多了计算r所需的实数乘法次数)。因此,BQP算法的有效性很大程度上依赖于最优判决的结果。如果判决结果越好,后续的ML检测规模就越小,算法总的复杂度就越小。

下面分析这一检测概率。

因为ri>Si和ri<-Si是互斥事件,所以满足最优判决准则的概率可表示为

(14)

由式(4)得

(15)

(16)

式中，ui=[Ri1,Ri2,…,RiNT]T∈RNT,下面给出GSSK系统最优判决准则的检测概率。

定理 1对于GSSK系统的检测问题,满足判决准则的二进制变量的概率为

(17)

式中,Nc表示发送信号矢量集合M的大小。

证毕

式(17)给出了接收端对发送矢量每一元素的检测概率。当系统的噪声方差越大,即信噪比越小时,通过最优判决准则判决检测的概率就越大,BQP算法第2步需要进行部分ML检测需要的实数乘法次数就越低,此时BQP算法的复杂度低于ML算法。随着系统信噪比的增加,通过最优判决准则判决检测的概率降低,BQP算法第2步进行部分ML检测需要的实数乘法次数就越多,此时BQP算法的复杂度会增加。当最优判决完全失败时,BQP算法复杂度高于ML算法。

5结论

目前,大天线技术和绿色通信技术受到业界的广泛兴趣,而GSSK技术作为这两个技术融合的优选方案,本文的算法不仅有较好的实际应用意义,而且也代表了另一种思路,对相关的信号检测算法也有参考意义。

参考文献：

[1] Mesleh R Y, Haas H, Sinanovic S, et al. Spatial modulation[J].IEEETrans.onVehicularTechnology,2008,57(4):2228-2241.

[2] Di Renzo M,Haas H,Ghrayeb A,et al.Spatial modulation for generalized MIMO:challenges,opportunities,and implementation[J].ProceedingsoftheIEEE,2014,102(1):56-103.

[3] Rajashekar R, Hari K V S, Hanzo L. Reduced-complexity ML detection and capacity-optimized training for spatial modulation systems[J].IEEETrans.onCommunications, 2014, 62(1): 112-125.

[4] Liu W L, Wang N, Jin M L, et al. Denoising detection for the generalized spatial modulation system using sparse property[J].IEEECommunicationsLetters, 2014, 18(1): 22-25.

[5] Xiao Y, Yang Z F, Dan L L, et al. Low-complexity signal detection for generalized spatial modulation[J].IEEECommunicationsLetters, 2014, 18(3): 403-406.

[6] Jeganathan J, Ghrayeb A, Szczecinski L, et al. Space shift keying modulation for MIMO channels[J].IEEETrans.onWirelessCommunications, 2009, 8(7): 3692-3703.

[7] Zhou E, Hao L. Optimal power allocation for space shift keying modulation in a distributed antenna system[J].IEEECommunicationsLetters, 2013, 17(9)：1734-1737.

[8] Chang R Y, Lin S J, Chung W H. New space shift keying modulation with hamming code-aided constellation design[J].IEEEWirelessCommunicationsLetters, 2012, 1(1): 2-5.

[9] Di Renzo M, Haas H. Improving the performance of space shift keying (SSK) modulation via opportunistic power allocation[J].IEEECommunicationsLetters, 2010, 14(6): 500-502.

[10] Jeganathan J, Ghrayeb A, Szczecinski L. Generalized space shift keying modulation for MIMO channels[C]∥Proc.oftheIEEE19thInternationalSymposiumonPersonal,IndoorandMobileRadioCommunications,2008: 1-5.

[11] Ntontin K, Di Renzo M, Perez-Neira A, et al. Adaptive generalized space shift keying[J].EURASIPJournalonWirelessCommunicationsandNetworking, 2013(1): 1-15.

[12]Larsson E G. MIMO detection methods: how they work[J].IEEESignalProcessingMagazine, 2009, 26(3): 91-95.

[13]Yu C M, Hsieh S H, Liang H W, et al. Compressed sensing detector design for space shift keying in MIMO systems[J].IEEECommunicationsLetters, 2012, 16(10): 1556-1559.

[14]Chang R Y, Chung W H, Lin S J. Detection of space shift keying signaling in large MIMO systems[C]∥Proc.oftheWirelessCommunicationsandMobileComputingConference(IWCMC), 2012: 1185-1190.

[15]Beck A, Teboulle M. Global optimality conditions for quadratic optimization problems with binary constraints[J].SIAMJournalonOptimization, 2000, 11(1): 179-188.

[16]Liu W L, Pei Y Y, Jin M L. Partial optimal MIMO detection for BPSK communication system[J].JournalofSignalProcessing,2013,29(10):1315-1322.(刘文龙,裴莹莹, 金明录. BPSK通信系统的部分最优MIMO检测算法[J].信号处理, 2013, 29(10):1315-1322.)

[17] Tropp J A, Gilbert A C. Signal recovery from random measurements via orthogonal matching pursuit[J].IEEETrans.onInformationTheory, 2007, 53(12): 4655-4666.

[18] Shang Y, Fromherz M P J, Crawford L. A new constraint test-case generator and the importance of hybrid optimizers[J].EuropeanJournalofOperationalResearch, 2006, 173(2): 419-443.

[19] Guo L M, Luo D Y. A TOA/AOA hybrid location method in nonline-of-sight environment[J].JournalofCircuitandSystems, 2010, 15(5): 26-30.(郭丽梅, 罗大庸. 非视距环境中TOA/AOA混合定位方法[J].电路与系统学报, 2010, 15(5): 26-30.)

张新贺(1980-),男,讲师,博士研究生,主要研究方向为空间调制系统检测、压缩感知理论的应用及稀疏信号的重构。

E-mail:cdaszxh@sina.com

吴金隆(1989-),男,硕士研究生,主要研究方向为MIMO系统信号检测、空间调制系统信号检测。

E-mail: wujinlong@mail.dlut.edu.cn

门宏志(1988-),女,博士研究生,主要研究方向为空间调制系统检测、压缩感知理论的应用及稀疏信号的重构。

E-mail: menruiye@sina.com

金明录(1958-),男,教授,博士研究生导师,博士,主要研究方向为信号与通信系统基础理论和技术。

E-mail: mljin@dlut.edu.cn

网络优先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20150202.1727.004.html

Detection algorithm for GSSK system based on global optimality

conditions for binary quadratic programming

ZHANG Xin-he1,2, WU Jin-long1, MEN Hong-zhi1, JIN Ming-lu1

(1.SchoolofInformationandCommunicationEngineering,DalianUniversityofTechnology,

Dalian116024,China; 2.SchoolofElectronicandInformationEngineering,

UniversityofScienceandTechnologyLiaoning,Anshan114051,China)

Abstract:Generalized space shift keying (GSSK), a preferred scheme in the combination of the large-antenna technology and the green communication technology, has received a wide range of interests. The main features of GSSK are that only a few antennas are activated at any time instant and antenna indices are exploited to convey information. The computational complexity of the maximum likelihood (ML) detector is extremely high due to the large transmit-antenna which has been the limitation in practical application. Thus, simplified suboptimal detection algorithms have been widely studied. A novel GSSK detection algorithm based on global optimality conditions for binary quadratic programming is proposed. The proposed algorithm uses the optimal decision criterion to judge the transmit information. Subsequently the algorithm can determine the combination of transmit antennas based on the previous transmit information. Thus, the transmit binary bit stream is estimated. The simulation results show that the performance of the proposed algorithm, which exhibits lower computational complexity, is better than orthogonal matching pursuit (OMP) and convex superset relaxation (CSR) suboptimal detection algorithms. The proposed method achieves a better tradeoff between the performance and complexity.

Keywords:generalized space shift keying (GSSK); binary quadratic programming; global optimality conditions; detection algorithm

作者简介：

中图分类号：TN 914

文献标志码：A

DOI:10.3969/j.issn.1001-506X.2015.07.30

基金项目：国家自然科学基金(61301130)资助课题

收稿日期：2014-09-18；修回日期：2014-12-16；网络优先出版日期：2015-02-02。