基于改进布谷鸟搜索算法的多控制器部署方案*

杨晓琴

(太原广播电视大学，山西 太原 030024)

0 引 言

随着有线网络规模的急剧膨胀，原有的网络技术无法满足无线终端的需求. 因此，软件定义网络[1-2](Software defined networks, SDN)提出将网络的数据层与控制层解耦，采用集中控制的方式提高无线网络的控制能力. 相比原有的网络架构，SDN提高了网络控制的灵活性，增强了网络新技术的支持能力.

SDN通过南向接口，实现控制层与数据层的交互，当前主要的通信协议有OpenFlow, HyperFlow, Cross Flow等. SDN的网络状态主要由控制器[3]负责，随着SDN控制元素的增长，一个SDN控制器由于自身能力的限制，难以控制所有元素. 同时，单个控制器一旦发生故障，会造成整个网络的瘫痪. 主流方式是在SDN网络中分布式部署多个控制器，提高大规模网络的控制能力. 但在大规模网络部署中，控制器的数量和位置决定了网络的成本，因此如何有效合理地部署控制器是SDN中的难点. 软件定义网络的多控制器部署问题由Heller提出[4]，目前已经吸引了很多学者研究，模型主要考虑节点的平均时延和最小时延，解决方法主要有聚类方法[5]、模拟退火算法[6]、粒子群算法[7]等.

Yang等人于2009年提出了一种新的智能优化算法——布谷鸟搜索算法(Cuckoo Search，CS)[8]. 该算法是Yang等人基于布谷鸟巢寄生行为所提出的. 与其他智能优化算法相比，该算法易于实现、操作简单，在许多最优化问题的处理结果更有优势，并且已经成功应用于很多工程领域[9-10]. 赵专政等[11]使用布谷鸟算法对文本进行分类，提高了分类效率. 胡宗庆[12]利用布谷鸟算法拟合模型参数，使指数曲线模型参数的求解更加方便，模型的精度更高. 高述涛[13]提出一种CS算法优化BP神经网络参数的短时交通流量预测模型. 姚远远等[14]尝试采用CS算法来求解JSP问题也达到了很好的效果.

因此，为了提高CS算法的搜索性能，避免算法陷入局部最优，本文提出了一种改进的CS算法，将改进的CS算法应用到SDN控制器部署问题，并通过仿真实验验证本文所提出方法的有效性.

1 多控制器部署问题

1.1 问题描述

由于单一控制器的处理能力有限，对于大规模广域网来说，使用单一控制器通常无法及时有效地处理来自所控交换机的所有请求. 如果在大规模广域网上部署SDN，那么就需要使用多个控制器. 不可避免需要解决以下问题：对于一个给定的网络拓扑，需要多少控制器并且这些控制器应该部署在哪些位置，才能实现控制器的合理部署，从而使得整个网络的目标性能达到最优. 这就是所谓的多控制器部署问题，非常值得深入研究.

1.2 模型建立

假设在网络拓扑G(V,E)中，其中V代表网络中的节点，E代表网络拓扑中的边. 多控制器部署问题的模型建立如下：

Minimizef(x)+g(x),

(1)

(2)

(3)

约束条件如下：

1) 假设控制器的个数总数是N.

(4)

2) 每个控制元素只能被一个控制器控制.

(5)

3) 每个控制器最多管理L个元素.

(6)

2 基于改进布谷鸟算法的多控制器部署方案

2.1 布谷鸟搜索算法

布谷鸟算法[15-17]是一种新型的智能优化算法，这种算法源于模拟布谷鸟巢寄生的行为和莱维飞行习性两个方面. 该算法相比于其他算法的特别之处是搜索路径不同，它的搜索方式是Levy飞行，Levy飞行由两部分组成：一是方向，二是步长，方向按照均匀分布进行选择，而步长选择是服从Levy分布的游走步长. 在CS算法中，步长的选择是利用具有Levy分布特征的Mantegna法则来完成的. Levy飞行可以在不确定的区域中最大限度地进行有效搜索. 该算法比较简单，参数少，易于实现，具有很好的全局搜索能力，因此受到国内外许多学者的关注.

布谷鸟算法基于以下三个理想化的条件：

1) 每只布谷鸟随机选择一个鸟窝，并放置一个蛋；

2) 表现好的鸟窝将会被保留至下一代，这样可以保证算法能够获得更优解；

3) 可以选择的鸟窝数量n是固定的，另外鸟窝中的鸟蛋被发现的概率是Pa，且Pα∈[0,1].

基于以上三个理想化的条件，布谷鸟搜索算法主要包括局部搜索和全局搜索两种位置更新公式. 其中，全局搜索位置更新公式为

⊕Levy(β),

(7)

(8)

式中：μ和ν服从标准正态分布，β=1.5.

(9)

(10)

2.2 改进的布谷鸟搜索算法

为了提高算法的局部搜索能力，本文在进行局部搜索时让个体朝着全局最优的方向搜索，保证算法更新方向的有效性，具体公式修改如式(11)所示

(11)

(12)

此外，如果让全部个体采用公式(8)进行局部搜索，一直朝着较优个体的方向搜索，从而导致算法陷入局部最优，影响算法性能. 为了规避较优个体陷入局部最优，进一步提出改进布谷鸟算法(Motified cuckoo search algorithm, MCS).

首先对所有个体按照优劣依次排序，然后将种群划分为两部分. 较优种群按照公式(10)进行局部搜索，由于这些个体当前位置较优，在进行局部搜索时按照式(10)搜索范围增大. 较差种群按照公式(11)进行局部搜索，由于这些个体当前位置较差，在进行局部搜索时依赖历史最优位置的信息，提高个体搜索精度. 通过这样改进，布谷鸟算法种群整体的局部搜索能力增强，并且具有跳出局部最优的能力. 经实验验证，较优种群与较差种群的数量比为1∶9时，性能最佳.

2.3 基于改进布谷鸟算法的多控制器部署方案

本文利用改进的布谷鸟算法对大规模广域网多控制器部署问题进行研究，以期达到最小的控制开销，从而实现多控制器的合理有效部署. 本文主要研究的对象是由支持Openfllow的交换机和多个有容量限制的控制器所组成的大规模广域网，并且每个控制器都维持一个全局网络视图. 根据Openfllow协议，在任何时候网络中一个交换机都至少与一个控制器相连接. 算法具体步骤如下：

Step 1： 输入SDN控制器个数，网络拓扑，布谷鸟位置及参数；

Step 2： 按照公式更新每个布谷鸟位置；

Step 3： 根据公式计算每个位置的适应值；

Step 4： 是否满足终止条件，若否，转到step2；

Step 5： 输出控制器位置和平均时延.

3 仿真实验

不同的网络拓扑具有不同的复杂度. 因此，这里将在两个网络拓扑上进行实验验证，这两个拓扑如图 1 所示.图1(a)是斯坦福大学提出的第二个网络OS3E，SDN部署由34个节点和41个边组成.图1(b)是联通主干网，由35个节点和38个边组成. 这两种拓扑几乎都接近于真实网络. 本文的算法用MATLAB编写，并在英特尔I5和4GB RAM的机器上运行. 算法的粒子数为20，迭代次数是50代. 每个算法的具体参数列于表 1 中.

图 1 网络拓扑图Fig.1 Network topologies表 1 算法参数设置Tab.1 Parameters of algorithms

算法参数GAPc=0.8, Pm=0.1PSOc1=2.0, c2=2.0, w(0.9→0.4)CSPa=0.25, a=1

本文将MCS与其他两种启发式算法在网络拓扑上进行比较. 所涉及的算法为： 遗传算法(Genetic Algorithm，GA)，粒子群算法(Particle Swarm Algorithm，PSO)，布谷鸟算法(Cuckoo Search Algorithm，CS).

为了验证该算法的性能，实验采用不同的控制器数目. 随着控制器的增加，多控制器部署问题的复杂性将大大增加.

图 2 给出了不同控制器数之间平均潜伏期的变化. 由图2(a)可以看出，MCS在这个网络拓扑上的所有控制器号码中具有最好的性能，略优于CS，粒子群优化算法和遗传算法相对较差. 由图2(b)可以看出，MCS性能优于其他三种算法，PSO的性能稍差于CS，其中GA具有最差的性能. 综述所述，MCS可以通过改进的搜索策略跳出局部最优，在两个网络拓扑上具有更好的全局最优.

4 结束语

本文研究了软件定义网络中的多控制器部署问题. 为了实现平均等待时间和处理时间之间的折衷，提出了一种新的布谷鸟搜索算法. 问题函数考虑了三个部分： 控制器和控制元素、控制器和控制器之间的平均等待时延. 在两种网络拓扑进行了仿真，实验结果表明，该算法比其他算法具有更好的性能. 在今后的工作中，我们将研究动态网络拓扑中的多控制器部署问题.