（应用数学专业论文）基于遗传算法的选播路由算法研究.pdf

河南大学研究生硕士学位论第1 页 摘要 选播( a n y c a s t ) 是i p v 6 中的一种标准通信模型，可以实现一台主机与一组 具有相同选播地址的目的主机中“最近”的一台主机进行通信( 这组目的主机提 供相同的服务) 。选播服务的主要功能是允许用户根据需要做出合适的选择，因此 路由问题是选播技术的关键问题，它直接决定了网络服务的可用性和效率的高低。 具有时延约束和代价要求的选播路由问题是一个n p 完全问题，遗传算法通 常用于解决此类问题。“早熟”收敛是遗传算法在实际应用中常见的一个疑难问题， 主要表现为种群中最优个体的适应度值得不到提高，种群在经过若干迭代后仍找 不到最优解，而造成“早熟 的主要原因是群体多样性的过早缺失。 本文在深入分析和研究选播服务模型和选播路由算法的基础上，针对上述问 题，给出了一种基于改进的遗传算法的选播q o s 路由算法。该算法可以解决具有 时延约束的条件下要求代价最小的选播路由问题。 本算法把遗传算法应用于选播q o s 路由问题中，发挥其并行性和群体寻优的 特点；引入相异度的思想改进交叉算子和变异算了来增加群体的多样性；利用模 拟退火理论调整和改进适应度函数，使得种群中个体的适应度值在进化过程中得 到明显提高；改进了初始种群的生成方法，使其生成多样化且“起点较高的初 始种群。从而抑制“早熟”收敛的发生。 为了验证算法的有效性和收敛性，本文有针对性地设计一个仿真实验平台， 并实现了该算法的仿真。大量仿真实验表明，本算法能够从多个选播成员中找到 满足选播q o s 请求( 满足时延限制，且代价最小) 的最优路径为用户提供服务， 且算法是有效和收敛的，较好的解决了“早熟”收敛问题。通过对比仿真实验数 据，证明了本算法具有较快的收敛速度，且提高了找到最优解的成功率。 关键词：遗传算法；i p v 6 选播：服务质量；路由算法；相异度 第1l 页 河南大学研究生硕士学位论文 a b st r a c t a n y c a s ti sd e f i n e da s as t a n d a r dn e t w o r ks e r v i c eo fi p v 6 ( i n t e r n e tp r o t o c o l v e r s i o n6f o rn e x tg e n e r a t i o nn e t w o r k ) i ti sd e s i g n e dt oa l l o wu s e r st os e l e c ta n d c o m m u n i c a t i o nt ot h e n e a r e s t ”s e r v e ri nag r o u po fc o n t e n t e q u i v a l e n ts e r v e r sw h i c h h a v et h es a m ea n y c a s ta d d r e s sa n dp r o v i d et h es a m es e r v i c e t h ep r i m a r yf u n c t i o no f a n y c a s ti st oa l l o w e du s e r st os e l e c tt h er i g h ts e r v e r t h ec r i t i c a lp r o b l e mi sq o s r o u t i n gw h i c hd i r e c t l yd e t e r m i n e st h ea v a i l a b i l i t yo fn e t w o r ks e r v i c ea n dt h el e v e lo f e f f i c i e n t t h er o u t i n ga l g o r i t h mt h a tc a l l sf o rd e l a ya n dc o s ti san pc o m p l e t ep r o b l e m g e n e t i ca l g o r i t h mi su s e dt od e a lw i t ht h e s ei s s u e s “p r e m a t u r i t y c o n v e r g e n c ei st h e p r a c t i c a lp r o b l e mb yu s i n gg e n e t i ca l g o r i t h mt oa p p l i c a t i o n s t h er e p r e s e n t a t i o ni st h a t t h ei n d i v i d u a l sf i t n e s sc a n tb ee l e v a t e do rc a n tf i n dt h eo p t i m u mi n d i v i d u a la l t e ra n u m b e ro fi t e r a t i o n s t h ec a u s eo ft h ep r o b l e mi st h ev a r i e t yo fi n d i v i d u a ll o s tt o o e a r l y i nt h ep a p e r , a f t e rm a k i n gap r o f o u n ds t u d yi nt h em o d e lo fa n y c a s ts e r v i c ea n d a n y c a s tr o u t i n ga l g o r i t h m ，a i m i n gt oa b o v e m e n t i o n e di s s u e s ，a na n y c a s tq o sr o u t i n g a l g o r i t h mb a s e do ng e n e t i ca l g o r i t h mi si m p r o v e d t h ei m p r o v e da l g o r i t h mc a nr e s o l v e t h ea n y c a s tr o u t i n gp r o b l e mw h i c hh a v er e q u e s to fm i n i m u mc o s ta n dc o n s t r a i n e do f d e l a y t h ei m p r o v e da l g o r i t h ma p p l i e sg e n e t i ca l g o r i t h m st oa n y c a s tq o sr o u t i n g a l g o r i t h mp r o b l e m s ，t op l a yi t sp a r a l l e l i s ma n do p t i m i z i n gt h ec h a r a c t e r i s t i c so fg r o u p s ； t h ei n t r o d u c t i o no ft h et h o u g h to fd i s s i m i l a r i t y , t oi m p r o v et h ec r o s s o v e ro p e r a t o ra n d m u t a t i o no p e r a t o rb ya d d i n gt h ev a r i e t yo fi n d i v i d u a l ；t h eu s eo fs a ( s i m u l a t e d a n n e a l i n ga l g o r i t h m s ) t h e o r yt oa d j u s tt h ef u n c t i o no ff i t n e s s i na d d i t i o ni tm e n d e d t h em e t h o do fg e n e r a t i n gi n i t i a lp o p u l a t i o nt og e n e r a t ed i v e r s i t ya n dh i g h e r “s t a r t i n g p o i n t i n f f i a lp o p u l a t i o n t h u si n h i b i tt h eo c c u r r e n c eo f “p r e m a t u r i t y c o n v e r g e n c e i no r d e rt ov e r i f yt h ev a l i d i t yo ft h ei m p r o v e dr o u t i n ga l g o r i t h m ，i tb u i l tu pa n e t w o r ka n y c a s tr o u t i n gs i m u l a t o rc o n t r a p u n t a l l y al a r g en u m b e ro fs i m u l a t o r e x p e r i m e n t ss h o wt h a ta l g o r i t h mc a nf i n dt h eb e s ts e r v e rf o rt h eu s e r st om e e tt h e 河南大学研究生硕士学位论文第1 l i 页 d e m a n d so fa n y c a s to fq o s ( t om e e tt h ed e l a yc o n s t r a i n t s ，a n dt h ec o s ti st h es m a l l e s t ) ， a n di ti se f f i c i e n ta n dc o n v e r g e n t b yc o m p a r i n gt h es i m u l a t i o nd a t ap r o v e dt h a tt h e i m p r o v e da l g o r i t h mh a sf a s t e rc o n v e r g e n c es p e e da n db e t t e rs u c c e s sr a t e k e y w o r d ：g e n e t i ca l g o r i t h m ；i p v 6a n y c a s t ；q u a l i t yo fs e r v i c e ( q o s ) ；r o u t i n g a l g o r i t h m ；d i s s i m i l a r i t y 关于学位论文独立完成和内容创新的声明 本人在导师的指导下独立完成的，对所研究的课题有新的见解。据我所知，除 文中特别加以说明、标注和致谢的地方外，论文中不包括其他人已经发表或撰 写过的研究成果，也不包括其他人为获得任何教育、科石开机构的学位或证书而 使用过的材料。与我一同工作的同事对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意：i ：、7 弦澎? 一? 氆。， 嘲蕊学位躐煞麓篁丝。 膨。 ， ：，l t - r l ， 学位审请八，。( 学位论交作者 ，蒂名：二星丝； 翁：i 渗滗哧鬻蠹泌曰 i 害? ，髯镊：；0 镬转妒年7 乃i 麓曰 j 。j 孝夸霉尹蔓；龟絮； k ；拳易j ，：；，豫 | ：i 懑霪豢妻渗，缝二鎏 蓼，关于学位论文著作权使用授权书三； 甏彩骧麓爱。荔汐。：。爹 本人经河南大学审核批准攮争硕士学琏。作为学位诊文的作者，本人完全 了解并同意河南本学有关保学j 使用学彼磷袭酌要求，即问南大学有权向国家 图书馆、科研信息扭构、数据收集机棉和夺校图书馆等提供学位论文( 纸质文 本和电子文本) 以供公焱检索、聋睁菇八授权呵南炙学出于宣扬、展览学校 学术发展和进行学术交流等曰i 诋：薮黟拳取影评2 1 _ ：、缩印、扫描和拷贝等复制手 段保存、汇编学位论文( 纸质文本和电子文本) 。 ( 涉及保密内容的学位论文在解密后适用本授权书) 学位获得者( 学住论文作者) 签名：皇丝 一 2 0 吖年乞月 曰 学位论文指导教师签名：y g 鳖 2 。夕“月日 河南大学研究生硕士学位论文第1 页 1 1 课题研究背景 第1 章绪论 随着计算机网络的飞速发展，一些流媒体等新兴业务也在不断推出( 如网络 电视、视频点播、网络游戏等) ，与此同时，此类用户也在迅速增加，此类业务对 网络的服务质量提出了更高要求，同时也大大增加了网络的负载，传统的数据传 输服务已经无法满足网络的正常运行。目前主要采用复制服务器技术来提高服务 质量和平衡网络负载，如i n t e m e t 中的镜像服务器、视频点播服务器、代理服务 器掣1 1 。解决此类问题的关键是如何在多个服务器中找到“最好 的服务器，在 用户和服务器之间建立一条可行的数据传输通路，来满足人们对网络服务质量的 要求。选播服务是解决此类问题的好办法，为了支持此类服务方式，r f c l 5 4 6 中 提出了选播( a n y c a s t ) 的概念【2 】，i p v 6 已将其定义为标准服务模型。 选播是i p v 4 向i p v 6 过度过程中产生的一种新的通信模式，i p v 4 过渡到i p v 6 不仅是因为地址空间不足的问题，也因为越来越多的网络用户提出更多的q o s 要 求的原因，选播就可以满足这类要求。与传统的单播、多播等通信模式不同，选 播通信方式是一台主机与一组目的主机中的一台之间进行通信，这组目的主机共 享一个选播地址，且提供相同的服务。比如，多镜像网址可以共享单个的选播地 址，这样，用户只需要发送一个请求就可从“最近 的那台服务器上得到所需要 的信息，如气象预报、股市最新情况等。 选播通信方式对于提高网络服务质量和改善网络的负载均衡具有广泛的应用 前景，可以满足许多新兴业务尤其是多媒体业务对网络服务质量( q o s ) 提出的 不同要求，如带宽、时延、代价、时延抖动等。 选播通信的特点使其可以应用到许多方面，如：a n y c a s t 地址对应多个目标 节点为q o s 资源预留提供了更多的选择余地【3 】；平衡复制服务器的负载，提高网 络性能；主机自动配置( 如域名服务、镜像网站等) ；支持分布式的复制服务器， 实现“最优 服务的选择；支持移动i p 节点方便获取就近服务而不需重新注册 更换代理，实现移动组播等。 由此可见，如何找到一条满足q o s 要求的“最优服务器是选播问题的关键 第2 页河南大学研究生硕士学位论文 所在，路由算法因此显得非常重要。 本文将针对满足时延和代价要求的选播路由算法进行研究，并对算法进行实 现和仿真分析。本课题研究的选播路由算法将具有一定的理论价值和广泛的应用 前景。 1 2 课题研究现状 选播作为新一代网络i p v 6 中定义的一种新的标准通信模式，具有很高的研究 价值和市场价值，一些相关领域的研究也在迅速展于 z 1 4 , 5 , 6 , 7 j 。目前对选播的研究主 要集中在两个方面【8 】，一是应用层选播，另一个方向是网络层选播。 在应用层的研究主要包括对目标服务器的选择和选播通信模型的研究方面。 对选播通信模型的实现主要通过管理手段实现选播服务，改善网络应用。应用层 的优点是：选播易于部署，不需要底层硬件提供新支持，无需占用网络层地址的 空间，还可以支持成员负载、磁盘空间等应用层距离指标；缺点是收集这些信息 的成本较高，因此可扩展性和重用性较差。 在网络层的研究主要是利用选播路由技术实现选播服务、提高网络通信的效 率和服务器的负载均衡，研究问题主要集中在组管理协议 9 , 1 0 】、地址结构j ，安 全问题以及可扩展性1 2 , 1 3 等方面，在路由协议【1 4 , 1 5 1 和路由算法 1 6 , 1 7 , 1 8 1 方面也取得 了一定的进展。在网络层较容易获得带宽、时延、费用等底层的信息，网络层选 播成员为支持选播路由付出的代价只是周期性汇报网络状态的开销，与用户以及 成员的数量无关。网络层目标服务器的选择主要依赖于网络的拓扑结构，路由选 择是实现网络层选播的关键所在。 选播q o s 路由所涉及的参数主要包括：带宽、时延、代价、时延抖动、包丢 失率等。研究表明【1 9 1 ，在进行选播q o s 路由选择时，包含了两个或者两个以上的 加性度量参数，或者包含加性度量和乘性度量的组合时，该路由选择问题就是一 个n p 完全问题。传统的穷举算法不能解决此类问题，目前解决此类问题的方法 多为启发式算法。 遗传算法是一类借鉴生物界自然选择和遗传机制的随机化肩发式搜索算法， 具有并行搜索、群体寻优等特点，被广泛用于解决n p 完全问题。因此，用遗传 算法解决q o s 路由选择问题非常合适。一些研究者已经将遗传算法应用到q o s 路由方面的问题中【2 0 , 2 1 , 2 2 , 2 3 , 2 4 , 2 5 1 ，其中应用到选播q o s 路由算法中的并不多。研 河南大学研究生硕士学位论文第3 页 究者通过遗传算法解决选播q o s 路由问题主要从遗传算法编码、初始种群生成、 染色体编码、适应度函数设计、遗传算了的改进等方面着手，取得了一定的成果 2 6 刃, 2 8 , 2 9 。但是把遗传算法应用到选播q o s 路由1 口- j 题中往往存在易于收敛于局部 的问题，即容易出现“早熟 收敛现象。“早熟”收敛是遗传算法在实际应用中常 见的一个疑难问题，主要表现为种群中最优个体的适应度值得不到提高，种群在 经过若干次迭代后仍找不到最优解，造成“早熟”的主要原因是群体中个体多样 性的过早缺失【3 。 因此，对遗传算法的改进还有很大的空间。例如：如何生成更好的初始种群； 如何增加群体的多样性；如何设计更合适的适应度函数；如何进一步改进选择、 交叉、变异操作；如何在全局搜索和局部搜索之间达到一种平衡等。 1 3 课题研究内容 本文针对“早熟收敛的问题给出了一种改进的选播路由算法，引入个体相 异度的思想来增加群体的多样性，利用模拟退火理论调整适应度函数，从而抑制 “早熟收敛的发生。仿真实验表明，本文改进的选播路由算法提高了算法的搜 索效率，能够解决满足时延约束的情况下代价最小的选播路由问题。 网络中选播路由的确定需要链路状态信息，本文不讨论如何收集和更新网络 中的链路状态信息，而是在假定网络状态信息在路由算法进行时保持不变，在此 基础上讨论如何根据状态信息，计算在有时延限制和费用约束的条件下满足q o s 要求的传输路径。概括起来，本文主要工作包括如下几点： ( 1 ) 分析选播服务的研究现状和主要实现技术，根据现在最新研究状况，指出 迫切需要解决的问题。 ( 2 ) 研究已有基于遗传算法的选播q o s 路由算法存在的问题：算法易于收敛于 局部，即“早熟现象，导致不能从全局找到最优解。给出一种基于改进的遗传 算法的选播q o s 路由算法，本算法把相异度的思想和模拟退火算法的理论同时引 入到遗传算法中，通过改进适应度值函数和遗传操作对算法进行优化，抑制“早 熟”收敛的发生。 ( 3 ) 通过设计和搭建网络仿真平台，设置网络状态信息，采用w a x m a n 方法生 成了具有实际特征的网络拓扑结构，对算法进行了仿真，然后分析了算法的有效 性、收敛性和成功率等。 第4 页河南大学研究生硕士学位论文 第2 章相关理论基础 本文的主要工作是把遗传算法应用到时延和代价约束的选播q o s 路由算法 中，作为本文的理论基础，本章简要介绍选播通信服务、q o s 路由算法、遗传算 法等与论文研究相关的内容。 2 1选播通信服务 2 1 1选播通信的网络模型 选播是点对多点中的任一点之间的通信，即实现从一台主机向一组目的主机 中与源主机“最近的一台目的主机进行通信。目的主机的地址由一个选播地址 表示，具有相同选播地址的服务器提供相同的功能。 为了更好的说明选播服务的定义，本文采用图2 1 所示的网络图来表示选播 服务的模型，其中r 表示网络的路由节点，h 是请求选播服务的终端主机( 用户) ， s e r v e r 是选播服务器。 选播地址m选播地址m选播地址m 图2 1选播服务网络模裂 河南大学研究生硕士学位论文第5 页 用g ( a ) 表示网络的路由节点集，其中任一节点称之为选播组g ( a ) 的一个成 员，提供选播服务的服务器从属于g ( a ) 。在图2 1 中，g 似j = 球3 ，r z r 5 ，其中 尺3 、r 彳、尺5 是g ( a ) 的三个组成员，s e r v e r l 、s e r v e r 2 、s e r v e r 3 分别是与尺3 、尺4 、 r 5 相连的选播服务器。为了简化讨论问题，可以把具有选播地址的路由节点当成 是与之相连的选播服务器。对于那些发出目标地址为a 的选播服务请求的源节点 集用g s ( a ) 表示。在图2 1 中发出服务请求的有两个源节点即h 1 和h 2 ，希望能 访问到离自己“最近的服务器，从而获得最佳的服务。如图2 1 所示，用户h 1 的请求将由s e r v e r l 来提供服务，用户h 2 的请求将由s e r v e r 3 来提供服务( 图中 虚线所示) 。 在r f c 2 3 7 3 中，选播服务的特殊规定如下： ( 1 ) 选播地址只能分配给路由器而不能分配给终端主机或服务器； ( 2 ) 选播服务器或镜像的服务器从属于路由节点； ( 3 ) 一个具有选播地址的路由节点只能与一个选播服务器相连，当一个选播服 务请求到达选播路由节点时，就可以认为该请求到达了与之相连的选播服务器； ( 4 ) 一个选播地址a 可以分配给多个路由节点； ( 5 ) 选播地址不允许作为源端地址而只能作为目标地址出现在选播数据包中。 另外选播还具有如下特点【8 】： ( 1 ) 节约路由和链路资源，数据包通过最短路径发送到选播地址中离它“最近” 的组员； ( 2 ) 简化配置。用户只需要配置一个选播地址，就可从一组服务器中获得服务； ( 3 ) 提供弹性服务。如果选播组中正在提供服务的组员由于某种原因断开了， 可通过选播路由在其他组员中找到离用户“最近”的组员继续提供服务，这样很 大程度地保证了服务的可靠性： ( 4 ) 有利于网络的负载平衡。将选播和单播以及组播比较，不难发现单播和组 播在路由过程中多个点选择同一段路由的可能性很大，使网络负载不平衡，容易 造成拥塞，而选播在很大程度上减轻了这种不平衡； ( 5 ) 可以与组播结合使用，用来改进组播的路由算法； ( 6 ) 提供一种“最近”的机制，与服务定位协议s l p 比较可以获得更好的服务 效率。 第6 页河南大学研究生硕士学位论文 2 1 2 传统的通信服务 计算机网络中数据的传输都要从一个终端传输到另外一个终端，不同的通信 服务方式决定了不同的路由方式，传统的通信服务方式一般有如下几种。 ( 1 ) 单播( u n i c a s t ) ：单播是点对点的通信，它是目前应用最为广泛的一种通 信方式 3 l 】。在单播通信方式下，从源i p 主机发送出的每个数据包只能传送给一个 目的主机，而目的主机由数据包中的目标i p 地址决定。单播通信要求在发送方和 接收方之间有单独的数据通道，如果有另外的多个目的主机希望同时获得这个相 同的数据包，发送方主机必须向每个希望接收此数据包的用户发送一份单独的数 据包拷贝。 ( 2 ) 组播( m u l t i c a s t ) ：组播是指一点对多个节点的通信【3 2 】。分组被发送到特 定的组播组，只有属于该组播组的目的端才能接收此数据，该组以外的均接收不 到该分组，而且组播只发送给那些有要求的组成员。组成员是动态的，它可以在 任何时候加入或离开一个组，组的大小与位置没有限制，一个主机可以是多个组 的成员。一个主机用组播协议向n 个主机发送相同的数据时，只要发送一次，其 数据由网络中的路由器和交换机逐级进行复制并发送给各个接收方，这样既节省 服务器资源也节省网络主干的带宽资源。目前的网络视频会议、分布式数据库、 远程教育等都是组播的典型应用。 ( 3 ) 广播( b r o a d c a s t ) ：广播是局域网中常用的通信方式【3 3 1 。在广播通信模式 下，数据包从源主机发向网络中所有的主机，即“o n e t o a l l ”。广播存在着一些问 题，即同一网络链路上的大量广播意味着该链路上的所有节点都必须处理所有广 播，其中绝大部分节点最终都将忽略该广播，因为该信息与自己无关。把广播数 据包在子网之间进行转发将导致拥塞和主机资源浪费等问题。因此，i p v 6 中不再 定义广播地址，而是由组播地址替代。 2 1 3 选播通信服务的功能 选播服务的功能主要体现在以下几个方面。 第一，可以保证用户和它“最近 的服务器通信，“最近”并不一定代表距离 最近或跳数最少，在实际网络中还有其他衡量路由优劣的标准，如带宽、时延、 代价等参数指标，而如何找到“最近 的服务器是选播路由要解决的问题。 河南大学研究生硕士学位论文第7 页 第二，在i p v 6 关于选播通信的定义中，并没有给出定义选播地址专门的地址 格式，仍然使用了单播的地址格式，这为终端用户提供了方便。用户不需要知道 是哪台服务器提供了服务，请求服务时也无需确定该服务器的i p 地址。由于所有 的服务器选播地址是相同的( 从用户的角度看) ，用户需要哪种服务，只要提供该 服务的选播地址即可，网络能自动选择该地址所表示的一组服务器中最合适的一 台为其服务，这就为用户提供了透明服务。 第三，由于多台服务器提供相同的服务，即使其中有一台甚至多台发生故障 停止服务，只要至少还有一台还在正常工作，服务仍然可以继续。选播机制大大 提高了网络服务的可靠性和稳健性，有利于网络负载的均衡。 第四，根据选播地址结构的特点，可以实现不同基于不同策略的路由机制， 如：基于源路由的策略、分布式路由的策略和分层路由的策略。 2 。1 4 选播通信服务的应用 从选播的特点可以看出它具有很多符合网络发展趋势的优点，可以说选播是 继组播后提出的一种更加重要的通信方式，将会在越来越多的领域中发挥作用， 目前主要有以下几种应用。 ( 1 ) 最优服务的选择：由选播的第一个功能特点可知，假设把选播地址分配给 多个下载电影的服务器，当用户下载电影时，网络会自动找到一台最优的服务器 向用户提供服务。 ( 2 ) 主机的自动配置：只要把某一选播地址分配给d n s 服务器，当一台主机 从一个网络移动到其他网络时，无需为这台主机重新配置本地d n s 服务器，主机 可以使用选播地址与任何网络的d n s 服务器进行通信【3 4 】。这也是选播最典型的 应用之一。 ( 3 ) 实现在分布式操作系统中的透明服务：分布式操作系统的一个关键性技术 就是透明服务器问题。在一个很大范围的网络上，如何实现透明服务器，从而实 现分布式操作系统的基本功能是一个十分困难的问题，而选播则提供了一种非常 有效的解决方案。由于一个选播地址代表的选播组本身就实现了透明服务器，所 以所有的服务请求都可以通过选播的方式自动的被网络发送到最好的服务器，不 需要请求方作任何干预。另外选播服务可以提高分布式系统的稳定性和可靠性， 并平衡系统的负载。因此，选播服务对于在网络全域上实现统一的分布式操作系 第8 页河南大学研究生硕士学位论文 统起着重要的作用。 ( 4 ) 在移动网络中管理移动节点：选播除了用在复制服务器之间的选择外，还 可以用于相同或相似属性节点间的选择。例如，当一个移动主机需要与其宿主子 网的某个本地移动代理通信时，选播可以在主机宿主了网中为其选择一个合适的 本地移动代理。在条件动态改变的情况下，如何管理移动节点和移动服务是现代 军事和商业移动网络的核心问题。而选播技术和相关的动态路由功能为解决这个 问题提供了一条思路，有望大大改善移动网络的性能。 ( 5 ) 支持组播路由：组播给网络服务带来了巨大的变化，在实际应用中已经得 到了的证明，而选播服务己被提出来做组播路由的基础。k i m 等人选用p i m s m ( p r o t o c o li n d e p e n d e n tm u l t i c a s ts p a r s em o d e ) 支持每个组拥有多个汇聚路由器 ( r e n d e z v o u sr o u t e r s ) ，而选播汇聚点r p ( r e n d e z v o u sp o i n t ) 保证组播数据流可 以随时建立，同时可避免单一l 冲成为瓶颈或故障点而起到容错的作用【3 5 1 。 2 2 o o s 路由算法 q o s 即服务质量( q u a l i t yo f s e r v i c e ) 是指网络在传输数据流时必须满足的一 系列服务需求，这些服务要求可用以下路由参数表示和衡量。q o s 包括用户要求 和网络服务提供者的行为两个方面。用户要求指用户在i n t e m e t 网络上进行多媒 体通信时所要求的服务类型以及相应的传输性能和质量；网络服务提供者的行为 指服务商所能提供的服务类型和质量等。 2 2 1 0 0 s 路由参数 对于服务质量的度量所采用的度量参数主要包括：带宽、时延、代价、时延 抖动、包丢失率等。这些参数也是选播路由算法所需要依据的重要参数。 ( 1 ) 带宽：带宽指链路可用的流通容量，是链路传输能力的一种度量。在实际 网络中，每条链路的传输容量都有上限，超过了规定大小往往会造成网络的拥塞， 降低服务质量。 ( 2 ) 剩余带宽( 可用带宽) ：剩余带宽是指链路还能接受的网路流通容量，通 常是链路的极限容量和已用带宽的差值。影响路由选择的往往是剩余带宽而不是 已用带宽。 ( 3 ) 时延：时延是指数据从网络的一端传输到另一端所花费的总的时间。时延 ；n - i 南大学研究生硕士学位论文第9 页 主要可以分为两类：固定时延和可变时延。固定时延是数据在链路上的传播时间 和中间节点的转发时间；可变时延是指数据在传输过程中由于某些中间节点繁忙 而需排队等待的时间。网络中很多数据不能顺利传输很多时候是因为路由中的部 分节点过于繁忙导致的。路由时延直接决定着用户请求服务的响应时间。 ( 4 ) 代价：代价是网络链路的使用成本或其他网络资源使用状态的测度。通信 代价是一种重要的参数，例如有些公司尤其是一些公司由于费用和性能的原因， 采用自己的线路传输数据( 时延可能会比较长) ，而不是采用费用较高的公用线路。 ( 5 ) 时延抖动：抖动是指时延的变化，即相邻两个数据包到达接收者的时间间 隔与发送者发送这两个数据包的时间间隔之间的差异。 ( 6 ) 包丢失率：包丢失率是指在网络中传输数据包时丢弃数据包占全部传输包 的比率，包丢失的原因主要是由于网络拥塞而引起的。 本文中的选播q o s 算法将会用到时延和代价这两个参数。 根据q o s 度量参数的特性和运算规则，可将这些参数分为几类：加性度量参 数、乘性度量参数、凹性度量参数。设路径p a t h 由n 条链路组成，即 p a t h = e l ，e 2 , e 3 , ，e d ，e i 表示一条路径，令f i t n e s s ( p a t h ) 表示路径尸口砌的参数值， 则q o s 路由参数特点可以表示公式如下： 加性度量：f i t n e s s ( p a t h ) = f ( e ，) ( 2 1 ) i = 1 乘性度量：f i t n e s s ( p a t h ) = 兀f ( e ，) f = l ( 2 2 ) 凹性度量：f i t n e s s ( p a t h ) = m i n 矧 2 3 。f ( e ，) ( 2 3 ) 其中时延、时延抖动和代价属于加性度量参数，包丢失率属于乘性度量参数， 而带宽属于凹性度量参数。当路由选择的约束条件包含两个或两个以上的加性度 量参数，如延迟、代价等，或者包含加性度量和乘性度量( 如丢失率) 的组合时， 则该路由选择问题为n p 完全问题【l9 1 。此类问题不能在多项式时间内精确求解， 目前解决n p 完全问题的方法往往采用启发式的方法。 2 2 2 0 0 s 路由算法的设计目标 一般来说，路由算法的设计目标有如下几个方面【3 6 】： 第10 页河南大学研究生硕士学位论文 ( 1 ) 路径优化：优化指路由算法选择最佳路径的能力，寻找最佳路径主要依靠 度量的标准，协议首先必须严格定义它们待优化的度量标准，使得算法知道哪个 度量参数的权值较大，哪个度量参数的权值小。 ( 2 ) 快速收敛：即算法是高效率的。路由算法必须能够快速收敛，收敛是所有 路由器一致找到最佳路径的过程。当某网络事件致使路径不可用时，路由器通过 网络分发路由更新信息，促使最佳路径的重新计算，最终使所有路由器达成一致。 收敛很慢的路由算法可能会产生路由环或网络中断。 ( 3 ) 可靠稳定：路由算法必须可靠，即在出现不正常或不可预见事件的情况下 仍能正常处理。例如，硬件故障、高负载和不j f 确的实现方法等。因为路由器位 于网络的连接点，当它们失效时会产生重大的问题。好的路由算法通常是经过了 时间考验，证实在各种网络条件下都很稳定的算法。 ( 4 ) 简单低耗：路由算法应设计得尽量简单。即路由协议必须是高效地工作， 尽量减少软件和硬件的开销。 ( 5 ) 灵活性：路由算法还应该是灵活的，即它们应该迅速、准确地适应各种网 络环境。 2 2 3o o s 路由策略 在q o s 路由解决方案中所牵涉到的q o s 路由参数的数量越大，运算的复杂 度越高，随着网络规模的增大其算法的复杂度将会急剧增加，选播路由算法所找 到的路径并不是传统的最短路径，而是满足一定q o s 需求的“最好”路径。通常 在实际的q o s 路由算法中，主要考虑的是用户最为关心的一个或者两个路由参 数。为了降低路径计算的复杂度，人们提出了一些路由策略。根据如何维护状态 信息和如何实施搜索可行路径，可将q o s 路由策略分为源路由、分布式路由和分 层路由三种，简要介绍如下： ( 1 ) 源路由：在源路由策略中，每个节点都需要保存网络的状态信息，包括网 络拓扑结构，每个节点和其他相连节点的路径的度量参数值，如：时延、代价等。 当用户请求到达时，源节点根据网络状态信息和业务度量参数的要求计算路径， 如果存在合适的路径，则由源节点沿所选路径发送资源预约信令建立路径。源路 由方法的优点是易于实现且灵活，源节点可以独立选择路由算法计算路由，不需 要多节点相互协调进行路由选择，可以避免死锁和环路等现象。在基于源路由的 河南大学研究生硕士学位论文第11 页 发送策略中，更容易设计出可实现的低复杂度路由算法。但由于实际的网络中节 点信息随时可能发生变化，因此其状态信息准确性不高，路由开销大，网络可扩 展性不好等。 ( 2 ) 分布式路由：分布式路由的每个节点保存着所有到达目的节点的下一跳列 表，当一个数据报到达时，通过分布式的发送信息命令，了解本节点对应于到达 某个节点的前一个节点和后继节点，然后查表选择下一跳的节点，把数据报发送 出去。这种路由方式需要各个节点间互相协调，共同完成。优点是路由计算是由 路径上的各个节点共同分担，缺点是可能会由于各个节点间没有协调一致导致每 个节点所保留的其他节点的状态信息不一致，因此可能会引起回路问题。 ( 3 ) 分层路由：分层路由主要通过将多个节点汇聚成一个逻辑节点，最上层的 逻辑节点间采用分布式路由的方法寻找路由路径，下层的每个节点仍采用源路由 的方式选择路径。这种方式兼具源路由和分布式路由的优点，且可扩展性好，但 是由于汇聚信息引入的不精确性，分层路由也可能导致选路失败的问题【3 7 】。 本文研究的选播路由算法是基于源路由的策略，对选播路由算法进行分析和 实现。 2 3 遗传算法 本文在深入分析选播服务模型和选播路由算法的基础上，将改进的遗传算法 应用到选播q o s 路由问题中，给出了一种基于改进的遗传算法的选播q o s 路由 算法。此处需要简要介绍遗传算法的基本内容。 2 3 1 遗传算法简介 遗传算法( g e n e t i ca l g o r i t h m ) 是由美国m i c h i g a n 大学的j o h nh o l l a n d 教授 领导的研究小组于2 0 世纪7 0 年代提出来的一种基于自然界物种进化论和自然遗 传机制的搜索算法，具有并行性和群体寻优的特点，是一种适合在复杂而庞大的 搜索空间中寻找最优或次优解的方法。 遗传算法利用简单的编码技术和繁殖机制来表现复杂的现象，适用于处理传 统搜索方法难于解决的复杂问题和非线性问题。特别是由于它不受搜索空间的限 制，不必要求诸如连续性、导数存在和单峰假设，以及固有的并行性等【3 引，遗传 算法己被广泛地应用于组合优化、机器学习、并行处理、自适应控制、人工神经 第12 页河南大学研究生硕士学位论文 网络训练等优化问题以及具有n p 难度的问题中。 本质上，遗传算法是对生物进化过程的模拟。在生物进化过程中生物群体在 其生存环境约束下，通过各个体的竞争，自然选择、杂交、变异等方式所进行的 “物竞天演，适者生存，不适者淘汰”的一种自然优化过程。因此遗传算法的执 行过程可以认为是某种优化问题的求解过程。g a 正是模拟生物的这种自然选择 和群体遗传机理的数值优化方法。 具体来说，g a 把一组随机生成的可行解作为父代群体，把适应度函数( 目 标函数或它的一种变换形式) 作为父代个体适应环境能力的度量，依据优胜劣汰 原则，通过对群体施加竞争，经选择、交叉生成子代个体，后者再经变异，实现 群体内个体结构重组，如此反复进化迭代，使个体的适应能力不断提高，产生性 能更优的下一代群体，使优秀个体不断向最优点靠近【2 引，直到找到满足环境约束 的优良个体或合乎具体的应用准则为止。 2 3 2 遗传算法的基本概念 1 染色体 染色体( c h r o m o s o m e ) 又称为个体( i n d i v i d u a l ) ，属于生物学上的概念。在 遗传算法中的染色体通常用一个所谓的串来表示( 有时也采用一个向量表示) ，如 x = x l x 2 x 。，其中x i 是串x 的基本单元，称为基因( g e n e ) ，n 称为基因数，也称 作串的长度。遗传算法要解决问题的编码不同，染色体的表现形式也不一样。 2 群体 群体( p o p u l a t i o n ) 是个体的集合，又称种群或集团。在使用遗传算法求解问 题时，首先随机选择若干个体构成一个种群，称作初始种群，以此为基础进行迭 代，每次产生新的个体集合都被称为了种群。 种群规模是种群包含个体的数量，是遗传算法的基本运行参数之一，其取值 非常重要：过小的种群规模会提高算法的运行速度，却降低了种群的多样性，甚 至导致过早收敛；种群规模过大，则会降低算法运行的速度。 3 编码 遗传算法不能直接处理问题空间的参数，必须把它们转换成遗传空间中由基 因按一定结构组成的染色体或个体，这一转换操作叫做编码( c o d i n g ) 。遗传编码 河南大学研究生硕士学位论文第13 页 决定着个体实施结构重组的方法，也即遗传进化中的交叉和变异策略。因此，如 何将问题的解转换为编码表达的染色体是应用遗传算法的首要问题，也是设计遗 传算法时的一个关键步骤。 编码方法除了决定个体的染色体排列形式之外，还决定了个体从搜索空间的 基因型变换到解空间的表现型时的解码方法，编码方法也影响到交叉、变异等遗 传操作的运算方法。可见，编码方法在很大程度上决定了如何进行种群的遗传进 化运算以及遗传进化运算的效率。 经典的编码方法用的是二进制串，但对于许多实际应用来说这种编码非常长， 难以直接描述出问题的性质。近年来，针对特殊问题人们提出了各种非0 1 串的 编码方法，例如，约束优化的实数编码、组合优化的整数编码等。总之，针对一 个具体应用问题，如何设计一种完美的编码方案一直是遗传算法的应用难点之一， 也是遗传算法的一个重要研究方向。 在网络路由问题研究中，往往使用不定长的自然数编码方式。在网络拓扑结 构中，每个节点都有相应的数字编号，而每条染色体就代表一条搜索的路径，因 此，从源节点到目的节点的每个节点编号序列组织在一起便构成一条染色体。 4 遗传算子 ( 1 ) 选择算子( s e l e c t i o no p e r a t o r ) ：选择算子是遗传算法中环境对个体适应性 的评价方式，在每一代的遗传中，选择适应度高的个体进入下一代，每个个体进 入下一代的概率取决于其适应度值，选择算子也是实现群体优良基因传播的基本 方式。选择算子对群体多样性具有严格单调减少的作用。从模拟生物学进化过程 来说，选择算子在保证了遗传算法迭代中的“适者生存 的群体进化现象，体现 了群体中个体求同的意向，在很大的程度上决定了遗传算法的收敛效果和速度。 选择算子在g a 中通常表现为优良个体在下一代群体中具有较强的繁殖能力，而 劣质个体则逐渐被淘汰，这使得群体整体的品质得以提高。常用的选择方法有适 应度比例法( 轮盘选择法) 、线性排名选择、锦标赛选择等，其中，轮盘选择策略 最为常用。 ( 2 ) 交叉算子( c r o s s o v e ro p e r a t o r ) 和交叉概率p c ：在生物的自然进化过程中， 两条染色体通过交叉可以形成新的染色体，从而产生新的个体或物种。在遗传算 法中也同样模拟相似的过程，这个过程通过交叉算子来实现。交叉算子以一定的 交叉概率p c ( p c ( 0 ，1 ) ) 在种群中随机选择一定数量的个体实施两两交叉操作。 第14 页河南大学研究生硕士学位论文 交叉操作通常是把两个基因串中的某一部分相互交换，产生两个新的个体。最常 用的交叉策略是点式交叉( p o i n tc r o s s o v e r ) ，它首先随机地在两个父染色体上选 择一个或多个交叉点，然后交换父体串对应的了串。因此交叉算- 了的主要作用就 是产生新个体，同时要求不要太多的破坏父染色体中的优良基