（计算机应用技术专业论文）基于免疫克隆计算的multiagent组播路由算法.pdf

摘要 摘要 在计算机网络中，电子商务、视频会议和远程教育等业务中所涉及组播通信 技术是当前研究的热点。组播是指同一信息从源节点传送到网络中多个目标节点 ( 并不一定是所有节点) 的通信方式。求解组播问题的目的是建立一棵满足q o s 约束条件且覆盖所有目标节点的，性能较好的组播树。 本文将免疫克隆计算的方法及思想与多智能体系统相结合，提出了两种解决 时延受限组播路由问题的算法，主要研究工作如下： 1 研究了最优s t e i n e r 树问题以及针对这一问题常用的启发式算法： 2 对多智能体系统( m u l t i - a g e n ts y s t e m ，m a s ) 及其应用现状进行研究；并 且在此基础上阐述了m u l t i - a g e n t 与智能进化计算相结合提出的多智能体遗传算法 ( m a g a ) ： 3 将免疫算子引入多智能体遗传算法，针对时延受限的组播路由问题，提出 了一种免疫m u l t i - a g e n t 组播路由算法。与传统遗传算法相比，本算法利用待求问 题的先验知识指导搜索、加速收敛，避免了问题进化的盲目性，并利用智能体的 竞争、协作、自学习等行为求解组播路由问题，取得了良好的效果； 4 在结合克隆选择计算和多智能体特点的基础上，提出了基于免疫克隆选择 的m u l t i - a g e n t 组播路由算法；该算法首先针对每个组播组成员求出满足时延约束 的备选路径集合，再利用克隆策略结合多智能体进化处理备选路径的选择，从而 达到构造组播树的目的。仿真实验证明，该算法有效克服了传统遗传算法的缺点。 且算法稳定、灵活、操作简便。 关键词：组播路由免疫克隆选择算法免疫算法多智能体服务质量 a b s l r a c t a b s t r a c t i n c o m p u t e r n e t w o r k s ，t o p r o v i d e m u l t i c a s tc o m m u n i c a t i o nf o rm u l t i m e d i a r e a l t i m es e r v i c e ，s u c ha se - c o m m o l c e ，d i s t a n c e - e d u c a t i o na n dv i d e o c o n f e r e n c e ，i so n e o f t h e i m p o r t a n ti s s u e s i nc u r r e n tr e s e a r c hf i e l d m u l t i c a s t m u t i n g c o n s t r u c t s p a t h sa l o n g w h i c hd a t ap a c k e t sf r o mas o u r c ea r ed i s t r i b u t e dt om a n y , b u tn o ta 1 1 d e s t i n a t i o n si na c o m m u n i c a t i o n a ln e t w o r k af u n d a m e n t a li s s u ei nm u l t i c a s ti sh o wt oc o n s t r u c t l o w - c o s tn e e st h a ts a r i s f yt h eq u a l i t yo fs e r v i c e ( q o s ) r e q u i r e m e n t sa n ds p a n n i n ga l l d e s t i n a t i o n s m p a p e rc o m b i n e dt h em e t h o do fi m i n a n ec l o n a lc o m p u t i n gw i t l lm u l t i a g e n t ， a n d p r o p o s e dt w od e l a y - c o n s t r a i n e dm u l t i c a s ta l g o r i t h m s 1 1 1 cm a i nr e s e a r c hw 0 r ka n d r e s u l t sa r ef o l l o w s ： 1 n 璩e x i s t i n g h e u r i s t i ca l g o r i t h m sf o rs t e i n e rt r e ep r o b l e ma l e r e s e a r c h e d ； 2 p r i n c i p l ea n da p p l i c a t i o n so f m u l t i - a g e n ts y s t e m w e r er e s e a r c h e di nt h i sp a p e r ； a n db a s e do n t h i s ，t h ep a p e r a l s os t u d i e dm u l t i - a g e n tg e n e t i c a l g o r i t h m ( m a g a ) ； 3 i i m t l u n e o p e r a t o ri si m p o r t e di n mt h ef r a r n e w o r ko fm a g a a n da i ma t m u i t i c a s tr o u t i n gp r o b l e m ，m u l t i - a g e n tm u l t i c a s tr o u t i n gb a s e do ni f m n u n e a l g o r i t h m ( m a i a ) i sp r o p o s e d c o m p a r e t ot r a d i t i o n a lg a m a i au s e st r a n s c e n d e n t a lk n o w l e d g e o fs p e c i f i cp r o b l e m st od i r e c ta n da c c e l e r a t es e a r c h t h em g o f i t h ms o l v e sm u l t i e a s t m u t i n gb yc o m b i n e dw i t hi n t e l l i g e n tb e h a v i o r s ，s u c h 船c o m p e t i t i o n ，c o o p e r a t i o na n d s e l f - s t u d y , o f a g e n t 4 c h a r a c t e r i s t i c so fc l o n a ls e l e c t i o nc o m p u t a t i o na r ec o m b i n e dw i t hm u l t i - a g e n t ， m u l t i - a g e n t m u l t i c a s tr o u t i n gb a s e do ni i t i m u r ec l o n a ls e l e c t i o na l g o r i t h m ( m a i c s a ) i sp r o p o s e di nt h i s p a p e r f i r s t l y , f o re a c h m e m b e ro f m u l t i c a s t g r o u p ，t h ea l g o r i t h mg e t s t h es e to fp a t h st h a ts a t i s f yt h ed e l a ，h o n s t r a i n t ；a n dt h e n , s e l e c tc a n d i d a t e sb yu s i n g c l o n a ls t r a t e g i e sa n dm u l t i - a g e n te v o l u t i o nt oc o n s t r u c tam u l t i c a s tt r e e i ti ss h o w n t h a tt h ea l g o r i t h mh a sb e t t e rg l o b a ls e a r c h i n ga b i l i t ya n de f f e c t i v e l yo v e r c o m e st h e d r a w b a c k so fg aw i t hc o m p u t e rs i m u l a t i o n s a tt h es a n l et i m e , t h ea l g o r i t h mc o u l db e o p e r a t e ds t e a d i l y , e x p e d i e n t l ya n ds i m p l y k e y w o r d ： m u l t i c a s tr o u t i n gi m m u n ec l o n a ls e l e c t i o na l g o r i t h m i m m u n e a l g o r i t h mm u l t i - a g e n tq o s ( q u a l i t y o f s e r v i c e ) 创新性声明 6 9 5 5 1 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：壶j 滥! 日期兰盟： 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即；研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文( 保密的论文 在解密后遵守此规定) 。 本人签名： 壶91 2 圭1 0 。 导师签名：。! ：日期兰巡： 第一章绪论 第一章绪论 本章主要介绍计算机网络中组播技术的发展和特点，组播算法的研究现状以 及相关的组播协议；最后列出本文主要内容安排。 1 1 组播技术产生的背景 上个世纪末到本世纪初是网络技术飞速发展的时期，计算机网络的功能日益强 大，特别是以i n t e m e t 为代表的m 网络更是日新月异。基于i n t e r a c t 的新应用和业 务也不断推出，如电子商务、远程教学、视频会议等。当用户数据需要从一个终 端发送到另一个终端时，首先要确定传输路由，不同的通信方式，其确定路由的 方式也不同。 如今网络的通信方式主要有以下几种： 单播( u n i c a s t ：p o i n t t op o i n t ，点到点的通信方式) ，当只有两个终端参与同 一进程时，一般采用单播方式； 组播( m u l t i c a s t ：p o i n t t o m u l t i p o i n t ，点到多点的通信方式) ，是一源节点向 多个目标节点发送信息( 但不是所有节点) 的通信方式 汇播( c o n c a s t ：m u l t i p o i n t t op o i n t ，多点到一点的通信方式) ，远程数据采 集涉及汇播方式； 群播( m u l t i p o i n t t o m u l t i p o i n t ，多点到多点的通信方式) ，其典型应用是网 络即时游戏，在多方游戏中，需要将各自的状态互相同步发送； 广播( b r o a d c a s t ：p o i n tt oa l lp o i n t , 点到所有节点的通信方式) ，是网络中常 用的通信方式，广播通信方式在局域网中应用很广。 在上述几种通信方式中，组播是目前研究最多，也是应用最广的网络连接方 式。前面提到的新型网络应用，如视频会议、交互式游戏、声音视频电话、实时 多媒体播放、分布式计算、视频点播和远程教学等，它们的特点是涉及多个成员 的交互，本质上都具有组播的特征。组播通信方式需要网络提供合适的协议支持， 否则这些应用实现起来代价很大或不可行，所以在功能和性能两个方面对传统网 络协议提出了新的挑战。 1 2 组播技术概述 所谓组播。指的是一个源节点向多个目标节点发送信息的通信方式，参与组 !基于免疫克隆计算的m u l t i - a g e n t 组播路由算法 播的多个目标节点组成了一个组播组，每个端节点称为组播组成员。实现组播功 能可以有三种方式： 第一种是由源节点向各用户单独发送同样的消息，这种方式以单播为基础， 每次会话需要产生与用户数量相等的分组，用户数量较少时，这种方式基本可以 满足需求。第二种是每个分组都含有一张目标节点清单，当分组到达路由器时， 路由器检查所有目标节点，以确定将要用到的输出链路的集合，并为所使用的每 一条输出线路复制一个新的分组，每个分组中仅含有使用此线路的那些目标节点。 这种路由方式就像各自分组寻址一样，只是若干分组必须经过同一路由时，其中 一个分组负担全部费用，而其它的分组不必承担费用【l 】。最后一种方式是建立组播 树，由源节点向树中的相邻节点发送消息，然后这些相邻节点继续向树中下一级 节点转发这些消息，这种方法大大减少了源节点发送的消息量，防止了网络链路 的阻塞。 组播树分为有源树和共享树两种类型【6 】。一些组搔路由协议为每一个源节点建 立其各自的组播树，这些树就是有源树。有源树的根是信息源( 源节点) ，叶子节 点必然是信宿节点。有源树的计算分为两种：第一种是最短路径树，源节点到各 组播成员都以最短路径相连，使用较广的两种算法是b e l l m a n - f o r d 算法 3 】【4 1 和 d i j k s t r a - g 法圆，显然最短路径树的全树费用并不一定是最优的；第二种有源树是 s t e i n e r 树，即：在一个连通图中，给定一个节点子集，要求在图中找到一棵覆盖给 定子集的费用最小的生成树。这是。个n p - c o m p l e t e 问题，即最优算法无法在多项 式时间内完成。因此，要寻求有效的启发式算法，降低算法复杂度，丽性能上逼 近理论算法。目前，针对s t e i n e r 树i h l 题的算法很多【7 o l ，h w a n g 在文献【7 】中分别提 出了精确和启发式的s t e i n e r 算法。有源树的缺点在于，对于有m 个成员的组播组， 则需要生成肌棵组播树，其计算和存储费用都很大。 组播会话存活期间，当组播成员发生变化( 新成员加入或者原有成员退出) 时，组播树也会相应发生变化。但是组播树中的某些部分可能不会发生变化，对 于同一个网络中的不同组播树，虽然这些树的源节点和组播成员不同，但是它们 的通路上可能存在至少一个相同的路由器。共享树就是利用了不同组播树可以在 网络中共享同一个路由器的事实，与其让每棵树根植在不同的源节点上，倒不如 让这些树根植在一个指定点( r e n d e z v o u sp o i n t ，r p ) 上。 共享树，也称为核心树，最早在文献【i l 】中被提出。在这种方式中，只需要为 每一个组播组建立一棵组播树，各组节点之间的通信通过被称为c o r e 1 2 1 的指定节点 进行：各节点通过最短路与核心相连，将消息发往核心，再由核心发往接收节点。 可以看出，与有源树相比，共享树大大减少了的计算和存储的开销但是，一般 共享树的费用比有源树要大2 倍以上；当核心是组成员的情况下，其代价会达到有 源树的3 倍以上i t 3 1 ，现有路由协议有p r o t o c o li n d e p e n d e n tm u l f i e a s t ( p i m ) 瞄l 和 第一章绪论 c o r n - b a s e dt r e e s ( c b t ) 1 5 】。共享树的主要问题在于核心的选取和维护较为困难，文 献【1 3 】【1 6 】中给出了几种选取核心的方法。此外，为降低中心失败带来的影响，通 常要维护一个包含多个核心的列表。 1 3 组播的特点 组播的特点主要体现在以下三个方面： 1 带宽 运用组播技术分发信息常常能从本质上减少撼个网络带宽的需求。与单播技 术( 点到点通信方式) 相比，当多个用户要求同一服务器提供同样信息时，使用 单播技术，带宽需求将随用户的增多而增加；而对于组播，由于在共用链路上传 递信息的一份拷贝，因此带宽的需求不会随用户数量的增多而增加。 2 服务器负载 单播实现一点到一点的通信模式，因此随着用户数目的增加，服务器必须为 每一个新增的有通信要求的用户传输一份信息的拷贝，因此采用这种通信方式将 严重增加服务器的负担：而组播则是实现一点对多点的通信方式，对多目标节点 共享的链路只传送一次，这样就大大减轻了服务器的负担，从而提高了服务器处 理能力。 3 网络负载 当将内容相同的信息传送给多个用户时，运用组播技术能够明显地减少带宽 要求，而带宽消耗的降低等同于网络负载的降低。 1 4 组播路由算法及研究现状 有效进行组播通信的关键是确定组播路由。组播路由算法的目的是确定组播 树，并且一般用树的“费用”来衡量组播树质量的好坏，组播树费用是指树中所 有链路费用的总和【册。在实际应用中，有效利用网络资源是非常重要的，因此要 求组播树的费用最小。下面对组播路由算法进行介绍： 1 3 1 动态算法和静态算法 根据路由算法所依据的网络拓扑和状态信息的不同，可将其分为动态和静态 路由算法。静态路由算法认为网络的拓扑和状态信息是固定不变的【5 i s , 9 1 ，静态路 由实现简单，但是不适应网络状态的动态变化；真实网络中存在许多动态变化，如 网络拓扑结构的变化，组成员的变化等，动态算法根据网络的实时状态信息进行， 基于免疫克隆计算的m u l t i - a g e n t 组播路由算法 能够根据网络的状态变化调攘其所选的路径。动态算法是通过对组播树的结构进 行一定程度的调整来处理成员加入或者离开之后组播树的更新问题。 1 3 2 分布式算法和集中式算法 组播路由算法按其实现方式，又可分为集中式和分布式算法。集中式组播路由 一般都是源路由算法( s o u r c e - r o o t e dr o u t i n g ) ，即源节点通过某个链路协议获得 完整的网络拓扑信息，并进行路由的计算；而分布式算法则不需要每个组成员掌 握整个网络的拓扑，而只是在具有局部信息条件下就可参与路由的确定，这特 点对于实现大型网络的组播路由是十分有利的。 l _ 3 3 分层组播路由算法 随着网络规模的扩大，路由器的路由表也会成比例增长。增大的路由表不仅 占用路由器的内存，而且需要更多的c p u 扫描时间，以及更大的带宽来发送关于 表格的状态报告。在某一时刻，网络可能会增大到不可能让每个路由器都给出至 其他每个路由器的路径表项。 分层路由算法针对网络规模的丕断扩大而提出，在分层路由中，网络被划分 为不同的层次，最底层域由实际路由器构成，稍上一层域是由若干路由器组成的 一个逻辑组。若干个逻辑组又组成更上一层的逻辑组。每个逻辑组在其上一层的 网络中只以一个逻辑节点表示，而忽略其内部细节，每个逻辑组在其边界的路由 器中将路由信息进行会聚；这样在组内的路由器仅仅知道在同一组内如何选择路 由和如何将分组送到目的端的全部细节，但对其他的组则只需要了解它们的会聚 信息。因此，分层路由中的信息传输量大大降低，网络的扩展性得到了改善。 分层路由结构如图1 所示。a a l ，a a 2 ，a a 3 ，a a 4 组成逻辑节点a a ，类似 组成逻辑节点a b 和a c ，再由a a ，a b ，a c 组成逻辑节点a 。 采用分层路由算法有许多集中式算法所无法比拟的优点，如： 1 由于采用分层的方法，顶层的节点数大大减少，由此减少了路由表的搜索 时间。路由表的计算量也大大减少一每一层节点内部的路由表只在内部有效； 2 每一层的节点只保存当前层的状态信息，与上下层都没有关系，从而减少 了对内存的需求量； 3 每一层节点只在同一层内进行节点状态信息的交换，从而降低了信息的传 输量，节省了网络资源。同时，本层节点内部状态信息的交换被限制在节点内， 不会扩散到其他节点； 4 在每一个节点所代表的一个区域内，所采用的路由协议和路由算法与别的 第一章绪论 区域无关，也就是说，不同的区域可以采用不同的路由协议和算法。 蕊 i 。 一，一 画商 图1 层次网络模型 分层路由机制的缺点是； 1 分层的处理，区域的划分，导致了网络状态信息的不准确、不及时； 2 网络状态信息的不准确，导致无法提供最优化路径，降低了寻径性能。 网络层次的构造基本上有两种：一种是以主干为核心的两层结构，另一种是 不依赖主干的多层结构。对于多层结构的构造，有自上而下的t o p - d o w n 方法和自 下而上的b o t t o m - u p 方法。采用分层路由机制，并非要否定现有的路由协议和算 法。因为在一个区域内，局部网络的规模可能很小，完全可以采用小规模网络情 况下的路由算法。因此，将分层寻径机制的研究与小规模网络情况下的路由算法 研究结合起来也是有意义的。 1 3 4 q o s 组播路由算法 随着网络技术的迅速发展，交互式会议电视，分布式网络游戏、协同文档编辑、 视频点播、网络电话、远程实时医疗等应用都对网络的服务质量( q u a l 姆o f s e r v i c e ， q o s ) 有所涉及，网络的服务质量包括网络中端到端时延、带宽、抖动等多方面的 约束。其中，端到端时延是实时通信应用中一个基本方面，对于实时通信来说， 如果延时过长，就会引起用户视觉和听觉上的不舒服，甚至引起语义的无法理解； 实时组播通信中，端到端的延时抖动则很重要，例如电视会议要保证各她的与会 者要同时听到发言者的讲话，从会场到各地的消息传输的延时必须限制在一定的 范围内，延时值只能在这个范围内波动；对于视频点播，网络必须提供足够的带 宽和可以接受的数据丢失率以保证一定的图象质量。 所以，提出q o s 组播路由算法来提高网络资源利用率，降低网络成本是很有 必要的。q o s 组播路由算法一般满足以下几点： !基于免疫克隆计算的m u l t i - a g e n t 组播路由算法 1 - 一般性：多媒体应用在带宽、时延、抖动、费用等方面有不同的服务质量 要求，从网络设计者来说，希望有一个一般的路由算法，能够针对不同类型的服 务质量要求。执行不同的路由策略； 2 扩展性：当网络基础设施扩大、能力增强、技术进步，路由算法应能适应 新的应用和环境； 3 简单性：路由算法容易维护和更新。 对于q o s 组播路由问题，一般包括最优化( o p t i m i z a t i o n ) 和给定某个约定 ( c o n s t r a i n t ) a 这些要求的组合就形成了用户对网络提出的各种q o s 要求。如我们 要求组播树中源节点到各个组成员的延时不高于某个定值，但组插树的费用要求 最小，这就是组播的路径延时受限和组播树优化的组合。组播q o s 路由问题中研 究得最多的是受限组播树( c o n s t r a i n e dm u l t i e a s ta l g o r i t h m ) ，其中包括延时受限最 小费用组播树，带宽受限组播树问题，延时抖动受限问题。如今除了启发式组播 路由算法以外，智能q o s 组播路由算法也成为研究的热点。由于q o s 路由闯题的 复杂性，引入人工智能方法是很合理的。 1 5 组播路由协议 要确定组播路由，首先要收集网络中的相关状态信息，路由算法就在这些信 息的基础上确定路由选择。网络的状态信息包括网络的拓扑结构、链路和路由器 的负载程度、链路和路由器的生效和有效、网络中路由器的类别( 是否具有组播 功能) 等。这些信息的收集是由路由协议( r o u t i n g p r o t o c 0 1 ) 来完成的。这一部分 介绍几个实际应用中的组播路由协议，其中d v r m p 和m o s p f 是由i n t e r a c t 上的 点到点路由协议r i p ( 路由选择信息协议) 与o s p f ( 开放式最短路优先) 派生出 来的。 1 4 1 组播开放式最短路径优先协议( m n l t i e m to p e ns h o r t u tp a t hf i r s t ， m o s p f ) l 删 m o s p f 是利用点到点的链路状态数据库，以o s p fv 2 为基础的组播路由协 议。由于o s p f 应用i ) i j k s t r a 算法进行路由选择，因此每个节点都要保存全嗣的拓 扑信息，所有节点对网络的看法一致。它不需发送任何分组，节点就可根据全网 链路状态表计算组中每个信源的组播树，而且各节点对此树的看法一致为了减 少计算量，m o s p f 可以按需执行算法，但该方法的缺点是增大延时m o s p f 的 最大优点是享有o s p f 对网络拓扑的变动快速反应能力。然而这个能力是 ；消耗路 由器c p u 资源为代价，不适用于网络拓扑不稳定的环境。随着网络中组数量的增 第一章绪论 7 加，这种消耗也在迅速增加。 1 4 2 距离向量组搔路由协议( d s t a n c ev e c t o rm u l f i c a s t r o u t i n gp r o t o c 0 1 d v m r p ) 1 2 1 i d v m r p 是一种距离向量路由协议，采用动态生成最短路径树。它由四个过程 构成：第一个是邻居查找过程，即查找网络上具有d v m r p 能力的路由器；第二 个是组播数据传输过程，即向期望接收组播数据的主机进行组播数据的传输；最 后是加入过程和剪枝过程，它们分别实现动态的从组播分发树中增加和删除接收 组播数据的主机和路由器。该协议不适合网络规模较大且对实时性要求较高环境。 1 4 3 独立点到点协议( p r o t o c o li n d e p e n d e n t m u i t i c m t , p i m ) i ? , 2 1 p d 讧设计的出发点在于在广域网范围内同时支持共享树与有源树。并能完成 两者之间的灵插转换，因而集中了两者的优点同时避免它们的缺点。当组成员较 为密集时以广播形式传送数据。然后从树上删除不存在接收节点的分支；而当组 员分布稀疏时，构造共享树传送，避免分组的广播开销分别对应以上两种情况， p n d 有两种模式：密集模式( d 蜘m o d e ，d m ) 和稀疏模式( s p a r s em o d e 。s m ) 。 p i m _ d m p - 3 1 是指在组播组所覆盖的区域内，组成员数量在子网中占很高的比 例。p i m - d m 优点是配譬简单，易于排错，并且可以和d v m r p 互连：它的不足 之处在于扩散和剪枝影响网络性能。 p i m - s m t 2 4 是在指组播组所覆盖的区域内，组成员数量在子网中占很低的比 例。在稀疏模式中，每个组播组有一个汇合点( r e n d e z v o u sp o i n t , r p ) ，组播源数 据先沿最短路径树向r p 发送数据，再由r p 沿共享树将数据发送到各个接收端， 随后直接建立组播源到接收端的最短路径树。其特点在于能从共享树向最短路径 树转换，直接建立从组播源到接收端的最短路径树，绕过r p 进行组播数据转发， 从而提高了组播包转发效率，减少了网络延迟和r p 上出现的瓶颈，改善网络性能。 1 4 4 基于核心树c b t ( c o r eb a s e dt r e e ) 协议i 巧i 在诸如分布式交互仿真和分布式交互电视游戏等组播应用中，在单个组播组中 有很多主动的发送者一c b t 协议构造一棵由所有组员共享的树，整个组的组播通 信都在这棵相同的树上发送和接收。一棵c b t 共享树以一个路由器为核心来构造 广播树。如果加入操作时，加入路由器先发送一个加入消息到核心路由器，再由 核心路由器返回一个确认消息，这样就形成一个树的分支。如果一个加入消息在 !基于免疫克隆计算的m u l t i - a g e n t 组播路由算法 到达核心路由器之前到达广播树上的一个路由器，这个路由器就会终止转发加入 消息，并返回一个确认消息，然后它就连接到共享树上。c b t 协议中核节点是瓶 颈，可通过多核路由来解决瓶颈问题。 1 4 5 专用网络接口协议( p r i v 叠t e n e t w o r k - n e t w o r k i n t e r f a c e 。p n n i ) 1 2 卅 p n n i 是一种基于分层结构的路由协议，它由两部分组成：第一部分是用于路由 选择的路由信息交换协议，该协议定义了a 1 m 交换机之间的拓扑及信息的分发处 理过程；第二部分进行整个路由域的路径计算过程。p n n i 网络中通过聚合和压缩 向上层路由域通告低阶层路由域的拓扑信息，在各逻辑组节点中各有一个核节点 负责本组中的路由通告和拓扑聚合。p n n i 的目的之一是要为这些度量的通告提供 某种手段，以便让各节点能够找出任意两个节点之间的最短路径。p n n i 的优点是 节约了存储空间并且大大减少了路由计算时间，但同时也增大了信息的不可靠性。 1 6 本文主要研究内容 本文主要研究了时延受限的组播路由问题，即如何构造满足时延约束条件且 费用最小的组播树。文中探讨了遗传算法、免疫算法以及免疫克隆选择算法等计 算智能方法在组播路由问题中的应用，并结合多智能体( m u l t i - a g e n t ) 方法提出 了两种时延受限的组播路由算法。 本文主要内容安排如下： 第二章主要介绍了本文中所涉及到的基本理论，主要包括s t e m e r 树理论及其 常用的启发式算法，进化计算基础理论的概述，q o s 问题的简要介绍等本章最 后介绍了本文所采用的仿真网络模型的产生方法，它是由北卡罗来那州立大学的 s a l a m a 和r e e v e s 在w a x m a n 网络的基础上提出的，与w a x m a n 网络相比，该网络 模型能更好的放映用户对节点的平均度的要求，并且不会有孤立节点产生。 第三章概述了a g e n t 和m u l t i - a g e n t 的基本理论，并介绍了m u l t i - a g e n t 同计 算智能方法结合所提出的多智能体遗传算法( m a g a ) 及其在函数优化方面的应 用情况。 第四章介绍了免疫算法及其应用于组播路由问题时疫苗的生成策略，并将免 疫思想引入m a g a 框架，利用时延受限的组播路由问题的先验知识作为疫苗，指 导和加速搜索。提出了一种免疫m u l t i - a g e n t 组播路由算法，并进行仿真实验以及 结果分析。 第五章介绍了计算智能方法一一免疫克隆选择算法，并将其搜索方式同 第一章绪论 9 m u l t i - a g e n t 相结合，提出了基于免疫克隆选择的m u l t i - a g e n t 组播路由算法，并对 其进行仿真实验以及结果分析。 最后对全文进行总结。 第二章组播树理论基础和算法 第二章组播树理论基础和算法 求解组播路由问题实际是构造费用最小的组播树，即求解最优s t e i n e r 树问题。 为此，本章介绍了有关s t e i n e r 树问题的理论及其相关的算法，并对算法的复杂度 和性能进行分析；本章最后介绍了q o s 的基本概念以及本论文中所采用的仿真网 络模型，由于能够较好地模拟真实网络，因此该模型被大多数研究组播算法和组 播路由协议的学者所采纳。 2 1 s t e i n e r 树问题 对于组播路由问题，一般要建立费用最小的组播树，而最优s t e i n e r 树的费用 是最小的，因此构造最优s t e i n e r 树被认为是实现组播通信的最好办法之一。s t e i n e r 树理论及其算法也成为求解组播树的基础。对s t e i n e r 树问题的研究早在上世纪6 0 年代就已经开始，到现在为止，已经有很多这方面的文献。s t e i n e r 树问题的应用 不仅在通信方面，在电路图的自动布线、交通线路的经济规划、车辆的调度和编 组、通信线路的铺设等方面都有应用。 本文讨论计算机通信网络中的组播路由问题，在计算机通信网中一般用无向 连通图来表示。为此我们主要研究无向带权连通图中的s t e i n e r 树算法及其性能。 首先给出无向带权连通图上s t e i n e r 树问题的定义。 计算机网络可以抽象为无向连通图：g = ( k 毋，其中v 为网络节点( 路由器) 的集合，点为边( 通信链路) 的集合，在每条边e e 上定义一个权值函数 c ( e ) ：e r + ，表示每条边的费用( 这是一个广义上的费用，它可以根据链路的距 离、信道带宽、平均通信量、通信时延等计算出来) ，给定一个节点子集d 矿， 这里d 对应为组播组成员，s t e i n e r 问题就是寻找一棵覆盖给定节点集合d 且费用 最小的最优s t e i n e r 树= ( ，) ，s e ，用c ( ) 表示树的费用，即： c q 叫) 2 厶c t e ) l 从最优s t e i n e x 树的定义可知，最优s t e i n e r 树中的叶子节点都应是d 中的节点 ( 组播组成员) ，一般称d 中的节点为基本节点；最优s t e i n e r 树中除基本节点外 的其它节点称为s t e i n e r 节点，图g 中所有可能成为s t e i n e r 节点的节点集合记为s ， 易知d n s = a 。矿= d u s 。 最小生成树和最短路径阿题都是s t e i n e r 树问题的特例。当d = v 时，s t e i n e r 树问题就转化为最小生成树问题；而当给定节点集合中只包含两个节点时，即i d i _ 2 基于免疫克隆计算的m u l t i - a g e n t 组播路由算法 时就变为最短路问题。最小生成树问题和最短路径问题都存在多项式时间的最优 解法，但s t e i n e r 树问题是一个n p c o m p l e t e 问题，它不存在多项式时间的最优解 法。 2 2 s t e i n e r 树的启发式算法 前面已经提到，s t e i n e r 树问题是n p - c o m p l e t e 问题，为此针对该问题一般讨 论解决它的启发式算法，使我们能在一个低阶多项式时间内得到一个“接近”最 优的解。启发式算法并不保证给出最优解，那么如何评价启发式算法的好坏就主 要是基于两个方面的考虑：首先是时间复杂性方面的要求，即要求有一个多项式 时间界：其次是性能方面的要求，即希望所求的近似解尽可能“接近”最优解。 可以从不同角度未评价启发式算法的性能，大体上可分为三类：第一类是以算法 在最坏情况下的表现为标准，研究算法得到的近似解与最优解的接近程度，越接 近则算法质量越高；第二类是以算法的平均行为为标准，研究得到最优解的概率； 第三类是局部搜索算法，寻找局部最优解。 在组播通信中，最优组播树问题就是求解最优s t e i n e r 树问题，下面简单介绍 几种最常用的s t e i n e r 树问题的启发式算法： 2 2 1 无约束最小生成树算法 其目标函数如下： m i n ( c o s t ( t ( s ，d ) ) ) ( 2 2 - 1 ) 丁 d ) 表示覆盖源节点和组成员的一棵生成树。无约束s t e i 榭算法并不能优化端到 端时延，因此也许并不适合实时网络的应用。 k o u ，m a r k o w a d 和b e r m a n 提出的k m b 算法【5 1 是最著名的无约束最b s t e i n e r 树 算法，它在有些文献中又被称为d n h 算法，算法步骤描述如下： 算法1k m b 算法 s t e p l ：构造图g 的距离完全图g ，_ ( d ，e ) ，其中v ( u ，y ) e 是图g 中节 点“到节点v 的最短路径，即边0 ，v ) e 的费用等于g 中节点“到节点v 的最短 路的费用； s t e p 2 s t e p 3 s t e p 4 s t e p 5 构造图g 的最小生成树t ； 将r 呻的边再转换为g 中的最短路径，形成子图g s ； 求出国的最小生成树乃； 删除t s 中非基本节点的叶子节点，最后得到所求的树l 第二章组播树理论基础和算法 k m b 算法在计算过程中使用了p r i m 算法，由于p r i m 算法被用来优化对称网络， 因此当被应用于非对称网络时，k m b 算法的性能会受到影响；k m b 算法在对称网 络上得到的组播树的费用一般只比最优s t e i n e r 树 2 8 , 2 9 高5 。k _ m b 算法的时间复杂 度为0 ( 1q i m 2 ) ，d w a l l 在文献【3 0 】【3 l 】中提出了k m b 算法的分布式计算的版本。 2 2 2 无约束最短路径算法 最短路径算法以分别最小化连接源节点和组成员的各条路径的长度为目标。 最短路径树( s p t ) 的性质根据衡量链路的标准不同，分为以下几种： 1 最小跳数( m i n i m u m - h o p ) 树，每条链路都设为单位长度。 2 最短路径费用( k a s t - c o s t , l c ) 树长度设为该链路费用，此时最短路 径算法目标函数可用下式表示： r , a n ( c o s t ( g 辑g ) ) ) b 留e d ( 2 。2 - 2 ) r 是根为信源节点j 并且覆盖组成员集合d 的树，其总费用不一定是最优的。 3 最短路径时延( l e a s t - d e l a y , l d ) 树，目标函数如下式： r n i n ( 蚓弓( j ，g ) ) )v g 芒d ( 2 ，2 - 3 ) 其参数意义同l c ，只是链路代价变成了时延 b e l l m a n - f o r d 算法1 3 2 1 、d i j k s 岫算法【2 堤最著名的两种最短路径算法，这两种算 法都能很好的运行在非对称网络上，并在多项式对问内收敛。b e l l m a n - f o r d 算法的 时间复杂度为o ( i v l 3 ) ，i 纠为网络节点总数。文献 3 3 1 给出了分布式b e l l m a n - f o r d 算 法，它的计算仅需要保留在各个网络节点中有限的网络信息即可。但a w e r b u e h 等 人【3 4 】证明了在最坏情况下分布式b e l l m a n - f o r d 算法的计算复杂度有可能随网络节 点数的增加而呈指数级增长，因此提出了该算法的两种不同的分布式版本，有效 的解决了计算复杂度过大的问题。d i j k s t r a 最短路径算法没有分布式计算的版本， 它的时间复杂度为o ( 旷1 2 ) 。文献【3 5 】给出两种算法运行时间的比较 2 2 3 遗传算法( g e n e t i ca l g o r i t h m ，g a ) m 1 遗传算法是在上世纪7 0 年代初期由美国的h o l l a n d 教授发展起来的，是以达尔 文自然进化与遗传变异理论为基础的求解复杂全局优化问题的仿生型算法。它是 智能计算( i n t e l l i g e n tc o m p u t i n g ) 中的一个重要内容，智能计算也称为软计算( s o f t c o m p u t i n g ) ，它是受自然界规律启迪，根据其原理模仿设计求解问题的算法，由 伯克利大学教授l 。z a d e h 提出的1 3 7 j 。由于本文后面提出的算法需要同遗传组播路由 算法进行比较，因此有必要介绍一下遗传算法的基本概念和计算过程。 兰基于免疫克隆计算的m u l t i - a g e n t 组播路由算法 遗传算法模拟生物进化过程通过向自然学习来求解问题，利用简单的编码 技术和繁殖机制来表现复杂的现象，从而解决非常困难的问题。遗传算法是一种 基于自然选择和遗传的概率搜索算法，尤其适用于处理传统搜索方法难于解决的 复杂和非线性问题。它已被广泛地应用于组合优化、机器学习、并行处理、人工 智能、自适应控制、人工神经网络训练等优化问题中。 遗传算法从一个称之为群体的随机初始解集合开始，通过对群体实施遗传操 作以实现群体内个体结构重组的迭代过程。下面介绍遗传算法中的一些主要算子 和基本概念： 1 选择算子( s e l e c t i o n o p e r a t o r ) 选择算子的作用是选择群体中适应度较高的个体构成新的一代群体。其中每 个个体被选中的概率取决于该个体对环境的适应程度。 2 交叉算子( c r o s s o v e ro p e r a t o r ) 交叉算子通常作用在两个不同的个体上把两个个体基因中的某一部分相互互 换，产生两个新的个体。交叉算子以一定的概率发生作用，可分为单点交叉、多 点交叉、均匀交叉、线性交叉和算术交叉等。 3 变异算子( m u t a t i o no p e r a t o r ) 变异算子是在遗传算法中用来模拟生物在自然界的遗传环境中