《毕业设计论文基于蚁群算法的网络多节点路由优化》由会员分享，可在线阅读，更多相关《毕业设计论文基于蚁群算法的网络多节点路由优化（33页珍藏版）》请在金锄头文库上搜索。
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。一个理想的路由选择算法至少应该具备以下几点特征：完整性和正确性，即每个路由器中的路由表都必须给出到所有可能目的节点的下一跳该怎么走，且给出的走法是正确的；简单性，即路由选择的计算不应使网络的通信量增加太多额外的开销；健壮性，主要指当某些节点、链路出现故障不能工作，或故障恢复后投入运行，算法能及时改变路由；公平性，即算法对所有用户都是公平的；最佳性，即以最低的成本实现路由算法。为了降低数据包在网络中的传输开销和时延，要求为数据选择的路径是最短的。这里
