基于蚁群优化算法的SDN路由策略

刘振鹏，张庆文，李 明，李泽园，李小菲

(1.河北大学 电子信息工程学院 河北 保定 071002；2.河北大学 信息技术中心，河北 保定 071002)

0 引 言

为解决传统网络中分布式特点导致无法全局控制等问题，软件定义网络 (Software Defined Network)[1]被提出并在众多研究者的关注下快速发展.其中，通信网络路由的优化问题[2-5]一直是其研究热点.流量调度问题[6]的研究意义重大，路由选择的优劣决定着网络是否发生拥塞等问题，对网络整体性能有较大的影响，因此关于数据流最优路径的选择问题越来越被重视.

目前针对该问题已经提出很多方案，其中较传统的等价多路径算法(ECMP)[7]根据两个节点间存在多条等价路径的特点，以多条链路组合起来的链路聚合方式增强了吞吐量以及单链路故障时的容错能力，该算法通过计算数据包报头的五元组哈希值选择路径，对同一个目的节点有多条路径可以选择，且这几条路径是等价的，将数据流按照特定分配的方式均匀分配到各等价路径中.但路径中出现多条较大的数据流则容易发生拥塞.最短路径算法[8]为CSPF算法中的一种，其核心思想是在保证跳数最小的链路中选择可用带宽最大的路径作为传输路径.该算法首先根据跳数来选择可用路径，并不能根据网络状态选择最优路径，可能导致链路利用率不高.Awad等人[9]提出一种基于机器学习的多路径路由(MLMR)框架，利用网络状态估计控制器提供的相应路由配置，并学习它们之间的映射功能，实时预测多路径路由.Xu等人[10]提出了一种基于软件定义网络(SDN)的多路径流量调度机制MTSS,该机制利用SDN网络的数据流调度灵活性和多路径特性，改善了云数据中心网络的流量均衡，并提出了一种启发式的MSS流量均衡算法.该算法对网络链路进行周期性监测，动态调整重链路上的流量，实现可编程的数据转发和负载均衡.但在负载较大时会出现严重的网络拥塞现象.在流量调度策略中，选择最优路径的路由算法是该技术的核心，选择最优路径时在保证跳数尽量小的同时，也应该考虑网络的实时负载.

蚁群算法[11]在路由选择中得到较好的应用，但其全局搜索能力较弱，算法容易陷入局部最优解，且收敛速度慢.基于以上不足，本文提出一种蚁群优化算法，通过将算法中的信息素浓度重要程度和挥发系数进行优化，改进为动态参数，使算法前期和后期有着不同的侧重点，算法前期着眼于有效提升全局搜索能力，增加输出结果的可靠性；后期主要解决收敛速度问题，以减少算法运行时间.

1 蚁群算法与蚁群优化算法

1.1 蚁群算法原理

蚁群优化算法是一种仿生学算法，可以用来解决很多问题.在路由选择问题中，将最优路径视为最优解，将其他路径作为能找到最优解的最优解空间.在该过程中，蚂蚁在信息素的作用下选择最佳路径的正反馈机制，最终会让大多数蚂蚁使用最佳路径，从而得出路由问题的最优路径.蚁群优化算法中每只蚂蚁根据信息素的浓度来选择路径[12-13]，路径上的信息素越多，蚂蚁选择该路径的概率越高，信息素也会随时间慢慢挥发，因此在蚂蚁经过较少的路径上信息素浓度会逐渐降低，被选择的概率也渐渐降低.蚁群这种行为产生了一种正反馈机制，随着时间的推移，蚁群渐渐聚集到信息素浓度最高的路径.蚁群算法中，蚂蚁选择路径的概率表示为式：

(1)

在寻路过程中信息素的更新起着重要作用，每次信息素的更新包括两部分：信息素挥发和信息素累加，蚂蚁经过的路径会累加信息素，但如果没有持续累加，该路径信息素浓度会渐渐挥发.其具体更新机制的数学表达式如下：

τij(t+1)=(1-ρ)τij(t)+Δτij(t)

(2)

(3)

式中：τij(t+1)表示信息素更新后的信息素浓度，ρ为信息素挥发系数，Δτij(t)为位置i到位置j的信息素浓度增量，I为蚂蚁数量.

信息素浓度的增量Δτij的计算模型分为三种：蚁量系统模型、蚁密系统模型、蚁周系统模型.其中蚁量系统模型表达式为:

(4)

式中：Q为释放信息素总量，dij为位置i到位置j的距离.

蚁密系统模型表达式为：

(5)

蚁周系统模型表达式为：

(6)

式中：Lk为蚂蚁经过的路径长度.由于本文需要选择链路负载较小且跳数较小的路径，所以本文选用蚁周系统模型，即式(6).路径跳数越多，信息素浓度增量越小，有Lk=mk.

1.2 蚁群优化算法设计

1.2.1 蚁群优化算法

在蚁群算法中，因为靠信息素浓度来决定选择路径的概率，算法很容易陷入局部最优解，导致算法并没有找到最优路径就收敛，搜索能力有限.信息素的更新过于复杂也容易导致算法收敛速度很慢，增加迭代次数.本文对算法的优化在于对信息素浓度的重要程度、信息素浓度更新规则以及信息素挥发机制等方面的改进，以增强算法的全局搜索能力，增加最优路径的可靠性，并简化复杂的信息素更新规则，加快收敛速度.

1)启发函数的定义.启发函数的定义对算法影响较大，必须能较清晰地表达出不同路径的相对优劣.由于SDN控制器可以获取链路的状态信息，可以准确地获得当前链路的负载情况，由此定义：

(7)

(8)

ηij(t)=(1-δij(t))

(9)

2)对信息素浓度重要程度改进.定义每条路径的信息素初始浓度为τ0，在式(1)中α与β为信息素浓度与启发式的重要程度，两个值对算法有着极大的影响.在蚁群算法中，随着信息素浓度的增加，信息素浓度高的路径会聚集更多的蚂蚁，由于正反馈的机制，信息素浓度也会越来越高，往往会造成算法过早地收敛于一条信息素浓度较高的路径，且蚁群一旦开始聚集，这个过程就是不可逆的.本文对算法中的信息素浓度α重要程度进行改进，表达式为：

(10)

式中：nmax表示最大迭代次数，αmax表示信息素浓度重要程度的最大值，二者均为设定的固定值，n为当前迭代次数.α按照(10)定义，其变化趋势会呈现一个平滑增加的曲线，迭代前期，由于迭代次数较小，α的值也较小，此时信息素浓度的影响最低，虽然随着迭代次数的增加，信息素累积，但算法对路径的选择依然主要取决于启发函数，增强了算法的全局搜索能力，迭代后期，路径上信息素浓度较高，且α的值也越来越大，算法迅速收敛，此时算法的最优路径可靠性更高.

3)对挥发系数的改进.因为信息素浓度增量采用蚁周系统模型式(6)，即蚂蚁经过的跳数越多，信息素浓度增量越少.为了避免算法陷入局部最优解，以及加快后期的收敛速度，算法对挥发系数ρ也采用逐步减小的动态参数，其表达式如下：

(11)

式中：ρ为挥发系数，ρmax为信息素挥发系数最大值，ρmin为信息素挥发系数最小值.挥发系数的动态递减设定，首先加强了前期算法的全局搜索能力，最大程度上避免算法陷入局部最优解的可能性，使算法输出的最优路径更可靠.其次算法后期挥发系数的减小，使信息素浓度快速增加，加快后期的收敛.因为信息素挥发系数ρ的取值范围是(0,1)，一般取ρmax的值为：ρmax=1，所以式(11)可以简化为：

(12)

1.2.2 算法步骤

通过对蚁群算法的改进使其更适用于路由选择问题，算法有效地提升了全局搜索能力，且收敛速度较快，蚁群优化算法的具体流程为：

步骤一：初始化网络及参数，包括网络拓扑、链路状态、链路集合、节点集合,和关于蚁群算法的蚂蚁数量I、最大跳数mmax、最大迭代次数nmax、信息素浓度重要程度最大值αmax、启发式重要程度β,以及涉及信息素浓度更新的各链路信息素浓度初始值τ0、挥发系数最小值ρmin、信息素总增量Q.

步骤二：根据式(10)计算本次迭代的信息素浓度重要程度α，由初始节点根据式(1)和式(9)以及式(12)计算选择概率来选择交换机，直至所有蚂蚁到达目的节点或达到最大跳数mmax，单次迭代完成.

步骤三：根据式(2)和式(3)以及式(6)更新信息素浓度τij(t+1)，判断更新迭代次数是否达到最大迭代次数nmax，未达到则重复步骤二.

步骤四：迭代次数达到迭代次数nmax，完成迭代，结束迭代并输出最优路径.

算法流程如图1所示.

图1 蚂蚁优化算法流程图Fig.1 Flow chart of ant colony optimization algorithm

2 仿真实验及结果分析

实验环境以Mininet[14-16]为实验仿真平台，模拟搭建4个pod，四个核心交换机的Fat-Tree结构，如图2所示的SDN网络，使用Ryu控制器作为SDN控制器.并使用Mininet自带的Iperf软件在模拟网络中生成流量负载并设置相关参数，将本文算法和等价多路径算法ECMP和最短路径算法作对比，通过分析实验结果验证本文提出的蚁群优化算法的有效性.

图2 实验拓扑图Fig.2 Experimental topological graph

2.1 实验环境

处理器：INTEL CoreI5-5200U；内存：8GB；操作系统：Ubuntu 16.04；仿真平台：Mininet；控制器：Ryu.

2.2 实验设置

实验采用4个pod的Fat-Tree网络拓扑，交换机为OpenFlow交换机，各链路带宽设置为100 Mb/s.使用Iperf工具产生模拟流量，由于蚁群优化算法相比ECMP算法等更复杂，完成路径选择时间更长，所以并不适合处理占用带宽较小的小流.实验模拟主机向网络随机发送大流，定义向网络中发送的大流的主机数量占比为网络负载.在蚁群优化算法中，初始参数的合理设定十分重要，对算法效果有着决定性的作用.在对部分参数设定范围的研究基础上[17]，设定参数如表1.

表1 算法初始参数值设定Tab.1 Setting of algorithm initial parameters

蚂蚁数量的设定取决于网络的规模，在实验中根据网络拓扑中主机个数将其设定为10.最大跳数的设定如果太大，会增加算法每次迭代的时间，太小会影响算法效果，实验中将其设定为11.最大迭代次数根据相关文献[18]，选择算法迭代50次.信息素重要程度和启发式重要程度有着相对性，算法中由于信息素浓度重要程度是递增的，且为信息素浓度后期收敛的主要参考，所以信息素浓度重要程度最大值设为3，启发式重要程度设为2.信息素初始浓度各链路相同均为1，挥发系数的最小值设为0.5.将本文蚁群优化算法与经典的ECMP和最短路径算法进行对比.

2.3 实验结果及分析

在算法中信息素浓度的重要程度α由公式(10)计算变化，呈递增趋势直到达到最大值αmax，如图3所示.其变化趋势相对启发式的重要程度来看算法前期信息素浓度的大小对蚂蚁选择下一跳位置的影响并不大，最大程度地避免了算法前期陷入局部最优解，增强了全局搜索能力，后期随着α的逐渐增大，信息素的累积也逐渐增加，蚂蚁开始趋向收敛于信息素积累较多的路径中，最后α继续增加，超过启发式重要程度，所有蚂蚁收敛于一条路径.

图3 信息素浓度重要程度α与启发式重要程度β变化趋势Fig.3 Change trend of pheromone importance α and heuristic importance β

挥发系数如式(12)变化，随着迭代次数增加，挥发系数ρ由大到小递减，如图4所示.前期挥发系数较大，后期挥发系数逐渐减小，和信息素浓度重要程度α相互影响下，前期信息素浓度的影响会比较小，对算法全局搜索能力有显著的提升以及后期的收敛也会较明显.

图4 挥发系数ρ随迭代次数n增加的变化趋势Fig.4 Variation trend of volatilization coefficient ρ with the increase of iteration times n

1) 链路利用率对比.网络链路利用率指的是被利用链路数目占链路总数比例.相同负载下，链路利用率越高，表示网络流量分布越均匀，算法性能越强.图5为网络中链路利用率的对比结果，随着网络负载的逐渐增大，链路利用率逐渐增加.当网络负载达到一定程度后，由于蚁群优化算法对于网络链路负载的计算，其链路利用率高于ECMP和最短路径算法，后期网络负载达到1时，本文算法较ECMP链路利用率提升17.1%，ECMP是将同一目的节点的数据包按特定分配方式，均匀分配到多条等价路径上，因此在负载达到一定程度后该算法缺乏对于网络链路差异性的判断，所以其链路利用率最低.本文算法相较最短路径算法链路利用率提升9.9%(见表2)，最短路径算法侧重于根据跳数寻找最优路径，然后在具有最小跳数的路径中选择可用带宽最大的路径，且一旦需要重新计算路径时也会从剩余的几条最小跳数路径中选择带宽最大的路径作为输出结果，该算法注重跳数的优势，链路利用率较低.

图5 链路利用率对比Fig.5 Comparison of link utilization

表2 负载为1时蚁群优化策略链路利用率和相对提升Tab.2 Link utilization and relative promotion of ant colony optimization strategy when load is 1

2) 网络平均吞吐量对比.网络的平均吞吐量是指网络系统在单位时间吞吐量的平均值，其直观地反映了网络的传输性能.图6为平均吞吐量对比，ECMP在三种算法策略中平均吞吐量是最低的，其中等价路径分配模式很容易造成网络拥塞，从而导致其平均吞吐量最低，最短路径算法首先选择跳数最小的路径，然后在选择跳数最小的路径中带宽最大的路径，减少了网络拥塞发生的机率.本文算法将链路负载和路径的跳数同时代入计算，选择的最优路径可靠性更高(见表3).

表3 负载为1时蚁群优化策略平均吞吐量和相对提升Tab.3 Average throughput and relative improvement of ant colony optimization strategy when load is 1

图6 平均吞吐量对比Fig.6 Average throughput comparison

3 总 结

本文提出了一种基于蚁群优化算法的SDN网络路由策略，蚁群优化算法作为动态路由算法其复杂度高于等价多路径算法ECMP，因此蚁群优化算法更适用于处理网络中占用带宽较大的大流.通过将蚁群算法中的信息素浓度重要程度和挥发系数由固定参数改进为动态参数，使算法更适用于网络中的路由算法，同时解决了蚁群算法自身全局搜索能力弱、收敛速度慢的不足.