基于蚁群算法的网络多节点路由优化

1、1 绪论通信网络的迅速发展，新业务的不断出现，使多点通信成为网络必须支持的功能。传统网络中使用一对一的通信协议支持多点协议，数据需要做多个拷贝，分别传送，极大的浪费了网络资源。未来的多媒体通信，将带来大量的多点通信，使用点对点协议将造成网络效率的低下；另外，多媒体通信的业务通常需要达成一定的同步关系，使用点对点协议完成多点通信不再有效；而复用技术的发展使组播在共同的链路上共享带宽成为可能。由于上述原因必须考虑多点路由问题。由于网络是动态变化的，网络拓扑结构的变化的不可预测性和变化的频繁性和不确定性是网络多点路由问题与其他常见的组合优化问题的根本不同之处，网络流量的随机性和偶然性也是网络动态变化

2、的主要因素。有效快捷的网络路由算法是网路发展的重要问题。 而蚁群算法的出现和广泛应用，提供了多点路由优化设计的新的思想。蚁群算法是一种模拟进化算法，它是在对自然界中真实蚁群的集体行为研究的基础上，由意大利学者M.Dorigo等人首先提出的。M.Dorigo等人充分利用了蚁群搜索食物的过程与著名的旅行商问题（TSP）之间的相似性，通过人工模拟蚂蚁搜索食物的过程（即通过个体之间的信息交流与相互协作最终找到从蚁穴到食物源的最短路径）来求解TSP问题。仿生学家通过大量细致观察研究发现，蚂蚁个体之间是通过一种被称为外激素的物质进行信息传送，从而能相互协作，完成复杂的任务。蚂蚁在运动过程中，能在它所经过的

3、路径上留下该物质，而且蚂蚁在运动过程中能够感知这种物质的存在及其强度，并以此指导自己的运动方向，蚂蚁倾向于朝着这种物质强度高的方向移动。因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。蚁群算法是一种随机搜索算法，与其它模拟进化算法一样，通过候选解组成的群体的进化过程来寻求最优解，该过程包含两个基本阶段：适应阶段和协作阶段。在适应阶段，各候选解根据所积累的信息不断调整自身结构；在协作阶段，候选解间通过信息交流，以期产生性能更好的解。蚁群算法之所以能引起相关领域研究者的注

4、意，是因为这种求解模式能将问题求解的快速性、全局优化特征以及有限时间内答案的合理性结合起来。其中，寻优的快速性是通过正反馈式的信息传递和积累来保证的。而算法的早熟性收敛又可以通过其分布式计算特征加以避免，同时，具有贪婪启发式搜索特征的蚁群系统又能在搜索过程的早期找到可以接受的问题解答。这种优越的问题分布式求解模式经过相关领域研究者的关注和努力，已经在最初的算法模型基础上得到了很大的改进和拓展。基于蚁群算法的以上特点，将蚁群算法用于OSPF协议的网络中，根据不同网络的需要寻找最优路径（可以是时延、中间路由器个数或者费用等参数最优化），将是一个非常值得我们去研究的课题。1.1 本设计研究的目的意义

5、人们生活的现代社会是一个由计算机信息网络、电话通信网络、运输服务网络、能源和物流分配网络等各种网络组成的复杂的网络系统。网络优化的目的就是研究如何有效地计划、控制和管理这个网络系统，使之发挥最大的社会效益和经济效益。网络优化是运筹学的是一个经典和重要的分支，所研究的问题涉及诸多领域，一方面是如何最大限度的节省资源，如最短路径、最小费用等；另一方面是在网络资源有限的情况下如何发挥其最大效益，如最大物流问题、最优资源配置问题等。网络优化问题是一类特殊的组合优化问题，属于NP难问题。对于此类NP问题，传统运筹学的优化方法显得无能为力，寻找、研究、应用启发式智能化的优化方法显得尤为重要。蚂蚁算法就是其

6、中一种有效的启发式智能优化算法。本设计就是要在掌握蚁群算法的基础上，将其用于网络路由优化问题，根据不同网络的特点和需求，对算法进行相应修改，编写出优化软件。由于这种求解模式能将问题求解的快速性、全局优化特征以及有限时间内答案的合理性结合起来，因而能适应网络各种因素随机变化的的特性，将其用于OSPF协议的工作过程中，可以快速有效的找出其所需的最优路径。最终，实现网络资源的合理利用和高效的数据传输，提高网络的运行速度，这对于互联网今后的快速发展起着重要的促进作用。1.2 本设计的研究现状蚁群算法诞生于1991年，是一类新颖而前沿的问题求解算法。在算法改进与理论问题的应用领域，这种算法很快就得到了国

7、内外学者们的关注。在国外，学者们提出了不同版本的蚁群算法，进一步地提高算法的性能；同时，他们也把蚁群算法应用到众多复杂的经典理论问题中，包括旅行商、车辆路由、二次指派、工序调度、背包问题、群组规划等等。在某些具体问题中，蚁群算法的性能更是达到乃至超越了用于该问题的其它经典的求解算法。国内在最近几年也掀起了一股研究蚁群算法的热潮，与蚁群算法相关的学术著作层出不穷，算法的应用领域得到了不断的拓广，算法的性能也得到了不断的提高。在工业社会的实际应用领域，蚁群算法的成功正引起了国际上众多企业的关注。EuroBios公司首先把蚁群算法应用于求解现实世界中不同类型的调度问题。同时，AntOptima公司以

8、蚁群算法为工具，成功地开发出多种工业优化的软件工具，例如DYVOIL产品成功地解决了瑞士某企业的车辆燃油分配管理问题；ANTROUTE产品则解决了一些大型连锁超市集团企业的运输车辆调度与路由问题。此外，国外的企业还把蚁群算法应用于大型制造商生产线的设计、平衡的规划、水利设施的建设、数据挖掘、金融现金流的分析与预测等广泛的实际应用领域。 蚁群算法在通信网络领域（特别是解决网络领域问题）的应用受到越来越多的学者的关注。网络信息的分布式性、动态性、随机性和异步性与蚁群算法非常相似，如利用局部信息发现解，间接地通讯方式和随机状态的转换。在网络多点路由优化方面，已经取得了不错的进展。Di Caro和Do

9、rigo已经在相关文献中将蚁群算法应用于网络路由问题，并称这种算法为AntNet。根据网络的不同特点以及路由算法的不同，研究人员提出了各种改进的蚁群算法，提高了算法的性能和在实际中的应用价值。例如，在传感器网络中，充分考虑了网络能量有限的特点，提出了ACRA算法，提高了网络的寿命；高程ACS算法提高了算法的质量和收敛速度，引入蚂蚁回退机制则使得所有蚂蚁都能到达目的节点；最大-最小蚂蚁系统为信息素设置上下限避免了算法出现停滞的现象；基于混沌蚁群算法的路由模型，降低了时间复杂度，避免了蚁群算法陷入局部最优解。此外，还有利用遗传算法和蚁群算法的融合算法进行路由优化算法，WDM网络中基于较少波长的组播

10、路由优化算法等。但是蚁群算法的研究时间不是很长，还没有形成系统的分析方法和具有坚实的数学理论基础。参数的选择更多的是依靠实验和经验没有定理来确定，而且它的计算时间偏长，其在理论和实践方面尚存在许多问题需要更加深入的研究和解决。国内直到上个世纪末才有学着开始关注ACO算法，目前对该算法的研究还停留在算法的改进和应用方面。不过蚁群算法具有正反馈、并行计算和强鲁棒性等许多优点，随着研究的深入，蚁群算法将给我们展示一个求解复杂组合优化问题的优秀寻优算法。如何抽象实际问题，使蚁群算法的求解更接近工程实际是广大蚁群算法研算法理论及其应用的研究必将是个长期的研究课题。蚁群算法这一新兴的仿生优化算法在路由优化

11、方面必将展现出更加广阔、更加引人注目的发展前景。1.3 本课题要研究与解决的问题（1） 本课题首先要研究基于两种不同路由算法的路由协议：基于距离矢量算法的RIP协议和基于链路状态算法的OSPF协议，其中重点学习OSPF协议的具体工作过程及其特点。 （2）本课题将详细探讨蚁群算法基本原理、蚁群优化的一般过程、SACO算法以及其改进算法。我们知道，使用OSPF协议的路由器在工作过程中首先是通过发送Hello报文等方法与其他路由器建立连接并交换信息（包括链路状态、可达信息等），利用Dijkstra算法构造出网络的拓扑结构，寻找最短路径。然而网络是动态的，它的拓扑结构、流量随时变化，不同链路的带宽、时

12、延也不相同，我们希望能找到一种更快速有效的优化算法，以适应这种动态的、复杂的网络，提高网络的效率。蚁群算法给我们提供了一条很好的思路，它最初的提出正是用于寻找最短路径问题。（3） 在本课题的研究过程中，我们首先不考虑其他链路状态的因素，将最优路径问题简化为仅仅是与中间路由器跳数有关的最短路径问题，则利用蚁群算法计算出的最短路径就是最小跳数的路径。（4） 考虑时延等不同代价的最佳路径，对基本算法做如下改动：根据每条链路信息的不同，考虑时延、带宽等的作用的大小，给每条链路赋予一个不同权值，在计算路径长度时乘上权值（本设计中为了方便以链路的物理长度来代表其时延），修改信息素时加入权值因素的影响，这样

13、得出的最优路径即最少开销的路径。（5）最后，编写出相应的软件，进行计算机仿真，找出不同代价下的最佳路径，实现多点路由优化。2 路由选择的基本概念2.1 路由技术路由技术其实是由两项最基本的活动组成，即决定最优路径和传送数据包。其中，数据包的传送相对较为简单和直接，而路径的确定则更加复杂一些。路由算法在路由表中写入各种不同的信息，路由器会根据数据包所要到达的目的地，选择最佳路径把数据包发送到可以到达该目的地的下一台路由器处。路由器之间可以进行相互通信，它们通过传送不同类型的路由更新信息来维护各自的路由表。路由更新信息一般是由部分或全部路由表组成。通过分析其他路由器发出的路由更新信息，路由器可以掌

14、握整个网络的拓扑结构。链路状态广播是另外一种在路由器之间传递的信息，它可以把信息发送方的链路状态及时的通知给其他路由器。路由器要实现数据转发的功能，至少要完成两方面的内容：根据数据包的目的地址和网络拓扑选择一条最佳路径，把对应不同目的地址的最佳路径在路由表中；搜索路由表，决定向哪个端口转发数据，并执行相应的操作。在上面的两方面工作中，前者是选择策略问题，而后者是选路机制问题。选路策略的实质就是如何确定数据传送的最佳路径，它是通过建立和维护路由表来实现的。选路策略的不同，从本质上讲就是建立和维护路由表的方式不同。事实上，无论是静态路由选择还是各种动态路由选择协议，它们都是围绕选路策略站开的。选路

15、机制实质上就是如何查找路由表，并根据查表的结果把数据转发出去。一般来说，路由器首先搜索匹配的主机地址，如果没有，再搜索匹配的网络地址（可能需要子网掩码），最后搜索默认路由。一旦查到匹配表项，路由器就会把数据从相应的接口发送出去。在具体查找路由表时，可以使用不同的算法，常见的路由查询算法有二进制Trie树算法、路径压缩Trie树算法、多分支Trie树算法、基于前缀长度空间的二分查找法、基于地址区间的二分查找法以及基于硬件的TCAM机制等。衡量这些算法的指标包括时间复杂度（即查表的速度）、空间复杂度（路由表占用内存的大小）、预处理和更新速度（增加、删除、变更路由表条目时，路由表的更新速度）、可扩展

16、性等。路由查询算法的好坏直接影响路由查询的效率。一般来说，很难有哪算法可以同时在上述几个指标上达到最优。选路策略只影响路由表的内容，比如对同一个目的IP地址来说，由于选路策略的不同，最佳路径不能会不一样，但这并不影响选路机制的执行过程，只会对其执行的结果产生影响。2.2 路由选择算法路由选择算法是指路由器获得对网络拓扑结构的认知，并为数据包选择正确的传输路径的方法或者策略2。一个理想的路由选择算法至少应该具备以下几点特征：完整性和正确性，即每个路由器中的路由表都必须给出到所有可能目的节点的下一跳该怎么走，且给出的走法是正确的；简单性，即路由选择的计算不应使网络的通信量增加太多额外的开销；健壮性

17、，主要指当某些节点、链路出现故障不能工作，或故障恢复后投入运行，算法能及时改变路由；公平性，即算法对所有用户都是公平的；最佳性，即以最低的成本实现路由算法。为了降低数据包在网络中的传输开销和时延，要求为数据选择的路径是最短的。这里的“最短”在不同场合有着不同的含义，它可以是跳数的多少，物理距离的长短或者时延的大小等。互联网中使用的各种路由选择协议或者算法，其根本目的就是寻找源节点和目的节点之间最短的一条路径，即最短路由。路由算法的分类标准很多。按照能否根据网络状况的变化而动态调整可以分为静态（非自适应）和动态（自适应）两大类；按照工作的模式可以分为集中式和分布式两大类，前者由路由控制中心集中收

18、集网络拓扑结构信息并计算路由，后者由网络中所有路由器通过交换路由信息，各自独立的计算路由。互联网的复杂性使得当前使用的路由算法主要是动态的、分布式的。目前互联网上的动态路由协议主要基于两种动态分布式路由选择算法：距离矢量路由算法和链路状态路由算法。2.2.1 距离矢量路由算法距离矢量路由算法的基础是分布式的BF算法。在距离矢量路由中，各个路由器都维持一个距离矢量表，对每个目的节点都有一个对应的表项，包括两部分内容：到该目的节点最短路径上的下一个路由器；到该目的节点的最短路径长度。在工作时，路由器周期性地和相邻的路由器交换路由表中的信息，即向邻居路由器发送路由表的全部或部分。这种信息是由若干（v

19、，d）对组成的表项，其中，v代表矢量，指出该路由器可以达到的目的地；d表示去往目的地v的距离。各个路由器根据收到的信息，按照分布式BF算法重新计算到各目的节点的距离，并对自己的路由表进行修正。这种一步一步的处理使得每一个路由器都可以知道其他路由器的情况，并形成关于网络“距离”的累积透视图。2.2.2 链路状态路由算法 链路状态路由算法也被称为最短路径优先SPF算法，它的提出主要是为了克服距离矢量路由算法所存在的收敛速度慢，难以适应大型网络等缺陷。链路状态路由算法的基本步骤如下：（1）每一个路由器启动后，首先执行对相邻节点的发现工作，并获得它们的地址，这个过程在具体实施时是通过发送特殊的Hell

20、o分组实现的；（2）各路由器主动测试到每一个相邻路由器的链路时延或成本，并根据测试结果设置相关的链路的状态；（3）各路由器构造自己的LS（链路状态）信息包，LS信息的内容包括本路由器的标号、本路由器的邻居路由器的链路状态、该LS信心包的序号和生存时间等；（4）各路由器向所有参与SPF的路由器广播其LS信息，可以周期性地发送，也可以在链路状态发生变化时发送；（5）每个路由器的收听到所有的LS信息后，可以构造或更新表示整个网络拓扑结构的图G（V，E），顶点V表示路由器，边E表示连接路由器的链路，这时路由器就可以用Dijkstra算法从图G中计算出到所有目的路由器的最短路径，也就是构造以自己为根节点

21、的SPF树。对比距离矢量路由算法和链路状态路由算法，总结它们各自特点如下：距离矢量路由算法实现简单，对路由器处理能力要求不高，但收敛速度慢，适用于规模较小和拓扑结构变化不快的网络；链路状态路由选择算法能够及时反映网络拓扑结构的变化，收敛速度很快，适应于规模较大和拓扑变化较快的网络，但由于每一个路由器均需要实时形成全网的拓扑图及构造以自己为节点的树，所以对处理器性能要求比较高，另外，路由信息是以广播的形式传播的，占用的网络带宽比较多。2.3 路由协议路由协议可以分为内部网关协议IGP和外部网关协议EGP两大类。简单的定义是，内部网关协议是用于自治系统内部的动态路由协议，包括RIP、OSPF等；而

22、外部网关协议是用于自治系统之间的拓扑信息交换的路由协议，包括BGP等。本设计将基于OSPF协议，下面将详细讨论该协议。开放最短路径优先协议OSPF17是一种基于区域（路由域）实现的、建立在Dijkstra算法和链路状态算法基础之上的内部网关动态路由协议。最初提出OSPF主要目的是为了距离矢量路由协议RIP等所存在的收敛速度慢、采用固定度量以及不能动态负荷平衡等缺陷。目前OSPF由于其优异的性能，已经成为应用最广泛的内部网关协议之一。OSPF的基本思想如下：（1） 每个OSPF路由器都维护一个用于跟踪网络状态的链路状态数据库（Link State Data-Base ，LSDB)。数据库中的内容

23、是反映路由器状态的各种链路状态通告（Link State Advertisement，LSA），这些状态包括路由器可用接口、已知可达路由和链路状态信息，各OSPF路由器都会主动测试所有与之相邻的路由器的状态，并根据测试结果设置相关链路状态。利用LSDB，路由器就可以得到一张整个网络拓扑结构的图。在图论中,OSPF计算出的路由也是一种无环路的路由为了减小路由器的LSDB，不同的LSA又有不同的作用范围，这就使得OSPF具有一定的路由层次性。这种路由层次性是用划分区域的方法来实现的。OSPF的管理距离是110。最佳路径的度量有：路径长度它是最常用的路由度量，一般定义为跳数，即从源端到目的端所经过的

24、路由器个数；可靠性在路由算法中指网络链接的可依赖性，有些网络链接可能比其他的失效的更多，网络失效后，一些网路链接可能比其他的更容易或更快修复，通常是网管给网络链接赋以度量值；时延路由时延指分组从源端到达目的端所花时间，影响时延的因素有中间的网络链接的带宽、经过每个路由器的端口队列、所有中间网络链接的拥塞程度和物理距离等，时延是多个变量的混合体，是个比较常用和有效的度量；带宽指链路可用的流通容量（通常以网速来表示），虽然带宽是链路可获得的最大吞吐量的基本保证，但是通过具有较大链路带宽的路由不一定比经过较慢链路路由更好；负载指诸如路由器等网络资源的繁忙程度，负载可能涉及很多方面的的计算，包括CPU

25、使用情况和每秒处理分组数；通信开销。 （2） OSPF基于Dijkstra算法和自治系统中路由器的链路状态进行路由计算。路由器在计算路由表时要借助于Dijkstra算法建立起来的最短路径树。路由器把自己作为树根，用该树跟踪系统中每个目标的最短路径，并由此计算出区域内路由；接着，通过查看区域间LSA计算到自治系统内部其他区域目的地的路由；最后，检查自治系统外部LSA，计算到自治系统外部目的地的路由。路由表更新通过LSA发送给在同一个路由域内的所有其他路由器。OSPF协议工作过程：OSPF的工作过程可以分为三个互相关联的主要部分：称为“呼叫”（Hello）协议、近邻关系建立和“可靠洪泛”机制。呼叫

26、协议、近邻关系建立和可靠洪泛机制完成了OSPF包的交互过程，并最终实现同一个路由域中所有路由器的LSDB一致。与RIP等路由协议不同，OSPF的各类报文都是直接封装在IP报文中的，不需要使用传输层协议（TCP、UDP等）的支持。OSPF有五种报文：Hello报文（发现及维持邻居关系，选举DR，BDR）、DD报文（本地LSDB的摘要）、LSR报文（向对端请求本端没有或对端的更新的LSA)、LSU报文（向对方发送其需要的LSA）、LSAck报文（收到LSU之后，进行确认）。OSPF路由协议针对每一个区域分别运行一套独立的计算法则，对于ABR来说，由于一个区域边界路由器同时与几个区域相联，因此一个区

27、域边界路由器上会同时运行几套OSPF计算方法，每一个方法针对一个OSPF区域。下面对OSPF协议运算的全过程作一概括性的描述。 当一个OSPF路由器初始化时，首先初始化路由器自身的协议数据库，然后等待低层次协议（数据链路层）提示端口是否处于工作状态。如果低层协议得知一个端口处于工作状态时，OSPF会通过其Hello协议数据包与其余的OSPF路由器建立交互关系。一个OSPF路由器向其相邻路由器发送Hello数据包，如果接收到某一路由器返回的Hello数据包，则在这两个OSPF路由器之间建立起OSPF交互关系，这个过程在OSPF中被称为adjacency。在广播性网络或是在点对点的网络环境中，OS

28、PF协议通过Hello数据包自动地发现其相邻路由器，在这时，OSPF路由器将Hello数据包发送至一特殊的多点广播地址，该多点广播地址为ALLSPFRouters。在一些非广播性的网络环境中，我们需要经过某些设置来发现OSPF相邻路由器。在多接入的环境中，例如以太网的环境，Hello协议数据包还可以用于选择该网络中的指定路由器DR。一个OSPF路由器会与其新发现的相邻路由器建立OSPF的adjacency，并且在一对OSPF路由器之间作链路状态数据库的同步。在多接入的网络环增中，非DR的OSPF路由器只会与指定路由器DR建立adjacency，并且作数据库的同步。OSPF协议数据包的接收及发送

29、正是在一对OSPF的adjacency间进行的。OSPF路由器周期性地产生与其相联的所有链路的状态信息，有时这些信息也被称为链路状态广播LSA（Link State Advertisement）。当路由器相联接的链路状态发生改变时，路由器也会产生链路状态广播信息，所有这些广播数据是通过Flood的方式在某一个OSPF区域内进行的。Flooding算法是一个非常可靠的计算过程，它保证在同一个OSPF区域内的所有路由器都具有一个相同的OSPF数据库。根据这个数据库，OSPF路由器会将自身作为根，计算出一个最短路径树，然后，该路由器会根据最短路径树产生自己的OSPF路由表。OSPF路由协议通过建立交

30、互关系来交换路由信息，但是并不是所有相邻的路由器会建立OSPF交互关系。下面将OSPF建立adjacency的过程简要介绍一下。OSPF协议是通过Hello协议数据包来建立及维护相邻关系的，同时也用其来保证相邻路由器之间的双向通信。OSPF路由器会周期性地发送Hello数据包，当这个路由器看到自身被列于其它路由器的Hello数据包里时，这两个路由器之间会建立起双向通信。在多接入的环境中，Hello数据包还用于发现指定路由器DR，通过DR来控制与哪些路由器建立交互关系。两个OSPF路由器建立双向通信这后的第二个步骤是进行数据库的同步，数据库同步是所有链路状态路由协议的最大的共性。在OSPF路由协

31、议中，数据库同步关系仅仅在建立交互关系的路由器之间保持。OSPF的数据库同步是通过OSPF数据库描述数据包（Database Des cription Packets）来进行的。OSPF路由器周期性地产生数据库描述数据包，该数据包是有序的，即附带有序列号，并将这些数据包对相邻路由器广播。相邻路由器可以根据数据库描述数据包的序列号与自身数据库的数据作比较，若发现接收到的数据比数据库内的数据序列号大，则相邻路由器会针对序列号较大的数据发出请求，并用请求得到的数据来更新其链路状态数据库。我们可以将OSPF相邻路由器从发送Hello数据包，建立数据库同步至建立完全的OSPF交互关系的过程分成几个不同的

32、状态，分别为：Down：这是OSPF建立交互关系的初始化状态，表示在一定时间之内没有接收到从某一相邻路由器发送来的信息。在非广播性的网络环境内，OSPF路由器还可能对处于Down状态的路由器发送Hello数据包。 Attempt：该状态仅在NBMA环境，例如帧中继、X.25或ATM环境中有效，表示在一定时间内没有接收到某一相邻路由器的信息，但是OSPF路由器仍必须通过以一个较低的频率向该相邻路由器发送Hello数据包来保持联系。 Init：路由器的各个接口发送Hello数据报文到其他运行OSPF的路由器，当邻接路由器收到第一个Hello数据报文，这时就进入Init状态。在该状态时，OSPF路由

33、器已经接收到相邻路由器发送来的Hello数据包，但自身的IP地址并没有出现在该Hello数据包内，也就是说，双方的双向通信还没有建立起来。 2-Way：这个状态可以说是建立交互方式真正的开始步骤。在这个状态，路由器看到自身已经处于相邻路由器的Hello数据包内，双向通信已经建立。指定路由器及备份指定路由器的选择正是在这个状态完成的。在这个状态，OSPF路由器还可以根据其中的一个路由器是否指定路由器或是根据链路是否点对点或虚拟链路来决定是否建立交互关系。 Exstart：这个状态是建立交互状态的第一个步骤。在这个状态，路由器要决定用于数据交换的初始的数据库描述数据包的序列号，以保证路由器得到的永

34、远是最新的链路状态信息。同时，在这个状态路由器还必须决定路由器之间的主备关系，处于主控地位的路由器会向处于备份地位的路由器请求链路状态信息。 Exchange：在这个状态，路由器向相邻的OSPF路由器发送数据库描述数据包来交换链路状态信息，每一个数据包都有一个数据包序列号。在这个状态，路由器还有可能向相邻路由器发送链路状态请求数据包来请求其相应数据。从这个状态开始，我们说OSPF处于Flooding状态。 Loading：在loading状态，OSPF路由器会就其发现的相邻路由器的新的链路状态数据及自身的已经过期的数据向相邻路由器提出请求，并等待相邻路由器的回答。 Full：这是两个OSPF路

35、由器建立交互关系的最后一个状态，在这时，建立起交互关系的路由器之间已经完成了数据库同步的工作，它们的链路状态数据库已经一致，这个状态称为“全毗邻状态”，每台路由器保存着一张毗邻路由器列表称为“毗邻数据库”。两个OSPF路由器数据库同步是所有链路状态路由协议的最大共性。在OSPF路由协议中，数据库同步关系仅仅建立在交互关系的路由器之间保存。OSPF协议的优点：（1）OSPF是真正的LOOP- FREE(无路由自环)路由协议源自其算法本身的优点(链路状态及最短 路径树算法)（2）OSPF收敛速度快:能够在最短的时间内将路由变化传递到整个自治系统（3）提出区域(area)划分的概念,将自治系统划分为

36、不同区域后,通过区域之间的对路由信息的摘要,大大减少了需传递的路由信息数量也使得路由信息不会随网络规模的扩大而急剧膨胀（4）将协议自身的开销控制到最小1)用于发现和维护邻居关系的是定期发送的是不含路由信息的hello报文,非常短小包含路由信息的报文时是触发更新的机制(有路由变化时才会发送)但为了增强协议的健壮性,每1800秒全部重发一次2)在广播网络中,使用组播地址(而非广播)发送报文,减少对其它不运行ospf 的网络设备的干扰3)在各类可以多址访问的网络中(广播,NBMA),通过选举DR,使同网段的路由器之间的路由交换(同步)次数由 O(N*N)次减少为 O (N)次4)提出STUB区域的概

37、念,使得STUB区域内不再传播引入的ASE路由5)在ABR(区域边界路由器)上支持路由聚合,进一步减少区域间的路由信息传递6)在点到点接口类型中,通过配置按需播号属性(OSPF over On Demand Circuits),使得ospf不再定时发送hello报文及定期更新路由信息只在网络拓扑真正变化时才发送更新信息（5）通过严格划分路由的级别(共分四极),提供更可信的路由选择（6）良好的安全性,ospf支持基于接口的明文及md5 验证（7）OSPF适应各种规模的网络,最多可达数千台3 蚁群算法3.1 蚁群优化的原理分析 AC O是受自然界中真实蚁群的集体觅食行为的启发而发展起来的一种基于群

38、体的模拟进化算法，属于随机搜索算法。M.Dorigo等人充分利用了蚁群搜索食物的过程与著名TSP问题之间的相似性，通过人工模拟蚁群搜索食物的行为来求解TSP问题。从下面的的“双桥实验”可以看出，像蚂蚁这类社会性动物，虽然个体的行为极其简单，但由这些简单个体所组成的蚁群却表现出极其复杂的行为特征。如蚁群除了能够找到蚁巢与食物源之间的最短路径外，还能适应环境的变化，即在蚁群运动的路线上突然出现障碍物时，蚂蚁能够很快地重新找到最短路径。蚁群是如何完成这些复杂任务的呢?仿生学家经过大量地观察、研究发现，蚂蚁在寻找食物时，能在其经过的路径上释放一种蚂蚁特有的分泌物一外激素，使得一定范围内的其它蚂蚁能够感

39、觉到这种物质，且倾向于朝着该物质强度高的方向移动。因此，蚁群的集体行为表现为一种信息正反馈现象:某条路径匕经过的蚂蚁数越多，其上留下的外激素的迹也就越多(当然，随时间的推移会逐渐蒸发掉一部分)，后来蚂蚁选择该路径的概率也越高，从而更增了该路径上外激素的强度。蚁群这种选择路径的过程被称之为自催化行为，由于其原理是一种正反馈机制，因此也可将蚁群的行为理解成所谓的增强型学习系统。接下来简单解释一下蚁群发现最短路径的原理和机制。在蚁巢和实物之间有两条道路，Nest-A-B-D-Food和Nest-A-C-D-Food，其长度分别为4和6。单位时间内蚂蚁可移动一个单位长度的距离。开始时所有路径上都没有外

40、激素。在t=0时刻，20只蚂蚁从蚁巢出发移动到A。由于路径上没有外激素，它们以相同概率选择左侧或右侧道路，因此平均有10只蚂蚁走左侧，另外10只走右侧。在t-4时刻，第一组先到达食物源的蚂蚁将折回。在t=5时刻，两组蚂蚁将在D点相遇。此时BD上的外激素数量与CD上的相同，因此返回的10只蚂蚁中有5只选择BD而另5只选择CD.在t-S时刻，前5个蚂蚁将返回巢穴，而在AC.C D和AB上各有5个蚂蚁。在t=9时刻，前5个蚂蚁又回到A并且再次面对往左还是往右的选择这时，AB上的轨迹数是20而AC上是15，因此将有较为多数的蚂蚁选择往右，从而增强了AB上外激素的量。随着该过程的继续，两条道路上外激素数

41、量的差距将越来越大，直至绝大多数蚂蚁都选择了最短的路径。正是由于一条道路要比另一条道路短，因此，在相同的时间间隔内，短的路线会有更多的机会被选则。3.2 简单蚁群优化SACO介绍蚁群算法前我们首先来介绍以下双桥实验：在该实验中，巢穴和食物之间用等长度的双分支桥连接。最初桥的两个分支都没有任何信息素，过了一段时间之后，尽管这两个分支长度相等，还是有一个分支被绝大多数蚂蚁所选择。原因是随机的路径选择促使所随机选择到的分支上信息素浓度积累。通过该实验，研究人员建立了一个形式化的模型来描述蚂蚁选择路径的过程。建模过程中，他们假设各蚂蚁分泌等量的信息素且不考虑信息素的挥发，得出蚂蚁在t+1时刻选择路径A

42、的概率如下所示（其中和分别表示在t时刻路径A、路径B上所经过的蚂蚁数量） （3.1）式中，c代表未开发路径（不含信息素的路径分支）对蚂蚁的吸引度，表示蚂蚁选择路径的过程中受信息素的影响程度。的值越大，蚂蚁选择高信息素浓度路径的可能性越大，即便两条路径的信息素浓度差别很小。c越大，则需要越高的信息素浓度来影响蚂蚁的下一步选择。实验表明，当时，该概率模型与实际相符。 我们以常见的寻找图中两节点间最短路径问题为例，G=（V，E），其中V表示图节点的集合，E表示图中边的集合。图中共有个节点，表示蚂蚁k所经历的路径的长度两节点间跳转边的数量。对于每个边（i，j），都赋予了相应的信息素浓度。对于SACO2

43、1来说，每个边地信息素浓度都被初始化为一个小的随机值。 严格来讲，初始时每个边应该不含信息素，蚂蚁随机的选择路径。根据上述算法，给每个边的信息素浓度一个小的随机值更容易实现。每个蚂蚁k（k=1,2，,）都被置到源节点。对于SACO的每次迭代，每只蚂蚁逐渐建立一条到达终节点的路径。在每个节点，蚂蚁都会进行决策选择下一段路径。如果蚂蚁k当前节点是i，那么它选择下一结点j的概率为 （3.2）式中是对于蚂蚁k来说，跟节点i相连接的可选节点的集合。如果蚂蚁k在节点i时，那么把节点i加入到中，这么做会导致路径中有环出现，而这些环将会在形成完整路径后去除。上式中是一个正的常量，用于放大信息素浓度的影响。太大

44、的会过度增大信息素的影响，尤其是初期随机的信息素浓度，从而会导致算法快速收敛到次优路径。一旦所有蚂蚁到达终结点，并去除了路径中的环，每只蚂蚁会沿原路径回到源节点，并沿途在每个边（i，j）上释放一定的信息素，其中是该路径第t步那段路径的长度： （3.3） 即 （3.4）式中表示蚂蚁的总数量。由上式可知，一条边的信息素浓度跟该边所在的路径的优良程度成正比路径越短越优。计算出的所应释放的信息素量代表相应的路径的优良度。对于SACO，解（建立的路径）的优良简单地表示为该路径的长度（也就是经历的边地数量）的倒数。而其他的测量度同样适用，比如所经历每条边所带来的开销，或者路径的物理长度。一般来说，用表示时

45、刻t的解，用f（）表示解的估量。如果不与解的质量成比例，且所有的蚂蚁释放相同的信息素量，那么仅仅是路径的长度影响（短的返回时间造成信息素释放频率增大）蚂蚁倾向于选择短路径。由此我们得出蚂蚁算法中两种形式的解估量：隐式估量（路径长度的差异造成蚂蚁间的相互影响）、显示估量（信息素的释放量跟路径的优良程度成正比）。但是我们应该注意到，这种决策信息仅限于蚂蚁的局部环境，SACO适用于简单图和蚂蚁数量较少的情况，这样大多能找到最短路径。但是当图较大时，算法变得不鲁棒，对参数敏感，性能较差。此外，对于蚂蚁数目很多的情况，可能导致算法不收敛。对于复杂的图来说，信息素的挥发变得更为重要。当=0时（信息素不挥发

46、），算法不收敛；当信息素挥发过多（过大）会导致算法收敛到次优路径。对于较小的，算法一般可以收敛到最短路径，对于复杂问题来说，大的会导致更差的收敛性能。3.3 蚁群算法的主要特点ACO算法的主要特点概括如下：1）采用分布式控制，不存在中心控制;2）每个个体只能感知局部的信息，不能直接使用全局信息;3）个体可改变环境，并通过环境来进行间接通讯(Stigmergy机制);4）具有自组织性，即群体的复杂行为是通过个体的交互过程中突现出来的智能;5）是一类概率型的全局搜索方法，这种非确定性使算法能够有更多的机会求得全局最优解 ;6）其优化过程不依赖于优化问题本身的严格数学性质，诸如连续性、可导性，及目标

47、函数和约束函数的精确数学描述;7）是一类基于多主体(MultiA gent)的智能算法，各主体间通过相互协作来更好的适应环境;8）具有潜在的并行性，其搜索过程不是从一点出发，而是同时从多个点同时进行。这种分布式多智能体的协作过程是异步并发进行的，分布并行模式将大大提高整个算法的运行效率和快速反应能力。4 基于蚁群算法的网络多点路由的优化与仿真4.1 网络路由优化问题的描述网络是指把某些元件有目的的、按一定形式连接起来、完成特定任务的总体。从抽象的数观点来看，网络实质上是一个赋权的有向图，它由节点和连接这些节点的弧及其方向组成。自然界和人类社会中的大量事物及事物之间的相互关系(例如物质结构、城市

48、规划、交通运输、信息的传递、工作的调配、事物关系等等)都可以用点与线连接起来的网络图来描述。网络图是从实际模型中抽象出来的，因此可以根据问题的实际需要给弧和节点赋予一个数来表明它所对应元件的不同物理意义。这个具有特殊意义的数，我们称之为节点或弧的权。例如，在公路运输网络中，弧的权可以为路的长度或单位长度的运费；在供水网络系统中，弧的权可以是水流量或水管的直径；在电网络中，弧的权可以为元件的电阻、电压或电流等。网络最短路径是在网络图中寻求边权和最小的最小路。而网络中的这个权可以是链路的带宽、时延、开销等，或者它们的综合。所谓的网络路由优化问题是指在一个网络中，要求在某些约束条件下找出从节点A到B

49、之间的最佳路由，即是在某些含义下的最佳路由（即上面所说的加权最优值）。目前已经有许多智能化算法，如遗传算法、模拟退火算法、神经网络等用于网络路由优化，已取得较好的结果。4.2 基于蚁群算法来选择路由算法的思想的概述通过前面对蚁群算法和网络优化问题的研究我们发现，可以将实际中的路由选择问题抽象成求最短路径问题的模型，进而利用蚁群算法求出最佳路径。该模型如下：用一种控制报文( 又称蚂蚁) 来搜集路径信息进行路由选择。本文用移动代理来模拟蚂蚁,分为两种,即前向蚂蚁Fant和后向蚂蚁Bant , 并通过移动代理的复杂交互来决定路由。用前向蚂蚁（表示从源节点到目的节点的移动代理）搜集从源节点到目的节点的

50、路径信息( 包括端到端的延迟、所经过的跳数等);后向蚂蚁（表示从目的节点返回到源节点的移动代理）据此来改变所经过的各个节点的路由信息。本文在研究过程中将问题简化，用端到端所经过的跳数来表示信息素值（时延等可以利用对边进行权值的设定来实现）。将网络中各节点的路由表用用一种概率表表示，其中概率表示信息素强度，即信息素表。 初始状态时，所有路径上的信息素均匀分布，蚂蚁不断对信息素进行更新，信息素本身也在随着时间不断减少。从源点发送一组蚂蚁，按上面的规则进行移动，蚂蚁可以遍历所有节点，并且蚂蚁能够记住所经过路径的信息，包括跳数和时延，并最终到达目的节点。显然走路径短的蚂蚁最先到达目的节点，目的节点只接

51、收最先到达的蚂蚁。最先到达终点的蚂蚁（即全局最优蚂蚁）按原路径返回，并修改沿途节点的路由表（信息素表），增大相应边上的信息素浓度（即增大选择该路径的概率）。如此不断地迭代运算，算法将收敛于最短路径。为了完成建立最优路径的任务，蚂蚁拥有如下属性和特点：1）蚂蚁有记忆功能来保存建立的路径信息。该记忆主要用于保证满足约束条件，比如每个节点只允许访问一次。该记忆还用于按原路径返回，来释放信息素，增强对应边上的信息素浓度。2）蚂蚁为每个状态决定一些可选的邻节点。其中包括所有的从当前节点有效转移的可达节点。之后蚂蚁进入一个新的状态（部分解）。3）每只蚂蚁都被分配一个初始状态，对应初始节点。4）每只蚂蚁都对

52、应一个或多个终止条件，终止条件包括路径达到限定的最大节点数、找到可接受的解、或者到达终节点。5）每只蚂蚁依据概率转移规则从可选邻节点中选取下一结点。6）每只蚂蚁都拥有修改所经历路径上的信息素浓度的能力，作为与其他蚂蚁通信的方式。4.3 基于蚁群算法的路由优化具体过程 蚂蚁系统在以下方面改进简单蚁群优化算法：增加启发式信息，改变转移概率；增加禁忌表，来增加记忆功能。因此，本课题在研究过程中将采用蚂蚁系统算法，并基于OSPF协议进行路由优化。4.3.1 最优路径的建立在基于蚁群算法的最优路径建立过程中，每个节点包含一个缓存器，存放着近学习到的和用过的路由信息。源节点s要发送数据到目的节点d，它首先

53、在自己的路由表里查找是否存在一条到d的路由。如果没有到d的路由信息时，就进行路由发现过程。具体过程如下: 每个节点初始化连接邻居节点链路的信息素； 源节点产生m只前向蚂蚁； 第k只前向蚂蚁所在的当前节点i首先检查路由表中是否有到目的节点d 的路径，如果有则前向蚂蚁单播，否则前向蚂蚁按概率选择其邻居节点j，并且在前向蚂蚁中插入中间节点i的编号、地址和路径信息。节点i选择下一跳j的规则为 （4.1）式中代表从节点i移动到节点j的后验效应，以边（i，j）上的信息素浓度表示；代表从节点i移动到节点j的先验效应，通过启发式信息计算得出。信息素浓度表示过去从节点i到j移动带来的影响，是对过去优质移动的记忆

54、。上式中的转移概率跟SACO有两方面的不同：1) 蚂蚁系统中的转移概率是在信息素浓度（代表之前较优的移动）和启发式信息（下一移动的倾向性）之间的平衡。这样做可以很好的处理探索-开发之间的关系。算法的搜索倾向于过去一段时间搜索中较优的路径，从而探索搜索空间以获取信息。同时，为了发现类似的优质路径，算法会开发以前未涉及到的路径。而探索与开发之间最好的平衡是通过调节参数得到的。当时，将不会利用信息素信息，也就是忽略之前的搜索经验。搜索降级为随机贪心搜索。当时，下一节点的吸引性将被忽略，算法在某些问题上变得跟SACO很相似。启发式信息增加了对有吸引力的解的显式倾向性，它通常是问题独立的函数。比如说对于

55、最小化路径长度问题，它可以表示为 （4.2）式中表示节点i与节点j之间的距离或者开销。2）集合表示蚂蚁k在节点i可选后续节点集合。可选节点集合可以直接包含节点i的相邻节点。或者，为了避免环的出现，在中仅包含蚂蚁k未访问过的节点。为此，为每只蚂蚁建立一个禁忌表。当蚂蚁访问一新节点时，就把该节点加入到禁忌表中。禁忌表中的节点将不会被包含在中，确保每个节点只被访问一次。 中间节点接收到前向蚂蚁后按照的规则进行转发,直到前向蚂蚁到达目的节点d停止。中间节点和目的节点可能收到同一个前向蚂蚁的复制品。此节点只接收最早到达且跳数最少的那个前向蚂蚁，将其余的丢弃。源节点到目的节点的过程中，每个前向蚂蚁记录所访

56、问过的节点和所经过的每条链路上的时延及跳数，保存在前向蚂蚁本身的一个栈中。Bant可据此信息在返回途中对个节点的信息素表进行修改，并可根据节点的数目计算出跳数h。当出现环路时，即Fant又返回到一个已经访问过的节点时，则将所有与形成环路的节点有关的信息全部去掉，Fant按相同的概率值在邻居节点中选择一个作为下一跳，以免再次进入环路； 当Fant到达目的节点d 后，则转换成后向蚂蚁Bant，Bant中包含了Fant收集到的所有的路径信息。Bant根据该路径信息以更高优先级按原路路径返回源节点i，并根据时延和跳数信息在返回途中对每个节点上的信息素表进行更新。在每个中间节点i上，Bant可以读出从该

57、节点到邻居节点的时延，由此可计算出从此节点经其相邻节点到达目的节点的时延和跳数，据此信息可以进一步计算信息素增量。后向蚂蚁到达源节点s后一次路由建立过程完毕。信息素的挥发采用跟SACO相同的形式，当每只蚂蚁搜索完一条路径后，每条边的信息素进行如下更新： （4.3）而： （4.4）式中表示蚂蚁在时刻在边（,）上释放的信息量。Dorigo等人研究出蚂蚁系统的三个变种，它们的区别在于的计算方式（针对最小化问题）。（1）蚁周系统： （4.5）对于蚁周系统来说信息素的释放量，跟蚂蚁建立的路径质量成反比。因此，是用全局的信息来更新信息素浓度，Q是正的常量。对于最大化问题： （4.6）（2）蚁密系统： （4