（计算机软件与理论专业论文）基于蚂蚁网络算法的qos多播路由算法研究.pdf

南京邮电大学硕士研究生学位论文中文摘要 中文摘要 本文在分析了蚂蚁网络算法的优点和不足以后，借助已有的融合思想，将遗传算法嵌 入到蚂蚁算法之中，提出g a a ( ac o m b i n a t i o na l g o r i t h mo fg e n t i ca n da n t n e ta l g o r i t h m ) 算 法，用遗传算法的优点解决蚂蚁网络算法搜索效率低的缺点。g a a 算法在遗传算法和蚂 蚁网络算法的如何融合上进行了新的尝试，算法包含生成次优路径集合和得到最优路径两 个部分。其中生成次优路径集合是用遗传算法的思想完成，包括染色体编码、染色体适应 度评价、选择操作、交叉操作四个部分；得到最优路径是由蚂蚁网络算法完成的。 同时本文在g a a 算法的基础上构造了一个q o s 多播路由算法q m r a g a a 算 法。q m g h g a a 算法，包括三个子算法模块，分别为：“静态构造初始多播树 子算法、 “节点加入”子算法和“节点退出 子算法。q m r a g a a 算法真正做到了协议无关，同 时q m g h g a a 算法还具有额外负载低、自适应性强、不产生回路等优点。 仿真结果表明，g a a 算法在改进搜索效率上是有效性的；同时和传统的0 0 s 多播路由 算法相比q m r h g a a 算法在加入成功率、自适应性、都有了很大的提高，建树代价也控 制在很好的范围内。 关键词：多播路由算法，服务质量，蚂蚁网络算法，协议无关； 南京邮电大学硕士研究生学位论文 a b s t r a c t a f t e ra n a l y z i n gt h em e r i t sa n ds h o r t a g e so fa n t n e ta l g o r i t h m ，t h ep a p e rp u t st h e t r a d i t i o n a r ya l g o r i t h mi n t oa n t n e ta l g o r i t h m ，i nv i r t u eo ft h ef o r m e ri d e a lo fc o m b i n a t i o n , a n d p r e s e n t san e wr o u t i n ga l g o r i t h mg a a ( ac o m b i n a t i o na l g o r i t h mo fg e n e t i ca n da n t n e t a l g o r i t h m ) t h ea l g o r i t h mc o m b i n et r a d i t i o n a r ya l g o r i t h ma n da n t n e ta l g o r i t h m ，a n du s et h e v i r t u eo ft r a d i t i o n a r ya l g o r i t h mt oo v e r c o m et h es h o r t a g ei na n t n e ta l g o r i t h mf o ri t si n e f f i c i e n t s e a r c h t h ea l g o r i t h mc o n s i s t so ft w op a r t s ：t og e tas e to fs e c o n d - o p t i m a lp a t h sa n dt og e ta l l o p t i m a lp a t h t h ef o r m e rp a r ti sc o m p l e t e db yg e n e t i ca l g o r i t h mi n c l u d i n ge n c o d i n ga p p r o a c h ， f i t n e s se v a l u a t i o n ，s e l e c to p e r a t i o n ，a n dc r o s so p e r a t i o n , w h i l et h el a t t e rp a r ti sc o m p l e t e db y a n t h e ra l g o r i t h m t h e n ，an e wq o sm u l t i c a s tr o m i n ga l g o r i t h m ( q m r a - g a a ，q o sm u t i c a s tr o u t i n g a l g o r i t h mb a s e do nc o m b i n a t i o na l g o r i t h mo fg e n e t i ca n da n t n e 0b a s e do ng a a i sp r o p o s e d i nt h ep a p e r t h eq m r a g a ac o n s i s t so ft h r e es u b a l g o r i t h mp a r t ：s t a t i cs t r u c t u r i n go r i g i n a l m u l t i c a s tt r e e ，n o d ej o i n e ds u b - m o d u l e ，a n dn o d ed r o po u ts u b - m o d d e t h eq m r a - g a ai sa r e a l l yp r o t o c o l - i n d e p e n d e n ta l g o r i t h m a tt h es a n l et i m e ，t h e r ea r es o m ev i r t u e s ，s u c ha sl o w e r a d d i t i o n a ll o a d ，s t r o n ga d a p t a b i l i t y , w i t h o ml o o pa n ds oo n s i m u l a t i o nr e s u l t ss h o wt h a tt h en e wr o u t i n ga l g o r i t h mg a a o u t p e r f o r mc o n v e n t i o n a l r o u t i n ga l g o r i t h m si nt e r m so fc o n v e r g e n c e m e a n w h i l e ，c o m p a r ew i t hc o n v e n t i o n a lq o s m u l t i c a s tr o u t i n ga l g o r i t h m ，t h eq m r a g a ah a sp r e f e r a b l ej o i ns u c c e s s r a t i o ，s e l f - a d a p t a b i l i t y a n dh a sa c c e p t a b l ec o s to fs t r u c t u r em u l t i c a s tt r e e k e y w o r d s ：m u l t i c a s tr o u t i n ga l g o r i t g m ，q u a l i t y o fs e r v i c e ，a n t n e t a l g o r i t h m ， p r o t o c o l i n d e p e n d e n t i i 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名：! 址日期：立哟 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 研触橼坠盟导师始鱼啦魄迎进二l 南京邮电大学硕士研究生学位论文 第一章引言 1 1 课题背景 第一章引言 当代社会已经进入信息时代，网络技术在飞速发展。由于视频会议、推送技术、大规 模协作计算、为用户群进行软件升级、用于培训和企业报告的共享自板式的多媒体应用、 网络代理、镜像和高速缓存站点等等应用，都依赖于从一个主机向多个主机或者从多个主 机向多个主机发送同一信息的能力，所以一个特定组内部的信息交流变得越来越普遍。在 组的规模比较小的情况下，只需点对点交换信息即可；但是如果组的规模比较大，点对点 交换信息无论对网络还是对信息发送者，都是一种负担，代价昂贵。有时虽然可以用广播 的方式进行处理，但如果在一个上百万节点的网络上向数千台主机进行广播是很低效的甚 至是不大可能的。因为绝大部分机器对此信息不感兴趣，造成信息垃圾；更糟糕的是，部 分主机虽需要此信息但可能被误认为对此信息不感兴趣而收不到此项信息。因此，我们需 要一种办法让本身规模较大而相对互连网又较小的工作组能相互方便、快捷地传递信息。 为此，我们引进了i p 多播的概念。多播是一种一对多的传播方式，能很好的满足特定组 内信息交互的需要。而随着i n t e r n e t 商业化应用的飞速发展，对多播业务的服务质量 ( q o s ) 提出了更高的要求，为了满足业务需求，高效的q o s 多播路由算法就显得至关重 要。 q o s 路由难以解决的原因之一，就是i p 网络中的i n t e m e t 电话、远程实时会议和网络电 视等许多多媒体应用都会对网络时延、时延抖动、分组包丢失率、带宽、路由器缓冲空间 以及c p u 处理周期等诸多q o s 参数提出各种各样的要求。在一些情况下，多种约束会同时附 加在路由生成过程中，从而导致q o s 路由问题难解。 由于构造满足约束条件的q o s 多播路由树的问题是一个n p 完全问题 1 。而传统的方 法存在解决这类问题时存在着各种缺陷不能很好的满足各种业务的需要，所以一些新的方 法研究已经逐步开展。新兴起的启发式方法在解决这类问题上有很大的优势，所以很多学 者将遗传算法 2 、模拟退火算法 3 、人工免疫算法 4 等用在解决n p 完全问题上取得了 些可喜的成果。 第l 页 南京邮电大学硕士研究生学位论文第一章引言 蚂蚁算法 5 是近年来兴起的随机优化方法，是意大利学者m d o r i g o 等最早提出的， 它是一种源于大自然的新的仿生类算法。蚂蚁有能力在没有任何提示下找到从其巢穴到食 物源的最短路径，并且能随环境的变化而变化，适应性的搜索新的路径，产生新的选择。 其根本原因是蚂蚁在寻找食物源时，能在其走过的路上释放一种特殊的分泌物信息素 ( p h e r o m o n e ，随着时间的推移该物质会逐渐挥发) ，后来的蚂蚁选择该路径的概率与当时 这条路径上该物质的强度成正比。当一定路径上通过的蚂蚁越来越多时，其留下的信息素 也越来越多，后来蚂蚁选择该路径的概率也越高，从而更增加了该路径的信息素强度，而 强度大的信息素会吸引更多的蚂蚁，从而形成一种正反馈机制。通过这种正反馈机制，蚂 蚁最终可以发现最短路径。特别地，当蚂蚁巢穴与食物源之间出现障碍物时，蚂蚁不仅可 以绕过障碍物，而且通过蚁群信息素轨迹在不同路径上的变化，经过一段时间的正反馈， 最终收敛到最短路径上。蚂蚁算法是一种分布式、全局化的优化方法，不仅可以用于求解 单目标优化问题，而且可用于求解多目标优化问题，所以很适合用来解决q o s 多播路由问 题。 综上所述，蚂蚁算法是非常适合用来解决q o s 多播路由问题的。但是目前将蚂蚁算法 应用于q o s 多播路由问题的一些研究大多只偏重某一个方面，在性能方面还不能很好的满 足各种业务的需求。并且由于蚂蚁算法本身的局限性，容易造成路径搜索时间过长、搜索 停止等问题。 1 2 课题来源及研究目标 本课题来源于中兴科技基金项目基于o s p f 的路由协议快速收敛算法研究，该项 目从改进传统的最短路径算法和a v l 树增删算法两个方面研究，提高了单播路由协议的 收敛速度。本论文中的内容是对该项目内容的一个扩展，研究基于蚂蚁网络算法的q o s 多播路由算法，改进多播路由加入成功率、搜索时间、协议独立性等方面性能。 本文的主要目标是改进原有的蚂蚁网络算法，并在此基础上构造一个基本蚂蚁网络算 法的q o s 多播路由算法。改进后的q o s 多播路由算法满足以下几个要求： ( 1 ) 真正做到协议独立性，即不依赖于现有的单播协议。包括不需要单播协议生成 全局拓扑结构和不需要单播协议提供初始的可行路径解空间。 ( 2 ) 和经典的q o s 多播路由算法相比在连接成功率、自适应性和建树代价上都有所 第2 页 南京邮电大学硕士研究生学位论文 第一章引言 提高。 1 3 本文组织 全文共分六章，内容组织如下： 本文第一章介绍了本课题的背景、来源，以及本文主要目标，并给出了本文组织； 第二章分为两个部分，第一部分介绍了多播技术的相关知识，包括多播的概念、多播 路由算法的研究现状以及多播算法的性能指标：第二部分介绍了q o s 多播路由的相关知 识，包括q o s 的定义、q o s 多播路由的度量指标以及q o s 多播路由算法的研究现状。 第三章也分为两个部分，第一部分介绍了蚂蚁算法的概念，给出了基本蚂蚁算法的算 法描述和应用于数字网络的蚂蚁算法一a n t n e t 算法的具体描述以及蚂蚁算法在路由中 的研究现状：第二部分给出了本文所改进的蚂蚁算法川a a 算法，该算法结合了蚂蚁 算法和遗传算法的优点，首先用遗传算法对初始解空间处理，得到次优解空间，然后再用 蚂蚁网络算法在次优解空间的基础上得出最优解。 第四章是本文的核心部分，给出了q o s 多播路由问题的网络模型和问题描述，然后 将第三章的g a a 算法应用于q o s 多播路由问题，构成了一个完整的q o s 多播路由算法。 该算法实现了协议独立性，并且提高了多播路由的加入成功率。 第五章是算法的仿真与对比分析部分，该部分首先介绍了n s 2 仿真软件，构造了仿 真网络环境，然后在n s 2 仿真环境中实现了改进的a n t n e t 算法和第四章所提的算法，并 且和现有的其他几个算法做了比较。 第六章总结了本文所做的工作，并对该课题进一步研究的方向进行了展望。 第3 页 南京邮电大学硕士研究生学位论文第二章相关技术 第二章相关技术 如今，在许多城市的城域网中，从接入到核心的各个部分都实现了宽带化，这让人们 可以在宽阔的信息高速公路上更顺畅地进行通信，人们已经不再局限于传统点到点的交流 了，渴望多点之间的沟通。组播技术为多点通信业务的开展提供了良好的技术支持。而现 实中的多播业务必然有q o s ( q u a l i t yo fs e r v i c e ，服务质量) 要求。q o s 指的是报文传送 的吞吐量、时延、时延抖动、丢失率等性能。从i p 网诞生开始，q o s 问题就一直是i p 网 的软肋之一。本章将介绍多播技术的相关概念、多播算法的研究现状、q o s 的相关概念 以及q o s 多播路由算法的研究现状。 2 1 多播技术 2 1 1 多播技术相关概念 i p 多播( i pm u l t i c a s t ) 技术，又称为多址广播或者组播，是一种允许一台或多台主 机( 多播源) 发送单一数据包到多台主机( 一次的，同时的) 的t c p i p 网络技术。多播 作为一种点对多点的通信，是节省网络带宽的有效方式之一。多播技术需要从主机到路由 器和交换机都能够支持。 1 多播与单播、广播 6 】 单播( u n i c a s t i n g ) 是指只有一个目的地的数据报传递。采用多个点到点连接传送信 息时，服务器必须同时与多个客户端建立连接传送信息。有多少个客户，信息就在网络上 有多少个拷贝。这样的连接可以是物理线路或者是逻辑连接。该种方式有两个明显缺点。 首先对于服务器端压力较大：有多少个客户端需要该信息，就需要在服务器端建立多少个 连接。服务器端的处理能力限制了客户端的数量。其次对网络有较大的压力。例如一个高 清的节目源带宽一般约为2 0 m b i t s ，如果同时向1 0 0 个客户发送，相当于需要2 g b i t s 的 网络带宽。网络资源制约该方式下客户端的数量。多个点对点连接的优点在于每个独立连 接都是双向的，有利于互动。 多个点到点连接通信，如图2 1 所示。 第4 页 南京邮电大学硕士研究生学位论文 第二章相关技术 图2 - 1 多个点到点连接通信示意图 多播能使一个或多个多播源只把数据包发送给特定的多播组，而只有加入该多播组的 主机才能接收到数据包。服务器发送一份拷贝，网络负责在所有需要复制的分枝上复制。 采用多播方式传送信息的网络通常是智能较高的网络，网络根据客户所在的位置构造一棵 逻辑树，在构成的逻辑树上广播。这样网络上不需要该信息的客户端就不会收到服务器多 播发送的信息。 多播通信方式如图2 2 所示。 图2 - 2 多搔通信方式不恿图 广播( b r o a d c a s t i n g ) 是多点投递的最普遍的形式，它向每一个目的站投递一个分组 的拷贝。它可以通过多个单次分组的投递完成，也可以通过单独的连接传递分组的拷贝， 直到每个接收方均收到一个拷贝为止。在多数网络中，用户是通过把分组分送给一个特殊 保留的地址即广播地址( b r o a d c a s ta d d r e s s ) 来进行广播投递，它的主要缺点是会耗费大 量的主机资源和网络资源。 2 多播地址 7 】 主机的地址有两种：i p 地址和m a c 地址，分别对应于网络层和数据链路层，i p 地 址由4 个8 位字节组成。在i p v 4 中多播地址是一个d 类i p 地址，范围从2 2 4 0 0 0 到 2 3 9 2 5 5 2 5 5 2 5 5 。 m a c 地址有6 个8 位字节组成，i n t e m e t 权威机构把0 1 0 0 5 e o o 0 0 o o 到 0 1 o o 5 e 7 f f f - f f 范围的多播地址保留用于以太网和光纤分布式数据接口( f d d i ) m a c 地址。为了将一个i p 多播地址映射到一个m a c 层多播地址，i p 多播地址的2 3 个低字节 第5 页 南京邮电大学硕士研究生学位论文 第二苹相关技术 位被直接映射到m a c 层多播地址2 3 个低序位。根据d 类地址约定，i p 多播地址的前4 位是固定的，i p 多播地址中有5 位没有映射到m a c 层多播地址。因此，某个主机可以接 收不是它所属的组的m a c 层多播数据包。然而，一旦确定了目标i p 地址，这些数据包 就会被i p 丢弃，而令牌环网使用同样的方法进行m a c 层多播寻址。然而，许多令牌环 网络适配器并不支持它。因此在默认情况下，功能地址0 x 0 0 0 0 0 4 0 0 0 0 将用于通过令牌 环网发送的所有i p 多播流量。 3 多播路由树【8 】 一般要求多播服务的业务对带宽和实时性要求较高，涉及用户较多，占用的资源也多， 因此有必要优化多播路由。多播路由算法就是要寻求最优多播树，理想有效的路由算法将 设计一棵仅覆盖多播组成员的树，并体现如下特征：树随着组成员变化动态更新：最小化 结点需要保存的状态信息量：避免链路和结点的流量集中：根据费用函数优化路由。多播 路由树有两种类型：一种是有源树，另一种是共享树。 有源树是多播树最简单的一种形式。有源树的根是多播信息的来源，分支形成了通过 网络到达接收站点的分布树。有源树也有两种形式：一种是最短路径树( s p t ) ，另一种 是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 树问题是等价的。 有源树的潜在缺点是，它不易于升级到大型网络。假设一个网络有n 个组，每个组平 均有m 个成员，对于每个组，m 棵生成树都要存储，总共有m * n 棵树，如果多播组很大， 用于存储树的空间就很大了。 共享树也是核心树( c b t ) 。这里，每个组只计算一棵生成树，其树根( 核心) 靠近 多播组的中间部位，要发一个多播消息，主机先将它发往核心，再由核心沿着生成树发送 消息，虽然这棵树并不是对于任何源结点都是最优的，但它将每组m 棵树的存储开销降 第6 页 南京邮电大学硕士研究生学位论文第二章相关技术 低到了一棵树，节省了大量的空间。一些多播组中会存在数个有效发送源，而c b t 只构 建一棵共享树给组中所有成员共享，整个多播流量都在这棵共享树上面不论发送源有多少 或者在什么位置。共享树能极大地减少路由器的多播状态数据。 c b t 共享树由一个核心路由器构建，路由器发送加入请求给核心路由器，核心路由 器接收到请求后返回确认，这样就构成树的一个分支。加入请求在被确认之前无需被一直 传送到核心路由器，如果加入请求到达核心路由器之前到达树上的某个路由器，该路由器 就收下这个请求包而不继续向前发送并确认这个请求包，发送请求的路由器就连接到共享 树上。 4 多播组 9 】 使用同一个i p 多播地址接收多播数据包的所有主机构成了一个主机组，也称为多播 组。一个多播组的成员是随时变动的，一台主机可以随时加入或离开多播组，多播组成员 的数目和所在的地理位置也不受限制，一台主机也可以属于几个多播组。此外，不属于某 一个多播组的主机也可以向该多播组发送数据包。 2 1 2 多播算法研究现状 构造多播树是解决多播路由问题的常用方法，多播路由算法主要用来建立一棵性能好 多的多播树，并使它满足各种业务的服务质量( q o s ) 需求。下面根据不同类型的多播路 由树对多播路由算法的研究现状进行介绍。 1 。最短路径树( s p t ) 最短路径算法使多播树上从源节点到目的节点的每条路径上链路权值之和最小。 d i j k s t r a 算法是最著名的最短路径算法，其时间复杂分别为o ( n 2 ) 【l o 】。对于s p t 的构造 算法，人们在d i j k s t r a 算法基础上不断进行改进，到目前为止，构造s p t 树的最快算法的 时间复杂度为o ( e + n l o g n ) 1 1 、1 2 1 ( 其中n 表示图中结点数目，e 表示图中边的数据) 。 2 s t e i n e r 树 基于s t e i n e r 树的多播路由问题是致力于构建一棵总费用最小的多播树，构造s t e i n e r 树已经被证明是n p 问题，不可能获得多项式时间算法，在可接受的时间内只能计算得到 一棵近似的s t e i n e r 树。s t e i n e r 树算法 1 3 】可用来解决最优化问题，但对于有约束的应用 类算法很难满足其端到端的约束条件。针对该问题人们提出了许多求近似最优解的启发式 第7 页 南京邮电大学硕士研究生学位论文 第二章相关技术 算法。m p h 1 4 、a d h 1 4 、k m b 1 5 等算法提供了较好的近似最优解。m p h 算法在树 外所有目的节点中选择距离树最近的那个目的节点通过最短路与树相连，该算法的的复杂 度为d ( 19l 露2 ) ( n 为图中节点数) 。a d h 算法认为最优s t e i n e r 树是包括基本节点和s t e i n e r 节点的最小生成树，因此，一旦能够确定s t e i n e r 节点，那么就能求到最优解，该算法的 复杂度为o ( n 3 ) ( n 为图中节点数) 。k m p 算法用到了距离完全图和最小生成树算法，该 算法平均性能较好，复杂度为伙1 9 , 2 ) ( n 为图中节点数) 。 6 共享树 共享树算法首先由w a l l 在文献 1 6 1 q b 提出，以选定中心为根，其它组成员按照最短 路的原则与中心建立连接，构造成一棵由所有发送节点共享的树。共享树的主要问题就是 选择中心点，典型的中心点选择方案有最佳中心点方案、随机选择方案、最大中心树、最 小最短路径方案、平均距离最小方案、最小直径方案、全局中心方案等 1 7 、1 8 1 。此外， 采用多中心c b t 也可有效抑制中心失败的影响，但由于构造和管理多中心c b t 的复杂性， 问题还是没有成熟的结论。 2 1 3 多播路由算法的性能指标 多播路由算法的好坏，也就是多播树的好坏。影响多播路由算法的因素有很多，但随 着应用的不同，其要求也各有不同，对于大多数应用来说，有些特性如时延、树费用等比 算法的其它特性更重要。而对于某些多媒体应用，丢包率和时延抖动也非常重要。下面是 多播树的各种特性参数 1 9 1 1 ) 费用：一棵多播树的费用等于多播树上每一条链路的费用之和。好的多播路由算 法就是使得费用尽可能的低。 2 ) 时延：这里时延是指源节点到目的节点的路径上各条链路和结点的时延之和。多 播树应尽可能的使得任何源至目的节点之间的端到端时延最小。 3 ) 可扩展性：多播树的可扩展性表现在两个方面：一是在多播成员很多的情况下构 造多播树的时间和占用的资源应尽可能的少，二是网络中的交换机或路由器应能够同时支 持大量的多播组。 4 ) 复杂度：复杂度是指计算一棵多播树所需要的时间与网络规模之间的关系。好的 第8 页 南京邮电大学硕士研究生学位论文第二章相关技术 算法应该是低复杂度的算法。 5 ) 动态特性：多播组可以划分为静态和动态二类。静态多播组的成员自始至终不改 变，而对以动态多播组来说，新成员可以随时加入，老成员可以随时退出。好的多播路由 算法应该允许多播成员无缝加入或退出，而且多播树的性能不能由于多播动态特性而变得 很差。 6 ) 强壮性：多播树能够在多个网络结点或多条链路失效时依然正常工作，并且性能 不会受到很大的影响。 7 ) 公平性：多播路由算法的公平性体现在两个方面。一是对于多播组的每个成员都 提供最低标准的服务，而不是以惩罚某些成员来换取另一些成员的q o s ，第二应该尽可 能使得参与的结点平分多播任务。 2 2q o s 多播路由的相关概念 当前i n t e m e t 只提供尽力发送服务，网络层不区分用户业务的种类，而将网络资源公 平地提供给各类业务，在分组丢失、时延等方面公平地对待各类业务。这种尽力发送的机 制使网络层无法保证传输的参数，然而丢包率、带宽、时延、时延抖动等对于应用业务往 往是至关重要的。例如，文件传输业务要求丢包率尽可能低，而传输时延不是关键因素； 实时多媒体业务则更看重时延和时延抖动。这就要求网络能够区别对待各种业务，并对它 们提供不同的服务质量。由于i p 是无连接的协议，不要求像a t m 网络那样在数据传输前 从源到目标节点建立连接。这种尽力发送的体系结构是无连接、与状态无关的，它既不能 支持资源预留，也不能预测传输参数，甚至还可能产生多媒体实时业务不希望的乱序等。 由此，面向服务质量的网络体系结构应运而生。 2 2 1q o s 定义 q o s 有多种等价和互补的定义形式。r f c 2 3 8 6 ( c r a w l e y ，1 9 9 8 ) 中q o s 的描述为：网 络在传输数据流时要求满足的一系列服务请求，也是指数据流通过网络时的性能要求，具 体可以量化为是带宽、延迟、延迟抖动、吞吐量和丢包率等。此处的服务是指数据包经过 网络节点时所接收的传输服务，强调端间或者网络边界的整体性。这种服务请求也可以被 描述为用户与网络之间的关于信息传输的质量的约定，即当用户按照约定的信息流特征产 第9 贾 南京邮电大学硕士研究生学位论文第二章相关技术 生数据时，服务者承担的q o s 。这里说明的是：q o s 包括用户的要求和网络服务者的行 为两个方面。用户与服务者之间的约定一般可以从下面几个方面进行描述： 1 ) 业务可用性：用户到i p 业务之间连接的可靠性。 2 ) 网络带宽：通常指网络信道的传输能力，在不同的时间段，这种能力可能是变化 的。 3 ) 延迟：也称为时延，指两个参照点之间发送和接收数据包的时间间隔。 4 ) 可变延迟：也称为抖动，指在同一发送节点沿不同路径发送数据到不同目的节点 的时间差异。 5 ) 吞吐量：网络中发送数据包的速率，可用平均速率或峰值速率表示。 6 ) 丢包率：在网络中传输数据包时丢弃数据包的最高比率。数据包丢失一般是由网 络拥塞引起的。 7 ) 路径长度：一般指数据从源传输到目的地所经历的路由器的个数。 8 ) 其他：如考虑网络节点的多播能力的度约束等。 2 2 2q o s 多播路由度量 度量在q o s 多播路由问题中起着重要的作用，它不仅定义网络可以支持的服务质量 类型，也定义应用的服务质量请求范围，并且还可以反映网络的基本特征。通信信息的 q o s 请求是通过单度量或组合度量来量化和提出的，如果信息的q o s 请求不能映射为单 度量或组合度量，那么网络就不能支持该信息的q o s 请求。假设路径p = ( a ，b ，c ，j ，k ) ， 用m ( a ，b ) 表示对应链路( a ，b ) 的度量，q o s 路由度量可分为如下三类【2 0 】： 1 ) 加性度量：m ( p ) = m 札b ) + m ( b ，c ) + + m ( j ，k ) 路径的加性度量状态是由该路径上所有链路的特性共同决定的。加性度量包括时延、 时延抖动、代价、端到端路由跳数等。 2 ) 乘性度量：m ( p ) = m ( a ，b ) + m ( b ，c ) 木 m ( j ，k ) 路径上的乘性度量为该路径上所有链路对应度量的乘积。乘性度量包括连接可靠性 ( 即成功传输率：1 丢包率) 等。 3 ) 凹性度量：m ( p ) = m i n ( m ( a , b ) ，m ( b ，c ) ，m ( j ，k ) ) 路径上的凹性度量状态是由传输链路中的瓶颈链路的状态所决定的。也就是说，一条 第l o 页 南京邮电大学硕士研究生学位论文第二章相关技术 路径上的某个凹性度量取决于该路径上所有链路对应于该度量的值中的最小值。凹性度量 包括最常用的剩余带宽、剩余缓存空间和链路速率等。此类度量只与路径上的某个瓶颈链 路的q o s 度量有关。 在具体的设计多播算法的过程中，要根据网络的实际情况和应用的需求来解决问题， 对算法考虑所有度量的做法是不切实际的。例如，对于实时传输的多播应用，时延是必须 保证的条件，代价则是评价网络使用效率的标准，都要纳入考虑的范围。而时延抖动、丢 包率等可以不加考虑。 2 2 3q o s 多播路由算法现状 基于q o s 的多播路由算法方面，d i j k s t r a 提出了一种基于最短路径树 2 1 1 的方法，其基 本思想是从源节点到各目的节点分别计算各自最短路径，并将其组成以源节点为根的树， 该方法并不能保证所生成的树的总成本最低。还有一些通过在源节点的计算来寻找一个受 限制的s t e i n e r 树的b s m a 2 2 、k m p 2 3 和c d k s 2 4 的算法，它们需要网络中的每个节点 都保存全局的网络状态信息以及q o s 参数信息，当网络和多播组规模很大时算法的代价很 大，并且不适合于组成员的动态加入和离开，因此它们不适合在i n t e m e t 上使用。 已经证明，多q o s 约束的多播路由问题是一个n p 完全问题，所以很多启发式算法被应 用到求解q o s 多播路由问题上。文献 2 5 】中提出了一种启发式搜索算法s a m r a ，首先采用 d d v c a 2 6 算法生成初始树，然后针对每一个目的节点采用k t h s p a ( k t hs h o r t e s tp a t h a l g o r i t h m ) 【2 7 算法计算k 个最低时延路径，并且构造一个备份路径集合来生成邻居节点， 最后用模拟退火算法进行解迭代，通过在备份路径集合中添加删除路径来构造新解，算法 复杂度为o ( k m n 3 ) ( 其中m 表示目的节点个数，k 为最短路径集合的大小，以为系统节点 个数) 。s a m r a 具有了很好的性能，不足是应用面不够广泛，只是针对时延以及时延变化 受限s t e i n e r ( d e l a ya n dd e l a yv a r i a t i o nb o u n d e ds t e i n e rt r e e ) 树的构造提出。 遗传算法自从被提出以来，学术界给予了高度的关注，遗传算法可以求解许多领域的 各种组合搜索和优化问题【2 8 】。遗传算法能够较快的找出近似全局最优解 2 9 】，在多播路由 中应用比较广泛 3 0 3 2 1 ，其 g a d v m 3 1 是在文献 2 2 - 2 4 的基础上进一步研究，它是应用 遗传算法来优化最小代价树，在g a d v m 中考虑了两个q o s 因素：每条边从源节点到目的 节点的时延以及路径间的时延抖动，根据这两个约束条件来构造最小代价树。从文献 3 1 】 第1 1 页 南京邮电大学硕士研究生学位论文第二章相关技术 中的试验仿真来看，g a d v m i 七b s m a 、k m p 等经典算法在耗费和时延及时延抖动上有了 改进。对比于g a d v m ，文献【3 2 】中虽然同样应用了遗传算法，但并不是采用构建最短路径 树的模型，而是最大化从源节点到目的节点的路径长度从而降低路由规模的思想，此方法 具有较好性能的同时实用性不够广泛。但是由于遗传算法的局限性，所有基于单纯遗传算 法的q o s 多播路由算法都存在编码空间太大、自适应性差【3 3 】等缺点。 由于蚂蚁算法具有很强并行性、全局寻优能力、自适应性以及易于和其它算法融合的 特性，蚂蚁算法在路由中的研究也非常广泛。有关蚂蚁算法在路由中的研究现状，将在3 2 节给出。 2 3 本章小结 q o s 多播路由问题是一个n p 完全问题，传统的多播路由算法在解决这一问题上存在 着很大的不足，所以很多启发式算法被应用于q o s 多播路由问题，取得了不错的效果。 遗传算法由于其自身的优点，在多播路由中的应用研究的比较广泛，但是由于遗传算法又 具有自适应性差等特点，使得基于遗传算法的q o s 多播路由算法在自适应性等性能上存 在着先天的不足。而蚂蚁算法具有很强的并行性、全局寻优能力和自适应性，所以将蚂蚁 算法应用于路由问题正成为当前研究的热点之一。下章将介绍蚂蚁算法和蚂蚁算法在路 由中的研究现状，并提出一种融合的蚂蚁算法g a a ( ac o m b i n a t i o na l g o r i t h mo f g e n t i c a n da n t n e t a l g o r i t h m ) 算法。 第1 2 页 南京邮电大学硕士研究生学位论文第三章改进的蚂蚁算法 第三章改进的蚂蚁算法 上一章介绍了q o s 多播路由的研究现状，从上一章的分析可以看出无论是传统的路 由算法还是新兴的启发式路由算法( 模拟退火、遗传算法等) 都存在着各种不足。本章将 介绍蚂蚁算法和蚂蚁算法在路由中的研究现状，并提出一种融合的蚂蚁算法g a a ( a c o m b i n a t i o na l g o r i t h mo fg e n t i ca n da n t n e ta l g o r i t h m ) 算法。 3 1 蚂蚁算法 3 1 1 蚂蚁算法简介 2 0 世纪9 0 年代，意大利学者m d o r i g o ，v m a n i e z z o 等人通过模拟自然界蚂蚁寻径 的行为，提出了一种全新的启发式算法一蚂蚁算法( a n t a l g o r i t h m ，a a ) 3 4 】，具有较强 的鲁棒性、寻径过程的并行性以及易于与其他启发算法结合的优越性。 蚂蚁算法是在研究自然界中蚁群行为的基础上提出的一种启发式方法。实验观察表 明，在蚂蚁寻找食物时，它们总能找到一条从食物到蚁巢的最优路径。原因是，蚂蚁在运 动过程中会在路径上释放出一种特殊的信息素，该物质随着时间的推移会逐渐挥发消失。 后面的蚂蚁可根据前面走过的蚂蚁遗留下来的信息素值来选择下一步要走的路径。一条路 径上的信息素值越高，蚂蚁选择这条路径的概率就越大，构成一个学习信息的正反馈过程， 最优路径上的信息素浓度越来越大，虽然单个蚂蚁的选路能力有限，但是通过个体之间的 信息交流( 正反馈) ，整个蚁群之间不断交换路径信息，最终找出最优路径。 在蚂蚁算法中，每个蚂蚁根据状态转移规则来选择下一跳节点，使用全局更新和局部 更新两种规则可以取得更快的全局优化结果。 3 1 2 蚂蚁算法描述 蚂蚁算法从诞生发展至今，经过了一系列的改进和演化，根据应用范围的不同有了 多个版本，下面主要介绍最初的蚂蚁算法a s ( a n ts y s t e m ) 算法和应用于数字网络的蚂 第1 3 页 南京邮电大学硕士研究生学位论文 第三章改迸的蚂蚁算法 蚁算法- a n t n e t 算法。 1 a s ( a n ts y s t e m ) 算法 a s ( a n ts y s t e m ) 算法【3 5 】是最早最原始的蚁群算法可描述为：设有m 只蚂蚁随机放在 具有1 1 个节点的全连通图上，g i , j ( f ) 表示t 时刻在i j 连线上的信息素量，r h j ( f ) 是与问题 相关的启发式信息，此外现，= l a , 。初始时刻，各条路径上信息量相等，设f “( o ) = c ( c 为常数) 。蚂蚁k ( k = l ，2 ，m ) 在运动过程中根据各条路径上的信息量和问题的启发式 信息决定转移方向，( f ) 表示在t 时刻蚂蚁k 由位置i 转移到位置j 的概率， 屯o ) = 拦裟( o y 器，触咴 巧芦【仍o ) r j 段 o ， 纪 3 1 式中，缸6 肌记录着蚂蚁已经遍历的节点，口，为调节信息素强度f 和启发式信息，7 相 对重要性的参数。 经过n 个时刻，蚂蚁完成一次周游，各路径上信息量要根据下式作调整： _ ，( ，+ 疗) = ( 1 一力乃，( ，) + q ，( ，+ 刀) ( 3 2 ) a z , ，+ 疗) = f 0 + 聆) k = l ( 3 3 ) 式中，pc ( o ，1 ) 表示信息素的挥发系数，f 乞表示第k 只蚂蚁在本次循环中留下的路径 o ，) 上的信息量；a r 。，j 表示本次循环中所有蚂蚁留在路径( f ，) 上的信息量。f 己可按照 下式计算， r ：，o + 刀) ： 罢 第职蚂蚁在本次循环中经过路径( l 力 ( 3 4 ) 10否则 式中，q 均为常数，t 为蚂蚁k 所遍历的路径的长度。 上述算法称为a n t c y c l e 算法，根据信息素更新策略的不同，d o r i g o 还给出了另外两 第1 4 页 南京邮电大学硕士研究生学位论文第三章改进的蚂蚁算法 种a s 算法： ( 1 ) a n t d e n s i t y 算法 f 乞( ， f + 1 ) = l g 第职蚂蚁在名孑经过路缀d ( 3 - 5 ) ( 2 ) a n t q u a n t i t y 算法 峨+ 1 ) ： 杀锹只蚂蚁f “步经过路缀“) ( 3 6 ) 【0 否则 式中，q l 、q 2 均为常数。 d o r i g o 等认为在a n t d e n s i t y 和a n t - q u n t i t y 算法中，蚂蚁在构建解的同时释放信息素； 而在a n t c y c l e 算法中，蚂蚁在完整地构造问题的解之后再释放信息素，利用的是整体信 息，因此效果要好于前两种算法。 4 a n t n e t 算法 蚂蚁算法在网络路由方面的应用也非常广泛，1 9 9 7 年d i c a r o 等人针对数字网络提出 了a n t n e t 算法【3 6 】，该算法是在a c s 算法基础上提出的。仿真结果表明在负载接近饱和 网络动态变化的情况下，a n t n e t 算法各方面性能都优于o s p f 等传统路由算法。a n t n e t 算法可描述为：在一个数字网络中有n 个节点，设s 为源节点，d 为目标节点，源节点随 机的释放人工蚂蚁，人工蚂蚁的目的地址为d 。 在算法中定义了两种人工蚂蚁：向前蚂蚁，记为：e 一 d ，表示从源节点s 到目的 节点d 的人工蚂蚁。向后蚂蚁，记为：b d 丑一d 是c 一 d 到达目的节点d 后产生的返 回蚂蚁，e 一按e 一，d 的原路返回，用于更新所经节点的路由表。 网络中的每个节点s 按照一定的速率发送人工蚂蚁只一 d ，只一，d 作为一般的数据包处 理，与一般数据包一起按先进先出原则