（通信与信息系统专业论文）tdscdma系统中慢速动态信道分配技术的研究.pdf

摘要 t d s c d m a 系统中慢速动态信道分配技术的研究 专业名称：通信与信息系统 硕士生：陈洁婷 指导教师：戴宪华教授 摘要 t d - s c d m a ( t i m ed i v i s i o n - s y n c h r o n i z a t i o nc o d ed i v i s i o nm u l t i p l ea c c e s s ) 标准是大唐电信集团代表中国提出，由国际电信联盟i t u 批准并加入第三代合 作项目的移动通信国际标准之一。其研发一直受到国家的高度重视，很多关键技 术已经成为国内外研究的热点。 动态信道分配技术( d c a ) 是t d s c d m a 系统的关键技术之一，优秀的 d c a 算法能够充分发挥t d s c d m a 系统资源分配灵活的特点，在以下行业务为 主的3 g 综合业务中获得最佳资源利用率。d c a 分为慢速动态信道分配( s d c a ) 以及快速动态信道分配( f d c a ) 。 t d s c d m a 系统中的慢速动态信道分配的主要任务是进行各个小区间的 资源分配，依据小区内业务不对称性的变化，在每个小区内分配和调整上下行资 源，使时隙的上下行传输能力和业务上下行负载的比例关系相匹配，以获得最佳 频谱效率。本文在国内外d c a 算法研究的基础上，对t d s c d m a 系统的慢速 d c a 技术进行了研究，提出了一种小区合并方法并引入和改进了人工智能中的 遗传算法来实现慢速动态信道分配的优化，最终使得系统资源利用率最大化。本 文的工作和成果对t d s c d m a 系统慢速d c a 技术的研究具有一定的参考价值。 关键词：t d s c d m a ，动态信道分配，遗传算法，资源利用率 a b s t r a c t r e s e a r c ho ns l o wd y n a m i cc h a n n e la l l o c a t i o n t e c h n o l o g y i nt d - - s c d m a s y s t e m m a j o r ： c o m m u n i c a t i o na n di n f o r m a t i o ns y s t e m n a m e ： j i e t i n gc h e n s u p e r v i s o r ：p r o f x i a n h u ad a i a b s t r a c t t d s c d m a ( t i m ed i v i s i o n - s y n c h r o n i z a t i o nc o d ed i v i s i o nm u l t i p l ea c c e s s ) s t a n d a r di sr a i s e db yd a t a n gt e l e c o mg r o u p ，w h i c hh a v e b e e na c c e d e da so n eo ft h e i n t e r n a t i o n a ls t a n d a r d sf o rt h et h i r dg e n e r a t i o np a r t n e r s h i pp r o j e c tb yt h ei t u ( i n t e r n a t i o n a lt e l e c o m m u n i c a t i o nu n i o n ) i t sr &dh a sb e e nr e c e i v e dah i g hd e g r e e o fa t t e n t i o n , m a n yo ft h ek e yt e c h n o l o g yh a sb e c o m eah o tr e s e a r c hf i e l da th o m ea n d a b r o a d d y n a m i cc h a n n e la l l o c a t i o nt e c h n i q u e s ( d c a ) i so n eo ft h ek e yt e c h n o l o g i e si n t d - s c d m as y s t e m , e x c e l l e n td c a a l g o r i t h mc a ng i v ef u l lp l a yt ot h ec h a r a c t e r i s t i c s o ff l e x i b l er e s o u r c e sa l l o c a t i o ni nt d s c d m as y s t e ma n do b t a i nt h eb e s tr e s o u r c e s u t i l i z a t i o ni nt h ed o w n s t r e a mt r a f f i c b a s e d3 gs e r v i c e s d c ai sd i v i d e di n t oas l o w d y n a m i cc h a n n e la l l o c a t i o n ( s d c a ) a n df a s td y n a m i cc h a n n e la l l o c a t i o n ( f d c a ) i nt d s c d m as y s t e m , t h em a i nt a s ko ft h es l o wd y n a m i cc h a n n e la l l o c a t i o ni st o c b x r yo u tt h er e s o u r c e sd i s t r i b u t i o na m o n gv a r i o u sc e l l s ，a l l o c a t ea n da d j u s tt h eu p l i n k a n dd o w n l i n kr e s o u t c e sa c c o r d i n gt ot h ea s y m m e t r i ct r a f f i c ，s ot h a tt h et r a n s m i s s i o n c a p a c i t ya n d t r a f f i ci sm a t c ht og e tt h eb e s ts p e c t r a le f f i c i e n c y 1 n a b s t r a c t t h i sp a p e rr e s e a r c ho nt h es l o wd c a a l g o r i t h mi nt d s c d m as y s t e m , p r o p o s e ac e l lm e 玛e rm e t h o d ，i n t r o d u c ea n di m p r o v et h eg e n e t i ca l g o r i t h mo fa r t i f i c i a l i n t e l l i g e n c et oa c h i e v et h es l o wd y n a m i cc h a n n e la l l o c a t i o no p t i m i z a t i o n , u l t i m a t e l y m a x i m i z er e s o u r c eu t i l i z a t i o n t h i sw o r ka n dt h er e s u l t sh a sc e r t a i n r e f e r e n c ev a l u et o t h er e s e a r c ho ns l o wd c ai nt d s c d m a s y s t e m k e yw o r d s ：t d - s c d m a , d y n a m i cc h a n n e la l l o c a t i o n , g e n e t i c a l g o r i t h m , r e s o u r c eu t i l i z a t i o n i v 论文原创性声明 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经引用的内容外，本论文不包含任何其他个人或集 体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名1 ；墓沼。芎 日期：加l 。年 g 月午日 学位论文使用授权声明 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保 留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权 将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料 室被查阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、 缩印或其他方法保存学位论文。 学位论文作者躲节、涟涉车 日期：z , o i o 年月4 日 。 导师签名： 日期：叫0 第一章绪论 1 1 研究背景及意义 第一章绪论帚一早三；百下匕 自2 0 世纪8 0 年代以来，移动通信在全球范围内得到了迅速发展，经历了第 一代的模拟移动通信系统及第二代的g s m 和窄带c d m a 移动通信系统两个发 展阶段，目前已经进入一个新的发展阶段，也就是人们普遍关注的第三代移动通 信( 3 g ) 阶段。在第三代移动通信系统中，业务的主要类型将不在是上下行业 务量对称的语音业务，而是上下行业务量严重不对称的多媒体及数据业务。 目前第三代移动通信系统主要有3 个国际标准，分别是：北美提出的 c d m a 2 0 0 0 、欧洲和日本提出的w c d m a 和我国提出的t d s c d m a 。其中 t d s c d m a 系统采用了上行同步、智能天线、联合检测、接力切换、软件无线 电等一系列高新技术，对系统容量和性能带来的好处被业界所公认【l 】。 在第一代和第二代移动通信系统中，由于我国起步较晚，技术基础薄弱，基 本没有核心专利，在技术上受制于人。2 0 0 5 年，由中国提出的t d s c d m a 系统 正式成为国际第三代移动通信标准之一，这是中国百年电信史上的第一次重大突 破。但由于t d s c d m a 系统的提出大约比另外两种第三代移动通信标准 w c d m a 和c d m a 2 0 0 0 晚5 年左右，相对其他两个标准来说t d s c d m a 系统 的发展相对落后，尚未成熟。因此，对t d s c d m a 系统进行深入地研究对我国的 通信事业的发展具有重大意义。 动态信道分配技术( d c a ) 是t d s c d m a 系统采用的众多先进技术之一。 它涉及到用户终端、节点和无线网络控制器等多个网络单元的设计构造。d c a 算法的好坏对系统的性能有着直接的影响，由于第三代移动通信系统业务的多 样性，业务对上下行资源需求不断变化，有必要借助d c a 算法灵活地对上下行 信道资源进行分配以获得系统最佳的资源利用率。业内普遍认为对d c a 技术进 行深入地研究具有重要意义，目前对它的研究已成为移动通信研究领域中的热点 问题。 第一章绪论 1 2 t d s c d m a 系统概述 t d - s c d m a 系统是我国提出的世界上第一个采用时分双工( t d d ) 方式和 智能天线技术的第三代移动通信系统标准之一，系统同时采用了多用户检测、软 件无线电、接力切换等一系列高新技术，具有频谱利用率高，资源灵活分配等特 点。 1 2 1t d s c d m a 系统的物理信道信号格式 t d s c d m a 系统的物理信道采用四层结构，包括系统帧、无线帧、子帧和 时隙，码。一个1 0 m s 的无线帧包括两个5 1 n s 的子帧，每个子帧包含1 0 个时隙， 包括7 个业务时稼和3 个特殊时隙，其中时隙t s 0 固定用于下行方向t s l 固定 用于上行方向，其余时隙的方向可以变化。特殊时隙中，d w p t s 和u p p t s 分别 对应于下行和上行同步时隙g p 为上下行间保护间隔。图1 - 1 为t d s c d m a 系 统的子帧结构。 1 2 8 m d st w p t s ( 9 6 c h i p ) r 帧5 m s ( 6 4 0 0 c h i p ) g p u p p r s 转换 ( 9 6 c h i p )( 1 6 0 c h i p ) 图1 1t d s c d m a 系统予帧结构 t d s c d m a 系统中，一个物理信道就是在指定无线帧的一个特定时隙内传 输的一个突发。一个突发包括以下三部分：数据部分、m i d a m b l e 部分和一个保 护时隙。其中的数据部分由信道码和扰码共同扩频，扩频因子可以取l ，2 ，4 ， 8 或1 6 ，物理信道的数据速率取决于扩频因子的大小。多个突发可以同时发送， 在这种情况下，不同突发的数据部分必须使用相同的扰码，但应使用不同的信道 码吐 第一章绪论 1 2 2t d s c d m a 系统的基本参数 t d s c d m a 系统的基本参数可以归纳为如表1 1 所示【1 】： 表1 1t d s c d m a 系统的基本参数 参数值 技术特征t d - s c d m a 信道间隔 1 6 m h z 码片速率 1 2 8 m c s * 多址方式f d m a + t d m a 十c d m a 双工方式 t d d 帧长短帧长1 0 m s ( 子帧5 m s ) 信道载波4 8 ( 对称业务) d s 与m c 方式单载波窄带d s 数据调制 q p s k 8 p s k ( 2 m b s 业务) 扩频调制q p s k 语音编码 8 k n s a m r ) 信道编码卷积编码+ t u r b o 基站发射功率最大4 3 d b m 移动台发射功率 3 3 d b m 小区覆盖半径 o 1 1 2 k i n 切换方式硬切换软切换接力切换 上行同步 1 8 c h i p 相干检测上行、下行：连续的公共导频 3 第一章绪论 功率控制开环加闭环功率控制，2 0 0 次s 多速率方案 多时隙、可变扩频和多码扩频 基站间定时 同步 1 2 3t d s c d m a 系统的主要特点 t d s c d m a 系统的主要技术特点如下：t d d 模式、低码片速率、上行同步、 接力切换、智能天线等。这些技术特点有些是t d s c d m a 系统特有的，有些是 其他标准也包含的。正是由于这些技术特点才使得它成为第三代移动通信系统的 主流标准之一【2 1 。 ( 1 ) t d d 模式：t d s c d m a 系统采用t d d 模式。与f d d 方式不同，t d d 方式使用同一频率的不同时隙作为信道的承载，由保护时隙来分隔接收与 发送信道，其单向资源在时间上不连续。 ( 2 ) 低码片速率：t d s c d m a 系统采用的码片速率为高码片速率的l 3 倍。 码片速率越低，载波占用的带宽也越小，可以节省频率资源。另外，码片 速率低则硬件实现更加容易，可以降低设备成本。 ( 3 ) 上行同步：指来自不同用户终端的上行信号到达基站解调器的时间完全同 步。采用上行同步技术后，基站端接收的各个信号之间完全正交，因此不 会产生多址干扰，提高了系统容量。 ( 4 ) 接力切换：接力切换具有软切换不丢失信息的优点的同时又克服了软切换 对临近基站信道资源和服务基站下行信道资源浪费的缺点，简化了用户终 端的设计。接力切换技术的采用可以提高切换的成功率，进而提升系统的 性能。 ( 5 ) 智能天线：t d d 模式中，基站对上行信道估计的信道参数可以用于智能 天线的下行波束成型。因此，t d d 模式下智能天线技术的实现相对f d d 模式要容易些。 4 第一章绪论 1 3 国内外研究现状 通信系统设计的目的是为了满足业务量需求，在保证通信质量的前提下尽可 能提高系统容量。在3 g 通信系统中，由于业务方式的多样性，当业务不断变化 时，系统内业务对上下行资源的需求也不断变化。如果采用固定的时隙分配，会 造成系统资源的浪费，不月 匕1 a 1 4 k 1 3 好的满足系统需求【3 1 ，因此有必要对上下行时隙进 行动态分配以适应不同的业务情况。但是这样也可能引入交叉时隙干扰，影响系 统的性能 4 1 。因此，对系统进行时隙的动态分配时，要考虑上下行业务变化，还 要考虑交叉时隙干扰的影响。 d g j e o n g 和w s j e o n 等人在双小区模型下对c d m a t d d 系统的上下行时 隙分配策略进行了相关研究【5 】【6 】【7 】，主要包括相同时隙分配策略( s a ) 和不同时 隙分配策略( d a ) 。研究结果表明与s a 策略相比，d a 策略虽然引入了一定的 算法复杂度，但是在性能上也有所提升。 h y o m o 和s h a r a 对1 9 小区环境下的时隙分配进行了s a 策略的研究【8 1 1 9 ， 由于s a 策略的局限性，其系统资源利用率的提高有限。 h h a a s 和s m c l a u g h l i n 提出了一种时隙反转技术( t s o t ，t i m es l o to p p o s i n g t e c h n i q u e ) 1 o 】。当前向链路的干扰小于反向链路时，就将该时隙反转，根据干 扰测量的结果，选择干扰较小的时隙分配。研究结果表明t s o t 技术可以有效地 减少干扰，但由于t d s c d m a 系统中上下行时隙分配了之后不能随意更改，所 以该算法并不适用于t d s c d m a 系统。 文献 1 1 】提出了一种热点小区算法，该算法将业务情况考虑进来，在时隙分 配中优先保证业务量大的小区不受到交叉时隙的干扰。依据业务情况将系统内所 有小区划分为若干个簇，每个簇采用相同的时隙分配。算法中先选出部分业务量 较大的小区作为热点小区，热点小区根据自身的业务状况确定时隙分配情况，其 相邻的小区采用和热点小区一致的时隙分配 1 1 1 。这样就保证了业务量大的小区 不会发生交叉时隙干扰，其实质就是牺牲了热点小区周围小区的容量以换来热点 小区容量的提高。该算法受系统内的业务情况影响较大，其适用范围有限。 5 第。章绪论 1 4 主要研究内容和论文结构 1 4 1 主要研究内容 本文主要研究t d s c d m a 系统的慢速动态分配技术，根据系统中不同小区 的业务的情况，合理地、有效地对系统内所有小区分配上下行时隙，在满足系统 上下行资源需求的基础上，尽量降低交叉时隙干扰带来的影响，以提高系统容量。 本文提出了一种小区合并的方法并引入和改进了人工智能中的遗传算法对慢速 动态信道分配的组合优化问题进行求解，在众多解空间中搜索最优解以实现系统 平均资源利用率的最大化，并通过实验仿真验证该方法的可行性。 1 4 2 论文结构安排 论文结构安排如下： 第一章绪论 阐述了本课题的研究背景及意义，概括性的介绍了t d s c d m a 系统标准， 包括物理信道、帧结构，基本参数和主要特点。说明了本文的主要研究内容以及 论文结构。 第二章动态信道分配技术 本章首先简要介绍了无线资源管理的概念和组成、r r m 模块在通信实体中 的位置及各个模块的作用，之后介绍了信道分配技术的几种类型，着重介绍其中 的动态信道分配技术并详细描述了慢速d c a 和快速d c a 的任务、遵循的原则 以及具体步骤。 第三章遗传算法 本章概述性的介绍了遗传算法的基本原理和方法、常见的编码方式和基本的 遗传算子，着重介绍了遗传算子的具体操作，最后简要地概括了自适应遗传算法 的优点。 第四章基于自适应遗传算法的慢速d c a 方案 6 第一章绪论 本章分析了t d s c d m a 系统特有的交叉时隙干扰，提出了系统模型并简要 介绍了传统慢速d c a 算法，针对现有慢速d c a 算法的缺点，本章提出种小 区合并方法和基于自适应遗传算法的慢速d c a 方案，并在此基础上对该慢速 d c a 算法进行改进。对基于自适应遗传算法的慢速d c a 方案及其改进方案进行 了实验仿真和算法复杂度分析，仿真结果表明改进后的慢速d c a 方案在性能和 收敛速度上都有了明显提升，验证了算法的可行性。 第五章总结与展望 总结论文所作的工作，并指出存在的问题及后续工作的建议。 7 第二章动态信道分配技术 第二章动态信道分配技术 2 1 无线资源管理机制 2 1 1 无线资源管理概述 对于无线通信系统来说，资源的概念是很广泛的，既可以是频率，也可以是 时间，还可以是码字，甚至是空间资源。无论从哪个角度来看，无线通信系统都 是资源受限的系统，如何高效地利用有限的无线资源来满足日益增长的用户需 求，在移动通信中是一个需要解决的问题。 无线资源管理( 删) 就是对移动通信系统的空中接口资源的规划和调度。 在保证一定规划覆盖和服务质量要求的情况下，接入尽可能多的用户。在带宽资 源有限的情况下，为网络内用户终端提供可靠的通信质量保斟1 2 】。 r r m 的作用主要有三个方面【1 3 】： ( 1 ) 保障用户申请业务的服务质量，包括b l e r 、b e r 、业务优先级等； ( 2 ) 确保系统规划的覆盖范围； ( 3 ) 充分提高系统容量。 在第三代移动通信系统中，无线资源管理( 1 u 洲) 的主要控制功能位于r n c 实体内，由r n c 、n o d e b 和u e 共同来完成所有功能。 2 1 2r r m 模块 从组成结构来分，r r m 包括算法模块、资源分配模块、无线资源数据库和 对外接口模块等。图2 1 为r r m 模块在通信实体中的位置，其中算法模块是r r m 模块的核心，具体包括以下功能部分【1 4 】： ( 1 ) 功率控制模块：保证链路通信质量的前提下降低功率的损耗，延长终端的 使用时间。 ( 2 ) 切换控制模块：保证用户通信的连续性，在维持通信质量的前提下将用户 8 第二章动态信道分配技术 从当前小区的通信链路转移到相邻小区。 ( 3 ) 接纳控制模块：维持网络的稳定性和用户的q o s 。当用户发起呼叫或者切 换请求时，接纳控制模块运作，执行相应功能。 ( 4 ) 分组调度模块：支持分组数据业务，包括基于r n c 的分组调度和基于基站 的分组调度。 ( 5 ) 负载控制模块：计算和提供网络的负荷信息，当网络过载时，触发r r m 中其他模块的综合作用将网络恢复正常。 ( 6 ) 动态信道分配模块：主要功能包括信道优先级排队、信道选择、信道调整 和资源整合。 ( 7 ) 无线链路检测模块：监测无线链路的质量，当通信链路质量变差时，向相 应的r r m 模块发送链路情况的报告。 ( 8 ) 资源管理模块：具体包括码资源分配、逻辑信道资源和传输信道资源的管 理。 l c i l l b ， 基站 u u 1 移动台 饿翁 锣渺 图2 1 ：r r m 模块在各通信实体中的位置 9 第二章动态信道分配技术 2 2 动态信道分配技术概述 2 2 1 信道分配技术 信道分配方案可以分为固定信道分配( f c a ) 、动态信道分配( d c a ) 和混 合信道分配( h c a ) 三种。具体包括呼叫接入控制、信道分配、信道调整三个 步骤【1 6 】。 f c a 是指根据预先估计的系统业务负荷情况将信道资源分给若干小区，在 距离间隔足够大的前提下，信道可以复用【1 7 】。在第二代移动通信系统中，业务 方式主要是语音通信业务，通信信道主要用于传送语音业务，由于语音业务具有 业务对称性，其对上下行信道资源的需求基本一样，因此在第二代移动通信系统 中，信道分配方案大都采用固定信道分配方案( f c a ) 。虽然f c a 对无线信道资 源进行管理比较容易，信道间干扰也易于控制，但其信道无法最佳化使用，频谱 信道效率低【1 8 】。 d c a 方案可以很好地克服f c a 的缺点。在d c a 方案中，信道资源不固定 属于某个小区，所有信道资源集中起来由r n c 进行分配。r n c 根据系统内所有 小区的业务情况，信道的通信质量等因素动态地对信道进行分配。在第三代移动 通信中，业务类型除了传统的语音业务还包括了大量的数据业务，业务对上下行 资源的需求不再相同，因此需要使用d c a 技术来对通信资源进行分配，最大化 地提高系统容量。h c a 是f c a 和d c a 的结合，在h c a 中全部信道被分为固定 和动态两个集合。本文主要研究的是d c a 技术。 d c a 的途径主要有频域、时域、码域以及空域4 种方式。在频域上，通过 改变无线载波的频率来进行频域d c a ，以减小目前所使用的无线载波所有时隙 中的干扰。在时域上，采用时分多址( t d m a ) 技术，通过改变时隙可进行时域 d c a 。同样，在码域上，可以通过改变分配的码道来避免偶然出现的码道质量 恶化。另外，由于智能天线技术的提出，我们在空域上可以通过用户定位和波束 赋形来减少小区内用户之间的干扰，选择用户间最有利的方向去耦，进行空域动 态信道分配【1 2 1 。 l o 第二章动态信道分配技术 一般来讲，动态信道分配技术( d c a ) 包括两个方面：慢速d c a 和快速 d c a 。前者将资源分配到小区，后者则把资源分配给承载业务【饽】。d c a 的具体 流程如图2 2 所示。 慢速 d c a 图2 - 2d c a 流程 2 2 2 慢速d c a 慢速信道分配的重要任务是对小区资源分配或信道指派，为每个小区分配和 调整上下行链路资源和分配信道优先级2 0 1 。 由于3 g 系统支持上下行业务需求不对称的数据业务，因此系统内不同小区 对上下行资源的需求互不相同。t d s c d m a 系统可以利用其特有的帧结构动态 地调整时隙转换点以满足业务的q o s 需求【1 3 1 。 慢速d c a 遵循以下原则【1 4 1 ： ( 1 ) 在频域内，不同簇可以进行频率复用。在频域内的簇复用不需要进行频率 规划但要根据需要对不同小区进行时隙分配。 嚣 丽 饼 ；iifl；iiliilll删瓶 遴渊慊雠 第二章动态信道分配技术 ( 2 ) 在t d d 帧结构中，除去第一个业务时隙t s 0 固定用于下行方向，时隙t s l 固定用于上行方向外，其他的业务时隙方向都可以自行安排。因此，可以 通过设置合适的上下行时隙转换点来调整上下行资源的分配。 ( 3 )由于系统内不同小区的业务情况会随时间而不断变化，为了适应系统内不 同小区的业务情况，需要在较长的时间范围内对所有小区时隙动态地进行 重新分配。 2 2 3 快速d c a 快速动态信道分配( f a s td c a ) 是指系统为申请接入的用户分配物理信道， 并根据系统状态对已分配的资源进行调整。由图2 2 可以看到，f d c a 的主要步 骤包括信道优先级排队、信道选择、信道调整和资源整合 2 1 1 。 f d c a 遵循以下一些准则【2 2 1 。 ( 1 ) 用于信道分配的基本资源单元由码字、时隙和频率确定。 ( 2 ) 基站将所有基本资源单元集中起来对各个业务请求进行相应的资源分配。 对于某个业务请求，可以在码域、时域或者空域对其分配资源，还可以随 意进行组合。 ( 3 ) 信道分配根据业务类型的不同采用相应的分配策略。对于实时业务和非实 时业务而言，实时业务在整个通信过程中保持信道占用，而非实时业务则 遵循“b e s te f f o r t 策略。 ( 4 )当系统内实时高速率业务发起接入请求时，系统进行资源整合。资源整合 包括用户切换信道和系统收回部分低优先级用户的资源分给优先级较高 的用户。 ( 5 ) 通过采用智能天线技术，在进行d c a 时，可以保证同一时隙内不同用户 在空间上分隔开来，也可以通过使用不同的时隙将空间上处于同一方向的 不同用户进行分隔，以减少用户相互间的干扰。 1 2 第二章动态信道分配技术 2 3 本章小结 本章首先简要介绍了无线资源管理的概念和组成、r r m 模块在通信实体中 的位置及各个模块的作用，之后介绍了信道分配技术的几种类型，着重介绍其中 的动态信道分配技术并详细描述了慢速d c a 和快速d c a 的任务、遵循的原则 以及具体步骤。 1 3 第三章遗传算法 3 1 遗传算法概述 第三章遗传算法 遗传算法( g e n e t i ca l g o r i t h m , g a ) 是一类借鉴生物界自然选择机制产生的 随机化搜索算法，最先是由美国m i c h g a n 大学的j o h nh o l l a n d 于1 9 7 5 年提出。 遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。它的 思想源于生物遗传学和适者生存的自然规律，是具有“生存+ 检测”的迭代过程的 搜索算法。遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、 适用于并行处理以及应用范围广等显著特点，奠定了它作为2 1 世纪关键智能计 算之一的地位【2 3 1 。 3 1 1 遗传算法的基本原理和方法 遗传算法的基本思想是基于模仿生物界遗传学的遗传过程。它把问题的参数 用基因代表，把问题的解用染色体代表( 在计算机里用二进制码表示) ，从而得 到一个由具有不同染色体的个体组成的群体【2 4 1 。这个群体在特定的问题环境里 生存竞争，适者有最好的机会生存和产生后代。后代随机化地继承了父代的最好 特征，并也在生存环境的控制支配下继续这一过程。群体的染色体都将逐渐适应 环境，不断进化，最后收敛到一簇最适应环境的类似个体，即得到问题最优的解 2 5 1 o 遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法，在这个算法 中要用到各种遗传学的概念。下面给出遗传学概念、遗传算法概念和相应的数学 概念三者之间的对应关系2 6 1 。如表3 1 所示： 表3 1 遗传学概念、遗传算法概念和数学概念的对应关系 序号遗传学概念遗传算法概念 数学概念 1个体要处理的基本对象、结构也就是可行解 2 群体个体的集合 被选定的一组可行解 3 染色体个体的表现形式 可行解的编码 1 4 第三章遗传算法 4 基因染色体中的元素编码中的元素 5 基因位某一基因在染色体中的位置元素在编码中的位置 6 适应值个体对于环境的适应程度，可行解所对应的适应函数 或在环境压力下的生存能力 值 7 种群被选定的一组染色体或个体根据入选概率定出的一组 可行解 8 选择从群体中选择优胜的个体， 保留或复制适应值大的可 淘汰劣质个体的操作行解，去掉小的可行解 9 交叉 一组染色体上对应基因段的根据交叉原则产生的一组 交换新解 l o 交叉概率染色体对应基因段交换的概 闭区间【0 ，l 】上的一个值， 率( 可能性大小)一般为0 6 5 0 9 0 1 1 变异染色体水平上基因变化编码的某些元素被改变 1 2 变异概率染色体上基因变化的概率 开区间( 0 ，1 ) 内的一个值， ( 可能性大小)一般为0 0 0 1 - 4 ) 0 1 1 3进化、 个体进行优胜劣汰的进化，目标函数取到最大值，最 一代又一代地优化优的可行解 适者生存 3 1 2 遗传算法的步骤 遗传算法计算优化的操作过程就如同生物学上生物遗传进化的过程，主要包 括选择算子( s e l e c t i o n ) 、交叉算子( c r o s s o v e r ) 和变异算子( m u t a t i o n ) 2 7 1 。 遗传算法基本步骤是： ( 1 ) 编码：把问题的解表示成“染色体”，在算法中就是以编码得到的串。 ( 2 ) 生成初始群体：在执行遗传算法之前，给出一群“染色体”，也就是假 设的可行解。 第三章遗传算法 ( 3 ) 适应性值评估：把假设的可行解置于问题的“环境”中，按适应度值进 行评估，从中选择适应度大的染色体。 ( 4 ) 选择：选择的目的是为了从当前群体中选出优良的个体，使它们有机 会作为父代为下一代繁殖子孙。 ( 5 ) 交叉：遗传算法中最主要的遗传操作。通过交换操作可以得到新一代 个体，新个体组合了其父辈个体的特性。交换体现了信息交换的思想。 ( 6 ) 变异：变异首先在群体中随机选择一个个体，对选中的个体以一定的 概率随机地改变某个基因位的值。变异为新个体的产生提供了机会。 ( 7 ) 判断群体性能是否满足某一指标、或者是否已完成预定的迭代次数， 不满足则继续操作，否则输出最优解。 遗传算法有很多种具体的不同实现过程，以上介绍的是标准遗传算法的主要 步骤。图3 1 为遗传算法基本流程图： 图3 1 遗传算法基本流程图 1 6 第三章遗传算法 3 2 编码 遗传算法一般不直接处理待优化问题的参数，而是将它们转换成由基因按一 定结构组成的染色体或个体，即转化为对参数编码的处理。由于遗传算法被广泛 应用，迄今为止人们已经提出了许多不同的编码方法。总的来说，基本的编码方 法主要有二进制编码、浮点数编码和符号编码【2 8 1 。 3 2 1 二进制编码 二进制编码方式以( 0 ，1 ) 为基本字符集，个体的基因型有两种，分别是0 和1 。一个个体是一连串的二进制数。如11 0 11 0 1 0 1 0 是一个染色体长度为1 0 ， 采用二进制编码方式的个体。 二进制编码符号串的长度与问题所要求的求解精度有关，一般来说，长度越 长，精度越高。假设某一, 一。u m i n ，】，染色体长为，则总的 编码情况有2 7 种。 假设参数编码的对应关系如下： 0 0 0 0 0 0 0 0 0 0 0 0 ：o u m 缸 0 0 0 0 0 0 0 0 0 0 0 1 ：1 + 万 1 1 1 1 1 1 1 1 1 1 1 1 ：2 1 - 1 则二进制编码的编码精度为 万= 与挚( 3 - 1 ) 假设某个体x 的编码是：x ：6 ，岛一岛一z 6 2 岛 则对应的解码公式为： x 叱+ c 缸2 一) 与争 p 2 ) 1 7 第三章遗传算法 3 2 2 浮点数编码 在浮点数编码方案中，每个个体的基因值用某一范围内的浮点数表示，基因 位代表变量的取值，个体的基因长度等于决策变量的数目。 假设某优化问题包含4 个变量： z ( i = 1 ，4 ) ，其中每个变量的取值范围为【u m i n ，u m a x 】，则 rr ，r rj 就表示个体的基因型，其对应的表现型是：x = 【5 8 0 ，6 9 0 ，3 5 0 ，3 8 0 7 在浮点数编码方案中，种群中所有个体的基因值要在给定的区间范围内，个 体在进行交叉、变异等遗传操作后得到的新个体，其基因值也必须在规定的区间 范围内【2 3 】。 3 2 3 符号编码 符号编码方案是指群体中个体的基因值取自无数值含义而只有代码含义的 符号集【2 3 】。符号集可以是一个字母表，如( a ，b ，c ，d ，) ；也可以是一个 数字序号表，如( 1 ，2 ，3 ，4 ，5 ，) 等等。 十进制编码是符号编码的一种，其采用的符号集为十进制里的基本数字( o ， l ，2 ，8 ，9 ) ，每个参数对应一个数字，所有参数串连成一定长度的数字字 符串。在处理具体问题根据变量的取值选择合适的字符集大小，如果变量的取值 可能只有4 神，那么符号集就相应的为( 0 ，1 ，2 ，3 ) 。 对前例，如果采用十进制编码，按2 位小数位的精度编码时，该个体可表示 为如下： 第三章遗传算法 3 3 遗传算子 遗传操作是模拟生物进化过程，对种群中所有个体进行一定的操作得到新一 代的种群，通过迭代不断地产生新的种群，使问题的解，逐代优化，并最终得到 最优解。 在遗传算法中，选择合适的编码方式后随机产生初始群体，对种群中每个个 体按照它们对环境的适应度施加一定的遗传操作，从而模拟实现优胜劣汰的生物 进化过程。遗传算子主要包括选择算子、交叉算子和变异算子2 7 1 。 3 3 1 选择算子 选择操作是从群体中选择适应度高的个体，淘汰适应度低个体进入到接下来 的操作。其目的是把优秀的基因保存下来，通过直接遗传到下一代或者藉由交叉 操作得到新个体后遗传到下一代【2 引。常用的选择算子有：适应度比例方法、最 佳个体保存方法、期望值方法、排序选择方法、联赛选择方法等【3 1 1 。本论文采 用的是适应度比例方法结合最佳个体保存方法的方式。 ( 1 ) 适应度比例方法 适应度比例方法也称赌轮盘选择法。其个体的选择概率和适应度值之间为线 性正比例关系，个体的适应度值越大，其对应的选择概率也越大。假设群体规模 为m ，其中第f 个个体的适应值为f ，则其被选中进入接下来操作的概率为： f 成= 东( k 1 ，2 ，m ) ( 3 3 ) f 一 卜吖 ( 2 ) 最佳个体保存法 最佳个体保存法是指将群体中适应度最高的个体不进行遗传操作而直接复 制到下一代群体的方法。最佳个体保存策略的操作过程如下【2 9 】： i ：找出当前群体中适应度最高和最低的个体；若当前个体适应度比总的迄今 为止最好的个体适应度还要高，则用当前最优个体替代总的最优个体； 1 9 第三章遗传算法 i i ：用迄今为止最好个体替换最差个体。 采用此方法的优点是进化过程中某一代的最优解不被交叉和变异操作破坏， 是遗传算法收敛性的一个重要保证条件【2 3 】。 3 3 2 交叉算子 交叉操作是指对两个相互配对的染色体按照某种方式相互交换部分基因，从 而得到两个新个体。交叉运算是遗传算法中产生新个体的主要操作，在整个进化 过程中起着关键的作用 3 0 1 。交叉算子包括单点交叉、双点交叉等。本论文采用 的是单点交叉方式。 ( 1 ) 单点交叉 单点交叉时，随机设定一个交叉点，配对的个体交叉点后的基因串互换从而 得到两个新个体。具体操作用以下例子说明： 配对个体个体a0 0 ll i 101- 0 0 1 1 0 1 0新个体4 个体b 10o1 1 010- 1 0 0 1 1 0 1新个体 交叉点 a 和b 为两个配对个体，上例中，交叉点为5 ，交叉点后的部分基因串互换， 得到新的个体彳和。其中交叉点是随机设定的，对于长度为n 的染色体，可 以实现n 1 个不同的交叉结果。 ( 2 ) 双点交叉 与单点交叉类似，首先设置交叉点，其次将部分基因互换。与单点交叉不同 之处在于双点交叉的交叉点有两个，进行交换的是两个交叉点之间的基因串，具 体操作用例子表示如下： 配对个体个体a1 0 l 110 l 11 1 0 0 1 0 1 1新个体彳 第三章遗传算法 个体b00 l 01o l 00 0 0 11 0 0 0新个体b 交叉点l交叉点2 a 和b 为两个配对个体，上例中，随机设置了两个交叉点，个体a 和个体 b 在这两个交叉点之间的基因串相互交换，得到新个体4 ，b 。对于染色体长度 为n 的个体采用二点交叉，共有( n 一2 ) ( n 3 ) 种不同的交叉方式。 3 3 3 变异算子 变异算子是对群体中的个体的某些基因值作变动，以一定的概率将个体中基 因位的值变异为符号集中其他基本字符。 变异的基本步骤如下： ( 1 ) 以一定概率随机选定要变异的基因位； ( 2 ) 改动需变异的基因位的值。 变异操作使遗传算法具有局部随机搜索能力，并可维持种群的多样性，防止 算法过早收敛【3 l 】。 以下为变异的一个例子，其中第3 位和第6 位随机被选为变异位。 父代个体a1 0 0 1 1 1 1- 1 0 1 1 1 0 1子代个体4 。 遗传算法中，交叉算子因其具有全局搜索能力而作为主要算子，变异算子因 其局部搜索能力而作为辅助算子。遗传算法通过交叉和变异这一对相互配合又相 互竞争而使其具备兼顾全局搜索和局部搜索的均衡搜索能力【2 3 1 。 3 4 自适应遗传算法 在遗传算法中，交叉概率只和变异概率己的取值直接影响遗传算法性能的 好坏。对于交叉概率，如果选取得越大，个体产生的速度就越快，但同时 破坏模式的可能性也越大，这样就容易丢失掉良好的基因；但是如果过小，又 2 1 第三章遗传算法 会使得搜索过程缓慢甚至于停滞不前。而对于变异概率巴，如果己取值过小， 产生新个体的可能性也减小，如果已取值过大，那么遗传算法就变成了随机的 搜索算法【3 l 】。 s r i n v i v a s 等提出一种自适应遗传算法( a d a p t i v eg a ) 。当种群个体适应度趋 于一致或者局部最优时，只和己会自适应增加，否则，和己会自适应减少。 因此，自适应的只和己能够提供相对较好的只和己。 在自适应遗传算法中，和己按如下公式进行自适应调整3 1 1 ： _ 辫以厶p 4 ， i 红，厂 血 ni 掣序岛 已= 厶觚一岛加喀 ( 3 - 5 ) 【i 心，f 岛 公式3 4 和公式3 5 中， 厶觚代表群体中最大的适应值；无唱代表群体 适应值的平均数；f 代表配对的两个个体中较大的适应值；f 代表变异个体 其中参数向，也，岛，毛的取值范围是( 0 ，1 ) ，通过自行设定墨，如，屯， 包的值，就可以自适应地调整和己的值。自适应遗传算法中适应度值与、己 第三章遗传算法 p c k p m k 图3 2 自适应交叉概率( 后= j | 1 = 后2 ) 图3 3 自适应变异概率( 七= 七3 = | i 4 ) f f 由图3 2 和图3 3 可以看出，当适应度值低于平均数哪时，说明该个体是 性能较差，此时采用较大的和己；否则，说明该个体性能优良，此时取较小 的和已。、己的取值随着适应度值的增大而递减，对适应值最大的个体， 其交叉概率和变异概率减小至零。 适