（计算机应用技术专业论文）基于蚂蚁优化的QoS约束分布式多播路由算法研究与实现.pdf

摘要 随着因特网通信业务量的不断膨胀，如何有效地在q o s 约束下寻找 具有最小网络费用的多播路由树成为研究的热点。论文主要研究基于蚂 蚁优化算法的具有q o s 约束的分布式多播路由算法问题，解决了已有算 法在多播规模增大时路由选择时间长，全局优化性能差，容易产生回路 的问题。 论文在研究分布式网络、o o s 约束，多播路由的基础上，建立了分布 式q o s 多播路由的数学模型，包括网络模型、q o s 度量及特征和多播路由 模型。发现已有算法当多播规模增大时，蚂蚁死亡率较高，容易产生回 路。提出了一种带回路检测的分布式度约束算法，首先建立初始多播路 由树，多播路由树的寻找和建立可以在同时完成；提出一种改进的蚂蚁 优化算法，定义两种类型的蚂蚁代理：向前蚂蚁和向后蚂蚁，两种蚂蚁 互相协作，共同发现满足带宽和延迟约束的最小代价路径，蚂蚁一边前 进一边对已经建立的初始多播路由树进行优化，充分利用了分布节点的 局部信息，能够降低蚂蚁死亡率，改善解的质量，降低了产生回路的可 能。 论文改进了算法收敛规则，通过信息素强度变参数控制，残留信息素 数量限幅控制和挥发系数动态自适应调节，增加了算法收敛速度，提高 了算法的全局收敛性。通过与b s m a 和k m b 算法进行网络规模影响，多 播规模与时延限制影响等仿真实验结果比较分析，表明本算法适应大规 模的网络和多播要求，路由选择时间较短，全局优化能力较好和收敛时 间适当。 关键词蚂蚁优化算法；多播路由；服务质量( q o s ) a bs t r a c t w i t ht h ev o l u m eo fi n t e m e tc o m m u n i c a t i o n sb u s i n e s s c o n t i n u e st o e x p a n d ，h o wt of i n dam i n i m u mc o s to ft h en e t w o r k sm u l t i c a s tr o u t i n gt r e e s i nq o sc o n s t r a i n t sb e c o m eah o tr e s e a r c h r e s e a r c hm a i n p a p e r st h e d i s t r i b u t e d q o sm u l t i c a s tr o u t i n g b a s e do na n t c o l o n yo p t i m i z a t i o n a l g o r i t h m ，w h i c hh a sb e e ns o l v e dt h ep r o b l e mo fr o u t i n gf o ral o n gt i m ea n d o p t i m i z et h eo v e r a l lp e r f o r m a n c eo fp o o ra n di ti se a s yl o o pi nt h ee x i s t i n g a l g o r i t h mw h e nt h es i z eo fm u l t i c a s ti n c r e a s e t h i s p a p e rp r o p o s e s an e wd i s t r ib u t e dq o sm u l t i c a s t r o u t i n g m a t h e m a t i c a lm o d e lb a s e do nr e s e a r c hp a p e r sd i s t r i b u t e dn e t w o r k s ，q o s c o n s t r a i n t s ，m u l t i c a s tr o u t i n g ，i n c l u d i n g t h en e t w o r km o d e l ，q o sa n d m e a s u r e m e n tf e a t u r e sa n dm u l t i c a s t r o u t i n gm o d e l w h e nt h e s i z eo f m u l t i c a s ti n c r e a s e ，w ef o u n dt h ep r o b l e mo ft h eh i g h e rm o r t a l i t ya n ta n di ti s e a s yl o o pi nt h ee x i s t i n ga l g o r i t h m t h i sp a p e rp r o p o s e sad i s t r i b u t e dl o o p d e t e c t i o nw i t h d e g r e e c o n s t r a i n t s a l g o r i t h m ，f i r s t o f a l l ，t h e i n i t i a l e s t a b li s h m e n to fm u l t i c a s tr o u t i n gt r e e ，m u l t i c a s tr o u t i n gt r e et of i n da n dc a n b es e tu pa tt h es a m et i m et oc o m p l e t e t h i sp a p e rp r o p o s e sa ni m p r o v e da n t a l g o r i t h m ，w h i c hd e f i n et w ot y p e so fa n t sa g e n t s ：f o r w a r da n ta n db a c k w a r d a n tw h i c hf i n dc o m m o nb a n d w i d t ha n d d e l a y c o n s t r a i n t st om e e tt h e m i n i m u mc o s to ft h ep a t h a n t sh a v eb e e no p t i m i z e dt h ei n i t i a lm u l t i c a s t r o u t i n gt r e eo nt h es i d eo ft h ef o r w a r ds i d et om a k ef u l lu s eo ft h ed is t r i b u t i o n o ft h el o c a ln o d e ，t oi m p r o v et h eq u a l i t yo fs o l u t i o n s ，r e d u c i n gt h ec i r c u i t t h i s p a p e ri m p r o v e s t h e c o n v e r g e n c e r u l e s t h r o u g hi n f o r m a t i o n i n t e n s i t yc h a n g ec o n t r o l ，r e s i d u a lp h e r o m o n el i m i t i n gc o n t r o la n dc o e f f i c i e n t o fv o l a t i l ed y n a m i ca d a p t i v et oi n c r e a s et h es p e e do fa l g o r i t h mc o n v e r g e n c e a n di m p r o v et h eg l o b a lc o n v e r g e n c e t h ei m p a c to nt h es i z eo ft h en e t w o r k a n dm u l t i c a s t i n ga n dd e l a yr e s t r i c t i o n so nt h es i z eo ft h ei m p a c tt e s tr e s u l t so f s h o wt h a tt h i sa l g o r i t h mh a sa d a p t a b i l i t yo ft h el a r g e - s c a l en e t w o r k sa n d m u l t i c a s tr e q u e s ta n dr e l a t i v e l ys h o r tp e r i o do ft i m er o u t i n g ，e x c e l l e n tg l o b a l o p t i m i z a t i o na n dc o n v e r g e n c eo ft h ea p p r o p r i a t et i m e ，c o m p a r e dw i t ht h e bs m aa n dk m ba l g o r i t h m k e yw o r d sa n tc o l o n yo p t i m i z a t i o na l g o r i t h m ，m u l t i c a s tr o u t i n g ， q u a l i t yo fs e r v i c e ( q o s ) 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获 得中南大学或其他单位的学位或证书而使用过的材料。与我共同工作的 同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：日期：型年j l 月卫日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校有权 保留学位论文并根据国家或湖南省有关部门规定送交学位论文，允许学 位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可以 采用复印、缩印或其它手段保存学位论文。同时授权中国科学技术信息 研究所将本学位论文收录到中国学位论文全文数据库，并通过网络向 社会公众提供信息服务。 作者签名：牡 导师签名日期：之堕年型月尘日 硕十学位论文第一章绪论 1 1 研究背景 第一章绪论 随着网络多媒体技术的飞速发展，因特网上多媒体应用层出不穷，如i p 电话、 视频会议、视频点播、远程教育等多媒体实时业务、电子商务在i n t e m e t 上传送等。 i n t e m e t 已逐步从单一的数据传送网向数据、语音、图像等多媒体信息的综合传输网 演化【lj 。这些不同的应用对服务质量的需求在迅速增长。目前这种单一的、点对点的、 “尽力而为”的网络结构已经越来越不能适应当前网络应用的发展需要，研究和发展 适合于传输实时多媒体数据的新代网络技术成为必然趋势。 为满足上述需要，服务质量( q u a l i t yo f s e r v i c e ，q o s ) 和多播的概念应运而生， q o s 用于定性或定量地描述服务的提供者与接收者之间所协商的服务性能( 如最小带 宽、端到端的延迟、延迟抖动以及包丢失率等) ，即保证分组在传输过程中能够获得 可预测、可分类及可管理的服务质量级别【2 】。多播则是一源节点将同一数据信息发送 到多个目的节点的通信技术，当前要求网络具有多播( m u l t i c a s t ) 能力的音频视频会 议、交互式仿真、多人游戏、分布式数据库等应用的规模越来越大，涉及到的节点数 越来越多，交互数据量也越来越大，若对每个信宿单独发送数据包，则将大大浪费网 络资源，增加节点的处理负担，严重时会加剧网络的拥塞。因此，实现多播通信的关 键是如何确定多播路由，即如何找到满足q o s 约束条件的多播树p j 。 由于q o s 所涉及的内容很多，包括流量整形、包调度算法、路由算法、资源预 留以及接入控制等，因而在q o s 的早期研究中，主要的研究集中在网络节点的调度 策略和接入控制策略上，而路由算法却一直被忽视。近年来的研究表明，路由算法对 实现网络的服务质量保证起到了非常关键的作用，同时也是平衡网络负载、控制网络 拥塞以及充分利用网络资源的重要保证【4 】。简单地讲，q o s 路由就是要寻找满足特定 q o s 要求的一条路由路径( q o s 单播路由) 或一棵多播树( q o s 多播路由) ，其目的 是在路由建立的过程中为网络应用提供q o s 服务，使其能满足带宽、时延、时延抖 动和费用的限制，并可以优化网络资源、提高网络资源的利用率。 对于具有单一约束( 如带宽约束) 的q o s 路由( 包括单播和多播) 问题，通常 可以通过对传统的路由算法或协议( 如d i j k s t r a 算法、p i m 协议等【5 j ) 进行修改来求 解。在以往的研究中，多播路由问题常归结为最小费用的多播树问题，属于树优化问 题。后来人们发现，要实现实时的数据图像传播，必须考虑带宽、时延、丢包率等 q o s 保证，这样存在多个约束的q o s 多播路由问题就复杂得多，特别是存在多个可 加性q o s 度量( 包括网络代价、链路的延迟、延迟抖动等，但需要特别说明的是： 硕士学位论文 第一章绪论 网络代价虽然也是q o s 度量的一种，但通常作为路由计算所优化的目标，不作为q o s 约束条件。) 的情况。已经证明，存在两个或两个以上不相关、可加性度量的q o s 路 由问题属于n p 完全问题【6 j 。n p 完全问题是当今数学界尚未很好解决的问题，由此 可见研究q o s 路由技术的难度，如何解决此类n p 完全问题，找到满足q o s 约束的 最优( 或次优) 路径或多播树是当前q o s 路由研究的重要目标。 另一方面，网络路由包括两个基本任务：收集当前的网络状态信息和利用所收集 的状态信息计算满足某些条件的路由路径或多播树。由此可见，网络节点在路由计算 的过程中必然要用到相关的网络状态信息，q o s 路由与多播路由也不例外。这些状态 信息主要包括：网络拓扑的连接性、链路的可用带宽、传输延迟以及节点中的排队延 迟、剩余缓冲区大小等。在这些状态信息中，有些状态信息的变化频率并不高，如拓 扑的连接性、链路的传输延迟，但另有一些状态信息却频繁地、快速地波动，如链路 的剩余带宽、节点中的排队延迟和剩余缓冲区大小，在大型网络中，这种动态变化更 是如此。在动态网络中，网络节点不可能拥有整个网络的瞬时和详细的状态信息，即 节点所知道的网络状态信息往往是过时的、非精确的，路由算法只能依靠部分或近似 的网络状态信息进行路由计算。 因此，现有的q o s 多播路由算法往往是通过启发式算法来进行，在目前已有的 启发式算法中，由意大利学者m d o r i g o 提出的蚂蚁优化算法以其健壮性、并行性、 灵活性以及搜寻过程不需要人工干预和求解精度高的特点得到了广泛应用。该算法不 依赖于具体问题的数学描述，具有全局优化能力和本质上的并行性，同时比遗传算法、 模拟退火算法等早期进化算法具备更强的鲁棒性、求解时间短、易于计算机实现等优 点，已被初步应用于高度复杂的组合优化问题、通信网络的路由选择问题。同时，现 有的启发式算法往往都是集中式的，需要中心节点来负责计算路由树并且这个中心 节点必须具有全网的信息，这在大型网络中是不现实的，根据局部网络信息求解的分 布式算法显得更加重要。因此，本文提出了一种改进的基于蚂蚁优化的分布式q o s 多播路由算法，并结合多播路由问题的特点对算法进行了深入研究与分析，通过仿真 实验讨论了本文方法的性能，与传统的蚂蚁算法对比，不仅可以实现全局优化，有效 地提高网络数据包的传输质量，而且可以大大节约路由选择时间，为解决o o s 分布 式多播路由问题提供了一个新的思维方法。 蚂蚁算法是一种模拟蚂蚁觅食行为的仿生优化算法，具有并行搜索、群体寻优的 特点，对于多播问题具有较强的可扩展性。对于q o s 多播路由，文献【3 】提出一种混 合蚂蚁算法，将遗传算法与蚂蚁算法相合并，但是由于未采取有效措施抑制遗传算法 的早熟现象，算法易陷入局部极值。文献【4 】提出一种启发式蚂蚁算法，算法要求每 只蚂蚁在一次循环中遍历所有目标点，由于文中采取对蚂蚁刚访问链路信息素衰减的 局部更新策略，使算法有深度搜索的趋势，会造成大量的无效搜索，随着网络的增大 将极大地降低算法效率。为了能够快速、优质地实现q o s 多播路由，本文在对q o s 2 硕十学位论文 第一章绪论 多播路由模型进行分析的基础之上，根据多播路由中约束条件下对各目标点“单播 路由相对独立的特性，首先将多播路由分解为对各目标点的单播路由，然后在带费用 启发信息控制策略下，由“单播 路径再合并生成多播树，避免了算法早熟，提高了 算法的全局搜索能力，同时在求解蚂蚁算法中引入了局部信息素惩罚更新机制和基于 多播树奖惩的全局信息素更新机制，能有效缩小算法的搜索范围，提高算法收敛速度。 1 2 研究现状 多播路由的实质是多播树的构造，根据算法是否支持q o s 特性，可分为q o s 敏感 ( q o s a w a r e ) 的和非q o s 敏感( q o s o b l i v i o u s ) 1 8 j 的两类。q o s 多播试图建立一棵从源端 到成员节点的满足一定q o s 请求的优化多播树，非q o s 多播则采用传统的i p 尽力而 为( b e s t e f f o r t ) 机制传输多播数据。而现有的q o s 多播路由算法按路由的计算方式又大 致可以分为两类：源路由算法和分布式路由算法。源路由算法是指路由计算在源节点 上进行，并且需要全局状态信息的路由算法；分布式路由算法是指路由计算分散在中 间节点上，一般只需要局部状态信息的路由算法。这些算法从本质上讲都是探讨如何 化解有关q o s 多播路由的n p 完全问题。 1 2 1 国内外研究现状 目前，国内外研究q o s 多播路由问题的主要有下面几种算法： k o m p e l l a 算、法【9 】也称k p p 算法，是一种求解满足延迟约束s t e i n e r 树的启发式算 法。k p p 算法共分三步：构造完全图，完全图的顶点为多播会话的源节点和目的节 点，完全图的边为满足延迟约束的最小代价路径：以此完全图为基础构造一棵最小 代价生成树( s t e i n e r 树) ；最后，将完全图的各边还原为原始物理路径，并移去还 原操作中所形成的回路。该算法的时间计算复杂度为o ( a i v i ) ，其中，川为网络中的 节点数，为端到端延迟的上限。 c d k s 算法【lo 】由q s u n 等人提出，也是一种求解满足延迟约束s t e i n e r 树的算法。 该算法首先利用d i j k s t r a 算法找到最小代价树，然后检查各最小代价路径是否满足延 迟约束，如不满足，就用d i j k s t r a 算法计算出另一棵最小延迟树，最后合并这两棵树， 并移去可能存在的回路。c d k s 算法最后总能找到满足延迟约束且代价最小的多播 树，其时间计算复杂度为o ( a i v l 3 ) 。 b s m a 算法】由p a r s a 等人提出，它首先使用d i j k s t r a 算法求出从多播源节点到 各目的节点的最小延迟路径，以构成最小延迟树。在不违反延迟约束的前提下，用第 k 条最短路径算法精练该最小延迟树，即用代价更小的路径来代替原路径，使得最小 延迟树的总体代价不断降低。文献 1 2 】的实验表明，在目前所有求解满足延迟约束 s t e i n e r 树的启发式算法之中，b s m a 算法的代价精度最好。但b s m a 算法也有其缺 点，就是计算复杂度很高为o ( k a i v l 3l o g i v l ) ，因此不适用于大型网络。 3 硕十学位论文第一章绪论 c h e n n a h r s t e d t 算法【l3 】由s c h e n 和k n a h r s t e d t 提出，是一个完全的分布式算法， 首先，多播会话的源节点以扩散的方式发送探测报文，探测报文仅沿着能满足q o s 约束、且至少能够到达一个目的节点的路径发送。探测报文在扩散时，能够探测出满 足q o s 约束且距离最短的路径，这些最短路径以渐进的方式生成多播树。对于准备 加入到多播组的新成员，也可以采用相同的方式( 但方向相反) 向多播树发送探测报 文，从而找到满足q o s 约束且距离多播树最短的路径。该算法的消息复杂度为d i e i 其中吲为网络中的链路数。这种算法实际上是在路由时间和通信开销之间选择的折 衷，因为探测失败时，会增加路由时间和通信开销，如果在每个节点保存了全局信息 ( 即便不准确) ，并为源节点赋予一定的票( t i c k e o 数，每个探测至少需要具有一票，则 上述算法可以获得更好的性能。 q o s m i c 路由协议i l4 j 是一种比较成功的q o si n t e m e t 多播路由协议，可以大致把 它归为分布式路由算法，其候选路径的搜索由本地搜索和树搜索两个进程构成。当本 地搜索未能找到时，协议就采用树搜索，树搜索使新成员发送一个m j o i n 报文到所 谓指定管理节点( d e s i g n a t e dm a n a g e rn o d e ，简称d m n ) ，d m n 在组播树中选择一个树 节点子集。这个子集中的节点随后向新成员发送b i d 报文。这些b i d 报文所经历的 路径是由单播路由协议决定的，它们构成候选路径。在挑选阶段，新成员根据接收到 的b i d 报文挑选出满足q o s 要求的最佳路径及其管理节点。在q o s m i c 中，多播组 成员能够动态地加入退出多播树，也可以从共享树切换到更有q o s 竞争力的有源树， 而且q o s 约束也容易被扩展，但是，管理节点的引入增加了q o s m i c 的消息复杂度， 也降低了系统的鲁棒性。 以上所列举的q o s 多播路由算法( 包括源路由和分布式路由) 都属于平面路由 算法，不适用于大型网络。目前，有关q o s 层次多播路由的研究十分少见，尽管陆 慧梅提出了一种支持q o s 的层次多播路由算法框架【l5 1 ，s y a n 等人提出了q o s m i c 协议的域问路由方案【l6 1 ，但是这些研究要么只是考虑了一个q o s 约束( 带宽约束) ， 要么算法不具备可扩展性。除此之外，在现有的q o s 多播路由算法中，也出现了几 种采用新型组合优化方法( 如遗传算法【17 1 、蚂蚁算法【1 引、模拟退火算法【1 9 j 等) 的路 由算法。例如，q s u n 和ex i a n g 等人分别提出了各自的基于遗传算法的q o s 多播 路由算法；吕国英和c c h u 分别提出了各自的基于t s p ( 旅行商问题) 蚂蚁算法( 静 态蚂蚁优化) 的q o s 多播路由算法。但是，这些组合优化的方法依然存在着一些缺 点和不足，就是易陷于局部最优，收敛速度慢，有时甚至无法收敛。 1 2 20 0 8 多播路由算法存在着的问题与不足 总的来看，现有的q o s 多播路由算法存在着以下的问题与不足： ( 1 ) 没有考虑到过时的、非精确的网络状态信息对q o s 多播路由的影响，而状 态信息的非精确性又是客观存在的，在大型网络中更是如此。需要说明的是，尽管有 4 硕士学位论文 第一章绪论 一些分布式的q o s 多播路由算法在路由计算时只使用了较为精确的局部( 或本地) 的状态信息，但它们都是以单播源路由算法作为其路由计算的基础，因此，同样会不 可避免地涉及到状态信息的非精确性问题。实验证明，网络状态信息的不精确性直接 影响到收敛速度和路由成功率。 ( 2 ) 路由的扩展性( 层次路由) 问题【2 0 】仍然是一个没能很好解决的问题，目前 提出的大多数启发式算法本质上都是集中式的。如何实现有效的多q o s 状态参数( 即 特征值) 的拓扑聚集【2 ，并尽可能地减小由此而带来的状态信息的不精确性；如何表 示这些聚集的网络状态信息；如何利用这些聚集的状态信息找到满足多个q o s 约束 的路径或多播树【2 2 1 。这些技术难题至今为止都没能很好地解决，现有的q o s 多播路 由算法也都未涉及到这方面的内容。 ( 3 ) 对q o s 约束的考虑比较孤立，没有兼顾其它q o s 度量的影响，也没有考虑 到q o s 路由与传统“b e s t e f f o r t ”路由的结合。总体来讲，源路由算法的计算复杂度 偏大，分布式路由算法的消息复杂度偏大。另外，基于遗传算法( 或静态蚂蚁算法、 模拟退火算法等) 的q o s 多播算法也普遍存在着计算复杂度过高、收敛速度过慢【2 3 。2 5 l 的问题。 1 3 本文的工作与组织结构 应用多播的关键是确定有效的多播路由，即求解最优s t e i n e r 树1 26 。，这一问题被 证明是n p 完全问题。目前提出的大多数启发式算法本质上都是集中式的，即至少需 要一个掌握整个网络拓扑信息的核心节点【27 1 。如p a r s a 等提出的b s m a 算法，由k o u 等提出的k m b 算法【2 引。本文主要研究基于蚂蚁优化算法的具有q o s 约束的分布式 多播路由算法问题( d i s t r i b u t e dq o sm u l t i c a s tr o u t i n gb a s e do na n tc o l o n y o p t i m i z a t i o n a l g o r i t h m ，以下简称为d q m r a c o 算法) ，解决已有算法在多播规模增 大时路由选择时间长，全局优化性能差，容易产生回路的问题。本文的工作主要分为 以下三部分： 1 、具有q o s 约束的分布式多播路由模型建立的研究 论文分析了现有蚂蚁优化算法的优缺点，在研究分布式网络、q o s 约束，多播路 由的基础上，建立了分布式q o s 多播路由的数学模型，包括网络模型，q o s 度量及 特征模型和多播路由模型。网络模型假设存在一种分配策略，能将网络节点的q o s 度量合理地分配到与其相邻的链路的q o s 度量上。q o s 度量及特征模型设计了节点 的q o s 度量和链路的q o s 度量和多播路由模型，用数学描述了主要包括带宽、延迟、 延迟抖动、网络代价和包丢失率等q o s 度量。多播路由模型定义了用t ( s ，m ) 表示以 s 为根、包括目的节点集肘的一棵多播树。 2 、基于蚂蚁优化算法的具有q o s 约束的分布式多播路由算法的研究 定义两种类型的蚂蚁代理：向前蚂蚁和向后蚂蚁，给出了算法原理，算法步骤， 硕+ 学位论文 第一章绪论 对算法进行了以下改进：提出了一种带回路检测的分布式度约束算法，首先建立初始 多播路由树，多播路由树的寻找和建立可以在同时完成；提出一种改进的蚂蚁优化算 法，利用基于“超边 替换的蚂蚁算法优化多播树，定义两种类型的蚂蚁代理：向前 蚂蚁和向后蚂蚁，两种蚂蚁互相协作，共同发现满足带宽和延迟约束的最小代价路径， 蚂蚁一边前进一边对已经建立的初始多播路由树进行优化，充分利用了分布节点的局 部信息，能够降低蚂蚁死亡率，改善解的质量，提高了全局优化性能，降低了产生回 路的可能。改进了算法收敛规则，通过信息素强度变参数控制，残留信息素数量限幅 控制和挥发系数动态自适应调节，增加了算法收敛速度，提高了算法的全局收敛性。 3 、系统仿真与性能分析的研究 通过仿真实验讨论了网络规模、多播规模和时延限制对分布式q o s 多播路由算 法性能的影响，并与b s m a 算法和k m b 算法进行了比较，d q m r a c o 算法可适应 大规模的多播环境，方便的避免循环回路的产生，而且引起的额外负载较小，具有较 短的建立路由时间。 本文共分为六章，各章的内容如下： 第一部分，绪论。介绍了q o s 多播路由算法技术的研究背景，国内外研究现状、 存在的问题、本文的工作和组织结构。 第二部分，蚂蚁优化算法和q o s 多播路由的相关理论和技术。介绍了q o s 约束、 q o s 多播路由概念、分类和研究的主要难点，传统蚂蚁算法的优点和不足，传统蚂蚁 算法求解q o s 多播路由的相关技术。 第三部分，基于蚂蚁优化的分布式q o s 多播路由算法的设计。建立了分布式q o s 多播路由的数学模型，包括网络模型、q o s 度量及特征和多播路由模型。提出了基于 蚂蚁优化的分布式q o s 多播路由算法，定义两种类型的蚂蚁代理：向前蚂蚁和向后 蚂蚁，给出了算法原理，算法步骤，对算法进行了改进：( 1 ) 采用带回路检测的分布 式度约束算法为大规模网络建立初始多播路由树：( 2 ) 利用基于“超边替换的蚂蚁 算法优化多播树。( 3 ) 改进了算法的收敛规则。 第四部分，基于蚂蚁优化的分布式q o s 多播路由算法的分析。分析了d q m r a c o 算法的规则，说明算法如何实现路径选择、局部更新和全局更新。对算法进行了正确 性证明和复杂性分析，对带回路检测的分布式度约束算法性能进行了分析，对算法的 收敛性进行了分析。 第五部分，仿真实验与分析。针对前面几章的研究内容实施仿真实验与分析，通 过仿真实验与分析结果来验证基于蚂蚁优化的分布式q o s 多播路由算法的优越性。 第六部分，总结和展望。对本文所做工作进行了全面的总结，分析了工作中存在 的不足，并对下一步的研究工作进行了探讨。 6 硕士学位论文 第二章相关理论和技术 第二章相关理论和技术 2 1q o s 约束的多播路由 随着i n t e r n e t 的不断发展，各种各样的网络应用不断涌现，相继出现了i p 电话、 视频会议、远程多媒体教学等网络应用，这些网络应用对网络传输时延、延时抖动、 网络带宽、数据丢失率等特性较为敏感，而当前i n t e r a c t 只提供尽力发送服务，网络 层不区分用户业务的种类，而将网络资源公平地提供给各类业务，在分组丢失、延迟 等方面公平地对待各类业务，这种尽力发送的机制使网络层无法保证上述对于应用业 务至关重要的传输参数。例如，文件传输业务要求分组的丢失率尽可能低，而传输延 迟不是关键因素：实时多媒体业务则更看重延迟和抖动。这就要求网络能够区别对待 各种业务，并对它们提供不同的服务质量。因此这就要求网络应能根据用户的要求分 配和调度资源。 2 1 1o o s 约束 为解决这个问题，学者们提出了服务质量1 3 2 j 的概念，并开始研究q o s 数据传输 方式与协议，寻找用q o s 数据传输方式来解决上述网络应用问题1 3 引，许多研究人员 还提出了有关q o s 的算法 3 4 3 5 】。i e t f ( i n t e m e te n g i n e e r i n gt a s kf o r c e ) 成立了专门 的工作小组来研究媒体服务质量的定义和相关的标准。服务质量是指发送和接收信息 的用户之间，以及用户与传输信息的集成服务网络之间关于信息传输的质量约定【3 6 1 ， 是网络在传输业务流时业务流对网络服务的需求的集合，其中业务流是指与特定q o s 相关的从源到目的地的分组流。也就是说，q o s 是应用业务对网络传输服务提出的一 组可度量的要求，主要包括带宽、端到端延迟、分组丢失率、抖动、花费等网络在 传输相应的数据业务时，必须满足这组要求。q o s 需求可以通过一个约束集来描述， 包括链路约束、路径约束和树约束。链路约束定义了从源到目的地的每一条链路的约 束，如带宽约束；路径约束定义了从源到目的地的一条路径上端到端q o s 需求，如 延迟；树约束定义了对组播中整个组播树的约束，例如对组播树延迟的约束是对树中 从源到所有目的地的路径中最大延迟的约束。服务质量q o s 不是对网络中某个个体 或元素的行为描述，它涉及到用户与用户，用户与网络以及网络内部节点( 或元素) 的整体行为。传统的i n t e r n e t 只提供单一的服务，即“尽力而为的服务。为了在i n t e m e t 上提供有质量保证的服务，必须制订有关服务数量和服务质量水平的规定，规定中需 要在网络方面增加一些协议，对具有严格时延要求的业务和能够容忍延迟、抖动和分 组丢失的业务进行分类，同时采用多种分组调度机制和算法对这些业务进行处理，这 7 硕士学位论文第二章相关理论和技术 就是q o s 机制的职责，也就是说，q o s 机制不是用来增加网络带宽，而是通过最优 化的使用和管理网络资源使其尽可能满足多种业务的需求。 2 1 2o o s 多播路由概念 用户的数据要从一个终端发送到另一个终端，首先要确定传输路由，不同的通信 方式确定路由的方式也不同，数据包在网络中传输一般有三种方式：单播、广播和多 播。其中单播的实现一般采用d i j k s t r a 提出的最短路由算法【2 9 j 或b e l l m a n f o r d 算法p o j 来建立点到点的路由，多播是源节点向多个目的节点发送信息的通信方式，信息同时 传递给一组目的地址，消息在每条网络链路上只传递一次，而且只有在链路分叉时， 消息才被复制。研究多播的目的是为了提高对网络资源的利用率，它允许一个或多个 发送者发送单一的数据包到多个接收者，多播源把数据包发送到特定多播组，而只有 属于该多播组的地址的成员才能接收到数据包，多播不仅可以大大的节省网络带宽还 可以提高数据传送效率，减少主干网出现拥塞的可能性。 单播在源节点和每一个目的节点之间都需要单独的数据信道，对网络带宽的占用 会随信道的增加而线性增长。广播是多点传递的最普遍的形式，它向网络中的每一个 节点传送一个分组的拷贝，其主要缺点是对此信息不感兴趣的主机也必须收到。多播 也称为组播，是一种一点到多点、多点到多点的通信方式，即多个信宿同时接收一个 或多个信源发送的相同信息1 3 。如图2 1 。 接收者i接收者2 接收者3接收者4接收者5 a ) 单播数据传输方式 8 接收者6 接收者7 硕士学位论文第二章相关理论和技术 b ) 广播数据传输方式 接收者6 接收者7 接收者1接收者2接收者3接收者4接收者5 接收者6 接收者7 c ) 多播数据传输方式 图2 - 1 单播、广播、多播数据传递示意图 多播主机的扩展、多播路由和i p v 6 的出现，使得网络层具有逐跳的多播能力来 满足更加严格的q o s 需求。但在设计q o s 的多播路由时因为时延、时延抖动、带宽 和分组包丢失率等多个约束的存在通常使多播路由问题不可解1 3 引。当多播路由算法和 多播路由协议结合时，由于状态收集与更新、节点的加入引起拓扑的变化、以及树的 维护与可扩展等方面要考虑，结果使得协议设计过程更为复杂。 q o s 多播树在计算路径时，随着q o s 约束的增加，计算开销也相应增加，计算 多播路径的开销包括节点接入路径建立所消耗的时延以及多播路由信令开销【3 9 1 。随着 时延敏感的网络应用和分布式多媒体应用的大量出现，越来越需要用有效的方法来计 算满足q o s 需求的多播树，因此，为了更有效地进行多播通信，确定多播路由非常 9 硕+ 学位论文第二章相关理论和技术 关键，多播路由算法就是用来确定多播树。多播树是通过在每个路由器设置路由表而 建立的，路由表上给出了为使信息传送到组成员，此路由器应选择哪个邻接节点，由 于网络的动态变化，每个路由器的路由表也需要定期更新，此外路由表的设置要保证 不能有回路的产生。 2 1 30 0 8 多播路由分类 路由计算可以是集中计算，即整个路由的计算在一个节点内进行，也可以是分布 计算，即计算丌销由沿着路由的各个节点分担，也可以是层次计算【矧。总之，整个路 由选择包括收集、更新网络状态信息和查找路由路径等过程，根据处理策略的不同可 分为源路由、分布式路由和层次路由【4 l 】三种。q o s 多播路由按算法实现方式可以分 为集中式和分布式两种。 ( 1 ) 集中式路由1 4 2 j 的路由选择策略是由网络控制中心n n c ( n e t w o r kc o n t r o lc e n t e r ) 承担的。n n c 首先通过某种链路协议获得完整的网络拓扑信息，之后进行路由计算。 显然，集中式路由能够得到相对较优的多播树：但也存在一些缺点，如对n n c 的计 算性能和可靠性有很高的要求；节点在收集全网拓扑信息时容易造成链路拥塞，产生 时延；当网络规模较大时还存在异步更新的问题等。 ( 2 ) 分布式路由1 4 3 】选择的基本思想是每个网络节点只计算本地的路由表，多播组 成员在只具有局部信息的条件下参与路由的确定，不需要每个组成员掌握整个网络的 拓扑信息。显然，分布式多播路由选择中不存在一个存储整个网络信息的“核心”节 点，因此整个网络系统的鲁棒性较强，这对于大型网络多播路由的确定是十分有利的， 因此，目前的i n t e m e t 高性能组播路由算法要求对分布式计算方式进行有效的支持。 q o s 路由的目标就是在源节点到目的节点之间，如何找到一条能够同时满足一个 或几个约束条件且具有最小代价的路径，使用多个特征值可以在某种程度上更精确地 描述约束；然而，找到一条符合多个约束条件的路径实质上是一个很难解决的问题， 这种问题往往不存在多项式解法。 2 1 40 0 $ 多播路由研究的主要难点 q o s 多播路由研究的主要难点在于： ( 1 ) 状态信息的不确定性：传输时的时间延迟和抖动、新连接的加入和原连接的 取消等都导致网络状态的不断变化。这些变化因素都直接影响了全网状态信息的准确 性，从而影响路由算法的性能。 ( 2 ) n p c o m p l e t e 问题：即同时对两个以上相互独立的参数提出要求时，这个问题 就是一个n p c o m p l e t e 问题。由于q o s 多播路由需要对时间延迟，链路带宽，丢失 率等多个参数的性能提出要求，所以它是一个n p c o m p l e t e 问题，而n p c o m p l e t e 问题难以用传统方法进行最优化。 1 0 硕士学位论文 第_ 二章相关理论和技术 由于状态信息的不确定性和多约束参数的难以优化，使得用传统的方法来解决 q o s 多播路由和实现网络负载的均衡和拥塞避免存在着较大的困难。 2 2 蚂蚁优化算法 随着通信网络( 包括电路交换网与分组交换网) 的迅速发展，越来越多的人工智 能技术需要用于其中，以解决复杂的网络问题，如：q o s 路由、拥塞控制、负载平衡 等也可以用来提高网络路由的可靠性和可扩展性。从本质上讲，多播路由问题是一个 动态的、分布式的、多目标优化的问题，并且，路由决定应该由每个网络节点根据本 地的状态信息独立计算完成。而蚂蚁算法本身隐含的并行、分布式计算能力与网络路 由具有较强的相似性m j ，且蚂蚁选择路径时是基于概率的，因此可方便的实现拥塞规 避，这是其他算法所无法比拟的。因此，多播路由问题很适合利用蚂蚁优化的方法来 处理和解决。 2 2 1 蚂蚁算法概述 蚂蚁算法亦称蚂蚁优化【45 | ( a n tc o l o n yo p t i m i z a t i o n ，a c o ) ，是一种基于生物种 群的仿生算法。它是意大利学者d o r i g o ，m a n i e z z o 等人在2 0 世纪9 0 年代初首先提 出来的，算法应用在旅行商m 】( t r a v e l i n gs a l e s m a np r o b l e m ，t s p ) 和资源二次分配问 题1 47 j ( q u a d r a t i ca s s i g n m e n tp r o b l e m ) ，取得了较好的效果。研究表明，自然界中的 蚂蚁具有找到蚁巢与食物之间最短路径的能力，这种能力是靠其在所经过的路径上留 下一种挥发性的分泌物来实现的。这种分泌物被称为信息烈4 引( p h e r o m o n e ) ，它会随 着时问的推移而逐渐消失。蚂蚁在一条路径上前进时会留下信息素，后来的蚂蚁选择 该路径的概率与此时这条路径上的信息素强度成正比。对于一条路径来讲，选择它的 蚂蚁越多，那么该路径上所留下的信息素的强度就越大，而强度越大的信息素会吸引 更多的蚂蚁，从而形成了一种正反馈。通过这种正反馈，蚂蚁最终能够找到蚁巢与食 物之间的最短路径1 4 圳。 蚂蚁算法是一种受自然界生物的行为启发而产生的“自然算法，它包含两个基 本阶段：适应阶段和协作阶段。在适应阶段，各候选解根据积累的信息不断调整自身 结构。在协作阶段，候选解之间通过信息交流，以期望产生性能更好的解，这类似于 学习自动机的学习机制，其基本原理如图2 2 ： 硕十学位论文 第二章相关理论和技术 嗖覃 、乒矽 图2 - 2 蚂蚁路线图 上图表示蚂蚁觅食的线路，a 为蚁穴，b 为食源，从a 到b 有两条线路可走， a c b 是长路径，a d b 是短路径。蚂蚁走过一条路线以后，在地面上会留下信息素气 味，后来的蚂蚁就是根据留在地面上这种气味的强度选择移动的方向。图2 2 ( a ) 表示起始情况，假定蚁穴中有4 只蚂蚁，分别用l ，2 ，3 ，4 表示，b 为食源。开始 时蚁穴中蚂蚁l ，2 向食源移动，由于路线a c b 和a d b 上均没有蚂蚁通过，在这两 条路线上都没有信息素气味，因此蚂蚁l ，2 选择这两条线路的机会均等。令蚁1 选 择a c b 线路，蚁2 选择a d b 线路，假定蚂蚁移动的速度相同，当蚁2 到达食源b 时，蚁1 还在途中，如图2 2 ( b ) 。蚁2 到达食源以后就返回，这时从b 返回也有 两条线路选择，哪一条线路上信息素的气味重就选择哪一条。因为蚁l 还在途中，没 有到达终点，这时在b c a 线路上靠近b 端处，蚁l 还没有留下信息素气味，所以蚁 2 返回蚁穴的线路只有一个选择，就是由原路返回。当蚁2 返回a 时，蚁3 开始出发， 蚁3 的线路选择必定是a d b ，因为这时a d b 上气味浓度比a c b 上重( a d b 上已 有蚂蚁两次通过)，如图2 2 ( c )