（计算机软件与理论专业论文）基于蚁群算法的网络路由算法.pdf

山东大学硕士学位论文 摘要 作为人工智能一个新的分支，蚁群算法以其较强的鲁棒性、优良的分布式计 算能力、易于与其他方法相结合的优点受到了越来越广泛的关注；应用涉及到从 一维静态问题到多维动态问题。作为多维动态问题的特例网络路由作为互联网的 核心，一直受到研究领域的关注：网络路由是指引信息从源节点到目的节点传输 所必需的活动，这个问题既重要，又难以解决。w a n gz t 2 3 】等证明当网络路由中 包含两个以上的限制是，它是一个n p c c 问题。传统的方法很难有效地解决n p - c 问题，应用蚁群算法在解决上述问题时可以有效地改善网络路由的质量。用蚁群 算法来进行网络路有选择策略进行研究，正是本文的主要方向。由于网络的这些 特性，以及真实网络的物理分布性，使得a c o 算法在这方面上具有特别的优势。 本文首先介绍了蚁群算法的起源和发展、网络路由的相关知识以及设计时的 重点和难点；其次根据网络路由的特点，结合蚁群算法对网络路由选择作了一般 意义上的优化选择( a c r ) ，并在仿真平台上进行了相关的数据分析和与其它算 法进行了比较；接下来我们深入探讨了在面对更加具体和实用的路有策略一q o s 路由和拥塞路由时如何应用蚁群算法进行优化，使其具有较强的鲁棒性和较高的 寻址效率。 本文改进了基于蚁群算法路由选择问题。完成的主要工作包括：通过正向挥 发一反向积累的机制的蚁群算法的信息素更细策略，快了收敛速度，增强了蚂蚁 探索新路径的能力；同时提出了对于网络路由中路由节点要求的r s v p 的不对称 性提出了相应的解决方案，使其适应q o s 路由；面对拥塞时为了提高了蚂蚁探索 新路径的启发策略，应用正态函数进行信息素的挥发策略，确保可以活化蚂蚁探 索路径的能力，从而有效地缓解网络拥塞和降低可能出现的拥塞并可以很大程度 上的缓解拥塞带来的网络服务质量的降低。实验结果表明以上所涉及的系统改进 具有良好的实用性、有效性和鲁棒性。 当然目前所设计的系统还有一些需要改进的地方，如加快蚂蚁收敛速度，解 决无效蚂蚁存活问题，并行化问题，多路径优化选择方面的问题等。 关键词：a c o ；网络路由；q o s ；a c r ； 山东大学硕士学位论文 a b s t r a c t a sn e w r e s e a r c h i n gb r a n c ho fa r t i f i c i a li n t e l l i g e n c e ，a n tc o l o n ya l g o r i t h m ( a c o ) g e t sm o r ea n dm o r ea t t e n t i o nf r o mp e o p l e t h er e a s o ns o u n d sf r o mt h a ti th a sb e a e r r o b u s t n e s s ；m o r ee x c e l l e n c ed i s t r i b u t e dc o m p u t i n gp o w e r ；e a s i e rc o m b i n e dw i t h o t h e r sm e t h o d s a n dt h er e s e a r c hf o ri th a sa p p l i e dt om a n yf i e l d s ，i n v o l v e d 、) v i 吐lt h e p r o b l e md e v e l o p e df r o mo n e - d i m e n s i o n a l s t a t i cp r o b l e mt om u l t i d i m e n s i o n a l d y n a m i cp r o b l e m s o m ea p p l i c a t i o n sc a l lg e tm o r ee f f i c i e n ta n dr o b u s tw i t hu s i n g a c o ，w h i c hi n v o l v ew i t hn p cp r o b l e m t h en e t w o r kr o u t i n ga st h es c o r eo ft h e i n t e m e td e s e r v e sm o r ea t t e n t i o n st h a no t h e r s ；w h i c hi sn o to n l yi m p o r t a n tb u ta l s o c o m p l i c a t e d ；t h ei m p o r t a n tc o m e sf r o mt h ee f f e c t st ot h et o t a ln e t w o r k ；a n dt h e c o m p l i c a t e dc o m e sf r o mt h eo b s t i n a t ec h a r a c t e r ss u c ha sl o a d i n go ff l o w i n ga n dt h e n e t w o r kt o p o l o g yw h i c hh a v eo b v i o u sr a n d o ma n dc h a n g ew i t ht i m ea n dt i m e t h e g o a lo fn e t w o r ki st of i n dap a t hf r o mt h es e r v e rt ot h ec l i e n t ；w h i c hw a sc o n f i n e db y t h eb a n d w i d t h ，d e l a ya n df e e a n dw a n gze t ca n dt e s t i f yt h a tw h e nt h e r ea r et w oo r m o r ec o n f i n e m e n t si nt h en e t w o r kr o u t i n g ，i tm e a n sw ea r er e f e r r i n gt ot h ep r o b l e mo f n p c b u tt h em e t h o do ft r a d i t i o nw e a k e n so nr e s o l v et h ep r o b l e m a n dw ec a nu s e t h ea c ot or e s o l v et h ep r o b l e m se a s i e r ，i m p r o v et h ee f f i c i e n to fn e t w o r kr o u t i n g s o t h em a i nd i r e c t i o no fm yr e s e a r c hi st h en e t w o r kr o u t i n g 诹t 1 1a c o f o r e s e e i n gt h e c h a r a c t e ro ft h en e t w o r ka n dt h ep h y s i c a ld i s t r i b u t i o no ft h en e t w o r km a k et h ea c o o w na d v a n t a g eo nt h es i d e i nf a c tt h ea c ov e r yf i t st h ep r o b l e ms u c ha st o p o l o g y a n df l o w i n gw h i c hi st m c e r t a i na n dd i s t r i b u t e d , c a nr e s o l v em u l t i - g o r e da n d c o n s t r a i n tp r o b l e ma n ds oo n i nt h i st h e s i s ，w ei n t r o d u c et h eo r i g i na n dd e v e l o p m e n to fs o c c e rr o b o t ，r e l a t i v e k n o w l e d g e o fm i d d l es i z es o c c e rr o b o tc o m p e t i t i o n ，t h ei m p o r t a n ta n dd i f f i c u l ti s s u e s o nd e s i g n i n gv i s i o ns y s t e m s a f t e rag e n e r a ld e s c r i p t i o no fr o b o tv i s i o ns y s t e m s ，s o m e t e c h n o l o g i e sa b o u tr o b o tv i s i o ns y s t e m sa r ed i s c u s s e di n c l u d i n gi m a g ep r e p r o c e s s i n g ， c o l o ri m a g e s e g m e n t a t i o n ，i m a g er e p r e s e n t a t i o na n do b je c tr e c o g n i t i o na n ds oo n t h i sa r t i c l ew i l li n t r o d u c et h es o u r c ea n dd e v e l o p m e n to fa c o ，t h ek n o w l e d g e 山东大学硕士学位论文 a b o u tn e t w o r kr o u t i n ga n d0 1 1 1 f o c u sa n dd i f f i c u l t yw h e nw ed e s i g nt h es y s t e m a c c o r d i n gt h ec h a r a c t e ro fn e t w o r k ，w ei m p r o v et h eq u a l i t yo fs e r v i c e ( q o s ) r o u t i n g a n dc o n g e s t i o nr o u t i n g ，w h i c hw i l lm a k ei to w nb e t t e rr o b u s t n e s sa n de f f i c i e n t a d d r e s s i n g t h ea r t i c l ei m p r o v e st h ea l g o r i t h mo fq o sr o u t i n ga n dc o n g e s t i o nr o u t i n g f o ra c o o u rm a i nj o bi n c l u d e st h ef o l l o w i n g ：c h o o s i n gm o r ee f f i c i e n tp h e r o m o n e u p d a t e ，a c c e l e r a t i n gt h es p e e do fc o n v e r g e n c e ，m a k et h ef o u n dp a t hm o r es u i t a b l et o t h eq u a l i t yo fd e m a n d ；p r o p o s i n gt h er e s o l u t i o nf o rt h ea s y m m e t r i co fn e t w o r kr s v p , r e s e r v i n gc a p a b i l i t yo ft h ef i n d i n gt h en e wp a t h ，s od e c l i n i n gt h ep o s s i b i l i t yo f c o n g e s t i o na n di m p r o v et h eq u a l i t yo fn e t w o r ki nt h eb a de n v i r o n m e n t t h er e s u l to f e x p e r i m e n t ss u p p o r t st h ea r g u m e n t s ，i tr e a l l yi m p r o v er o b u s t , v a l i da n dr e a l - t i m e t h e r ea r es t i l ls o m ed r a w b a c k so ft h ea l g o r i t h m t h ec a p a b i l i t yt o c o n v e r g e n c e s h o u l db ei m p r o v e d , p r o b l e mo fd e a da n t , p a r a l l e l i z a t i o ns e a r c h ，m u l t i - g o a l o p t i m i z a t i o np a t hs h o u l db es o l v e k e y w o r d s ：a c o ，n e t w o r kr o u t i n g ，q o s ，a c r i i i 原创性声明和关于学位论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：童敝 日 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：奄军参上导师签名： 山东大学硕士学位论文 1 1 研究的背景和意义 第1 章绪论 从上世纪6 0 年代的a r p n e t 开始试验并投入使用以来，网络就以其其它工 具无法比拟的优越性迅速地发展起来：近年来，网络用户的数量更迅速增长，据 统计到2 0 0 8 年1 月，全球1 5 岁及以上使用互联网的人数达到了1 7 4 7 亿，同比 增长1 0 ，导致网络中通信流急量的剧增加。而i n t e m e t 已由以往的单一数据传 送网发展成传送数据、语音、视频等多媒体信息的宽带综合业务网。因此基于 i n t e m e t 的数据流剧增造成网络性能的下降，目前的网络路由算法已经越来越不 适应现如今的网络需求，导致越来越严重的网络拥塞问题的出现。 路由质量的优劣对网络的总体性能有很大的影响，但是由于网络固有的特 性，例如流量负载和网络拓扑，这些特性都有明显的随机性，而且会随时间的发 生变化使问题变得异常复杂。我们所求的最终目的就是发现一条从服务端到客户 端的一条最优路径使其满足带宽、时延和费用等的限制。a c o ( a n tc o l o n y o p t i m i z a t i o n ) 的处理泛型和问题所固有的( 拓扑和流量模式上的) 分布性与不确 定十分匹配，而且可以以灵活的解决多目标任务和带约束的问题特别适合与路由 问题相结合。 计算机通信网络固有的特性( 随机性，多变性，不可预测性，突发性) 容易 造成延迟、延迟抖动和丢包等服务质量( q o s ：q u a l i t yo fs e r v i c e ) 性能指标下降， 其中带宽、缓存、吞吐量等网络资源利用率的关键因素，因此有效解决路由问题 对于提高网络性能具有重要意义。网络产生拥塞的根本原因是用户提供给网络的 负载大于当时所需的网络资源容量和处理能力，在i n t e m e t 中，局部存储空间不 足、通信信道带宽容量不足、处理机处理能力较弱等都是产生拥塞现象的直接原 因，但是无论增加缓存容量或是提高处理器及链路的速度都不能从根本上解决问 题，因为网络的拥塞的产生只是出现在网络的局部区域或者是某一个节点的某个 端口，而不是整个区域的拥塞( 如果出现这种情况，升级硬件设备成为必然的选 择) ：因此优良的路由选择策略解决当前问题的关键；相反，某些情况下盲目升 级硬件甚至可能会进一步加剧拥塞网络中发生拥塞后如果不加以控制，往往会导 致恶性循环，这时如果路由器没有空余的缓存空间，它就必须丢掉新到的数据包， 山东大学硕士学位论文 当数据包丢弃时，发送方会因为超时而重传此包，由于发送端在未收到确认之前 不能丢弃数据包，相应的缓存不能释放，使缓存进一步消耗，导致拥塞加重，在 网络流量非常高的情况下，网络甚至会完全瘫痪，几乎没有数据包能够送达接收 方。网络路由的主要目标是有效的分配进入网络的数据流量，保证通信子网不会 被用户发送的数据流淹没，合理地使用瓶颈资源。直观上，解决网络路由可以从 两方面入手，一是路径优化，即尽量避免拥塞的发生，是网络运行的最佳状态； 二是在拥塞发生后采取补救措施消除拥塞。完全避免网络拥塞的路由算法必然会 以牺牲网络的资源利用率为代价，在追求公平、高效、高利用率的网络环境下， 采取这种保守的方法显然是不适宜的。当前路由算法大多采用传统意义上的经典 可证明的算法，很少采用仿生学算法来解决相类似的问题：本文试图采用此类方 法来探讨解决路由问题的可能性。 蚁群算法作为仿生优化算法的一种，自1 9 9 1 年由意大利学者d o r i g om 提出 后是一个复杂的智能系统，它具有较强的鲁棒性、优良的分布式计算机制、易于 与其他研究方法结合等优点。作为一个新兴的科学，尽管不存在着确切的数学依 据来证明其可靠性，但是实际应用的过程中，蚁群算法在科学和实际应用中取得 了巨大的成就，证明其确实有效。它对于像n p 、n p _ c 相关问题提出了相关的解 决方案，其中包括路由问题、分配问题、调度问题、子集问题。 网络路由问题可以看作是路由问题的一个子集，但是有其独特的性质：网络 结构的动态的变化；影响因素的多样性和复杂性；网络路由的层次性；网络拓扑 图的由立体图而不是平面图等等因素。这给我们在解决问题路由问题带来很多的 困难，但是蚁群算法特有的优点在解决网络优化方面具有的先天优势促使我们结 合网络的特征，提出适合网络路由的算法 1 2 国内外研究现状 1 2 1 网络拥塞的研究 目前经典的拥塞控制的研究主要分为： ( 1 ) 从控制论的角度出发，拥塞算法可以分为开环控制( o p e n - l o o p ) 和闭环 控$ 1 j ( c l o s e d - l o o p ) 两大类。当流量的特征可以准确规定、性能要求可以事先获得 时，适于使用开环控制。开环控制的典型例子是就是资源预留( p s v p 协议) 。这 山东大学硕士学位论文 n i l 种方法虽然是一种很直接的方法，但由于实现确定精确的业务特征几乎不可能， 需要预留多余的网络资源，就会造成网络资源利用率下降。特别是当系统不提供 资源预留或者流量特征不能准确描述时，开环明显不适合只能使用闭环解决。闭 环的路由控制建立在反馈基础上，它首先检测网络中拥塞的发生，然后将拥塞信 息传递到拥塞控制点，最后拥塞控制点根据拥塞信息进行调整，以消除拥塞。闭 环的抑塞控制可以动态适应网络的变化，但是它的一个缺陷是算法的性能受到反 馈延迟的影响。当拥塞发生点和拥塞控制点之间的延迟很大时，拥塞控制算法的 性能会严重下降。 ( 2 ) 根据拥塞控制的实施位置，可以将拥塞控制算法分为两类：链路算法 ( l i n ka l i z o r i t h m ) 和源算法( s o u r c ea l g o r i t h m ) 。链路算法在网络设备( 如路由器和 交换机1 中执行。它的主要作用是检测网络拥塞的发生，生成拥塞反馈信息。源 算法在主机和网络的边缘设备中执行。它的主要作用是根据反馈信息调整发送速 率。拥塞控制算法设计的关键问题是如何给出反馈信息和如何对反馈信息进行响 应。 ( 3 ) 从实施控制的类型上，拥塞控制可以分为基于窗口和基于速率两种类型。 t c p 采用的是典型的基于窗口的控制方式，t c p 通过调整拥塞窗口的大小控制 发送到网络中的数据量，其易于实现，且可以限制注入网络的最大流量：基于速 率的控制方式是通过对t c p 的窗口控制机制进行建模，得到t c p 连接吞吐量与 网络参数之间的解析式，来控制发送端的发送速率的大小，一般适合于多媒体数 据流的传输控制，重点的性能指标是t c p 友好性。 ( 4 ) 从推断网络状态的反馈信息的类型上，可以分为显式拥塞控制和隐式拥塞 控制。在显式控制方式中，网络使用显式信号向执行控制的端点通告其状态( 可 用带宽、缓存容量等) ；在隐式控制方式中，控制端使用流量估计或者通过超时、 重复a c k 等隐含信号来推断网络状态。 1 2 2 蚁群算法的研究 蚁群算法的主要的研究发展现状分为： ( 1 ) 动态优化问题：动态问题可以是一个多量值的函数，这些量的值是由一个 潜在系统动态设置的。换句话说，这个问题的一些特征是随时间而变化的。本文 3 山东大学硕士学位论文 研究的网络路由问题即使动态的又是随机的。说它动态的是因为随着时间而变， 说它是随机的是因为在不同的瞬间时态中，流量假定值是一个随即变量。目前解 决上述问题的有3 种方法：第一种方法是在重新初始化所有的信息之后简单的重 启算法，第二三种方法是建立在一个假设的基础上的，这就是至少在节点替换率 不高的动态优化问题中，信息素包含的信息是有效地。 ( 2 ) 随即优化问题随即优化问题是某些用预定义的问题的变量具有随机特性的 问题，目前可以使用a c o 解决的随即优化问题主要集中在：网络路由问题，概 率t s p 问题。主要是通过使用一个粗略的、可计算的近似函数和具体问题相关 的启发式方法在构建路径的过程中指导蚂蚁，能够提高算法的性能。 ( 3 ) 多目标问题：多目标问题是要对多个而且经常是互相冲突的目标进行评估 的问题。一般利用决策者在解决问题之前就能向目标赋予权重和优先级将m o o p 问题转变为一个单一目标。在第一种情况中，通过计算所有目标的加权总和就可 以将目标转化为单一目标；在第二种情况中，不同解可以按照优先级顺序排序并 且按照字典顺序互相比较。这方面的研究在本文中可以向组播和多播方面发展。 限于本文的主要研究课题，并未向这方面进行探讨一这将是日后的研究的主要方 向和课题。 1 3 论文的主要工作 现有的路由排队管理机制都各自有不同的特性，有的使用丢包事件和链路空 闲事件来管理拥塞，有的使用控制数据流量来管理拥塞，有的是在队列满时丢弃 随后到达的分组来控制拥塞，在了解了这些问题之后，采用何种应对措施有利于 拓展已有网络路由算法，为其增加新鲜血液，为今后网络路由提供新的可行性方 法，有利于研究更完善的网络路由机制。 本文主要使用网络仿真工具n s 2 对常用的路由机制进行仿真研究，目的是为 不同网络应用环境找出相对可靠的路由机制，并进一步完善n s 2 仿真软件中的 路由算法。 根据研究的目标，本文的主要研究工作有以下几点： ( 1 ) 研究了基于蚁群算法的网络路由算法，设计了适用于网络特性的启发因 子及其发散因子，并分析了算法在对n s f n e t 和c r e n e t 的简单仿真运行情况， 4 山东大学硕士学位论文 由于是基于n s 2 平台的仿真，其实验数据与真实的网络运行存在一定的差距。 研究了在不同的数据分布的情况下a c r 算法和经典的网络路由算法的性能之间 的差异。 ( 2 ) 进一步优化基于蚁群算法的网络路由算法，提出了适合于q o s 路由的算法， 并进行仿真实验，同时分析算法实验的结果从平面q o s 路由，开始到层次路由， 我们给出了详细的设计算法，包括数学模型，算法设计等等，并在相应的条件下 进行了性能仿真，并给出了相应的仿真结构，并对结果进行了详细的分析。 ( 3 ) 完善了基于蚁群算法的拥塞规避路由策略，分析了所提出的路由策略的优越 性，及其在仿真条件下的性能分析。提出了“蚂蚁泛洪 的策略有效地提高了蚂 蚁算法在拥塞规避路由中的表现。 本文的具体内容安排如下： 第一章：绪论：阐述目前蚁群算法和网络路由的研究现状和存在的问题， 介绍本文的研究目的、研究内容，以及本文的主要工作及组织结构。 第二章：基于蚁群策略的网络的相关技术：介绍了通用蚁群算法和网络路 由、q o s 和拥塞路由的基本概念和相关问题。 第三章：结合蚁群算法的优势，将其运用到通用的网络路由问题的求解中 去，本文参考t d o r i g om 【2 4 1 的a n t n 就算法，并加以改进使其加快了收敛速度和并 行化的特征。 第四章：面对更加具体的路由问题：q o s 和拥塞路由本文提出了相应的解决 方案。 第五章：结论和进一步的研究方向。 1 4 总结 本章主要是对本文进行概括性总结；指出了下面章节将要研究的内容和重点。 对所研究的算法的现状和前景予以分析；概括性说明了本文所研究的内容。 山东大学硕士学位论文 第2 章基于蚁群算法的路由策略的相关技术 本章我们开始介绍蚁群算法的起源及其发展，并讨论了蚁群算法的思想起源， 蚁群算法和自然界蚂蚁之间的异同；通过讨论了蚁群算法的数学模型和数据结 构，算法要求的启发因子以及收敛因子可以深入的了解其解决问题的方式；算法 流程也是我们讨论的重点，脱胎于基本的蚁群算法的最大最小蚁群算法 ( m m a s ) 、排列蚁群算法( r a n k e da s ) 、精华蚁群算法( e a s ) 都基本与其算 法相类似，当然包括本文介绍的算法。 接下来我们介绍了网络路由的基础知识，并列举了相关的经典算法，和当今 网络路由中面临的问题；同时我们更近一步的讨论了q o s 路由和网络拥塞路由的 这些对一般意义上的路由问题的深化研究，同时更具有实际意义。本章的引入为 接下来的解决方面奠定了理论上和现实上的基础。 2 1 蚁群算法 自然界一直是人类创造力的丰富的源泉，人类从与自然界的相互作用之中获 得认识事物的能力。自然界中的许多自适应优化现象不断的给人以启示：生物体 和自然生态系统可通过自身的演化就使许多高度复杂的优化问题得到了完美的 解决。近些年来，一些与经典的数学规划原理截然不同的、试图通过模拟自然生 态系统机制以求解决复杂优化问题的仿生优化算法相继出现( 如遗传算法、蚁群 算法、人工免疫算法、微粒子群算法等) ，丰富了现代优化技术，也为那些传统 最优化技术难以处理的组合优化问题提供了切实可行的解决方案。 2 1 1 蚁群算法的来源与基本原理 经研究发现：自然界中的单个蚂蚁的智能并不高，同时没有集中的指挥，但 他们却能协同工作来集中食物，建立蚁穴并抚养后代，它们依靠群体优势发挥超 过单体的智能。蚁群算法( a n tc o l o n ya l g o r i t h m a c a ) 是一种模拟昆虫王国中的 蚂蚁群体智能行为的启发元算法，它具有较强的鲁棒性、优良的分布式计算机制、 易于与其他方法相结合等优点。尽管蚁群算法的严格理论基础尚未奠定，但是目 6 山东大学硕士学位论文 前人们对蚁群算法的研究已经由单一的旅行商问题( 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 1 ( a ) 所示。 蚂蚁群体不仅能完成复杂的任务，而且还能适应环境的变化，如在蚁群运动路线 上突然出现障碍物时，一开始各只蚂蚁分布均匀的，不管路径的长短，蚂蚁总是 按照相等的概率选择各条路径，如图1 1 ( b ) 所示。蚂蚁在运动的过程中，能够 在其经过的路径上留下信息素，而且能过感知信息素浓度的方向移动。相等的时 间内较短的路径上的信息素就遗留的较多，而选择较短路径的蚂蚁也随之增多， 如图1 1 ( c ) 所示。不难看出，由于大量蚂蚁组成的蚁群集体行为表现出了一种 信息正反馈现象，即某一路径上走过的蚂蚁越多，后来的选择该路径的概率越大， 蚂蚁个体之间就是通过这种信息交流机制来搜索食物，并最终沿着最短路径行 进，如图1 1 ( d ) 所示。 翱忡臻# 融一 冒潲湘 2 1 2 蚁群算法的起源 图2 - 1 蚁群算法示意图 根据蚂蚁“寻找事物”的群体行为，意大利学者d o r i g om 例等率先于1 9 9 1 7 山东大学硕士学位论文 年在法国巴黎召开的第一届人工生命( e u r o p e a nc o n f e r e n c eo na r t i f i c i a l l 1 t e ， e c a l ) 上最早提出了蚁群算法的基本模型；1 9 9 2 年，d o r i g om 又在其博士学位 论文中进一步阐述了蚁群算法的核心思想。通过比较人工蚂蚁与真实蚂蚁的异同 比较可以得到对a c a 的比较直观的了解 相同点比较： a 都存在一个群体中个体相互交流通讯的机制 人工蚂蚁和真实蚂蚁都存在改变所处环境的能力：真实蚂蚁在经过的径中上 留下信息素，人工蚂蚁改变路径上存储的数字信息，它记录了蚂蚁当前解和历史 解的性能状态，而且可被其他后继人工蚂蚁读写。蚁群依赖这种交流方式来改变 了当前蚂蚁所经过周围的环境。像真实的信息素发挥一样在蚁群算法中的一个发 挥机制。挥发机制使得人工蚂蚁和真实蚂蚁可以逐渐的忘却历史遗留信息，这样 可使蚂蚁在选择路径时不局限于以前蚂蚁所存留的“经验”。 b 完成一个相同的任务相同 人工蚂蚁和真实蚂蚁都要完成一个相同的任务，即寻找一条从源节点( 巢穴) 到目的节点( 食物源) 的最短路径。人工蚂蚁和真实蚂蚁都不具有跳跃性，只能 在想临界点之间一步一步移动，直到遍历完所有城市。 c 利用当前信息进行路径选择的随机策略 人工蚂蚁和真实蚂蚁从某一节点到下一结点的移动都是利用概率选择策略实 现的，概率选择策略只利用当前的信息来预测未来的情况，而不能利用未来的信 息。因此，人工蚂蚁和真实蚂蚁所使用的选择策略在时间和空间都是局部的。 不同点： 1 人工蚂蚁存在于一个离散的空间中，它们的移动是从一个状态到另一个 状态的转换； 2 人工蚂蚁具有一个记忆其本身过去行为的内在状态； 3 人工蚂蚁存在于一个与时间无关的环境中： 4 人工蚂蚁是完全盲从的，它还受到问题空间特征的启发； 为了改善算法的优化效率，人工蚂蚁可增加一些性能，如预测未来、局部优化、 回退等，这些行为在真实蚂蚁中是不存在的：一些改善蚁群算法中的人工蚂蚁可 实现简单预测。 山东大学硕士学位论文 2 1 3 蚁群算法模型的建立 对蚂蚁个体的抽象 由于蚂蚁算法是对自然界中蚂蚁觅食行为的一种模拟，是一种机理上的应用， 因此首先必须对真实蚂蚁进行抽象，而不可能也没必要对蚂蚁个体进行再现。我 们把抽象出来的人工蚂蚁可以看作是一个简单的智能体，能够完成所求问题简单 的构建过程，也能通过一种通讯手段相互影响来达到问题求解的目的。 问题空间的描述 自然界中的真实蚂蚁存在于一个三维的环境中，而问题空间的求解一般是在 平面内进行的，因此需要将真实的三维空间抽象为一个平面。另外一个问题是真 实蚂蚁是在一个连续的二维空间中行走的，而我们无法用计算机直接来描述一个 连续的平面，必须将连续的平面离散化与一组点组成的离散平面，人工蚂蚁可在 抽象出来的点上自由运动，我们要做的只不过是将问题空间抽象成为一个二维离 散的空间。 寻找路径的抽象 真实蚂蚁在觅食过程中主要是按照所处的环境中的信息量来决定其前进的方 向，而人工蚂蚁是在平面的节点上运动的，因此可把觅食过程抽相称算法中解的 构建过程，将信息素抽象为处在于图的边上的轨迹。在每一节点上，人工蚂蚁感 知连接该节点与相邻节点上的信息素轨迹的浓度，并根据浓度大小决定走向下一 节点的概率。 信息素挥发的抽象 自然界中的真实蚂蚁总是在所经上连续不断地留下信息素，而信息素也会随 着时间的推移而不断的挥发。由于计算机处理的时间只能是离散事件，所以必须 使信息素的挥发是离散发生。通常的做法是，当妈以完成从某一节到下一节点的 移动后，即经过一个时间单位之后，进行一次信息素的挥发，而这种在离散时间 点进行信息素挥发的方式与蚂蚁觅食过程的机理是完全相符的。 以上几点是对真实蚂蚁觅食行为的抽象，整个过程体现了蚁群算法的自组织性， 但是这种自组织系统存在一个缺陷，即系统的演化需要较长的时间。 9 山东大学硕士学位论文 7 1 2 1 4 基本蚁群算法的数据结构 设q ( f ) 表示f 时刻位于节点f 的蚂蚁数目，嘞( ) 为f 时刻路径( f ，- ，) 上的信息素 量，n 示t s p 为蚁群中的总数目，则刀2 善抚n ；r = 和t v 0 ( f ) 旧，c ，cc 是t 刻集 量， 示为蚁群中的总数目，则 百 ；1 一iv 川h 产，。是刻集 合c 的节点连接勺上当前信息量。 蚂蚁七( 后= 1 2 ，所) 在运动过程中，根据各条路径上的信息量和路径的统计信 息共同决定的概率寻找路径。用表纽6 彪e ( 忌= 1 ，- ，2 ，m ) 来记录蚂蚁当前所走过的 路径，t a b l e t 随着蚂蚁k 的搜寻过程动态调整。在搜索过程中，蚂蚁根据各条路 径上的信息量及路径的启发信息来计算状态转移概率。p ；( f ) 表示在t 时刻蚂蚁k 由元素( 城市) i 转移到节点j 的状态转移概率。 i【国扩( f ) 】“【刁腑( f ) 】声 p ；( f ) = h ( f ) 】4 【7 7 以( f ) 】， ij 叠ca l l o w c a 【0 ( 3 1 ) 式中，a l l o w e d e2 c 一细6 ”i ) 表示蚂蚁k 下一步允许概率的城市；伍，口为信 息素和期望式启发因子的相对重要性，其值越大，该要素对蚂蚁选择路径的概率 影响也就越大；勺( ) 为期望启发式因子，反映了蚂蚁在运动过程中启发信息在 蚂蚁选择路径中的受重视程度，其值越大，则该状态转移概率越接近于贪心规则。 r i c k ( t ) 为启发函数，其表达式如下 7 7 玻( f ) = 厂1 ( 3 - 2 ) 式中，办表示相邻两个城市之间的距离。对蚂蚁k 而言，吒则越大，p ；o ) 也 就越小。 为了避免残留信息素过多淹没启发信息，在每一只蚂蚁走完一步或完成对所 有的城市的遍历( 也即一个循环结束) 后，要对残留信息进行更行遗忘更新处理。 由此，竹l 时刻在路径( i ，j ) 上的信息量可按照如下的规则进行简化调整 l o 山东大学硕士学位论文 勺( f + 刀) = ( 1 一尸) f 扩o ) + 勺( f ) ( 3 - 3 ) 脚 a r f ( f ) = f ；( f ) 七= l ( 3 4 ) 式中，夕表示信息素的挥发系数，1 一夕则表示信息素的残留因子，为防止信息 素的无限量的积累，p 的取值范围为：pc o ，1 ) ；勺( ) 表示本循环中的路径( i j ) 上的信息素的增量，初始时刻勺( o ) = o ，勺( ) 表示第k 只蚂蚁在本次循环中留 在路径( i j ) 上的信息量。 2 1 5 基本蚁群算法的实现步骤 1 ) 参数初始化。令时间t - - o 和循环次数c = 0 ，设置最大循环次数f - 。， 将蚂蚁m 置于n 个元素( 城市) 上，令有向图上每一条边( i ，j ) 的初始 化信息量勺( ) 2c o n 肼，其中n s t 表示常量，且初始时刻勺( o ) = 0 。 2 ) 循环次数m2 虬+ 1 。 3 ) 蚂蚁路径记录表索引号k = l 。 4 ) 蚂蚁数目k 卜k + l 。 5 ) 蚂蚁个体根据状态概率公式( 3 1 ) 计算的概率选择元素( 城市) j 并 前进，j c t a b u s 。 6 ) 修改记录表指针，即选择好之后将蚂蚁移动到新的元素( 城市) ，并 把该元素( 城市) 移动到该蚂蚁个体的禁忌表中。 7 ) 若集合c 中元素( 城市) 未遍历完，即k c ，则在理论上无差错传输就是不可能的。 所以在网络低速链路处就会形成带宽瓶颈，当其满足不了所有信源带宽要求时， 网络就会发生拥塞。 ( 3 ) 处理器与链路带宽不匹配，也能引起拥塞。如果路由器的c p u 在执行排队 缓存、更新路由表等功能时，处理速度跟不上高速链路，也会产生拥塞。同样， 低链路对高速c p u 也会产生拥塞。因此，网络中拥塞现象发生的原因是“需求” 与“供给”不匹配。由于i n t e m e t 的设计机制导致其缺乏“接纳控制”能力，因此 在网络资源不足时不能限制用户数量；同时，i n t e m e t 是一个分散控制系统，由 于缺乏中央集成控制，网络无法控制用户使用资源的数量，而只能依靠降低服务 质量来继续为用户服务，也就是“尽力而为”的服务。 单纯地增加网络资源之所以不能解决拥塞问题，是因为拥塞本身是一个动态 问题，它不可能只靠静态的方案来解决，而需要协议能够在网络出现拥塞时保护 网络的正常运行。拥塞控$ 1 1 ( c o n g e s t i o nc o n t r 0 1 ) l h 题是以管理相互竞争的发送数 据源合理分享有限的传输带宽资源为目的，达到能有效避免拥塞的发生，抑制拥 塞的发展，并且能将网络从拥塞状态中恢复回来。在正常情况下( 即没有出现网 络故障时1 ，拥塞控制功能的目的是为了避免网络拥塞；当然拥塞的发生往往不 可避免和预测的这是因为：网络传输通常是采用分组交换，如果路由器缓存总是 空的，虽然传输时延低，但是网络的利用效率也低；如果路由器缓存总是被占用， 传输时延高，但是网络利用效率也高。因此拥塞控制的研究目的不是要完全避免 拥塞，而是在于采用合理的算法与机制确保网络不因传入数据流过大耗尽网络资 源节点而导致崩溃，对网络拥塞做出反应，最小化拥塞的强度、范围和持续时间。 拥塞控制至少应该包含两部分：一个算法路径中的拥塞情况进行响应，动态 的调节数据发送速率；另一方面，要有一个中间节点管理机制能有效地预测、监 测路径中的拥塞程度，通过显式或隐式的方法在拥塞发生前及时警告源端、在拥 塞发生之后抑制发送端以超出中间节点转发速率的速度发送报文分组。文献【5 - 7 1 对网络拥塞做了一定的研究，分组交换网络的性能( 功率、往返时间r t r 、吞吐 量) 与负荷的关系可以用图2 6 来说明。 1 9 山东大学硕士学位论文 性能 功率 盎膂 图2 6 网路性首邕和负荷之i 司的关系 由图2 6 可看出，当负荷较小时，网络吞吐率和资源功率随负荷的增长以指 数增长，r t t 随负荷的增长略有上升。当负荷到达膝点时，功率到达最大值，在 此之后吞吐量的增长远远慢于负荷的增长，r t p 迅速上升，功率快速下降，若继 续增长负荷，则存在丢包的可能。负荷到达崖点时，吞吐量达到最大值，功率达 到最小值。r t t 以指数增长，系统处于拥塞状态。膝点指资源功率到达最大值的 负荷量。崖点指资源功率下降到最小值且开始丢包时的负荷量。若一种控制机制 使得网络工作在膝点附近，该方法称之为拥塞避免( c o n g e s t i o na v o i d a n c e ) ；若一 种控制机制使得网络工作在崖点或崖点以后的网络回复至膝点前后，该方法称之 为拥塞恢复。拥塞控制策略包括拥塞避免和拥塞控制这两种不同的控制机制。拥 塞避免是“预防”机制，它的目标是避免网络进入拥塞状态，使网络运行在高吞 吐量、低延迟的状态。拥塞控制是“恢复”机制，它用于把网络从拥塞状态中恢 复出来。 在网络控制的研究中，拥塞控制和流量控制是网络的经典问题【5 ，引，但这两 个概念容易混淆。拥塞控制必须确保网络能进行数据传输，这是全局性的问题， 涉及到所有主机、路由器以及所有其他导致网络负荷能力削弱的因素。而流量控 制只与发送者和接受者之间的点到点的数据传输有关，它的任务是确保一个快速 发送方的发送速度不受影响。 y a n g 提出了拥塞控制的一般分类方法【9 】： ( 1 ) 根据算法的实现位置，可以将拥塞控制算法分为两大类：t c p 源端算法 ( s o u r c a l g o r i t h m ) 和邛链路算法( 1 i n ka l g o r i t h m ) 。源端算法在主机和网络边缘设 备中执行，作用是根据反馈信息调整发送速率。拥塞控制算法设计的关键问题是 山东大学硕士学位论文 如何产生反馈信息和如何对反馈信息进行响应。口链路算法在网络设备中实行， 作用是检测网络拥塞的发生，产生拥塞反馈信息。 ( 2 ) 根据实施控制的手段，可以将拥塞控制分为基于窗1 ：3 的拥塞控制算法和基 于速率( 又称基于方程的) 拥塞控制算法。基于窗口的控制算法从源端或接收端维 持一个类似于t c p 拥塞窗口的漏斗机制，来控制一次性发送到网络中的数据量 1 1 0 1 。基于速率的拥塞控制算法又可称为基于方程的拥塞控制算法、基于模型的拥 塞控制算法【1 0 _ 1 h 2 1 。基于速率的方法通过对t c p 窗口机制进行建模，得到t c p 连接吞吐量与网络参数之间的解析式，用来指导源端发送速率的大小，一般用于 流媒体的传输控制。 ( 3 ) 从控制理论的角