（计算机应用技术专业论文）基于禁忌搜索的多用户检测方法.pdf

曩士曩t 格文，量于募暮蔓曲，甩户格谢才盛 基于禁忌搜索的多用户检测方法1 学科专业：计算机应用技术研究方向：智能信号处理 指导老师：刘光远教授研究生：温万惠( 2 0 0 2 5 0 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 系统中， 通信信道同时被多个用户共享，当用户数较多时，多址于扰( m u l t i p l ea c c e s s i n t e r f e r e n c e ) 会使系统性能恶化。相关资料 6 】表明，多址干扰已经成为制约c d m a 系统进一步发展的瓶颈，因此，在未来通信系统的开发中，多用户检测( m u l t i - u s e r d e t e c t i o n ) 技术被视为一门关键技术。 计算智能( c o m p u t a t i o n a li n t e l l i g e n c e ) 方法是近几年提出并发展起来的新型 计算方法，是多门学科相互交叉和渗透的方法论，其思想和内容涉及数学、物理 学、生物进化、人工智能、神经科学和统计力学等方面，为解决复杂问题提供了 新的思路和手段。禁忌搜索算法是计算智能方法的一种，它模拟人类智力过程， 通过引入一个灵活的存储记忆结构和相应的禁忌准则来避免迂回搜索，进而保证 多样化的有效搜索，最终实现全局优化。这一基本算法思想最早是由g l o v e r 于 1 9 8 6 年提出的，它是对局部领域搜索的一种扩展，实现这一扩展的是它的存储 记忆和禁忌准则。另一种计算智能方法是群智能优化方法，它通过粒子之间的合 作寻优来取得好的优化结果。 多用户检测问题可以转化为一个组合优化问题，因此可将计算智能的优化机 理应用于多用户检测的求解过程。本文研究的重点就是基于禁忌搜索的多用户检 测技术，针对禁忌搜索方法解决多用户检测这个问题进行了数值仿真、对比分析 和讨论。 本文受教育部科学技术重点项目( 1 0 4 2 6 2 ) 和重庆市科委基金项目( 2 0 0 3 - - 7 8 8 1 ) 的资助。 曩士掌矗* 文，t 于墓善量，用户澍幸 下面是本文各部分主要内容的摘要： 第一部分主要介绍了多用户检测技术的研究现状，研究意义以及计算智能在 多用户检测中的应用，并对论文所作的工作以及论文内容的安排作了说明。 第二部分介绍了同步和异步c d m a 通信系统模型，多用户检测的性能测度 和最佳多用户检测方法，分析了次佳多用户检测方法的意义，最后介绍了群智能 优化方法、禁忌搜索算法及其与多用户检测的结合点。 第三部分讨论了一种可变禁忌长度多用户检测方法，提出了一种基于自适应 集中性和多样性搜索策略的禁忌搜索算法，并将其用于多用户检测。 第四部分提出并讨论了两种基于群智能禁忌搜索的智能优化算法，并将其用 于多用户检测以检验其全局寻优能力 第五部分对第三、四部分中提出的方法进行了数值仿真，从检测性能、抗远 近效应能力和计算复杂度三个方面进行了比较和分析。 第六部分是对全文的总结及对将来研究工作的展望。 总之，本文所做的工作及取得的研究成果可归纳为以下几个方面： ( 1 ) 对响应禁忌搜索进行了研究，并提出一种可变禁忌长度搜索算法，使 之更适合多用户检测这个问题。 ( 2 ) 对禁忌搜索算法进行改进，提出了一种自适应禁忌搜索算法，较好地 解决了集中性搜索和多样性搜索的矛盾，增强了禁忌搜索算法的全局寻优能力。 ( 3 ) 将群智能思想与禁忌搜索方法相结合，提出了一种新的智能优化方法： 群智能禁忌搜索方法，该方法结合粒子群优化和禁忌搜索的优点，使求解问题的 过程更有效和高效地进行。 ( 4 ) 针对传统多用户检测方法及最佳多用户检测的不足，将上述自适应禁 忌搜索算法及群智能禁忌搜索方法用于多用户检测中，取得了良好的检测性能和 计算效能。 通过本文的研究可以看出，基于禁忌搜索的多用户检测方法在检测性能上比 传统的多用户检测方法优越，在计算复杂度上比最佳多用户检测更易于工程实 现。本文提出的群智能自适应禁忌搜索算法综合了几种优化算法的优点，不但在 多用户检测问题中得到了很好的检测性能，而且具有一定的普遍适用性，可以用 于求解其它组合优化问题。 关键词：码分多址，多用户检测，多址干扰，远近效应，计算智能，禁忌搜 索，集中性和多样性搜索，群智能，计算复杂度 曩士毒怔静文? 基于蕞毒垃曲，焉户捌帝盛 t a b us e a r c hb a s e dm u l t i u s e rd e t e c t i o ni nc d m a m a j o r c o m p u t e ra p p l i c a t i o nt e c h n i q u e s u p e r v i s o r ：p r o f l i ug u a n g y u a n d i r e c t i o n ：i n t e l l i g e n ts i g n a lp l o c e s s i n g a u t h o r ：w e nw a n h u i ( 2 0 0 2 5 0 1 ) a b s t r a c t c o d e d i v i s i o nm u l t i p l ea c c e s s ( c d m a ) i sk n o w na st h em a i nt e c h n i q u eo ft h e t h i r dg e n e r a t i o na n df u t u r em o b i l ec o m m u n i c a t i o n s y s t e m s r e g a r d l e s so fi t sb e n e f i t s o nl a r g ec a p a c i t y , s o ns w i t c h h i g h - q u a l i t yt o n ea n de x c e l l e n ts e c r e c yp e r f o r m a n c e c d m am o b i l ec o m m u n i c a t i o ns y s t e m sa 托i n t e r f e r e n c e l i m i t e ds y s t e m s w h e n m u l t i - u s e r ss h a l et h et r a n s m i s s i o n c h a n n e l ，t h ec o m m u n i c a t i o np e r f o r m a n c eo f c d m a s y s t e m sd e c a y f o r t h em 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 ) a ne f f i c i e n tm e t h o d s u p p r e s s i n gm a ii sm u l t i - u s e rd e t e c t i o n ( m u d ) w h i c hv i e w sm a ia su s e f u lr e s o u r c e a n dm a k e sf u l lu s eo ft h e r e l a t i o n s h i pb e t w e e nu s e r st oi n c r e a s et h ed e t e c t i o n p e r f o r m 如e n t h u s ，t h em u di so n eo ft h ek e yt e c h n i q u e si nf u t u r ec d m a c o m m u n i c a t i o ns y s t e m s c o m p u t a t i o n a li n t e l l i g e n c e ( c i ) i san o v e lm e t h o d o l o g yf o ri n f o r m a t i o n p r o c e s s i n g ，w h i c h 、棚p r o p o s e da n ds t u d i e dw i d e l yi nr e c e n ty e a r s t a b us e a r c hi sa c o m p u t a t i o n a li n t e l l i g e n c em e t h o df o rg l o b a lo p 幽n i z i n g , w h i c ht r i e st oo b t a i nt h e g l o b a lo p t i m u mb yi t sm e m o r ys t r u c t u r ea n dt a b us t r a t e g i e s a n o t h e rc im e t h o di s s w a r mo p t i m i z i n g , w h i c hi n c l i n e st ot h e 羽o b a lo p t i m u mb yt h ec o o p e r a t i o no f p a r t i c l e si nt h es w a m i s i n c et h ep r o b l e mo fm u dc a nb et r a n s f o r m e di n t oac o m b i n a t o r i a lo p t i m i z a t i o n p m b l e m ，t h es t r a t e g i e so fc if o ro p t i m i z a t i o nc 壮b ea p p l i e di nm u d t h i st h e s i s f o c u s e si t sw o r ko nt a b u - s e a r c hb a s e dm u l t i u s e rd e t e c t i o n a na d a p t i v et a b us e a r c h a l g o r i t h ma n dn e wt e c h n i q u e sb a s e do us w a r mi n t e l l i g e n c ea n dt a b us e a r c hw e r e p r o p o s e da n da p p l i e di nm u d 一士季t 静文? t 于善善麓毒崎，甩户 一方盛 t h ec o n t e n t so f e a c hp a r ti nt h ed i s s e r t a t i o na r ea sf o l l o w s ： p a r t1m a i n l yi n t r o d u c e st h ea c t u a l i t i e so fm u d t e c h n i q u e s ，t h es e n s eo fm u d 砖s e a r c ha n dt h ep o s s i b i l i t yt oa p p l yc ii nm u d ab r i e fd e s c r i p t i o nf o rt h es t r u c t u r o o f t h ep a p e ri sa l s oi nt h i sp a r t p a r t2g i v e st h em o d e lo fs y n c h r o n o u sa n d a s y n c h r o n o u sm u l t i - u s e rd e t e c t i o ni n c d m as y s t e ma n dt h em o d e lo fo p t i m a ld e t e c t i o n , f o l l o w e db yad i s c u s s i o no nt h e c o n j u n c t i o np o i n to f s w a r mi n t e l l i g e n c e ，t a b us e a r c ha n dm u d p a r t3a n dp a r t4h a v ep r o p o s e da n dd i s c u s s e da na d a p t i v et a b us e a r c ha n dt w o n e wo p t i m i z i n gm e t h o d sb a s e do ns w a r mi n t e l l i g e n c ea n dt a b us e a r c h p a r t5i st h ee x p e r i m e n t a ld a ma n dc o r r e s p o n d i n ga n a l y s i s p a r t6s u m m a r i z e st h ew o r ko ft h i sd i s s e r t a t i o na n dg i v e st h ep r o s p e c tf o rf u t u r e r e s e a r c h i naw o r d ，t h er e s e a r c hw o r kf i n i s h e di nt h i sp a p e rc a nb es u m m e du pi n t of o u r a s p e c t s ： f i r s t l y , r e a c t i v et a b us e a r c h ( r t s ) w a sa d a p t e df o rm u l t i - u s e rd e t e c t i o n s e c o n d l y , t a b us e a r c hw a si m p r o v e db yi n s e r t i n ga na d a p t i v ei n t e n s i f i c a t i o na n d d i v e r s i f i c a t i o ns t r a t e g yi n t ot h eb a s i ct a b us e a r c hm e t h o d t h i r d l y , t h es w - n li n t e l l i g e n c ea n dt a b us e a r c hw e r ec o m b i n e dt of o r man e w i n t e l l i g e n c eo p t i m i z a t i o na p p r o a c h , t h es w a r m - a d a p t i v et a b us e a r c hf s - a t s ) t h e n o v e la p p r o a c hr e f i n e dt h eb e n e f i t so fs w a r mi n t e l l i g e n c ea n dt a b us e a r c h ，a n dm u c h h a t t e rs e a r c hp e r f o r m a n c ew a so b t a i n e db e c a u s eo fi t se f f e c t i v ea n de f f i c i e n ts e a r c h s t r a t e g i e s a tl a s t , a l lt h e s ei m p r o v e do p t i m i z a t i o n t e c h n i q u ew e r ea p p l i e di nm u d ， e x c e l l e n td e t e c t i o np e r f o r m a n c ea sw e l la sl o wc o m p u t a t i o n a lc o m p l e x i t yw e r e a c q u i r e d k e yw o r d s ：c o d e - d i v i s i o nm u l t i p l ea c c e s s ，m u l t i = u s e rd e t e c t i o n ，m u l t i p l ea c c e s s i n t e r f e r e n c e ，n e a r - f a re f f e c t , c o m p u t a t i o n a li n t e l l i g e n c e , t a b us e a r c h , i n t e n s i f i c a t i o na n dd i v e r s i f i c a t i o ns e a r c h ，s w a r m i n t e l l i g e n c e ， c o m p u t a t i o n a lc o m p l e x i t y 4 嘎士量佳囊 文? 亍善暑搜蠢昔，用户嘲方盛 第一章引言 码分多址( c d m a ) 移动通信系统是一种先进的移动通信系统，c d m a 技 术已成为第三代以及将来移动通信的主流技术。它具有大容量、软切换、清晰 话音质量和良好的保密性能等优点，能在一定程度上缓和有限频带与无限用户 需求之间的矛盾。但c d m a 系统和其它移动通信系统一样，也是一种受干扰限 制的系统。 在c d m a 系统中，干扰可以大致分为三种类型：加性白噪声干扰、多径干 扰和多址干扰。当同时通信的用户数较多时，多址干扰( m a d 成为最主要的 干扰。多址干扰是由于系统中多个用户共享信道，由用户的扩频序列之间的非 零相关系数引起的。当多址干扰严重时，系统的性能明显恶化。因此，抑制多 址干扰成为c d m a 移动通信系统的一项主要任务。 多址干扰也称为多用户干扰，因此，多址干扰的抑制问题也就是多用户检测 问题，而多用户检测技术被认为是c d m a 通信系统的关键技术之一。多用户检 测的基本思想是：通过充分利用同时通信的用户的信息( 信号到达时间、使用 的扩频序列和信号幅度等) 来消除多址干扰，进而提高信号的稳定性，它不再 像传统检测那样忽略系统中其它用户的存在( 即把其它用户仅视为干扰) 。 自从s v e r d u 在文献【l 】中提出具有奠基意义的最佳多用户检测模型以来， 关于多用户检测问题的研究一直是移动通信领域中的一个研究热点。众多学者 积极投身于这一问题的研究中，进行了卓有成效的工作，目的是找出一种能够 有效解决多址干扰抑制问题的方法。 1 1 多用户检测技术发展概况及现状 s v c r d u 在文献【1 】、【2 】、【3 】中指出：多址干扰是一种含有有用信息的可用 资源。而传统的c d m a 多用户检测器把多址干扰视为一种噪声干扰加以滤除， 没有充分利用多址干扰的可用信息。因此s v e r d u 提出了c d m a 最佳多用户检 测理论，这一理论研究成果在国际上被公认为c d m a 多用户检测理论发展史上 的一个里程碑，奠定了c d m a 多用户检测的理论基础。 v e r d u 的最佳多用户检测方法是基于最大似然序列估计的方法，它在理论上 可以完全克服多址干扰，但由于其算法的计算复杂度随用户数的增多呈指数倍 曩士学位论文? 亍辱置哥，甩户警一幸叠 增长，难以为工程实现所接受。尽管如此，最佳多用户检测理论仍然引起了国 内外众多学者的广泛关注，他们从不同角度来讨论c d m a 多用户检测问题。许 多国际著名刊物每年都刊登很多关于多用户检测方法的学术论文，国际会议也 对此问题进行了专题讨论，目的是寻找一种检测性能上比较接近最佳多用户检 测方法的性能。而计算复杂度又比较合理，并且易于实现的次佳多用户检测方 法。目前，关于多用户检测问题的讨论还在继续中，学者们的主要研究工作大 体上可从如下几个方面来认识： 首先，学者们力求在检测模型上向实际情况步步逼近。这主要指信道模型 从简单的加性高斯白噪声( a w g n ) 信道向实际信道的逼近v e r d u 的最佳多 用户检测是在简单的a w g n 背景下提出的，对于这类最简单的恒参信道，利 用已知扩频码的结构和统计信息比较容易，其实现相对来说也比较简单。把信 道从a w g n 信道扩展到平坦瑞利单径衰落信道，再扩展到多径衰落信道，直 至实际环境的时变多径快衰落信道，在这种情况下，信道是变参量的信道，已 知扩频码的结构信息由于信道衰落、多径时延等因素而被破坏，要想实时求得 这些待求的“已知”结构信息，就必须引入信道估计理论与技术。由此可知， 这种模型逼近的难点在于降低实现的复杂度。 对于模型逼近这一方面的研究，自适应检测是己知的一种较好的检测方法。 它可以用比较短的滤波器处理固定相关器的输出，滤波器可望较快收敛，其缺 点是要求有一组同步的相关器，而且当信道响应突然变化或出现新的同信道用 户( 这两种情况在实际通信中是经常发生的) 时，训练序列要重新发送。目前 许多学者致力于盲自适应检测的研究，它可以避免反复发送训练序列造成的频 谱资源浪费，而且只需知道期望用户的特征波形和定时信息，因此需要预知的 “信息”比较少。盲自适应检测在信道中同时通信的用户数可变的情况下具有 很重要的现实意义，而收敛速度慢和运算量大则是这一方法有待改进的地方。 其次，另一种研究方向是力求从理论上的最佳结构逐步向工程上的次佳结 构的发展。 v e r d u 的最大似然最佳多用户检测思想，利用v i t e r b i 最大似然算法可将实 现的复杂度降到o ( 2 ) ，其中x 为系统中同时通信的用户数，但它仍然具有 指数增长的复杂度，是一个n p 难问题，实际工程中无法接受如此增长的检测 嘎士学位论文，于囊暑蔓曲，甩户各州方凶 时延。为了寻找具有实际应用价值的方案，研究者们将目光从追求最佳转向次 佳，使得检测性能与计算复杂度之间取得一个合理的折衷。 另一方面，多用户检测与其他技术的结合，实现联合优化也是一个重要的 发展方向。目前研究较多的有：多用户检测与r , a k o 接收机结合的空时二维最佳 检测；多用户检测与智能天线结合的空时最佳检测：多用户检测与计算优化方 法结合的检测技术等。 1 - 2 多用户检测技术的研究意义【6 】 c d m a 系统中的主要干扰类型有：加性白噪声，多径干扰和多址干扰。加 性白噪声是所有通信系统中都存在的一类可加性噪声，一般服从高斯分布且功 率谱是平坦的。多径干扰主要是由电波的多径传输在接收端引起的接收信号的 畸变，一般称为符号问干扰或码间干扰。多址干扰是由同一个小区同时通信的 多个用户扩频码的非正交性引起的。在码分多址中，多个同时通信的用户占用 同一时隙，同一频带，区分它们的是各自不同的扩频码。如果各用户的扩频码 理想正交，则不会出现多址干扰。然而由于信道的移动性和各用户信号到达基 站的不一致，在接收端扩频码不可能完全正交。扩频码不为零的互相关函数使 得多个用户同时通信时必然产生多址干扰。 当小区中同时通信的用户数较多时，多址干扰是最主要的干扰。克服多址 干扰可以通过在发送端使用互相关为零的扩频码( 对于同步码分多址方式) 或 互相关函数很小的扩频码( 对于异步码分多址方式) ，也可以通过严格的功率控 制使距离基站不同距离的用户到达基站接收点的功率或信噪比平衡一致来克服 远近效应。 然而正如上文所分析的，扩频码的正交性在实际通信环境中会被破坏，通 过设计好的扩频码只能在一定程度上减小多址干扰的影响。而功率控制也只能 尽可能减少多址干扰的影响，不能从根本上消除多址干扰。 另外两种抑制多址干扰的方法是空间滤波技术和多用户检测技术。空间滤 波的基本思想是：将小区内的多址干扰按区间区域将大区划成小区，以达到在 每个小区内减少多用户干扰影响的目的。多用户检测技术则是引用信息论并通 过严格的理论分析后提出的一种新型抗多址干扰技术，既可以抑制多址干扰， 又可以抵抗远近效应，进而增大系统的容量。 疆士，t 静文? 亍摹暑冀幸酋j 甩1 - 警一 盛 由此可见，对多用户检测技术的深入研究具有重要的现实意义 1 3 计算智能及其在多用户检测中的应用 计算智能( c o m p u t a t i o n a li n t e l l i g e n c e ) 方法是近几年提出并发展起来的新 型计算方法，是多门学科相互交叉和渗透的方法论，其思想和内容涉及数学、 物理学、生物进化、人工智能、神经科学和统计力学等方面，为解决复杂问题 提供了新的思路和手段。虽然对计算智能精确定义不容易，但公认的一种粗略 定义可以这样认为：凡是仿照自然法则构造的计算，均可称为计算智能，有时 也称为软计算( s o f tc o m p u t i n g ) 。如模拟人类智力过程的禁忌搜索算法、模仿 生物界种群生存法则的粒子群优化算法等。均属此类这些方法协同地通过“拟 物”与“仿生”以解决实际工程问题。随着对计算智能方法研究的深入，最近 国际上出现了另一种提法：自然计算o q a t u r a lc o m p u t a t i o n ) 。自然计算是对一些 计算系统的研究，这些计算系统将大量来源于自然系统( 包括生物系统、社会生 态系统和物理系统) 的方法和灵感应用在大型、复杂和动态系统的处理中。 禁忌搜索算法通过引入一个灵活的存储记忆结构和相应的禁忌准则来避免 迂回搜索，进而保证多样化的有效搜索以最终实现全局优化。这一基本算法思 想最早是由g l o v e r 于1 9 8 6 年提出的【7 】，它是对局部领域搜索的一种扩展，实 现这一扩展的正是它的存储记忆和禁忌准则。 粒子群优化算法是近几年提出的一种新的寻优方法【1 1 】。它的特点是群中的 个体的寻优行为受两个“最优解”( 个体最优和群体最优) 的影响。通过在个体 之间传送优良解信息，使个体的寻优更有效。个体之间的寻优是相对独立的， 有利于并行计算。 v e r d u 在他的著作中已指出，最佳多用户检测问题是一个n p 难问题。禁忌 搜索和粒子群优化算法过去几年内被用于求解n p 难问题，在诸如旅行商问题 等很多领域已取得了显著的成绩。因此如果能把多用户检测问题转化为一个组 合优化问题，则无疑找到了计算智能方法与多用户检测的结合点，前人的工作 已经找到了这个结合点 2 1 】。 1 4 本文的具体工作及内容安排 本文的具体工作包括： 啧士学t 论文，量亍善毒簋夤曲，用户格一毒矗 ( 1 ) 改进已有的一种禁忌搜索方法( 响应禁忌搜索) 使之适用于多用户检 测，得到了较好的检测性能。 c 2 ) 提出一种自适应禁忌搜索方法，通过自适应的集中性和多样性搜索使 这种禁忌搜索方法的全局寻优能力增强，用于多用户检测得到了良好的检测性 能。 ( 3 ) 为进一步提高禁忌搜索算法的搜索性能，将粒子群优化算法中的群智 能思想引入到禁忌搜索中，为构造以禁忌搜索为主豹混合算法的研究提供了新 的思路。 ( 4 ) 将自适应禁忌搜索与群智能思想结合，提出了一种新的智能优化算法 ( 群智能自适应禁忌搜索算法) ，用于多用户检测得到了很好的检测性能 与具体工作相对应，本文的内容安排如下： 第一章为引言部分，主要介绍了多用户检测技术的研究现状，研究意义以 及计算智能在多用户检测中的应用，并对论文所作的工作以及论文内容的安排 作了说明。第二章介绍了同步和异步c d m a 通信系统模型，多用户检测的性能 测度和最佳多用户检测方法，分析了研究次佳多用户检测方法的意义，最后介 绍了禁忌搜索算法、群智能优化方法以及它们与多用户检测的结合点。第三章 讨论了一种可变禁忌长度多用户检测方法。并提出了一种自适应禁忌搜索算法， 将其用于多用户检测。第四章提出并讨论了两种基于群智能禁忌搜索的智能优 化算法，并将其用于多用户检测，给出了适合于多用户检测的算法流程。第五 章是对前两章所讨论的方法的数值仿真，对各仿真结果作了必要的说明和分析， 并用旅行商问题( t s p ) 对群智能自适应禁忌搜索算法的有效性进行了检验。第六 章是对全文的总结以及对今后研究工作的展望。 曩士毒t 备文? 量干善喜奠士竹，用户* 一十盛 第二章多用户检测以及两种计算智能方法的 基本原理 前一章中已经述及多用户检测在c d m a 移动通信系统中的重要地位，并对 禁忌搜索和粒子群优化算法作了概要介绍。为了更好地在后续章节中阐述本文 的研究工作，本章将介绍c d m a 通信系统的等效数学模型、多用户检测的性能 测度、最佳多用户检测的必要推导过程、次佳多用户检测器的分类以及蔡忌搜 索和粒子群优化算法的基本思想。 2 1 c d m a 通信系统的等效数学模型【2 3 】 理想情况下，码分多址要求各用户信号的特征波形的互相关( 或内积) 为 零。实际中，常用特征波形之间的相互干扰足够小这一要求取代特征波形正交 的要求。这样做的目的是使得用户特征波形的互相关相对于特征波形能量足够 小，以便正确判决出期望用户发送的数据比特。 为简化分析，首先考虑一个k 个用户的同步d s ，c d m a 系统，采用b p s k 调制，经高斯白噪声信道进行数据传送的基本数学模型由下式给出： ，( ，) = a t 以( f ) + o n ( t ) ，t 【o ，r 】 ( 2 1 1 ) t 。l 上式中，4 是用户k 的接收信号幅值，r 为码元间隔，以( r ) 是分配给第k 个用 户的确定性特征波形，它具有单位能量，即i p 。1 1 2 = fs 。( o a t = l ，而 以 一l ，+ 1 ) 表示第k 个用户发射的比特数据， ( ，) 是具有单位功率谱密度的加 性高斯白噪声，( f ) 是接收机接收到的信号。 以三个用户的情况为例，假定各用户的比特数据的时间定时存在偏移 靠抟= 1 , 2 ，3 ) ，各用户的数据速率相同，均为1 t ( 即t 为比特间隔) ，如图2 。1 1 所示。 不失一般性，假定每个用户发送的数据包的长度等于2 肘+ 1 。将式( 2 1 1 ) 推广到非同步情况，得到非同步c d m a 系统的基本数学模型如下： 嘎士季位诱- 文，于t 暑簟童曲，矗产 一毒盛 mf ，( ，) = a i 以【弧( ，i t f i ) + 硎( ，) ( 2 1 2 ) t 一mk = l 当接收端收到连续时间波形，( ，) 后，先要对连续信号离散化，得到离散时间 信号y ( f ) ，常用的方法是让接收信号先通过一组匹配滤波器，然后对各路匹配 滤波器的输出采样，如图2 1 2 所示 r 用户1 f ， rf 胪2 寸j j 土l f 2 r 肿3 弛- l j 三l l ，“) 图2 i 1 用偏移描述非同步 y 。( f ) y 2 ( f ) y r ( f ) 图2 1 2 匹配滤波器 每个滤波器与一个不同用户的特征波形匹配。在同步的情况下，匹配滤波 器组的输出为 ( r ) = er ( u ) s y l r ( u ) s l ( f u ) d u ( r ) = i - ( f m( 2 1 3 ) y f ( f ) 2j ：r ( u ) s f ( 卜u ) d u 曩士学位静文? 千t 暑美的，甩户论鲥幸磕 式中，s 。( f ) 是第k 个用户的扩频波形，而，( f ) 是式( 2 1 1 ) 所示的接收机接收 到的信号。假定发送数据以等概率取一l 或+ 1 ，将式( 2 1 1 ) 代入式( 2 1 3 ) ，易知 第k 个匹配滤波器的离散对闻输出y 。( f ) 可以表示成以下形式； n ( f ) = a i k ( i ) + ，屯( j ) 户且+ h 。 ( 2 1 4 ) j - l , j c k 式中，儿d 表示第七个匹配滤波器的第i 个采样输出，k = l 2 p j k 是第j 个用户与第k 个用户特征波形的互相关，定义为： p p = rs ，( r ) 屯( o a t ( 2 1 5 ) 而 ”t = 盯f t i ( f ) j i ( t ) d t ( 2 1 6 ) 为高斯随机过程。其均值为零，方差为仃2 。 若令： j = 【毛，】1 ，a = d _ f a g a l ，以】( 2 1 7 ) 并记归一化的互相关矩阵： r = e s s 7 ) 叫以】鼻；。 ( 2 1 8 ) 其对角线元素风= l ，则匹配滤波器组的采样输出可以用向量表示为： y = r a b + 行( 2 1 9 ) 式中，y - 【) - l ，y f 】7 ，疗= 【疗i ，】7 ，b = b l ，b r 】7 。对于向量一， e n n 7 ) = 仃2 胄( 2 1 1 0 ) 定义2 1 1 ( 充分统计差)若假设检验问题的统计量包含了原观测值与 最佳决策有关的所有信息，则称之为充分统计量。 由式( 2 1 3 ) 知，y 是解调b 的充分统计量。多用户检测可以说就是设计处 理这些充分统计量的方法，以达到在某种代价函数最小化的意义下解调出b 。 对于非同步c d m a 系统，同理可得其离散时间数学模型，即匹配滤波器组 的输出表达式： 曩士学位静 ，亍t 曲，甩户一幸叠 n 【司= 4 以( f ) + 4 0 【f + l 】p 。( f j 一1 ) + 4 屯【j 】卢k ( 一o ) + i 娃i n a j b j i p ( r j f i ) + ，b j i 1 p l k ( r , 一f j ) + 哪， k = l 一k p tj “ ( 2 1 1 1 ) k i ( 2 1 1 2 ) 七 xe ( x ) 的步骤叫做一个移动( m o v e ) 。 t s 涉及到初始解、邻域、禁忌表、禁忌长度、候选集、藐视准则等基本参 数，所有这参数的选取都将对搜索结果产生很大影响。因此，对t s 算法的应 用的个关键就是适当地设置这些基本参数。 曩士学t 静文，量子善毒蔓蠢的，用户格州方基 简单的t s 算法步骤可描述如下： s t e p i 给定算法参数，产生初始解x ，置禁忌表为空； s t e p 2 判断算法终止条件是否满足，若是，则结束算法并输出结果；否则； 继续以下步骤： s t e p 3 利用当前解x 的邻域函数产生其所有( 或若干) 邻域解，并从中确 定若干候选解，组成候选集 s t e p 4 对候选解判断藐视条件是否满足，若是，则用满足藐视准则的最佳 状态y 替代工成为新的当前解，并用与y 对应的禁忌对象替换最早进入禁忌表 的禁忌对象，同时用y 替换“当前最优”状态，然后转s t e p 6 t 否则，继续以 下步骤： s t e p 5 判断候选解对应的各对象的禁忌属性，选择候选集中非禁忌对象对 应的最佳状态为新的当前解，同时用与之对应的禁忌对象替换最早进入禁忌表 的禁忌对象元素。 s t e p 6 转到s t e p 2 。 一般而言，要设计一个禁忌搜索算法，需要确定算法的以下环节： ( 1 ) 初始解 多数情况下，随机产生初始解，对于某一类问题而言，也可用诸如插入法 等特定算法产生高质量的初始解。 ( 2 ) 邻域 邻域的生成依据具体问题选择相应法则。 ( 3 ) 适配值函数 适配值函数用于对搜索状态的评价，进而结合禁忌准则和藐视准则来选取 新的当前状态。一般用目标函数直接作为适配值函数，这是最为广泛也是容易 的做法。也可用目标函数的任何变形，或采用反映问题目标的某些特征值作为 适配值函数。选取何种值函数要视具体问题而定。 ( 4 ) 禁忌对象 禁忌对象就是被置入禁忌表中的元素，禁忌的目的是为了尽量避免迂回搜 索并且多搜索一些有效的解空间。一般来说，禁忌对象的选取有三种方法：以 状态本身或其变化作为禁忌对象；以状态分量的变化作为禁忌对象；以适配值 1 4 曩士学位格文- 量于鼻暑奠砖，用户警剐者叠 或其变化作为禁忌对象。选取何种禁忌对象也要视具体问题而定。 ( 5 ) 禁忌长度 禁忌长度可以是固定不变的，也可以是动态变化的。大量研究表明，禁忌 长度的动态设置方式比静态方式具有更好的性能。但是，如果算法有其它的策 略协调好集中性搜索和多样性搜索的关系，则另当别论，这正是本文研究的工 作之一。 ( 6 ) 候选集 候选集在当前状态的邻域中择优选取。这里的择优指所选的解在适配值、 搜索方向等某一方面是优良的。当邻域空间比较大时，使用候选集可以提高算 法的搜索效率。 ( 7 ) 藐视准则 藐视准则的应用使得某些状态解禁，以实现更高效的优化性能。常用的藐 视准则的方式有：基于适配值的准则；基于搜索方向的准则；基于最小错误的 准则：基于影响力的准则。 ( 8 ) 终止准则 常用的终止方法有：给定最大迭代步数，不管搜索结果如何，只要达到最 大迭代步数则算法终止；设定某个对象的最大禁忌频率，满足条件后算法终止； 设定适配值的偏离程度等。 在文献【l o 】中，f r e dg l o v e r 和s a mh a n a t i 给出了基于近因记忆( r e c e n c y m e m o r y ) 和频率记忆( f r e q u e n c ym e m o r y ) 的几种禁忌搜索算法有限收敛( f i n i t e c o n v e r g e n c e ) 的数学证明。近因记忆与频率记忆的不同仅在于它们对应算法的邻 域结构是否对称。这篇文献第一次给出了基于以上两种记忆形式的禁忌搜索的 明确界限。对这些禁忌搜索算法的有限收敛性的证明是把它们与一些“随机” 算法，比如模拟退火( 原文为a n n e a l i n g ) 区分开来的重要标志。详细的证明过程 参见文献 1 0 3 的第一部分至第三部分( s e c t i o n1 - s e c t i o n3 ) 。 2 5 2 粒子群优化的基本思想 粒子群优化方法是从最初的对一个简化的群体模型进行模拟的基础上发展 起来的，它基于两个主要的方法，最明显的是它与人工生命的紧密联系，其次 是它与进化计算的密切联系。 嘎士量t 凳文，量亍善善麓壹曲，用户格洲方浊 一些科学家用计算机模拟鸟群和鱼群的运动，发现群体内某一局部的运动 变化可能导致整个群体运动的不可预测的变化。他们用“近邻速度匹配” ( n e a r e s t - n e i g h b o r v e l o c i t ym a t c h i n g ) 和“狂热”( c r a z i n e s s ) 来定义群体状态的 调整，前者使整个群体趋于同向，无变化的运动状态，后者则使群体内部产生 扰动，导致群体状态的改变。群体就在这两个因素的共同作用下呈现一种规则 的、优雅的但又不可预测的状态。 当这些研究成果被最终发展为一种优化方法以后，“近邻速度匹配”和“狂 热”的概念被发展为“群体最优”( g l o b a lb e s t ) 和“个体最优”( 1 0 c a lb e s t ) ( 为 避免与禁忌搜索中的全局和局部最优混淆，在这里作如上翻译) 的概念，“鸟群” 和“鱼群”等人工生命也被统称为“粒子群”。粒子群在群体最优和个体最优的 共同作用下搜索问题的最优解。个体最优是个体对自己搜索经历的自觉记忆， 群体最优从概念上说则类似于公众知识，或群体标准，所有的个体都趋向于这 个标准。因此，个体状态的调整实际上受两个因素的影响，即个体经历的最优 以及群体标准的最优。这两个最优对个体状态的影响程度的比例关系将决定个 体在局部的寻优和向更广的解空间探索之间的关系( 在禁忌搜索中，把这个叫 做集中性搜索与多样性搜索的关系) 。如果这个比例不当，那么群体将表现为限 入局部最优或每个粒子孤立地漫无目的的低效搜索。 j a m e sk e n n e d y 和r u s s e l le b e r h a r t 在他们的论文p a r t i c l es w a r m o p t i m i z a t i o n 中给出了粒子群算法的几种数学表达式，但是由于个体最优和群 体最优的影响比例难以很好地确定，因此这几种数学表达式并不能很好地描述 粒子群算法。虽然如此，他们总结的关于群智能的五个原则却是可以借鉴的： 首先是“p r o x i m i t y ”原则。即粒子应能够进行简单的空间和时间上的计算。 第二是“q u a l i t y ”原则，即粒子应能够对环境中的质量因素作出反应。在寻 找问题的最优解的过程中，粒子对解空间中解的质量好坏应能够判别。 第三是“d i v e r s er e s p o n s e ”原则，即粒子不应把它的活动限制在过于狭小的 空间中。这就要求算法要使搜索过程具有一定的多样性。 第四是“s t a b i l i t y ”原则，7 即在环境变化时，粒子不应总是改变它的行为模 式。在寻优过程中，粒子的寻优模式不应总是随着解空间的变化而变化，要有 一定的稳定性； 1 6 嘎士学位蔷文，量亍摹暑置琦，用户籍砸幸盛 第五是“a d a p t i v e ”原则，即当计算代价值得的时候，粒子应能够改变它的 行为模式。 b a r r y & s e c m s t 和g a r yb l a m o n t 在他们的论文( v i s u a l i f i n gp a r t i c l es w a r m o p t i m i z a t i o n