Routing based on ACO(基于蚁群算法的网络路由优化)
基于蚁群算法的网络多点路由的优化与仿真
摘要
网络的动态特性体现在：拓扑结构、流量随时变化；不同链路的带宽、时延和差错率也不相同。因此，研究人员迫切希望找到一种优化算法，能更快速、更有效的适应网络复杂的动态特性，提高网络的效率。
本设计讨论了基于两种不同路由算法的路由协议、蚁群算法基本原理、蚁群优化的一般过程以及简单的蚁群优化SACO。构造出了基于蚁群算法的多点路由优化的一般模型，包括最短路由建立、路由维护与更新、链路中断与修复的一般过程。采用了改进转移概率和信息素更新策略的蚂蚁系统，针对不同的需求（跳数、链路时延、带宽、费用等）进行设计、仿真，寻找出不同的最优路径，对结果进行了对比和分析。设计中还对跳数最少算法中的迭代次数等参数进行不同的设置，对比不同参数下的优化结果，分析参数对仿真结果的影响。
关键词:蚁群算法；最短路径；OSPF协议；链路状态路由算法
Multi-point routing optimization and simulation of the network
based on ant colony algorithm
Abstract
The dynamic characteristic of the network reflects in:its topology structure and flow change all the time;also,bandwidth,error ration and delay of different link differ.Therefore,the researchers hope to find a more rapid and effective optimized algorithm,in order to adapt to this dynamic and complex network,and improve the network's efficiency.
This paper have discussed two kinds of routing protocol based on different routing algorithm,the basic principle of ant colony algorithm,general process of ant colony optimization and Simple ant colony optimization SACO.And then construct the general model of multi-point routing optimization based on ant colony algorithm,including the general process of the seting up of shortest route,routing maintenance and update,break and repairation of the link.This topic use the ant system with the improved transition probability and pheromone update strategy in the algorithm,design and simulate in view of the different demand(hop,link time delay,bandwidth,expenses,etc),looking for and analysing different optimal paths.In the design of the hop least algorithm,we set the parameters,such as iterative times,differently,comparing the optimization results of the simulation under different parameters,and analysing the influence.
Keyword:ant colony algorithm;the shortest path;the OSPF agreement;link state routing algorithm
1绪论
通信网络的迅速发展，新业务的不断出现，使多点通信成为网络必须支持的功能。传统网络中使用一对一的通信协议支持多点协议，数据需要做多个拷贝，分别传送，极大的浪费了网络资源。未来的多媒体通信，将带来大量的多点通信，使用点对点协议将造成网络效率的低下；另外，多媒体通信的业务通常需要达成一定的同步关系，使用点对点协议完成多点通信不再有效；而复用技术的发展使组播在共同的链路上共享带宽成为可能。由于上述原因必须考虑多点路由问题。
由于网络是动态变化的，网络拓扑结构的变化的不可预测性和变化的频繁性和不确定性是网络多点路由问题与其他常见的组合优化问题的根本不同之处，网络流量的随机性和偶然性也是网络动态变化的主要因素。有效快捷的网络路由算法是网路发展的重要问题。
而蚁群算法的出现和广泛应用，提供了多点路由优化设计的新的思想。蚁群算法是一种模拟进化算法，它是在对自然界中真实蚁群的集体行为研究的基础上，由意大利学者M.Dorigo等人首先提出的。M.Dorigo等人充分利用了蚁群搜索食物的过程与著名的旅行商问题（TSP）之间的相似性，通过人工模拟蚂蚁搜索食物的过程（即通过个体之间的信息交流与相互协作最终找到从蚁穴到食物源的最短路径）来求解TSP问题。仿生学家通过大量细致观察研究发现，蚂蚁个体之间是通过一种被称为外激素的物质进行信息传送，从而能相互协作，完成复杂的任务。蚂蚁在运动过程中，能在它所经过的路径上留下该物质，而且蚂蚁在运动过程中能够感知这种物质的存在及其强度，并以此指导自己的运动方向，蚂蚁倾向于朝着这种物质强度高的方向移动。因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。蚁群算法是一种随机搜索算法，与其它模拟进化算法一样，通过候选解组成的群体的进化过程来寻求最优解，该过程包含两个基本阶段：适应阶段和协作阶段。在适应阶段，各候选解根据所积累的信息不断调整自身结构；在协作阶段，候选解间通过信息交流，以期产生性能更好的解。
蚁群算法之所以能引起相关领域研究者的注意，是因为这种求解模式能将问题
求解的快速性、全局优化特征以及有限时间内答案的合理性结合起来。其中，寻优的快速性是通过正反馈式的信息传递和积累来保证的。而算法的早熟性收敛又可以通过其分布式计算特征加以避免，同时，具有贪婪启发式搜索特征的蚁群系统又能在搜索过程的早期找到可以接受的问题解答。这种优越的问题分布式求解模式经过相关领域研究者的关注和努力，已经在最初的算法模型基础上得到了很大的改进和拓展。基于蚁群算法的以上特点，将蚁群算法用于OSPF协议的网络中，根据不同网络的需要寻找最优路径（可以是时延、中间路由器个数或者费用等参数最优化），将是一个非常值得我们去研究的课题。
1.1本设计研究的目的意义
人们生活的现代社会是一个由计算机信息网络、电话通信网络、运输服务网络、能源和物流分配网络等各种网络组成的复杂的网络系统。网络优化的目的就是研究如何有效地计划、控制和管理这个网络系统，使之发挥最大的社会效益和经济效益。网络优化是运筹学的是一个经典和重要的分支，所研究的问题涉及诸多领域，一方面是如何最大限度的节省资源，如最短路径、最小费用等；另一方面是在网络资源有限的情况下如何发挥其最大效益，如最大物流问题、最优资源配置问题等。网络优化问题是一类特殊的组合优化问题，属于NP难问题。对于此类NP问题，传统运筹学的优化方法显得无能为力，寻找、研究、应用启发式智能化的优化方法显得尤为重要。蚂蚁算法就是其中一种有效的启发式智能优化算法。
本设计就是要在掌握蚁群算法的基础上，将其用于网络路由优化问题，根据不同网络的特点和需求，对算法进行相应修改，编写出优化软件。由于这种求解模式能将问题求解的快速性、全局优化特征以及有限时间内答案的合理性结合起来，因而能适应网络各种因素随机变化的的特性，将其用于OSPF协议的工作过程中，可以快速有效的找出其所需的最优路径。最终，实现网络资源的合理利用和高效的数据传输，提高网络的运行速度，这对于互联网今后的快速发展起着重要的促进作用。
1.2本设计的研究现状
蚁群算法诞生于1991年，是一类新颖而前沿的问题求解算法。在算法改进与理论问题的应用领域，这种算法很快就得到了国内外学者们的关注。在国外，学者们提出了不同版本的蚁群算法，进一步地提高算法的性能；同时，他们也把蚁群算法应用到众多复杂的经典理论问题中，包括旅行商、车辆路由、二次指派、工序调度、
背包问题、群组规划等等。在某些具体问题中，蚁群算法的性能更是达到乃至超越了用于该问题的其它经典的求解算法。
国内在最近几年也掀起了一股研究蚁群算法的热潮，与蚁群算法相关的学术著作层出不穷，算法的应用领域得到了不断的拓广，算法的性能也得到了不断的提高。
在工业社会的实际应用领域，蚁群算法的成功正引起了国际上众多企业的关注。EuroBios公司首先把蚁群算法应用于求解现实世界中不同类型的调度问题。同时，AntOptima公司以蚁群算法为工具，成功地开发出多种工业优化的软件工具，例如DYVOIL产品成功地解决了瑞士某企业的车辆燃油分配管理问题；ANTROUTE产品则解决了一些大型连锁超市集团企业的运输车辆调度与路由问题。此外，国外的企业还把蚁群算法应用于大型制造商生产线的设计、平衡的规划、水利设施的建设、数据挖掘、金融现金流的分析与预测等广泛的实际应用领域。
蚁群算法在通信网络领域（特别是解决网络领域问题）的应用受到越来越多的学者的关注。网络信息的分布式性、动态性、随机性和异步性与蚁群算法非常相似，如利用局部信息发现解，间接地通讯方式和随机状态的转换。在网络多点路由优化方面，已经取得了不错的进展。Di Caro和Dorigo已经在相关文献中将蚁群算法应用于网络路由问题，并称这种算法为AntNet。根据网络的不同特点以及路由算法的不同，研究人员提出了各种改进的蚁群算法，提高了算法的性能和在实际中的应用价值。例如，在传感器网络中，充分考虑了网络能量有限的特点，提出了ACRA算法，提高了网络的寿命；高程ACS算法提高了算法的质量和收敛速度，引入蚂蚁回退机制则使得所有蚂蚁都能到达目的节点；最大-最小蚂蚁系统为信息素设置上下限避免了算法出现停滞的现象；基于混沌蚁群算法的路由模型，降低了时间复杂度，避免了蚁群算法陷入局部最优解。此外，还有利用遗传算法和蚁群算法的融合算法进行路由优化算法，WDM网络中基于较少波长的组播路由优化算法等。
但是蚁群算法的研究时间不是很长，还没有形成系统的分析方法和具有坚实的数学理论基础。参数的选择更多的是依靠实验和经验．没有定理来确定，而且它的计算时间偏长，其在理论和实践方面尚存在许多问题需要更加深入的研究和解决。国内直到上个世纪末才有学着开始关注ACO算法，目前对该算法的研究还停留在算法的改进和应用方面。不过蚁群算法具有正反馈、并行计算和强鲁棒性等许多优点，随着研究的深入，蚁群算法将给我们展示一个求解复杂组合优化问题的优秀寻优算
法。如何抽象实际问题，使蚁群算法的求解更接近工程实际是广大蚁群算法研算法理论及其应用的研究必将是—个长期的研究课题。蚁群算法这一新兴的仿生优化算法在路由优化方面必将展现出更加广阔、更加引人注目的发展前景。
1.3本课题要研究与解决的问题
（1）本课题首先要研究基于两种不同路由算法的路由协议：基于距离矢量算法的RIP协议和基于链路状态算法的OSPF协议，其中重点学习OSPF协议的具体工作过程及其特点。
（2）本课题将详细探讨蚁群算法基本原理、蚁群优化的一般过程、SACO算法以及其改进算法。我们知道，使用OSPF协议的路由器在工作过程中首先是通过发送Hello报文等方法与其他路由器建立连接并交换信息（包括链路状态、可达信息等），利用Dijkstra算法构造出网络的拓扑结构，寻找最短路径。然而网络是动态的，它的拓扑结构、流量随时变化，不同链路的带宽、时延也不相同，我们希望能找到一种更快速有效的优化算法，以适应这种动态的、复杂的网络，提高网络的效率。蚁群算法给我们提供了一条很好的思路，它最初的提出正是用于寻找最短路径问题。
（3）在本课题的研究过程中，我们首先不考虑其他链路状态的因素，将最优路径问题简化为仅仅是与中间路由器跳数有关的最短路径问题，则利用蚁群算法计算出的最短路径就是最小跳数的路径。
（4）考虑时延等不同代价的最佳路径，对基本算法做如下改动：根据每条链路信息的不同，考虑时延、带宽等的作用的大小，给每条链路赋予一个不同权值，在计算路径长度时乘上权值（本设计中为了方便以链路的物理长度来代表其时延），修改信息素时加入权值因素的影响，这样得出的最优路径即最少开销的路径。
（5）最后，编写出相应的软件，进行计算机仿真，找出不同代价下的最佳路径，实现多点路由优化。
2路由选择的基本概念
2.1路由技术
路由技术其实是由两项最基本的活动组成，即决定最优路径和传送数据包。其中，数据包的传送相对较为简单和直接，而路径的确定则更加复杂一些。路由算法在路由表中写入各种不同的信息，路由器会根据数据包所要到达的目的地，选择最佳路径把数据包发送到可以到达该目的地的下一台路由器处。路由器之间可以进行相互通信，它们通过传送不同类型的路由更新信息来维护各自的路由表。路由更新信息一般是由部分或全部路由表组成。通过分析其他路由器发出的路由更新信息，路由器可以掌握整个网络的拓扑结构。链路状态广播是另外一种在路由器之间传递的信息，它可以把信息发送方的链路状态及时的通知给其他路由器。
路由器要实现数据转发的功能，至少要完成两方面的内容：①根据数据包的目的地址和网络拓扑选择一条最佳路径，把对应不同目的地址的最佳路径在路由表中；②搜索路由表，决定向哪个端口转发数据，并执行相应的操作。在上面的两方面工作中，前者是选择策略问题，而后者是选路机制问题。
选路策略的实质就是如何确定数据传送的最佳路径，它是通过建立和维护路由表来实现的。选路策略的不同，从本质上讲就是建立和维护路由表的方式不同。事实上，无论是静态路由选择还是各种动态路由选择协议，它们都是围绕选路策略站开的。选路机制实质上就是如何查找路由表，并根据查表的结果把数据转发出去。一般来说，路由器首先搜索匹配的主机地址，如果没有，再搜索匹配的网络地址（可能需要子网掩码），最后搜索默认路由。一旦查到匹配表项，路由器就会把数据从相应的接口发送出去。在具体查找路由表时，可以使用不同的算法，常见的路由查询算法有二进制Trie树算法、路径压缩Trie树算法、多分支Trie树算法、基于前缀长度空间的二分查找法、基于地址区间的二分查找法以及基于硬件的TCAM机制等。衡量这些算法的指标包括时间复杂度（即查表的速度）、空间复杂度（路由表占用内存的大小）、预处理和更新速度（增加、删除、变更路由表条目时，路由表的更新速度）、可扩展性等。路由查询算法的好坏直接影响路由查询的效率。一般来说，很难有哪算法可以同时在上述几个指标上达到最优。选路策略只影响路由表的内容，比如对同一个目的IP地址来说，由于选路策略的不同，最佳路径不能
会不一样，但这并不影响选路机制的执行过程，只会对其执行的结果产生影响。
2.2路由选择算法
路由选择算法是指路由器获得对网络拓扑结构的认知，并为数据包选择正确的传输路径的方法或者策略[2]。一个理想的路由选择算法至少应该具备以下几点特征：①完整性和正确性，即每个路由器中的路由表都必须给出到所有可能目的节点的下一跳该怎么走，且给出的走法是正确的；②简单性，即路由选择的计算不应使网络的通信量增加太多额外的开销；③健壮性，主要指当某些节点、链路出现故障不能工作，或故障恢复后投入运行，算法能及时改变路由；④公平性，即算法对所有用户都是公平的；⑤最佳性，即以最低的成本实现路由算法。为了降低数据包在网络中的传输开销和时延，要求为数据选择的路径是最短的。这里的“最短”在不同场合有着不同的含义，它可以是跳数的多少，物理距离的长短或者时延的大小等。互联网中使用的各种路由选择协议或者算法，其根本目的就是寻找源节点和目的节点之间最短的一条路径，即最短路由。
路由算法的分类标准很多。按照能否根据网络状况的变化而动态调整可以分为静态（非自适应）和动态（自适应）两大类；按照工作的模式可以分为集中式和分布式两大类，前者由路由控制中心集中收集网络拓扑结构信息并计算路由，后者由网络中所有路由器通过交换路由信息，各自独立的计算路由。互联网的复杂性使得当前使用的路由算法主要是动态的、分布式的。目前互联网上的动态路由协议主要基于两种动态分布式路由选择算法：距离矢量路由算法和链路状态路由算法。2.2.1距离矢量路由算法
距离矢量路由算法的基础是分布式的B—F算法。在距离矢量路由中，各个路由器都维持一个距离矢量表，对每个目的节点都有一个对应的表项，包括两部分内容：到该目的节点最短路径上的下一个路由器；到该目的节点的最短路径长度。在工作时，路由器周期性地和相邻的路由器交换路由表中的信息，即向邻居路由器发送路由表的全部或部分。这种信息是由若干（v，d）对组成的表项，其中，v代表矢量，指出该路由器可以达到的目的地；d表示去往目的地v的距离。各个路由器根据收到的信息，按照分布式B—F算法重新计算到各目的节点的距离，并对自己的路由表进行修正。这种一步一步的处理使得每一个路由器都可以知道其他路由器的情况，并形成关于网络“距离”的累积透视图。
2.2.2链路状态路由算法
链路状态路由算法也被称为最短路径优先SPF算法，它的提出主要是为了克服距离矢量路由算法所存在的收敛速度慢，难以适应大型网络等缺陷。
链路状态路由算法的基本步骤如下：
（1）每一个路由器启动后，首先执行对相邻节点的发现工作，并获得它们的地址，这个过程在具体实施时是通过发送特殊的Hello分组实现的；
（2）各路由器主动测试到每一个相邻路由器的链路时延或成本，并根据测试结果设置相关的链路的状态；
（3）各路由器构造自己的L—S（链路状态）信息包，L—S信息的内容包括本路由器的标号、本路由器的邻居路由器的链路状态、该L—S信心包的序号和生存时间等；
（4）各路由器向所有参与SPF的路由器广播其L—S信息，可以周期性地发送，也可以在链路状态发生变化时发送；
（5）每个路由器的收听到所有的L—S信息后，可以构造或更新表示整个网络拓扑结构的图G（V，E），顶点V表示路由器，边E表示连接路由器的链路，这时路由器就可以用Dijkstra算法从图G中计算出到所有目的路由器的最短路径，也就是构造以自己为根节点的SPF树。
对比距离矢量路由算法和链路状态路由算法，总结它们各自特点如下：距离矢量路由算法实现简单，对路由器处理能力要求不高，但收敛速度慢，适用于规模较小和拓扑结构变化不快的网络；链路状态路由选择算法能够及时反映网络拓扑结构的变化，收敛速度很快，适应于规模较大和拓扑变化较快的网络，但由于每一个路由器均需要实时形成全网的拓扑图及构造以自己为节点的树，所以对处理器性能要求比较高，另外，路由信息是以广播的形式传播的，占用的网络带宽比较多。2.3路由协议
路由协议可以分为内部网关协议IGP和外部网关协议EGP两大类。简单的定义是，内部网关协议是用于自治系统内部的动态路由协议，包括RIP、OSPF等；而外部网关协议是用于自治系统之间的拓扑信息交换的路由协议，包括BGP等。本设计将基于OSPF协议，下面将详细讨论该协议。
开放最短路径优先协议OSPF[17]是一种基于区域（路由域）实现的、建立在
Dijkstra算法和链路状态算法基础之上的内部网关动态路由协议。最初提出OSPF 主要目的是为了距离矢量路由协议RIP等所存在的收敛速度慢、采用固定度量以及不能动态负荷平衡等缺陷。目前OSPF由于其优异的性能，已经成为应用最广泛的内部网关协议之一。
OSPF的基本思想如下：
（1）每个OSPF路由器都维护一个用于跟踪网络状态的链路状态数据库（Link State Data-Base，LSDB)。数据库中的内容是反映路由器状态的各种链路状态通告（Link State Advertisement，LSA），这些状态包括路由器可用接口、已知可达路由和链路状态信息，各OSPF路由器都会主动测试所有与之相邻的路由器的状态，并根据测试结果设置相关链路状态。利用LSDB，路由器就可以得到一张整个网络拓扑结构的图。在图论中,OSPF计算出的路由也是一种无环路的路由?为了减小路由器的LSDB，不同的LSA又有不同的作用范围，这就使得OSPF具有一定的路由层次性。这种路由层次性是用划分区域的方法来实现的。OSPF的管理距离是110。最佳路径的度量有：①路径长度—它是最常用的路由度量，一般定义为跳数，即从源端到目的端所经过的路由器个数；②可靠性—在路由算法中指网络链接的可依赖性，有些网络链接可能比其他的失效的更多，网络失效后，一些网路链接可能比其他的更容易或更快修复，通常是网管给网络链接赋以度量值；③时延—路由时延指分组从源端到达目的端所花时间，影响时延的因素有中间的网络链接的带宽、经过每个路由器的端口队列、所有中间网络链接的拥塞程度和物理距离等，时延是多个变量的混合体，是个比较常用和有效的度量；④带宽—指链路可用的流通容量（通常以网速来表示），虽然带宽是链路可获得的最大吞吐量的基本保证，但是通过具有较大链路带宽的路由不一定比经过较慢链路路由更好；⑤负载—指诸如路由器等网络资源的繁忙程度，负载可能涉及很多方面的的计算，包括CPU使用情况和每秒处理分组数；⑥通信开销。
（2）OSPF基于Dijkstra算法和自治系统中路由器的链路状态进行路由计算。路由器在计算路由表时要借助于Dijkstra算法建立起来的最短路径树。路由器把自己作为树根，用该树跟踪系统中每个目标的最短路径，并由此计算出区域内路由；接着，通过查看区域间LSA计算到自治系统内部其他区域目的地的路由；最后，检查自治系统外部LSA，计算到自治系统外部目的地的路由。路由表更新通过LSA发
送给在同一个路由域内的所有其他路由器。
OSPF协议工作过程：
OSPF的工作过程可以分为三个互相关联的主要部分：称为“呼叫”（Hello）协议、近邻关系建立和“可靠洪泛”机制。呼叫协议、近邻关系建立和可靠洪泛机制完成了OSPF包的交互过程，并最终实现同一个路由域中所有路由器的LSDB一致。与RIP等路由协议不同，OSPF的各类报文都是直接封装在IP报文中的，不需要使用传输层协议（TCP、UDP等）的支持。OSPF有五种报文：Hello报文（发现及维持邻居关系，选举DR，BDR）、DD报文（本地LSDB的摘要）、
LSR报文（向对端请求本端没有或对端的更新的LSA)、LSU报文（向对方发送其需要的LSA）、LSAck报文（收到LSU之后，进行确认）。
OSPF路由协议针对每一个区域分别运行一套独立的计算法则，对于ABR来说，由于一个区域边界路由器同时与几个区域相联，因此一个区域边界路由器上会同时运行几套OSPF计算方法，每一个方法针对一个OSPF区域。下面对OSPF协议运算的全过程作一概括性的描述。
当一个OSPF路由器初始化时，首先初始化路由器自身的协议数据库，然后等待低层次协议（数据链路层）提示端口是否处于工作状态。
如果低层协议得知一个端口处于工作状态时，OSPF会通过其Hello协议数据包与其余的OSPF路由器建立交互关系。一个OSPF路由器向其相邻路由器发送Hello数据包，如果接收到某一路由器返回的Hello数据包，则在这两个OSPF路由器之间建立起OSPF交互关系，这个过程在OSPF中被称为adjacency。在广播性网络或是在点对点的网络环境中，OSPF协议通过Hello数据包自动地发现其相邻路由器，在这时，OSPF路由器将Hello数据包发送至一特殊的多点广播地址，该多点广播地址为ALLSPFRouters。在一些非广播性的网络环境中，我们需要经过某些设置来发现OSPF相邻路由器。在多接入的环境中，例如以太网的环境，Hello协议数据包还可以用于选择该网络中的指定路由器DR。
一个OSPF路由器会与其新发现的相邻路由器建立OSPF的adjacency，并且在一对OSPF路由器之间作链路状态数据库的同步。在多接入的网络环增中，非DR 的OSPF路由器只会与指定路由器DR建立adjacency，并且作数据库的同步。OSPF 协议数据包的接收及发送正是在一对OSPF的adjacency间进行的。
OSPF路由器周期性地产生与其相联的所有链路的状态信息，有时这些信息也被称为链路状态广播LSA（Link State Advertisement）。当路由器相联接的链路状态发生改变时，路由器也会产生链路状态广播信息，所有这些广播数据是通过Flood 的方式在某一个OSPF区域内进行的。Flooding算法是一个非常可靠的计算过程，它保证在同一个OSPF区域内的所有路由器都具有一个相同的OSPF数据库。根据这个数据库，OSPF路由器会将自身作为根，计算出一个最短路径树，然后，该路由器会根据最短路径树产生自己的OSPF路由表。
OSPF路由协议通过建立交互关系来交换路由信息，但是并不是所有相邻的路由器会建立OSPF交互关系。下面将OSPF建立adjacency的过程简要介绍一下。
OSPF协议是通过Hello协议数据包来建立及维护相邻关系的，同时也用其来保证相邻路由器之间的双向通信。OSPF路由器会周期性地发送Hello数据包，当这个路由器看到自身被列于其它路由器的Hello数据包里时，这两个路由器之间会建立起双向通信。在多接入的环境中，Hello数据包还用于发现指定路由器DR，通过DR来控制与哪些路由器建立交互关系。
两个OSPF路由器建立双向通信这后的第二个步骤是进行数据库的同步，数据库同步是所有链路状态路由协议的最大的共性。在OSPF路由协议中，数据库同步关系仅仅在建立交互关系的路由器之间保持。
OSPF的数据库同步是通过OSPF数据库描述数据包（Database Des cription Packets）来进行的。OSPF路由器周期性地产生数据库描述数据包，该数据包是有序的，即附带有序列号，并将这些数据包对相邻路由器广播。相邻路由器可以根据数据库描述数据包的序列号与自身数据库的数据作比较，若发现接收到的数据比数据库内的数据序列号大，则相邻路由器会针对序列号较大的数据发出请求，并用请求得到的数据来更新其链路状态数据库。
我们可以将OSPF相邻路由器从发送Hello数据包，建立数据库同步至建立完全的OSPF交互关系的过程分成几个不同的状态，分别为：
Down：这是OSPF建立交互关系的初始化状态，表示在一定时间之内没有接收到从某一相邻路由器发送来的信息。在非广播性的网络环境内，OSPF路由器还可能对处于Down状态的路由器发送Hello数据包。
Attempt：该状态仅在NBMA环境，例如帧中继、X.25或ATM环境中有效，
表示在一定时间内没有接收到某一相邻路由器的信息，但是OSPF路由器仍必须通过以一个较低的频率向该相邻路由器发送Hello数据包来保持联系。
Init：路由器的各个接口发送Hello数据报文到其他运行OSPF的路由器，当邻接路由器收到第一个Hello数据报文，这时就进入Init状态。在该状态时，OSPF 路由器已经接收到相邻路由器发送来的Hello数据包，但自身的IP地址并没有出现在该Hello数据包内，也就是说，双方的双向通信还没有建立起来。
2-Way：这个状态可以说是建立交互方式真正的开始步骤。在这个状态，路由器看到自身已经处于相邻路由器的Hello数据包内，双向通信已经建立。指定路由器及备份指定路由器的选择正是在这个状态完成的。在这个状态，OSPF路由器还可以根据其中的一个路由器是否指定路由器或是根据链路是否点对点或虚拟链路来决定是否建立交互关系。
Exstart：这个状态是建立交互状态的第一个步骤。在这个状态，路由器要决定用于数据交换的初始的数据库描述数据包的序列号，以保证路由器得到的永远是最新的链路状态信息。同时，在这个状态路由器还必须决定路由器之间的主备关系，处于主控地位的路由器会向处于备份地位的路由器请求链路状态信息。
Exchange：在这个状态，路由器向相邻的OSPF路由器发送数据库描述数据包来交换链路状态信息，每一个数据包都有一个数据包序列号。在这个状态，路由器还有可能向相邻路由器发送链路状态请求数据包来请求其相应数据。从这个状态开始，我们说OSPF处于Flooding状态。
Loading：在loading状态，OSPF路由器会就其发现的相邻路由器的新的链路状态数据及自身的已经过期的数据向相邻路由器提出请求，并等待相邻路由器的回答。
Full：这是两个OSPF路由器建立交互关系的最后一个状态，在这时，建立起交互关系的路由器之间已经完成了数据库同步的工作，它们的链路状态数据库已经一致，这个状态称为“全毗邻状态”，每台路由器保存着一张毗邻路由器列表称为“毗邻数据库”。两个OSPF路由器数据库同步是所有链路状态路由协议的最大共性。在OSPF路由协议中，数据库同步关系仅仅建立在交互关系的路由器之间保存。OSPF协议的优点：
（1）OSPF是真正的LOOP-FREE(无路由自环)路由协议?源自其算法本身的优
点?(链路状态及最短路径树算法)
（2）OSPF收敛速度快:能够在最短的时间内将路由变化传递到整个自治系统?
（3）提出区域(area)划分的概念,将自治系统划分为不同区域后,通过区域之间的对路由信息的摘要,大大减少了需传递的路由信息数量?也使得路由信息不会随网络规模的扩大而急剧膨胀?
（4）将协议自身的开销控制到最小?
1)用于发现和维护邻居关系的是定期发送的是不含路由信息的hello报文,非常短小?包含路由信息的报文时是触发更新的机制?(有路由变化时才会发送)?但为了增强协议的健壮性,每1800秒全部重发一次?
2)在广播网络中,使用组播地址(而非广播)发送报文,减少对其它不运行ospf 的网络设备的干扰?
3)在各类可以多址访问的网络中(广播,NBMA),通过选举DR,使同网段的路由器之间的路由交换(同步)次数由O(N*N)次减少为O(N)次?
4)提出STUB区域的概念,使得STUB区域内不再传播引入的ASE路由?
5)在ABR(区域边界路由器)上支持路由聚合,进一步减少区域间的路由信息传递?
6)在点到点接口类型中,通过配置按需播号属性(OSPF over On Demand Circuits),使得ospf不再定时发送hello报文及定期更新路由信息?只在网络拓扑真正变化时才发送更新信息?
（5）通过严格划分路由的级别(共分四极),提供更可信的路由选择?
（6）良好的安全性,ospf支持基于接口的明文及md5验证?
（7）OSPF适应各种规模的网络,最多可达数千台?
3蚁群算法
3.1蚁群优化的原理分析
AC O是受自然界中真实蚁群的集体觅食行为的启发而发展起来的一种基于群体的模拟进化算法，属于随机搜索算法。M.Dorigo等人充分利用了蚁群搜索食物的过程与著名TSP问题之间的相似性，通过人工模拟蚁群搜索食物的行为来求解TSP问题。从下面的的“双桥实验”可以看出，像蚂蚁这类社会性动物，虽然个体的行为极其简单，但由这些简单个体所组成的蚁群却表现出极其复杂的行为特征。如蚁群除了能够找到蚁巢与食物源之间的最短路径外，还能适应环境的变化，即在蚁群运动的路线上突然出现障碍物时，蚂蚁能够很快地重新找到最短路径。蚁群是如何完成这些复杂任务的呢?仿生学家经过大量地观察、研究发现，蚂蚁在寻找食物时，能在其经过的路径上释放一种蚂蚁特有的分泌物一外激素，使得一定范围内的其它蚂蚁能够感觉到这种物质，且倾向于朝着该物质强度高的方向移动。因此，蚁群的集体行为表现为一种信息正反馈现象:某条路径匕经过的蚂蚁数越多，其上留下的外激素的迹也就越多(当然，随时间的推移会逐渐蒸发掉一部分)，后来蚂蚁选择该路径的概率也越高，从而更增了该路径上外激素的强度。蚁群这种选择路径的过程被称之为自催化行为，由于其原理是一种正反馈机制，因此也可将蚁群的行为理解成所谓的增强型学习系统。
接下来简单解释一下蚁群发现最短路径的原理和机制。
在蚁巢和实物之间有两条道路，Nest-A-B-D-Food和Nest-A-C-D-Food，其长度分别为4和6。单位时间内蚂蚁可移动一个单位长度的距离。开始时所有路径上都没有外激素。
在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 上外激素的量。随着该过程的继续，两条道路上外激素数量的差距将越来越大，直至绝大多数蚂蚁都选择了最短的路径。正是由于一条道路要比另一条道路短，因此，在相同的时间间隔内，短的路线会有更多的机会被选则。
3.2简单蚁群优化SACO
介绍蚁群算法前我们首先来介绍以下双桥实验：
在该实验中，巢穴和食物之间用等长度的双分支桥连接。最初桥的两个分支都没有任何信息素，过了一段时间之后，尽管这两个分支长度相等，还是有一个分支被绝大多数蚂蚁所选择。原因是随机的路径选择促使所随机选择到的分支上信息素浓度积累。通过该实验，研究人员建立了一个形式化的模型来描述蚂蚁选择路径的过程。建模过程中，他们假设各蚂蚁分泌等量的信息素且不考虑信息素的挥发，得出蚂蚁在t+1时刻选择路径A 的概率如下所示（其中)(n t A 和)(t n B 分别表示在t 时刻路径A 、路径B 上所经过的蚂蚁数量）
)1(1))(())(())(()1(+?=++++=+t P t n c t n c t n c t P B B A A A ααα
（3.1）
式中，c 代表未开发路径（不含信息素的路径分支）对蚂蚁的吸引度，α表示蚂蚁选择路径的过程中受信息素的影响程度。α的值越大，蚂蚁选择高信息素浓度路径的可能性越大，即便两条路径的信息素浓度差别很小。c 越大，则需要越高的信息素浓度来影响蚂蚁的下一步选择。实验表明，当202≈≈c 和α时，该概率模型与实际相符。
我们以常见的寻找图中两节点间最短路径问题为例，G=（V ，E ），其中V 表示图节点的集合，E 表示图中边的集合。图中共有||V n G =个节点，k L 表示蚂蚁k 所经历的路径的长度—两节点间跳转边的数量。对于每个边（i ，j ），都赋予了相应的信息素浓度ij τ。
对于SACO [21]来说，每个边地信息素浓度都被初始化为一个小的随机值）
（0ij τ。严格来讲，初始时每个边应该不含信息素，蚂蚁随机的选择路径。根据上述算法，给
每个边的信息素浓度一个小的随机值更容易实现。每个蚂蚁k （k=1,2，???,k n ）都被置到源节点。对于SACO 的每次迭代，每只蚂蚁逐渐建立一条到达终节点的路径。在每个节点，蚂蚁都会进行决策选择下一段路径。如果蚂蚁k 当前节点是i ，那么它选择下一结点j 的概率为
???????∈=∑∈其他如果,0j ,)()()(k allowed j ij ij k ij allowed t t t p k ααττ（3.2）
式中k allowed 是对于蚂蚁k 来说，跟节点i 相连接的可选节点的集合。如果蚂蚁k 在节点i 时，k allowed φ∈，那么把节点i 加入到k allowed 中，这么做会导致路径中有环出现，而这些环将会在形成完整路径后去除。
上式中α是一个正的常量，用于放大信息素浓度的影响。太大的α会过度增大信息素的影响，尤其是初期随机的信息素浓度，从而会导致算法快速收敛到次优路径。
一旦所有蚂蚁到达终结点，并去除了路径中的环，每只蚂蚁会沿原路径回到源
节点，并沿途在每个边（i，j）上释放一定的信息素k ij τ?，其中）
（t L k 是该路径第t 步那段路径的长度：
k ij τ?）
（t L 1
k ∝（3.3）即)
()()1(1
t t t k n k k ij ij ij ∑=?==+τττ（3.4）式中k n 表示蚂蚁的总数量。
由上式可知，一条边的信息素浓度跟该边所在的路径的优良程度成正比—路径
越短越优。计算出的所应释放的信息素量k ij τ?代表相应的路径的优良度。对于SACO，
解（建立的路径）的优良简单地表示为该路径的长度（也就是经历的边地数量）的倒数。而其他的测量度同样适用，比如所经历每条边所带来的开销，或者路径的物
理长度。一般来说，用）（t x k 表示时刻t 的解，用f（）（t x k ）表示解的估量。如果
k τ?不与解的质量成比例，且所有的蚂蚁释放相同的信息素量，那么仅仅是路径的
长度影响（短的返回时间造成信息素释放频率增大）蚂蚁倾向于选择短路径。由此我们得出蚂蚁算法中两种形式的解估量：隐式估量（路径长度的差异造成蚂蚁间的相互影响）、显示估量（信息素的释放量跟路径的优良程度成正比）。
但是我们应该注意到，这种决策信息仅限于蚂蚁的局部环境，SACO适用于简单图和蚂蚁数量较少的情况，这样大多能找到最短路径。但是当图较大时，算法变得不鲁棒，对参数敏感，性能较差。此外，对于蚂蚁数目很多的情况，可能导致算法不收敛。
对于复杂的图来说，信息素的挥发变得更为重要。当ρ=0时（信息素不挥发），算法不收敛；当信息素挥发过多（ρ过大）会导致算法收敛到次优路径。
对于较小的α，算法一般可以收敛到最短路径，对于复杂问题来说，大的α会导致更差的收敛性能。
3.3蚁群算法的主要特点
ACO算法的主要特点概括如下：
1）采用分布式控制，不存在中心控制;
2）每个个体只能感知局部的信息，不能直接使用全局信息;
3）个体可改变环境，并通过环境来进行间接通讯(Stigmergy机制);
4）具有自组织性，即群体的复杂行为是通过个体的交互过程中突现出来的智能;
5）是一类概率型的全局搜索方法，这种非确定性使算法能够有更多的机会求得全局最优解;
6）其优化过程不依赖于优化问题本身的严格数学性质，诸如连续性、可导性，及目标函数和约束函数的精确数学描述;
7）是一类基于多主体(MultiA gent)的智能算法，各主体间通过相互协作来更好的适应环境;
8）具有潜在的并行性，其搜索过程不是从一点出发，而是同时从多个点同时进行。这种分布式多智能体的协作过程是异步并发进行的，分布并行模式将大大提高整个算法的运行效率和快速反应能力。
4基于蚁群算法的网络多点路由的优化与仿真
4.1网络路由优化问题的描述
网络是指把某些元件有目的的、按一定形式连接起来、完成特定任务的总体。从抽象的数观点来看，网络实质上是一个赋权的有向图，它由节点和连接这些节点的弧及其方向组成。自然界和人类社会中的大量事物及事物之间的相互关系(例如物质结构、城市规划、交通运输、信息的传递、工作的调配、事物关系等等)都可以用点与线连接起来的网络图来描述。网络图是从实际模型中抽象出来的，因此可以根据问题的实际需要给弧和节点赋予一个数来表明它所对应元件的不同物理意义。这个具有特殊意义的数，我们称之为节点或弧的权。例如，在公路运输网络中，弧的权可以为路的长度或单位长度的运费；在供水网络系统中，弧的权可以是水流量或水管的直径；在电网络中，弧的权可以为元件的电阻、电压或电流等。网络最短路径是在网络图中寻求边权和最小的最小路。而网络中的这个权可以是链路的带宽、时延、开销等，或者它们的综合。
所谓的网络路由优化问题是指在一个网络中，要求在某些约束条件下找出从节点A到B之间的最佳路由，即是在某些含义下的最佳路由（即上面所说的加权最优值）。目前已经有许多智能化算法，如遗传算法、模拟退火算法、神经网络等用于网络路由优化，已取得较好的结果。
4.2基于蚁群算法来选择路由算法的思想的概述
通过前面对蚁群算法和网络优化问题的研究我们发现，可以将实际中的路由选择问题抽象成求最短路径问题的模型，进而利用蚁群算法求出最佳路径。该模型如下：
用一种控制报文(又称蚂蚁)来搜集路径信息进行路由选择。本文用移动代理来模拟蚂蚁,分为两种,即前向蚂蚁F ant和后向蚂蚁B ant,并通过移动代理的复杂交互来决定路由。用前向蚂蚁（表示从源节点到目的节点的移动代理）搜集从源节点到目的节点的路径信息(包括端到端的延迟、所经过的跳数等);后向蚂蚁（表示从目的节点返回到源节点的移动代理）据此来改变所经过的各个节点的路由信息。本文在研究过程中将问题简化，用端到端所经过的跳数来表示信息素值（时延等可以利用对边进行权值的设定来实现）。将网络中各节点的路由表用用一种概率表表示，其中概率表示信息素强度，即信息素表。
初始状态时，所有路径上的信息素均匀分布，蚂蚁不断对信息素进行更新，信息素本身也在随着时间不断减少。从源点发送一组蚂蚁，按上面的规则进行移动，蚂蚁可以遍历所有节点，并且蚂蚁能够记住所经过路径的信息，包括跳数和时延，并最终到达目的节点。显然走路径短的蚂蚁最先到达目的节点，目的节点只接收最先到达的蚂蚁。最先到达终点的蚂蚁（即全局最优蚂蚁）按原路径返回，并修改沿途节点的路由表（信息素表），增大相应边上的信息素浓度（即增大选择该路径的概率）。如此不断地迭代运算，算法将收敛于最短路径。
为了完成建立最优路径的任务，蚂蚁拥有如下属性和特点：1）蚂蚁有记忆功能来保存建立的路径信息。该记忆主要用于保证满足约束条件，比如每个节点只允许访问一次。该记忆还用于按原路径返回，来释放信息素，增强对应边上的信息素浓度。2）蚂蚁为每个状态决定一些可选的邻节点。其中包括所有的从当前节点有效转移的可达节点。之后蚂蚁进入一个新的状态（部分解）。3）每只蚂蚁都被分配一个初始状态，对应初始节点。4）每只蚂蚁都对应一个或多个终止条件，终止条件包括路径达到限定的最大节点数、找到可接受的解、或者到达终节点。5）每只蚂蚁依据概率转移规则从可选邻节点中选取下一结点。6）每只蚂蚁都拥有修改所经历路径上的信息素浓度的能力，作为与其他蚂蚁通信的方式。
4.3基于蚁群算法的路由优化具体过程
蚂蚁系统在以下方面改进简单蚁群优化算法：增加启发式信息，改变转移概
率k
p；增加禁忌表，来增加记忆功能。因此，本课题在研究过程中将采用蚂蚁系统ij
算法，并基于OSPF协议进行路由优化。
4.3.1最优路径的建立
在基于蚁群算法的最优路径建立过程中，每个节点包含一个缓存器，存放着近学习到的和用过的路由信息。源节点s要发送数据到目的节点d，它首先在自己的路由表里查找是否存在一条到d的路由。如果没有到d的路由信息时，就进行路由发现过程。具体过程如下:
①每个节点初始化连接邻居节点链路的信息素；
②源节点产生m只前向蚂蚁；
③第k只前向蚂蚁所在的当前节点i首先检查路由表中是否有到目的节点d的路径，如果有则前向蚂蚁单播，否则前向蚂蚁按概率选择其邻居节点j，并且在前
路由算法分类比较
路由算法是路由协议必须高效地提供其功能，尽量减少软件和应用的开销。 路由器使用路由算法来找到到达目的地的最佳路由。 关于路由器如何收集网络的结构信息以及对之进行分析来确定最佳路由，有两种主要的路由算法：总体式路由算法和分散式路由算法。采用分散式路由算法时，每个路由器只有与它直接相连的路由器的信息——而没有网络中的每个路由器的信息。这些算法也被称为DV（距离向量）算法。采用总体式路由算法时，每个路由器都拥有网络中所有其他路由器的全部信息以及网络的流量状态。这些算法也被称为LS（链路状态）算法。 收敛是在最佳路径的判断上所有路由器达到一致的过程。当某个网络事件引起路由可用或不可用时，路由器就发出更新信息。路由更新信息遍及整个网络，引发重新计算最佳路径，最终达到所有路由器一致公认的最佳路径。收敛慢的路由算法会造成路径循环或网络中断。 路由算法的核心是路由选择算法，设计路由算法时要考虑的技术要素有： 1、选择最短路由还是最佳路由； 2、通信子网是采用虚电路操作方式还是采用数据报的操作方式； 3、采用分布式路由算法还是采用集中式路由算法； 4、考虑关于网络拓扑、流量和延迟等网络信息的来源； 5、确定采用静态路由还是动态路由。 各路由算法的区别点包括：静态与动态、单路径与多路径、平坦与分层、主机智能与路由器智能、域内与域间、链接状态与距离向量。 链接状态算法（也叫做短路径优先算法）把路由信息散布到网络的每个节点，不过每个路由器只发送路由表中描述其自己链接状态的部分。 距离向量算法（也叫做 Bellman-Ford算法）中每个路由器发送路由表的全部或部分，但只发给其邻居。 也就是说，链接状态算法到处发送较少的更新信息，而距离向量算法只向相邻的路由器发送较多的更新信息。 metric是路由算法用以确定到达目的地的最佳路径的计量标准，如路径长度。
流线优化模型与算法研究及应用
配套的处理方式；果蔬采后商品化处理量几乎达到了100％，形成了完整的果蔬冷链体系。而我国的产地基础设施不完善，未能解决分选、分级、预冷、冷藏运输和保鲜等采后果蔬的处理问题。我国果蔬冷链存在许多问题：产地预冷环节薄弱；冷藏运输工具落后；冷库发展水平低；缺乏有影响力的第三方冷链物流。我国果蔬冷链发展水平要赶上发达国家还有较长的路要走。 要完善我国的果蔬冷链业，除了大力研发性价比合理、符合国情的相关冷链设备、设施以外；还需要全面的对整个果蔬冷链过程中存在的影响果蔬产品质量的风险因素进行分析和评价，从而一一破解；更需要系统地梳理整个果蔬冷链链条，是指实现协同化，构建果蔬冷链质量质量保障体系。这样才能真正确保果蔬产品的质量安全，确保千万消费者食用上安全放心的果蔬产品。 流线优化模型与算法研究及应用 张锦*（交通与物流学院） 1 研究背景 目前我国物流产业正处于高速发展期，理论体系与应用研究正在不断完善。物流活动的目的就是使物流服务来满足物流需求，即通过仓储、加工、运输、配送、包装、装卸搬运等活动来满足社会经济活动中供应商、制造商、零售商、消费者等需求方的对物的移动、储存与服务的需求。在宏观层面的区域及城市经济和微观层面的制造、贸易、消费等典型社会经济活动中的物流活动可抽象为具有特定需求的空间结构，称作物流需求网络。 在物流系统中，由若干特定的点、线和特定的权构成的，反映物流服务与需求关系的供需网络称之为流线网络，它具有以下典型特征。 1．反映了仓储、加工、运输、配送、包装、装卸搬运等物流服务与需求方在物品数量、到达时间、物流费用等方面的物流需求间的供需关系。 2．具有嵌套、多层、多级、多维、多准则、拥塞等典型的超网络结构特征，并且具有连接供需两个物流网络的超网络结构。 3．当实际需求为特定值时，物流服务追求的目标为用恰当的费用，在恰当的时间把恰当数量的恰当物品，经恰当的路线送到恰当的地点。 物流供应网络与物流需求网络之间的关系可由超网络结构进行刻画，用匹配度刻画物流服务与物流需求之间的适应程度。 2 国内外研究现状 目前，国内外学者对流线的组织与优化问题研究较少，与此问题相关的内容包括物流网络、物流网络分配、动线优化、超网络理论与应用、变分不等式算法及其在供应链网络中的应用等内容。 2.1 物流网络研究现状 国外的学者大都倾向从微观的企业角度去研究物流网络的资源配置和协调问题,如物流基础设施、市场竞争机制以及配送运输等问题。这类研究大多利用数学规划法、系统仿真法、启发式 *作者简介：张锦，男，教授。
基于数学模型的网络优化方法研究
基于数学模型的网络优化方法研究 赵鹏 通信一团技术室 摘 要 为了提高网络链路的利用率，解决网络传输中的最大流问题，该文利用建立数学模 型的方法来求解网络的传输路径，研究了基于路径的网络优化方法。该方法能够极大地提高网络的链路利用率，从而降低网络的拥塞，使得网络的性能得到较大改善。 关键词 网络优化 最大流 数学模型 1 引言 随着网络技术的进步和人们对多媒体综合业务需求，传统的数据网络逐渐转向多媒体网络，在这过程中，除了相关服务以外，我们还面临许多极具战性的网络设计和优化问题。网络优化的目标是提高或保持网络质量，而网络质量是各种因素相互作用的结果，随着网络优化工作的深入开展和优化技术的提高，优化的范围也在不断扩大。 在计算机网络优化设计中，各条链路的容量分配和各节点间的路由选择是两个重要问题。在给定网络拓扑结构和各节点间传输流量的条件下，如何确定各条链路的容量大小和选择各节点间的最佳路由，使整个网络成本费用最低并能满足规定的性能指标呢？ 许多网络优化的文献，研究针对CDMA 网络、GPRS 网络、GSM 网络、PHS 网络等具体网络在投入运行后，对网络进行参数采集、数据分析，找出影响网络质量的原因，通过技术手段或参数调整使网络达到最佳运行状态，涉及到交换网络技术、无线参数、小区参数配置、信令和设备技术等方面。 本文针对目前许多网络传输链路和网络设备没有得到充分利用，从而影响网络性能的问题，利用网络优化方法从理论上进行分析，研究了用于提高网络链路利用率的基于路径的网络优化方法，该方法能够充分地利用网络链路进行流量传输，从而改善网络的整体性能。 2 网络优化理论 很多情况下可以将网络优化问题转化成数学问题进行研究和分析。从根本上讲，优化问题包含三个基本要素： 决策变量集合或向量：n R x ∈（本文，x 代表在一条或多条路径上的流量） 目标函数R R x f n →:)( 一组约束条件g(x)和h(x)，用来定义x 的范围。 解决优化问题实际上就是找出一个点x*，使得f(x)最大化或最小化。 典型的网络优化问题包含找出一组路由和该路由上的流量值以便达到最大或最小化目标函数的目的。目标函数可以代表最大链路利用率、平均延迟或其他指标。 基于路径的问题首先要计算出网络流可能流经的路径，要最大限度的利用网络链路，同时路径上的流量不能超过链路容量。 对于基于路径的网络优化问题可以简单表示成： max f(x) s.t. ∑∈=P p p b x
计算机网络的路由算法与性能优化研究
计算机网络的路由算法与性能优化研究本文从网络收集而来，上传到平台为了帮到更多的人，如果您需要使用本文档，请点击下载按钮下载本文档（有偿下载），另外祝您生活愉快，工作顺利，万事如意！ 随着社会的发展需要，计算机单一的发展方式已经跟不上时代的发展要求，为了更好的促进社会的发展，人们尝试将计算机网络与电话、电报等联系在一起，并逐步发展到今天。有线网络和无线网络被广泛应用在各行各业中，已经覆盖全球范围。现在越来越多的人在使用计算机网络，它给人们的生产和生活都带来了极大的方便。计算机网络广泛应用的同时，也在不断的进行技术的更新和设施的完善，计算机运行的速度与过去相比，已经非常高。视频点播对数据的传输速率具有较高的要求，而语言的传输速率则不能够高于临界值，在现今发展的计算机网络中已经被成功的解决，计算机网络路由的应用起着关键性的作用，对计算机网络的发展具有非常重要的意义。 1 计算机网络路由器的概述 计算机网络应用日益普及，已经成为人们工作和生活中不可或缺的部分。正是因为如此，互联网中IP 服务已经无法满足人们的需求，因此，我们应该尽快提高互联网的服务质量，而计算机网络路由正是计算
机领域发展的关键，加强对计算机网络路由的研究，促进计算机网络的发展。目前计算机网络的发展规模越来越大，网络信息的传播需要依赖于网络，而现今社会的信息流量越来越大，对网络路由的承载能力也有了更高的要求，而路由算法的复杂化也给计算机网络的发展带来了挑战。路由算法的作用是为了寻找最佳路径对数据信息进行传递，从而提高网络资源的利用率。计算机路由的选择也是一个非常复杂的过程，要考虑计算机网络组合优化的问题，保证计算机网络性能的高效和稳定。 计算机网络路由优化开始于对计算机网络的研究，并逐步渗透到计算机网络的领域中。为了提高计算机网络资源的利用率，减小信息传输的时延，在计算机网络路由选择的过程中，根据其网络的拓扑结构和链路的容量选择最佳的传输路径来达到提高资源利用率的目的。近几年来，随着计算机技术的发展，大型网络系统应用越来越广泛，使得计算机网络路由器的分析计算变的更加的复杂。对于计算机网络来说，在广域网中，实时流必须面向所连接的路由，且在传输的过程中要连接终端用户，且必须按照正确的顺序和逻辑关系进行数据的传输，保证计算机网络的性能。终端用户之间需要一条网络路径，这条路径需要包括
计算机网络复习提纲-第五章
第5章网络层 5.1网络层概述 网络层负责数据包经过多条链路、由信源到信宿传递过程，并保证每个数据包能够成功和有效率地从出发点到达目的地。为实现端到端的传递，网络层提供了两种服务：线路交换和路由选择。线路交换是在物理链路之间建立临时的连接，每个数据包都通过这个临时链路进行传输；路由选择是选择数据包传输的最佳路径，在这种情况下，每个数据包都可以通过不同的路由到达目的地，然后再在目的地重新按照原始顺序组装起来。 网络层是通信子网的最高层，对上层用户屏蔽了子网通信的细节，如子网类型、拓扑结构、子网数目，向上层提供一致的服务、统一的地址。 5.1.1网络层功能 (1)为传输层提供建立、维持和释放网络连接的手段，完成路由选择、拥塞控制、网络 互联等功能。 (2)根据传输层的要求选择网络服务质量。服务质量的参数主要包括：残留差错率、服 务可用性、可靠性、吞吐量、传输延迟等。 (3)对数据传输过程实现流量控制、差错控制以及顺序控制。 (4)提高资源子网主机节点与通信子网的接口，向传输层提供虚电路服务和数据报服务。 网络层的主要功能是完成网络中主机间的报文传输，其关键问题之一是使用数据链路层服务将每个报文从源端传输到目的端。 基本功能：实现端到端的网络连接，屏蔽不同子网技术的差异，向上层提供一致的服务。 主要功能： 路由选择和转发 通过网络连接在主机之间提供分组交换功能 分组的分段与成块，差错控制、顺序化、流量控制
5.1.2网络层服务的特点 网络层的服务有如下特点： (1)最重要的特点是无连接 (2)服务是不可靠的，传送过程中可能延迟、不按顺序到达或者丢失等 (3)服务是尽力而为的。 网络层实现这种无连接服务的分组传送机制称为网际协议，通称IP协议。 网络层服务应遵循以下三个原则： (1)服务应与通信子网技术无关。 (2)通信子网的数量、类型和拓扑结构对传输层是隐蔽的。 (3)传输层能获得的网络地址应采用统一的编号形式，即使跨越多个LAN和WAN。 5.2路由算法 路由算法是网络层软件的一部分，它负责确定一个进来的分组应该被传送到哪条输出线路上。 5.2.1路由算法选择的参考标准 路由算法选择有以下参考标准： (1)正确性：沿着路由表所指引的路由，分组一定能够传输到最终到达的目的网络和目 的主机。 (2)最优化：指路由算法选择最佳路径的能力。 (3)简洁性：算法设计简洁，利用最少的软件和开销，提供最有效的功能。 (4)坚固性：路由算法处于非正常或不可预料的环境时，如硬件故障、负载过高或操作 失误时，都能正确运行。 (5)快速收敛：收敛是在最佳路径的判断上所有路由器到达一致的过程。收敛慢的路由 算法会造成路径循环或网络中断。 (6)灵活性：路由算法可以快速、准确地适应各种网络环境。
遗传算法优化的BP神经网络建模[精选.]
遗传算法优化的BP神经网络建模 十一月匆匆过去，每天依然在忙碌着与文档相关的东西，在寒假前一个多月里，努力做好手头上的事的前提下多学习专业知识，依然是坚持学习与素质提高并重，依然是坚持锻炼身体，为明年找工作打下基础。 遗传算法优化的BP神经网络建模借鉴别人的程序做出的仿真，最近才有时间整理。 目标： 对y=x1^2+x2^2非线性系统进行建模，用1500组数据对网络进行构建网络，500组数据测试网络。由于BP神经网络初始神经元之间的权值和阈值一般随机选择，因此容易陷入局部最小值。本方法使用遗传算法优化初始神经元之间的权值和阈值，并对比使用遗传算法前后的效果。 步骤： 未经遗传算法优化的BP神经网络建模 1、随机生成2000组两维随机数(x1,x2)，并计算对应的输出y=x1^2+x2^2，前1500组数据作为训练数据input_train，后500组数据作为测试数据input_test。并将数据存储在data中待遗传算法中使用相同的数据。 2、数据预处理：归一化处理。 3、构建BP神经网络的隐层数，次数，步长，目标。 4、使用训练数据input_train训练BP神经网络net。 5、用测试数据input_test测试神经网络，并将预测的数据反归一化处理。 6、分析预测数据与期望数据之间的误差。 遗传算法优化的BP神经网络建模 1、读取前面步骤中保存的数据data； 2、对数据进行归一化处理； 3、设置隐层数目； 4、初始化进化次数，种群规模，交叉概率，变异概率 5、对种群进行实数编码，并将预测数据与期望数据之间的误差作为适应度函数； 6、循环进行选择、交叉、变异、计算适应度操作，直到达到进化次数，得到最优的初始权值和阈值； 7、将得到最佳初始权值和阈值来构建BP神经网络； 8、使用训练数据input_train训练BP神经网络net; 9、用测试数据input_test测试神经网络，并将预测的数据反归一化处理； 10、分析预测数据与期望数据之间的误差。 算法流程图如下：
BP神经网络模型简介及相关优化案例
华东理工大学 2016-2017学年第2学期 研究生《石油化工单元数学模型》课程论文2017年6月 开课学院：化工学院任课教师：欧阳福生 考生姓名：丁桂宾学号：Y45160205 成绩：
BP 神经网络模型简介及相关优化案例 一、神经网络模型简介 现代神经生理学和神经解剖学的研究结果表明，人脑是极其复杂的，由约1010个神经元交织在一起，构成一个网状结构。它能完成诸如智能、思维、情绪等高级精神活动，被认为是最复杂、最完美、最有效的一种信息处理系统。人工神经网络（Artificial Neural Networks ，以下简写为 NN ）是指模拟人脑神经系统的结构和功能，运用大量的处理部件，通过数学方法，由人工方式构造的网络系统[1] 。 图1表示作为 NN 基本单元的神经元模型，它有三个基本要素[2]： （1） 一组连接权（对应于生物神经元的突触），连接强度由各连接上的权值表示，权值为正表示激励，为负表示抑制。 （2） 一个求和单元，用于求取各输入信息的加权和（线性组合）。 （3） 一个非线性激励函数，起非线性映射作用并限制神经元输出幅度在一定的范围内（一般限制在[0,1]或[?1,+1]之间）。 图1 神经元模型 此外还有一个阈值k θ（或偏置 k k b θ-=）。以上作用可以用数学式表达为： ∑= =P j kj k j x w u ；
k k k u θν-=； ) (k k v y ?= 式中 P x x x x ,...,,,321为输入信号， kP k k k w w w w ,...,,,321为神经元k 的权值， k u 为 线性组合结果， k θ为阈值。(.)?为激励函数，k y 为神经元k 的输出。 神经网络理论突破了传统的、串行处理的数字电子计算机的局限，是一个非线性动力学系统，并以分布式存储和并行协同处理为特色，虽然单个神经元的结构和功能极其简单有限，但是大量的神经元构成的网络系统所实现的行为却是极其丰富多彩的。
图论与网络优化课程设计_Matlab实现
图论与网络优化课程设计 四种基本网络（NCN、ER、WS、BA） 的构造及其性质比较 摘要：网络科学中被广泛研究的基本网络主要有四种，即：规则网络之最近邻耦合网络（Nearest-neighbor coupled network）,本文中简称NCN；ER随机网络G(N,p)；WS小世界网络；BA无标度网络。本文着重研究这几种网络的构造算法程序。通过运用Matlab软件和NodeXL网络分析软件，计算各种规模下（例如不同节点数、不同重连概率或者连边概率）各自的网络属性(包括边数、度分布、平均路径长度、聚类系数)，给出图、表和图示，并进行比较和分析。 关键字：最近邻耦合网络；ER随机网络；WS小世界网络；BA无标度网络；Matlab；NodeXL。
四种基本网络（NCN、ER、WS、BA） 的构造及其性质比较 1.概述 1.网络科学的概述 网络科学（Network Science）是专门研究复杂网络系统的定性和定量规律的一门崭新的交叉科学，研究涉及到复杂网络的各种拓扑结构及其性质，与动力学特性（或功能）之间相互关系，包括时空斑图的涌现、动力学同步及其产生机制，网络上各种动力学行为和信息的传播、预测（搜索）与控制，以及工程实际所需的网络设计原理及其应用研究，其交叉研究内容十分广泛而丰富。网络科学中被广泛研究的基本网络主要有四种，即：规则网络之最近邻耦合网络（Nearest-neighbor coupled network）,本文中简称NCN；ER随机网络G(N,p)；WS小世界网络；BA无标度网络。本文着重研究这几种网络的构造算法程序。计算各种规模下（例如不同节点数、不同重连概率或者连边概率）各自的网络属性(包括边数、度分布、平均路径长度、聚类系数)，给出图、表和图示，并进行比较和分析。 2.最近邻耦合网络的概述 如果在一个网络中，每一个节点只和它周围的邻居节点相连，那么就称该网络为最近邻耦合网络。这是一个得到大量研究的稀疏的规则网络模型。 常见的一种具有周期边界条件的最近邻耦合网络包含围成一个环的N个节点，其中每K个邻居节点相连，这里K是一个偶数。这类网络的一个重要特征个节点都与它左右各/2 就是网络的拓扑结构是由节点之间的相对位置决定的，随着节点位置的变化网络拓扑结构也可能发生切换。 NCN的Matlab实现： %function b = ncn(N,K) %此函数生成一个有N个节点，每个节点与它左右各K/2个节点都相连的最近邻耦合网络 %返回结果b为该最近邻耦合网络对应的邻接矩阵 function b = ncn(N,K) b=zeros(N); for i = 1:N for j = (i+1):(i+K/2) if j<=N b(i,j)=1; b(j,i)=1; else b(i,j-N)=1;
D2D网络中基于强化学习的路由选择与资源分配算法研究
D2D网络中基于强化学习的路由选择与资源分配算法研究 随着通信网络的发展,终端直连通信技术(Device-to-Devic,D2D)被广泛关注,它的应用将满足用户日益增长的流量需求。然而,D2D技术的引入使得蜂窝网络内部的干扰冲突加剧,用户难以满足服务质量(Quality-of-Service,QoS)的需求。 一些传统算法基于网络“抓拍”信息可以计算得到各采样时刻的网络控制策略,却难以适应复杂多变、高度动态的网络环境。因此,本文着手于动态环境下的D2D网络中的通信问题进行了深入地研究,并结合正在兴起的机器学习技术,提出了更加智能化的解决方案。 在本文中我们将分别研究“多跳D2D网络”与“D2D直连通信”两类D2D应用场景的通信问题,提出了在两种场景下基于强化学习的在线学习方法,从而解决多跳网络中的路由问题与D2D直连网络中的资源分配问题。而随着问题复杂程度的增加,强化学习算法也相应由浅入深。 在路由问题中,因问题复杂程度较低,我们利用传统强化学习算法中的值迭代算法求解,而在资源分配问题中因问题规模变大,本文依次提出了基于深度Q 学习(Deep Q-Learning,DQN)的资源分配算法和深度确定性策略梯度(Deep Deterministic Policy Gradient,DDPG)的资源分配算法分别解决了问题中状态空间连续与动作空间连续的问题,而这两种算法都是深度强化学习(Deep Reinforcement Learning,DRL)中的经典算法。在多跳D2D网络路由问题中,我们考虑了三类随网络动态变化的QoS指标,并利用值迭代算法求解,同时提出了分布式的强化学习算法解决了集中式算法学习周期过长的问题。 仿真发现,在动态环境中,所提算法在性能与时间复杂度方面相较于传统算
基于蚁群算法的网络多节点路由优化
1 绪论 (1) 1.1 本设计研究的目的意义 (3) 1.2 本设计的研究现状 (3) 1.3 本课题要研究与解决的问题 (4) 2 路由选择的基本概念 (5) 2.1 路由技术 (5) 2.2 路由选择算法 (6) 2.2.1 距离矢量路由算法 (7) 2.2.2 链路状态路由算法 (7) 2.3 路由协议 (8) 3 蚁群算法 (13) 3.1 蚁群优化的原理分析 (13) 3.2 简单蚁群优化SACO (14) 3.3 蚁群算法的主要特点 (17) 4 基于蚁群算法的网络多点路由的优化与仿真 (17) 4.1 网络路由优化问题的描述 (17) 4.2 基于蚁群算法来选择路由算法的思想的概述 (18) 4.3 基于蚁群算法的路由优化具体过程 (19) 4.3.1 最优路径的建立 (19) 4.3.2 路由的维护与更新 (24) 4.3.3 链路中断与修复 (24) 4.4 实验结果分析 (24) (25) (26) (27) (27) (28) 5 总结 (31) 参考文献 (32) 致谢 (34) 1 绪论 通信网络的迅速发展，新业务的不断出现，使多点通信成为网络必须支持的功能。传统网络中使用一对一的通信协议支持多点协议，数据需要做多个拷贝，分别传送，极大的浪费了网络资源。未来的多媒体通信，将带来大量的多点通信，使用点对点协议将造成网络效率的低下；另外，多媒体通信的业务通常需要达成一定的同步关系，使用点对点协议完成多点通信不再有效；而复用技术的发展使
组播在共同的链路上共享带宽成为可能。由于上述原因必须考虑多点路由问题。 由于网络是动态变化的，网络拓扑结构的变化的不可预测性和变化的频繁性和不确定性是网络多点路由问题与其他常见的组合优化问题的根本不同之处，网络流量的随机性和偶然性也是网络动态变化的主要因素。有效快捷的网络路由算法是网路发展的重要问题。 而蚁群算法的出现和广泛应用，提供了多点路由优化设计的新的思想。蚁群算法是一种模拟进化算法，它是在对自然界中真实蚁群的集体行为研究的基础上，由意大利学者M.Dorigo等人首先提出的。M.Dorigo等人充分利用了蚁群搜索食物的过程与著名的旅行商问题（TSP）之间的相似性，通过人工模拟蚂蚁搜索食物的过程（即通过个体之间的信息交流与相互协作最终找到从蚁穴到食物源的最短路径）来求解TSP问题。仿生学家通过大量细致观察研究发现，蚂蚁个体之间是通过一种被称为外激素的物质进行信息传送，从而能相互协作，完成复杂的任务。蚂蚁在运动过程中，能在它所经过的路径上留下该物质，而且蚂蚁在运动过程中能够感知这种物质的存在及其强度，并以此指导自己的运动方向，蚂蚁倾向于朝着这种物质强度高的方向移动。因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。蚁群算法是一种随机搜索算法，与其它模拟进化算法一样，通过候选解组成的群体的进化过程来寻求最优解，该过程包含两个基本阶段：适应阶段和协作阶段。在适应阶段，各候选解根据所积累的信息不断调整自身结构；在协作阶段，候选解间通过信息交流，以期产生性能更好的解。 蚁群算法之所以能引起相关领域研究者的注意，是因为这种求解模式能将问题求解的快速性、全局优化特征以及有限时间内答案的合理性结合起来。其中，寻优的快速性是通过正反馈式的信息传递和积累来保证的。而算法的早熟性收敛又可以通过其分布式计算特征加以避免，同时，具有贪婪启发式搜索特征的蚁群系统又能在搜索过程的早期找到可以接受的问题解答。这种优越的问题分布式求解模式经过相关领域研究者的关注和努力，已经在最初的算法模型基础上得到了很大的改进和拓展。基于蚁群算法的以上特点，将蚁群算法用于OSPF协议的网络中，根据不同网络的需要寻找最优路径（可以是时延、中间路由器个数或者费用等参数最优化），
路由算法的比较及电路交换与包交换的优缺点
LS路由算法与DV路由算法的比较 徐雄博20050830226 信息安全 2 班 摘要：当一个分组要从源主机带目的主机时，网络层必须确定从发送方到接受方的分组所采用的路径。选路算法的目的就是给定一组路由器以及连接路由器的链路，选路算法要找到一条从源路由器到目的路由器的“好”的路径，即具有最低费用的路径。根据算法是全局性的还是分布式的，选路算法可分为两种：具有全局状态信息的链路状态算法（link state algorithm, LS）以及分散式的选路算法距离向量算法（distance-vector, DV）。本文将通过对这两种算法的比较来找出两个算法在不同的情况下，每种算法的适应环境。 关键词：路由算法；RIP路由协议；OSPF路由协议；LS路由算法；DV路由算法 Abstraction：When a packet want to round from source host to destination host, the network layer must nonetheless determine the path that packets take from senders to receivers. The purpose of a routing algorithm is that given a set of routers, with links connecting the router, a routing algorithm finds a “good” path from source router to destination router. Typically, a good path is one that has the least cost. According to whether the algorithms are global or decentralized, the routing algorithm can be classified into two types: algorithms with global state information are often referred to as link-state (LS) algorithms, and the decentralized routing algorithm called a distance-vector (DV) algorithm. Through this passage we will find the environment which suits each algorithm most. Keywords：routing algorithm，RIP，OSPF，LS，DV 1.概述 随着社会的发展，计算机技术已经越来越普及。不同的网络层提供的不管是数据服务还是虚电路服务，网络层都必须确定为从发送方到接受方的分组所采用的路径。我们看到选路的工作是从发送方到接受方通过路由器的网络决定的好路径。选路算法的目的是简单的，即给定一组路由器以及连接路由器的链路，选路算法要找到一条从源路由器到目的路由器的“好”的路径，。通常一条好的路径指具有最低费用的路径。对选路算法分类的一种方法是根据该算是全局性的还是分散式的可分为全局选路算法（global routing algorithm）和分散式选路算法（decentralized routing algorithm）[1]。而根据这两个路由选路算法，历史上曾有两个选路协议曾被广泛用于Internet上自治系统内的选路：选路信息协议（Routing Information Protocol，RIP）与开放最短路径优先（Open Shortest Path First，OSPF）[2]。 2.路由算法 路由算法在路由协议中起着至关重要的作用，采用何种算法往往决定了最终的寻径结果，因此选择路由算法一定要仔细。通常需要综合考虑以下几个设计目标： ——（1）最优化：指路由算法选择最佳路径的能力。 ——（2）简洁性：算法设计简洁，利用最少的软件和开销，提供最有效的功能。 ——（3）坚固性：路由算法处于非正常或不可预料的环境时，如硬件故障、负载过高或操作失误时，都能正确运行。由于路由器分布在网络联接点上，所以在它们出故障时会产生严重后果。最好的路由器算法通常能经受时间的考验，并在各种网络环境下被证实是可靠的。
路由基本原理及路由协议详情详情
路由基本原理及路由协议 一．OSI/RM参考模型中分组交换网络的（网络层）路由选择1．路由选择 路由选择也较路径选择。 路由选择是指选择和建立一条合适的物理或逻辑的通路，以供进网数据从网络的源节点到达宿节点的控制过程。 2．路由问题概述 分组交换网结构可以抽象成以下网络拓扑图 数据分组从源节点A到达宿节点D的路径（通路）有： l1,l3（A-B-D） l2,l6（A-C-D） l2,l4,l7（A-C-E-D） 问题： 哪条通路是最佳的？ 最佳－即最短路径问题。 假如上图中每条边都有权值，A到D的最短路径应该是所有路径中，构成路径的边的权值之和最小的哪条路径。 权值：在网络中主要是数据传输时延和距离。 3．对路由选择算法的要求 a.能正确、迅速、合理地传输数据分组 b.能适应由于节点或链路故障引起的拓扑变化 c.能适应网络通信量的变化，使网络内的通信负载达到均衡 d.算法应尽量简单 4．路由选择算法的两大策略 a．静态路由选择算法——基于网络拓扑（距离）和时延的要求，以固定的准则来选择路由。因此这类算法也叫做确定型（非自适应）路由算法。这类算法简单，速度快，但不能适应因种种原因而引起的网络拓扑变化和网络内部通信量的变化。这类算法使用于那些网络拓扑结构不经常变化的小型网络。 b.动态路由选择算法——基于网络状态参数的变化，来选择某段时间内有效的路由。这类算法能够适应网络拓扑状态和其它状态参数的变化而调整路由。因此这类算法也叫做自适应路由算法 5．实现路由选择算法的一般方法 a.标头指示法 b.路由表法 在每个交换节点（路由器）中建立路由表。 二、互联网中的路由算法——IP路由技术
图与网络优化模型
第十章 图与网络优化模型 在图论中通常用V 表示点，E 表示边（无向），A 表示弧（有向），G 表示图，点和边构成的图称为无向图，G=（V ，E ），点和弧构成的图称为有向图,G=(V ,A)。 对图G 的边（或弧）标上权数，称为赋权图。 求1到7的最短路。 本图是个有向图，弧上的数字不妨理解为距离。目前用于求解最短路的算法有多种，如：动态规划法，Dijkstra 算法，0-1规划方法等。 下面只介绍0-1规划法 设1为起点，7为终点。引入1,0=ij x 表示：若弧(i,j)在最短路上,1=ij x ,否则，0=ij x Z 为目标函数上各弧的路程之和。 起点1必定有一条弧出发,所以 12 1=∑=n j j x 终点n 必定有一条弧到达,所以11 1 =∑-=n i in x 其它点有两种情况： (1) 该点不在最短路上，即无进线弧，也无出线弧。满足： 0,1=∑≠=n k i i ik x ， 且0,1=∑≠=n k i i ki x (2) 该点在最短路上，即有进线弧，也有出线弧。满足： 1,1=∑≠=n k i i ik x ，且 1,1=∑≠=n k i i ki x 改写上述两个等式为： 0,1 ,1==∑∑=≠=ii n j kj n k i i ik x x x
???? ??? ????????===<<==== ∑∑∑∑∑=====1,0,...,2,1,01,11..min 11 1111 ,ij ii n i ji n i ij n i in n i i n j i ij ij x n i x n j x x x x t s x w Z model : sets : city/1..7/;!定义7个城市; links(city,city):dist,x;!定义各城市之间的距离表(若城市i 到城市j 无路,用一个大数表示),决策变量; endsets data : dist=0 2 10 1000 1000 1000 1000 1000 0 7 3 1000 1000 1000 1000 1000 0 1000 4 1000 1000 1000 1000 1000 0 1000 1000 8 1000 1000 5 1000 0 3 7 1000 1000 1000 1000 1000 0 12 1000 1000 1000 4 1000 3 0 ; enddata n=@size (city); min =@sum (links:dist*x); @sum (city(i):x(1,i))=1; @sum (city(i):x(i,n))=1; @for (city(i)|i#gt#1 #and# i#lt#n : @sum (city(j):x(i,j))=@sum (city(j):x(j,i))); @for (city(i):x(i,i)=0); @for (links:@bin (x)); end 10.2 旅行售货员TSP 模型
路由基本原理及路由协议详情详情
实用标准文案 路由基本原理及路由协议 一．OSI/RM参考模型中分组交换网络的（网络层）路由选择 1．路由选择 路由选择也较路径选择。 路由选择是指选择和建立一条合适的物理或逻辑的通路，以供进网数据从网络的源节点到达宿节点的控制过程。 2．路由问题概述 分组交换网结构可以抽象成以下网络拓扑图 的路径（通路）有：A到达宿节点D数据分组从源节点）（A-B-Dl,l31）（A-C-Dl,l62 A-C-E-D）l,l,l（724问题：哪条通路是最佳的？最佳－即最短路径问题。假如上图中每条边都有权值，A 到D的最短路径应该是所有路径中，构成路径的边的权值之和最小的哪条路径。 权值：在网络中主要是数据传输时延和距离。 3．对路由选择算法的要求 a.能正确、迅速、合理地传输数据分组 b.能适应由于节点或链路故障引起的拓扑变化 c.能适应网络通信量的变化，使网络内的通信负载达到均衡 d.算法应尽量简单
4．路由选择算法的两大策略 a．静态路由选择算法——基于网络拓扑（距离）和时延的要求，以固定的准则来选择路由。因此这类算法也叫做确定型（非自适应）路由算法。这类算法简单，速度快，但不能适应因种种原因而引起的网络拓扑变化和网络内部通信量的变化。这类算法使用于那些网络拓扑结构不经常变化的小型网络。 b.动态路由选择算法——基于网络状态参数的变化，来选择某段时间内有效的路由。这类算法能够适应网络拓扑状态和其它状态参数的变化而调整路由。因此这类算法也叫做自适精彩文档．实用标准文案 应路由算法 5．实现路由选择算法的一般方法 a.标头指示法 b.路由表法在每个交换节点（路由器）中建立路由表。IP路由技术二、互联网中的路由算法——IP路由1．互联网中的路由主要有路由器的路由功能完成。2．路由器中的路由功能 a.实现网间中继IP数据包的功能，包括：数据帧的封装和拆封、IP地址到MAC地址的映射等 b.对IP数据包的控制，例如ttl=0时丢弃数据包 c.依据路由表选择最佳路由。 d.支持有关的路由算法和路由协议 3．路由表 互联网路由器中的路由表只保存部分路由信息。即每个表项只给出目的网络号，和下一（个路由器）站的地址。
第九章网络优化模型
教学要求: b拿握图爲基础，拿握最蔻路问題，最大流问題和最小费用流问題等网络优化栈型及其基本算出O b会应用模矍和方出解决一些管理中的基本问題
口目录口图与阿络 口树 □最短珞问题 口最丸浇问题 □最小赛用济问题
一、图的概念及分类 图是由作为研克对象的有限个集合和表达这些顶A之间关糸的m条线的集合组成的丿 记顶点集合^V={v lz v2,……v n},线集合%L={—???lm} 图则记为G = (V, L),线又分为孤和边，顶点也称为结点孤是由一对有序的顶点组成，表示两个顶点之间可能运动的方向取旖孤的方向就变成了边，边是只要任两点之间有连线，两个方向均可使用，孤可作为城市道路的单行道，边则是双行道
顶点、孤.有向图■无向图■ <>道路.环、连通图、连通子 图、次的基本概I 念 6—do 3 O 1 5 3 2 次：以3点为 顶点的边的条 数隸为顶点的 次
二?网络 点或边带有禁种数量指捺的图叫网划图、简称网修。 ?与点或边有关的禁些数量指栋，我们经常称之为权,权可以代蔻如距离、费用.彖量等。左图可以看作: A从发色厂（节点1丿向禁城市（节点6丿输送赳力，必须通过中转誌（节点2, 3, 4, 5丿转送，边上数字代表两节点问的距禽。色力公司希望迄择合适的中转哉，使从色厂到城市的传输路线最短。 —个输油管道网。节点1表示管道的起点，节点6表示管道的终点，节点2到5表示中转站，?务边的数字表示该段管道能通过的最大输送量。应怠样安排输油线路，使从节点1到节点6的总输送量最丸？ > 一張城市分布图。现蛊要蛊各城市之间架设色话线，应如何架设，使各城市 之间既能通话，又使总的架设路线最短？
网络优化全过程
二、网络优化的全过程 网络优化的目标是提高或保持网络质量，而网络质量是各种因素相互作用的结果，随着优化工作的深入开展和优化技术的提高，优化的范围也在不断扩大。事实上优化的对象已不仅仅是当前的网络，它已经渗透到包括市场预测，网络规划，工程实施直至投入运营的整个循环过程的每个环节。 1、网络优化与工程建设 高质量的工程实施是网络质量的基本保障，也是优化活动开展的前提。优化人员应积极参与工程质量规范的制定，并总结优化中发现的工程质量问题，及时反馈给工程部门。 2、网络优化与规划 用户数量的高速增长，用户流动性增加都将导致系统在高负荷状态下运行使网络产生阻塞，网络安全面临威胁。 网络优化能够通过各种手段减少不必要的系统开销，增加系统有效容量或调整负荷分布，缓解阻塞，保障网络安全。但要从根本上解决这些问题，必须提高规划水平，加快规划速度，使扩容跟上市场发展的速度。 目前的优化技术已经能够帮助规划部门深入地了解现有设备的实际容量，资源利用率，负荷分布情况；建立更标准的话务模型并预测该话务模型下的系统容量和分布；根据给定的话务模型预测话务和信令的流
向和流量，使网络结构设计更加合理。 3、网络优化与市场经营 网络质量的好坏将直接影响到运营商的经营业绩，所以网络优化人员必须倾听经营部门反馈并帮助经营部门更有效地提取用户信息。另外，为了增加市场份额，满足用户需求，运营商不断地引入新业务，这些业务将对网络的负荷和性能带来影响，优化应该在新业务引入的初始阶段进行密切跟踪尽快做出判断并采取措施。设计合理的费率政策也将给运营商带来更多的利益，在新的费率政策生效时，网络优化人员可以通过分析话务统计和借鉴以往的经验，了解其对网络性系统负荷和用户行为的影响，并帮助市场经营部门对费率政策是否有效进行科学的评估。 三、网络优化技术 随着优化活动的深入和范围的扩展，网络优化技术也日趋成熟。一般的网络优化活动分为两个阶段：先对现有的网络进行性能评估，对发现的问题进行分析，然后运用各种手段实施优化。 1、常规的网络评估和分析 1）、根据话务统计对网络性能指标进行分析 主要指标有：掉话率、接通率、切换成功率、位置更新成功率、寻呼成功率。
网络优化的现状和发展
[回到网络优化主页] -------------------------------------------------------------------------------- 移动网络优化的现状与发展 目前网络优化已经发展成为一种综合性很强的技术，本文对优化工作中采用的技术和软件进行了描述，并提出一些尚待研究的课题。 一、网络优化内容 1、故障排除的经验 GSM网络发展到一定规模，覆盖已经得到相当的改善，但网络质量仍然不能满足用户的要求，主要原因是：扩容频繁，扩容期间网络监控和保障不利，因受到工期紧的影响，质量监控体系不完善，使得安装和开通过程中存在较多质量问题。随着设备使用时间的增加，一些故障，特别是隐性故障逐渐增多，这类故障并未达到告警门限，但恶化了网络性能。 针对以上情况，许多运营商和供应商开展了以检查工程质量为主的清障排故工作，通过对用户投诉强烈、指标较差的小区进行上站检查和路测，发现并清除了安装开通差错和一些硬件问题，网络质量得到了初步改善。 2、无线优化 通过清障排故网络优化人员积累了一定的经验，优化人员和各种仪器设备有所增加，网络优化进入了发展阶段。这个阶段是以降低掉话率和通话建立失败率等无线指标为主要目的，除了常用的设备检查和路测，对频率规划进行优化也是主要的方法，通过优化，无线指标有较大改善，用户对网络质量的主观评价也有所提高，隐性故障得到进一步清除，频率规
划得到改进。随着无线技术逐步成熟。优化的重点逐渐转移到以提高接通率为标志的交换机指标上来。 3、有线优化 接通率指标如交换机接通率或长途来话接通率的提高不但意味着网络性能得到改善，而且直接意味着花费收入的增加。但由于接通率受许多因素的影响，其中一些问题是本地移动通信运营商自身无法解决的，比如去话接通率和市话网及其他移动网有很大关系。接通率反映一个地区的综合通信质量，与无线指标相比，接通率的提高需要更多的努力和时间。一个常见的误区是将接通率不高盲目地归结为交换机问题，但接通率，特别是来话接通率与本地的无线网络质量有很大的关系，覆盖不好、话音、信令信道阻塞、频率干扰和硬件故障都是接通率不高的常见原因。所以，只有以整体的眼光，综合无线和有线两方面的手段才能切实提高交换指标。 二、网络优化的全过程 网络优化的目标是提高或保持网络质量，而网络质量是各种因素相互作用的结果，随着优化工作的深入开展和优化技术的提高，优化的范围也在不断扩大。事实上优化的对象已不仅仅是当前的网络，它已经渗透到包括市场预测，网络规划，工程实施直至投入运营的整个循环过程的每个环节。 1、网络优化与工程建设 高质量的工程实施是网络质量的基本保障，也是优化活动开展的前提。优化人员应积极参与工程质量规范的制定，并总结优化中发现的工程质量问题，及时反馈给工程部门。 2、网络优化与规划 用户数量的高速增长，用户流动性增加都将导致系统在高负荷状态下运行使网络产生阻塞，网络安全面临威胁。 网络优化能够通过各种手段减少不必要的系统开销，增加系统有效容量或调整负荷分布，缓解阻塞，保障网络安全。但要从根本上解决这些问题，必须提高规划水平，加快规划速度，使扩容跟上市场发展的速度。