基于PSO算法的OSPF多约束路由策略

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

关键词：PSO算法；OSPF；网络路由器；多约束路由；QoS

DOIDOI：10.11907/rjdk.1431035

中图分类号：TP311

文献标识码：A 文章编号：16727800（2015）006007604

基金项目基金项目：安徽省高等教育振兴计划项目（2013zytz063）

作者简介作者简介：江家宝（1968-），男，安徽无为人，硕士，巢湖学院信息工程学院讲师，研究方向为模式识别与智能控制、嵌入式系统、计算机网络；郑尚志（1963-），男，安徽巢湖人，博士，巢湖学院信息工程学院教授，研究方向为操作系统理论、人工智能。

0 引言

随着网络通信要求的不断提高和Internet的飞速发展，路由器成了网络连接中最为关键的设备，路由器中运行的软件对网络连接性能和效率的影响越来越明显。目前，国内外OSPF网络路由器的主流产品仍然使用SPF算法解决路由问题。为缓解网络路由拥塞等瓶颈问题，人们陆续提出了遗传算法、模拟退火算法等多种方法实现OSPF协议。

本文在研究OSPF 协议原理及PSO（Particle Swarm Optimization）算法基本概念和实现方法[1] 的基础上，详细阐述了网络路由选择过程中必须满足的QoS和实时性等多种要求，以及在目标函数值的引导下，如何实现PSO和遗传算法对复杂的OSPF网络路由解空间进行有效搜索[23]，以获得最佳路由和多条次路由，并有效利用这些路由进行路由规划。通过仿真实验验证了将PSO算法应用于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算法实现

算法每次迭代对所有粒子都依次进行“进化、评估、取代”操作。

（1）进化。它是算法的核心，对粒子j路径上的每点进行如下操作：①利用式（4）计算并处理第k维飞行速度V[j][k]；②依据式（5）计算第k维位置，记x=（p[j].path[k]+V[j][k]），结果是浮点数，按0.5的概率向上/下取整后再对（N+1）取余；③这是进化的难点所在，假设路径数组P[j].path[i]≠0， P[j].path[i+1，+2，….，k-1]均为0，则定义P[j].path[i]为P[j].path[k]的前驱节点。若x值非法（是负数、起点、终点、已经经历过的节点），则从[0，N]中随机选取一个合法值给x。若x=0或与P[j].path[i]前驱节点可达，p[j].path[i]=x；否则作如下修正，记p[j].path[i]前驱节点p[j].path[m]的直达节点集合为A，p[j].path[0：m-1]经历过的节点集合为B，从集合A-B中随机选取一点赋给p[j].path[i]。若集合A-B为空，则p[j].path[m]以0.5的概率赋值0，以0.5的概率作上述修正，处理完p[j].path[m]后再重新处理p[j].path[i]。以此类推，极端情况是向前递推处理到p[j].path[1]，这时肯定能从起始位置的直达节点中找一个节点作为p[j].path[1]的值，否则起始节点就是孤立点（无解）；④若p[j].path[i]为终点，则p[j].path[i，i+1，..，N-2]=0，进化结束。若i=N-2，则检查p[j].path[N-1]能否直达前驱节点，若直达则进化结束，否则用类似步骤3的方法处理其前驱节点。

（2）评估。计算粒子各路径特征参数和目标函数值p[j].fit，如果是新路由，则插入按目标函数值降序排列的可达路由链表。

（3）取代。比较目标函数值，若p[j].p_fit

5.2 遗传算法实现

遗传算法[3，9]与PSO的初始化相同。利用锦标赛方法实现选择算子。以概率Pc进行交叉操作，交叉方法是：①找出用于交叉的父代个体A和B路径上的所有相同节点；②从相同节点中随机选取两个用于交叉，产生两个新个体；③若新个体中有相同节点，则删除相同节点间的链路（见图1）。以概率Pm进行变异操作，变异方法是：先对路径节点p[j].path[i]以概率p更新，再仿照PSO进化操作步骤C的方法进行相应处理。

目标函数常量a和b的设置主要看实际网络注重时延和带宽的程度，若侧重于追求时延小，则设置a>b；当某段链路的时延大于Dmax时，罚函数Fd=λ的值设置越小，目标函数值也就越小，一般设置λ≤0.3；当某段链路的带宽小于一定值时，罚函数Fs=μ的值设置越小，目标函数值也就越小，一般设置μ=0.5左右。本文侧重于追求网络时延小，故此目标函数常量设置为：a=0.6、b=0.4、λ=0.1、μ= 0.5。链路特征值的上下限设置取决于实际网络的性能要求，本文设置为：带宽下限Bmin=0.1Mbps、带宽上限Bmax=10Mbps、花费下限Cmin=1、花费上限Cmax=200、时延上限Dmax=250ms、丢包率上限Lmax=0.001。

为便于对比分析，PSO算法和遗传算法的网络拓扑结构、网络状态数据初始化、群体大小（20）、主循环次数（500）都对应相同。遗传算法的交叉概率Pc=0.4，变异概率Pm=0.06。PSO算法参数m按照迭代循环次数线性地从2.0递减到0.01，参数C1取0.2，参数C2取3.0。

6.2 实验结果

选取多对节点进行测试，表1列举了具有代表性的6个节点的仿真结果，表2列举了具有代表性的3对节点的测试结果。

表1的仿真结果表明，在相同时间内（112s），网络主要节点发送和接收的平均速率PSO和遗传算法都比SPF明显提高，并且PSO算法高于遗传算法。提高的主要原因是：SPF中的数据包在连续两次运行SPF期间始终沿前一次求得的唯一最优路径发送，由于网络链路性能时刻在动态变化，重新运行SPF之前原最优路径的性能很可能变得很差，很显然这种做法不合理。PSO和遗传算法能够很好地解决SPF的这种不合理现象，解决方法是一次运行算法求得最优路径和多条次优路径，当前路径性能一旦发生明显恶化就立刻选取相对次优的路径而不必等到下一次运行算法重新路由，这样相对次优路径上的网络资源就得到了有效利用。这说明在性能参数动态变化的OSPF网络中，为了满足QoS要求，快速改变路径是必要的。

表2的测试结果表明，PSO与遗传算法相比，找到的最佳路由目标函数值大多数相同，少数较优，但次路由的目标函数值均值较大方差较小；最佳路由cost值比较接近SPF，而且次路由cost均值和方差都较小；满足QoS要求的路径数量明显增多，运行时间明显缩短；SPF只搜寻一条最佳路径，计算时间显然最短。这说明PSO算法的搜索能力较强、计算效率较高，比较适宜解决多约束OSPF网络路由规划问题。

7 结语

本文重点阐述了PSO算法在OSPF网络路由选择中的具体应用，同时比较了PSO算法、遗传算法和SPF算法的运行结果，通过对比分析可以得出如下结论：在满足QoS要求的多约束OSPF网络路由选择中，与SPF算法相比，PSO与遗传算法能够很好地利用相对次优路径上的网络资源，从而提高网络性能；与遗传算法相比，PSO算法具有搜索能力强、运行效率高等优点。研究表明，PSO算法在满足QoS要求的OSPF网络路由选择领域中具有很好的应用前景，值得进一步研究。

参考文献：

[1]曾建潮，介婧，崔志华.微粒群算法[M].第1版.北京：科学出版社，2004.

[2]魏娟.基于遗传算法的OSPF路由研究[J].科技咨询，2013（22）：3739.

[3]杨云，徐永红，张千目.一种QoS路由多目标遗传算法[J].通讯学报，2004（1）：4351.

[4]李想，李劲.基于OSPF协议的光缆需求算法研究[J].信息通讯，2012（2）：193194.

[5]ANTON RIEDL.Optimized routing adaptation in IP networks utilizing OSPF and MPIS[C].IEEE Xplore，2003：17541758.

[6]WANG XIAOMEI，ZHANG ZHENG，RAN CHONGSHEN.A rerouting strategy in lowearth orbit QoS sattllite networks[J].Journal of Beijing University of Postsand Telecommunication，2005，28（1）：3034.

[7]张倩倩，秦莹莹.基于动态最短路径策略的多QoS路由算法[J].软件导刊，2011，10（6）：3436.

[8]王小明，卢俊岭，李英姝，等.模糊随机环境下的无线传感器网络多约束多路径路由[J].计算机学报，2011（5）：779791.

[9]SCHMITT， LOTHAR M.遗传算法理论[J].Theoretical Computer Science，2004，310（2）：181231.

英文摘要Abstract：The OSPF network routing problems were solved by the use of traditional SPF algorithm， due to not considering the multiconstraint conditions and the effective use of secondary path， once the optimal path occurs to congestion， the network transmission performance will be decreased dramatically. In this paper， the PSO algorithm was applied to the OSPF network routing planning， used by multiconstraint conditions and combined by the characteristics of OSPF network and a variety of routing parameters， which was effectively improved by the local network congestion and obtained the global optimum fast routing and routing algorithm， and verified the improved algorithm by using the simulation data. The results showed that the proposed algorithm gets better improvement than the genetic algorithm and the traditional SPF algorithm in the solution of route planning problem and the network transmission performance.

英文关键词Key Words： PSO； IGP； Routing Tactics； QoS