基于改进入侵杂草算法的多用户检测

国 强，张金程，周 凯

(哈尔滨工程大学 信息与通信工程学院，黑龙江 哈尔滨 150001)

0 引言

在DS-CDMA系统[1]中，由于扩频序列的非完全正交性、各用户的随机接入以及实际信道的异步传输等原因，使得用户之间产生多址干扰。当用户数量达到一定程度，多址干扰成为主要的系统干扰，采用传统检测器(Conventional Detector，CD)会使系统容量降低，通信质量下降，严重影响系统性能。多用户检测技术[2-3]是克服多址干扰的关键技术之一。最优多用户检测器(Optimal Multi-user Detection，OMD)[4]虽然具有良好的检测性能，但是其计算复杂度随着用户数的增加成指数增长，当用户数量较多时计算复杂度极高，工程上难以实现。DS-CDMA系统的多用户检测问题可以看作是一个组合优化问题，通过智能算法来求解[5-8]。

入侵杂草算法(Invasive Weed Optimization，IWO)[9]是Mehrabian和Lucas在2006年提出的一种仿生优化算法，模拟自然环境中杂草的生长扩散过程，具有收敛速度快、鲁棒性好、结构简单以及易于实现等特点[10]。IWO算法在多目标优化[11]、阵列天线稀布[10，12]和能源负荷动态调度[13]等领域得到广泛应用。这些应用大多属于连续空间或者整数空间优化问题，而利用IWO算法求解二进制离散空间问题的研究相对较少。

本文主要研究DS-CDMA系统的多用户检测，为解决最优多用户检测器复杂度过高问题，引入入侵杂草优化算法。并从抗多址干扰能力、抗远近效应能力和收敛性等方面进行仿真分析。

1 系统模型

1.1 同步DS-CDMA系统模型

假设一个具有K个用户的DS-CDMA系统，所有用户采用二进制相移键控调制(Binary Phase Shift Keying，BPSK)，系统的信道噪声为加性高斯白噪声，在不考虑信道衰落和多径效应的情况下，假设捕获跟踪条件理想，即忽略载波调制解调，则通信系统接收端的信号模型为：

(1)

式中，SF表示扩频序列长度；Ak表示用户k的信号幅度；bk表示用户k发送的比特信息；Tb表示码元间隔；T表示传输信息的周期间隔；τk表示用户k的延时；n(t)表示均值为0，能量为σ2的加性高斯白噪声；sk(t)表示用户k的扩频序列，其波形是持续时间为Tb的矩形波，并且具有归一化能量，即

(2)

若所有用户的延时均为0，式(1)变为同步DS-CDMA系统的信号模型，简化扩频序列，则可表示为：

(3)

1.2 传统检测器

传统检测器，利用用户的扩频序列对接收到的信号进行相关接收。相关处理后的信号表示为：

(4)

式中，nk为信道噪声经过匹配滤波器k后的剩余噪声；MAIk为干扰用户对期望用户产生的多址干扰；ρjk为用户j和用户k扩频序列的归一化互相关系数。

(5)

对相关处理后的信息进行硬判决，得到：

bk=sign(yk) 。

(6)

1.3 最优多用户检测器

最优多用户检测算法的基本思想是充分利用所有用户信息，对用户信号进行联合检测，相当于用户比特信息先验概率相等条件下的最大似然序列检测，性能能够接近单用户系统。检测得到的结果要使式(7)的似然函数最大化。

(7)

经过推导，上式可等效为使式(8)最大化。

(8)

式中，H=ARA，A为以用户幅度为元素的对角阵。

OMD检测器的运算复杂度为O(2k)，与用户数量成指数关系。当用户数较多时，以现有的硬件水平难以实现。

2 基本的入侵杂草优化算法

入侵杂草优化算法是模拟自然界中杂草的繁殖、扩散和消亡的过程而得到的一种寻优算法。其中每一个杂草代表要求解问题的一个可行解，子代杂草为杂草通过空间扩散得到的新解。在寻优过程中，杂草根据自身适应度值的大小产生一定数量的种子，种子以正态分布的步长分布在父代杂草的周围区域，成长为代杂草。在每一级迭代中，通过比较所有父代杂草和子代杂草的适应度值，保留适应度好的杂草进行下一代繁殖扩散。其过程主要包括3个步骤[10]：

① 种子繁殖。杂草xi根据其适应能力产生不同数量的种子，适应度值好的杂草产生较多的种子，适应度值差的杂草产生较少的种子。对于求解最大化问题，生成种子的数量根据式(9)确定：

(9)

式中，f(xi)表示杂草xi的适应度值；fmax和fmin表示当前迭代中所有种子的最大适应值和最小适应值；Smax和Smin表示一个种子能够产生的最大种子数量和最小种子数量。

② 空间扩散。种子按照均值为0、标准差为σ正态分布步长生长成杂草，分布在父代杂草的周围空间。每一代标准差σiter的大小按照式(10)确定：

(10)

式中，iter表示当前的迭代次数；itermax表示最大的迭代次数；σini和σfin表示标准差的初始值和最终值(一般初始值大于最终值)；n是非线性调和因子，通常情况下n=3[14]。

杂草i产生的第s个种子的位置可以表示为：

(11)

③竞争排除。在种子的繁殖扩散过程中，当杂草的数量达到最大种群规模Pmax后，将父代杂草和子代杂草按适应度值大小进行排序，保留适应值较好的Pmax个杂草，淘汰其余的杂草。

3 基于改进IWO算法的多用户检测

3.1 改进的IWO算法

3.1.1 映射函数

在标准的IWO算法中，种子的扩散空间是围绕在父代杂草周围的高斯分布。在调制方式为BPSK的DS-CDMA系统中所传输的信息为{-1，+1}，所以标准IWO算法中的扩散方式不能直接应用于二进制杂草个体的扩散，需要通过恰当的方式进行映射，把扩散值转换成杂草某一维度的变异概率。

(12)

式中，sigmokd(x)=1/(1+e-1)。

由映射产生的变异概率，得到该维度的变异标志flag，表示为：

(13)

式中，rand为(0，1)之间的随机数。

则其子代杂草第k维的值为：

(14)

3.1.2 改进的标准差变化曲线

在标准的IWO算法中，正态分布的标准差按式(10)计算，从图1可以看出随着进化代数的增加，标准变化曲线下降缓慢。若最大迭代次数为30代，则当迭代次数达到25时，标准差才能接近最小值。在二进制多用户检测系统的进化前期，较大的标准差可以使子代杂草分布在距离父代杂草较远的位置，即子代杂草与父代杂草的汉明距离比较大，有利于全局搜索。但是在进化中后期，种群分布在最优解的附近，较大的变异概率不利于提高寻优精度。为此设置标准差的变化曲线如式(15)所示，图1中改进变化曲线为其示意图。可以看出，改进的进化曲线在进化前期可以使算法在整个空间进行全局搜索，之后迅速在较小区域进行局部搜索。

σiter=tanh(-iter+4)+2.5。

(15)

图1 正态分布标准差变化曲线

3.2 基于改进IWO算法的多用户检测器

改进IWO算法的多用户检测器步骤：

① 参数设置。设置种群的初始规模和最大规模；种子繁殖的最大数量和最小数量等参数。

② 种群初始化。为了保证初始种群的多样性，采用均匀分布方式产生初始种群，使初始杂草随机分布在整个搜索空间。

③ 根据式(8)计算每个种子的适应度值，按照式(9)计算每一个杂草产生种子的数量，完成种子繁殖。

④ 通过杂草扩散的正态分布标准差，计算每一维度的扩散值，通过式(12)得到变异概率，产生变异标志，然后进行维度变异、完成空间扩散。

⑤ 计算子代杂草的适应度值，和父代杂草一起进行排序，进行竞争排除，淘汰较差个体。

⑥ 判断是否到达结束条件。若满足结束条件，则输出用户的估计值；否则继续执行步骤③。

4 仿真分析

假设一个用户数为10的同步DS-CDMA系统，采用BPSK调制，扩频序列采用长度为31的Gold码，最大归一化互相关系数为9/31。为了方便讨论，假定系统具有严格的功率控制，扩频序列和用户幅度估计准确。

为了验证基于改进IWO(Improved IWO，IIWO)算法多用户检测器的有效性，使用CD检测器、解相关检测器(De-correlation Detector，DEC)、OMD检测器、基于基本遗传算法(Genetic Algorithm，GA)、基本PSO算法和基本IWO算法的多用户检测器进行对比。GA的种群规模设置为10，交叉概率设置为0.8，变异概率设置为0.05；PSO多用户检测器的参数设置参考文献[15]，种群规模设置为10，加速度因子分别设置为2，最大加速度设置为6；IWO算法的最大种群规模设置为5，杂草产生的最大种子数量为4，最小数量为0，初始标准差为4，最终标准差为1.5，非线性调和因子为3；IIWO算法的最大种群规模设置为5，杂草产生的最大种子数量为4，最小数量为0，标准差按式(15)变化。智能算法的最大迭代次数设置为30。

仿真实验1：检测器在不同信噪比下的误码率如图2所示。从图中可以看出，在上述参数设置下，IWO和IIWO检测器接近OMD检测器的性能，而信噪比大于8 dB时，PSO和GA检测器在30次迭代内未寻找到最优解。

图2 检测性能随信噪比变化情况

仿真实验2：为了验证算法的抗远近效应能力，假设除用户1外其他用户的信息幅度为1，信噪比为8 dB，用户1与其他用户的幅度比A1/Ai从0.1～10变化。所有用户的平均误码率如图3所示。从图中可以看出，IIWO检测器的误码率比DEC检测器约低1.5 dB，具有良好的抗远近效应能力。

仿真实验3：为了验证算法的收敛特性，设置信噪比为8 dB，最大进化代数为30。不同检测器的平均误码率随进化代数的变化情况如图4所示。由图4中可以看出，IIWO检测器的收敛性能明显优于PSO检测器、IWO检测器和GA检测器，在进化代数为10时，即可找到最优解。

仿真实验4：为验证检测器性能随用户数量的变化情况，设信噪比为8 dB，最大进化代数为30。所有用户的平均误码率变化情况如图5所示。可以看出，IIWO算法的误码率最低。

图3 不同检测器抗远近效应能力对比

图4 不同检测器收敛性能对比

图5 检测性能随用户数量变化情况

5 结束语

为了将入侵杂草优化算法应用于多用户检测，本文在算法中引入映射函数，针对基本正态分布标准差收敛速度慢的问题，提出改进的标准差变化曲线。仿真结果表明，该方法在抗多址干扰、抗远近效应能力方面接近最优多用户检测；收敛速度优于基本GA，PSO，IWO算法；当用户数量变化时，检测性能优于CD、DEC和其他3种基于智能算法的检测器；而且计算复杂度要明显低于OMD检测器。下一步将研究IWO算法与其他智能算法相结合的多用户检测器，进一步提高检测器的收敛速度和鲁棒性。