（信号与信息处理专业论文）dscdma系统中基于蚁群算法的多用户检测技术的研究.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 c d m a 系统在技术上的优势己经使它成为3 g 的核心体制，但系统的容量 和通信质量受限于多址干扰。多用户检测技术是宽带c d m a 通信系统抗干扰的 关键技术，其中最优多用户检测方法在理论上可以完全克服多址干扰，但计算 复杂度大，因而目前无法实时实现。近年来，在智能计算领域出现一类新型的 群智能优化算法，如蚁群算法、粒子群算法、鱼群算法等，它们模拟自然界生 态系统机理，具有许多与传统优化算法不同的特点，并已成功运用于求解一些 n p 难解问题。本文的主要工作就是将改进蚁群算法应用到多用户检测中去： 首先，分析了d s c d m a 通信系统中的多用户问题，从算法复杂性的角度 认识d s c d m a 通信中的多用户检测方法。 其次，详细介绍了蚁群算法的原理以及它在解决n p 问题中的应用。 最后，结合现有多用户检测问题的实际特点，把改进的蚁群算法应用到其 当中去。并通过仿真实例，验证了改进算法的有效性。 本文主要包括以下创新之处： ( 1 ) 在文献 6 】中基于蚁群算法建立的多用户检测问题的模型的基础上，向蚁 群算法中引入迭代优化策略，从而实现在相同复杂度的情况下降低误码率，加 快收敛速度。 ( 2 ) 针对蚁群算法初始信息匮乏，导致算法速度慢的缺点，把它和具有快速 收敛能力的h o p f i e l d 神经网络相结合，让h o p f i e l d 神经网络为蚁群算法提供良 好的信息素初值，从而使误码率降低，并且受用户数量增大的影响变小，加快 算法收敛速度。 关键词码分多址扩频系统；多用户检测；蚁群优化算法；h o p f i e l d 神经网络 西南交通大学硕士研究生学位论文第l i 页 a b s t r a c t c o d ed i v i s i o nm u l t i p l ea c c e s s ( c d m a ) h a sm o r ea d v a n t a g e st h a no t h e r a c c e s st e c h n o l o g i e s ，s oi th a sa l r e a d yb e c a m et h ec o r et e c h n o l o g yo ft h et h i r d g e n e r a t i o n w i r e l e s sc o m m u n i c a t i o n s y s t e m s ，b u t t h e s e s y s t e m s a r ea l l i n t e r f e r e n c e - l i m i t e d ，t h es y s t e mp e r f o r m a n c e a n dc a p a c i t yi sl i m i t e d b yt h e m u f t i a c c e s si n t e r f e r e n c e ( m a d m u f t i u s e r d e t e c t o r ( m u d ) i s t h e k e y i n t e r f e r e n c ec a n c e l l a t i o nt e c h n o l o g yo ft h ew i d e b a n dc d m ac o m m u n i c a t i o ns y s t e m ， t h eo p t i m a lm u dc a l lo v e r c o m et h em a it h e o r e t i c a l l y ，b u ti tc a nn o tb ec a r r i e do u t i nr e a lt i m eo nt h ec u r r e n tt e c h n o l o g yc o n d i t i o nd u et oi t sh i g hc o m p l e x i t y i nr e c e n t y e a r s ，i nt h ef i e l do fi n t e l l i g e n tc o m p u t a t i o n , t h e r ea r es e v e r a lt y p e so fs w a r m i n t e l l i g e n c ea l g o r i t h m s t h a th a v ee m e r g e d , s u c ha sa n tc o l o n y o p t i m i z a t i o n a l g o r i t h m s ( a c 0 ) ，p a r t i c l es w a r mo p t i m i z a t i o n ( p s 0 ) ，s h o a lo p t i m i z a t i o na n ds o o n t h e r ea r es e v e r a ld i s t i n c t i v ef e a t u r e si nt h es w a r mi n t e l l i g e n c ea l g o d t h r n st h a t a r ed i f f e r e n tf r o mc o n v e n t i o n a lo p t i m i z a t i o na p p r o a c h e s ，a n dt h e yh a v ea l r e a d yb e e n u s e dt os o l v em a n yc l a s s i c a ln p p r o b l e m s t h i st h e s i si sd e d i c a t e dt ot h ea p p l i c a t i o n o f i m p r o v e da n tc o l o n yo p t i m i z a t i o n ( a c o ) t os o l v et h ei s s u eo fm u d f i r s t l y ，a n a l y s i so ft h em u dp r o b l e mi nc d m ac o m m u n i c a t i o ns y s t e m s ， c o m i n go u tf r o mt h et h e o r yo fc o m p u t a t i o n a lc o m p l e x i t y s e c o n d l y ，i n t r o d u c et h et h e o r yo fa c oa n da p p l i c a t i o ni ns o l v i n gn pp r o b l e m i nd e t a i l l a s t l y ，a p p l yi m p r o v e da c ot o m u dp r o b l e m c o n s i d e r i n g i t sf a c t u a l c h a r a c t e r i s t i c ，m o r e o v e r ，h a v ep r o v e dt h ei m p r o v e da c 0 sv a l i d i t yb ye m u l a t i o n t h em a i nc o n t r i b u t i o no ft h i st h e s i sc a l lb es u m m a r i z e da sf o l l o w s ： ( 1 ) o nt h eb a s i so ft h em o d e lo fm u db a s e do na c oi nd o c u m e n t 6 】， i m p r o v e dt h ea c oa l g o r i t h mi no r d e rt or e a l i z el o wb i te r r o rr a t e ( b e r ) 、p i c ku p r a t eo fc o n v e r g e n c ew h e nh a v i n gs a m e c o m p l e x i t y ( 2 ) i no r d e rt os o l v et h ed i s a d v a n t a g eo fd e f i c i e n ti n i t i a lp h e r o m o n ea n ds l o w r a t eo fc o n v e r g e n c eo fa c o ，w ec o m b i n ea c 0w i t hh o p f i e l dn e u r a ln e t w o r kw h i c h o w n i n gf a s tc o n v e r g e n c ea b i l i t yt o g e t h e r l e th o p f i e l dn e u r a ln e t w o r ks u p p l yg o o d i n i t i a lp h e r o m o n ef o ra c o ，s ot h a ti m p r o v e sb o t hc o m p l e x i t ya n db e r 西南交通大学硕士研究生学位论文第1 li 页 k e yw o r d ：c o d ed i v i s i o nm u l t i p l ea c c e s sc o m m u n i c a t i o ns y s t e m ( c d m a ) ； m u l t i u s e rd e t e c t o r ( m u d ) ；a n tc o l o n yo p t i m i z a t i o na l g o r i t h m s ( a c o ) ；h o p f i e l d n e u r a ln e t w o r k 西南交通大学四南父遗大罕 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规 定，同意学校保留并向国家有关部门或机构送交论文的复印件和 电子版，允许论文被查阅和借阅。本人授权西南交通大学可以将 本论文的全部或部分内容编入有关数据库进行检索，可以采用影 印、缩印或扫描等复印手段保存和汇编本学位论文。 本学位论文属于 1 保密口，在年解密后适用本授权书； 2 不保密影使用本授权书。 ( 请在以上方框内打“4 ) 舯老y 南虢多易杉 日期： 弗6 易 珲 攀 妒身篁 名 7 签移 者虱作曩黼叼 途 ： 位期学r 西南交通大学学位论文创新性声明 本人郑重声明：所呈交的学位论文，是在导师指导下独立进 行研究工作所得的成果。除文中已经注明引用的内容外，本论文 不包含任何其他个人或集体已经发表或撰写过的研究成果。对本 文的研究做出贡献的个人和集体，均己在文中作了明确的说明。 本人完全意识到本声明的法律结果由本人承担。 本学位论文的主要创新点如下： ( 1 ) 在文献 6 】中基于蚁群算法建立的多用户检测问题的模型 的基础上，向蚁群算法中引入迭代优化策略，从而实现在相同复 杂度的情况下降低误码率，加快收敛速度。 ( 2 ) 针对蚁群算法初始信息匮乏，导致算法速度慢的缺点，把 它和具有快速收敛能力的h o p f i e l d 神经网络相结合，让h o p f i e l d 神 经网络为蚁群算法提供良好的信息素初值，从而使误码率降低， 并且受用户数量增大的影响变小，加快算法收敛速度。、 西南交通大学硕士研究生学位论文第1 页 第1 章引言 1 1 课题的研究背景和发展方向 由于移动通信在未来的信息产业中具有举足轻重的地位，发达国家的政 府部门、电信运营商及制造商均不遗余力地积极参与有关第三代移动通信标 准制定及其科研开发工作，以期在未来的竞争中占据有利地位。码分多址 ( c o d ed i v i s i o nm u l t i p l ea c c e s s ，稍称c d m a ) 移动通信系统是一种先进的 移动通信系统，c d m a 技术己成为第三代移动通信的主流技术。它具有大容 量、软切换、清晰的话音质量和良好的保密性能等优点，能缓和有限频带与 无限用户需求之间的矛盾。因此，它越来越为移动通信运营商和用户所青睐。 然而，与其它移动通信系统一样，c d m a 系统也是一种干扰限制系统，随着 干扰用户数的增加，c d m a 系统容量将降低，系统性能将恶化。在c d m a 通信系统中，干扰可以大致分为三种类型：加性白噪声干扰、多径干扰、多 址干扰。当同时通信的用户数较多时，多址干扰( m u l t i p l ea c c e s si n t e r f e r e n c e ， 简称m a i ) 成为最主要的干扰，这主要是由于c d m a 系统中多个用户共享 同一个信道，不同用户之间的非零互相关系数而引起的。多址干扰已成为制 约c d m a 系统进一步发展的致命瓶颈，因此抵抗与限制多址干扰成为c d m a 移动通信系统的一项主要任务。多址干扰也称多用户干扰，因此，多址干扰 的抑制问题也就是多用户检测问题，而多用户检测技术被认为是c d m a 通信 系统的关键技术之一。多用户检测的基本思想是：通过挖掘有关干扰用户的 信息( 信号到达时间、使用的扩频序列和信号幅度等) 来消除多址干扰，进 而提高信号的稳定性，不再像传统检测器那样忽略系统中其它用户的存在。 关于多用户检测问题的研究，近年来一直是移动通信领域中的一个研究 热点。众多学者己积极投身到这一问题的研究中，进行了卓有成效的工作， 目的是寻找到一种能够解决多址干扰抑制问题的有效方法，作为抑制多址干 扰的一种主要手段。多用户检测的理论研究起源于八十年代初，有关这方面 最早的文献是1 9 7 9 年s c h n e i d e r 发表的一篇文章，但没有引起人们的关 注。直到1 9 8 6 年，v e r d u 利用对数似然函数的可分解性，证明了s c h n e i d e r 的 猜想：直扩码分多址系统中的最佳多用户检测可以由匹配滤波器组后接 v i t e r b i 译码器构成。该检测器的提出，显示了c d m a 系统巨大的容量潜力 西南交通大学硕士研究生学位论文 第2 页 和性能改善潜力，使多址干扰抑制问题引起了学者们的注意。然而，由于最 佳多用户检测算法的复杂度随系统中的用户数成指数关系增长，当用户数较 大时，运算量非常大，以致于实现起来很困难。但是v e r d u 的工作为进一步 的研究奠定了理论基础，促使人们去寻找复杂度低，性能比传统检测器优越 的各种次佳多用户检测器。 多用户检测在处理方法上，大致可分为线性与非线性两大类。线性多用 户检测是在标准判决之前对相关器的输出矩阵进行线性变换，各用户复杂度 只是用户数的线性函数，而性能接近最佳多用户检测器。目前，线性多用户 检测器主要包括：传统检测器、解相关检测器和最小均方误差检测器等。非 线性方法中，目前研究较多的是基于判决反馈的多址干扰抵消检测技术。另 外还有多级检测、基于神经网络的多用户检测器、序列检测、分组检测等等。 由于无线传输信道的时变和不可靠性，使得多用户检测器的参数如振幅、相 位以及用户间的互相关性要不断改变更新。因此人们又开始研究自适应的多 用户检测器，使得参数能根据接收信号不断的自动调整，对接收信号进行学 习，从而抑制干扰。而当通信信道响应突然变化或出现新的同信道用户时， 对于自适应检测器来说，需要对训练序列不断发送造成了频谱资源的极大浪 费，因此人们便转而研究只使用观测数据不需要训练序列的自适应多用户检 测，称为盲自适应多用户检测。近来将一些现代优化算法以及他们的混合优 化算法应用于多用户检测又已经成为了一个新的研究热点，也取得了一定的 优化成果。 1 2 蚁群优化算法 1 2 1 基本蚁群算法的起源 蚂蚁是地球上最常见、数量最多的昆虫种类之一，常常成群结队地出现 于人类的日常生活环境中。这些昆虫的群体生物智能特征，引起了一些学者 的注意。受自然界中真实蚁群集体行为的启发，意大利学者m d o r i g o 于2 0 世纪9 0 年代初，在他的博士论文中首次系统地提出了一种基于蚂蚁种群的 新型优化算法蚁群算法( a n tc o l o n yo p t i m i z a t i o n ，a c o ) ，并成功地用 于求解旅行商( t s p ) i f i 题，自1 9 9 6 年之后的五年的时间里，蚁群算法逐渐引 起了世界许多国家研究者的关注，在应用领域得到了迅速拓宽。我国最早研 究蚁群算法的是东北大学张纪会博士和徐心和教授。目前人们对蚁群算法的 西南交通大学硕士研究生学位论文第3 页 研究已由当初单一的t s p 领域渗透到了多个应用领域，由解决一维静态优 化问题发展到解决多维动态组合优化问题，由离散域范围内研究逐渐拓展到 了连续域范围内的研究。使这种新兴的仿生优化算法展现出勃勃生机，并已 经成为可与遗传算法相媲美的仿生优化算法。 1 2 2 蚁群算法的研究背景 群智能理论研究领域有两种主要的算法：蚁群算法( a n tc o l o n y o p t i m i z a t i o n ，a c o ) 和微粒群算法( p a r t i c l es w a r mo p t i m i z a t i o n ，p s o ) 。前者 是对蚂蚁群落食物采集过程的模拟，已成功应用于许多离散优化问题。微粒 群算法也是起源于对简单社会系统的模拟，最初是模拟鸟群觅食的过程，但 后来发现它是一种很好的优化工具。与大多数基于梯度的应用优化算法不 同，群智能依靠的是概率搜索算法。虽然概率搜索算法通常要采用较多的评 价函数，但是与梯度方法及传统的演化算法相比，其优点还是显著的，主要 表现在以下几个方面： ( 1 ) 无集中控制约束，不会因个别个体的故障影响整个问题的求解，确 保了系统具备更强的鲁棒性 ( 2 ) 以非直接的信息交流方式确保了系统的扩展性 ( 3 ) 并行分布式算法模型，可充分利用多处理器 ( 4 ) 对问题定义的连续性无特殊要求 ( 5 ) 算法实现简单 群智能方法易于实现，算法中仅涉及各种基本的数学操作，其数据处理 过程对c p u 和内存的要求也不高。而且，这种方法只需目标函数的输出值， 而无需其梯度信息。己完成的群智能理论和应用方法研究证明群智能方法是 一种能够有效解决大多数全局优化问题的新方法。更为重要是，群智能潜在 的并行性和分布式特点为处理大量的以数据库形式存在的数据提供了技术保 证。无论是从理论研究还是应用研究的角度分析，群智能理论及其应用研究 都是具有重要学术意义和现实价值的。 西南交通大学硕士研究生学位论文第4 页 1 2 3 蚁群算法的研究现状 9 0 年代d o r i g o 最早提出了蚁群优化算法蚂蚁系统( a n ts y s t e m ，a s ) ， 并将其应用于解决计算机算法学中经典的旅行商问题( t s p ) 。从蚂蚁系统开 始，基本的蚁群算法得到了不断的发展和完善，并在t s p 以及许多实际优化 问题求解中进一步得到了验证。这些a s 改进版本的一个共同点就是增强了 蚂蚁搜索过程中对最优解的探索能力，它们之间的差异仅在于搜索控制策略 方面。而且，取得了最佳结果的a c o 是通过引入局部搜索算法实现的，这 实际上是一些结合了标准局域搜索算法的混合型概率搜索算法，有利于提高 蚁群各级系统在优化问题中的求解质量。最初提出的a s 有三种版本： a n t d e n s i t y 、a n t q u a n t i t y 和a n t c y c l e 。在a n t d e n s i t y 和a n t q u a n t i t y 中蚂蚁 在两个位置节点间每移动一次后即更新信息素，而在a n t c y c l e 中当所有的蚂 蚁都完成了自己的行程后才对信息素进行更新，而且每个蚂蚁所释放的信息 素被表达为反映相应行程质量的函数。通过与其它各种通用的启发式算法相 比，在不大于7 5 个城市的t s p 中，这三种基本算法的求解能力还是比较理 想的，但是当问题规模扩展时，a s 的解题能力大幅度下降。因此，其后的 a c 0 研究工作主要都集中于a s 性能的改进方面。较早的一种改进方法是精 英策略( e l i t i s ts t r a t e g y ) ，其思想是在算法开始后即对所有已发现的最好路径 给予额外的增强，并将随后与之对应的行程记为t 。b ( 全局最优行程) ，当进行 信息素更新时，对这些行程予以加权，同时将经过这些行程的蚂蚁记为“精 英”，从而增大较好行程的选择机会。这种改进型算法能够以更快的速度获得 更好的解。但是若选择的精英过多则算法会由于较早的收敛于局部次优解而 导致搜索的过早停滞。 为了进一步克服a s 中暴露出的问题，提出了蚁群系统( a n tc o l o n y s y s t e m ，a c s ) 。该系统的提出是以a n t q 算法为基础的。a n t q 将蚂蚁算法 和一种增强型学习算法q 1 e a r n i n g 有机的结合了起来。a c s 与a s 之间存在 三方面的主要差异：首先，a c s 采用了更为大胆的行为选择规则；其次，只 增强属于全局最优解的路径上的信息素。其中，0 p l 是信息素挥发参数，三即 是从寻路开始到当前为止全局最优的路径长度。 t ，o + 1 ) = ( 1 一p ) t 玎o ) + p 下尹o ) ，其中t 尹( 力= 1 ( 1 1 ) 西南交通大学硕士研究生学位论文第5 页 再次，还引入了负反馈机制，每当一只蚂蚁由一个节点移动到另一个节 点时，该路径上的信息素都按照如下公式被相应的消除一部分，从而实现一 种信息素的局部调整，以减小已选择过的路径再次被选择的概率。 t 盯- - 0 一芎) t j 7 + 亏to ，其中o 专 1 0 ，b ( 期望值启发式因 子) 是表示路径长度在选择概率上的作用，其中b 之o ，在n 次循环后，所有 蚂蚁的禁忌表都已填满，此时计算每个蚂蚁走过的路径的长度，并找到最短 路径保存i 记录此路径并更改该路径上的信息素。这一过程重复直至达到最 大周游值结束。 信息素更新的公式是： r o + 刀) 2 p r ，o ) + r “( 3 - 2 ) 勺= r ： ( 3 - 3 ) a r ，表示在某条边上的累加新增信怠素的和，p 表示信息素消散的等级， 残留信息的保留部分，0 p 1 ，1 一j p 表示残留信息被削弱的部分，为了防止 信息的无限积累，p 必须小于1 ，r ：表示t 和t + n 之间第k 个蚂蚁在此边上 留下的信息素的数量。 f ! 的计算公式为： r 1 瞄：旁如果在琊h 砣间第阶蚂蚁使用此边 ( 3 呦 10 ，其它 其中q 为常量，表示蚂蚁循环一周所释放的总信息量。三r 为第k 个 蚂蚁在本次循环中所走路径的长度。它等于第k 个蚂蚁经过的各段路径上所 需的花费d j i 的总和。如果蚂蚁的路径总花费越高，那么其在单位路径上所 西南交通大学硕士研究生学位论文第2 4 页 释放的信息素浓度就越低。很显然，蚂蚁不会在其没有经历过的路径上释放 信息素。在以上算法中q 、0 【、b 、p 和蚂蚁数的最佳组合值是通过实验来确 定的。它们对算法性能也有很大的影响，a 值的大小表明留在每个结点上的 信息量受重视的程度，a 值越大，蚂蚁选择以前选过的点的可能性越大，但 过大会使搜索过早陷于局部最优解。b 的大小表明启发式信息受重视的程度。 q 值会影响算法的收敛速度，q 过大会使算法收敛于局部最优解，过小又会 影响算法的收敛速度，随问题规模的增大，q 的值也需要随之变化。蚂蚁的数 目越多，算法的全局搜索能力越强，但数目的加大将使算法的收敛速减慢， 而且在蚂蚁数目相同时，随问题规模的增大，算法的全局搜索能力将会降低。 3 4 蚁群算法在多用户检测技术中的应用 3 4 1 基于蚁群算法的多用户检测问题模型 文献【6 】中通过分析多用户检测问题与t s p 问题的异同，针对多用户检测 问题提出了一种更为简单的蚁群算法实现思想。该思想可以描述如下： 在t s p 问题中，每一只蚂蚁所要完成的任务就是找到一条经过n 个城市 的一条路径。在每到达一城市后，蚂蚁都要先检查随身携带的禁忌表( t a b u l i s t ) ，然后依据转移概率在没有经过的城市中选择下一个将要到达的城市， 并将这个城市添加到禁忌表中。在多用户检测中，由于各个用户之间相互独 立，所以可以把对k 个用户发送数据的判断看成是k 个独立的问题。不失一 般性，可以让蚂蚁按照从第1 个用户到第k 个用户的顺序进行判断，这样在 设计程序时就可以抛弃在基本蚁群算法中的禁忌表，降低程序的复杂度。同 时，这种处理方法很适合于并行计算，当用户数较多时，可以把解分成多段， 同时由多个蚂蚁进行求解，从而降低计算时间。另外，因为每个用户的数据 只有1 或者是1 两种可能，相当于只有两条供选择的路径，转移概率的公式 也会比t s p 问题简单。 蚁群算法中有一个很重要的参数：能见度7 7 。即边( i ，j ) 的能见度，反映由城 市i 转移到城市j 的启发程度，这个量在蚂蚁系统的运行中不变。在t s p 问 题中我们往往是把城市之间的距离作为启发信息的，并且在公式( 3 1 ) 中，7 7 。 和信息素强度r ，共同决定着转移概率p ：( f ) 的值，a 和p 为两个参数，分别反 映了蚂蚁在运动过程中所积累的信息和启发信息在蚂蚁选择路径中的相对重 要性。在多用户检测问题中，因为各个用户之间的独立性以及每个用户所发 西南交通大学硕士研究生学位论文第2 5 页 送数据的平稳随机性，我们很难寻找到类似于t s p 问题中城市间距离这样的 启发信息，所以本文中直接将能见度町。抛弃，仅利用信息素强度r 。进行转移 概率计算，由此可得到转移概率公式为： 蜘) 5 揣扣l ，2 ( 3 - 5 ) j 一l ，+ 1 ) 表示蚂蚁m 对第k 个用户的数据作出的判断。从式( 3 - 5 ) 可以 看出，我们在抛弃叩打的同时，也抛弃了参数口和卢，再加上上式中分母只有 两项相加，和式( 3 1 ) 相比，式( 3 5 ) 的计算复杂度大大降低。至此，就可以用 蚁群算法的思想将多用户检测问题描述成如图3 3 所示的一个路径选择问 题。 ab 路口1路口2 路口k 图3 3 多用户检测问题模型【6 1 在图3 3 中，a 点代表蚁穴，b 点代表食物所在地，蚂蚁要从a 点出发， 沿着灰色的路径到达b 点，但在途中要经过k 个岔路口，每个路口有两个长 度不等的路径分支。蚂蚁在每个路口都要根据遗留的信息素浓度依照式( 3 5 ) 所示转移概率进行路径选择，并在所经过的路径上释放信息素，要求蚂蚁最 终找到一条最短的路径。 在这个模型中，k 个路口代表着k 个用户，上下两条路径分支分别代表 了第k 各用户的数据1 和1 ，较短的路径分支表示用户的真实值。这样我们 就把多用户检测问题用蚁群算法的思想描述成为简单的路径选择问题，这个 模型其实就是著名g o s ss “双桥”模型。在后面的章节中，我们将在这个模型 的基础进行实验仿真。 西南交通大学硕士研究生学位论文第2 6 页 3 4 2 基于改进算法的多用户检测 ( 1 ) 改进的蚁群算法 在文献 6 中，为了简化蚂蚁在路径选择时要考虑的因素，作者在抛弃禁 忌表的同时也抛弃了启发信息。但是在蚂蚁选择路径的初期，启发信息对路 径的选择有很大的影响，如果初始时刻选择的路径比较好的话，就有可能很 快的趋向全局最优，从而降低误码率。另外，在处理m u d 问题时既要考虑 检测效果又要兼顾检测速度，在选择路径时也要考虑启发信息势必使检测速 度减慢，因此，针对以上问题本文通过引入文献 8 和 9 】中的两种方法对蚁群 算法进行改进： 加入启发信息【8 】 t s p 问题以城市间距离作为启发信息r 7 而m u d 问题是各用户信号比 特不同组合对目标函数的影响，所以采用将信息素痕迹留在被选择的节点上， 而不是连接节点的弧上，并且启发信息采用目标函数的线性函数，目标函数 为： ( 6 ) = 2 b f y b f h b ， ( 3 6 ) 迭代优化策略【9 】 为了进一步提高算法的执行效率，在算法中引入变量l m i 。用来记录每轮 求解后的路径最小值。该变量初始化为可能的最大值。在求得解路径后更新 该变量的值。并在以后各轮中，把每次蚂蚁选路后求得的当前解路径与该值 进行比较，如果大于该值，则本轮循环终止，进入下一轮循环，蚂蚁进行重 新选路。 ( 2 ) 算法描述及参数选择 目标函数 以式( 2 7 ) 为目标函数。 信息素更新规则 不同于t s p 问题中寻找的是路径的最小值，多用户检测问题要寻找的是 目标函数的最大值，所以式( 3 2 ) 在此更改为： r 蚵o + 1 ) = j c i r 蔚o ) + f 6 嘞 ( 3 7 ) 其中，缸蛔。：，( 6 6 删l j ( b b e s t k t ) 是本次迭代最优解的目标函数值。 西南交通大学硕士研究生学位论文第2 7 页 最大轨迹量t t 。：士，0 驴) ( 3 - 8 ) t m “2 i - ，妒。j 、。7 l p 其中，( 6 驴) 是全局最优解6 驴的目标函数。 最小轨迹量t 血 因为在多用户检测问题模型中，蚂蚁在每个路口只有两条路径分支可以 供选择，所以可知a v g = 2 ，则： t ：! 些( ! 二丝。! ：! 鲍坠当。!( 3 9 ) ( a u g 一1 ) 么 其中，气为算法收敛时蚂蚁在一个路口选择“正确 路径的概率， 为蚂蚁在所有路口都能正确选择路径的概率，k 为用户数，百蚴和t 血的值随 全局最优解的更新而动态变化。在本文中采用= o 8 5 【6 1 挥发系数p ，蚂蚁个数m 采用文献 6 】中的结果，p = 0 7 5 ，m = i 5 k ，k 为用户数。 ( 3 ) 改进算法的基本步骤： 初始化参数，包括用户数k ，最大循环次数，蚂蚁个数m ，挥发系 数，口和卢等参数，其中a 和卢比例为2 ：1 。 一 把匹配滤波器的输出作为初始全局最优解，计算t 一和t 曲的值。所 有路径信息量初始化为t 一 根据公式( 3 6 ) 计算各点的初始路径的启发信息。 m 只蚂蚁依据概率选择公式( 3 1 ) 。按照从用户1 到k 的顺序寻找到 m 个解。 把m 个解代入目标函数式计算适应值，求出本次迭代最优解并与全 局最优解比较，若优于全局最优解，用迭代最优解替换全局最优解。如果迭 代最优解小于全局最优解，则利用改进算法i i 进行重新选路，否则转向 根据公式( 3 7 ) 用迭代最优蚂蚁进行信息素更新。 当m 只蚂蚁寻找的m 个解相等即趋于局部最优时，采用下面公式进 行信息素轨迹的平滑化： c 沁) = t 髟( ) + 6 0 一( f ) 一t 口( ) ) ( 3 l o ) 其中，0 6 r 一，则= r 岬：若7 目 0 ，都有0 f 3 5 1 离散h o p f i e l d 网络在不同工作方式下的性能有以下一些结论1 3 6 】： 1 若权矩阵为对称阵，而且对角线元素非负，那么网络在异步工作方式 下必收敛于一稳定状态。 2 若权矩阵为对称阵，网络在同步工作方式下必收敛到一个稳定状态或 周期为2 的极限环。 3 若权矩阵为正交投影矩阵，那么在同步工作方式下必收敛到一个稳定 状态。 4 在稳定性分析中，同步方式工作的神经网络可以等价于另一个异步方 式工作的神经网络。 本文中主要应用结论1 。 h o p f i e l d 网络已经有很多成功的应用，主要有联想记忆和优化计算两种 形式。用于优化计算的基本原理是在串行工作方式下，把一组2 n 个初始状态 映射到一组稳定状态集合上去。此时，能量函数，即式( 4 4 ) 达到最小。凡是 可以把目标函数写成式( 4 4 ) 形式的优化问题，都可以用h o p f i e l d 网络求解。 需要注意的是，这样找出的极小点是一个局部极小点。 用h o p f i e l d 网络求解优化问题时一般遵循如下步骤： 1 对于待定的网络，选择一种合适的表示方法，使得神经网络的输出与 问题的解对应起来。 2 构造神经网络的能量函数，使其最小值对应问题的最优解。 3 由能量函数倒过来推出神经网络的结构，即神经元之间的连接权值和 阈值。 西南交通大学硕士研究生学位论文第3 7 页 4 由网络结构建立起网络，令其运行，那么稳定状态就是在一定条件下 问题的解答。在条件有限的情况下，由网络结构可推导出网络的运行方式， 在计算机上模拟，也能得到满意的解。 通过对h o p f i e l d 网络和最优多用户检测的研究，知道： 1 离散型神经网络在解决组合优化问题上具有独特的魅力，它通过网络 自身动态演化，能够在瞬间获得组合优化的近似解。 2 多用户检测问题最终可以归结为个组合优化问题。 基于以上两点，下面详细推导如何用h o p f i e l d 网络实现最优多用户检 测，从而得到一个次最优的多用户检测器。由于异步c d m a 实现起来太复 杂，所以多用户检测技术最有可能先在同步c d m a 中实现，本文主要研究 同步c d m a 中的多用户检测技术。根据式( 2 7 ) 和式( 2 1 0 ) ，可知 扩= a r g m一il筮x(be+i 劾7 耖一6 足幻) ( 4 6 ) ，一n t 。u ， 式中，= k ，吃，】t , r k 6 船表示第k 个匹配滤波器的输出； b = 慨，6 2 ，b k 】，b k 表示第k 个用户在【o ，t 】上传输的信息比特； s = ( 毛) 啦( 耽勺= 麻，其中毛= 影；多 r 表示实数，m f 似) 表示实数域上的k 阶矩阵； r s 是归一化相关矩阵，其元素为p 。，对角线元素为1 将式( 4 6 ) 作如下转换：b 。= 鹕m 警 2 6 贸一6 f s 足s 6 6 q + l ，一母“ = a r g m a xk一三1l如酗6 茸+ i ，一日。 么 j = 翟磐陟以幻- 6 ，l ( 4 - 7 ) 6 爿+ l ，一q l z j e 为k 阶单位阵，6 吐幻正定，所以 6 。= a 。r 。卜g 。m ，一碍i n 。l 1 26 s r 占6 6 s ， = a 。r ；g + 。m ，一u i n 。l 一三16 ( 二j 彳) 6 6 】， ( 4 8 ) 西南交通大学硕士研究生学位论文第3 8 页 易知上式中h 为对角线为0 的对称矩阵，r s 是k 个用户的互相关矩 阵；y 为传统检测器匹配滤波器的输出。y = 陟。，j ，：，y k r 由式( 4 - 4 ) 可知， h o p f i e l d 网络的能量函数为： e = 一二1v 7 1 ( t ) w v ( t ) - ，r ( f ) p ( 4 - 9 ) 对比式( 4 - 8 ) 和式( 4 9 ) ，发现它们有相同的形式，即可以用h o p f i e l d 网 络来求多用户检测的最优解。求解过程就是h o p f i e l d 网络的收敛过程。网 络的演变遵循式( 4 3 ) ，即 ( 0 ) = 厂n、 _ ( f + 1 ) = s g n l 坳v ( d qi ( 4 1 0 ) ，= 1 用h o p f i e l d 网络求解最优多用户检测，只需作如下变换： w q 。一hq n = k e j = y j 巧删= l i m v j ( i ) ( 4 1 1 ) 。 i - k 口0 网络初始状态可取 1 ，( 0 ) = z = s g n ( y j ) ，= l ，2 ，k ( 4 - 1 2 ) 4 3 蚁群算法和h o p f i e l d 神经网络的结合 4 3 1 结合的设计思想 h o p f i e l d 神经网络具有快速收敛能力，但对于系统中的反馈信息却没有 利用，往往搜素的结果陷入局部极小点。蚁群算法是通过信息素的累积和更 新而收敛于最优路径，具有分布、并行、全局收敛能力，但初期信息素匮乏、 导致算法速度慢。为了克服两种算法各自的缺陷，形成优势互补，为此把蚁 群算法和h o p f i e l d 神经网络相结合，结合的设计思想是首先采用h o p f i e l d 神 经网络能通过网络自身的动态演化，能够在瞬间获得组合优化的近优解的特 点，然后将通过h o p f i e l d 网络搜到的历史最优值作为后期用蚁群算法搜索的 初始信息素的分布，充分利用蚁群算法的正反馈机制以提高求解的效率。结 合算法的总体流程见图4 2 ： 西南交通大学硕士研究生学位论文第3 9 页 传统检测器 + 的输出初始化参数( t 等) ，根 据最优解生成信息素 初始分布 h o p fe l di ) 【：gi 一 络1优化 计算每只蚂蚁移动到下 上 一节点的概率，根据概 利用迭代优化 率公式( 3 1j 移动蚂蚁 策略进行信息 把目标函数和 素更新 h o p f i e l d 网络的 r jl 能量函数作对比 把每个结果分别带 得出网络运行所 入公式( 2 7 ) 计算目标 需的权值和阈值 函数值，找出最优解 t = t + l i i l 人 。 生成若干组最优 解 7 肇鬻劳否 灭循外伙 一 山 输出最优值 4 3 2 算法设计 图4 - 2 结合算法的总体流程 结合蚁群算法与h o p f i e l d 网络的优化算法分为两部分，首先先用h o p f i e l d 网络对用传统检测的输出结果进行优化，得到能量最小值，然后再应用改进 的蚁群算法对找出的具有能量最小值的路径进一步优化调整。结合算法的步 骤描述如下： ( 1 ) 进行h o p f i e l d 神经网络的优化过程，得出各个用户的能量最小值以 及对应的路径。 ( 2 ) 初始化蚁群最大循环代数n c ；各路径上的信息素初值r = 常数；蚂蚁 的个数m ，m 大小为用户数的1 5 倍；挥发系数p = o 7 5 。 ( 3 ) 根据( 1 ) 得到的路径，用其对应的能量最小值更新信息素的数值，以 此作为蚁群算法工作时个路径上的信息素初值。 西南交通大学硕士研究生学位论文第4 0 页 ( 4 ) m 只蚂蚁根据公式( 3 1 ) ，其中口和卢的取值也为2 ：1 ，按照从用户 1 到k 的顺序寻找到m 个解。 ( 5 ) 把m 个解代入目标函数式计算适应值，求出本次迭代最优解并与全 局最优解比较，若优于全局最优解，用迭代最优解替换全局最优解。如果迭 代最优解小于全局最优解，则利用3 4 2 节中改进算法中的第中策略进行 重新选路，否则转向( 6 ) 。 ( 6 ) 根据公式( 3 7 ) 用迭代最优蚂蚁进行信息素更新。 ( 7 1 检查是否满足终止条件，若满足则输出最优解。 4 3 3 仿真实验 考虑一个1 0 用户的同步d s c d m a 系统，采用长度为l = 3 1 ，最大互相 关为9 3 1 的扩频序列，发送的数据d a t a = 5 0 0 个，在高斯白噪声信道环境下， 对匹配滤波器检测方法( c d ) ；解相关检测方法( d e c ) ；最小均方检测方法 ( m m s e ) ；不带禁忌表但用启发信息指导选路的m m a s 算法( g m m a s ) ；蚁群 算法和h o p f i e l d 神经网络结合的算法( a c o h o p ) 进行仿真，这五种算法的 仿真结果如图4 - 3 所示： 付 a c oh o p 一。器m ”8 - - 4 - - - d e c m m s e o，23 4 56 7891 0 信嗓比s n r b 图4 - 3 五种算法中用户1 的误码率随信噪比的变化曲线 - ， ， - 一 - - ” 一 z山m碍露菅 西南交通大学硕士研究生学位论文第4 1 页 表4 - 1 五种算法的运行时间比较( 单位，秒) 算法c dd e cm m s eg m m a sa c o h o p 运行时间9 1 7 1 91 1 1 7 1 91 4 9 5 3 15 9 2 3 5 9 4 4 9 1 6 5 6 3 图4 - 3 是用五种不同的算法对用户1 误码率随信噪比变化的仿真结果， 从图4 - 3 中可以明显的看出虽下面一条粉红色曲线所代表的蚁群算法和 h o p 丘e l d 神经网络结合的算法( a c o - h o p ) 的效果最好。表4 - 1 是相对应的 每种算法在发送数据相同的情况下每种算法实现所需要的时间，从表4 - 1 中 可以看出a c o h o p 算法不仅可以降低误码率，而且找到最优解的速度也比 较快。h o p f i e l d 神经网络是一个动态回归网络，它可以很快的稳定在能量极 小点，得到需要的最优值。 从上面的分析可以看出蚁群算法和h o p f i e l d 神经网络结合的算法把 h o p f i e l d 神经网络具有快速收敛能力和蚁群算法所具有的分布、并行、全局 收敛能力的优点充分的利用起来了。 在第三章中改进的算法虽然取得了很好的效果但也存在随用户数的增加 误码率会受到很大影响的不足，在图4 - 4 中，对a c o h o p 算法随用户数量 的增加产生的误码率进行仿真，可以看到由1 5 个用户到2 0 个用户之间，误 码率曲线已趋向水平，而不像在第三章中，g m m a s 算法的误码率曲线一直 上升。可见，a c o h o p 算法受用户数影响并不大，从而弥补了g m m a s 算 法的不足。t 矿 一一一争- 一一一卜：蘸g m