（计算机科学与技术专业论文）tdscdma无线网络优化方法研究与应用.pdf

m st h e s i s r e s e a r c ha n d a p p l i c a t i o ni nt d - s c d m aw i r e l e s s n e t w o r k o p t i m i z a t i o n s p e c i a l t y ：c o m p u t e rs c i e n c e & t e c h n o l o g y m a s t e r d e g r e ec a n d i d a t e ：g u a n j i nw a n g s u p e r v i s o r ：p r o f c o n g x uz h u c o l l e g eo f i n f o r m a t i o ns c i e n c e & e n g i n e e r i n g c e n t r a ls o u t hu n i v e r s i t y c h a n g s h ah u n a n p r c 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：圣兰全日期： 型! 呈年三月罩日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名：王缝 导师签名桠日期：塑年金月乒日 摘要 扇区天馈优化和扰码优化是t d s c d m a 无线网络优化中的重要 环节，直接影响到无线网络的性能。如今，无线网络规模不断扩大， 小区密集度越来越高，无线环境越来越复杂，网络优化难度越来越大， 同时用户对无线网络的质量要求越来越高。网络优化工程师在很大程 度上都需要借助相应的优化软件，因此，利用无线网络优化工具提供 优秀的网络优化方案成为网络优化的趋势。 建立了扇区优化问题的数学模型，通过研究天线方位角、下倾角 和发射功率对无线网络覆盖的影响，建立了扇区参数的评估方法；针 对扇区优化问题为组合优化问题的特点，选择遗传算法作为扇区优化 算法，设计了二进制矩阵式编码，对交叉方法进行改进，设计了基于 分块的交叉方法。 针对扰码优化问题建立了扰码优化的数学模型，对扰码的干扰原 理进行了分析，建立扰码方案的评估方法，鉴于扰码优化问题足组合 优化问题，选择了遗传算法作为扰码优化算法，同时采用了基于分块 的交叉方法，利用禁忌搜索方法对变异算子进行改进，加快收敛速度。 为了验证算法性能，选择了两个城市的实际网络分别对扇区优化 算法和扰码优化算法进行了实验验证。扇区优化问题的评估指标 p c c p c hr s c p 、p c c p c hc i 和导频污染均有不同程度的提升，过覆 盖没有变化，达到预期目标。对扰码性能的评估结果是扰码k p i 覆盖 指标、下行导频码k p i 覆盖指标和b q 指标均有不同程度的提升，实 验表明，算法能够满足实际工程的要求。 关键词网络优化，t d s c d m a 标准，扇区优化，扰码优化 a b s t r a c t c e l l o p t i m i z a t i o na n ds c r a m b l ec o d eo p t i m i z a t i o n i s i m p o r t a n t s t a g ed u r i n gt h et d s c d m a w i r e l e s sn e t w o r ko p t i m i z a t i o n ，a n dt h e n o b t a i n sas a t i s f y i n gn e t w o r k sq u a l i t y t o d a y ，t h ea m o u n to fn e t w o r ki s i n c r e a s i n g ，c e l l sa r em o r ei n t e n s i t ya n dt h et a s ko fn e t w o r ko p t i m i z a t i o n i sh a r d e r ；m e a n i n gw h i l e ，m o b i l ep h o n eu s e rr e q u e s tm o r eh i g hq u a l i t y n e t w o r k e n g i n e e r sl a r g e l yd e p e n d o n c o r r e s p o n d i n go p t i m i z a t i o n s o t t w a r ei nt h en e t w o r ko p t i m i z a t i o nw o r k w ec o u l dc o n c l u d et h a ti ti sa t r e n dt h a tp r o v i d ee x c e l l e n ts c h e m eb yc e l lo p t i m i z a t i o nt o o l s o n em a t h e m a t i cm o d e lo fc e l lo p t i m i z a t i o ni ss e tu p r e s e a r c ht h e r e l a t i o nb e t w e e na z i m u t h ，d o w nt i l ta n dt r a n s m i t t e dp o w e ra n dt h e n e t w o r kc o v e r a g e ；p r o p o s et h ec e l lp a r a m e t e re v a l u a t em e t h o d s i n c ec e l l o p t i m i z a t i o np r o b l e mi s c o m b i n a t o r i a l o p t i m i z a t i o np r o b l e m s ，g e n e t i c a l g o r i t h mi s u s e dt os o l v et h i sp r o b l e m g e n e t i ca l g o r i t h mh a sb e e n d e v e l o p e dw h i c hc h r o m o s o m ec o d e db yb i n a r ym a t r i x f o rg e t t i n ga r a p i dc o n v e r g e n c e ，as p e c i a lc r o s s o v e rm e t h o dn a m e dp a t c h c r o s s o v e r h a sb e e np o s t e d s c a l i n gf u n c t i o na p p l i e dt ot h ef i t n e s sf u n c t i o nt oa v o i d l o c a lc o n v e r g e n c e o n em a t h e m a t i cm o d e lh a sb e e ns e tu pf o rt h es c r a m b l ec o d e o p t i m i z a t i o np r o b l e m ；a n do n ee v a l u a t em e t h o dh a sb e e np r o p o s e da f t e r a n a l y s i s t h e p r i n c i p l e o ft h ei n t e r f e r e n c e s i n c es c r a m b l ec o d e o p t i m i z a t i o n i sc o m b i n a t o r i a l o p t i m i z a t i o np r o b l e m s ，a na l g o r i t h m c o m b i n eg e n e t i ca l g o r i t h ma n dt a b us e a r c hb e u s e dt os o l v et h e s c r a m b l ec o d ep l a n n i n gp r o b l e m f o rg e t t i n gar a p i dc o n v e r g e n c e ，a s p e c i a lc r o s s o v e rm e t h o dn a m e dp a t c h c r o s s o v e rh a sb e e np o s t e d t o a v o i db l i n ds e a r c h ，t a b us e a r c hw a su s e df o rt h ei n d i v i d u a lm u t a t i o n w es e l e c t e dt w oe x p e r i m e n t a ln e t w o r k si nt w oc i t yi n d i v i d u a lt ot e s t t h ec e l lo p t i m i z a t i o na l g o r i t h ma n dt h es c r a m b l ec o d ea l g o r i t h m t h e r e s u l to fc e l lo p t i m i z a t i o ni sp r e s e n t e da n dt h eo u t s t a n d i n gp e r f o r m a n c e o ft h i s o p t i m i z a t i o na l g o r i t h m i si l l u s t r a t e d t h ep c c p c hr s c p c o v e r a g er a t i o ，p c c p c hc ic o v e r a g er a t i o ，p i l o tp o l l u t i o ni n d e xa n d o v e rc o v e r a g ei n d e xi n c r e a s e i n d i v i d u a li nd if f e r e n td e g r e e m e a n i n g w h i l e ，t h es c r a m b l ec o d ek p i ，d o w n l i n kp i l o tc o d ek p ih a si m p r o v e d a n dt h ep c c p c hi n t e r f e r eb a d q u a l i t yd e c r e a s e di nd i f f e r e n td e g r e e k e yw o r d sn e t w o r ko p t i m i z a t i o n ，t d s c d m as t a n d a r d ，c e l l o p t i m i z a t i o n ，s c r a m b l ec o d eo p t i m i z a i t o n 目录 摘要i a b s t r a c t i i 第一章绪论1 1 1 论文选题背景1 1 2 扇区优化研究现状分析2 1 3 扰码优化的研究现状分析3 1 4 论文主要工作6 1 5 论文组织结构6 第二章t d s c d m a 网络优化相关技术8 2 1 遗传算法8 2 1 1 算法介绍8 2 1 2 遗传算法类库g a l i b 1 0 2 2 禁忌搜索算法1 2 2 2 1 算法介绍1 2 2 2 2 禁忌搜索算法类库m e t s l i b 13 2 3 传播模型校正与覆盖仿真分析1 5 2 3 1 传播模型校正1 5 2 3 2 覆盖仿真分析1 7 2 4 本章小结1 9 第三章扇区优化和扰码优化数学模型2 0 3 1 扇区优化2 0 3 1 1 扇区优化的数学模型2 0 3 1 2 自动扇区优化2 2 3 2 扰码优化2 5 3 2 1 扰码优化的数学模型2 7 3 2 2 自动扰码优化2 9 3 3 本章小结3 2 第四章基于改进遗传算法的t d s c d m a 自动扇区优化3 3 4 1 改进的扇区优化算法3 3 4 1 1 编码与初始解3 3 4 1 2 交叉与变异3 4 4 1 3 选择操作与评价函数3 6 4 2 实验结果与分析3 6 4 3 本章小结4 4 第五章基于遗传算法与禁忌搜索的t d s c d m a 扰码优化4 5 5 1 扰码优化算法4 5 5 1 1 遗传算法与禁忌搜索算法比较分析4 5 5 1 2 编码与初始解一4 5 5 1 3 交叉与t s 变异4 6 5 1 4 选择操作评价函数4 8 5 2 实验结果与分析一4 8 5 3 本章小结5 5 第六章总结与展望5 6 6 1 总结5 6 6 2 展望5 7 参考文献5 8 致谢6 2 攻读硕士期间从事的科研工作及取得的研究成果6 3 硕士学位论文 第一章绪论 1 1 论文选题背景 第一章绪论 中国移动通信用户数增幅和t d s c d m a 基站建设速度都非常迅速。2 0 0 9 年 中国手机用户突破7 4 亿户，3 g 用户突破1 0 0 0 万户，t d 用户突破5 0 0 万户， 移动通信已经成为人们的首选的通信方式，推动着经济增长和社会发展。 t d s c d m a 网络建设方面，第一期的网络建设期间，为满足2 0 0 8 年北京奥运会 通信的要求，中国移动在l o 个城市完成1 4 万个基站的建设；在2 0 0 8 年7 月开 始的第二期网络建设中，新增了2 8 个城市的网络建设规模，第三期的网络建设 将扩大到2 0 0 个城市。海外推广方面，t d s c d m a 已经在韩国、意大利、加拿 大、罗马尼亚、加纳、缅甸等国家和地区建立了多个国际t d s c d m a 试验网和 试验系统，预示着中国提出的3 g 国际标准t d s c d m a 已经驶入了快速发展的 轨道。 t d s c d m a 网络的快速建设的同时，没要太多的关注网络的覆盖问题，导 致网络建设好的初期出现很多覆盖空洞，比如p c c p c h 弱覆盖，c i 弱覆盖，导 频污染，过覆盖等。由于网络没有做到无缝覆盖，用户反映最多的问题是信号不 好问题，语音电话出现打不通、有时断线、声音不好等问题、可视电话有马赛克 等现象，使得用户对t d s c d m a 网络留下了不好的印象。因此在网络建没后期 急需对网络进行全方位的优化，以提供用户的感知度。 尽管t d s c d m a 网络还存在不少问题，但是这并没要打消中国通信产业界 包括中国移动、各设备厂家及各网络优化公司对建设高质量的t d s c d m a 的信 心。目前，大规模的网络优化工作正在紧锣密鼓的进行着。 t d s c d m a 网络优化的手段主要有1 2 l ：工程参数优化和系统参数优化。工 程参数包括工程设计、安装和丌通有关的参数，如天线增益、天线型号、站址、 电缆损耗、天线方位角、天线下倾角以及天线安装高度等参数。工程参数的调整 工作量比较大，例如站点调整需要结合网络规划来考虑，周期较长；天线高度调 整涉及到天馈改造等。不过工程参数对网络性能的影响比网络资源参数更直接， 更具决定意义。因此，对于类似天线方向、下倾角等相对较易调整参数可尽量优 先调整，这对改善越区覆盖等容易对t d 网络产生重要影响的问题有立竿见影的 效果。频率和扰码是t d s c d m a 系统中的重要无线资源f 3 j 。频率规划是指在网 络建设过程中根据某地区的话务量分布而分配相应的频率资源以实现有效覆盖 和业务量的承载。我们知道，在移动通信系统中，各种信息是通过载波作为载体 在终端和基站问进行传输。对有用信号来说，其他系统、载频、用，、的信号都是 硕士学位论文第一章绪论 干扰信号，尤其是相同频率同码字的信号干扰更强。在g s m 网络中，同频干扰 会造成信号质量差，话音质量大幅度的下降；在c d m a 网络中，干扰就会消耗 网络系统容量，迫使干扰电平增加。最终结果都是网络性能下降，用户满意度降 低。 t d s c d m a 系统采用了智能天线等技术，可以通过波束赋形的技术来避免 其他用户对当前用户的干扰。但是干扰还是不能够完全避免，因为由于无线传播 环境的复杂性，不可避免的产生多径和时延，这就导致t d s c d m a 系统中依然 存在一定的同频和邻频干扰，因此，需要对频率和扰码进行详细的规划。 目的国内很多地方网络优化还主要采用人工方法，通过人工经验给出方案。 而我国移动通信建设发展之快世间罕见，现在国内不少城市一直处于新建、扩容、 再扩容不断发展的阶段，往往第一期扩容尚未完成，第二期扩容又要开始。随着 扩容，基站参数的变动以及一些其它因素，网络中天馈参数资源要进行局部或全 面的改动，全部靠人工经验设计，但是这个过程工作量大，耗时长，效率低下， 非常容易出错，之后必须反复检查，但是很难达到全局优化，只能局部达到要求。 人们急需一套高效的、令人满意的且价格低廉的自动网络规划与优化软件以摆脱 繁重的手工设计工作【4 】【5 1 。 近年来，随着数字地图的普及同时精细化程度越来越高，为通过计算机软件 参与规划和优化提供了便利，特别是网络实际测量数据的引入参考，是的网络优 化更加准确，贴近实际，因此传统的人工规划和优化方法已经很难适应网络快速 建设的需求，通过软件参与规划和优化是大势所趋。 提出的网络优化算法就是为了解决网络优化过程中碰到的问题，加快网络优 化的进度，为运营商节约网络成本，提供用户感知度。通过提出的算法，开发出 相应的网络优化工具，满足现场工程的需求。 1 2 扇区优化研究现状分析 网络优化就是对无线网络的天馈参数、无线设备参数进行调整，从而使得无 线网络在无线覆盖、网络容量、系统性能等方面达到最优化的过程。无线网络优 化主要经过下述几个步骤： 首先设定网络质量目标，即设定k p i 指标。这些指标的数据来源有：网管 系统；路测设备；协议分析仪；用广t 投诉数据。再由软件工具对收集到的数据进 行分析，通过人工经验提出解决这些问题的方法。 其次是参数优化，反复调整某砦参数，直到最后达到预期质量目标为止，就 得到了整体解决方案。按照整体方案对网络进行伞而调整后。目前，在r 常网络 2 硕士学位论文 第章绪论 天馈优化过程中，由塔工负责在基站上面调整方位角、机械下倾角，同时网优人 员跑路测验证分析测量数据，根据分析的结果确定是否还需要调整天馈参数、怎 么调，通知塔工进行调整。这个过程完全依据网优人员的经验，塔工听从网优人 员的建议反复调整试验，反复路测，直到达到预期效果为止。但是这种方式效率 非常低下，有一定的盲目性，依赖于网优人员的经验，极有可能调整的方案达不 到预期的效果。 随着无线网络技术的发展，无线网络优化的基本思路和步骤没有发生变化， 但是网络的规模越来越大、复杂性越来越高、优化的工作量越来越大，同时优化 工期要求尽可能的缩短。传统的优化方法不再满足现场优化的需要。随着一些新 技术的发展，使得无线网络优化邻域的创新看到了曙光，比如g i s 技术，智能 算法的出现，使得网络优化精确性有了更加进一步的提耐6 1 。 随着通信技术及计算机计算技术的发展，在欧洲和美国率先提出了自动扇区 优化( a u t o m a t i cc e l lp l a n n i n g ) 的概念，即采用根据相关的网络工程参数数据、无 线传播模型、及网络质量方针评估，通过计算机软件来搜索最优或者较优的天馈 方案。由于w c d m a 为欧洲的3 g 标准，c d m a 2 0 0 0 为美国的3 g 标准，因此 国外研究者对这两个标准的自动扇区优化算法进行了大量的研究1 7 儿引，也产生了 不少的自动扇区优化工具。天馈优化问题是典型的n p 。c o m p l e t e 问题。文献桫j 采用改进的模拟退火算法，通过优化g s m 的前向链路发射功率、方位角和机械 下倾角三个无线参数，使得覆盖( c o v e r a g e ) 、容量( c a p a c i t y ) 和服务等级( q u a l i t yo f s e r v i c e ) 达到最佳。w c d m a 标准的相关研究中，文献l l o l 针对不同的业务类型， 比如语音业务、多媒体业务等，通过系统仿真，分析下倾角、天线波瓣宽度这两 个参数对不同业务的影响。文- 献【i 采用线性规划的方法对w c d m a 系统的导频 发射功率进行优化，使得满足覆盖要求的同时不至于产生严重的过覆盖。文献1 1 z j 以提高网络的覆盖质量同时尽可能降低运营商投资成本为优化目标，采用随机搜 索算法、爬山搜索算法、局部搜索算法对网络扇区进行优化。站址优化时移动通 信中的一项非常有经济意义的任务，以尽量少的站址满足覆盖，可以为运营商节 省开支，文献【1 3 】从候选站址中选择最少的站来满足覆盖，转化为最小击中集问 题。采用了贪心算法、进化算法和基于孤岛的遗传算法求解最小击中集问题 1 1 4 】【1 5 】【1 6 】；采用遗传算法对基站进行选址，优化目标是覆盖范围、系统容量和覆 盖信噪比质量。 1 3 扰码优化的研究现状分析 t d s c d m a 采用了c d m a ( 码分多址) 技术【 i ，c d m a 技术的 现源r - a f l q 硕士学位论文 第一章绪论 对更高质量无线通信的需求。第二次世界大战期间因战争的需要，开发出了防止 敌方干扰的c d m a 系统，后来由美国高通公司更新成为商用蜂窝电信技术。后 来的3 g 标准c d m a 2 0 0 0 和t d s c d m a 都采用了此技术。因此在c d m a 2 0 0 0 和t d s c d m a 中都需要对码进行合理的分配。码的分配问题和g s m 频率问题 一样，都是组合优化问题【1 引。t d s c d m a 系统的码资源【1 9 j 包括：3 2 个s y n c d l 、 2 5 6 个s y n c u l 、1 2 8 个m i d a m b l e 、1 2 8 个s c r a m b l i n g 。所有码被分成3 2 个码 组，每个码组由1 个s y n c d l 、8 个s y n c u l 、4 个m i d a m b l e 、4 个s c r a m b l i n g 组成。不同的邻近小区将使用不同的码组。对u e 来说，只要确定了小区使用的 s y n c d l ，也就知道该小区使用哪些s y n c u l 、m i d a m b l e 、s c r a m b l i n g 。由于 t d s c d m a 的扰码长度比较短，并且系统的扩频因子比较小，不同小区间的复 合码就存在重合的情况，因此容易产生干扰，需要进行合理的分配。 目前，码分配算法的研究算法有f 2 0 j f 2 1 1 1 2 2 】【2 3 l ：基于复用簇的码分配算法，基 于图着色的码分配算法，采用基于仿真的码分配算法。 ( 1 ) 基于复用簇的码分配算法 复用簇的码分配原理就是利用蜂窝原理，在有限的码资源情况下提高系统容 量。为了实现蜂窝结构，把所需要的覆盖范围划分成许多称为小区的区域，利用 传输过程无线电波衰耗随距离增加而增加的特性，让同一个码在相隔足够远的小 区中重复使用。这种分配算法的步骤是：a 、定义好复用簇，b 、给簇内小区分配 扰码，c 、按照簇的拓扑外延方法给小区分配扰码。 这种方法主要使用于分布比较均匀，而且蜂窝小区朝向基本一致的蜂窝网 络，主要使用于建网初期的网络规划阶段。但是实际的网络往往是非常不规整， 而且朝向非常不一致的，因此提出了如下码分配方法。 ( 2 ) 基于图着色的码分配算法 对于分布不规则的复杂网络，复用簇的分配方法得不到好分配方案，因此后 来又提出了基于图着色模型的分配算法。在实际网络中，由于无线信号随着距离 增大产生衰减，因此在距离足够远的两个小区可以复用相同的扰码。即：随着距 离的增大，扰码的正交性要求降低。算法的步骤如是：建立小区的扰码相关性约 束矩阵，矩阵元素口f ，表示小区f 与小区，的扰码相关性不能高于q 。通过约束矩 阵可以建立带权的无向图，边的权就是矩阵的元素口一已经证明图着色问题是 4 硕士学位论文 第一章绪论 n p 完全问题1 2 4 1 ，已经提出许多求解n p 完全问题的方法，比如局部搜索算法、神 经网络算法、模拟退火算法以及遗传算法。 ( 3 ) 基于仿真的码分配算法 基于仿真的码分配算法与基于图着色的码分配方法的区别之一在于扰码正 交性的获取，且基于仿真的码分配算法考虑了多径信号的影响。原来正交性很好 的两个码，由于多径影响，导致正交性变差；这类问题可以通过仿真来发现。这 个算法对小区间的扰码干扰进行仿真，获得更加精确相关性，然后采用已有的图 着色算法进行求解。 t d s c d m a 标准由中国大陆提出，国内研究机构对t d s c d m a 的扰码分 配算法进行了大量的研究，主要设备生产商也提出了自己的算法【2 5 1 。 大唐移动算法【2 5 1 ： ( 1 ) 确定码规划的小区优先级；确定某个小区的优先级别原则为小区的邻区 总数、已分配扰码的邻区，如果邻区数目越多，认为可能的干扰就越大，给此小 区分配合适的扰码越困难，分配优先级就越高。 ( 2 ) 下行导频码的分配；考虑相同的下行导频码复用距离尽量远，邻小区使 用不同的下行导频码。 ( 3 ) 扰码和其他码字的分配；下行导频码确定后，根据扰码的相关性来选取 最适合的扰码，然后根据码组的对应关系可以确定其他码字。 中兴通讯算法【2 5 l ： ( 1 ) 设定邻小区的复合码相关性值门限，保证在一定距离范围内复合码相关 性大的扰码不能被复用；复合码为扰码与扩频码的乘积，实际网络中式复合码相 关性决定系统性能而不是扰码相关性。 ( 2 ) 对小区分配扰码，原则是不将复合码相关性大的扰码分配给相邻小区， 同时邻小区之间的复合码相关性要低于设定的门限。 ( 3 ) 根据扰码的分配结果确定其他码字。 普天通信算法1 2 5 l ： ( 1 ) 对当前某个待分配扰码的小区，对它的邻区按照优先级别大小进行排序， 距离越小，优先级越高。 ( 2 ) 寻找合适的扰码；搜索与邻区扰码满足互相关性要求的扰码，充分考虑 硕士学位论文第一章绪论 同扰码的复用距离、同频同扰码的复用距离、同频同下行导频码的复用距离，以 降低干扰。如果没有合适扰码满足要求，则降低复用距离的要求，最终确定小区 最适合的扰码。 ( 3 ) 根据扰码的分配结果确定其他码字。 以上提到的不同算法都有一个共同的特点，就是扰码分配要充分考虑扰码相 关性，相邻小区不能出现强相关性码字。但是所用的算法基本都是采用局部搜索 的方式，很难得到最优解。鉴于t d - s c d m a 网络在中国刚刚开始运营，后期难免有 更多的问题，因此需要研究更好的扰码分配算法。 1 4 论文主要工作 扇区优化、频率优化和扰码优化是t d s c d m a 网络优化的重要环节，占据 了网络优化的大部分工作。t d s c d m a 频率优化与g s m 标准的频率优化类似， 而且g s m 的频率优化问题已经做了大量的研究工作，因此将重点放在扇区优化 和扰码优化。 深入研究了遗传算法、t d s c d m a 覆盖仿真原理和扰码的干扰原理，主要 完成了一下几方面的工作： ( 1 ) 深入研究遗传算法，对遗传算法的相关操作算子进行改进，以适应扇区 优化和扰码优化的要求。 ( 2 ) 深入研究t d s c d m a 系统仿真相关原理，建立了扇区优化的评估方法， 进而建立算法的适应度函数。 ( 3 ) 深入研究t d s c d m a 系统的扰码干扰原理，建立扰码方案的评估方法， 进而建立算法的适应度函数。 ( 4 ) 利用研究成果，开发两款t d s c d m a 网络优化工具：a c pt d s c d m a 和 f p ot d s c d m a 。 1 5 论文组织结构 本论文组织结构如下： 第一章介绍了研究背景及主要的工作，以及自动扇区优化和扰码优化的发展 状况。 第二章介绍遗传算法和禁忌搜索算法的相关理论，对传播模型校币和覆盖仿 真方法进行了阐述。 6 硕士学位论文 第一章绪论 第三章建立了扇区优化和扰码优化的数学模型。 第四章遗传算法在扇区优化中的应用，详细介绍扇区优化的基本思路、算法 和评估方法。 第五章遗传算法在扰码优化中的应用，详细介绍扰码优化的基本思路、算法 和评估方法。 第六章对本文进行了总结，提出改进方向。 7 硕士学位论文第二章t d - s c d m a 网络优化相关技术 第二章t d s c d m a 网络优化相关技术 本章讲述在本项目中用到的相关技术背景，包括如下内容： ( 1 ) 遗传算法相关理论，以及本项目用到的遗传算法开源框架库g a l i b ； ( 2 ) 禁忌搜索相关理论，以及本项目用到的禁忌搜索开源框架库m e t s l i b ； ( 3 ) 传播模型校正相关知识和基本步骤； ( 4 ) 扇区优化方案和扰码优化方案涉及到的t d s c d m a 覆盖仿真指标； 2 1 遗传算法 本小节介绍遗传算法原理，以及本课题中使用到的遗传算法类库g a l i b 。 2 1 1 算法介绍 7 0 年代，j h h o l l a n d 教授等人根据达尔文进化论、孟德尔和摩根的遗传学 理论得到启发，提出遗传算法( g e n e t i ca l g o r i t h m 简称g a ) 的概念f 2 6 l 。提出用位 串来表示复杂的结构，并用变换来改变这种结构的方法，以此模拟生物进化的机 制，同时证明了遗传算法可以在搜索空间中收敛到全局最优解。同时，美国 d e j o n g 博士用遗传算法来求解函数的最优解，验证了遗传算法的实用性1 2 7 1 。1 9 8 0 年，遗传算法被用于机器学习邻域，且研制出了一种被称为分类器的系统。1 9 8 9 年，g o l d b e r g 通过写书1 2 8 】对遗传算法做了详细的阐述。此后，许多学者对遗传 算法做了改进，在各个邻域出现了遗传算法的成功应用，包括机器学习、模式识 别、神经网络、控制系统优化1 2 9 1 1 3 0 】1 3 1 1 。在人工生命邻域，研究人员将遗传算法 与计算机科学相结合，试图模拟自然界的自适应、自组织和再生能力，设计出具 有生命”的人工系统1 3 2 】1 3 3 】。 1 遗传算法的基本概念【3 4 1 ( 1 ) 个体：是遗传算法中用来模拟生物染色体的二进制位串； ( 2 ) 种群：一定数目的个体的集合； ( 3 ) 种群规模：种群中个体的数量； ( 4 ) 位串：个体的表现形式，在算法中为二进制串； ( 5 ) 基因：基本遗传单元，表示不同的生物特征； ( 6 ) 适应度：个体优劣程度指标的数值描述； ( 7 ) 平均适应度：是多于个个体适应度值的算术平均值； ( 8 ) 繁殖：由一代种群繁衍产生另一代种群的方式；繁殖方式包含选择、交 叉、变异等； 8 硕士学位论文第二章t d - s c d m a 网络优化相关技术 ( 9 ) 复制：指在父代种群中挑选出一定数量的参与繁殖下一代种群的个体； ( 1 0 ) 选择：以一定概率从种群中选出若干个体的过程； ( 1 1 ) 交叉：指对优选后的父代个体进行基因模式的重组而产生后代个体的繁 殖机制；在个体繁殖过程中，交叉能引起基因模式的重组，从而有可能产生含优 良性能的基因模式的个体； ( 1 2 ) 变异：指模拟生物在自然界的遗传进化环境中由于各种偶然因素引起的 基因模式突然改变的个体繁殖方式； ( 1 3 ) 编码：从表现型到基因型的映射： ( 1 4 ) 解码：从基因型到表现型的映射。 2 遗传算法的主要运行步骤 采用遗传算法求解优化问题，包括如下步骤： ( 1 ) 编码方法 根据不同的问题确定编码方法，有实数编码、二进制编码等。 ( 2 ) 创建初始种群 ( 3 ) 计算个体的适应度 ( 4 ) 执行如下操作： 选择，用子代的优秀个体替换父代的劣质个体； 交叉，通过优秀的父代生成子代； 变异，改变某个个体的基因，形成新的个体，添加到新鲜个体中。 ( 5 ) 反复执行( 3 ) 和( 4 ) ，直到满足条件为止。 遗传算法的一般流程如图2 一l 所示，其中包含如下四个主要步骤： 图2 - 1 遗传算法的基本流程 3 遗传算法的主要特点1 3 5 l 在寻求解决各种优化问题的过程中，人们提出了各种各样的优化算法，如单 纯形法、梯度法和动态规划法等。这些优化算法有各自的优劣、应用场景和使用 范围。但足遗传算法是一中可以用于求解复杂优化问题的搜索算法，它t 要有下 述几个特点： 9 硕士学位论文第二章t d - s c d m a 网络优化相关技术 ( 1 ) 以变量的编码形式作为基本操作对象。不同于其他大多数优化算法直接 用决策变量的实际值来参与计算的特点，遗传算法是采用决策变量的编码形式为 运算对象。这些编码后的对象正好体现了基因和染色体等概念。达到模仿自然界 中生物遗传和进化的目的。在这方面，编码体现了极大的优越性。 ( 2 ) 遗传算法仅仅以目标函数值来判断解的优劣。在解决实际的优化问题过 程中，有很多函数很难求出其导数信息，特别是一些组合优化问题，甚至有的问 题写不出函数表达式，比如一个仿真系统。在这种情况下就很难用传统的优化算 法求解。因为很多传统的优化算法需要知道函数的表达式和导数信息，这些恰是 传统优化算法的不足。而遗传算法仅仅需要知道函数的值，就可以对其进行优化， 在优化过程中，遗传算法将函数值或者系统评价值进行变换，得到适用于算法的 适应度值，就可以指导算法进行优化。这一特点是遗传算法的大特点。 ( 3 ) 遗传算法搜索具有并行性。 遗传算法具有并行性，主要体现在它的搜索过程是从一个种群迭代到另外一 个种群的过程，通过选择、交叉和变异产生出新的种群，这个过程是通过整合多 个个体的信息完成的，也就是参考了多个点，并非传统方法中从一个初始点迭代 到最优点的搜索过程，如果第一个点选择不好，往往就容易陷入到局部最优解。 ( 4 ) 遗传算法属于概率搜索。 遗传算法属于概率搜索，体现在它的选择、交叉和变异算子都是以概率方式 进行的，可以很大程度上避免陷入局部最优解，传统优化算法的一个点到另外一 个点的转移关系和转移方法是确定的，这样可能永远达不到最优解。 2 1 2 遗传算法类库g a l i b g a l i b 是用c + + 开发的遗传算法开源库，由美国m i t 的m a t t h e ww a l l 丌发 完成。下面将对其特征及使用方法加以介绍【3 6 l i 3 7 1 。 g a l i b 中主要类介绍 g a l i b 的派生关系见图2 2 。 l o 硕+ 学位论文 第二章t d - s c d m a 网络优化相关技术 翱喇嘲陶哪_ 铀h | a _ 喇m 州鹂棚叫榭， i 鑫嘲州嗤舢啊函崎_ 时 图2 - 2g a l i b 类继承图 1 g a g e n o m e 基因组类 实际问题在使用遗传算法之前，一定要确定问题的编码形式。编码必须和问 题所有可能解一一对应。 基因组类( g a g e n o m e ) 是进化个体的基类，由其派生的子类对应着问题的具 体编码形式。g a l i b 提供了四种子类：链表型( g a l i s t g e n o m e ) 、树型 ( g a t r e e g e n o m e ) 、数组型( g a a r r a y g e n o m e ) 和二进制串i 亍( g a b i n a r y s t r i n g ) 。用 户可以根据问题需要进行选择。 基因组类包含三个主要算子的默认实现方法：初始化、变异和交叉操作。初 始化过程可以自动生成个体的值，用户也可以实现自己的初始化方法；变异和交 叉方法也可以由用户根据具体的问题场景自己重新实现，改写这些算子的实现方 法。 2 g a s c a l i n g s c h e m e 适应度定标函数 遗传算法的一个主要优点利用计算函数数值直接进行搜索。在使用目标函数 值之前，需要采用适应度定标函数对其进行处理，比如有的函数值为负数，但是 在采用赌轮选择方法时需要进行非负处理；同时还包含其他目的的处理。 3 g a p o p u l a t i o n 群体类 群体类( g a p o p u l a t i o n ) 是个体的集合，多个个体组成一个种群。种群类包含 了初始化种群的实现方法和评估算子的实现方法，默认的初始化算法实现方法为 每个个体的初始化实现方法，默认评估方法为每个个体的评估方法。种群类还可 以记录优化过程t ，的最佳个体、最佳个体的适应度值等。 附岫汕 描 m一 一 基 曩llriiliillil g 1一啾 鹾一 硕士学位论文第二章t d - s c d m a 网络优化相关技术 4 g a g e n e t i c a l g o r i t h m 遗传算法类 遗传算法类( g a g e n e t i c a l g o r i t h m ) 包含的功能和方法有：对重要参数的统计， 进化策略的方法时下你，终止策略，用户可以根据问题的实际情况改写这些方法。 g a l i b 提供了四种遗传算法： 标准遗传算法( g a s i m p l e g a ) ，该算法要么只保留父代的最佳个体，要么不 保留父代的任何个体，子代完全通过交叉和变异得到。 稳态遗传算法( g a s t e a d y s t a t e g a ) ，父代的个体被保留到子代中，子代的个 体包含父代的原始个体和通过交叉和变异生成的新个体，两类个体按照一定的比 例存在。 增量遗传算法( g a i n c r e m e n t a l g a ) ，每次只生成一个或者两个新的个体，用 这些新个体将父代中通过某种方法挑选出来的同样数目的个体替换掉，挑选方法 可以为随机挑选，最大相似度挑选和最差个体挑选等； 种群遗传算法( g a d e m e g a ) ，这是一种并行遗传算法。多个种群可以统计进 行进化，并且每个种群采用的是稳态遗传算法，种群之间的个体相互迁移，相互 替换。 2 2 禁忌搜索算法 本小节介绍遗传禁忌搜索原理，以及本课题中使用到的禁忌搜索算法类库 m e t s l i b 。 2 2 1 算法介绍 早在1 9 8 6 年，g l o v e r 提出了禁忌搜索算法的思想3 8 l p 9 1 。对人类智力过程进 行模拟，是一种全局逐步寻优算法，是局部搜索的一种扩展。引入了灵活的存储 结构和相应的禁忌