基于模拟退火的并行进化规划多用户检测算法

1、基于模拟退火的并行进化规划多用户检测算法许良凤 丁志中 赵 烨(合肥工业大学计算机与信息学院通信所, 合肥 230009)摘 要：模拟退火和多种群并行进化规划是2种较好的改进进化算法性能的方法。将这2种思想有机地结合起来, 提出了一种基于模拟退火的并行进化规划多用户检测算法。在该算法中, 进化在多个不同的子群中并行进行, 利用模拟退火算法的爬山性能, 避免单种群进化过程中出现的过早收敛现象, 提高整个算法的收敛速度。仿真结果表明, 这种新的多用户检测算法抗多址干扰和抗远近效应能力都优于单种群的模拟退火进化规划多用户检测算法, 并且在多址干扰和远近效应存在的条件下, 其收敛速度明显优于基于单种群

2、的模拟退火进化规划检测器。 关键词：CDMA；多用户检测器；模拟退火；进化规划中图分类号：TN914.53文献标识码：A国家标准学科分类代码：510.50Multi-user detection algorithm based on simulated annealing parallel evolutionary programmingXu Liangfeng Ding Zhizhong Zhao Ye(School of Computer and Information, Hefei University of Technology, Hefei 230009)Abstract: Simu

3、lated annealing and multi-group parallel evolutionary programming are two helpful methods which can improve the performance of evolutionary algorithm. The two ideas are well combined a new multiuser detection, that is the parallel evolutionary programming algorithm based on simulated annealing, is p

4、roposed in the paper. In the algorithm, the evolutions of subgroup is performed in parallel with the hill climbing performance of simulated annealing, so this algorithm can avoid the premature convergence of the alone group evolutionary process and improves the convergence speed of the algorithm. Th

5、e simulation results show that the new algorithm not only is superior to the multi-user algorithm based on the alone group simulated annealing evolutionary programming, but also can faster convergence than the detector based on the alone group simulated annealing evolutionary programming in the term

6、s of multiple-access interfere and near-far resistance.Keywords: code division multiple access; multi-user detector; Simulated annealing; evolutionary programming1 引 言码分多址是近年来用于数字蜂窝移动通信的一种先进的无线扩频通信技术。然而多址干扰及由它引起的远近效应却成为制约其发展的致命瓶颈1。克服多址干扰最根本方法是寻找完全正交的地址码。然而在异步信道中, 随着用户数增加, 要找到这样的地址码是极为困难。于是人们开始研究各种多用

7、户检测方法来克服或减轻多址干扰和远近效应2。近年来许多学者提出了一系列基于遗传算法3和神经网络等智能算法的多用户检测器4, 这些方法都可使计算复杂度有较大下降, 性能也优于传统检测器。但都存在着一些不足如收敛速度问题。进化计算是一种模拟自然进化过程的随机优化方法。进化规划5是进化计算中的代表算法之一, 但大量的研究证明, 该算法存在的缺点6是进化容易出现过早收敛, 从而陷入局部极值点, 即早熟现象; 进化后期, 个体之间的竞争趋于缓慢因而导致算法后期的搜索效率降低。针对这些弱点利用进化规划能全局寻优的优势和模拟退火算法的爬山性能设计了基于模拟退火的并行进化规划多用户检测算法, 在该多用户检测算

8、法中, 一方面利用了并行进化规划将并行计算机的高速并行性和进化规划天然并行性相结合, 极大地提升了进化规划的求解速度和质量; 另一方面通过Boltzmann机制来接收子代, 这样做有利于优良个体的保留。随着进化过程的进行, 温度逐渐下降, 接收劣质解的概率逐渐减小, 即利用模拟退火算法的爬山性能提高整个算法的收敛速度。仿真结果表明, 该检测算法在抗多址干扰的能力和抗远近效应的能力优于单种群的模拟退火进化规划检测算法, 收敛速度更快。文中着重于同步CDMA系统的研究。2 CDMA系统接收模型假设一个CDMA通信系统的用户数为K, 传输信道为高斯信道。则基站接收到的信号为：(1)式中: 和Ak分别

9、是第个用户发送的 信息比特和信号幅度, T是码元间隔, 是第个用户的特征波形, n(t)是具有单位功率谱密度的加性高斯白噪声。同步高斯信道K个用户匹配滤波器输出为(2)将式(1)代入式 (2) 并写成向量形式, 即 y=RAb+n式中: 是不同用户扩频波形的相关矩阵, 为用户信息向量, n为高斯白噪声向量。最佳多用户检测就是采用最大似然序列估计为准则找出一个接收信号序列, 使给定输出序列的似然函数最大, 最佳多用户检测器输出向量为7 (3)式中: H= ARA。3 基于模拟退火并行进化规划的多用户检测算法并行进化规划主从处理器的结构图如文献8所示。由式(3)可知, 多用户检测是一个组合优化问题

10、, 结合模拟退火及并行进化规划特点, 提出一种基于模拟退火并行进化规划的CDMA多用户检测问题的优化处理方法。每个处理器运行的模拟退火进化规划的主循环详细流程图如图1所示。图1 每个处理器运行的模拟退火进化规划的主循环流程图Fig. 1 Main loop flow chart of each processor movement based on simulated annealing evolutionary programming3.1 适应度函数定义解空间称为一种群体, 为种群的规模。x中的任意一个元素称为染色体, xi中的或-1, 称为基因, K为用户数。多用户检测问题的目标就是要获

11、得使达到最大时的xi值, 因此代价函数应为 (4)为了保证个体的适应度是正值,由代价函数所构造的适应度函数为 (5)3.2 编 码由于多用户检测器的输出是双极性信号(+1和 -1), 所以不需要编码。3.3 种群初始化为了加速收敛速度和减小计算复杂度, 将传统检测器的输出作为初始种群的一个个体, 其余个体从解空间中随机产生。3.4 变 异对子种群中的个体进行高斯变异得到N个新个体式中 Nk (0,1)是均值为0, 方差为1的高斯随机变量。3.5 选 择将变异前的个体和变异后的子代组成临时种群, 并计算临时种群中2N个个体的适应度函数, 使用随机q竞争法则, 选取排在前面N个个体组成新的种群作为

12、下一代进化的初始种群。4 实验结果与分析讨论一个12个用户的同步DS-CDMA通信系统, 假设扩频序列采用31位Gold序列, 采用高斯信道, 并用MATLAB软件进行仿真。实验中, 模拟退火的并行进化规划的参数如下：从处理器的个数为2, 每个从处理器处理种群的个体总数为8, 变异概率为, 温度冷却系数=0.9, 退火初始温度T=999, 每个用户发送5 000个bit。4.1 严格功率控制下的误码率的检测在严格功率控制下, 接收到所有用户的功率相同, 并选择每一个用户信噪比(SNR)从-6 dB增加到4 dB来比较基于模拟退火并行进化规划的多用户检测器和基于单种群的模拟退火进化规划检测器在不

13、同信噪比下的误码率(BER)情况, 结果如图2所示。图2 功控下的误码率Fig. 2 BER under power control由图2可以看到, 本文方法的抗误码性能比基于单种群的模拟退火进化规划检测器好。4.2 抗远近效应能力实验参数：设定第二个用户的信噪比(SNR2)从6 dB增加到4 dB, 其他用户的SNR固定在6 dB, 来比较不同检测器抗远近效应能力, 结果如图3所示。由图3可以看到, 本文方法的抗远近干扰性能比基于单种群的模拟退火进化规划检测器好。图3 远近效应下的误码率Fig. 3 BER comparison of near-far effect4.3 收敛速度在考察算法

14、的收敛速度时, 最大的迭代代数设为50。首先考察在严格功率控制下, 所有用户的信号功率相等, 信噪比为-2dB, 不同的迭代次数, 基于模拟退火并行进化规划的多用户检测器和基于单种群的模拟退火进化规划检测器的误码率和迭代次数的关系如图4所示。图4 功控下的收敛曲线Fig. 4 Convergent curve of power control在远近效应下, 除了用户1其他用户设为干扰用户, 目标用户的信噪比为-2dB, 干扰用户功率相同, 用户1的误码率和迭代次数的关系如图5所示。图5 远近效应下的收敛曲线Fig. 5 Convergent curve under near-far effec

15、t从图4和图5可以看到, 基于模拟退火并行进化规划的多用户检测器无论在多址干扰还是在远近效应存在的条件下, 其收敛速度优于基于单种群的模拟退火进化规划检测器。5 结 论本文构造了模拟退火并行进化规划的多用户检测器, 通过上述分析比较得出：模拟退火并行进化规划的多用户检测器在抗多址干扰性能和抗远近效应性能都优于基于单种群的模拟退火进化规划检测器的检测性能, 并且新的检测器能够快速收敛。参考文献：1 尤肖虎. 第三代移动通信系统发展现状与展望J. 电子学报, 1999, 27: 1-10.YOU X H. A perspective of the third generation mobile c

16、ommunications systemJ.  Acta Electronica Sinica, 1999, 27: 1-10.2 BELLLCORE S M. Multiuser detection for DS-CDMA communicationsJ. IEEE Communications Magazine, 1996, 34(10): 124-135. 3 ERGUN C, HACIOGLU K. Multiuser detection using a genetic algorithm in CDMA communications systemJ. IEEE Trans.

17、 Communications, 2000, 48(8): 1374-1383.4 KECHRIOTIS G, MANOLAKOS E S. Hopfield neural network implementation of the optimal CDMA multiuser detectorJ. IEEE Trans. on Neural Networks, 1996, 7(1): 131-141.5 LIM H S, RAO M V C, TAN A W C, et al. Multi-user detection for DS-CDMA systems using evolutiona

18、ry programmingJ. IEEE Communications Letters, 2003, 7(3): 101-103.6 YAO X, LIU Y, LIN G. Evolutionary programming made fasterJ. IEEE Transactions on Evolutionary Computation, 1999, 3(2): 82-88.7 VERDU S. Minimum probability of error for asynchronous gaussian multiple access channelsJ. IEEE Transaction on Information Theory, 1986, 32(1) :85-96.8 许良凤, 胡敏. 基于并行进化规划的多用户检测器J.电子测量与仪器学报, 2007, 21(4): 108-111.XU L F, HU M. Multi-user detector based on parallel evolutionary programmingJ. Journal of Electronic