推荐阅读：摘要：利用传统SPF算法解决OSPF网络路由难题时，由于没有考虑多约束条件和有效利用次路径，一旦最优路径发生拥塞，网络传输性能将急剧降低。将PSO算法应用于OSPF网络路由规划，利用多约束条件并结合OSPF网络多种路由参数的特性，重点对有效改善网络局部拥塞
摘要：利用传统SPF算法解决OSPF网络路由难题时，由于没有考虑多约束条件和有效利用次路径，一旦最优路径发生拥塞，网络传输性能将急剧降低。将PSO算法应用于OSPF网络路由规划，利用多约束条件并结合OSPF网络多种路由参数的特性，重点对有效改善网络局部拥塞和快速求得全局最佳路由及若干次路由算法进行探究，并利用仿真数据对所提出的改进算法进行验证。结果表明，在解决OSPF网络路由规划问题中，PSO算法较传统遗传算法和SPF算法能实现网路传输性能更优。
关键词：PSO算法；OSPF；网络路由器；多约束路由；QoS
DOIDOI：10.11907/rjdk.1431035
中图分类号：TP311
基金项目基金项目：安徽省高等教育振兴计划项目（2013zytz063）
作者简介作者简介：江家宝（1968-），男，安徽无为人，硕士，巢湖学院信息工程学院讲师，研究方向为模式识别与智能控制、嵌入式系统、计算机网络；郑尚志（1963-），男，安徽巢湖人，博士，巢湖学院信息工程学院教授，研究方向为操作系统理论、人工智能。
0 引言
随着网络通信要求的不断提高和Internet的飞速发展，路由器成了网络连接中最为关键的设备，路由器中运行的软件对网络连接性能和效率的影响越来越明显。目前，国内外OSPF网络路由器的主流产品仍然使用SPF算法解决路由问题。为缓解网络路由拥塞等瓶颈问题，人们陆续提出了遗传算法、模拟退火算法等多种方法实现OSPF协议。
1 OSPF协议原理
路由指在网络数据传输中采用某种策略为数据包从源点到达目的地点寻找一条理想路径。基于全局最优思想，网络设备为转发的数据包选择某种距离测度下的最优路径，沿最优路径发送数据包。支持OSPF协议的SPF算法在传送业务服务模式的网络中效果较好，但其无法满足多媒体业务的QoS需求[45]，主要表现如下：①SPF采用与链路带宽成反比的cost值度量距离来寻找最优路径，没有考虑其它约束条件，不能满足日益复杂的网络性能要求；②SPF忽略了次路由，一旦最优路径发生拥塞，其它可用路径被闲置，将大大降低网络传输性能。
拥塞时，网络时延和丢包率会剧增，若采用时延和丢包率来度量最优路径，可将流量转移到另一条路径上，但这种转移是全部转移，新路径又会由于负荷过重而拥塞，而原来的路径又会空闲，这样容易引起路由振荡。因此，需要选取新的OSPF实现方法，使其能满足日益复杂的QoS要求。
2 QoS路由问题
CCITT给出QoS的定义[67]为：“QoS是一个综合指标，用于衡量使用一个服务的满意度。”而现有的Internet都只是提供besteffort传送，不能提供QoS保证。为了适应网络的发展需求，Internet2工作组提出的新草案对QoS要求如下：①提供可计量的服务；②支持高级应用（如双向交互音/视频、远程控制等）；③良好的可扩展性；④可管理性；⑤能与终端用户操作系统和中间件协同工作等。要求QoS选路既要可行（即可达），又要有效（即最小化占用链路带宽，最小化链路拥塞等）。因此，为了满足QoS路由要求，路由规划时首先考虑如何有效利用网络资源，其次考虑如何减少路由计算的时间复杂性。
本文首次采用经过PSO算法修正的OSPF路由来解决上述问题。
3 QoS路由模型
网络链路的双向特征一般存在差异，网络的拓扑结构可用有向图G=（V，E）来描述（V为网络节点集合，E为节点间链路集合）。链路（v，e）的特性可用链路的可用剩余带宽band（v，e）、时延delay（v，e）（包含数据包在节点的处理时延、排队时延和发送时延）、丢包率loss（v，e）、发送报文所需的代价cost（v，e）（链路费用和传播时延的综合评价）来表示。
5 OSPF路由选择实现
采用十进制编码方案。以路径中节点的十进制标号序列作为路径编码值。比如，路径编码表示的路径为。
5.1 PSO算法实现
算法每次迭代对所有粒子都依次进行“进化、评估、取代”操作。
6.2 实验结果
表2的测试结果表明，PSO与遗传算法相比，找到的最佳路由目标函数值大多数相同，少数较优，但次路由的目标函数值均值较大方差较小；最佳路由cost值比较接近SPF，而且次路由cost均值和方差都较小；满足QoS要求的路径数量明显增多，运行时间明显缩短；SPF只搜寻一条最佳路径，计算时间显然最短。这说明PSO算法的搜索能力较强、计算效率较高，比较适宜解决多约束OSPF网络路由规划问题。
7 结语
本文重点阐述了PSO算法在OSPF网络路由选择中的具体应用，同时比较了PSO算法、遗传算法和SPF算法的运行结果，通过对比分析可以得出如下结论：在满足QoS要求的多约束OSPF网络路由选择中，与SPF算法相比，PSO与遗传算法能够很好地利用相对次优路径上的网络资源，从而提高网络性能；与遗传算法相比，PSO算法具有搜索能力强、运行效率高等优点。研究表明，PSO算法在满足QoS要求的OSPF网络路由选择领域中具有很好的应用前景，值得进一步研究。
