（运筹学与控制论专业论文）组播通信的路由选择算法分析与设计.pdf

东北大学硕士学位论文 第一章绪论 1 1研究背景 第一章绪论 随着光纤技术在网络传输中得到应用，信息高速公路已经在全世界范围内成网 状发展，为i n c e m e t 的不断壮大提供了硬件基础。同时，网络在各个领域上的应用， 也为我们带来了巨大的效益，网络被越来越多的人所认可。与此同时，人们又对 网络提出了更多的要求，从而出现了许多新兴的网络业务，如视频点播、电视会 议、实时信息公告、远程学习、大规模协作计算、分布式网络游戏、推送技术、 远程医疗等等。显然，如果在这些业务中使用单播的话，其效率是非常低的，不 能够满足用户的需求，而广播又会大量的浪费网络资源。1 9 9 2 年3 月，人们使用 组播主干网成功地举行了一次网络会议，从此组播受到了人们的重视并取得了很 大的发展。 在人们使用组播技术时，音频、视频的传输质量是非常重要的。因为高的延时、 延时抖动和丢包率是不能容忍的。所以q o s ( 服务质量) 又重新得到了人们的重 视。在光纤技术被使用以前，q o s 是一项有争议的概念。但是现在，没有人会再 怀疑它的作用了。这就好象是在胡同里不会出现红绿灯和交通警察，而在宽广的 网状公路上就必须有交通规则一样。因为再宽的公路如果没有交通规则的话也会 出现堵车。同理，再大的带宽，如果没有q o s 也一样会出现拥塞。 q o s 这个术语，用来定义网络给不同形式的流量提供不同级别的服务保障的能 力。它使网络管理员能指定某种流量的优先权或网络带宽，或端到端延迟的实际 质量级别。许多协议( 如：h t t p ) 和应用对网络拥塞不是很敏感，但是有些网络业 务必须确保在某个底线的基础上将信息传递到正确的地方。q o s 的目的就是满足 要求苛刻的业务需要，并与要求并不苛刻的业务共享网络资源。目前，在网络设 备中设置q o s 的方法和协议的数量飞速地增长。无论网络是用于小型公司、企业， 还是i n t e m e t 服务供应商，所有的网络都可以充分利用q o s 的方方面面以获取到适 宜的性能。 为了确保组播通信的服务质量，路由选择算法已经成为其至关重要的因素。路 由选择算法( r o u t i l l ga l g o r i f h m ) 是网络层软件的一部分，负责确定所收到分组应传送 的外出路线。随着计算机网络的发展，为了达到网络资源的最佳使用，寻求高效 的组播路由选择算法将显得越来越迫切。 东北大学硕士学位论史 、 第一章绪论 组播通信的服务质量。这被证明是一个n p c ( n o n d e t e 珊i n i s i i cp 0 l y n o m i a l c o m p l e i e j 问题，因此必须采用启发式算法。 1 2 研究现状 1 2 1现有的组播路由算法 实现组播路由最普遍的方法是构造树型路由结构，这是由于基于树实现有效 的组播路由具有以下两个优点：1 ) 分组以并行方式沿着树枝发送到不同的目的节 点；2 ) 网络中需要传送的复制分组最少，而且分组的复制只在树权处进行。 在现有的树型组播路由算法中，优化目标一般有两种。一个目标是端到端最 小延迟，这对于实时会议等多媒体应用来说是至关重要的。它通常通过寻找从发 送端到每一个接收端的最短路径来实现。它虽可以保证源到每个目的结点的最小 延迟，但网络开销较大。另一个目标是尽可能有效地利用网络资源。这个目标对 应于两个参量：最小化占用链路总带宽；最小化链路拥塞。用这种方式得到的组 播树网络开销小，但是以牺牲了端到端的最小延迟为代价的。 现有的主要组播路由算法包括：扩散( h o o d i n g ) 算法、分发树( s p a n i n gt r e e ) 算 法、逆向路径广播f r p b ，r e v e r s ep a 幽b r o a d c a s i n g ) 算法、修剪的逆向路径广播 f r r p b ，1 1 m n c a t e d r e v e r s e p a t h b r o a d c a s t i n 武算法、逆向路径多点播送( r p m ，r e v e r s e p a t hm u l t c a s t ) 算法、核心分发树( c b t ，c o r e b a s e d1 1 r e e ) 算法i l j 。 ( 1 ) 最简单的组播路由算法是扩散算法。当路由器收到一个组播分组时，它 首先确定这是否是该分组的第一次出现。如果这是第一次收到该分组，路由器向 除接收端口外的所有端口转发该分组，保证该分组到达网络上的所有路由器。如 果不是第一次收到该分组，它简单丢弃该分组。 由于路由器只需跟踪最近收到的多点播送分组，不需维护路由表信息，扩散 算法的实现是十分简单的。因为扩散算法会在网络上所有可用的路径上复制同 个组播分组，浪费网络带宽资源，因而不适用于h l t e m e t 范围的应用。由于每个路 由器都要维护最近收到的组播分组列表，占用大量路由器内存资源。 ( 2 ) 比扩散算法更有效的一个算法是选择网络拓扑连接结构的一个子集，形 成一个分发树。分发树是在网络中定义的一个以路由器为中间结点的树状结构， 使得网络中任何两个路由器在分发树上只有一条唯一的路径相连。 在定义了分发树后，路由器简单地转发每个组播分组到除接收到该分组的网 卜 东北大学硕士学位论疋 第一章绪论 络接口外的每个分发树分支的网络接口。沿着分发树分支的组播分组传送保证组 播分组不构成循环，并且网络中各路由器都可收到每个组播分组。 分发树算法很有效，并相对容易实现。但它的问题是把所有分组的传送集中 到少量链路上，并且不是从发送方到接收群组成员的最优路径。 ( 3 ) 分发树算法是为整个网络构造一个唯一的分发树，r p b 算法则是分别为 每个发送方所在子网构造以该子网为根的分发树。 如果路由器可确定本身是否位于从发方子网到另一个相邻路由器的最短链路 上，r p b 算法可修改成为改进的r p b 算法。这种改进可减少不必要的组播分组复 制。 r p b 算法的好处是比较有效和易于实现。它不要求路由器了解整个分发树， 不需要某种机制停止转发过程。它保证组播分组的转发是沿着从发方剑接收群组 成员的最短路径进行的。组播分组的转发是在多条链路上进行的，从各发方子网 出发的分发树是不同的，网络负载较均衡。 r p b 算法的缺点是它在生成分发树时没有利用接收群组成员的位置信息，导 致组播分组被不必要地转发到没有接收群组成员的子网上。 ( 4 ) t r p b 算法的设计是为了克服r p b 算法的缺点。路由器利用互连网群组 管理协议( i g m p ，i n t e m e tg r o u pm a n a g e m e n tp r o t o c 0 1 ) 可确定直接相连子网上是否 有接收群组成员，避免向直接相连而没有接收群组成员的子网转发分组。t r p b 算 法的缺点是它只部分地解决了r p b 算法的问题，可修剪掉没有相应接收群组成员 的叶子网，但无法修剪分发树的分支。 ( 5 ) r p m 算法是对r p b 算法和疆b 算法的改进。r p m 算法生成的分发树 只包括：1 ) 有接收群组成员的子网2 ) 从发方子网到有接收群组成员子网的中间路 由器和子网。 r p m 算法对分发树进行修剪，以使组播分组只向接收群组成员转发。 对于一个特定的( s o u r c e ，g r o u p ) 对，路由器收到的第1 个组播分组是沿t r p b 算法生成的分发树转发，保证分发树中每个叶路由器都可收到第1 个组播分组。 随后通过在分发树上路由器间传送修剪报文，停止向没有接收群组成员的分支转 发相应的组播分组。修剪报文的生成和传送使组播分组分发树只包含能通向接收 群组成员的分支。 r p m 算法的优点是网络带宽资源的利用率极高。它的缺点是试图在整个网络 上建立组播分组发送服务时的可扩展性问题。组播分组必须周期性发送到整个网 络上的所有路由器。它要求每个路由器维护所有接收群组和发送方的状态信息。 当接收群组和发送方的数目扩大时，这是一个很大的问题。 卜 东北大学硕士学位论文 第一章绪论 ( 6 ) c b t ( c o r c _ b a s e dt r e e ) 算法不是为每个( s o u r c e ，g m u p ) 对计算一个以发方 为根的分发树，而是针对一个接收群组和它的所有发送方建立一个分发树。除了 为每个接收群组设置不同的核心分发树外，c b t 算法类似于分发树算法。不管发 送方的位置如何，一个接收群组的所有组播分组都通过相同的分发树传送。一个 核心分发树有 个或多拿路出器作为“核心路由器( c o r er o u t e n ”。发送方的组播分 组被路由器以点到点的方式向该接收群组的核心路由器传送。当遇到相应接收群 组分发树的路由器时再沿分发树向所有接收群组成员传送。 c b t 算法的优点是可扩展性比r p m 算法好。c b t 算法只需要每个接收群组 有一个路由器维护相应的群组状态信息，而不是每个( s o u r c e ，g m u p ) 对的状态信息。 c b t 算法也不会周期地把组播分组传送到整个网络的所有路由器。 c b t 算法的缺点是：( 1 1 组播分组的转发集中在核心路由器周围，会彤成拥塞。 ( 2 ) 由于同一接收群组的所有组播分组都从一个分发树传送，分发树不是最短路径。 这会增加组播分组的传输延时。( 3 ) 核心路由器的位置选择和管理会带来管理上的 困难。 1 2 2 一些新兴的组播路由启发式算法 近年来，人们针对q o s 组播路由问题提出了些启发式算法。 ( 1 ) 文献 2 】提出了一种q b r ( q o s b a s e d r o u t i n g ) 算法，该算法以带宽、延 时和站点计数为优化目标，其基本思想是在满足带宽和延时约束的前提下，寻找 一棵带宽较大、延时较小、站点计数较少的组播树。这种算法有两点不足：一是 将站点计数作为一个新的优化目标，而站点计数的多少只能说明路径的长短，不 能够说明用户的网络花费较少；二是由于该算法需要找到所有满足带宽和延时约 束的组播树，其时间复杂度较大，因此不适用于大型网络。 ( 2 ) 文献【3 】、【4 】、【5 】、【6 】是在考虑了延时约束的基础上对网络花费进行了 优化，但是诸如带宽等q o s 约束没有被考虑进去。同时，这几种算法同样不适用 于大型网络。 ( 3 ) 文献【7 、 8 】中提到的两种算法考虑了多种q o s 约束，同时对网络花费 进行优化，但是同样没有解决时间复杂度较大的问题，使算法无法应用于大型网 络。 ( 4 ) 在文献一些中( 如【9 】、【1 0 、【1 1 、【1 2 】等) ，均采用了遗传算法作为 组播通信路由选择的方法。由于遗传算法具有并行搜索、整体寻优的特点，因此 大大降低了算法的时间复杂度。 一d 一 东北大学硕士学位论文 第一章绪论 遗传算法( g e n e t i cm g o r i t h m s ) 是在7 0 年代初期由美国密执根( m i c h i 2 a n ) 大学的h o l l 姐d 教授发展起来的1 1 = j j 。近三十年来，计算机学者对模拟自然过程，特 别是生物进化过程的算法产生了日益浓厚的研究兴趣。研究分析表明，软件技术 同生物技术有很大相似之处。研究者认为，软件这种智力的产物，同智力自身的 起源有着密切的联系。目前，人们已经开发出了许多著名的仿照自然过程的算法， 如：遗传算法( g e n e t i c 越g o r i i h m s ，简称g a ) 、进化策略( e v o l u t i o s t r a t e 西e s ) 、模 拟退火( s i m u l a t e da n n e a l i n 曲、进化程序设计( e v o l u t i o n a r y 点不足：一是 将站点计数作为一个新的优化目标，而站点计数的多少只能说明路径的长短，不 能够说明用户的网络花费较少；二是由于该算法需要找到所有满足带宽和延时约束的组播树，其时间复杂度较大，因此不适用于大型网络。 ( 2 ) 文誉劐魁蹬善耍霎* i 熹箨督强隔税蒋暑蘸羹萄，蘧臻些蓄慰季聂璺烈型 睦鏊燃专臻。 ；i莹冀!，；!丽k灯矧菇唑羹动鼬并明进化过程应用与人为系统的构造。一般而言， 许多自适应问题可用遗传术语来描述，而后使用所谓“遗传算法”(或其变形) 来求解。 遗传算法是模拟生物进化的过程及其在染色体上自然发生的遗传操作。生物 细胞中存在的染色体是由四个核苷酸构成的串，我们可将其看成一个四进制字符 串( 即字母表长度为4 ) 。这四个核苷酸沿着d n a 分子排列，不同的排列构成不同 的遗传密码。dna分子能够精确地自我复制，而且，dnax 东北大学硕士学位论支 第一章绪论 体的结构决定了生物体在环境中的表现及生存与繁殖率。子孙的染色体包含了来 自父辈的核苷酸串，这些核苷酸串将导致后代有优于父辈的性能。染色体上偶尔 也出现变异，使得后代群体能够出现多样性。 遗传算法是一种高度并行的数学算法，它使用以遗传操作为模式的数学操作， 将一组数学对象，转换为新一代群体，通常，每个数学对象是以染色体串的模式 出现，每个染色体串都具有一个适应度( f i t e s s ) 。以下简单介绍遗传算法的工作 机理【3 】。 一般而言，任何抽象的任务都可以认为是求解一个问题，而问题求解又可看 成对解空问的搜索。由于我们总是希望寻求“最佳”的解，因此可把求解过程当 作个优化过程。对于小空1 1 日j ，经典的穷举搜索方法足以解决问题；然而对较大 空间，就需要采用自适应的、智能的搜索技术。遗传算法正是这种模拟自然界生 物进化过程的自适应寻优技术，它的主要应用领域是复杂的非线性优化问题。尽 管遗传算法可归类为概率算法，但它不同于随机算法，它把定向搜索与随机搜索 有机地结合起来；正因如此，遗传算法也强于已有的定向搜索算法。 遗传算法的另一个重要的特点是使用一个潜在解的群体来搜索解空间。其它 方法一般总是采用单点搜索在解空间中寻找最优解，这些算法非常依赖于起始点 的选择，而且往往只能得到局部最优解。与此相对照，遗传算法是一个潜在解的 群体中进行多个方向的搜索，同时，在搜索过程中鼓励不同方向上信息的结合和 交流。群体经历了一个模拟进化过程：在每一代，较好的解“繁殖”，较差的解“消 亡”。在这个过程中起关键作用的目标函数( 适应度计算函数) 用于区别解的优劣。 一般说来，解决一个具体问题的遗传算法由下述五个部分组成1 1 3 j ： f 1 ) 制定问题的潜在解的遗传d n a 表示方法； 创建潜在解的初始群体的方法； ( 3 ) 评估解的适应度的计值函数( 适应函数) ； f 钔改变子孙结构的遗传操作； ( 5 ) 算法适用的各种参数、变量及终止条件等。 经典遗传算法的表示模式是将问题搜索空间中的每一个点表示为定长字符 串，即字母表k 上长度为l 的字符串，确定染色体串与空间点之间的映射关系有 时是显而易见的，有时则非常困难，需要对问题有深刻的认识和正确的判断。 根据需要解决的问题的性质，为群体中的每一个个体赋一个适应度值。改变 子孙结构的遗传操作主要有复制( r e p r o d u c t i o n ，也称繁殖) 、交叉( c r o s s o v e r ， 也称交配) 和变异( m u t a t i o n ) ，而控制遗传算法的参数包括群体的大小( 种群规 羔当釜姜巽考姜篓篓当：。：。一 苎二主竺堕 模) ，进化过程的最大代数以及控制各种遗传操作的概率等。 一。 经典遗传算法的执行步骤如下： ( 1 ) 【开始( s t a r t ) 1 ：随机创建由n 个染色体组成的初始种群； ( 2 ) 【适应度( f i t n e s s ) 】：为种群中的每 个染色体x 计算适应度f ( x ) ，其中f ( x ) 为适应函数； ( 3 ) 【产生新的种群( n e wp o p u l a t i o n ) 】：循环进行下述各步，直到新的种群创建结 束： 【选择( s e l e c t i o n ) 1 ：根据适应度值的大小( 适应度值越大，被选中的概率 就越大) 选择父代染色体； 【交叉( c r o s s o v e r ) 1 ：根据交叉率，对父代染色体进行交配，从而产生新的 子代个体。如果不进行交配，那么子代即为父代的一个拷贝： 变异( m u t a t i o n ) 】：根据变异率，对新的子代个体进行变异操作； 【接收( a c c e p t i n g ) 】：新的子代成为新的种群中的个体； ( 4 ) 替换( r e p l a c e ) 】：新产生的子代种群成为下一次计算的父代； ( 5 ) 测试f r e s t ) 】如果满足终止条件，则停止，并返回当前种群中的最好个体， 否则转入下一步： ( 6 ) 【循环( l 0 0 p ) 】：返回( 2 ) 步； 下图可以简单的描述遗传算法的步骤： l 编码和初始群体生成 l 扣 富 舌 图1 1 遗传算法描述 f i g 1 1c h a r to f g e n e t ca l g o t h m 上述遗传算法的组成与执行过程，表明了这是一种与领域无关的方法，它可 以解决大量的不同方面的问题( 包括我们要解决的问题) 。 j 1 一 东北大学硕士学位论文 第二章组播通信及其q o s 管理 第二章组播通信及其q o s 管理 2 1组播 组播是一种点到多点( 多点到多点或多点到点) 的通信方式，即多个接收端同 时接收个源发送的相同信息【1 5 j 。同单播( u n i c a s t ) 或广播( b r o a d c a s t ) 相比，组 播( m u l t i c a s t ) 的效率非常高，它能大大降低网络、服务器负载改善传输性能， 因为任何给定的链路至多用一次。这种效率优势随着网络规模和接收者数量的增 加而增加。与广播方式不同，组播允许每台机器选择是否参加组播，允许进行资 源发现，使网络负载减到最小，因此非常适合多点间的对话。 单播广播 图2 1 组播、单播和广播 f i g 2 1 m u l t i c a s t 、u n i c a s ta n db i d a d c a s t 组播 目前，这项技术已获得了包括c i s c 0 、朋破t 、m m 、i n t e l l 、m i c r o s o f t 等业界 的众多厂商的支持。并且已经获得一定范围的商业应用，例如，c i s c o 公司采用 i p 厂r v 来进行实时视频流组播用于公司内部的会议和培训；亚运村采用c i s c o 设备 构造北辰园区网络提供砰组播业务等等。 2 1 1 组播地址 在i p 地址中，d 类地址为组播地址【1 5 l ，组播地址与单播地址不同，它不是代 表一个特定主机，一个组播地址代表该组播组中所有接收组播分组的主机或者路 由器。 东北大学硕士学位论文 第二章组播通信凌其q o s 管理 o12 34 3 2 匠工工互二耍圈 图2 2 组播地址 f i g 2 2 a d d r e s so fm u l t i c a s t 地址的前4 个比特的内容是1 1 1 0 ，标识出这个地址是一个组播地址，其余的 2 8 比特标识了特殊的组播地址。在这个2 8 比特的组字段中不再有结构层次。特别 是，组字段并不标出组来源。也不会像a 、b 、c 类地址那样包含一个网络地址。 使用点分1 - 进制表示法来描述组播地址的范围是2 2 4 0 0 o 到2 3 9 2 5 5 2 5 5 2 5 5 。但 是地址2 2 4 ，o ，o 0 是保留的，它不能被赋给任何组，而2 2 4 0 0 1 也是永久性地赋给 了全主杌细( a l lh o s t s g r o u p ) 。它标识了参与该i p 组搔的所有毛机和路由器的集合。 2 1 2i n t e r n e t 组管理协议 为了参与本地网络上的口多播，主机必须使用允许收发组播数据报的软件。 而为了参与跨越多个网络的组播，主机就要通知本地的组播路由器，本地组播路 由器与其他组播路由器联系传送组成员关系信息，建立组播路由。这与通常的互 联网络中的路由器广播路由信息的过程很相似。 在一个组播路由器能够传播其多址组成员关系信息之前，它必须确定在本地网 络上有一个或多个主机已经加入了某个组播组。为此，组播路由器和实现组播的 主机必须使用i g m p ( i n t e m e tg r o u pm a n a g ep i o t o c o l ，i g m p ) 协议来进行组成员 关系信息的通信。 i g m p 的工作分为两个阶段【。第一阶段：当主机加入一个新的组时，它发送 一个i g m p 报文给全主机组播地址，宣布这个成员关系。本地组播路由器接收到 这个报文之后，向互联网上的其他组播路由器传播这个关系信息阻建立必要的路 由。篼二阶段：为适应动态的成员关系，本地组播路由器周期性地轮询本地网络 上的主机，以便确定现在的各个组中有哪些主机。如果经过若干个轮询后，某个 组中始终没有成员，组播路由器就认为该组中不再有本网络中的主机，于是停止 向其它组播路由器通告该组的成员关系信息。 i g m p 应仔细设计以避免本地网络的阻塞。首先，所有的主机与组播路由器之 间要使用i p 组播进行通信。当i g m p 报文封装到妒数据报中传送时，】p 目的地址 是全主机组播地址。因此，携带i g m p 报文的数据报在传送过程中，尽量耐用硬 件的组播能力。其结果是，在硬件支持组播的网络上，不参与i p 组播的主机就不 日，左派在柏林召开全国代表大会，形成了“国际派”( 0 m p p e i n t e m a t i o n a i e ) 。 1 9 1 6 年1 月1 日，国际派再次召开全国会议，通过了由罗莎卢森堡( r o s a l u ) c e m b u 理) 起草的世界各国社会民主党的任务的提纲，谴责右翼机会主义 的战争政策，强调党的任务是坚决反对“资产阶级的民族主义”。大会还决定定 期发行政治信札，李h 克内西用笔名“斯巴达克”发表了第一封通信，因而 后来人们也将“国际派”称作“国际派( 斯巴达克团) ”( g m p p ei n t e m a t i o n a l e ( s p a n a l 【u s g r u p p e ) ，以下简称“斯巴达克团”) 。不过，直到此时，斯巴达克团 还不是独立的政党组织。 1 9 1 6 年3 月2 3 日，社会民主党原主席胡戈哈阿兹在国会中严厉批判政 府的战争政策。一年后，以哈阿兹为首的一部分社会民主党人决定另行成立党中 央，同以艾伯特为首的右翼划清界限。他们自称是“独立社会民主党”( u s p d ) ， 原来的社会民主党则被视作“社会民主党多数派”( m s p d ，但在政治场合保留 “社会民主党”的称呼) 。由于在反对战争的立场上保持一致，斯巴达克团决定 加入独立社会民主党。 战争末期，在柏林的军工企业中出现了“革命者团体”( d i er e v o l u t i o n 蕴r e n 0 b l e u t e ) ，他们在组织关系上隶属自由工会，但反对“城堡和平”，更不愿意履 行为祖国志愿服务法。这些革命者主要是柏林五金工人联合会车工分会 ( d r e h e r - b 啪c h ei mb e r l i i l e rm e t a l l a r b e i t e r v 盯b a n d ) 的会员，主席是里夏德米 勒。1 9 1 8 年，原来的前进报编辑、后来的独立社会民主党柏林消息报( b e r l i n e r m i t t e i l u n g s b ) 编辑恩斯特道尔米施也加入其中，成为革命者团体的精神领 袖。另一位独立社会民主党中央委员格奥尔格雷德鲍尔( g e o r gl e d e b o l l r ) 也 参与组织工作。1 6 1 革命爆发前夕，革命者团体成员多为独立社会民主党党员。 至此，统一的社会民主党在1 9 1 8 1 9 年革命爆发前夕，在组织形式上已经分 裂为两个政党：社会民主党( m s p d ) 与独立社会民主党( u s p d ) 。然而从思想 上来看，独立社会民主党却不是统一的，它可以分为：以胡戈哈阿兹为首的独 立社会民主党右翼：以罗莎卢森堡与卡尔李h 克内西为首的斯巴达克团( 后 改为斯巴达克同盟，1 9 1 8 年1 2 月底成立德国共产党，k p d ) ；以里夏德米勒与 恩斯特道尔米施为首的革命者团体。 二、社会民主党 大战爆发后，社会民主党同国家的关系发生了根本变化，从反对派向改革 派演变，改良主义思想占据党内舆论主流。1 9 1 7 年首相更迭后，出于共同反对 “、p 时钟y o no e n z e n ，8 e 押汹s r m ei nd 8 rn o v e m b e r 他v d t “i 0 e i mp d 讲h 讧s e 髓c h 晔“c hu 呲e r s h t t n 2 曲e r 东北大学硕士学位论文第二章 组播通信及其q o s 管理 源浪费。 当然，稀疏模式也有一些缺点，这主要与使用r p 有关。第，r p 可能是一 个故障点。第一，r p 是组播业务流的集中点。第= ，使业务流从源到r p ，又到 接收者，可能无法找出最优路径。第一个问题可由b o o t r a p 选路洳议解决。后两个 问题在c b t 中，使用双向树来解决，而p i m s m 中则是通过一种将共享树变为最 短路径树的机制来解决。 2 2 组播通信的q o s 管理 2 2 1q o s 概述 q o s 是一套可利用的工具，网络管理员用客观存在来保证对某种流量提供最小 级别的服务l 。许多协议和应用对网络拥塞不是很敏感。例如，文件传输协议( f r p ) 能极大忍受网络延迟或带宽限制。对用户来说，n 甲只是需要长一点时间下载文 件到目标系统。虽然使用户心烦，但是这种缓慢并不妨碍应用的运行。另一方面， 新的业务如语音和视频对网络延迟特别敏感。如果语音数据包花很长时间到达目 的地，结果讲话声音会断断续续或失真。q o s 用来给这些应用提供有保障的服务。 2 2 2q o s 参数 我们经常发现使网络达到更好性能的最简单的方法是增加带宽。在当今g 比 特以太网和光纤网络的时代，更高的带度很容易达到。但是，更多的带宽并不总 是能保障报务的某个级别。有些容易导致拥塞的协议很容易吃掉已增加的带宽， 导致出现与带宽升级前一样的拥塞问题。一个更明智的方法是，分析通过颈瓶的 流量，判断每个协议与应用的重要性，然后给访问带宽的优先权分等级。 q o s 的主要参数包括：带宽、时间延迟、延迟抖动和丢包率。不同类型的业务 对q o s 参数值的要求可能相距甚远。例如，一个未经压缩的n t s c 制式的真彩色 视频应用需要高达2 7 m 字节秒的带宽，而一个电话质量的音频应用只需要6 4 k b p s 的带宽。不同的网络通信应用对q o s 的具体要求通常也有所不同。例如，实时交 互式计算机会议系统对时间延迟要求相当严格，一般在2 5 0 m s 以下，而电子邮件 则无此要求。表2 1 给出了部分网络通信业务对q o s 参数的要求。 东北大学硕士学位论文 第三革一种基于遗传算法的组播路由算法 已证明，两个不相关可加度量的q o s 组播路由问题是n p c 问题。显然，上述 q o s 组播路由问题属于n p 完全问题，其延时、费用为可加度量且互不相关。 因此只能用启发式算法解决该类问题。 3 2 遗传算法的基本工作 3 2 1编码 编码是遗传算法中的基础工作之一。为了便于遗传操作，解决不同的问题需要 使用不同的编码方式。以下是在实际问题中应用过的几种编码方式1 1 引。 ( 1 ) 二进制编码( b i n a r ye n c o d i n g ) 二进制编码是最常见的编码方式，这可能是由于最初的g a 算法都用这种编码 方式。该编码方式使每一个染色体都是由0 ，1 组成的二进制串。如： 染色体a ：l o l l 0 0 1 0 1 1 0 0 1 0 l o l l l 0 0 1 0 1 染色体b ：l l l l l l l o o o 0 0 1 l o o o 0 0 1 1 1 1 1 ( 2 ) 捐 歹0 编码( p e m u t a t i o ne n c o d i n g ) 排列编码中的每一个染色体都是一个数字串，每个数字代表序号。如： 染色体a ： 15 326479 8 染色体b ： 856723 149 ( 3 ) 数值编码( u ee n c o d i n g ) 在数值编码中，每一个染色体是由一串数值组成的。数值可以是与问题相关的 任何类型或复杂的对象。如： 染色体a ：1 2 3 2 4 5 3 2 4 30 4 5 5 62 3 2 9 33 4 5 4 5 染色体b ：a b d j e i f j d h d i e r j f d u ) f u 琶g t 染色体c ：( b a c k ) ，( b a c k ) ，( r i 曲t ) ，( f 0 刑a r d ) ，( 1 e f t ) ( 4 ) 树型编码( t r e ec o d e ) 在树型编码方式中，每一个染色体是某些对象的一棵树，在程序设计语言中， 这些对象即为函数或命令。如图3 1 所示： 羔2 生兰兰竺兰羔兰堑竺l 苎三兰二翌墨主垩堕簦竺塑丝堡壁鱼茎兰 染色体a 染色体b ( + ( ，5y ) ) ( d o u n t i i s t e pw a i i ) 图3 1 树形编码 n g 3 1t r e e d e 3 2 2 选择 从遗传算法的执行步骤中我们知道，算法从种群中选择父代染色体，然后进行 交叉操作1 18 。那么如何来选择这些染色体呢? 根据达尔文的进化理论，性能好的 生物体( 更适应的个体) 具有更高的生存与繁殖率；反之，生存与繁殖率则较低。 目前有许多选择最优染色体的方法，如赌轮( r o u l e t t ew h e e ls e l e c t i o n ) 法，b o l t z m a l l 法，锦标赛选择法( t o u m a m e n ts e l e c t i o n ) ，等级法( m ks e l e c t i o n ) ，乎稳状态法 ( s t e a d ys t a t es e l e c t i o n ) 及一些其他的方法等。 赌轮法( r o u l e t t ew h e e ls e l e c t i o n ) 根据每个染色体的适应度来选择进行交叉操作的父代双亲，也就是说，适应度 越大的染色体被选中的几率就越大。我们可以想象一个由种群中所有染色体构成 的赌轮，每个染色体根据它们的适应度而占有不同大小的扇面，如图3 2 所示。 图3 2 赌轮法 f g 3 2 u l e n ew h e e l 通过将骰子投掷到赌轮上来选择染色体。适应度大的染色体由于占有扇面的面 积大，因而被选中的概率就大。 等级法( r a n ks e l e c t i o n ) 当种群中染色体适应度差异很大时，赌轮法会遇到一些问题。例如，如果最好 的染色体的适应度占赌轮面积的9 0 ，那么其他染色体被选中的概率就会非常小。 九 墨!苎!塑主兰堡堡查等级法首先将种群中的染色体分级 墨三兰二翌墨壅竺竺查塑塑垫堡鱼苎兰 以每个染色体的适应度值的名次划分等 级。最坏的染色体为第一级，其次为第二级等等。最好染色体为第n级(n为种 群中染色体的数目) 。 在图3 3 中，可以看到将染色体用等级法来表示前后出现的变化。( a ) 划分等级前( 根据适应度)( a ) 划分等级后( 根据等级)图3 3等级划分前后的变化 f j 晷3 3v a r i a t 仰a n 盯r a n i d g 划分等级后，所有的染色体都有被选中的机会。但这神方法也会带来一些问题， 如较慢的 型嚣饕莹獭；l e 尊i 目d i ；j i 目g 女l ? l i ? i i 强耸簿终蘧毽霆骚麓涔繇拦转酣明刀粒婆穗鞲涯鹱鞴毪群霸斡，羹囊簿瞒潍 臻磊渤罐缅埘； 翌翟譬孳；酗戡黯醚* 辩妊醣旺o w h e e ls e l e c t i o n ) 根据每个染色体的适应度来选择进行交叉操作的父代双亲，也就是说，适应度 越大的染色体被选中的几率就越大。我们可以想象一个由种群中所有染色体构成 的赌轮，每个染色体根据它们的适应度而占有不同大小的扇面，如图3 2 所示。 图32 赌轮法 f g 3 2 u l e n ew h e e l 通过将骰子投掷到赌轮上来选择染色体。适应度大的染色体由于占有扇面的面 积大，因而被选中的概率就大。 等级法( r a n ks e l e c t i o n ) 当种群中染色体适应度差异很大时，赌轮法会遇到一些问题。例如，如果最好 的染 旧灞谎械母怕示突岱浅 x 东北大学硕士学位论文 第三章一种基于遗传算法的组播路由算法 3 2 3 交叉 交叉的方法有很多种，不同的编码方式也具有不同的交叉方法，本文给出了二 进制编码和树型编码的几种交叉方法。 ( 1 ) 二进制编码的交叉方法 单点交叉：这种交叉方式只有一个交叉点，子代染色体来源于两个父代染色体。 如：父代a父代b子代 1 l o o l l 0 1 1 + 7 7 d 7 7 i 7 = 1 l 0 0 17 7 7 两点交叉：这种交叉方式有两个交叉点，如 父代a父代b子代 1 1 1 0 0 1 0 1 1 1 + z d d 7 7 7 7 归= 1 1 d 仃7 n 一致交叉：子代染色体中的二进制位从父代的两个染色体中随机取得。如： 父代a父代b子代 1 1 0 0 1 0 1 1 + d ， d ，= ，1 0f 1 1 ( 2 ) 树型编码的交叉方法 传统的树型编码的交叉操作主要采用：在父代的两个染色体中各选择一个交叉 点，通过交换交叉点下的部分来产生子代个体。如图3 4 所示。 父代a父代b子代 3 2 4 变异 图3 4 树的交叉 f i g 3 4 m s s o v 盯o f t m e s 二进制编码的变异方法主要通过对选定的位进行取反来完成1 3 1 ，如： 1 ，0 0 1 0 0 1= 1 d o o l 0 0 l 东北大学硕士学位论文 第三章一种基于遗传算法的组播路由算法 树型编码的变异方法一般采用改变被选中节点的运算符或数字。如图3 5 所示。 变异前的染色体变异后的染色伴 图3 5 树的变异 f g 3 5m u t a t i o no ft r e e s 3 3 一种以性价比为优化目标的遗传算法 奉节对带有带宽和延时约束的组播路由最小费用问题加以改进，提出了一个 新的优化目标性价比。所谓性价比就是商品的性能与价格的比值，它能够反 应出某种商品的一个属性，即是否物有所值。算法共分两步。第一步是采用深度 优先搜索算法生成初始群体作为遗传操作的被选种群集合。群体中的每一个个体 都符合带宽和延时约束。第二步遗传操作中，父代染色体选择策略采用了精英理 论和赌轮法结合的方法；交叉策略采用了求同除异法；变异策略采用了删除结点 法。 3 3 1 初始群体的生成 设t 为组播树种群的集合，即t ( 、，e t ) g 寻找从s 到m 的组播树并满条件： d e l a y m 。；b a n d w i d t h 4d e l a y o 1 其中d e l a y m 。；为该树中从s 到m 的延时最大值，d e l a y o 为延时约束， b a i l d w i d t h = i1b a n d w i d t l l o b a i l d w i d t h m i l l ob a n d w i d t h 0 b a n d w i d t h m i n 其中b a n d w i d t l l 0 为带宽约束，b a n d w i d l h 。i 。为瓶颈带宽。 用下述算法得到初始种群： 第一步：设定种群规模； 第二步：生成一棵组播树； ( 3 6 ) ( 3 7 ) 第三步：判断该组播树是否满足公式( 3 6 ) ，是则该树属于初始种群并进入第 东北大学硕士学位论文 第三章一种基于遗传算法的组播路由算法 四步，否则将该树丢弃并返回第二步： 第四步：判断现有的组播树数量是否达到了第一步所设定的种群规模的数量， 是则输出初始种群，结束算法，否则i _ l i | 到第二步。 图3 6 显示了生成初始种群的基本流程： 否 开始 j 种群t 的规模为t ) 上 t = o i 一 扩 l _ t + l l l 用深度优先搜索算法生成一棵纽播树 上 u该组播树满足公式( 3 6 ) 吗 是上 该组播树属于t 上 t 中组播树的数量等于t 0 吗l 乒 输出t 上 结束 否 图3 6 牛成初始种群流稃盈 f i g 3 6 玎o wc h a r tf o rg e n e 瑚t j n gj n j t i a ip o p u l a t i o n 显然，t 中的每一棵组播树都符合q o s 的延时和带宽要求。这样选择出的种 群把不符合0 0 s 要求的组播树去除，从而减少了遗传算法搜索的空间，简化了算 法设计的难度，优化了算法的性能。 东北大学硕士学位论疋 第三章一种基于遗传算法的组播路由算法 3 3 2 遗传操作 遗传操作麸分为三步：选择、交叉和变异。 、选择 算法中，我们采取精英理论和赌轮法相结合的方法进行选择。其基本思想是： 首先把适应度最好的染色体保留，不参加选择，直接复制到f 一代：而后采用赔 轮法选中两个染色体生成新的个体，用新的个体取代父代染色体；最后把其它的 染色体复制到下一代。 本算法的适应度函数定义为： f ( t ) = b a n d w i d t b 。c o s t ( 1 ) ( 3 8 ) 其中b a n d w i d t h 。i 。为组播树各t 的链路中的最小带宽，c o s t ( d 为组播树t 的总 费用。 显然，这样定义适应度函数得出的最优解，其费用不一定是最小的。但是可 以得到较大的带宽；g 吏蒜骄；彰剥美能蓦蕊鹾；稚甍藉擐岔蒋翔瞎l 酸群萌瓣 型孽嘉耋希审簪罐璺合宰七禹毯管体的生成 设t 为组播树种群的集合，即t ( 、，e t ) g 寻找从s 到m 的组播树并满条件： d el a y m 。；b a n d w i d t h 4d e l a y o 1 其中d e l a y m 。；为该树中从s 到m 的延时最大值，d e l a y o 为延时约束， ba i l d w i d t h = i1b a n d w i d t l l o b a i l d w i d t h 。i l l ob a n d w i d t h 0 b a n d w i d t h m i n 其中b a n d w i d t l l 0 为带宽约束，b a n d w i d l h 。i 。为瓶颈带宽。 用下述算法得到初始种群： 第一 步：设定种群规模； 第二步：生成一棵组播树； ( 36 ) ( 37 ) 第三 x 查! ! 苎兰翌主堂竺笙圭 所示。 第三章一种基于遗传算法的组播路由算法 + 圈3 7 交叉 f 嘻3 - 7 c r o s v 盯o f t 抛e s 第二步连接子树的规则为：将这些零散子树看成一个染色体，在父代中随机 拿出一个染色体( 这个染色体的中间结点集合必须包含零散子树的中间结点集合， 如果不存在这样的染色体，则重新进行选择和交叉操作) 与这些零散子树进行并 操作，即子树中存在的链路保留，然后用随机取出的组播树中的其它链路将予树 进行连接，生成一棵完整的组播树，如图3 8 所示。 三、变异 交叉完成后，新的子女个体以概率p 进行变异。变异的方法为：以概率p 从 非最优染色体中去掉几个中间结点( 非根非叶结点) 及其与之相连的链路( 例如： 所有的染色体中间结点的和为1 0 0 0 ，p 如5 ，则需要去掉5 个中间结点) ，而后， 在父代中随机拿出一个染色体( 这个染色体的中间结点集合必须包含零散子树的 中间结点集合，如果不存在这样的染色体，则重新进行变异操作) 同子树进行并 操作( 其方法与交叉操作的子树连接相同) ，生成一棵完整的组播树。 东北大学硕士掌位论文 第三章一种基于遗传算法的组播路由算珐 u 3 3 3 算法步骤 第一步：设定种群规模、遗传代数、变异率的值 第二步：生成初始种群 第三步：计算每个染色体的适应度值 第四步：将适应度值最大的染色体直接复制到下一代 第五步；生成赌轮，选择父代进行交叉操作后复制到下一代 第六步：对非最优染色体进行变异操作后复制到下一代 第七步：将未参加交叉和变异操作的染色体复制到下代 第八步：判断遗传代数是否达到设定值，是则输出适应度值最大的解，否则 用得到的新一代染色体代替父代回到第三步。 图3 9 显示了本算法的基本操作过程。 东北大学硕士学位论五 第三章一种基于遗传算法的组播路由算法 开始 上 输入t 上 发定遗传代数a 0 上 a = o 1 计算每棵树的适应度函数 上 a _ a 0 7 广 扣 将适应度最大的树保留 上 用赌轮法选择父代 上 交叉、变异 上 子代和未参加交叉变异的父代组成t 上 1a 。a + 1 输出适应度晟大的树卜_ 上 结束 图3 9 算法流程 是 东北大学硕士学位论文 第三章一种基于遗传算法的纽播路由算法 3 3 4 算法的性能分析 为了验证算法的可行性，我们对该算法进行了三个内容的实验结果统计：收 敛性分析、性价比分析和算法的成功率。同时，我们还用实验的方法对种群规模、 遗传代数、交叉率以及变异搴的选取进行了总结。 实验中，带宽约束b 0 在 1 0 k ，1 0 0 k 】上均匀分布；延时约束d 0 在【5 0 m s ，3