基于pso算法的ospf多约束路由策略

《基于pso算法的ospf多约束路由策略》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于PSO算法的OSPF多约束路由策略摘要：利用传统SPF算法解决OSPF网络路由难题时，由于没有考虑多约束条件和有效利用次路径，一旦最优路径发生拥塞，网络传输性能将急剧降低。将PSO算法应用于OSPF网络路由规划，利用多约束条件并结合OSPF网络多种路由参数的特性，重点对有效改善网络局部拥塞和快速求得全局最佳路由及若干次路由算法进行探究，并利用仿真数据对所提出的改进算法进行验证。结果表明，在解决OSPF网络路由规划问题中，PSO算法较传统遗传算法和SPF算法能实现网路传输性能更优。关键词：PSO算

2、法；OSPF；网络路由器；多约束路由；QoSDOIDOI：10.11907/rjdk.1431035中图分类号：TP311文献标识码：A文章编号：16727800（2015）006007604基金项目基金项目：安徽省高等教育振兴计划项目（2013zytz063）作者简介作者简介：江家宝（1968-），男，安徽无为人，硕士，巢湖学院信息工程学院讲师，研究方向为模式识别与智能控制、嵌入式系统、计算机网络；郑尚志（1963-），男，安徽巢湖人，博士，巢湖学院信息工程学院教授，研究方向为操作系统理论、人工智

3、能。100引言随着网络通信要求的不断提高和Internet的飞速发展，路由器成了网络连接中最为关键的设备，路由器中运行的软件对网络连接性能和效率的影响越来越明显。目前，国内外OSPF网络路由器的主流产品仍然使用SPF算法解决路由问题。为缓解网络路由拥塞等瓶颈问题，人们陆续提出了遗传算法、模拟退火算法等多种方法实现OSPF协议。本文在研究OSPF协议原理及PSO（ParticleSwarmOptimization）算法基本概念和实现方法[1]的基础上，详细阐述了网络路由选择过程中必须满足的QoS和实时

4、性等多种要求，以及在目标函数值的引导下，如何实现PSO和遗传算法对复杂的OSPF网络路由解空间进行有效搜索[23]，以获得最佳路由和多条次路由，并有效利用这些路由进行路由规划。通过仿真实验验证了将PSO算法应用于OSPF网络路由规划中的有效性。1OSPF协议原理10路由指在网络数据传输中采用某种策略为数据包从源点到达目的地点寻找一条理想路径。基于全局最优思想，网络设备为转发的数据包选择某种距离测度下的最优路径，沿最优路径发送数据包。支持OSPF协议的SPF算法在传送业务服务模式的网络中效果较好，但其

5、无法满足多媒体业务的QoS需求[45]，主要表现如下：①SPF采用与链路带宽成反比的cost值度量距离来寻找最优路径，没有考虑其它约束条件，不能满足日益复杂的网络性能要求；②SPF忽略了次路由，一旦最优路径发生拥塞，其它可用路径被闲置，将大大降低网络传输性能。拥塞时，网络时延和丢包率会剧增，若采用时延和丢包率来度量最优路径，可将流量转移到另一条路径上，但这种转移是全部转移，新路径又会由于负荷过重而拥塞，而原来的路径又会空闲，这样容易引起路由振荡。因此，需要选取新的OSPF实现方法，使其能满足日益复杂

6、的QoS要求。2QoS路由问题CCITT给出QoS的定义[67]为：“QoS是一个综合指标，用于衡量使用一个服务的满意度。”而现有的Internet都只是提供besteffort传送，不能提供QoS保证。为了适应网络的发展需求，Internet2工作组提出的新草案对QoS要求如下：①提供可计量的服务；②支持高级应用（如双向交互音/视频、远程控制等）；③良好的可扩展性；④可管理性；⑤能与终端用户操作系统和中间件协同工作等。要求QoS选路既要可行（即可达），又要有效（即最小化占用链路带宽，最小化链路拥塞

7、等）。因此，为了满足QoS路由要求，路由规划时首先考虑如何有效利用网络资源，其次考虑如何减少路由计算的时间复杂性。10本文首次采用经过PSO算法修正的OSPF路由来解决上述问题。3QoS路由模型网络链路的双向特征一般存在差异，网络的拓扑结构可用有向图G=（V，E）来描述（V为网络节点集合，E为节点间链路集合）。链路（v，e）的特性可用链路的可用剩余带宽band（v，e）、时延delay（v，e）（包含数据包在节点的处理时延、排队时延和发送时延）、丢包率loss（v，e）、发送报文所需的代价cost（

8、v，e）（链路费用和传播时延的综合评价）来表示。5OSPF路由选择实现采用十进制编码方案。以路径中节点的十进制标号序列作为路径编码值。比如，路径编码表示的路径为。5.1PSO算法实现算法每次迭代对所有粒子都依次进行“进化、评估、取代”操作。（1）进化。它是算法的核心，对粒子j路径上的每点进行如下操作：①利用式（4）计算并处理第k维飞行速度V[j][k]；②依据式（5）计算第k维位置，记x=（p[j].path[k]+V[j][k]），结果是浮点数，按0.5的概率向上/