SDN网络中基于改进粒子群的最优路径规划算法

于立婷，谭小波，吴艳梅

(沈阳理工大学 信息科学与工程学院，沈阳 110159)

近年来，网络流量暴涨，网络规模不断扩大，对于网络的性能要求也逐渐提高，传统网络架构难以应对突发大数据流产生的链路拥塞，因此许多学者提出通过流量控制的方式解决此问题[1]。然而传统网络架构下的流量控制技术，在网络动态变化时不能及时获取全网流量信息。并且采用编写路由协议的方法部署各项业务，各个协议只针对单个独立业务所设计，因此只能优化网络中的局部链路，不能达到全网最优的效果，使得流量控制研究一度停滞不前。后来一些学者开展了网络便捷化的研究，软件定义网络[2](Software Defined Networking，SDN)应运而生。

SDN是一种优化和简化网络操作的体系结构方式，具有数据层与控制层分离、灵活的可编程能力、集中式的控制模型等优势，能够快速部署新型网络，并减少网络资源消耗[3]。与传统网络的流量控制方式不同，基于SDN的网络流量控制是在拓扑发现、链路监测的基础上，通过控制器端集中式的路径计算来提高网络性能。SDN网络流量控制的关键在于合理、高效的规划网络路径。大部分研究者采用人工智能领域的几种算法[4-6]，代替传统的Dijkstra算法计算最优路径。遗传算法(Genetic Algorithm，GA)是从生物学角度出发，通过分析生命进化的规律，将路径规划问题模拟成生物体遗传、进化的一种寻优算法[7]。该算法具有良好的自学习能力，可以随着进化过程寻找最优解，但算法的局部寻优能力较弱，易出现“早熟”的情况；蚁群算法(Ant Colony Optimization，ACO)是通过模拟蚂蚁寻找食物的过程而提出的一种智能自组织算法[8]，蚂蚁的智能行为是通过信息正反馈的原理寻找最短路径。但是蚁群算法在计算最优路径时设置的参数比较多，算法复杂度过高；粒子群算法(Particle Swarm Optimization，PSO)，是通过对鸟群迁徙等飞行活动规律的研究，开发的一种迭代优化算法[9]。该算法通过当前位置、个体最优解与全局最优解三项基本信息迭代寻找最佳路径。相比于上述两种算法，PSO没有“交叉”和“变异”等复杂操作，算法流程更为简单，且具备较强的收敛性，适用于搜索最优路径。但PSO在规划最优路径时，仍存在一定缺陷，表现为收敛速度慢且会出现过早收敛并产生局部极值，影响算法性能。

针对上述两点缺陷，本文结合SDN的特性对标准PSO进行优化，提出采用优化参数以及变异全局最优解的方法改进标准PSO，使其更适用于解决路径计算问题。仿真结果表明，改进的PSO极大程度的消除了收敛不稳定性和易出现局部极值的问题，并且对网络中可能出现的大数据流进行正确的路径规划，进而达到了避免网络拥塞的效果。

1 IVPSO路径规划算法

标准PSO不能有效解决路径规划问题，本文将对标准PSO的缺陷进行详细分析，采用优化参数以及变异全局最优解的方法改进标准PSO算法，进而提出一种最优路径规划算法IVPSO。

1.1 标准PSO算法

标准PSO算法是把路径规划问题看作在空中寻找食物的鸟群，“食物”便成为该问题的最优路径，“鸟”便是粒子。在PSO中，每个粒子用四项信息来更新自身的位置，PSO的初始化过程如下所示。

设某粒子群由m个粒子形成，而第i个粒子在D维向量中的飞行速度为

vi=(vi1,vi2,…，vim)

第i个粒子的D维向量表示的粒子位置为

xi=(xi1,xi2,…，xiD)

当前情况下，第i个粒子在D维向量中的最佳位置为

pbest_i=(pbest_i1,pbest_i2,…，pbest_iD)

当前情况下，所有粒子在D维向量中的最佳位置为

gbest_i=(gbest_i1,gbest_i2,…，gbest_iD)

速度、位置更新公式为

vid(t+1)=w×vid(t)+c1r1(pbest_id-xid(t))+

c2r2(gbest_id-xid(t))

(1)

xid(t+1)=xid(t)+vid(t+1)

(2)

式中：vid(t+1)是指此时此刻粒子在d维的速度；vid(t)是指上一时刻在d维的速度；xid(t+1)是指此时此刻在d维的位置；xid(t)表示上一时刻在d维的位置，且1≤i≤m， 1≤d≤D；w为惯性权重；c1和c2是学习因子， 取值为非负常数；r1、r2为[0,1]的随机数；pbest_id是第i个粒子在d维的个体极值点；gbest_id是整个种群在d维的全局极值点。

1.2 IVPSO算法

标准PSO算法有较强的收敛性和较少的参数种类，因此应用于材料、交通等许多领域。但在某些具体的应用中，粒子群算法也存在一定程度的局限性。本文研究基于SDN网络的路径计算采用标准PSO算法存在两点缺陷。若PSO中参数选择不当，则会出现局部极值问题。在路径计算时，某一节点选择当前情况下最优的下一跳节点，而其他节点向其学习，导致剩下节点都不能在全局范围搜索最优路径，造成局部最优；在PSO后期易出现收敛速度缓慢或者过早收敛的情况，收敛速度主要体现在迭代次数，迭代速度慢或过早趋于收敛状态并不利于计算出最优路径。

根据上述对标准PSO算法的缺陷详细分析，本文选择调整惯性权重以及变异全局最优解的方法改进标准PSO算法来解决上述问题。

1.2.1 调整惯性权重w

通过式(1)可以看出，w会根据前一时刻的粒子速度影响当前时刻的粒子速度，标准PSO算法将惯性权重w取值设置为1，这对粒子速度没有任何影响[10]。而在SDN网络中，网络的拓扑是动态变化的，因此w的取值不应设置为固定常数，应动态取值。但若w的取值较小，则会造成局部极值，若w的取值较高，则会降低搜索的速度。因此根据SDN网络特性，将w值随着迭代次数的增加而减小，从而实现算法收敛性的提高。本文将对w的进行动态取值，将w由wmax逐渐缩减到wmin，动态改变取值的公式步骤为

(1)由标准PSO算法的速度式(1)和位置式(2)可以得式(3)。

vid(t+2)=w×vid(t+1)-(c1r1+c2r2)(xid(t)+vid(t+1))+c1r1pbest_id+c2r2gbest_id

(3)

(2)当前时刻迭代速度、下一时刻迭代速度之间的关系。

-(c1r1+c2r2)xid(t)=vid(t+1)+wvid(t)-

(c1r1pbest_id+c2r2gbest_id)

(4)

(3)粒子的速度关系式如式(5)所示。

vid(t+2)+vid(t)(c1r1+c2r2-w-1)+vid(t)×w=0

(5)

(4)同理可以推出粒子的位置变化公式，如式(6)所示。

xid(t+2)=(1+w-c1r1-c2r2)xid(t+1)-

wxid(t)+c1r1pbest_id+c2r2gbest_id

(6)

(5)通过解析式(5)粒子速度公式和式(6)粒子位置公式，得出粒子的速度越大，位置就会越发散，而粒子位置的发散致使群体稳定性严重下降。如要保证粒子的速度和位置稳定性，通过计算发现w、c1和c2应当满足条件式(7)。

(7)

(6)本文对参数w设置如式(8)所示。

(8)

1.2.2 变异全局最优解gbest

通过调整惯性权重w提高了算法收敛性，但却存在可能出现过早收敛而造成局部极值的问题，因此要对全局最优解gbest进行变异。首先，对该算法设置一个最小收敛度因子∂min，并将当前收敛度∂与最小收敛度因子∂min进行比较，若∂≤∂min，则认为该算法出现过早收敛问题，∂的计算公式如式(9)所示。

(9)

(10)

式中：fi是第i个粒子的适应值；favg是当前所有粒子的平均适应值；fmax是当前粒子中的最大适应值；∂越小，粒子群越接近过早收敛，当∂≤∂min，则粒子过早收敛造成局部极值。

在确定了收敛度因子后，开始对全局最优解gbest进行变异，本文主要采取分治算法的基本思想，并结合随机扰动，将粒子群分解成n个子群，全局最优问题被分解成n个子群的最优求解问题，即gbest=(gi1best,gi2best,…，giDbest)。对gijbest按照式(11)的方法进行变异。

gijbest=gijbest×(1+0.618η)j=1,2,3…D

(11)

式中随机变量η服从均匀分布。根据分治思想，计算n个子群的全局最优值gibest的平均值，进而计算整个粒子群的全局最优解gbest，如式(12)所示。

(12)

式中t表示迭代次数。采用多次迭代的方法计算出各个子群的全局最优值gibest，进而计算出n个子群平均值。

2 仿真验证与结果分析

针对标准PSO算法存在的收敛性不稳定以及易产生局部极值的问题，通过优化参数以及变异全局最优解的方法进行改进，进而提出了一种最优路径规划算法IVPSO。对IVPSO进行仿真验证，为了准确获得IVPSO的收敛速度以及搜索范围，在Matlab7.6环境下对标准PSO、只优化参数的PSO以及IVPSO进行仿真，并采用优化领域常用的两种函数对上述三种算法进行验证，测试函数如表1所示。

将Sphere和Rastrigrin函数作为适应度函数，分别验证上述算法的两类性能。Sphere函数的关注点在于求解速度，也就是收敛速度，并且将收敛速度最优取值设置为0；Rastrigrin函数的关注点在于搜索范围，也就是局部极值问题。本文将进行50次实验来验证适应度值的准确性，并对实验结果计算加权平均数，仿真环境参数设置如表2所示。

表1 仿真测试函数

表2 仿真环境参数设置

图1为函数f1适应度值的对数曲线。

如图1所示，三条曲线都是基于Sphere函数实现的，可以看出IVPSO算法比标准PSO算法与只优化w的PSO算法更好地平衡了粒子的社会学习能力和个体学习能力，使IVPSO算法适应值更接近最优值并且IVPSO算法的收敛速度更快，即在相同的迭代次数下，IVPSO算法的适应度值更接近于最优解。

图2为函数f2适应度值的对数曲线。

图1 函数f1适应度值的对数曲线

图2 函数f2适应度值的对数曲线

如图2所示，三条曲线都是基于Rastrigrin函数实现的，比较三条曲线在适应度函数下的变化情况可以看出，PSO算法与只优化w的PSO算法收敛速度慢并且误差较大，而IVPSO算法在迭代的前150次快速收敛，并达到极优值，在迭代150次后无限接近于最优值。仿真结果表明，IVPSO算法的收敛速度较其他两种算法明显加快，更有利于解决局部极值问题。

上述仿真结果表明，IVPSO算法在解决局部极值和过早收敛等问题上取得显著效果，为了进一步验证 IVPSO算法的性能，将IVPSO算法运用到SDN网络流量控制模拟环境中，测试该算法对于流量控制的有效性以及实用性。

首先对SDN网络进行模拟配置：在物理机(ubuntu 13.10)上安装Floodlight控制器，负责监听和集中控制底层网络的拓扑信息；然后安装virtualbox并在其上安装mininet，在mininet中可以掌握多种类型网络的拓扑；接下来在宿主机上搭建SDN网络环境，并将路径计算模块模拟实现在主机上；最后在mininet中建立两个数据中心的底层网络，其结构如图3所示。

图3 底层网络结构图

本文的测试环境参数设置如下，链路的带宽B：20Mbit，链路时延DT：5ms，丢包率P：10，链路的队列最大长度：1000。

依照参数设置，在Floodlight控制器上运行最优路径规划算法IVPSO。Floodlight控制器可以实现网络瞬时状态的管理，进而实时获取整个网络的状态信息以及网络拓扑结构。模拟系统在监测动态变化的网络流量时，对突发的大数据流采用IVPSO算法规划最优路径。将启用IVPSO算法的SDN网络与常态下的SDN网络的链路性能进行测试对比。

本文将网络时延、丢包率两项参数作为检验网络链路性能的指标，采用iperf测试软件进行测试，并且对自定义的两种状态下的底层网络分别进行十组实验，监测到的网络链路情况如下，图4、图5分别表示SDN网络的时延情况与丢包率情况。

图4 时延

图5 丢包率

如图4、图5所示，采用IVPSO算法进行路径计算后的SDN网络，其时延和丢包率明显降低，即基于IVPSO算法的SDN流量控制技术对于网络性能有明显的提升。该流量控制技术可以将网络时延保持在0.3ms偏下的水平，并维持相对平缓的曲线，且将丢包率保持在0.5%偏下的水平，并维持相对平缓的曲线，这表明基于IVPSO算法的流量控制技术对突发的大数据流的链路分配比较均衡，实现各项业务的快速完成，从而避免了链路拥塞。

3 结束语

在SDN架构下，针对网络流量暴涨产生的网络拥塞问题，对可能产生的大数据流进行流量控制，并将路径规划作为流量控制的关键环节，提出了最优路径规划算法IVPSO。该算法采用优化参数和变异全局最优解的方法改进标准PSO，改进后的PSO算法IVPSO收敛速度明显加快，并且可以有效避免局部极值的产生。采用IVPSO算法对网络突发的大数据流进行路径规划，可以较好的解决网络拥塞问题，极大的减轻网络流量负担，提高了网络性能。