《基于粒子群算法的路由优化与流量均衡研究》由会员分享，可在线阅读，更多相关《基于粒子群算法的路由优化与流量均衡研究（53页珍藏版）》请在金锄头文库上搜索。
1、太原理工大学工学硕士研究生学位论文I基于粒子群算法的路由优化与流量均衡研究摘 要随着网络在诸多领域的应用网络业务呈现快速增长由此而对互联网提供的服务质量Quality of ServiceQoS提出更高的要求已经证明带有性能服务要求的QoS路由和流量优化是组合规划中的 NP-Hard 问题诸多学者引入诸如粒子群算法蚁群算法遗传算法等智能算法用以此类问题智能算法在网络问题中的应用已成为一个研究热点同时粒子群算法的应用也成为其一个研究的重要方面粒子群优化Particle Swarm OptimizationPSO算法是一种群体智能算法和启发式全局优化技术整个种群在算法规定的简单行为规则下能够表现出
2、复杂的特性PSO 与其他进化计算方法相比具有可设置参数少计算速度快和简单容易实现等优点这些使其成为一种简单有效的随机算法在处理约束条件问题时比传统的搜索算法要表现灵活的多目前越来越多的网络应用需要 QoS 保证,路由算法的目标由传统的寻找一条最短路径转变为寻找多约束下更优的路径由于基于最小跳数或最小时延的简单路由算法已经不能满足网络中具有质量要求和突发性的流量的需求以及不同类型的应用需求由此必须通过路由优化寻求满足约束条件的路径将分组推至目的节点进而可实现网络中的性能需求负载平衡等要求本文在对粒子群算法的相关情况和基于粒子群算法的路由算法的综述基础上提出一种关系矩阵来作为粒子群算法的编码方式并
3、用来处理路由优化和流量均衡问题也就是粒子的位置是一个含有整个网络的拓扑结太原理工大学工学硕士研究生学位论文II构信息的关系矩阵仿真实验表明采用关系矩阵编码方法可以使粒子群算法能够较好的应用到路由优化和流量均衡问题同时能够克服其他方法所带来的编码复杂对粒子群算法改动较大实现复杂等缺点本文所提出的编码方法能够无须对粒子群算法做出较大改动能够减少冗余空间的产生和冗余搜索关键字 粒子群算法路由优化流量均衡关系矩阵太原理工大学工学硕士研究生学位论文IIIRESEARCH ON ROUTING OPTIMIZATION AND FLOW BALANCING BASED ON PSOABSTRACTAs t
4、he network in many fields of application,quality of service provided bynetwork which presents the fast growth is put forward higher request. QoSrouting and Flow balance has been proved a NP complete problems, therefore,many scholars apply such as particle swarm algorithm, the ant colony algorithmand
5、 genetic algorithm of intelligent algorithm in such problems to seek theoptimum solution of the problem. Intelligent algorithm in network applicationshas become a hotspot, and particle swarm algorithm of application is also astudy of important aspects.PSO is a kind of swarm intelligence algorithm an
6、d heuristic globaloptimization technique, whose individual will flock with no quality and novolume, is a potential solution to solve the problem, and rules stipulatedalgorithm can show complex characteristics in the simple behavior. PSO hasfewer set parameters and computing speeder and easier to rea
7、lize, etc. Thesemake it become a kind of simple and effective in the treatment of randomalgorithm, constraint condition problem than traditional algorithm to moreflexible. At present more and more network application needs to ensure thequality of service, the target by routing algorithm of tradition
8、al find a shortestpath for more change more optimal path constraint. Based on the minimal hop太原理工大学工学硕士研究生学位论文IVdue to delay or simple routing algorithm in network cannot have satisfied withthe constant change of the quality requirements and different types of trafficdemand, the application must be
9、sought by routing optimization path will meetthe constraints of grouping nodes, which aim to push the performancerequirements can realize network load balance, etc.Before the related information of PSO and the routing algorithm based onPSO are proposed, relationship matrix as a kind of encoding meth
10、od is putforward to deal with routing optimization and flow optimization by PSO.Therefore the position of a particle must be relationship matrix in order that PSOcould performance well while dealing with the problems. The kind of encodingmethod can solve the problem of routing optimization and load
11、balancing in theapplication of PSO , that is , it can reduce the redundant space generating andredundant searching with making little change of using that coding method.Keywords: PSO,Routing optimization,Flow balancing, Relationship matrix太原理工大学工学硕士研究生学位论文1第一章 引言1.1 课题背景互联网网络业务的速猛发展对互联网的服务质量QoS提出了更高
12、的要求目前随着通信设备及其技术的不断完善改进传输链路和传输节点已经不再是限制网络发展的主要因素而作为网络业务交换节点的交换路由设备已成为制约网络性能的主要瓶颈由于网络动态性和实时性的存在传输数据路径的实际状态不仅与路径本身的条件有关更受当前网络路径上负载的影响此时如果网络节点对全局网络服务质量的状态了解不够精确这就使得路径状态信息的概率模型难以确定预计算也不够准确更新路由不实时路由算法的计算复杂度和时间复杂度过高而不能应用在实际的网络由于可以通过网络所分担的网络负载来充分反映互联网络复杂的动态特性而网络负载又是网络动态行为的主导因素因此在保证公平性满足约束优化性能减少阻塞为主要因素条件下在当前
13、的网络环境中进行路由优化以寻找出最优路径另外通过对网络负载进行合理的负载分担规划也是提升网络性能和保证服务质量的重要途径生命科学与工程科学的相互交叉相互渗透和相互促进已经成为近代科学技术发展的特点之一粒子群算法的出现及发展体现了科学交叉发展的这种特征和趋势近年来将粒子群算法应用到网络优化问题引起了很多专家学者的注意粒子群算法作为一种新的全局优化搜索算法以其简单通用实现容易设置参数少和鲁棒性强等优点和适用于并行处理以及应用范围广范等显著特点被成功应用到许多网络组合优化问题中QoS(Quality of Service)路由选择便是其中之一为了有效地求解约束优化问题人们逐渐将目光转向随机搜索算法其
14、中仿生随机算法以其较强的求解力通用性日益受到广大学者的关注并逐渐成为求解约束优化问题的重要工具与传统的优化算法相比仿生随机算法具有许多不可比拟的优越性其中最主要的一点是求解过程不依赖目标函数的解析性质同时能通过对问题解太原理工大学工学硕士研究生学位论文2空间的多点并行搜索以较大概率收敛于全局最优解另外仿生随机算法在处理约束条件时比传统的搜索算法要灵活得多不仅可借助进化操作对传统的罚函数法进行改进使之更加有效的处理约束条件也可以通过特定的编码保证个体落在可行点集内或者在每一演化代通过特定的修正算子对后代个体进行修正以满足约束条件而不需要借助于问题的梯度信息粒子群算法是一种简单有效的随机算法与其它
15、进化计算方法比较起来它的求解过程更加简单易行所付出的计算代价更小因此也被视为求解 CO 问题的可行方法其同样对于路由优化和流量均衡问题也是有效的1.2 路由算法本身面临的主要问题路由选择包含路径确定和通过确定的路径传输信息路径的确定即让路由器寻找到一条数据包从发送端通过诸多不同网络到达目的地的可行路由的过程路由优化的目的是提高路由选择协议选择路由的能力使路由选择算法根据度量标准如带宽跳数和延时等和度量标准所指定的权值选择最优路径以传输数据分组由于基于最小跳数或最小时延的路由算法已经不能满足当前网络中带有服务质量要求具有突发性的流量以及不同类型服务应用的要求有必要通过路由优化使路由算法选择满足约
16、束条件的可行路径将数据分组传递至目的节点进而实现网络中的管理策略性能需求负载平衡和可量测性等要求当前的路由优化基本上是实现基于多约束条件下对分组传递路径的智能选择目前路由优化算法的特征和性能大多都缺少路由模型和理论上的支持因此进行路由优化的理论研究比较困难评价标准也不全面基于状态信息概率分布的 QoS 路由算法必须依赖于链路状态信息的概率模型而实际的链路状态不仅与链路本身的条件有关而且还受当前网络流量的影响使得链路状态信息的概率模型难以确定大部分路由算法都只是针对 QoS 路由问题中的某些特殊情况进行的设计缺少多个算法的纵向的比较与分析当前的路由算法仍停留在算法研究阶段它必须被写入通信协议才能够被实际应用太原理工大学工学硕士研究生学位论文31.3 负载均衡当前的问题与研究的意义提高网络的运行效率网络运行可靠性网络资源的使用效率和流量均衡性能成为当前流量研究的主要目的负载均衡和流量优化的核心任务就是任务调度可以把多个请求任务相对均衡地分担到若干个控制节点然后由控制节点决策路由路径这样就能有效的利用各个控制节点并能提高系统的运行效率和吞吐能力保障整个网络系统的实时高效运行目前开放最短路径优
