（应用数学专业论文）基于qos的网络路由选择算法的研究.pdf

摘要 随着i n t e m e t 网络规模的迅速增长、网络技术的不断成熟完善，传统的“尽力而 为”网络机制并不能满足q o s ( q u a l i t yo fs e r v i c e ，服务质量) 通信的要求。所以，口 网络的q o s 路由问题已经成为当今网络通信领域的一个研究热点。基于蚁群算法的 q o s 路由选择算法一经提出，由于算法简单并且易于实现而得到了很多学者的关注， 并取得了较多的研究成果。 本文的研究工作有以下3 个方面： 1 ) 首先介绍了q o s 路由的背景知识及其算法的基本概念，并对q o s 度量参数的 定义进行了较为详细的论述。结合图论的知识对q o s 网络建立了数学模型。并讨论 了当前q o s 路由算法的研究现状。 2 ) 分析了蚁群算法的基本原理与模型，并介绍了算法的特点和研究现状。针对 q o s 路由的特点，对已有的蚁群算法进行了改进。并对改进算法进行了大量的仿真实 验，验证了改进算法在解决基于精确网络信息的q o s 路由问题上的有效性和稳定性。 3 ) 首先，讨论了实际的q o s 网络状态的非确定性的原因，及其解决方案和研究 现状。建立了基于概率的网络模型，并给出基于概率模型的q o s 路由算法 ( 1 h o b a b i l i t y - b a s e dq o sr o u t i n go p t i m i z a t i o na l g o r i t h m ，f q s r a ) ，并通过仿真实验验 证了该算法在解决o o s 路由问题上的有效性。 关键词：蚁群算法：服务质量；概率；路由算法 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to f t h en e t w o r kt e c h n o l o g y ，n e t w o r km e c h a n i s mf o r b e s t e f f o r t c e n t 髓t i s 母t h eq u a l i t yo fs 酬c c q o sr o u t i n gp r o b l e mh a db c c o m eo n eo fm a j o r r e s e a r c ht o p i c si nc o m p u t e rn e t w o r k s al o to f s c h o l a r sc o n c e r n e dt h ea n tc o l o n ya l g o r i t h m a n do b t a i nam o r er e s e 缸c hr e s u l t 够s o o na si tw a sp u tf o r w a r d f o ri t ss i m p l e n e s sa n de a s y t or e a l i z a t i o n t h i st h e s i sm a i n l yd i s c u s s e st h ef o l l o w i n ga s p e c 【s ： 1 、f i r s td e s c r i b e st h eb a c k g r o u n da n dc o n c e p t so fq o sr o u t i n g , a n db u i l d st h e m a t h e m a t i c sm o d e lf o rq o sn e t w o r kw i t hg r a p ht h e o r y t h e nd i s c u s s e st h er e c e n tr e s e a r c h s t a t u s ，p r o b l e m 2 、p r e s e n t st h eb a s i ct h e o r y , m o d e l c h a r a c t e r i s t i ca n dr e s e a r c h e so f t h ea c a b e c a u s e o f t h ec h a r a c t e r i s t i co f q o sm u t i n g , t h et h e s i sp r o p o s e st h ei m p r o v e da l g o r i t h m r e s u l t so f s i m u l a t i o n sd e m o n s t r a t et h a tt h ei m p r o v e da l g o r i t h mi se f f e c t i v ea n df e a s i b l eo ns o l v i n g q o sr o u t i n gp r o b l e m s 3 、d i s c u s s e st h er e a s o n , s o l u t i o n sa n dr e s e a r c h e so f t h ei m p r e c i s i o ni nq o sn e t w o r k s e 【a t e b u i l d st h en e t w o r km o d e lb a s e do np r o b a b i l i t y , a n dp r o p o s e sp r o b a b i l i t y - b a s e dq o s r o u t i n go p t i m i z a t i o na l g o r i t h m d e m o n s 廿a t e st h ee f f e c t i v i t yt h r o u g ht h es i m u l a t i o n s k e yw o r d s ：a n tc o l o n ya l g o r i t h m ；q o s ；p r o b a b i l i t y ；r o u t i n ga l g o r i t h m 学位论文独创性声明： 本人所呈交的学位论文是我个人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工 作的同事对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意。如不实，本人负全部责任。 论文作者( 签名) ： 学位论文使用授权说明： 凡旬年；月玎日 河海大学、中国科学技术信息研究所、国家图书馆、中国学术 期刊( 光盘版) 电子杂志社有权保留本人所送交学位论文的复印件或 电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子 文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外， 允许论文被查阅和借阅。论文全部或部分内容的公布( 包括刊登) 授权 河海大学研究生院办理。 论文作者( 签名) ：宰立l m ，计年3月玎e l 基于q 0 s 的网络路由选择算法的研究 第一章引言帚一早ji 百 1 1 研究背景 随着高速网络和多媒体技术的飞速发展，人们越来越多地提出了各种各样的要 求。传统的分组交换网络，如i n t e r n e t ，是面向非实时的数据通信( 如f t p 和e m a i l 的传输) 而设计的，采用的t c p i p 协议主要是为了优化整个网络的数据吞吐量并保证 数据通信可靠性f 。在这种传统协议的尽力而为( b e s te f f o r t ) 转发机制中，网络层不区 分业务，而将网络资源公平的提供给各类业务，在分组丢失和时延等方面公平的处理 各类业务，导致了传输没有明确的时间和可靠性保障。 当今的分布式多媒体应用( 如视频会议、视频点播( v o d ) 、i p 可视电话、远程教 育网络游戏) ，不仅包括文本数据信息，还包括语音、图形、图像、视频、动画这些 类型的多媒体信息。对这些有带宽、延迟、延迟抖动、丢失率、吞吐量等特殊要求的 应用来说，现有的“尽力而为”的服务显然是不够的。 为了满足网络上各种数据应用的服务质量要求，i e l l f 首先提出了服务质量 ( q u a l i t yo fs e r v i c e ，q o s ) 保证的概念。其核心思想就是针对不同客户或不同业务特性 的要求，尽可能地提供好的服务质量。服务质量体现的是消费者对服务者所提供服务 的满意程度，是对服务者服务水平的一种度量和评价。通过研究网络q o s ，可以提高 网络资源利用率，降低网络成本；网络运营商可以通过提供q o s 机制，根据不同用 户对q o s 的不同要求，提供多种有区别的服务，提高客户满意度，同时提高网络运 营商的经营收益。 q o s 路由的主要目标是为接入的业务选择满足其服务质量要求的传输路径，同时 保证网络资源的有效利用。大量的文献从不同的角度对网络q o s 问题进行了研究， 这些研究主要体现在下面几个方面i l 】： 1 ) 路由选择算法。路由选择是为发送报文分组而选择一条传输路径的过程。路 径选择算法设计的好坏关系到网络资源利用率和网络性能的高低。从理论上讲，路由 河海大学硕士学位论文 选择软件应当考虑网络负荷、数据报长度、数据报报头中规定的服务类型等情况， 但由于实现上的困难，通常以最短路由为前提进行路由选择。 2 1 流量控制和拥塞控制。网络流量控制是网络正常工作是采取的一系列措施， 使得网络避免出现发生拥塞的条件，从而避免造成网络拥塞。这些控制措施包括：网 络资源管理、介入允许控制、流量参数控制( 令牌桶工具使用) 、非一致性数据包的标 记和数据包的分流等。拥塞控制是网络拥塞时采取的一系列措施，从而使得网络拥塞 的强度、持续时间和扩散的影响减至最小。 3 1 流量工程。流量工程的作用在于使数据流通过网络，以避免不均匀的使用网 络而导致拥塞。而现在的动态路由协议总是选择最短路径转发包，导致不均匀的通信 分布。目前使用的方法是让网络管理员根据业务量的分布情况，手工配置链路和路由， 均匀的发配流量，不适合业务量分布不稳定和复杂网络的环境，因此流量工程实施需 要能够自动化和适应业务流量分布的变化，这样才能保证业务的q o s 。 4 ) 流量整形。流量整形是一种用来在接口上平缓通信、避免链路拥塞并满足服 务上要求的机制。流量整形通过对超过平均速率的分组进行排队或者保存到缓冲区， 将突发通信平缓，以满足配置的c i r 。一般使用先进先出( f i f o ) 或者加权公平排队 f w f q ) 方法调度队列中分组。 5 ) q o s 协商机制。在用户的服务质量请求与网络能提供的服务不一致的情况下， 要求网络可以根据与用户协商的结果来降低要求为用户提供服务。这种通过网络与用 户协商而为用户降低要求服务的机$ 0 t l p 为q o s 协商机制。 目前，在高速网络中按照用户的要求提供q o s 控制是一个很普遍的要求，也是 i n t e r a c t 发展的重点挑战。多媒体信息传输、管理q o s 控制和网络安全作为下一代网 络的核心技术之一，是当今计算机网络中研究与开发的热点问题。 1 2 解决方案和研究现状 目前q o s 单播路由问题是国内外研究的一个热点问题，近几年来，多篇文献论 述了q o s 路由算法研究的意义和重要性，具有深入研究的价值。 w a n g 和c r o w c r o f t 使用d i j k s t r a 最短路径树算法实现了带宽延迟受限的源路由求 解1 3 j 首先在网络拓扑图中将带宽不足要求的链路剪除掉，然后再以延迟为关键字使 2 基于q 0 s 的网络路由选择算法的研究 用最短路径树算法计算，这样求得的路径满足带宽约束并具有最短延迟。此外，他们 对最短最宽路径提出了分布式预计算方法。两个节点自j 的最宽路径是指在这两个节点 之间所有的路径中，瓶颈带宽最大的路径p 4 】。最短最宽路径( s h o r t e s t w i d e s tp a t h ) 是指 在多条最宽路径中最短的路径算法中每个节点通过链路状态协议维护全局状态，并 使用扩展b e l l m 锄f o r d 算法1 5 1 ( 或d i j k s t r a 算法【6 】) 为每个可能的连接目的地预先计算出 下一跳，这样，在连接请求时只需简单地查找路由表。这个算法在各个节点网络状态 信息一致的情况下可以保证无回路。 c h e n 和n a h r s t e d t 设计了多重路径受限的源路由算法 7 1 。算法的思想是将q o s 度 量的取值范围r 或z 映射到一个有限集合c ，从而保证多项式可解。以花费c o s t 为 例，设c 为最大花费约束，x 为一个小于c 的正整数算法将每个链路的花费映射到 集合中，其中属于区间【0 ，c 】的花费映射到中，属于区间的花费映射为( x + 1 ) ；花费c 映射为x 。可以证明，满足新问题的可行路径在原来的问题中也是一条可行路径，而 新问题可以通过扩展d i j l ( s t r a 算法或者扩展b e l l m a n f o r d 算法，在多项式时间内求解。 算法的性能与x 密切相关：随着x 的增大，找到可行路径的概率也增大，但同时引入 了更大的开销。因此，可以通过选取x 来调节该算法的性能。 。s h i n 和c h o u 设计了延迟受限的分布式算法1 9 l 。每个节点不需要保存全局状态， 而通过广播方式从源节点向目的节点传送累加了延迟的路由信息。中间节点在收到路 由信息时，首先累加自己的延迟，如果仍然小于规定的延迟，则再转发给其他邻居。 但是收到的路由信息必须满足以下两个条件之一：( 1 ) 它是第一次收到该信息；( 2 ) 信 息中累计的延迟比该节点原来收到的要小。路由信息的扩散路径就是延迟受限的可行 路径。若给路由信息设置适当的优先级，并使用特定的调度算法，则可以保证在每条 链路上最多发送一次这种路由信息。 k o r k m a z 等人设计了一种在多个可加性约束的条件下求解优化路径的通用算法 o o j 。算法首先构造路径花费函数，其中为路径p 的第i 维属性，为一个业务流所对应 的q o s 要求。最小化花费函数所找到的路径，为多重受限q o s 路由问题提供了一个 连续的近似频谱：从的线性近似，到时的渐近近似。因此，原来的多约束q o s r 问题 转化为最小化所对应的路径问题。 一3 - 河海大学硕士学位论文 j u t t n e r 等人基于拉格朗日松弛法设计了d c l c 的源路由求解算法l lz j 。算法首先 构造路径花费函数白( p ) 2 c ( p ) + a d ( n ，其中c 为原来的花费，d ( p ) 为路径p 的延 迟，五o 。然后以为关键字使用d i j k s t r a 算法计算最短路径p ，如果a = o 且同时p 满足延迟要求，则p 为原d c l c 问题的最优解；如果p 不能满足要求则可通过增大 而加大对g a p ) 的惩罚力度，求得满足延迟要求的路径。令 三( 2 ) = m i n 白( p ) i v p p ( 5 ，) ) 一加，其中d 为延迟要求，则对v 五o 有工( 兄) 为原 d c l c 问题的花费下界。算法通过计算特定的五从而最大化上( 五) ，得到花费下界，并 给出一条可行路径。 5 6 1 1 3 论文研究内容和组织结构 1 3 1 论文的研究内容 本论文主要研究基于q o s 约束的单播路由算法。分别在网络精确和非精确状态 的情况下，以蚁群算法为基础，分析和讨论了在多约束情况下的网络单播路由问题。 同时，结合大量的仿真实验验证了改进算法的有效性和稳定性。 本文的主要研究内容有： 1 ) 讨论q o s 路由的发展背景，分析当前q o s 路由算法的解决方案和研究现状。 讨论了q o s 路由的网络模型定义和q o s 度量参数，并给出q o s 单播路由算法的研究 的理论基础。 2 ) 描述了蚁群算法的基本原理及其模型，并以蚁群算法为基础，提出了一种用 于解决q o s 路由问题的改进蚁群算法。通过大量的仿真实验，验证了该算法在解决 q o s 路由问题上的有效性和稳定性。 3 ) 针对实际网络的不确定性，建立一种基于概率的网络模型，并在蚁群算法基 础上给出了相应的q o s 路由算法。并通过仿真实验验证了该算法在解决网络路由问 题上的有效性。 - 4 基于o o s 的网络路由选择算法的研究 1 3 2 论文的组织结构 论文全文共分为五章，具体内容安排如下： 第l 章讨论了q o s 路由的发展背景，归纳和分析了当前q o s 路由算法的研究成果， 以及研究存在的一些问题。并对本文的主要工作和组织结构进行了论述： 第2 章给出了q o s 路由的网络模型和q o s 度量参数的定义，并介绍了q o s 路由算 法的分类，为本文q o s 单播路由算法的研究工作奠定了坚实的理论基础； 第3 章研究了蚁群优化算法，包括该算法的原理、模型，并讨论了其优缺点。 第4 章针对q o s 路由的特点，对已有的蚁群算法进行了改进。并对该算法进行了仿 真实验，验证了算法在网络路由问题上的稳定性和有效性。 第5 章针对实际网络的具体要求，提出了一种基于概率的q o s 网络模型，并在蚁群 算法地基础上，建立了p q s r a 算法，并详细阐述了该算法的实现步骤。并 通过仿真实验验证了p q s r a 算法的有效性和健壮性。 1 3 3 论文的创新之处 论文的创新点主要有两点： 1 ) 针对蚁群算法在运算时容易陷于局部最优解，并出现停滞现象，本文进行了 相应的改进。改进算法能够自适应地更新信息素，使得算法尽可能地跳出局部最优解， 最终得到全局最优解。 2 ) 针对实际网络状态不确定性的特点，本文提出了一种基于概率的网络模型。 并在蚁群算法的基础上，给出了p q s r a 算法。仿真试验证明，该算法能够有效地解 决基于非精确网络状态的q o s 路由问题。 5 河海大学硕士学位论文 2 1 o o s 路由的概念 2 1 iq o s 路由的定义 第二章o o s 路由 定义2 1 i i 服务质量( q u a l i t yo fs e r v i c e ，q o s l 服务质量是网络在传输业务流 时，业务流对网络服务的需要的集合，其中业务流是指与特定q o s 相关的从源到目 的的分组流【矧。 也就是说，q o s 是应用业务对网络传输服务提出的一组可度量的要求，主要包括 代价、带宽、端到端时延、包丢失率、时延抖动等。网络在传输相应的数据业务时， 必须满足这组要求。q o s 需求可以通过一个约束集来描述，包括链路约束和树约束【列。 链路约束定义了从源节点到目的节点的每一条链路的约束，是对路由选择所使用 的链路的一种限制。树约束定义了对组播中整个组播树的约束，分为以下两种：1 ) 对 组播树中从源节点到目的节点的每条路径上性能度量的组合值的约束。例如，对组播 树时延的约束就是对树中从源节点到目的节点路径中最大时延的约束。2 ) 对从同一 源节点到任意两个目的节点路径上的性能度量的不同组合值的约束。 2 1 2q o s 路由的网络模型 网络由交换节点、链路和主机组成， g ( v ，e ) 1 5 6 ，其中v 代表网络中的交换设备， 向链路集。 在研究当中往往将其抽象为加权图 即网络节点集，e 代表传输线路，即双 定义2 1 2 1 ( 有向图) 有向图g 是由一个非空有限集合v 和其中某些元素的有序 对集合e 构成的二元组，记为g ( v ，d 。其中，v ) 称为图g 的节点集，元素v v 称 为图g 的一个顶点或节点；e 称为图g 的边集，元素勺e i 肭e ( v , ，v j ) 或e u = v , v j ， 为v 中元素的有序对，称为图g 的一条从叶到v j 的边( 弧) 。 6 - 基于0 0 s 的网络路由选择算法的研究 定义2 1 2 2 ( 有权图) 在有向图g ( v ，e ) 中，令元素e e 具有一组有序数列 ( w l ，w 2 ，) 作为p 的属性，则称g 为有权图，其中( w i ，也，) 称为弧p 的度量( 权 值) 。 定义2 1 2 4 ( 环) 环是指一条除了第一个顶点和最后一个顶点相同外其余顶点均 不相同的链路。 定义2 1 2 5 ( 路径) 在图g 中，如果对i = 1 ，2 ，七一1 有p ，v + ) e ，则 p = ( q ，v 2 ，唯) 为图g 的一条v i 至l j v k 的路径。 定义2 1 2 6 ( 对称网络) 在图a ( v ，d 中取任意链路( 甜，v ) ，对于链路的所有属性 有w f ( ，v ) = 似“) ，f = 1 ，2 ，朋，则称该网络为对称网络。 定义2 1 2 7 ( 非对称网络) 在图g ( y ，刃中，如果存在一条链路( u , v ) ，满足对至 少一个l f s m 有w j ( ，v ) w ( v ，“) ，则称该网络为非对称网络。 图2 1 有权图网络模型 c 从网络的抽象模型可知，网络由节点和链路两大要素组成。严格来说，对其进行 分析也应包括节点和链路两大要素。一般来说，对于大多数实时多媒体网络而言，其 链路是非对称的，因此网络链路应由两条有向边来表示。但为了便于理解，常常使用 对称网络模型以减少链路的数量，本论文研究的q o s 约束路由算法都是以对称网络模 型为例进行讨论，其实它们都适合于非对称网纠l i j 。 - 7 - 河海大学硕士学位论文 2 1 3q o s 路由的度量 定义2 1 3 1 度t ( m e t r i e ) 在网络g ( 矿，d 中，令链路e ee 具有一组有序数列 ( 嵋，w k ) 作为e 的属性，则( ，w e ，w k ) 称为链路口的度量，也称为权值 ( w e i g h t ) ! 1 。 q o s 需求要通过可测量的q o s 度量来实现。常用的几种q o s 度量主要包括可用 带宽、端到端延迟、分组丢失率、抖动和花费等 设g ( v ，d 表示网络，凡表示正实数集，r + 表示非负实数集，e e 表示任意一条 链路，则： 1 ) 代价c o s t ( e ) ：e 专且 2 ) 时延d e t a y ( e ) ：e 一足 3 ) 带宽b a n d w i d t h ( e ) ：e 寸足 4 ) 时延抖动出匆一f i t t e r ( e ) ：e 斗r + 5 ) 丢包率p a c k e t l o s s ( e ) ：e r + 不同的度量具有不同的性质。按照这些性质，q o s 度量可以分为可加性度量、可 乘性度量和晟大最小性度量三类。对于图g 中的路径尸= ( - ，k ，1 4 , v ) ，( 甜，v ) 表 示链路( “，v ) 的第f 个度量，整个路径p 的第i 个属性记为w ( p ) ，则以上三类度量的定 义如下： 定义2 1 3 2 ( 可加性度量) 若( p ) = w a y ，七) + h ( 七，) + + w a u ，v ) ，则称路径p 的 第f 个属性为可加性度量。 可加性度量包括延迟、抖动、花费、转发跳数等例如，一条路径p 的延迟为从 源到目的地的所有链路延迟的总和。如图2 1 中路径( 以6 ，e ，力的延迟总和为3 ，花费 为1 8 。 定义2 1 3 3 ( 可乘性度量) 若w j ( p ) = u ，k ) x w ，( k ，f ) x w , ( u ，v ) ，则称路径p 的 第f 个属性为可乘性度量。 例如，分组丢失率为可加乘度量，其中链路丢失率0sw j ( “，v ) 1 。在求解有关可 乘性度量问题时，可取其对数将其化为可加性度量。 一8 基于q 0 s 的网络路由选择算法的研究 定义2 1 3 4 ( 最小性度量) 若h ( p ) = m i n w , ( j ，七) ，嵋( t ，f ) ，( ”，v ) 1 或 w ( p ) - m a c , ( j ，七) ，( 七，) ，w ，( “，v ) 】，则称路径p 的第f 个属性为最小性度量。 例如，带宽为最小性度量，即路径带宽为路径上瓶颈链路的带宽。如图2 - 1 中路 径( a , b ，p ，力的带宽为l ( 其中链路( b , e ) 为带宽瓶颈) 。对于求解的问题可转化为问题。 对于不同类型的q o s 度量以及多个q o s 度量的组合，其计算的代价是不同的。例如， 求解多重最小性度量的组合可以在多项式时间内完成，而多重可加性度量的组合通常 不能在多项式时间内完成。 q o s 是应用业务对网络传输服务提出的一组可度量的要求，主要包括带宽、端到 端延迟、分组丢失率、抖动、花费等。网络在传输相应的数据业务时，必须满足这组 要求。q o s 需求可以通过一个约束集来描述，包括链路约束、路径约束和树约束。链 路约束定义了从源到目的地的每一条链路的约束，如带宽约束；路径约束定义了从源 到目的地的一条路径上端到端q o s 需求，如延迟；树约束定义了对组播中整个组播 树的约束，例如对组播树延迟的约束是对树中从源到所有目的地的路径中最大延迟的 约束。 2 20 0 $ 单播路由算法 根据应用范围，q o s 网络路由可以分为q o s 单播路由和q o s 组播路由。由于本 文针对单播路由，接下来着重阐述q o s 单播路由。 定义2 2 1 ( 可行路径( 可行树) ) 可行路径( 可行树) 是网络中从源到( 所有) 目标节点 的条路径( 组播树) ，并且该路径( 树) 具有足够的尚未分配的资源，能够满足特定的 q o s 需求1 5 6 1 。 定义2 2 2 ( 服务质量路由( q o s r ) ) 服务质量路由( q o sm u t i n g ) 是一种基于数据流 q o s 请求和网络可用资源进行路由的机制。或者，q o s r 是一种动态路由协议，并且 在其路径选择标准里可能包含可用带宽、链路和端到端路径利用率、资源消费量、延 迟、跳数以及抖动等q o s 参数【5 6 】。 定义2 2 3 ( q o s 单播路由) 对于网络g ( v ，d ，指定路由源节点5 v ，路由目的 节点d v ，q o s 约束集c 以及优化目标，q o s 单播路由就是找出满足给定q o s 约束 条件c 的s 到d 的最佳可行路径p ( s ，d ) c g 9 4 1 。 9 河海大学硕士学位论文 对于某些诸如剩余带宽、剩余缓存空间等服务质量的度量，路径的状态取决于瓶 颈链路的状态。对于这些服务质量的度量，可以定义两类基本的路由选择问题，其一 称为链路优化路由选择，如：带宽优化路由选择，它是寻找在瓶颈链路上具有最大带 宽的一条路径，这样的一条路径被称为最宽路径；其二称为链路约束路由选择，如： 带宽给路由选择，它是寻找瓶颈带宽高于要求值的一条路径链路。优化路由选择问题， 可以将d i j k s t r a 算法【7 8 1 或b e l l m a n f o r d 算法【7 8 1 稍作修改，而得以解决。链路约束路由 选择问题可以容易地减化为链路优化问题。 对于其它服务质量的度量，如延迟差、代价等，路径状态取决于路径上所有链路 的组合状态。同样，对于这些服务质量的度量，可以定义两类基本的路由选择问题， 其一称为路径优化路由选择，如：最小代价路由选择，它是寻找总代价最小的一条路 径。其二称为路径约束路由选择，如：延迟约束路由选择，它是寻找延迟局限于一个 要求的值之内的一条路径，这两个问题可由d i j k s t r a 算法或b e l l m a n f o r d 算法直接解 决嗍。 由此q o s 单播路由首先涉及四种基本的q o s 路由问题：链路约束路由问题 ( 1 i n k - c o n s t r a i n e dr o u t i n g ) 、链路优化路由问题( 1 i n k - o p t i m i z a t i o nr o u t i n g ) 、路径约束路由 问题( p a t h - c o n s t r a i n e dr o u t i n g ) 以及路径优化路由问题( p a t h - o p t i m i z a t i o nr o u t i n g ) 。 有关q o s 单播的一些组合路由问题都是由上面的四种基本问题演化而来，如图 2 2 所示。图中列出了q o s 单播路由中的基本路由问题和组合路由问题以及它们之间 的相互关系。 一1 0 基于q o s 的网络路由选择算法的研究 厂酾丽磊赢面丽i 虿 p 问题：多项式问题( p o l y n o m i a l ) n p 完全问愿：非确定多项式完全问题( n o n d c t e n n i n i s t i cp o l y n o m i a lc o m p l e t e ) 图2 - 2q o s 单播路由问题 由图可知，在q o s 单播路由中存在两类n p 完全的路由问题：路径约束路径优化 路由问题r p a t i l c o n s t r a i n e dp a t h - o p t i m i z a t i o nr o u t i n g ，p c p o ) 和多路径约束路由问题 一1 1 河海大学硕士学位论文 ( m u l t i - p a t h - c o n s t r a i n e dr o u t i n g ，m p c ) 。这两种n p 完全问题是基于以下两个基本假 设：1 ) q o s 度量相互独立；2 ) q o s 度量值是实数或极大整数。如果n 个q o s 度量中 n 1 个是有界整数，则n p 完全问题可以通过扩展的d i j k s t r a 或b e l l m a n f o r d 算法f 7 】 转化为p 问题。文献i s 0 1 也证明，如果所有的q o s 度量与其中任何一个相关，算法也 可以在多项式时间内求解。例如，在使用加权公平排队( w e i g h t e d f a i r q u e u e i n g ，w r q ) 调度的函数中，最差情况的时延和时延抖动是网络带宽的函数，因此，时延及时延抖 动约束路由问题可在多项式时间内求解。 表2 2 3 1 列举了近几年提出的一些典型的q o s 单播路由算法( 路由算法用作者姓 名表示) 。同时表中也列举了算法解决的路由问题、路由策略以及计算的时间复杂度 和状态信息】。 表2 - 1q o s 单播路由算法 算法 解决的问题路由策略时间复杂度状态信息 c h e n - n a h r s t e d t l 7 】带宽、代价约束 源路由o ( x n e )全局 带宽约束 源路由 o ( n l o g n + e )全局 m a - s t e e n k i s t e 8 0 】 多链路约束 源路由 o ( 砌p )全局 w a n g - c r o w c r o t t l 6 8 1 带宽、时延约束源路由 o ( n l o g 月+ p 、 全局 带宽约束 源路由 o ( n l o g n + p 1全局 g 谢n o r d a 明 ( 不精确) 时延约束源路由 多项式全局 ( 不精确) j u 恤一嗍时延约束最小代价 源路由 o ( e 2 l 0 9 4e )全局 多路径约束路径优 多项式 k o r k m a z 4 5 1 源路由全局 化 n e v e 8 8 】 多约束路径源路由 o ( 【n l o g ( k n + k 3 七m ) ) 全局 崔勇【卅多约束路径源路由 o ( k ( e + n l o g n ) ) 全局 王颖【3 9 1时延约束最小代价源路由 o ( n 2 + p n 2 1 全局 - 1 2 基于0 0 s 的网络路由选择算法的研究 o ( n e ) w a n g c r o w c r o f l 6 8 】 带宽优化分布式 全局 s a l a m a l 9 0 1 时延约束最小代价分布式 o ( n ) 全局 s u n i g q 时延约束最小代价分布式 o ( 以) 全局 o r d a 9 = z 多约束路径优化分布式 多项式 全局 o r d a 9 3 时延约束最小代价分布式 多项式 全局 吕国樊删时延、带宽约束分布式 o ( 矿) 全局 其中，仃表示网络节点数，e 表示链路数，k 为多约束路径的约束个数，x 为第k 条最短路径算法中的参数，尸为路径的个数。 2 3 本章小结 在这一章中，首先介绍了研究q o s 路由问题所使用的一般网络模型，并对q o s 度量参数的定义进行了较为详细的介绍。接着介绍了q o s 路由算法的分类，并对论 文所讨论的q o s 单播路由算法做了详细的介绍。 本章内容对全文起了引导作用，也可以说本章内容是对本文后续内容奠定了坚实 的基础。在本章基础上，我们将逐渐展开对q o s 约束的单播路由算法的研究。 - 1 3 河海大学硕士学位论文 第三章基本蚁群算法 3 1 蚁群算法的基本原理 蚁群算法是一种受自然界生物行为启发而产生的“自然”算法，产生于对蚁群行 为的研究。蚁群中的蚂蚁以“信息素”( p h e r o m o n e ) 为媒介，间接异步的相互联系。 这是蚁群算法的最大的特点。蚂蚁在行动( 寻找食物或者找回巢的路径) 中，会在它们 经过的地方留下一些化学物质，称之为“信息素”。这些物质能被同一蚁群中后来的 蚂蚁感受到，并作为一种信号影响后者的行动，具体表现在后到的蚂蚁选择有这些物 质的路径可能性比选择没有这些物质的路的可能性大得多。后到者留下的信息素会对 原来的信息素进行加强，并循环下去。这样，经过蚂蚁越多的路径，后到蚂蚁选择这 条路径的可能性就越大。由于在一定的时间内，越短的路径会被越多的蚂蚁访问，因 而积累的信息素也就越多，在下一个时间内被其他的蚂蚁选中的可能性也就越大。这 个过程会一直持续到所有的蚂蚁都走到最短的那一条为止团。 对于一个蚁群算法，其主要是进行两方面的工作：一是蚂蚁依照其前方各路径上 所存在的分泌物强度选择路径；二是对其所经过的路径上的分泌物强度进行调整。因 此，路径选择准则和分泌物调整准则的合适选取是非常重要的。 为了能够清楚的理解蚁群算法的数学模型，以求解平面上n 个城市的旅行商问题 ( t s p ) 为例说明。旅行商问题就是指按照一定的顺序访问每一个城市，在保证每个城 市只能被访问过一次情况下，使花费的代价最小。 首先引进如下记号：设i r a 是蚁群中蚂蚁的数量，吒( f ，- ，= 1 , 2 ，h ) 表示城市f 和 城市，之间的距离，岛( ，) 表示f 时刻位于城市f 的蚂蚁的个数，则有m = 包o ) 。r o ( t ) s - i 表示f 时刻在城市j ，j 连线上残留的信息量。初始时刻，各条路径上信息量相等，设 “( o ) = c ( c 为常数) 。每一个简单蚂蚁有以下特性： ( 1 ) 蚂蚁根据路径上的信息素强度，以相应的概率选择下一个城市。 1 4 基于o o s 的网络路由选择算法的研究 ( 2 ) 规定蚂蚁所选择的城市为之前未访问过的，由禁忌表控制( 设胁6 坼( t = l ，2 ， ，历) 表示第t 个蚂蚁的禁忌表) 。 ( 3 ) 完成一次周游后，蚂蚁在它的每一条访问的边上留下信息素。 蚂蚁七 = 1 ，2 ，埘) 在运动过程中，根据各条路径上的信息量决定转移方向。 露( r ) 表示在t 时刻蚂蚁t 由城市辟 移到城市j 的概率： 露=蠕一咄 。， 0 否则 其中：代表一个预先给定的启发式信息，在t s p 问题中，用城市f 和城市- ，之 间的边的长度吒定义了启发式信息的值，即= 1 吒；a 为残留信息的相对重要程度； 为预见性的相对重要程度；蚁群算法中的人工蚂蚁与大自然中的真实蚂蚁不同，人 工蚂蚁具有记忆功能，a l l o w e d k = 一t a b u 。 表示蚂蚁七下一步允许选择的城市，其 中，n 是一组城市，t a b u k ( k = 1 ，2 ，埘) 用以记录蚂蚁女当前所走过的城市，称为禁 忌表，集合t a b u 。随着进化过程作动态调整。 随着时间的推移，蚂蚁留在各个路径上的信息素会不断蒸发掉，用参数p 表示信 息素蒸发程度，0 p l ，蚂蚁完成一次循环以后，各路径上的信息量按照如下的规 则进行调整： 毛( ，+ ”) = ( 1 一p ) r # ( t ) + p a r o ( 3 2 ) = 苟 ( 3 3 ) 卜l 其中，苟表示第七只蚂蚁在本次循环中留在路径 上的信息量，勺表示本 次循环中路径i 上的信息量的增量。 根据信息素更新策略的不同，d o r i g om a c r o 5 8 1 曾给出了不同的蚁群算法模型，分 别称为a n t - c y c l e 模型，a n t - q t m n t i t y 模型和a n t - d e n s i t y 模。它们的差别在于苟( ，) 的求法不同。 在a n t - c y c l e 模型中： 1s 河海大学硕士学位论文 瑚归悟当第k 只蚂蚁在本次循环中经过( i ，j ) ( 3 4 ) 【0 ， 否则 式中：q 表示信息素强度，它影响算法的收敛速度；厶是第七只蚂蚁在本次循环 中所走路径的长度。 在a n t - q u a n t i t y 模型中： 瑚垆垮当第k 只蚂蚁在t 和t + l 之间经过( i j ) ( 3 5 ) 【0 ， 否则 在a n t - d e n s i t y 模型中： = 鲁喜盖“只蚂蚁在和t + 1 之间经过q j ( 3 6 ) 模型比较：a n t - q u a a t i t y 模型和a n t d e n s i t y 模型利用的是局部信息；而a n t - c y c l e 模型利用的是整体信息。在一系列标准测试函数问题上运行的实验表明，基于 a n t - c y c l e 模型的蚁群算法的性能优于其他两种模型算法。因此，对蚂蚁系统的研究 正朝着更好地了解a n t - c y c l e 模型的蚁群算法的方向发展。 3 2 蚁群算法的优缺点及其改进算法 3 2 1 蚁群算法的优点 蚁群算法是基于生物蚁群系统的集体觅食行为而发展起来的一类仿生优化算法， 因此算法必然带有真实蚁群系统的许多优点，总结如下： ( 1 ) 采用分布式控制，不存在中心控制 所有蚂蚁独立、无监督的同时搜索解空间中许多点，非常适合于并行实现，因此 本质上是一种高效的并行搜索算法。蚁群算法的分布计算特点表现在两个方面，一是 信息素分布在构造图的各条边上，每一只蚂蚁根据当前所在点的信息素情况构造解， 不需要控制中心；另一方面，在一只或者几只蚂蚁个体停止工作时，整个蚁群系统仍 然能够保持正常功能，因此算法具有较强的鲁棒性 ( 2 ) 强大的全局寻优能力 一1 6 基于q 0 s 的网络路由选择算法的研究 使用随机生成的蚂蚁群体而不是单只蚂蚁，使得算法找到全局最优解的概率增 加；另外，使用概率规则而不是确定性规则指导搜索；使得算法能够逃离局部最优。 而传统优化算法对初值、迭代步长的选择较敏感，一旦陷入局部最优就很难逃离。 ( 3 ) 适应性强 蚁群算法对搜索空间没有任何特殊要求，如目标函数的连续性、可导性以及目标 函数和约束函数的精确数学描述。 3 2 2 蚁群算法的缺点 虽然蚁群算法具有很强的全局寻优能力，在很多领域获得了广泛的应用，但也存 在一些缺陷，主要有以下三点： ( 1 ) 与其他的寻优算法相比教，蚁群算法的搜索时间过长。 一般地，蚁群算法的时间复杂度为o ( m ，1 2 i n ) ，n c 为循环次数，大部分的时 间被用于解的构造。 ( 2 ) 蚁群算法的执行过程中容易陷入局部最优解，甚至出现停滞现象。 蚁群算法中搜索进行到一定的程度后，所有蚂蚁个体发现的解趋于一致，此时， 即使使用随机搜索策略，也不可能在解空间中进一步搜索，这样就存在陷入局部极小 的可能性，不利于发现更好的解。原因在于信息素轨迹更新规则中不被选用的弧段上 的信息素轨迹和选中的弧段上的信息素轨迹的差异会变的越来越大，而蚂蚁始终沿着 信息素轨迹高的弧段爬行，这就导致当前不被选用的弧段今后被蚂蚁选择的概率变的 越来越小，进而使算法只会在某些局部最优解附近徘徊，出现停滞现象。 ( 3 ) 蚁群算法的数学基础比较薄弱。 蚁群算法虽然在应用方面有很大的优越性，但其理论基础方面仍很薄弱，如算法 的参数选择基本上都是基于经验的，算法的收敛性也是在众多假设条件下得到了一 些初步证明。 3 2 3 蚁群算法的改进算法 为了克服蚁群算法的缺陷，近年来，众多学者对蚁群算法进行了修正，发表了大 量有价值的学术论文。下面介绍几种具有代表性的改进方法： 一】7 - 河海大学硕士学位论文 ( 1 ) 蚁群系统【2 】 蚁群系统( a n tc o l o n ys y s t e m ，a c s ) 是d o r i g o 和g a m b a r d e l l a 在1 9 9 6 年提出 的i s 6 1 ，用于改善蚂蚁系统的性能。蚁群系统与a s 的不同之处主要体现在3 个方面。 第一，它采用了一种更具积极性的行为选择规则，从而能比a s 更好的开发利用蚂蚁 所积累的搜索经验。第二，信息素蒸发和信息素释放动作只在至今最优路的边上执行。 第三，蚂蚁每一次使用边( f ，力从城市i 移动到城市_ ，后，它就会去掉改变上一定量的 信息素，以增加探索其余路径的可能性。 在a c s 中，位于城市f 的蚂蚁七，根据伪随机比例规则选择城市，作为下一个访 问的城市。这个规则由如下式子给出： - ，：卜叫 丝 洲- i ，都 i s ，其他 其中g 是均匀分布在区间 o ，l 】的一个随机变量，吼是( o s 吼s 1 ) 是一个参数，s 是 根据式( 3 1 ) 给出的概率分