一种新的改进进化规划多用户检测方法

第２９卷第ｌ２期　２００６年１２月　合肥工业大学学报（自然科学版）　ＪＯＵＲＮＡＬ　ＯＦ　ＨＥＦＥＩ　ＵＮＩＶＥＲＳＩＴＹ　ＯＦ　ＴＥＣＨＮＯＬＯＧＹ　Ｖｏ１．２９　Ｎｏ．１２　Ｄｅｃ．２００６　＿种新的改进进化规划多用户检测方法　许良凤　（合肥工业大学计算机与信息学院，安徽合肥２３０００９）　摘要：针对码分多址接／ｋ（ＣＤＭＡ）＇系统中最优多用户检测的指数计算复杂度问题，结合ＣＤＭＡ通信的实际　特点，提出了一种基于改进的进化规划多用户检测方法，该方法是通过增加种群的多样性来改善进化规划易　于出现早熟收敛的缺点。实验表明，该多用户检测方法在抗多址干扰的能力和抗远近效应的能力都优于进化　规划的多用户检测方法。　关键词：码分多址；多用户检测；进化规划；遗传算法　中图分类号：ＴＮ９１４．５３　文献标识码：Ａ　文章编号：１００３—５０６０（２００６）１２—１５０８　０３　Ａ　ｎｅｗ　ｍｏｄｉｆｉｅｄ　ｅｖｏｌｕｔｉｏｎ　ｓｔｒａｔｅｇｙ　ｏｆ　ｍｕｌｔｉ—ｕｓｅｒ　ｄｅｔｅｃｔｉｏｎ　ａｌｇｏｒｉｔｈｍｓ　ＸＵ　Ｌｉａｎｇ－ｆｅｎｇ　（Ｓｃｈｏｏｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　ａｎｄ　Ｉｎｆｏｒｍａｔｉｏｎ，ｔｔｅｆｅｉ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ，Ｈｅｆｅｉ　２３０００９，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｉｎ　ｖｉｅｗ　ｏｆ　ｔｈｅ　ｅｘｐｏｎｅｎｔｉａｌ　ｃｏｍｐｕｔａｔｉｏｎ　ｃｏｍｐｌｅｘｉｔｙ　ｏｆ　ｔｈｅ　ｏｐｔｉｍａｌ　ｍｕｌｔｉ—ｕｓｅｒ　ｄｅｔｅｃｔｉｏｎ　ｉｎ　Ｃｏｄｅ　Ｄｉｖｉｓｉｏｎ　Ｍｕｌｔｉｐｌｅ　Ａｃｃｅｓｓ（ＣＤＭＡ）ｓｙｓｔｅｍｓ　ａｎｄ　ｔｈｅ　ｐｒａｃｔｉｃａｌ　ｃｈａｒａｃｔｅｒｉｓｔｉｃ　ｏｆ　ＣＤＭＡ　ｃｏｍｍｕｎｉｃａ—　ｔｉｏｎ，ａ　ｓｕｂ－ｏｐｔｉｍａｌ　ｍｕｌｔｉ—ｕｓｅｒ　ｄｅｔｅｃｔｏｒ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｍｏｄｉｆｉｅｄ　ｅｖｏｌｕｔｉｏｎ　ｓｔｒａｔｅｇｙ　ｉｓ　ｐｒｏｐｏｓｅｄ．Ｔｈｅ　ｐｒｅ—　ｍａｔｕｒｅ　ｃｏｎｖｅｒｇｅｎｃｅ　ｏｆ　ｔｈｅ　ｅｖｏｌｕｔｉｏｎ　ｓｔｒａｔｅｇｙ　ｉｓ　ａｖｏｉｄｅｄ　ｂｙ　ｍｅａｎｓ　ｏｆ　ｉｎｃｒｅａｓｉｎｇ　ｔｈｅ　ｒａｃｅ　ｉｎｄｉｖｉｄｕａ１．　Ｔｈｅ　ｓｉｍｕｌａｔｉｏｎ　ｒｅｓｕｌｔｓ　ｈａｖｅ　ｓｈｏｗｎ　ｔｈａｔ　ｉｎ　ｔｈｅ　ａｓｐｅｃｔｓ　ｏｆ　ｍｕｌｔｉｐｌｅ－ａｃｃｅｓｓ　ｉｎｔｅｒｆｅｒｅｎｃｅ　ｃａｎｃｅｌｌａｔｉｏｎ　ａｎｄ　ｎｇ　ｔｈｅ　ｅｖｏｌｕｔｉｏｎ　ｎｅａｒ－ｆａｒ　ｒｅｓｉｓｔａｎｃｅ，ｔｈｅ　ｄｅｔｅｃｔｏｒ　ｕｓｉｎｇ　ｔｈｅ　ｐｒｅｓｅｎｔｅｄ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｂｅｔｔｅｒ　ｔｈａｎ　ｔｈａｔｕｓｉ．ｓｔｒａｔｅｇｙ．　Ｋｅｙ　ｗｏｒｄｓ：Ｃｏｄｅ　Ｄｉｖｉｓｉｏｎ　Ｍｕｌｔｉｐｌｅ　Ａｃｃｅｓｓ（ＣＤＭＡ）；ｍｕｌｔｉ—ｕｓｅｒ　ｄｅｔｅｃｔｉｏｎ；ｅｖｏｌｕｔｉｏｎ　ｓｔｒａｔｅｇｙ；ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ　Ｏ引　言　此人们转而寻求运算复杂度和性能折衷的次佳多　用户检测算法，如解相关检测　］和最小均方误差．　检测等［５］。　在通信系统中　由于多址干扰的影响［　］，传统　检测器性能在各用户的相对功率不同时显著下　多用户信号的最佳检测在数学上可归结为求　解似然函数的最大值，因此可以用进化算法将此，　类问题转化为求解具有最大适应度值的问题。如　降，即产生“远一近”效应问题。多用户检测技术是　对远近效应、解决多址干扰问题的主要方法之　一　。目前，有关多用户检测技术主要有最佳多　文献［６］等提出基于遗传算法的多用户检测，其　计算量小于以前提出的次佳多用户检测，但遗传　算法由于被搜索的空间非常之大而导致其收敛速　用户检测器　和次佳多用户检测器两大类，虽然　最佳多用户检测器的性能较好，但其运算量随用　户数呈指数增长，难以满足实时通信的要求。因　收稿日期：２ＯＯ６—０３—２８；修改日期：２ＯＯ６—０４—３０　作者简介：许良凤（１９７０－－），女，安徽肥东人，合肥工业大学讲师．　度较慢，因而用于多用户检测中也存在收敛速度　维普资讯 http://www.cqvip.com

第１２期　等问题。　许良凤：一种新的改进进化规划多用户检测方法　１５０９　配滤波器组相关处理后的输出抽样值向量；Ｈ—　进化规划是进化计算中的代表算法之一，但　大量的研究证明，该算法存在的缺点ｌ＿７Ｊ之一是进　化容易出现过早收敛，从而陷入局部极值点，即早　熟现象。本文针对进化规划算法的这一缺点，将　进化规划进行改进并将其应用到多用户检测中，　该算法是在进化规划的变异操作后，随机产生一　ＡＲＡ；用户信息为　一［６　，ｂ　，…，　］Ｔ。　２改进的进化规划的多用户检测方法　定义解空间Ｂ＝＝＝｛Ｂ　，Ｂ　，…，Ｂ　）即为一种　群体，Ｎ为种群的规模。Ｂ中的任意一个元素　Ｂ　一［６　，ｂ　，・“，　］称为染色体，Ｂ　中的ｂ　一１或　一些个体，新种群是在父代、父代经过高斯变异产生　１称为基因，Ｋ为用户数。多用户检测问题的　的个体及随机产生的个体中产生。通过实验证　明，改进的进化规划多用户检测算法，无论是在抗　多址干扰的能力还是在抗远近效应的能力都优于　进化规划的多用户检测方法。　１多用户检测的系统模型　多用户检测器的原理框图Ｌ８ｊ，如图１所示。　对于同步通信系统，假定小区中用户数Ｋ，则天　线接收的基带信号为　Ｋ—　ｒ（　）＝＝＝　Ａｋｂ＾（ｊ）ｓｋ（￡－－ｊＴ）＋册（　）　＾一１　ｔ∈　Ｔ，ｊＴ＋丁］　（１）　其中，ｂ　∈｛一１，１）为第ｋ个用户发射的比特数　据；Ａ　为第ｋ个用户接收信号的幅值；Ｓ　（　）第ｋ　个用户的确定性扩展波形；Ｔ为码元间隔；　（ｆ）　加性高斯白噪声；　是噪声的均方差。　ｒ（ｔ）　‘＿＿　叫匹配滤波器ｌ　，ｒｆ、＋Ｊ　多　　＾　－＿叫匹配滤波器２卜＿　＿、－二二　户　用　－　Ｚ　检　：　：－　　（ｆ）　测　器　（　匹配滤波器　｝＿＿　——＿＋　图ｌ　多用户检测器的原理框图　匹配滤波器的输出为　Ｙ＝ＲＡｂ＋，ｌ　其中，ｂ是信息矢量；Ｒ为互相关矩阵　一　［　］　一ｌ，Ｐ　－－１，而　一　（￡）　（ｔ）ｄｔ。Ａ—ｉｄｉａｇ　［Ａ１，…，ＡＫ］，Ｅ（ｎｎ　）一　Ｒ。　以最大似然序列估计为准则，最佳多用户检　测方法是将其转化为一个二次整数优化问题的　解，其矩阵形式为　６一ａｒｇ｛ｍａｘ［２ｂＴｎｙ—ｂＴ硒］）　（２）　６∈／－］，１｝　＋　其中，　一［＿ｙ　，Ｙ　，…，＿ｙＫ］１是接收信号ｒ（　）经匹　目标就是要获得使２ｙＴＡＢ　—ＢＴＨＢ　达到最大时　的Ｂ　值，因此代价函数应为　Ｆ（Ｂ　）一２ｙＴＡＢ　—ＢＴＨＢ　（３）　为了保证个体的适应度是正值，根据代价函　数构造适应度函数为　ｆ（Ｂ　）一ｅ。＿。　Ｆ‘　’　（４）　基于改进的进化规划多用户检测方法流程　如下：　（１）初始化控制参数：群体规模Ｎ，用户数　Ｋ，进化代数Ｍ。　’　（２）编码：在多用户检测中，所要寻找的解向　量６是一个取值为＋１或一１的二进值序列，长度　等于用户数Ｋ，所以不需要对此问题进行编码。　（３）种群初始化：为了加速收敛速度和减小　计算复杂度，将传统检测器的输出作为初始种群　的一个个体，其余个体随机产生。　（４）计算适应度值，利用（４）式计算种群中各　个个体的适应度值。　（５）变异：对种群中的每一个个体进行变异　得到Ｎ个新个体Ｂ　一［６　，ｂ　，…，ｂ　Ｋ］，其中　ｂ　一ｓｇｎ［　＋Ｎｋ（０，１）］（ｋ一１，２，…，Ｋ），　（Ｏ，１）是均值为０，方差为１的高斯随机变量。　（６）随机产生一些个体，从问题解空间中随　机产生Ｎ个个体。　（７）计算适应度值，对（５）变异后产生的Ｎ个　新个体及（６）随机产生Ｎ个个体计算适应度值。　（８）选择：将３Ｎ个个体按适应度值从大到　小的顺序进行排列，选择前Ｎ个个体作为下一代　群体。　（９）若满足收敛条件，达到预先设定的遗传　代数Ｍ＝＝＝１０，则进化过程结束，否则转（５）。　由上面可以看出，传统的进化规划在进化规　划的变异操作后，新的种群是在父代及父代经　过高斯变异产生的个体中产生。而本文算法是　维普资讯 http://www.cqvip.com

１５１０　舍肥工业大学学报（自然科学版）　第２９卷　在进化规划的变异操作后，新的种群是在父代、　父代经过高斯变异产生的个体及随机产生一些　个体中产生。由于在产生新的种群时增加了随　机产生的一些个体，因此增加种群的多样性，这　样就保证了整个种群既具有大范围的搜索能　力，也具有局部寻优能力，从而较好的克服了进　化规划的早熟现象。　３试验与分析　本文讨论一个１Ｏ用户的同步ＤＳ－ＣＤＭＡ通　信系统，假设扩频序列采用３１位Ｇｏｌｄ序列。　仿真中，标准遗传算法的参数如下：遗传代数　为１Ｏ，交叉概率为Ｐ　一０．９，变异概率为Ｐ　一　０．０１，种群规模Ｎ：３０；进化规划算法和改进进　化规划算法的参数：遗传代数为１Ｏ，种群规模　Ｎ＝３０。首先进行功率控制下的误码率的检测。　在功率控制下，所有用户的信号功率相等，并选择　每个用户的信噪比（ＳＮＲ）从０（璐增加到２０　ｄＢ，　来比较不同检测器在不同信噪比下的误码率　（ＢＥＲ），实验结果如图２所示。　４　８　ｌ２　１６　２０　ＳＮＲ／ｄＢ　１．本文算法２．进化规划３．标准遗传算法４．传统检测　图２功控下的多用户检测器的误码率　从图２可以看出，改进的进化规划算法抗多　址干扰的性能优于标准遗传算法和进化规划　算法　在考察算法抗远近效应的能力时，不失一般　性，设定第２个用户的ＳＮＲ从０　ｄＢ增加到　１Ｏ　ｄＢ，其他用户的ＳＮＲ固定在１　ｄＢ，来比较不　同检测器抗远近效应的能力，实验结果如图３　所示。　从图３可以看出，基于改进进化规划的多用　户检测方法抗远近效应的性能，优于标准遗传算　法和进化规划方法。　ＳＮＲ／ｄＢ　１．本文算法２．进化规划３．标准遗传算法４．传统检测　图３远近效应下的多用户检测器的误码率　４结　论　本文提出了一种改进进化规划算法的多用户　检测器，通过增加种群的多样性来克服进化规划　早熟收敛的致命缺点。仿真结果表明，这种多用　户检测算法的性能比标准遗传算法和进化规划多　用户检测器有明显的改进，是一种有效可行的多　用户检测算法。此方法同样适合异步ＤＳ－ＣＤＭＡ　通信系统。　［参考文献］　Ｅｌｉ郭梯云，杨家玮，李建东．数字移动通信ＥＭ］．北京：人民邮　电出版社，１９９６．１５—１１３．　［２］王志斌，芦康俊，蔡国权．Ｄｓ／ＣＤＭＡ系统中的多用户检测　［Ｊ］．信息工程学院学报，１９９３，１８（１）：ｌ１—１５．　［３］Ｌｕｐａｓ　Ｒ，Ｖｅｒｄｕ　Ｓ．Ｌｉｎｅａｒ　ｍｕｌｔｉｕｓｅｒ　ｄｅｔｅｃｔｏｒｓ　ｆｏｒ　ｓｙｎｃｈｒｏ—　ＤＯＵＳ　ｃｏｄｅ－ｄｉｖｉｓｉｏｎ　ｍｕｌｔｉｐｌｅ　ａｃｃｅｓｓ　ｃｈａｎｎｅｌｓ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓ　Ｉｎｆｏｒｍ　Ｔｈｅｏｒｙ，１９８９，３５（１）：１２３　１３６．　［４］Ｂａｒａ　Ｍ．Ａ　ｎｅｗ　ａｐｐｒｏａｃｈ　ｆｏｒ　ｆｉｎｄｉｎｇ　ｔｈｅ　ｇｌｏｂａｌ　ｍｉｎｉｍｕｍ　ｏｆ　ｅｒｒｏｒ　ｆｕｎｃｔｉｏｎ　ｏｆ　ｎｅｕｒａｌ　ｎｅｔｗｏｒｋｓ［Ｊ］．Ｎｅｕｒａｌ　Ｎｅｔｗｏｒｋｓ，　１９８９，２：３６７—３７３．　Ｉｓ］Ｃｅｍ　Ｅ，Ｈａｃｉｏｇｌｕ　Ｋ．Ｍｕｌｔｉｕｓｅｒ　ｄｅｔｅｃｔｉｏｎ　ｕｓｉｎｇ　ａ　ｇｅｎｅｔｉｃ　ａｌ—　ｇｏｒｉｔｈｍ　ｉｎ　ＣＤＭＡ　ｃｏｍｍｕｎｉｃａｔｉｏｎｓ　ｓｙｓｔｅｍｓ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓ　Ｃｏｍｍｕｎ，２０００，４８（８）：１　３７４—１　３８３．　Ｅ６］　Ｚｈａｎｇ　Ｂ　Ｎｅｕｒａｌ　ｎｅｔｗｏｒｋｓ　ｆｏｒ　ｍｕｈｉｕｓｅｒ　ｄｅｔｅｃｔｉｏｎ　ｉｎ　ｃｏｄｅ－ｄｉｖｉｓｉｏｎ　ｍｕｌｔｉｐｌｅ－ａｃｃｅｓｓ　ｃｏｍｍｕｎｉｃａｔｉｏｎｓ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓ　ｏｎ　Ｃｏｍｍｕｎ，１９９２，４０　１１　２１２—１　２２２．　［７］Ｇｏｌｄｂｅｒｇ　Ｄ　Ｅ　Ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍｓ　ｉｎ　ｓｅａｒｃｈ，ｏｐｔｉｍｉｚａｔｉｏｎ　ａｎｄ　ｍａｃｈｉｎｅ　ｌｅａｒｎｉｎｇ［Ｍ］．Ｒｅａｄｉｇｎ，ＭＡ：Ａｄｄｉｓｏｎ　Ｗｅｓ—　ｌｅｙ，１９８９．９　１５０．　［８］许良凤．一种新的次优多用户检测器［Ｊ］．合肥工业大学学　报（自然科学版），２００５，２８（１１）：１　３８１—１　３８３．　（责任编辑张秋娟）