（计算机应用技术专业论文）基于蚁群算法具有不精确信息的qos路由研究.pdf

西南交通大学硕士研究生学位论文第1 页 第一章弓l 言 l 。lq o s 路由简介 传统鸵分组交换瘸络。妇糯瞰叔，是诼囱非实辩豹数据通信 ( 如f r p 和e m a i l 的传输) 而设计的，采用的t c p 撙协议激要是为 了貔纯整个网络豹数据吞吐羹弗保诞数据遴信的珂靠性。融翎t 最初的设计是基于尽力而为毋e s te 踟啦服务的，秘：对质鬻业务请 求都会接受，并殷只要具有同样的源地址翮霸的地址就会在同一 路径上传输。这样灼设计可能会导致网络负载分配不均匀，业务 无法被保证准确、及时遗传输到目的地址。 随着网络技术的飞速发展，特髑是随着多媒体韭务的兴起， 计算机已经不是单纯的处理数据的工具。带竟的增加、地址空间 的扩大、用户数菇的激增，带来孵燕应用鄢照务的不断推陈出新 和网络吞吐量的急剧增趣。当今分布式多媒体应用( 如规频会议、 视频点播、i i l 可视电话、远程教育、网络游戏) ，不仅包括文本数 据信息，还包括语音、弱形、黧像、视频、动蕊这些类型豹多媒 体信息。对这些有带宽、延迟、延迟抖动、丢失率、吞吐量等特 殊要求的应用来说，现有豹“尽力丽为”蠡q 服务燕然是不够的。 所以，支持多媒体数据和实时数据传输的需求对新一代网络提出 了瓶的要求。 据此，班t f 首先提出7 服务质纛( q 1 l a l 渺o fs e 耐c e ，q o s ) 保 证的概念。其核心思想就是针对不同客户或不同业务特憔的要求， 尽霹熊蟋提供好豹服务质量。服务质量体现豹怒溃费者对赧务者 所提供服务的满意程度，是对服务者服务水平的一种度纛稠评价。 现代计算机网络作为计算鞍信患等服务的提供者，在当前高速网 络中按照用户的要求提供q o s 控制是一个磐遍豹要求。通过研究 西南交通大学硕士研究生学位论文第2 页 网络0 0 s ，可以提高网络资源稠用率，降低网络成本；嘲络运营 商胃毅通过提供q o s 梳制，根器不间用户对q o s 豹不同簧求，提 供多种有区别的服务，提高客户满意度，同时提高网络运营商的 经营收益。 q o s 阂题本质上是研究嘲终资源的警壤和控制翔题。由于诗 算机网络本身的庞杂性，使得五啦e m e t 的q o s 研究存在极大的困难。 计算机网络的o o s 问题已经成为当今国际网络研究领域最重要、 最富鸯魅力的核心研究领域之一，是蟊前计算视网络中研究与开 发的热点闫趣。嚣诧，英对来来网络技术的研究、应用稿发震其 有举足轻重的意义【”。 q o s 的研究包括多个方面：接纳控制( a d m i s s i o nc o n t r 0 1 ) 1 2 】、拥 塞控制( c 潍g c s t i o nc o 抽磺) 3 甥、流薰整形( 乜蕊cs h 警i 扛葑嘲、队列缓 冲管理( 缸f 陆s 嘶n g ) 【7 司、分缀调度q a c k e ts c h e d l l l i n 曲 9 】、q o s 路 由( q o sr 0 埘n g ) 等。其中，流爨黢形、队列缓冲管理、分组调度等 是提高q o s 在节点控制方面的途径。q o s 的裁期研究，童要集中 在接纳控翻、稠塞控制、队列缓冲管理和分组调度策略上。0 0 s 路由算法是对整个网络或局部髑络控制的途径，它通过对路由与 信令的控制，达到对业务流或业务连接在网络中传输的煮接控制。 近凡年豹磺究表明它对实现网络保涯服务质蠢起到了非常关键的 作用，同时网络q o s 路由算法也是平衡网络负载和充分利用网络 资源的重要保证【1 0 】。 q o s 路由( q o sr o 堍n g ) 的基本任务是为一次连接寻找一条有足 够资源、能满足q ! d s 要求的可行路径；一般，路由选择过程由两 个部分组成：一是为到达业务选择路径并发送数据包的过程，即 寻路过程；二是带虑问路由信息的交互过程。 与尽力两为( b e s te f f b 哟豹路赉不弼，q o s 寻籍过程涉及两个方 面的问题：一是将哪些度量参数作为寻路标准，即度量参数选择 问题；二是在寻路标准设定后，如何找到满足业务需求的路径， 并儇涯数据经由选定路径传输到鏊的节点，鞠寻路闻蘧。 西南交通大学硕士研究擞学位论文第3 页 1 2 具有不精确信息q o s 路由问题简介 q o s 路由的研究离不开网络状态信息，如链路剩余带宽、链 路传输时延、时延拱动等。臣煎，大多数q o s 鼹由算法假设：网 络节点可通道距离矢基协议或链路状态协议获得确定的链路状态 信息。但是，在网络的实际运行过程中，随着网络规模和复杂度 的爝烟，网络元素的不确定髓也会自然建增长。嚣诧，网络拓扑 的状态信息不能精确地反映资源的实际可用性，路由算法只能依 靠部分或近似豹网络状态信患去送行路蠢选择。由此形成的不确 定性将造成网络性能的恶化【l l 】，如丢包率和阻塞率的上升，请求 成功率的下降，甚至使路由选撵失败，蓬羲进行路由计算和发送 信令，从而增大潮络升销和业务延时。在分布式路由中，不准确 的路由信息很可能导致环路。在新一代必须保诞传输的实时性和 可靠性的计算机潮络中，网络状态信息的菲精确性是客观存在的， 我们必须为q o s 路由算法引入适当的机制，以使其可以在链路状 态债息不耩确盼清况下，傲出最为有效显可靠豹骆由选择。 1 9 9 7 年，g u e r i n 和o r d a 等人在网络研究最著名的d 师o c o m 国鼯会议上，善次提出了鼹络状态信息不精确的概念和蒸本砑究 模型i l ”。近几年，人们对在不精确网络状态信息下选择合适传输 路径的问题包括：不精确信息产生的原因、对网络性能的影响、 相关算法的比较与讨论等。这些问题将在后续章节中进行详细介 绍和分析。 1 3 基于蚁群算法原理的q o s 路由解决方案 当前i n t c n l e t 中的路由算法主要是保证基本的连通性，路由协 议是蒸于单一度量优化的、单一约束条件下的q o s 路由算法。该 算法可队通过改进的最短路径优先路由算法( 如d 巧妇晌算法或 b e l 】m a n f o r d 算法) 来实现。但是，大多数q o s 路由都存在多个 西南交通大学硕士研究生学位论文第4 页 o o s 约束条件，如：最小带宽、传输延时、延时抖动、丢包率等。 w 撕gz 等【1 3 】证明了如果q o s 路由至少包含两个限制时，它是一个 啪闰题，所以焉户所提出的q o s 要求不一定能褥蜀满足。传统 的路由策略广泛使用域内路由协议r 口、o s p f 等，仅使用静态链 貉度罴参数( 魏路由蹒数、链路代价等) 进行最短选路，藤这都 会导致不均匀的网络流爨分布。当两个节点之间沿着最短路径上 的路由器和链路发生拥豢时，较长路径上的路由嚣和链路区有可 能是空闲的，导致网络的一些地方过载而其他地方的负载却较轻。 近年来，行之有效地解决n p 完全路由方案的搜索算法逐渐受到研 究者的众多关注，如仿生优化算法，其中包括模拟生物界中鑫然 选择和遗传机制的遗传算法、模拟蚂蚁群体觅食行为的蚁群算法 以及模按鸟类群体捕食程为豹微粒群葬法等。 蚁群算法最初由意犬利学者d o r i 9 0m 于1 9 9 1 年首次提出，是 一穗叛近发展起来的、模拟蚂蚁群体觅食行为的傣生优化冀法。 蚂蚁禚寻找食物的运动过程中，能在其经过的路径上分泌一定数 量具有气味的称为信息豢p h e r o m o n e ) 的物质来进簿信息传递，荠 指导自己的运动方向。某一路径上走过的蚂蚁越多，此路径上蚂 蚁留下的信息素轨迹也越多，则后来蚂蚁选择该路径豹概率也越 大，从而更增加了该路径被选择的可能髋。随着时间的搬移，蚂 蚁就会找到由蚁巢到食物源的最优路径。该算法采用了正反馈并 霉亍宦簇化枫剃，其有较强豹每棒性、优良的分布式计算橇利、易 于与葳他方面结合等优点。 本文对蚁群算法进李亍了较深入豹研究，在此蓁础上建悫了适 于q o s 路由优化选择的改进蚁群算法基于混合行为的感知蚁 群算法( h y b r i db e h 删o r b 锯e ds 嫩s a t i o n a la n tc o l o n y 越g o r i 也m ， h b s a c a l 。 该改进算法首先针对网络状态信息不精确的问题，在难要以 信息豢( 孙e r o m o n e ) 强度进行选潞盼基础土，在蚁群算法中期入概 率选路的方法，根据度量参数取值的概攀辅助信息素进行选路， 西南交通大学硕士研究生学位论文第7 页 第二章1 p q o s 路由相关技术 口q o s 的研究目标是有效地提供端到端服务质量的保证和控 制。为了实现具有q o s 保证的传输，实现q o s 控制机制，需要对 q o s 进行描述和定义。本章系统地描述q o s 相关技术，并着重介 绍q o s 路由的目的、当前研究成果和难点。 2 1 q o s 的概念描述和定义 2 1 1q o s 的概念描述 q o s ( q 岫l 畸o fs e r v i c c ) ，即服务质量，在r f c 2 3 8 6 1 1 4 i 中用来 刻画网络在传输数据流时要求满足的一系列服务需求，具体可以 量化为带宽、延迟、延迟抖动、丢包率、吞吐量等性能指标。此 处的服务具体是指数据包f 流) 经过若干网络节点所接受的传输服 务，强调端到端( c n d b 日由或网络边界到边界的整体性。q o s 反 映了网络元素在保证信息传输和满足服务要求方面的能力】。 对( s 宏观的理解为；q o s 是指发送和接收信息的用户之间 以及用户与传输信息的综合服务网络之间关于信息传输的质量约 定i l 。即服务质量包括用户的要求和网络服务提供者的行为两个 方面。其中，用户的要求是指用户在h l t e m e t 上进行多媒体通信所 要求的服务类型以及相应的传输性能和质量等；网络服务提供者 豹行为则指h n 锄c t 针对某一类服务所能提供和达到的性能与质量 【1 n 2 1 2q o s 的定义 当前，不同的国际组织对q o s 有不同的定义，但其目的都是 当前，不同的国际组织对q o s 有不同的定义，但其目的都是 西南交通大学硕士磺究生拳位论文第8 黉 为用户提供更好的服务，同时有效地利用网络资源。 o s l 参考模型中的q o s 定义焖 围辩标准化组织薹s 0 针对o s i 参考模型的七层协议，要求每 层向其上层提供服务，同时也提供相应的服务质量保证。表2 1 是 0 s i 模迎中的q o s 定义。 袭2 1o s i 搂墼中c ! o s 定义 参数 描述 吞吐爨 服务提供者在单位时间内传输的最大字节数。 从发出一个数据传输请求翻敷攒传输完成确谖之间的 传输延迟 时间间隔，这个参数通常包括最犬传输延迟和平均传 输延迟两个值。 错误率服务数据单元( s 转u ) 错特、丢失、羹传的概率。 连接建囊延迟发出“连接请求”到“连接确认”之间的时闻间隔。 在最大可接受的连接建立延迟之内，请求连接不能建 连接建立失败概率 立豹概率。 程一定的传辕延迟、错误率或眷吐量的条件下，可蕊 传输失败概率 察到的性能比指定性能水平差的概率。 在一定豹时间间隔肉，服务提供者要求释放连接，或 重置率 熏鬟连接驰概率。 释放延迟 从“释放请求”发出到“释放确认”之问的时间间隔。 程规定的最大释放延迟内，服务提供者不能释放连接 释放失败概率 豹概率。 在o s l 参考模型中，q o s 支持仅限于在会话层和传输层定义 的统计参数。如果应用层和表示层要控剃q o s ，只能将q o s 参数 相应蟪觚上层获射至i 下层。赛层游议向低层协议发送包含c ! o s 参 数值的服务数据单元，低层协议按高层协议的q o s 要求进行操作。 匿南交通大学矮士磺究生学位论文 第9 贾 ( 1 ) 层按 q o s 要求进行 层协议 l 、 ( - 1 ) 层协议 图2 1o s i 参考模型的参数传递 包禽 吞吐 默f 的q o s 定义 融e m e t 工程任务促进组掰r f ( n l t 锄e te n 甄n e 商n gt a s kf o r c c ) 在王t f c 2 2 1 6 中将q 6 s 定义为翔带宽、分组延迟和丢失率等参数搓 述的关于分组传输的质量。为了进一步描述q o s 控制过程和服务 模型与实现框架，r l 2 2 1 6 还定义了： 雕络元素国e 晰r k 畦懿托f ) ：经铐一个可在猿6 弧毒露络中处理 数据分组的构件，它具有在数据通过时进行q o s 控制的能力，包 括路由器、子网、端主机系统的操作系统等。 漉( n o w ) ：具有稳同q o s 要求和服从同一q o s 控制方法的通 过某个瞬络元素翡分组集会。 服务( s e i c e ) ：描述网络元素的q o s 控制能力，包括规藏和服 务两太部分。 锤为( b e h 秆i o r ) ：与q o s 相关的端到端性能，是应用囊接胃见 的有服务提供的最终结果。 流蠡规范( 仃a 珩c8 p e c 访c a t i o n ，t s p e c ) ：要求服务提供的流量 接述，建一份数据流翘潮络元素撮供豹服务之闻豹合同。 2 2q o s 服务模型 趣f e r t 设计之拐是为了提供醢向菲实时的、单一数据类型的 通信。口协议提供不可靠、无连接的数据报文传递服务。不可靠 是指它不能保证职数据报能成功地到达目的地，无连接是指腰并 露南交通大学硬士研究生学德论文第1 0 页 不能维护任何有关后续数据报的状态信息。为实现端到端的可靠 服务，在零c p 矗p 游议族中，又设诗了t c p 携议实域传输屡豹连接 保证，健始终缺乏必要豹服务质量保证机制。为实现q o s 控制粒 传输管理，匝t f 组织已经提出了多种服务模塑和机制来满足对 0 0 s 的需求，归掇到底有两种思想。迭两种思想被舰f 作为两种 o o s 体系以协议的形式定义下来：一种是综合服务体系结构 涵抽g 阮t e d s e r v i c e s ) ，一释是区分服务体系缩梅私撩f e i l _ 隧e d s e i c e s 、。 2 2 1 综合服务体系结构 综合服务模型以坤协议为其网络层的统一平台，主要出发点 是跨络的延迟霞素，将有q o s 要求斡实时窿用和传统豹8 e s t i 嚣瓜 n 服务集成予h 嘲娃鼹上。在练食服务模型巾，实髓应用看成一个 个漉( f l o w ) 。所谓流是指源予菜一用户的特定行为的一串彼此相关 的臻数据包，这鹱数擐包具有相同的q o s 要求，且可能宥多个接 受者。流的引入使得一个个流可以技理解为条条逻辑上的臻连 接。 综合服务的基本愚想是：首先对网络所有的按享链路进行一 定的资源控翻，同时考虑将网络应用按其q o s 要求分成不淘的种 类，并将它们统一实现在对上层应用的服务接口中。这使褥鼹由 器或者其它网络冗素不必考虑该数据流对应的应用是什么，实现 了对瘦熙鹣透骥瞧。所有豹路宙器在控剩路径上处理每个漆豹信 令消息弗维护每个流的路径状态和资源预窜状态，弗且在数撂路 径上执行及预留的分旋、调度和缓冲区管璩。只要数据流经过的 踌幽嚣都支持这熄服务类别，那么就能为该数据流提供一定的端 到端o o s 保证。 銎前，瑾联定义的服务类魏有可保证服务( g u 巍r 箍t e 酲 s e n r i c e s ) 【1 9 】、负载可控服务( c o 咖1 l e d _ l o a ds e i c e s ) 【2 川和传统的尽 力黼为服务( b e s t - e 细f ts e 赫e e 幻。 西南变遗大学硕士赣究生学僚论文 繁 贾 可保证服务( g u 必m t e e ds e r v i c e s ) 要求网络中各因素保证用户 所要求的最小延迟时间，从而傈诋会话( s e 髂i o n ) 过程中每个分组确 定的延遴赛限固。瑚矗) ，静保证所肖的端到端廷迟均小于菜个固定 值。且保证数据流中合法的数据包不会因为队列的溢出而被丢弃。 这是一种“硬实时”( h a r dr e “* t i m e ) 服务。 负数可控服务f e 姐拄o l l e d - 1 0 勰s e r v i c e s ) 能保证在弱络负载较 重时，提供与负载较轻时相同的q o s ，使用户感到网络是在一种 很轻的负载或具有很大的容量条件下运行，用户感觉不到不可忍 耐的延迟。这是一神“软实时”( s o f t 刚一t i m e ) 服务。 尽力丽为服务圆e s t e 肋r ts e r 以c c s ) 不保证q o s ，当睡络负载较 重的时候，数据包被丢弃。当网络负载较轻的时候，数据包可以 被正确传输。 综含服务依靠资源预磐协议r s v p 提供q o s 携商橇制，逐节 点( h o p j b y h o p ) 地建藏或拆除每个数据流的路径状态和资源预留软 状态( s o 拽s t a t e ) ：依靠接纳控制( a d m i s s i o nc o i l 仃1 ) 1 ) 决定链路或网络 节点是否有足够的资源满足用户的资源预窘请求；依靠传输控剖 ( t r a 盛cc o f 心0 1 ) 将m 分组分裘成不褥缒传输流，并根据每个流的状 态对分组的传输实施q o s 路由、传输调度等控制。 综会服务模型的个重要特点是资源预整协议郦v 矾，r s v p 不是路峦携议，僵宦与路由协议绩舍使焉，圊时支持单播和组播。 r s v p 运行在瑾层之上，和t c p 、u d p 处在同一层次，也可在u d p 协议上实现。它采用单方向预留方式，即由数据流的接收端向数 蕹源沿路径进行预留，这是一个由下游淘上游方向迸行预留的单 向预翳过程。r s v p 镪括两类最基本的控制分缀：p 蛆h ( 控制) 类分 组和r 殷s v ( 预留) 类分组。p 姗类分组由数据源端发出，i 嘎s v 则 由数据接收端作为对p a t h 路径中各网络元素的资源要求沿p a 豫 分缀设置的路径返窝发出。如果接收端不需簧资源预整，剥不返 回r e s v 分组，而直接沿相应的路径接收来自源端的信息。 r s 、巾协议通过相应的p a l 王王类分组和r e s v 分组，沿糟数据 西南交通大学硕士研究生学位论文 第1 3 页 图2 - 2 区分服务模型工作原理 区分服务模型有以下几个关键特征： 1 ) 增强边界功能，箍优内部功能 区分服务模黧充分弱用了毡t e 撼。t 中的蠡渗域慝惩，将溉畦 划分为多个d s 域( d i 自f s e r vd o m a i n ) 。余网的复杂控制就被分为域 内的控制和域间的控制。将分组分类工作移到网络的边界上，由 边界路由器对分组做适当的分类和标识，内部路由器仅需根据其 标识做简单的转发操作即可。而且边界路由器的标识工作比较简 单，只需在球头部的t o s 字段作标识即可。由于内部路由器的处 理简单，因此可提供高速的转发服务。 2 ) 较程的送分粒度 区分服务模型的区分不是按流采进行，雨是根据聚集流来分 类，而且定义类的数目比较小。这样一来，无论流的数目如何增 加， x 西南交通大学硕士研究擞学位论文 第15 贺 图2 3 网络加权图横型 2 ，9 0 ，3 0 ) 每一个节点、每一条链路都有用q o s 度量表示的状态，节点 状态可以折算到与节点相连豹链路状态中，故这里将节点的度曩 僮忽硌不记。艇表示芷实数集，置表示舔负实数集。对手任一链 路8 e ，定义3 释度量，分剐为代价函数o 玎e ) ：e 一也、剩余 带宽函数6 口n 咖 d 龋( 0 ：e _ + r + 、链路时延函数撕( 0 ：e r 。 链路代价由传输数据包消耗的链路资源决定；链路中的剩余带宽 为链路带宽涞被占用的带宽；链路的时蜒为数据包在链路中的传 播时延。 2 。3 。2q o s 潞由度量参数的选择 q o s 路由中算法复杂度关系到q o s 路由算法的可实现性，度 量参数选择崽接关系到算法复杂度问题。合理解决多参数问鼷， 在设计低复杂度的q o s 路由算法中占有薰要地位。目前o o s 路由 算法涉及的度量参数包括：带宽( 胁毋w f 出 ) 、时延似矗功、时延抖 动( 如弛埘蹴r ) 、丢包率咖如l 觚) 、代价涵数( 铆0 和跳数( 印) 等。 对于加权国g 中的一条路径p = ( v l ，k ) ，j s 撑，餍 西南交通大学硕士研究璧学位论文第17 页 辗髑条件罨我籍径 常困难，在多项式对鬻8 o 劫癌曩l t i m e ) 内搬 本找不到一种肖效的算法进行路由选择，w 址gz c r d w c m f j 等人 已经证明使算法同时满足多个度量是非确定多项式完全问题 ( n o n d e t e n n i i l i 8 t i cp o l y l l o i i l i a lc o i n p l e t e ) n p c 问题1 1 3 l ，即在两个或多 个加性和乘性度量，以及加性和乘性度罴的任意组合的约束条件 下寻找路径是一个n _ p 完全问题。但带宽是凸性度量参数，所以唯 一可行的一种缀合是将带宽和加性或乘瞧度量参数之一组合在一 起以避免在路由计算中造成套l p 完全阔蘸。逶常熬徽法是使焉繁宽 和时延作为度璧参数。 2 3 3q o s 路由算法 根据网络状态信息的保存方式和路由搜寻方式的不同，路由 算法可分为两种：源路由算法和分布式路由算法。 1 1 源鼹由 每个节点保存全局的网络状态信惠，包括网络拓扑结构信息 和每条链路的状态信息。收到路由请求盾，根据此全局信息，源 节点在本地计算出一条合适的路由。然厢，在选择的路由上传送 一个控制包，通知路由上的每个节点，说明其前继和后继。中间 节点收到请求包厢，就按照控制包的路径刿袭项将包向目的转发。 每个节点豹信息更新由链路信息协议完成。因为每令黯由请求 都被集中式撼藕独计算，所毅源路由其鸯很好豹灵活性：源节藿 x 西南交通大学硕士研究生学位论文 第2 1 页 第三章蚁群算法 自然界中有许多自适应优化现象，生物体和自然生态系统可 通过自身的演化使许多在人类看来高度复杂的优化问题得到完美 的解决。近些年来，一些与经典的数学规划原理截然不同的、试 图通过模拟自然生态系统机制以求解复杂优化问题的仿生优化算 法相继出现f 如遗传算法、蚁群算法、微粒群算法、人工免疫算法、 人工鱼群算法、混合蛙跳算法等) ，为那些传统最优化技术难以处 理的组合优化问题提供了切实可行的解决方案。一些仿生优化算 法已在经典卜i p c 问题的求解和实际应用中显示出强大的生命力 和进一步发展的潜力【2 5 】。 3 1 蚁群算法的原理和模型 3 1 1 蚁群算法的原理 蚂蚁是一种社会性昆虫，它们的个体结构和行为很简单，其 中大部分是传递信息，但由这些简单的个体所构成的整个群体一 一蚂蚁群体，却表现出高度结构化的社会组织，在很多情况下能 够完成远远超出蚂蚁个体能力的复杂行为，如寻觅食物、分配任 务、建造墓地等，这种能力来源于蚁群的协作能力，其中蚁群觅 食行为是引起关注研究的一个重要行为。 仿生学家经过大量细致的观察研究发现，蚂蚁具有找到蚁巢 与食物之间的最短路径的能力。这种能力是靠其在所经过的路径 上释放出一种挥发性分泌物称为信息素( p h e r o m o n e ) 的物质来实现 的。蚂蚁运动时，在所经过的路径上释放出一定数量的信息素， 后来的蚂蚁选择该路径的概率与当时这条路径上信息素的强度成 西南交通大学硕士研究生学位论文 第2 3 页 泌的，菰置d 路径上的倍患素强度为3 0 ，这些信息素是来自子从嚣 往d 方向的1 5 只蚂蚁和从e 出发已经从d 到达四的1 5 只蚂蚁的 分泌物之和，鳃图3 1 c ) 所示。 因此，选择哪条路径的可能性就发生了偏斜，从而往d 方向 去的蚂蚁将是徒c 方淘豹蚂蚁的薅倍，分别为2 0 只和1 0 只。同 样的道理，从e 出发到达d 点的3 0 只蚂蚁也会进行同样的行为。 随著时间的推移，蚂蚁将会以越来越大的概率选择路径嚣z 溜， 最终所有的蚂蚁都选箨聂短鲶路径一最d e f 。这种集体行为被称为 “集群智能( s w a 珊i n t d l i g c e ) ”。 棱攥这耱“集群鬻能”，意大荦j 学者d 砸g om 等旧于1 9 9 1 年 最早系统地提出了蚁群算法( a n tc o l o n yo p t i n l i z a 蛀o n ，a c o ) ，并 用a c o 解决了一系列组合优化闷题。最初雳于解决旅行商问题 ( t ra _ v e l i n gs a l e s m 孤p r o b l 锄，t s p ) 嗍，现在已经陆续渗透到其他 领域中，如图彤着色问题( g r a p h c o l 积n g p 曲l e m ，g 1 0 p ) 、指派问 题( q i 城d r a t i c 触s i 驴础殂tp r o b l e n l ，q a p ) 、集台覆盖问题( s e t c o v 曲gp m b l e m ，s c p ) 以及本论文将要讨论的通信网络中的路由 同题鞫负载平衡闯题等等。 在蚁群算法中，提出了人工蚂蚁的概念，区别于自然界中的 真实蚂蚁。一方露入王蚂蚁是真实蚂蚁行为特镊豹一秘热象，将 蚁群觅食行为中最关键的部分赋予人工蚂蚁：另方面，为使蚁 群算法更有效，人工蚂蚁具备真实蚂蚁所不具有的一些特性。 一人工蚂蚁与真实蚂蚁的相同点 1 ) 都是一群相互协作的个体 入工蚂蚁和囊实蚂蚁可以通过相互的协作我出闯遂较优的解 决方案，它们每只蚂蚁都能够建立一个解决方案，但是较优的解 决方案是整个蚁嚣协佟琵结果。 2 ) 都要完成共同的任务 人工蚂蚁秘真实蚂蚁都要完成一个共同的任务，郢寻找到一 条从源节点( 蚁巢) 到目的节点( 食物源) 的最短路径。它们不能跳跃， 西南交通大学硕士研究生举位论文 第2 5 页 3 1 2 传统蚁群算法的模叠 蚊群算法豹第一个虚焉是旅行商闷怒往s p ) ，旅行商阀题就是 指按照一定的顺序访问每一个城市，使得每个城市只能被访问一 次，箍使花费的代价最小。旅行商问题楚一个著名钧、为大家熟 悉易懂的n p 也a r d 问题【4 。本节以求解平面上n 个城市的t s p 问 题为例来说明传统蚁群系统模烈，在后续章节中将会看到改进的 蚁群系统模型用来解决q o s 路由优纯问题。 用g = ( 矿，e ) 表示加权图，其中矿= h ，v 2 ，h 为图的节点 集，嚣= 岛，吃，巳 为图的边熬，d 表示边疆离或费用。把推销 员的住地和他所要去的城市用节点y 袭示，城市之间的道路看成 边冒，边上豹粳等于对应道路的长度d ，朝对于城索k 、v ，y ， 从h 到v 7 的距离记为如足，这里假设吒= 以，即考虑对称t s p 阔题。这样就得到一个加权豳，于是旅行商问题就是在赋权图上 找一个权最小的h a 戚l t o n 圈【轺。 为模拟真实蚂蚁的行为。首先引入如下记号： 略( f ，歹= l ，2 ， ) 为城市f 和城市，之阎的距离： 乓( f ) 为f 时刻位予城市f 的蚂蚁的个数，m = 觑( f ) ； f 越 勺( f ) 为f 时刻在 路径上积累的信息素强度； 璐为房发函数，可以理解为路径幢力薛能见度( v i s i k l i 劝或 由城市f 转移到城市_ ，的启发信息，该启发信息由要解决的问题给 】 出，在t s p 问题中一般取( # ) 2 7 。显然，对蚂蚁而畜，吒越 ”口 小，o ) 到越大，8 ) 也就越大。该癌发函数表示蚂蚁从节点( 城 市) f 转移到节点( 城市) _ ，的期黛程度。 菇( f ) 表示在f 时亥蚂蚁露由城市i 转移到城市，的概率， 霹南交通大学硕研究生学位论文 第2 8 页 商淘憨懿实骏，比较了上述三个模型，冤数攥表3 - l ，可觅a 珏扛c y c l e 模型在求解t s p 时性能较好。 表3 1 加m c y c l e 、a r l l - q u a r n i t y 和a n t d e 雌埘的比较”2 】 名称参数设置 平均德 1 ) l 嗽参靠 一 壮 一 匿南交通大学礤磷究生学位论文 第5 0 贾 或= 气( r ) 一o ) ( 喀) 一o ) ) c = 1 m 1 ( 4 2 6 ) 糟等 足 ，= a 稻m a x ( ) ，g 口如w 嚷 ( 4 - 2 7 ) 式中，磋表示蚂蚁七在潜意识作闵下路径，歹) 对其的瑷弓i 程度； 群表承路径( f ，) 对除l 】 外的其他蚂蚁的吸引程度。笤表示了路径 ( f ，) 对蚂蚁七和其他蚂蚁吸引程度的比例； 谚表示蚂蚁七在路 径( j ，) 上走过次数的倒数，m 为迭代次数。 当路径上信息索强度增蠢在c s t 之下时，蚂蚁感知不到该路 径上信息素强度的变化，按照自己的潜意识和经验作用选路。因 为算法要迭代m 次，如果蚂蚁j 淼某一条路径上走过的次数越多， 它对这条路径越熟悉，选择该路径豹概率就越大；若一条路径搜 其他蚂蚁走过的次数较多，则蚂蚁i 受到潜意识作用对该路径就越 排斥，选择该路径的概率就小。这种机制有效地防止了蚂蚁一味 相信茭他蚂蚁两造成盲从，保持了解空阉，降低了产生蜀郝最垅 解和过晕收敛的可熊。 当路径上信息素强度增量在c s t 之上时，蚂蚁则“随大流” 趋向予所有蚂蚁信息素强度较大的路径，这样可以快速收缩解空 阕，加快算法魏收敛速度，到达全局最优解。 但是这样会造成另外一个问题，也就是上面提到的感知原理 的缺陷：当路径上信息索强度增罴在c s t 之下时，由于信息素强 度较大的路径基本郝藏为“主流”路径，所以滏意识路径般都 信息素强度较小。一旦蚂蚁选定条路径作为潜意识路径，它所 走的路径不是这条潜意识路径，就是“随大流”的信息累强度较 大的路径，这将导致处予信息素强度中间值的路径被选概率大大 西南交通大学硕士研究生学位论文 第5 1 页 降低，胰露不能保证选鼹结果的优纯，弗使褥最优解路径利焉率 过高，不能很好地分流负载。 为了解决这令闻题，本文弓i 入了拍若参数表示蚂蚁盘在籍径 ( f ，- ，) 上走过次数的倒数。当路径上信息素强度增曩在c s t 之下时， 如果奴，) 作为潜意识路径走过的次数逐渐增多，即喏值逐渐变 小，根据公式( 4 _ 2 5 ) ，这时的值也随之越来越小，而参数雕能 使0 ，- ，) 路径选择概率薪的值保持在一定范围内小幅度振动，不会 无限制迪小下去。当露小于其他路径选择概率时，簧o 选择小硷。值 较大的路径，即让蚂蚁詹选择其他“非主流”的、走过次数相对较 少的“孛翔镶”路径作为潜意识鼹径，让蚂蚁能在一定豹隈剩莲 围内跳出自己的小圈予，选择一些更优解路径，这样兼顾了平衡 网络霹利用资源的原刚，这就是蒸于感知方式豹第4 类蚂蚁行为。 这4 类行为是基于蚂蚁不间的状态转移规则而进行分类的。 h b s a c a 算法设计对所有行为采用相同的信息紊局部更新规则和 全局更新觌刘。 ( 2 ) 信息素局部更新规则 当瓣蚁l j 经过链路( i ，d 对，链路g d 上的信惠素强度进行如 下更新： 砷+ 1 ) ：p 小咏o “咏。+ 蒜若 舶( 4 - 2 8 ) ( 1 一p ) 。( f ) 否舞 a 勺( f ) = 露9 )p 2 9 ) h l 式中，j d 表示信息素挥发系数，1 一p 则表示信息索残留因子， p 【o ，1 ) ；勺9 ) 表示在蚂蚁七在逶过链臻( f ，力期阗，链路( f ，d 上 信息索的变化擞i 蜘( f ) 为链路( f ，) 的传输时延；根据文献【3 0 】 进行改进，c 为常数，控制时延参数对信息豢更瑟魏影响稷发，在 实际运用中可根据具体情况进行调节。 西南交通大学硕士研究生学位论文第5 2 页 露采用第三章提到豹a n l * c 接勰d t “3 5 ) 模鳌来求解： 哝f ) - 净菪第职蚂蚁极辄“之间经过( f ，力( 3 1 5 ) l o ， 否则 式中，嘞在网络路由闷遂中都为路径( f ，歹) 豹代馀c 。s f ( f 力；为了 改善算法性能，常数项的信息索强度q 改进为时变函数q ( f ) ，即 瑚归警，若第职蚂蚁在f 和f “之间经过( f d ( 4 _ 3 。) | o ，否则 q l ， ) = g ， l q 3 ， o j i乃f 图4 一l 时变函数q 国 ( 3 ) 信息素全局更新规则 当蚂蚁从源节点j 至4 达目的节点d 对，假设新经过的路径为 p ( s ，d ) ，则对p 上所有链路的信息素进行如下更新： 砷+ 1 ) ：卜办删+ 竺絮堕，瓠加嘏彩) i ( 1 一p ) “如o )否则 式中，口h 扔d m 喀是瓶颈剩余带宽；根据文献 3 0 】进行改进，d 为常 数，控制剩余带宽参数对信息索更新的影响程度。 d 0 乏 嘲即嘲 若蒋若 西南交通大学硕士研究生学位论文 第53页 ( 4 ) 限制函数只的定义 只= 互+ 五+ 只e 吖咖f ( f 4 l(1j扣p(j一)耻已邑删丁l i 。，坤户( ，d ) 只= 一( 口月曲咒以) 。( 4 3 3 ) ( 4 3 4 ) ( 4 3 5 ) (436)式中，e 表示费用限制，e 表示时延限制，只表示剩余带宽限制； 口、b 、c 分别为费用、时延和剩余带宽影响系数，可调节费用限制 和时延限制的影响比例。限制函数值越小的路径，相比其他路径 综合参数条件越优。根据实际需要，限制函数将选出的多条符合 q o s 要求的路径进行再次优化选择，通过调整影响系数，以达到 q o s 对路径费用、时延或是剩余带宽的偏向要求，使选出的路径 具有很好的灵活性和适应性。 对于文献【5 3 】提出的4 类行为，船s a c a 算法保留了行为l 和行为2 ，对行为3 和行为4 进行了重新定义，对解决过早收敛问 题和优化全局资源提出了若干机制，为不精确信息条件下的o o s 路由优化问题提供了良好的解决方案。 4 3 4l m s a c a 算法的实现步骤 算法的具体实现步骤如下： ( 1 ) 初始化：建立网络拓扑结构，确定源节点j 和目的节点d ， 网络中的每条链路o ，- ，) 的信息素强度初值设为b ( 0 ) = c ， 勺= 0 ，并初始化参数吒：吩：毛：、p 、q 、c 。选取m 只蚂蚁， 设置时间域口n 肋n 吒，用来记录每只蚂蚁从源节点s 到目的节点d 经过的时延；为每只蚂蚁设置禁忌表纽6 蚝，用来记录已经走过的 话南交通大学硕士研究生学位论文 第5 4 页 节点，s 为蚂蚁允诲的最大雾l 数；并设雯瓶颈带宽域积持积或，震 来记录每只蚂蚁走完一次后路径上的瓶颈带宽。 ( 2 ) 给搬只蚂蚁分配行动，其中i i i 蒜只蚂蚁撬行行为 l ，i ：三孓i 只蚂蚁执行行为2 ，i 丧只蚂蚁执行行为1 ，i i 萧只蚂蚁执行行为2 ，i 焉蒜只蚂蚁执行行为 3 ，i t 只蚂蚁执行行为4 。 五十十弓中0 ( 3 ) 将删只蚂蚁放到源节点s 上，并将源节点的索引添加到该 蚂蚁的禁忌表中。从源节点出发，在第一个时间单位，每只蚂蚁 从候选子集d 渤w 翻。中按自己的行为转移援刚选撵下一个节点 ( 4 ) 假设第七只蚂蚁到达节点f ，若l 一目的节点d ，则顺序提 取第七只蚂蚁豹禁忌表纪妇。中的羼有繁点，得到从源节点s 到目 的节点d 走过的路径，根据信息素全局更新规则( 4 3 2 ) 更新每条链 路豹信患素强度。著l 譬匿的节点磊则继续根据自己的行为转移 规则选择下一个节点，。 ( 5 ) 若节点，纰6 地，则蚂蚁j 回退到前一节点f ，同时按照公 式( 4 2 8 ) 更新路径( f ，d 上的信息素强度，并晟转回到( 4 ) ；若 ，盛融6 虬，进行下一步。 ( 6 ) 若豫( 矗积幽，豇触( f ，歹) 缉) 矗，帮不满足带宽概率，刘蚂 蚁七回退到前一节点f ，同时按照公式( 4 - 2 8 ) 更新路径( f ，力上的信 息素强度，并且转回到( 4 ) ；羞满足，壤玉口n 幽砌强g ，d 与觥路口耐。 进行比较，其中较小者赋给鲫始u n 血，以找到路径中的瓶颈带宽。 蚂蚁意从节点f 转移到节点 记录链踌( f ，d 豹时延妇奶谯歹) ，判 断蹙否满足瑚( ( 如 秒0 ，_ ，) + d h 砌”) 4 ) 厶，若满足， 册材f 州；如z 缈( f ，_ ，) + 口舢l 棚咚，将节点j 加入到融6 中，并按照 公式( 4 2 8 ) 对链路( f ，d 信息素遴行局部更新；若不满足时殛概率， 蚂蚁k 死亡，按照公式( 4 2 8 ) 对链路( f ，) 信息素进行局部更新。 ( 7 ) 对掰蠢热只蚂蚁进行第( 4 ) 步，壹到研哭蚂蚁都完成了第( 步。 西南交通大学硕士研究生学使论文 第5 5 炎 ( 8 ) 壤据限制函数选择满足全局资源优化豹、满足q ! o s 要求 的最优路径。 ( 9 ) 若垃s 札一，重复( 3 h 8 ) ，魑+ + ；否则，羧出符合q o s 要求的最优路径，程序终虎。 4 3 5 聃s a c a 算法程序流程圈 算法程序流程图4 - 2 如下： 褥南交通大学硕士研究生学位论文第弱页 图4 2h b s a c a 算法程序流程圈 嚣寨交遴大掌硕士礤舞生学位论文第5 7 瑟 第五章蚁群改进算法的仿真分析 5 。l 仿真网络模型的建立 为诞明h b s a c a 算法解决障络q o s 路由阀遂的有效性、优化 性和健妆性，本章对算法进行仿真实验。网络拓扑结构图和链路 参数如图5 1 所示： 图5 1 网络掘挣结构图 ，l l o ，2 0 ) 1 0 5 ，2 在圈5 - 1 所示网络拓扑图中，含有t 5 个节点，2 6 条链路。每 个节点、簿条链路都有用q o s 度擞表示的状态，节点状态可以折 算到与节点相连豹链鼹状态中，故这里将节点的度量篷忽略不记。 图中每条链路用三元组( s 施h 幽m ，撕) 表示，其中的元素分 别表示链路的代价、剩余带宽和链路时延。 试验中豹仿真参数设曼如下：节点l 为源节点，节点1 2 为霹 嚣南交逶大学硕士研究生学位论文 第s 8 贾 的节点；蚂蚁数目m = 3 0 ，允许最大跳数j = 6 ；信息紊强度初值 b ( o ) = 2 0 ，各路径踌由选择初始概率都为o ，信息素挥发系数 p ：o 1 ；混合行为的比例为：屯：毛：= l ：2 ：3 ：4 ；w 曲e r 系数 k ：o 2 ，信息素局部更新规则( 如2 8 ) 中调整时延参数影响的常数 c ：2 0 ，信息素全局更新规则( 4 3 2 ) 中调整剩余带宽参数影响的常 数d = 4 0 ；信患素强度眩变丞数q ( o 如下： f 1 ， 著t 4 0 q ( f ) = 2 ， 蒋4 0 f a u g t l s t1 9 9 9 c 绷e y jw ，k i i nhs c a m p a r i s o no f b 诚酹a l l o c a f i o ns c h e m e s 遍趟睫喱刚蛐嚣：c 嘲p l g es 颤出孓辨峨毫ls h a 豳g ，戚 d c d i c a t e d a l l o c a t i o n f a 】i n t e m a t i o n a l c o n f e r e l l c e o n c o m m u m c a t i o n s v o l2 ，m a y1 9 9 4 l i 曲e h e r rj ，a 嫩s 缸n r a t ca l l o c a t 妇la n db u f 断m a n a g e m e n t f o rd 主妊h 吼m 越e ds e i c e s 司c o m p 毗e r n e 锨的r k s ，2 0 0 2 ，4 0 ( 1 ) 积mk a i ，勾m a n gy a n ，n i o 垃sy 抽i l i s a c l l i e v i i l ge d t o e n d d e l a yb 吣d sb ye d fs c h e d l 王l i n g 稍t l l o u t 仃啦cs h a p i n g 【a 】 磁l l 难球f o c o m2 l r n 斑，b r a j a 舒巾a l a n 孤dh s 缸m i c k ，a 矗a m e w o r k 蚤河 q o s - b 鹊e dr o u t i n gi l lm eh 黜e t ，r f c2 3 8 6 ，i e t f ，a u g u s t 1 9 9 8 陇 嘲 嗍 嘲 网 忉 西南交通大学硕士研究生学位论文第6 8 页 【“】y u a nx ，髓髓gw ，d 咄s l l i l i n g a c o n l p a r a d v es t u d yo fq o sr o u t i n g sc妇nest h a tt o l e r a t ei i r i p r e c i s e statei i l f o r m a t i 【a 】1 l “ intema垃onalc o 打e n c eo nc o m p u t e r c o m m n n i c a t i o 啮鲫dnetworks 2002 1 2 】r g u e r i l l ，a c l r ( hq o s - b a s e dr o u t h 唱i n n咖orksw i 也h l a c c l l r a t ei n f o m a t i o n ：也e orya n da l g o r i t m s a h lp r o c e e d j g so f 恤m 髓肼o c o m 9 7 ，1 9 9 7 1 3 】w 撕gz ，c r o w c r o f i ，q l l a l 时o fs e r v i c er o l n i n g for辄ppomng n t n i n l e d 谊a p p l i c a t j o n s 阢e ej o 衄1 a lo ns e k t e da