（计算机应用技术专业论文）蜂窝网络中信道分配及多用户检测的免疫算法.pdf

硕十学位论文 摘要 蜂窝概念的提出在无线移动通信发展史上具有里程碑式的意义，将 无线移动通信系统划分成互相独立的小区，复用距离之外的小区可以使 用同一频谱，使无线移动通讯系统的容量得到了显著提高。随着蜂窝移 动通信的发展，越来越多的用户希望得到移动通信的支持，导致有限的 频谱资源越来越拥挤，为此人们采取了许多不同的技术。良好的信道分 配是解决拥挤的频谱资源的有效措施之一，本文介绍了信道分配问题及 其优化算法，并将免疫算法应用到信道分配问题中取得了较好的效果。 随着人们日益增长的对频谱资源的需求以频分多址( f d m a ) 为核心 技术的第二代蜂窝网络由于其自身固有缺点将逐渐被以码分多址 ( c d m a ) 为核心技术的第三代蜂窝网络( 3 g ) 所代替。然而多址干扰 以及由多址干扰引起的远近效应却成为制约其发展的致命瓶颈。多用户 检测技术可以克服或减轻多址干扰和远近效应，从而提高系统的接收性 能。本文介绍了现有的几种智能多用户检测器并对现有的免疫算法作了 改进，将内分泌机理引入免疫遗传算法，提出了免疫内分泌遗传算法， 证明了算法以概率1 收敛，并将免疫内分泌遗传算法应用到智能多用户检 测中。实验表明，该方法较之于传统方法，有良好的应用效果。 关键词：免疫算法；蜂窝网络；信道分配；多用户检测 蜂窝网络中信道分配及多用户检测的免疫算法 曼曼! ! 苎曼曼曼皇皇皇曼鼍皇曼曼曼鼍蔓i i ! ! 曼基皇曼! 曼皇! ! 皇皇皇! 曼曼曼! 皇曼! 曼皇! 曼蔓曼! 皂皇皇皇! ! 苎曼曼鼍曼曼鼍 a b s t r a c t t h e c o n c e p t o f c e l l u l a rn e t w o r k h a sg r e a ts i g n i f i c a n c e i nt h e d e v e l o p m e n t o fw i r e l e s s m o b i l e c o m m u n i c a t i o n b yd i v i d i n g w i r e l e s s c o m m u n i c a t i o ns y s t e mi n t oi n d e p e n d e n tc e l l s ，t h e c e l l s b e y o n d r e u s e d i s t a n c ec a nu s e t h es a m ef r e q u e n c yw i t h o u ti n t e r f e r e n c e t h u s t h e t o t a l c a p a c i t yo fw i r e l e s sc o m m u n i c a t i o ns y s t e mi s i m p r o v e dg r e a t l y w i t ht h e r a p i di n c r e a s eo fc e “u l a rm o b i l ec o m m u n i c a t i o ns y s t e m s ，m o r ep e o p l eh o p e t ob es u p p o r t e db ym o b i l ec o m m u n i c a t i o ns e r v i c e sw h i c hl e a dt h el i m i t e d f r e q u e n c yr e s o u r c e b e c o m em o r es t r i n g e n t t oc o p ew i t ht h i sp r o b l e m ，m a n y t e c h n o l o g i e sh a v eb e e nd e v e l o p e d ，a m o n gw h i c hav a l i dm e t h o dt oa l l e v i a t e f r e q u e n c yc o n g e s t i o n i se f f i c i e n tc h a n n e la s s i g n m e n t t h e c h a n n e l a s s i g n m e n tp r o b l e ma n do p t i m a la l g o r i t h mf o rs o l v i n gi t a r ei n t r o d u c e di n t h i st h e s is t h ei m m u n ea l g o r i t h mh a sb e e ne m p l o y e dw h i c hr e c e i v e s e f f i c i e n tr e s u l t w i t ht h ei n c r e a s i n gn e e do fl i m i t e df r e q u e n c i e s ，t h es e c o n d 。g e n e r a t i o n c e l l u l a r n e t w o r k ( f r e q u e n c ed i v i s i o nm u l t i p l ea c c e s s ，f d m a ) i sr e p l a c e d b vt h et h i r d g e n e r a t i o nc e l l u l a rn e t w o r k ( 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 ld u et oi t so w ni n h e r e n td i s a d v a n t a g e h o w e v e r ，c d m a si n h e r e n t d e f i c i e n c i e s ，s u c ha s ，m u l t i p l ea c c e s si n f e r e n c e ( m a i ) a n dn e a rf a re f f e c t f n f e ) ，a r e f a t a lb o t t l e n e c k sr e s t r i c t i n g i t s d e v e l o p m e n t m u l t i u s e r d e t e c t i o nt e c h n i q u ec a no v e r c o m eo rm i t i g a t e m a ia n dn f es oa st o i m p r o v et h er e c e i v i n gp e r f o r m a n c eo ft h e c d m as y s t e m i nt h i st h e s i s ， s e v e r a lk i n d s o f i n t e l l i g e n c e m u l t i u s e r d e t e c t o r s a r ei n t r o d u c e d c o m b i n i n gt h ee n d o c r i n em e c h a n i s ma n di m m u n eg e n e t i ca l g o r i t h m ，t h e i m m u n e e n d o c r i n eg e n e t i ca l g o r i t h m ( i e g a ) i sp r o p o s e d t h e c o n v e r g e n c e l s r o p e r t i e so ft h e i e g aa r ep r o v e dt h a tt h ei e g ac o n v e r g et og l o b a l o d t i m u mw i t hp r o b a b i l i t y1 t h e nt h ei e g aw a su s e di nt h ei n t e l l i g e n c e m u l t i u s e rd e t e c t i o n t h ee x p e r i m e n tr e s u l t sd e m o n s t r a t e t h a tt h i sn e w a l g a r i t h mh a sb e t t e rp e r f o r m a n c et h a nt h et r a d i t i o n a lo n e s k e yw o r d s ：i m m u n ea l g o r i t h m s ；c e l l u l a rn e t w o r k ；c h a n n e la s s i g n m e n t ； m u l t i u s e rd e t e c t o r l l 硕十学位论文 插图索引 图2 1f e a 算法流程图9 。 图2 2r e a 算法流程图10 图3 1 最佳多用户检测器原理框图15 图4 1 单点交叉示意图21 图4 2 单点变异与两点变异示意图2 2 图4 3 遗传算法的工作流程图2 2 图4 4 免疫算法原理框图j 2 6 图5 1 免疫算法原理图3o 图5 2 仿真蜂窝系统示意图3 2 图5 3 业务量与呼阻率3 3 图6 ：l 多用户检测器模型3 6 图6 2 平均误码率随远近比变化_ 41 图6 3 平均误码率随用户数变化4 2 i i l 蜂窝网络中信道分配及多用户检测的免疫算法 表1 1 表5 ：1 表6 1 表6 2 附表索引 蜂窝移动通信与传统通信对比表2 系统呼阻率随业务量增加量的变化33 平均误码率随远近比变化4 2 平均误码率随用户数变化4 3 i v 兰州理工大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特j 5 t l d n 以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：尹黎么 日期：瑚睁石月f o 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即： 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许 论文被查阅和借阅。本人授权兰州理工大学可以将本学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存和汇编本学位论文。同时授权中国科学技术信息研究所将本学位论文 收录到中国学位论文全文数据库，并通过网络向社会公众提供信息服 务。 作者签名：谍召 导师签名：身簪互霹 日期：2 0 年乡月，o 日 日期：) d 哆年否月，d 日 硕十学何论文 i i 曼量皇! 曼皇曼曼孽! ! 曼! ! 曼曾! ! 曼量皇曼曼舅曼曼! 皇曼曼! 量鼍曼! ! 曼曼曼皇! ! ! 皇曼曼曼曼! ! 曼曼曼曼曼! 笪! ! 鼍! ! 曼曼! 曼曼! 皇曼曼! ! 曼! 曼曼! 皇曼量 1 1 蜂窝网络概述 第1 章绪论 移动通信是指通信双方或至少一方在运动状态中进行信息传递的 通信方式。移动通信不受时间空间的限制，交流信息机动灵活，迅速可 靠。它被认为是实现通信理想目标的重要手段，是信息产业的重要物理 基础。 在自然界中，很多频率是已被使用的，因此可用于移动通信的频率 是有限的。移动通信的服务地区，特别是城市地区中，有限信道数以及 对移动无线电话业务的大量需求导致服务质量无法接受。用户无法迅速 接入网中，需要多次才能占到一个信道。这种情况刺激了蜂窝移动通信 韵发展。促使美国联邦通信委员会f ccd o c k e t18 2 6 2 和贝尔系统在19 71 年12 月制定了蜂窝移动通信标准【lj 。 什么是蜂窝网络呢? 简单地说，就是把移动电话的服务区别分为 一个个正六边形的子区，每个小区设一个基站。形成了形状酷似“蜂窝 韵结构，因而把这种移动通信方式称为蜂窝移动通信方式。蜂窝网络又 可分为模拟蜂窝网络和数字蜂窝网络，主要区别于传输信息的方式。 蜂窝网络被广泛采用的原因是源于一个数学猜想，正六边形被认为 是使用最少个结点可以覆盖最大面积的图形，出于节约设备构建成本的 考虑，正六边形是最好的选择。这样形成的网络覆盖在一起，形状非常 象蜂窝，因此被称作蜂窝网络。 蜂窝网络组成主要有以下三部分：移动站，基站子系统，网络子系 统。移动站就是我们的网络终端设备，比如手机或者一些蜂窝工控设备。 基站子系统包括我们日常见到的移动机站、无线收发设备、专用网络( 一 般是光纤) 、无线的数字设备等等的。我们可以把基站子系统看作是无线 网络与有线网络之间的转换器。 蜂窝移动通信传统移动通信对比如下表： 硕十学何论文 曼曼! 皇曼! 曼! 曼曼! ! ! ! 曼! ! ! 皂! ! ! 曼曼曼! 量曼皂! 曼皇! ! 曼! ! ! ! ! ! 曼! 曼曼曼曼i i i i ! 鼍! 曼曼! ! 苎皇! 苎! ! ! ! ! ! ! ! ! 曼! ! 苎! ! ! ! 暑! ! ! ! ! 烹 表1 1蜂窝移动通信与传统通信对比表 传统移动通信蜂窝移动通信 发射机类单基站发射机设在高处，一个蜂窝系统有多台发射 型使移动电台接受电平明显机，每发射机位于基站， 高于环境噪声蜂窝系统的运行受限于信 道干扰 发射机功高功率2 0 0 2 5o w低功率，每信道低于1o o w 窒 覆盖范围无干扰情况2 0 2 5 英里 10 30 英里 全范围30 0 至几千平方英里7 5 7 0 0 平方英里 干扰若两发射机相距6 0 1o o 英利用频率配置和小区划分 里内，则在离某发射机2 0可减小同信道干扰 英里外的地方明显受另一 发射机的干扰 信道数少量固定频率信道数，当固定频率信道数可在多个 系统在全负荷情况，增长小区重用 容量是不可能的 由上可知，在传统移动电话系统中，发射信号相当强，在附近服务 区无法复用此信道，这严重限制了可用信道的数目。因此，蜂窝系统与 传统移动通信系统相比具有大的用户容量，更有效的利用频谱，全国兼 容，业务密度可适应性，可提供便携机、车载台及其他特殊服务，较好 的服务质量和费用承受能力等优点。 1 2 论文选题的背景和意义 近几十年来，随着科学技术的发展，频谱资源的开发远远跟不上广 播、电视以及通信等领域对它需求的飞速增长。尤其是近十几年来随着 移动通信的迅速发展，人们体会到了这些现代化通信工具所带来的便利与 效益，使得移动通信用户急剧增加。对于移动通信运营商来说，分配给他 们的频谱资源非常有限且不可再生，然而随着小区不断缩小，用户密度不 断增大，最终导致用户数量的无限增长与系统资源的有限扩容这二者之间 的矛盾越来越突出。因此，必须在不降低无线链路质量的条件下，采用 某些技术，利用有限的频谱资源提高整个移动通信系统的容量。 现在常用的改善移动通信系统容量的方法主要有三种，即信道分配 2 硕十学位论文 技术1 2 - 4 、功率控制技术【1 1 和自适应天线技术【1 1 ，其中信道分配主要通过 采用恰当的信道分配技术实现有效的频率复用，功率控制和自适应天线 技术主要从降低同频干扰角度提高系统容量。其中本文主要是研究信道 分配技术。 另一方面，以时分多址( t d m a ) 为核心技术的第一代蜂窝网络和 以频分多址( f d m a ) 【lj 技术为核心的第二代蜂窝网络由于其自身固有缺 点将逐渐被以码分多址( c d m a ) 为核心技术的第三代蜂窝网络( 3g ) 所代替。与f d m a 和t d m a 相比，c d m a 有以下优点：1 、系统容量大； 2 、系统通信质量佳；3 、频率规划灵活；4 、频带利用率高；5 、适用于 多媒体通信系统。 众所周知，c d m a 系统是白干扰系统，它的容量和性能主要受到多 址干扰【5j 的限制。因此接收机的设计是一个重要问题，若能适当地抑制 多用户干扰，就可以显著地提高系统的性能或容量。而多用户检测技术【5 1 是在c dm a 技术的基础上发展起来的能明显抑制多址干扰，显著提高 c d m a 系统容量和性能的一种正在兴起的技术。 多用户检测t 5 】是抑制多址干扰的一种重要手段，又称联合检测或干 扰抵消方法。其产生原因是由于各用户的特征波形不完全正交，匹配滤 波后多址干扰仍然存在，阻碍了正确检测用户信息。多用户检测主要在 基站采用，将多个有用户作联合检测或从接收信号中减掉相互间的干扰， 从而有效地消除多址干扰和符间串扰( i s i ) 【5 1 。多用户检测理论【6 】由 k s s c h n e i d e r 提出，其基本思想就是把所用用户的信号都当作有用信号， 而不当作干扰信号来处理，这样就可以充分利用各用户信号的用户码， 幅度，定时和延迟等信息，从而大幅度降低多址干扰。 1 3 研究现状 最近30 年，国外关于信道分配方面的研究的热度依旧不减。然而， 国内对其的研究却远远不够。因此，对信道分配算法研究及改进就显得 尤为迫切和需要。 满足限制条件的频率分配问题已经在19 8o 年被h a l e 证明了是n p 难 问题【7 j 。而用于衡量系统性能的呼阻率的概念【2j 被z h a n g 和y u m 在19 89 年提出。m c d i a r m i d 和r e e d 在2 0 0 0 年证明了，是否存在z ( g ) = c o ( g ) ( z ( g ) 是图g 的加权色数，c o ( g ) 是图g 的最大权值) 是一个n p c 问题，因而目 前难以找到一个p ( 竞争比)为 1的理想算法【8 】。对于 0 一l o c a l ，l l o c a l ，2 一l o c a l ，4 一l o c a l 问题已经被j a n s s e n 在2 0 0 0 年证明其竞 硕十学何论文 争比p 分别为3 ，3 2 ，1 7 12 ，以及4 3 【9 】。同年m c d i a r m i d 等人将2 一l o c a l 问题其竞争比p 提高到4 3 【8 】，并且提出了2 一l o c a l 问题p 的上限可以达到 9 8 【8 】的猜测。2 0 0 2 年基于图中的每个顶点已知彩( g ) 的情况下，s p a r l 等 给出了一个p 为4 3 的信道分配算法【】。同年z e r o v n i k 等给出了p 为5 4 的一个信道分配算法，在2 0 0 4 年给出了p 为6 5 的一个算法【l1 1 。而基于 固定信道分配算法，动态信道分配算法，混合信道分配算法这三种基本 信道分配算法，人们开始探索智能信道分配算法，如党安红，朱世华等在 2 0 0 2 年提出了用遗传算法解决信道分配优化问题【3 1 。到了2 0 0 3 年_ 个关 于k l o c a l 的通用算法被f i t z p a t r i c k 等提出了，对于图g = ( v ，e ，口，a ，b ) ，其中 捌 砌毗2 砌砒4 一l o c a l 分别可以得到p 为主+ 罢，鼍+ 等，詈+ i 4 b 的结果【12 1 。在2 0 0 4 年p 为6 5 的7 一l o c a ，问题的算法【】由z e r o v n i k 给出。 s p a r l 等在2 0 0 5 年分别给出了p 为4 3 ，5 4 的两个算法，其算法相比与2 0 0 2 年提出的算法，对每个顶点能获取的信息做了削减，从而使算法更加实 用【13 1 。 多用户检测问题在19 7 9 年被首次提出【l4 1 ，在文章中sc h n e i d e r 提出 在d s c d m a 系统中最优多用户检测可以由匹配滤波器组后接v i t e r b i 译 码器构成。在l9 86 年v e r d u 正式提出了最佳用户检测方法( o m d ) ”】。 而19 89 年v e r d u 证明了最佳用户检测方法是一个n p h a r d 的组合优化问 题1 1 引，它指数次的时间复杂度，使其不能在现实中应用，因此人们开始 转向次佳多用户检测器的研究。l u p a s 等人在19 8 9 年首先提出了解相关 检测器，它的变换矩阵是各用户扩频码相关矩阵的逆阵【l6 1 。在19 9 0 年 v a r a n a s i 提出并分析了并行干扰抵消( p i c ) 技术( 也称非线性多极检测) ， 它的主要想法是将最大似然多用户监测技术应用到每一级中【l7 1 。在l9 9 4 年m a d h o w 等人提出了另一类线性检测器即最小均方误差( m ms e ) 检测 器i l 引。同年p a t e l 提出了串行干扰抵消( s i c ) 算法，它的出发点是在传 统单用户检测的基础上最简单的扩充得到多用户检测【i9 1 。在19 9 5 年 h o n i g 等人提出了基于最小输出能量准则的盲多用户检测算法，它以检测 器的输出能量最为目标函数，在已经知道期望用户的扩频序列的情况下， 就能进行多用户检测【20 1 。到了19 9 8 年w a n g 等人提出了基于子空间的盲 多用户检测算法【2 1 1 ，d i v s a l a r 等人提出了一种改进的并行干扰抵消算法 【2 2 】都获得了较好的系统性能。如今多用户检测问题仍是研究热点，吸引 众多研究者投身其中。 总之，信道分配问题及最佳多用户检测问题已经取得了很多可喜的 进展，但由于两问题均被证明是n p h a r d 问题，因此还需要研究者们孜 4 硕十学位论文 i 一 一 i一i!曼曼苎皇!曼曼曼皇晕曼曼!皇曼曼曼蔓曼!蔓曼皇苎!曼!寰曼曼曼曼皇!曼曼曼 孜不倦的探索，以求得更好的解决方法。 1 4 本文研究内容及结构安排 第一章介绍了蜂窝网络的概念、组成、背景、意义及研究现状。 第二章介绍了蜂窝网络中的信道分配问题的概念、产生、核心思想、 分类、约束条件以及解决方案和算法，其中重点介绍了排序分配方法中 的频率穷举法，需求穷举法和最小费用函数方法中代表性的着色算法， 神经网络算法，模拟退火算法。 第三章介绍了第三代蜂窝网络c d m a 中的多用户检测问题并着重介 绍了最佳多用户检测器以及线性多用户检测器中的解相关检测器、最小 均方差检测器和非线性多用户检测器中的串行干扰消除器、并行干扰消 除器。 第四章对遗传算法和免疫算法进行了概述，简述了它们的生物学基 础、基本原理。 第五章将免疫策略算法引入信道分配问题中，并同已有的信道分配 优化算法进行了比较，取得了更优的结果。 在第六章中。为解决遗传算法易陷入局部最优及不能以概率1 收敛的 问题，将内分泌机理引入免疫遗传算法提出了免疫内分泌遗传混合算法。 提高了免疫遗传算法的优化能力，并保证了算法以概率1 收敛，改善了多 用户检测问题解的质量。仿真实验表明混合算法的性能优于现有算法。 最后，对本文的研究工作进行了总结和展望。 5 硕十学何论文 第2 章蜂窝网络中的信道分配问题 随着科学技术进步和人们生活水平的提高，移动通信正在逐步走进 千家万户，使得无线用户数正随着移动通信的迅速发展和普及以惊人的 速度增长。高速增长的无线用户数与有限的频率资源这对矛盾变得更加 突出，人们不得不将分配给无线通信的有限频率资源进行有效复用。另 外从降低服务成本的角度看，对无线频率资源的有效利用也是很重要的， 它能够使基站数减少，降低系统的投资。因此如何提高频率利用率就成 为当前移动通信发展的关键所在，而采用合理的信道分配技术就能够有 效解决频率利用问题。 2 1 信道分配的概念 所谓“信道分配 ( c h a n n ela ssig n m e n t ) ，就是在采用信道利用技 术的蜂窝移动通信系统中，在多信道共用的情况下，以最有效的频谱利 用方式，为每个小区的移动通信设备提供尽可能多的可使用信道。 2 2 信道复用 蜂窝移动系统的一个特点是：在多个间隔距离较远的小区中，能够对 同一信道进行复用。因此如何将同一信道同时分配给这些不同小区将直 接影响到整个系统的性能【3 】。确定给定频谱的可用信道数时，主要根据 信道接收信号的质量和信道复用时产生的同信道干扰。而且两者也是限 制整个无线系统容量最关键的因素。 信道分配策略( ch a n n e1as sig n m e n ts tr a te g y ) 核心思想是：通过 利用同信道小区之间存在无线传播路径损耗的特点，来达到改善载干比 ( cir ) 的目的。例如s ；( k ) 表示使用同一信道k 进行相互通信的一组i 无 线终端。因为存在无线信号传播损耗，所以当i 组和另一i 组用户间隔足 够宽时，信道k 可以同时被两组用户使用。这样使用同一信道的组被称为 同信道系列或简称为同信道。在可接受的干扰水平下，能使用同信道的 最小距离被称为“同信道复用距离”。这种核心思想理想地来说能够使 系统的干扰水平达到最小，但是不幸的是大多数蜂窝系统无法仅采用这 种方式得到优化，因为存在诸如地形起伏、人为障碍等等其它因素。 6 硕十学 ) ：论文 2 3 信道分配策略的分类 根据不同特点和应用方式，信道分配策略可以分为许多不同种类。 通常我们根据信道与小区的关系，可以把信道分配策略分为固定信道分 配策咯( f c a ) 【3 1 、动态信道分配策略( d c a ) 2 3 1 和混合信道分配策略 ( h c a ) 1 2 4 】。 在f c a 中，服务区域被分为许多小区，信道根据一定的复用模式分配 给每个小区。f c a 非常简单，但是它不能随着小区业务量和用户分布的变 化而变化。为了克服f c a 的这些弱点，于是人们提出了d c a 策略。在d c a 中， 所有信道被放置在一个信道池内，根据各个小区的需要进行分配。d c a 以 高复杂度的代价换取信道分配的灵活性和对小区业务变化的自适应性。 但在较高业务承载条件下，d c a 策略其有效性低于f c a 。为了克服这个缺 点，人们又提出了结合f c a 和d c a 两种策略的h c a 。在h c a 中能用莱服务的 所有有用信道被分为固定和动态的两组信道。固定信道组包含着与f c a 策 略相同的分配给小区的一组标称信道【24 1 ，该组信道只被所分配的小区使 用。另外一组信道则可供系统中所有用户共享，这样一定程度提高了系 统的灵活度。当一个小区中有呼叫请求服务且此时该小区所有标称信道 都忙时，则将动态信道组中的一个信道分配给该呼叫。 2 4 信道分配中的干扰约束 在信道分配时必须满足信道的干扰约束。蜂窝通信的关键是频率 复用，即在一个叫、区内使用的信道可以在其它小区重复使用。但是，只 有当小区间的距离很远，使同信道干扰在允许范围内时，这些信道才能 复用。为了获得一个允许的同信道干扰，系统设计者必须保证同信道小 区之问的最小复用距离。同信道干扰还取决于同信道小区数和每簇中的 小区数。在蜂窝系统中同信道干扰是主要的干扰来源，在这个意义上来 说系统容量是受限于干扰而非噪声。与同信道干扰( 干扰落在接收机频带 内) 不同，邻信道干扰是调制射频信号进入邻信道带来的干扰。这种干扰 对系统带来的影响取决于邻信道距离、接收机的选择性和有用载波信号 电平与邻信道载波信号电平的统计相关。邻信道干扰可以看作是干扰的 第二种来源。控制同信道干扰和邻信道干扰的关键是设计者采用的信道 分配方法。 i 因此考虑到蜂窝网络中存在的电磁干扰，我们在进行信道分配时必 须受到以下干扰条件限制： 同信道约束( c c c ) t1 1 ：一个信道不能在其同信道干扰范围内再次使 7 硕十学何论文 用。 邻信道约束( a c c ) e1 1 ：相邻信道不能同时分配给相邻小区使用。 同小区约束( cs c ) t 11 ：同一个小区内的所有信道之间也必须要有一定 的频域间隔，通常要大于邻信道约束( a c c ) 所要求的。 2 5 数学表达 因为在不同多址系统中，信道可能有不同的含义，在f d m a 系统中 信道为频点，t d m a 系统中信道则为时隙1 1 ，而在c d m a 系统中信道 则可能指地址码【l 】，在本文中我们将侧重f d m a 系统中的信道分配，所 以我们这旱的信道是指频点。 假定一个蜂窝系统中，共有n 个小区，可用信道用c1 ，c 2 表示，总 数为c ，这样小区i 所分频的信道数的变化范围为o c ，具体的分配情况 要受很多约束条件( 通信量限制和冲突限制) 2 5 , 2 6 】。用矩阵x 表示冲突 限制如下： rx l l x ：i l k n 。 x i ；= j 1 ，如果小区济叫? 因不能重用_ 禽孽道( 2 1 ) 一u 10 ，如果小区i 和小区馆皂重用一个信道一 a = 三j 囊 ，a 暾= 戮小区i 分配梧道c 。 c2 2 ， 一种可行的信道分配必定使通信量限制和冲突限制都得到满足，即 若t i 为i 小区需求的信道数则可满足通信量a i k = t i 且对于任意小区两个 信道c k 和c 1 分配给小区i 和j ，则有f k - l i x i j 。 2 6 解决信道分配问题的方案和算法 信道分配问题已经被证明是n p h a r d 的组合优化问题1 7j ，对这个问题 的求解现在是一个较热门的课题。回顾以往解决信道分配问题的方法， 我们可以将所有方案分成两种不同类型。一种类型的算法是首先确定一 个包含系统内所有呼叫的排序列表，然后按照一定的分配策略来进行信 道分配。另一种类型算法先构造一个费用函数，该函数能够对一些条件， 例如对分配信道时所违犯干扰约束进行评估，然后试图使费用函数最小 8 、j m 一 眦 x k 硕十学位论文 i|1 1 化。下面我们将分别介绍这两种解决方案。 2 6 1 排序分配方法 这种解决信道分配问题的方案提出得比较早，它首先产生一个包含 所有呼叫的列表l 。根据这个呼叫列表，我们就可以按照一定的试探性算 法f 2 7 1 来进行信道分配。这种分配算法中比较有名的有“频率穷举法 ( f e a ) 2 7 1 和“需求穷举法 ( r e a ) 2 7 】。我们下面具体介绍这两种试探 性分配算法。 图2 1f e a 算法流程图 9 硕十学何论文 1 频率穷举法 f e a 从列表l 的顶部开始，将当前信道分配给当前呼叫，如果信道 不与已经分配好的信道发生冲突，则将该信道分配给当前呼叫，否则试 探下一个信道是否合适，直到所有信道全部试探完毕。接着对下一个呼 叫重复以上步骤，直到所有呼叫全部分配完毕。因此f e a 分配给当f j i 呼 叫的信道将是不违犯干扰约束的最小信道。 图2 2r e a 算法流程图 1 0 硕十学位论文 2 需求穷举法 r e a 将从第一个信道开始，将当前信道按照列表的顺序逐一进行试 探性地分配，如果当前信道能够对已经分配好的信道不产生干扰，则将 该信道分配给当前呼叫，然后继续试探下一个呼叫，直至所有呼叫试探 完毕。接着算法将下一个信道重复以上的步骤，直到所有的信道全部试 出 兀。 我们知道分配所需信道总数将很大程度依赖于列表中呼叫之间的顺 序。因此很多文献分别提出了一些方法，它们根据分配信道给呼叫的难 度等一些试探性手段来对呼叫排序。不幸的是通常即使这样一种排序的 方法也不能找到最佳的呼叫排序列表，因此用这种方法要想找到最优信 道分配方案通常比较困难。 2 6 2 最小化费用函数方法 由于排序分配算法的局限性，最近越来越多的研究者将精力放在最 小化费用函数方法上，试图找到二种比较好的算法来构造正确的费用函 数解决信道分配问题。这种方案是根据不同算法的特点，构造一个费用 函数来评估当前分配方案是否违反三种干扰约束，是否能全部满足各个 小区的呼叫请求。如果某个信道分配方案能满足信道分配问题所有的约 束和话务需求，那么费用函数将达到最小( 一般为零) ，否则根据所用算法 提供的某种迭代机制反复运算，不断调整分配方案，使得费用函数越来 越小，直到为零，所对应的信道分配即为最佳方案。在这种方法中信道 分配的质量和寻找最佳分配所需的时间将直接与算法提供的迭代机制有 关。多年来许多研究者尝试了很多算法，最早应用的是图形着色算法 ( g c a ) 【28 1 ，但是由于存在明显的缺陷，实际中应用的不多。在9 0 年代初， 随着基于自然和物理过程有关的启发式搜索算法的发展，有学者将神经 网络算法( n n a ) t 29 1 、模拟退火算法( s a ) t 3 0 1 和遗传算法( g a ) f 31 】应用到 信道分配问题中，显示出良好的特性。 1 图形着色算法( g c a ) c a p 最早作为一种广义图形着色问题来加以解决【28 1 ，它采用图来表 示不同小区信道之间所必须满足的干扰约束。图的每个点表示一个呼叫， 如果两个点对应的呼叫不能同时使用同一信道，则这两个点用一条边来 连接。边上用一个数字来标记，这个数字就是边的两个端点所需的最小 频率间隔。采用g c a ，c a p 可以等效成分配一个正整数给图中的每个点， 并且满足下面两个准则： ( 1 )如果两个点有边相连，则分配给两个点的整数之差的绝对值 硕十学何论文 要大于或等于边上的标记。 ( 2 )分配中所用的整数最大值尽可能小。 这种算法可较好地解决组合优化问题，其具体步骤可见文献【2 8 】，但 是该算法在实际的c a p 中却存在着缺陷。它寻找最优解的计算所需时间+ 将随着问题的大小成指数增长，也就是说对于实际大小蜂窝网络，采用 该种算法在可以接受的时间内找到最佳信道分配几乎是不可能的。 2 神经网络算法( n n a ) 近年来n n a 也已经被一些研究者用来解决信道分配问题。k u n z 采 用h o p f i e l d 和t a n k 神经模型网络模型【29 1 ，在每一个基站i 给每一个信道 j 之间创造一个神经元。配制二个代表频率间隔约束和信道需求的费用函 数，然后通过神经网络算法将其最小化。在不考虑相邻信道约束时，k u n z 成功地解决了一些小的信道分配问题。f u n a b i k i 和t a k e f u ji 进一步改进了 这种算法，将邻频约束考虑进去，发展了一种并行神经网络算法；获得 了更好的分配结果1 3 2 】。在他们的并行二维神经网络模型中，他们通过采 用一个由n m 处理元素组成的神经网络，来建立一个n 个小区和m 个 信道的信道分配问题模型。 采用n n a 其优点是：由于其整体地采用并行结构，因此可将信道状 态、系统条件、相关的干扰约束、样本数据等信息一并加以考虑，得到 近似优化的解。但是它也存在一些缺点，如在搜索最优解的过程中容易 陷入局部最优解，并且难以摆脱。 3 模拟退火算法( s a ) s a 最初来源于物理学中的固体退火过程。在工业中，经常要对金属 构件加以退火处理，就是先把物体加热到足够高的温度，然后让其缓慢 冷却下来。这是一个物质内部结构从无序到有序的过程，能使物质结构 内能逐渐减少。对应到组合优化问题中，定义优化的目标函数为c ，c 对 应的是物质结构的内能。s a 算法就是找到使c 最小的解状态。s a 比传 统的迭代逼近法优越之处在于：传统的方法是随机地产生一次状态转移， 若此转移使目标函数大大减小了，那么这次转移将被接受。这种方法一 个致命缺点就是极易陷入某个局部地驻点而且难以自拔，而此时距全局 地最优化还有很+ 大地距离。然而s a 则在m e t r o p o l i s 原则的基础上允许作 一些使目标函数增大的“上坡式移动”( u p h i l lm o v e s ) 30 1 ，以便能从绝大 多数局部驻点中脱离出来。 将s a 应用到c a p 中，关键是在c a p 中定义目标函数c 、离散的结 构空间s 以及相邻的结构空间s ，使c 取得最小值的解，其对应的结构 空间s 即是所要求的信道分配方案。在c a p 中，目标函数可用干扰兼容 1 2 硕十学何论文 矩阵与各小区信道需求数来共同确定。 我们假设一个蜂窝系统具有n 个小区，m 个可用信道，那么结构空 间s 的一种较为自然的选择方案就是用一个n m 维的二进制矩阵s = ( s ：) 来表示： 屯= 0 篙嚣0 5 斥j o i n , o j ( 3 1 ) 其中b k l ，一1 1 x k ( 3 2 ) 式中，b k 。就是使c ( 躲，k ) 取得最大值时的信息矢量。从式( 3 1 ，3 2 ) 可以看出，最佳多用户检测器实际上就是一个求有约束的优化问题。 许多学者对这个优化问题进行了不懈的研究。其中比较经典的实现 方法是v e r d u 于198 6 年在文献【5 】中采用b a y e s 后验概率最大的原理提出 的用匹配滤波器加维特比算法来实现最大似然序列检测 ( m a x i m u m l i k e l i h o o ds e q u e n c ed e t e c t i o n ，m l sd e t e c t i o n ) 。这种方法适 用于受符号间干扰( i n t e r s i g n a li n t e r f e r e n c e ，i s i ) 影响的信道，但是算法的 复杂度仍然是用户数的指数幂级，即2 k ，而且m l s 检测器需要知道接 收信号的幅度和相位，这要通过估计来得到。m l s 检测器过于复杂，不 实用。因此大家把主要精力集中在研究最佳多用户检测的间接的或近似 的实现方法，使得该方法既可克服多址干扰问题又具有合理的计算复杂 度，易于实时实现，这就是下面介绍的次佳多用户检测器。 硕十学位论文 3 2 次佳多用户检测器 目前，次佳多用户检测器的方法很多，按处理方法分，大致可分为 线性多用户检测器 3 3 1 和非线性多用户检测器【33 1 。线性多用户检测器包括 解相关检测【16 1 、最小均方误差检测18 1 和最优线性检测1 4 1 等。非线性检测 主要包括并行干扰抵消算法【17 1 、串行干扰抵消算法 19 , 3 5 1 以及各种神经网 络多用户检测器【3 6 】等。线性多用户检测器的思想是经过一个线性变换将 匹配滤波器的输出送入判决设备。非线性多用户检测器则利用可靠的己 知信息对干扰进行估计，然后在原信号中减去估计干扰以利于接收判决， 因而又称为干扰消除多用户检测器。它们的共同特点是：计算量都超过 传统多用户检测器，但低于最佳多用户检测器；检测性能好于传统多用 户检测器，但较最佳多用户检测器差。 3 2 1 线性多用户检测器 1 解相关检测器 解相关检测器( d e c o r r e l a t i n gd e t e c t o r ) 的出发点是将多用户检测中的 多址干扰等效为信道的产生响应矩阵r ，该矩阵只与各用户的扩频码以 及扩频码之间的相对时延有关。解相关检测器对接收机匹配滤波器的输 出用l = r 一与之相乘进行解相关，去除扩频码之间的相关性，从而达到消 除多址干扰的目的。 解相关检测器的输出结果为【l 州： b k d e c = s g n ( l e = y k ) = s g n ( r y k ) = s g n ( a k b k s k + n k d )( 3 3 ) 其中，a 。为第k 个用户信号到达基站时的幅度；b 。为第k 个用户传 输的信息序列；s k 为分配给第k 个用户的归一化特征波形；n k 。= r 。1 n k 为 解相关器的输出噪声。 解相关检测器在大多数情况下比传统检测器具有性能或容量上的提 高，与最大似然序列检测器相比计算复杂度大大降低。 解相关检测器的优点主要有： ( 1 ) 不需要估计接收幅度，而需要幅度估计的检测器通常对于估计错 误十分敏感。 ( 2 ) 计算复杂度远远低于最大似然检测器。每比特检测的复杂度是用 户数的线性函数，除去计算求逆的代价。 ( 3 ) 由于完全消除了多址干扰，因而在对抗远近效应方面得到最优 值。 但是该检测器具有下面的缺点： 1 6 硕十学位论文 c 1 ) 引起了噪声的增加，在输出端噪声的每比特功率总是大于或等于 传统检测器输出噪声的功率。 ( 2 ) 计算矩阵r 的逆很难实时实现。在同步系统中实现k k 矩阵的 求逆还是可以的；然而对于异步系统来说，r 的规模是n k n k ，对于一 个典型信息长度n 计算量太大了，因而难以用于实时通信系统。 2 最小均方误差检测器 最小均方误差检测器( m i n i m u mm e a n s q u a r e de r r o rd e t e c t o r m m s e d e t e c t o r ) 是在解相关的基础上发展而来，它是一种将背景噪声考虑在内 并使用接收信号功率信息的线性检测器。这种检测器的出发点是使传统 检测器的输出和实际的数据间的均方误差最小。它采用的线性变换l 。一为 【1 8 1 l m m 辩寻【r + n o 2 a k - 2 】_ 1 ( 3 4 ) 检测器的输出结果为18 1 ： bk m m s e2 s g n ( l m m s e y k ) ( 3 5 ) a 。为第k 个用