求解多输入多输出检测新算法——遗传粒子群优化

黑永强 李晓辉 易克初 郁光辉

(1.西安电子科技大学ISN国家重点实验室，陕西 西安 710071； 2.深圳市中兴通讯技术有限公司，广东 深圳 518057)

1. 引 言

对于多输入多输出(MIMO)系统而言，最大似然译码(ML)是最佳的接收算法，但是其计算量随发射天线数呈指数增长，这就大大限制了ML在实际系统中的应用，因而寻找次优的MIMO检测算法一直是业内探索的目标。为了解决这一问题，学者提出了许多次优的线性和非线性的算法[1-4]，然而这些算法难以取得较好的性能或者计算复杂度过高。目前基于凸优化MIMO检测算法引起了广泛关注[5-7]，其主要原因是该方法能够以较低的复杂度获取较好的性能，然而如何保证目标函数的凸性以及如何进行合理的松弛则是该算法的一大难题。

近年来许多学者开始尝试用进化算法求解检测问题，这主要是因为进化算法具有简单方便，运行速度快，实现简洁，调整的参数少等优势。目前，这一方面的研究包括将离散粒子群算法、遗传算法、克隆选择算法等用于多用户检测问题[8-10]，但是上述研究中进化算法仅适用于用户配置单天线的状况，而如何采用进化算法求解多天线MIMO系统检测问题则亟待进一步研究。上述研究中仅注重将进化算法应用于检测问题求解，而并未深入分析进化机制的优势和缺陷，因而，求解检测问题的性能将受限，如何设计出新的更加高效的进化算法，能够进一步提高求解问题的效率，这正是研究的出发点。

首先将粒子群优化算法(PSO)和遗传算法(GA)应用于求解MIMO系统检测问题。在此基础之上，提出新的遗传粒子群优化(GPSO)进化算法以克服PSO算法和GA算法求解MIMO检测问题的不足。新算法的求解思路是：将以MMSE估计的检测符号集作为初始种群，并根据粒子的适应度值将粒子分为精英粒子，次优粒子以及糟糕粒子三部分，然后对于精英粒子和次优粒子分别实施极值扰动和PSO进化策略，而对糟糕粒子实施淘汰后并重新产生从而改善算法的进化机制。仿真结果表明所提算法的有效性。

2. 系统模型

假定一个MIMO系统有Nt根发射天线和Nr根接收天线，MIMO系统相关信道模型如图1所示。

图1 MIMO系统相关信道模型

(1)

H=KRHCKT

(2)

式中:HC为不相关的复高斯变量信道矩阵；KT和KR分别满足

(3)

在此相关信道模型假设下，接收到的信号复向量为

r=Hx+n

(4)

对于MIMO系统，最优的最大似然检测(ML)的输出向量为

(5)

式中，Ω为星座符号集。但ML算法由于需要遍历整个发射符号集空间，其复杂度O(ΩNt)为星座大小和天线数目的指数函数，因此，在实际中一般难以接受。

3. MIMO检测问题求解

采用进化算法求解MIMO系统检测，首先需要解决以下两个问题：

1) 所优化的目标函数是什么？

2) 如何定义进化算法中的个体(优化变量)？

(6)

则有下式成立

rp=Hpxp+np

(7)

3.1 PSO求解MIMO检测问题

粒子群优化算法(PSO)[12]，由Eberhart和Kennedy于1995年提出，是一种模拟自然界鸟类、鱼群等寻找食物过程而提出的随机搜索算法。粒子群算法是一种基于群体的优化算法，其中每个粒子代表所研究问题的一个可行解,它具有位置和速度两个基本特征。每个粒子在搜索空间中以一定的速度飞行，并根据对个体和集体飞行经验的综合分析来动态调整其速度，然后更新个体当前的位置，每个粒子根据下面两个公式来更新自己的速度与位置

vi(τ+1)=wvi(τ)+c1r1(pbesti(τ)-xi(τ))+

c2r2(gbest(τ)-xi(τ))

xi(τ+1)=xi(τ)+vi(τ+1)

(8)

式中：pbesti(τ)和gbest(τ)分别表示个体极值和全局极值；c1和c2是加速度常数；r1和r2是服从[0,1]分布的随机数；vi(τ)受限于[-VmaxVmax]；w是惯性常量。

图2 粒子定义示意图

图2所示粒子采用浮点编码的优势在于能够有效扩展算法的求解范围，可以推广到高阶调制。此时，各浮点编码元素可映射为最近的星座点。

适应度函数定义：PSO算法通过适应度函数来评估粒子的优劣，根据粒子的定义，适应度函数可以定义为:

(9)

适应度函数值越小,则表明该粒子与最优检测向量之间的欧式距离越短，整个寻优过程中的全局最优粒子即代表PSO算法所得出的检测向量。根据粒子和适应度函数的定义并根据式(8)中的进化过程，可以实现PSO算法求解MIMO系统检测。

3.2 GA算法求解MIMO检测问题

遗传算法(GA)是一种基于生物遗传和进化机制的自适应概率优化技术[13]。它通过模拟自然选择和遗传中发生的选择、交叉和变异等现象，从一个初始种群出发，经过随机选择、交叉和变异操作，产生一群更适应环境的个体，使群体进化到搜索空间中越来越好的区域。经过这样一代又一代地不断繁衍进化，最后得到一群最适合环境的个体，从而求得问题的最优解。

类似PSO算法检测过程，采用GA算法求解MIMO系统检测问题时，GA中的个体与PSO中的粒子相对应，而适应度函数则采用相同的定义，所不同的是PSO算法通过更新粒子的位置和速度来寻优，而GA算法的寻优则通过遗传操作完成。GA求解MIMO检测的基本过程如下：首先随机初始产生Q个体，其中每一个体代表发送数据的一个估计值，然后计算个体的适应度值，并根据适应度值的优劣选择个体用于杂交。在每一代的进化过程中，用于遗传操作，即交叉、变异，生成下一代个体，也即子代。经过若干代进化之后，算法收敛于最好的个体，该个体作为GA算法所求出的最优检测解向量。GA算法求解MIMO检测过程的关键步骤如图3所示。

图3 GA算法求解MIMO检测关键步骤流程

3.3 GPSO算法求解MIMO检测问题

PSO算法通过进化过程经验记忆以及粒子之间的信息共享发挥作用，因而PSO算法具有很强的全局搜索能力，但由于所有的粒子都参与每一代进化未免会导致进化效率的降低。相反，GA在每一代中通过不断选择优秀的个体而丢弃质量较差的个体来完成进化，故GA算法具有很强的局部搜索能力，但GA算法中个体之间缺乏信息交互，因此，其全局寻优能力较弱以及收敛速度较慢。利用GA和PSO算法的各自优势，给出一种融合GA和PSO进化机制的新遗传粒子群进算法，并将其应用于求解MIMO系统检测，下文将给出算法的详细求解过程。

根据中债资信地方政府及城投行业研究团队对2016年政府类投融资平台-江苏篇调研结果知，截止2015年末，江苏省政府债务率68.5%，债务风险总体可控，江苏省内融资平台直接间接融资渠道较为通畅，2015年融资成本较此前明显降低，综合融资成本6%-8%之间。2017年后江苏省融资平台逐渐出现融资难、成本高。

初始化：初始化种群选取合适与否将直接关系到进化算法的迭代次数与收敛速度，如果采用常规的随机产生初始种群，则算法求解检测的计算效率很难保证。为了解决这一问题,采用接收信号MMSE估计值rMMSE作为初始种群，从而加快新算法寻找最优解的速率。

rMMSE=Gp·rp

(10)

粒子评估：在进化过程中，粒子的质量难免会有优劣之分。借鉴GA算法个体评估原理，将对每一代进化的粒子根据适应度值进行排序，然后将这些粒子进行划分为三部分：精英粒子、次优粒子、以及糟糕粒子，并对这些粒子分别采取各自的寻优策略。

xg+1(τ+1)=xg(τ)+(1-rd[1-

(τ/T)])vg+1(τ)

(11)

从式(11)中可看出，在搜索初期，对于较小的rd值时，精英粒子相对扰动空间较大；而在搜索后期，τ接近于T时，精英粒子在较小的空间内扰动。式(11)中自适应的调节精英粒子的变化范围能够保证停滞的精英粒子可以重新激活，并以更高的概率去寻找全局最优值。

为了便于分析，图4给出新算法进化机制的关键步骤。

图4 GPSO进化算法关键步骤流程

采用上述进化机制，GPSO算法求解MIMO检测问题的关键步骤如下：

step 1 设粒子群规模为Q，根据式(10)初始化粒子种群，并随机产生各粒子的速度。

step 2 根据式(9)计算粒子的适应度函数，找出个体极值和全局极值。

step 3 对于精英粒子，根据式(11)实施增强极值扰动。

step 4 对于次优粒子，根据式(8)实施改进PSO进化。

step 5 淘汰适应度值较低的粒子，并重新随机产生新的粒子以弥补空缺。

step 6 重复step3 ～step5步,直到满足性能要求或达到预先设定最大迭代次数T。

step 7 输出全局极值以及相应的检测结果。

4. 实验结果分析

采用第1部分描述的MIMO相关信道模型Nt=4,Nr=4。为了验证所提算法的有效性，仿真中同时引入了ZF算法、MMSE算法、最大似然(ML)算法。另外，PSO算法、GA算法和GPSO算法三种算法的公共参数如下：种群规模Q=80，最大迭代次数T=10。对于PSO，惯性常数w在[0.9，0.4]区间内线性递减，加速度常数c1=c2=2。对于遗传算法选取变异概率和交叉概率分别为0.05和0.8，其他参数均与PSO算法相同。而所提算法中的粒子淘汰率pt=0.5.

实验1分析比较GPSO算法和经典的检测算法以及进化算法的误码性能

图5 比较GPSO算法和经典算法误码性能曲线

图5比较了GPSO算法和经典检测算法的误码性能。由图5可知，最大似然检测算法(ML)是最优的，但是其指数复杂度也是最高的。GPSO算法相比较其他算法获得一定的信噪比增益，当种群数目由Q=50增加到Q=80，误码性能得到了明显的改善。而MMSE算法相对于ZF算法有一定的增益，这是因为MMSE算法相比ZF算法增加了接收SNR的估计。ZF算法的性能优于QR算法在于前者可以使得天线之间的干扰迫零，然而迫零矩阵引入了对噪声的放大，因此，其误码性能也较差。QR检测算法受误差传播的影响故其误码性能最差。

图6比较了所提算法以及另外两种进化算法的误码率曲线。需要指出的是图6中三种检测算法均采用MMSE估计值作为初始种群。可以看出，GPSO检测算法的性能要明显优于PSO检测算法和GA检测算法，从而体现出所提算法所采用进化机制的有效性。这也同样说明PSO和GA算法的进化机制均存在一定缺陷。另外PSO检测算法误码性能要优于GA检测算法，这是因为相比GA算法，PSO算法具有更强的全局寻优能力。另外，可以看出，随着种群数目Q的增加，三种算法的误码性能均得到一定的改善。

图6 比较GPSO算法和进化算法误码性能曲线

实验2分析迭代次数和粒子数目对GPSO算法误码性能的影响

图7 迭代次数对GPSO算法误码性能影响曲线

图7给出了迭代次数对GPSO算法误码性能影响曲线。可以看出，随着迭代次数的增加，误码性能逐步得到改善。其原因在于，在进化的过程中随着迭代次数的增加不断能够发现更优的粒子。但是随着迭代次数的进一步增加，误码率改善效果逐渐变得不明显，比如图中10次迭代相比较5次迭代所得增益没有5次迭代相比较1次迭代所得增益的效果显著。因此，在实际系统中可以根据需求来确定进化过程所需的最大迭代次数。

图8给出粒子数目对GPSO算法误码性能影响的曲线。由图可知，粒子数目越多，GPSO算法下的误码率曲线就越接近ML算法误码率曲线。这是因为更多数目的粒子参与进化，必然导致算法寻找到最优解的概率增加，因而误码性能得到改善。对比图7和图8可以发现，误码性能的改善既可以通过增加进化的迭代次数也可以通过加大粒子种群的数目来获得，因此，在实际系统中，可以根据要求合理地选取这两个参数。

图8 粒子数目对GPSO算法误码性能影响曲线

实验3所提算法计算复杂度分析与比较

由第一节可知，ML算法由于需要遍历所有可能的发射序列，其复杂度大小为Q(ΩNt)。这在发射天线数目较多或者采用较高的调制方式时，令人无法接受。相比较ML算法，ZF、MMSE算法能够显著降低算法的复杂度，大小近似为O(Nr3)，其中Nr为接收天线数目，但是ZF、MMSE算法复杂度降低是以性能损失为代价的。

对于上文所给出的三种算法，假定种群数目P，每个粒子处于D维空间及最大迭代数目为T。初始化粒子群以及计算适应度函数值大概需要的计算复杂度为O(PD)，另外对于更新全局极值，个体极值以及每个粒子其位置和速度所需要的复杂度分别可以近似为O(P),O(P)和O(PD)。因此，PSO算法每一代进化过程中其关键步骤所需的复杂度为O(PD)+O(P)+O(P)+O(PD)=O(2P+2PD).从而PSO算法的整体计算复杂度为：O(T(2P+2PD))。对于GA而言，遗传操作的三个关键算子选择、交叉、变异的时间复杂度分别为：O(P),O(PD)和O(PD)，因此，GA算法总的时间复杂度为O(T(P+3PD))。对于所提算法而言，初始化种群个体所需的计算复杂度近似为O(Nr2)，而粒子的适应度值进行排序引入的额外复杂度为O(P)，每个粒子附近的次优粒子的更新需要的复杂度为O(P)，因此，所提算法的计算复杂度为O(T(4P+PD)+Nr2)。忽略系数影响的条件下，PSO算法、GA算法以及所提算法的计算复杂度分别可以近似O(TPD),O(TPD),O(TPD+Nr2).根据选取粒子或个体的定义可知，P，D，T均随着发射空间维数Nt的增加而线性增加，则三种算法的复杂度分别近似为O(Nt3),O(Nt3),O(Nt3+Nr2).可见，相比ML算法，三种算法具有较低的复杂度；而考虑到获得相同的性能前提下所提算法所需迭代次数要少于PSO算法，因此，所提算法的计算复杂度相对于PSO算法以及GA算法基本上相差不大。

5. 结 论

提出了一种求解MIMO系统检测新算法：遗传粒子群优化算法，新算法通过有效地融合GA和PSO进化机制，从而加快了算法的求解效率。仿真结果表明：所提算法应用于MIMO系统检测十分有效，在种群规模Q=80和最大迭代次数T=10时，相比最大似然检测算法在误码率为10-2时SNR相差约为2 dB。而与基于PSO检测算法和基于GA检测算法相比，在相同的种群数目和迭代次数下，能够获得更好的误码性能。有望将所提算法进一步推广应用于多用户MIMO检测场景[14-15]，而如何进一步改善算法的进化机制则是今后研究的内容。

[1] WUBBEN D, BOHNKE R,RINAS I. Efficient algorithm for decoding layered space-time codes [J]. IEE Electronics Letter, 2001, 37(22):1348-1350.

[2] ZHANG J K, ALEKSANDAR K, MAX W. Equal-diagonal qr decomposition and its application to precoder dsign for successive cancellation detection. ieee transactions on information theory [J].2005, 51(1):154-172.

[3] 林 云，王 宇. MIMO系统中K-best球形译码算法研究[J].电波科学学报，2009, 24(1):141-147.

LIN Yun, WANG Yu. Study on K-best sphere decoding algorithm in MIMO system [J]. Chinese Journal of Radio Science, 2009, 24(1): 144-147. (in Chinese)

[4] SHEN C, ZHANG H R, LIN D. Detection algorithm improving VBLAST performance over error propagation [J].IEEE Electronics Letters, 2003, 39(6):1007-1008.

[5] SIDIROPOULOS N D, LUO Z Q. A semidefinite relaxation approach to mimo detection for high-order qam constellations [J]. IEEE Signal Processing Letters, 2006, 13(9):525-528.

[6] WEI C H, CHANG T H, MA W K. A linear fractional semidefinite relaxed ML approach to blind detection of 16-QAM orthogonal space-time block codes communications[C]//IEEE International Conference on Communications (ICC), BeiJing, 2008, 790-794.

[7] MA W K, SU C C, JALDEN J. Some results on 16-QAM MIMO detection using semidefinite relaxation[C]// IEEE International Conference on Acoustics, Speech and Signal Processing, 2008, USA, 2673-2676.

[8] BASHIR S, KHAN A A, SHAH S I. An application of ga for symbol detection in MIMO communication systems[C]//Third International Conference on Natural Computation, Hainan, China, 2007, 404-410.

[9] GAO H Y,PAN W Z. Multiuser detector based on discrete particle swarm optimization algorithm [J]. Journal of Harbin Institute of Technology, 2005, 37(9): 1303-1306.

[10] XU Yaohua, HU Yanjun. Research of ecologic system optimization algorithms for multiuser detection in CD MA communication systems [J]. Journal of Electronics and Information Technology, 2006,28(11):2111-2115.

[11] KLAUS I P, ANDERSEN J B. A Stochastic Multiple-Input-Multiple-Output Radio Channel Model for Evaluation of Space-Time Coding Algorithms[C]∥ IEEE 52nd Vehicular Technology Conference, USA, 2000, 893-897.

[12] KNENEDY J , EBERHART R. Particle swarm optimization [C]//IEEE Conference Proceedings of the International Conference on Neural Networks. Piscataway, USA,1995, 1942-1948.

[13]SAMII Y R, MICHIELSSEN E. Electromagnetic Optimization by Genetic Algorithms [M]. New York: Wiley, 1999.

[14] 芮贤义, 金荣洪, 耿军平.相关MIMO信道下空间分集系统中多用户分集性能[J]. 电波科学学报, 2008, 23(5):937-941.

RUI Xianyi, JIN Ronghong, GENG Junping. Performance of multiuser diversity in a spatial diversity system under MIMO correlated channels[J]. Chinese Journal of Radio Science,2008,23(5):937-941. (in Chinese)

[15] 曾二林, 朱世华, 廖学文. 基于自适应空分复用的分组多用户分集方案[J]. 电波科学学报, 2007, 22(3):424-429.

CENG Erlin, ZHU Shihua, LIAO Xuewen. A grouped multi-user diversity scheme based on adaptive space division multiplexing [J]. Chinese Journal of Radio Science, 2007, 22(3): 424-429. (in Chinese)