0 引言

软件定义网络 (Software Define Network, SDN)^[1]的标志性特点是将控制平面和数据平面解耦，实现集中化的网络控制。分布式控制器架构在破解控制器性能瓶颈, 在解决单点失效的同时，也带来了负载不均的问题。由于已提出的分布式控制器构架，如HyperFlow^[2]，其控制器与交换机之间是静态的映射关系，不能适应交换机请求流量的变化，容易造成控制器资源的失衡。

ElastiCon^[3]是第一个弹性的分布式的控制器架构。在该架构中，控制器与交换机维持一种动态的映射关系，过载控制器下的交换机可以迁移到负载较轻的控制器下。ElastiCon为控制器设定一个指定的负载域，负载过大或过小时，执行交换机迁移或删除控制器的操作。交换机迁移的方式为控制器负载均衡研究提供了新的思路，其实现方法简单，控制灵活可靠，已经成为研究的热点; 但ElastiCon提出的迁移策略并不完善，在该体制下，交换机只能迁移到邻近的控制器。就近迁移是一种局部的调动，当网络中某个区域负载较重时，该方法就失去了它的作用。

对比就近迁移策略 (Lowest Utilization Migration Algorithm, LUMA)^[4]将交换机迁移至剩余资源使用率最低的控制器来实现负载均衡，这种方法跳出了区域的限制，在整个网络中寻找空闲资源; 但交换机与控制器之间的传输时延是受限制的，时延过大会引起数据延迟、控制一致性等问题，这就要求交换机与控制器之间的距离必须受到限制。另外，这种距离上不加限定的迁移策略还容易产生交换机的跨域通信问题。

针对负载均衡与传输时延两方面因素，文献[5]提出基于改进型拍卖的交换机迁移机制 (Progressive Auction based Switches Migration Mechanism, PASMM)，将交换机的迁移问题优化成为控制器剩余资源的拍卖问题。其中，传输距离作为交换机对控制器估价函数的参数，以此来影响交换机的选择；文献[6]提出基于免疫粒子群算法的动态交换机迁移策略 (Dynamic Switches Migration Algorithm, DSMA)，将最小化负载均衡度和传输距离的加权和作为优化目标，通过免疫粒子群算法求解。PASMM中传输距离与估价函数成反比，交换机近距离优先选择控制器，当局部负载较重时，算法收敛速度较慢。而DSMA优化目标是负载均衡度与传输距离加权和，在负载较重时，不能保证控制器不过载。

本文在负载均衡和传输时延的基础上，进一步考虑交换机迁移过程产生的网络代价，提出基于改进引力搜索算法的交换迁移策略 (Switch Migration Strategy based on Improved Gravitation Search, IGS-SMS)。在该迁移策略中，用模糊满意度为三种优化目标设定权重，根据权重大小选择优先优化的目标，通过改进引力搜索算法快速求解。

1 问题建模

在本文的网络实例中，采用带内模式的co-located部署方案，也就是控制器与交换机节点部署在同一位置，且控制信息与数据信息采用相同的信道^[7]。网络拓扑结构如图 1所示。在图 1网络中有30个节点，每个节点位置有一台交换机。5个控制器分别部署在节点4、11、14、23、26处。

设在SDN中有M个控制器C={c₁, c₂, …, c_M}，控制器的容量CA={a₁, a₂, …, a_M}。交换机的数量为N，表示为S={s₁, s₂, …, s_N}。交换机分布矩阵X =(x_ij)_M×N，式中：

$ {x_{ij}} = \left\{ {\begin{array}{*{20}{l}} {1,}&{交换机j隶属于控制器i}\\ {0,}&{其他} \end{array}} \right. $

控制器资源使用率阈值为TH={th₁, th₂, …, th_M}，当控制器资源使用率超过阈值时，控制器过载，触发交换机迁移机制。

定义1    目标负载，定义为各控制器资源使用率中的最大值。

$ {f_1} = \mathop {\max }\limits_{i = 1,2,...,M} \left( {\left( {\sum\limits_{j = 1}^n {{r_j} \times {x_{ij}}} } \right)/{a_i}} \right) $

其中:r_j为交换机s_j的建流请求消息数，这是由于控制器的CPU负载主要来自于对交换机消息的处理，而建流请求消息所占的比例最大，因此可用建流请求消息数衡量控制器的负载。设μ_i为控制器的资源使用率，负载均衡度$\rho = \frac{1}{m}\sum\limits_{i = 1}^m {{{({\mu _i} - \bar \mu )}^2}} $是衡量负载均衡的重要指标，但负载均衡度无法描述过载状况，尤其是整体负载较重时，以负载均衡度为优化目标不能保证控制器无过载。因此选择目标负载作为衡量标准，f₁越小说明控制器负载越均衡。

定义2    平均传输时延，用交换机到控制器的平均最小传输跳数衡量。

$ {f_2} = \left( {\sum\limits_{i = 1}^M {\sum\limits_{j = 1}^N {l({c_i},{s_j}) \times {x_{ij}}} } } \right)/N $

为直观说明，以交换机到控制器的最小传输跳数衡量传输时延。其中l(c_i, s_j) 为交换机s_j到控制器c_i的最小跳数。f₂越小则说明平均传输时延越小。

定义3    交换机迁移数，用于衡量交换机迁移过程的代价，表示为f₃，指某时刻交换机分布矩阵的列与原交换机分布矩阵对应列不相同的数量。

优化模型为：

$ \min \;\;{f_1},{\kern 1pt} {f_2},{\kern 1pt} {f_3} $

(1)

$ {x_{ij}} \in \{ 0,1\} ;\quad \forall i,j $

(2)

$ \sum\limits_{i = 1}^M {{x_{ij}} = 1} ;\quad \forall j $

(3)

式 (1) 是模型的目标函数，f₁, f₂, f₃均为越小越优型目标，属于多目标优化问题；式 (2) 和式 (3) 是约束条件，保证每个交换机只隶属于一个控制器。

2 基于模糊满意度的多目标决策

模型中f₁、f₂、f₃没有统一的量纲，且三者之间存在制约，因此应用基于模糊满意度的多目标决策方法^[8]。首先根据隶属度函数求f₁、f₂、f₃的隶属度，进行归一化处理。优化目标是使交换机迁移过程中产生的网络代价整体最小，因此隶属度函数选择递增型函数，隶属度越大，说明产生的网络代价越大。为描述f₁、f₂、f₃之间的制约关系，把各目标函数隶属度的最大值最小化作为优化准则，从而将该多目标问题转化为单目标问题。设f₁、f₂、f₃的隶属度值为u₁、u₂、u₃，目标函数转换为：

$ F = \min [\mathop {\max }\limits_{k = 1,2,3} \,{u_k}] $

(4)

式 (4) 表明，函数隶属度越大，越能获得优化的优先权，即算法的每次迭代过程都为减小最大的网络代价。

f₂、f₃的隶属度函数可用图 2表示的递增连续函数表示。

其数学表达式为：

$ {u_k} = \left\{ {\begin{array}{*{20}{l}} {0,}&{{\kern 1pt} 0 \le {f_k} < f_k^{\min }}\\ {\frac{{{f_k} - f_k^{\min }}}{{f_k^{\max } - f_k^{\min }}},}&{f_k^{\min } \le {f_k} < f_k^{\max }}\\ {1,}&{{f_k} \ge f_k^{\max }} \end{array}} \right. $

定义阈值v、f₁的隶属度函数如图 3所示。

其数学表达式：

$ {u_1} = \left\{ {\begin{array}{*{20}{l}} {0,}&{0 \le {f_1} < v}\\ {{f_1},}&{v \le {f_1} < 1}\\ {1,}&{{f_1} \ge 1} \end{array}} \right. $

隶属度函数分为3部分，分别对应控制器负载的3种状况。当有控制器过载时，u₁=1，目标负载的优化有绝对的优先权，即最低指标要保证无控制器过载；当无控制器过载且目标函数超过阈值时，f₁的隶属度函数变为单调递增，与f₂、f₃竞争优化的优先权；当目标负载低于阈值时，u₁=0，目标负载不再参与竞争，可以认为f₁=v是负载均衡的最高指标。

3 模型求解 3.1 引力搜索算法

万有引力搜索算法 (Gravitation Search Algorithm, GSA) 是Rashedi等^[9]于2009年提出的一种群体智能优化算法，算法来源于自然界中的万有引力现象。设在D维空间中，有n个粒子，根据万有引力公式，第i个粒子X_i=(x_i¹, x_i², …, x_i^d, …, x_i^D) 在第d维上受粒子X_j的作用力为：

$ \boldsymbol{F}_{ij}^d(t) = G(t)\frac{{{\boldsymbol{M}_{pi}}(t) \times {\boldsymbol{M}_{aj}}(t)}}{{{R_{ij}}(t) + \varepsilon }}(x_j^d(t) - x_i^d(t)) $

(5)

其中：M_aj(t) 和M_pi(t) 分别为粒子X_j和粒子X_i的惯性质量；ε是一个很小的常量，防止分母为零；R_ij(t) 是粒子X_j和粒子X_i的欧氏距离；G(t) 是在t时刻的引力常数：

$ G(t) = {G_0}{{\rm{e}}^{ - \alpha \frac{t}{T}}} $

(6)

其中：G₀取值为100，α等于20，T是系统迭代次数。在GSA中，为了增强随机特性，设rand_j是范围在[0, 1]内的随机数，则粒子X_i在第d维受到的合力为：

$ \boldsymbol{F}_i^d(t) = \sum\limits_{j = 1,j \ne i}^n {ran{d_j}} \boldsymbol{F}_{ij}^d(t) $

粒子X_i在第d维的加速度a_i^d(t) 为：

$ \boldsymbol{a}_i^d(t) = \frac{{\boldsymbol{F}_i^d(t)}}{{{\boldsymbol{M}_i}(t)}} $

(7)

其中M_i(t) 是粒子X_i的惯性质量。对于每一次的迭代过程，粒子根据以下公式更新它的速度和位置：

$ \left\{ \begin{array}{l} \mathit{\boldsymbol{v}}_i^d(t + 1) = ran{d_i} \times \mathit{\boldsymbol{v}}_i^d(t) + \mathit{\boldsymbol{a}}_i^d(t)\\ x_i^d(t + 1) = x_i^d(t) + \mathit{\boldsymbol{v}}_i^d(t + 1) \end{array} \right. $

(8)

其中rand_i是[0, 1]内的随机数。惯性质量根据适应度值的大小计算，在GSA中，使用式 (9) 更新粒子的惯性质量：

$ \left\{ \begin{array}{l} {\mathit{\boldsymbol{M}}_{ai}} = {\mathit{\boldsymbol{M}}_{pi}} = {\mathit{\boldsymbol{M}}_{ii}} = {\mathit{\boldsymbol{M}}_i},\,\;\;\\ {m_i}(t) = \frac{{fi{t_i}(t) - worst(t)}}{{best(t) - worst(t)}}\\ {\mathit{\boldsymbol{M}}_i}(t) = \frac{{{m_i}(t)}}{{\sum\limits_{j = 1}^N {{m_j}(t)} }} \end{array} \right.;i = 1,2,..,n $

(9)

其中fit_i(t) 为t时刻粒子X_i的适应度。对于求最小值问题，best(t) 和worst(t) 定义如下：

$ best(t) = \mathop {\min }\limits_{j \in \{ 1,2,...,n\} } fi{t_j}(t) $

$ worst(t) = \mathop {\max }\limits_{j \in \{ 1,2,...,n\} } fi{t_j}(t) $

3.2 群体反向学习机制

引力搜索算法中初始状态随机生成，这导致了算法的寻优效率不够稳定。本文引入群体反向学习机制^[10-11]，优化粒子的初始分布，提高算法效率。

假设x∈[a, b]，则x反向粒子表示为x=a+b-x。粒子X_i=(x_i¹, x_i², …, x_i^D) 的反向粒子为X_i=(x_i¹, x_i², …, x_i^D)。对寻优空间的所有粒子计算其对应的反向粒子，将正向粒子和反向粒子作为整体进行适应度值的排序。选择其中适应度最好的n个粒子作为新的寻优群体。文献[12]的实验结果表明，引力搜索算法中引入反向学习机制可以降低陷入局部最优值的概率、加快收敛。

3.3 算法过程

为适应引力搜索算法，需将交换机分布矩阵转换为映射关系粒子。给M个控制器依次编号1, 2, …, M，映射关系粒子表示为：Y_l=(y_l¹, y_l², …, y_l^j, …, y_l^N)(l=1, 2, …, L)，其中N为交换机的数量，L为搜索空间规模，y_l^j表示对应交换机所属的控制器的编号。映射关系粒子与交换机分布矩阵一一对应。L个映射关系粒子构成映射关系矩阵Y =(y_l^j)_L×N。针对引力搜索算法求解随机性和收敛速度快的特点，实际操作中，减少算法迭代次数，多次求解选取最优值。

算法步骤：

1) 随机初始化映射关系矩阵并应用反向学习原理进行优化，将粒子的速度置零，设定循环次数Iteration；

2) 计算粒子适应度，选出最小的适应度值F_best和对应的映射关系粒子L_best；

3) 更新引力系数G(t)、best(t)、worst(t) 和粒子惯性质量M_i(t)；

4) 计算合力、加速度、速度、更新粒子的位置；

5) 在约束条件下，对映射关系矩阵标准化，用L_best代替负载均衡度较差的粒子；

6) 返回2)，直到达到设定的迭代次数；

7) 算法结束，完成一次求解，记录结果；

8) 重复执行算法h次，从中选取使负载均衡度最优的映射关系粒子作为最终的结果。

4 实验仿真

实验中，采用图 1的拓扑结构，初始映射关系粒子为X₀=(1, 1, 1, 1, 1, 2, 3, 3, 1, 2, 2, 2, 3, 3, 3, 2, 2, 2, 3, 3, 5, 4, 4, 4, 5, 5, 4, 4, 5, 5)，将交换机就近分配给控制器。假设各控制器的容量相等，值设为1；资源利用率阈值按编号顺序依次为0.9, 0.85, 0.85, 0.9, 0.95；交换机瞬时流量随机生成。实验以Matlab R2012a为平台，分两个部分进行。

实验一    验证IGS-SMS的性能，研究v在迁移策略中起到的作用。实验中，控制器平均资源占用率为68.18%。比较v取不同值时，负载均衡度、平均传输时延与交换机迁移数的变化，如图 4~6。

图 4中，v取值在0.6~0.9时，负载均衡度无明显变化，因为目标负载与网络中总负载量和负载分布有关，在控制器平均资源使用率达68.87%时，目标负载容易超过阈值，获得优先权；当v=1时，负载均衡度迅速增大，这是因为v=1表示只要无控制器过载，目标负载就不会成为优化的目标，此时负载均衡度得不到较好的保证。图 5、图 6中，随着v的取值增大，平均传输时延与交换机迁移数整体有下降趋势。因为增大v的取值，目标负载超过阈值的几率降低，优先权集中于平均传输时延与交换机迁移数。可以得出结论：v取值在控制器平均资源使用率到1之间，具体数值应根据交换机请求流量和网络性能需求设定。

从实验一可以看出：v可以有效描述负载均衡、传输时延以及交换机迁移重分配3种代价之间的制约关系；v并不直接决定目标负载权重的相对大小，v值决定的是目标负载在什么样范围内更有竞争力。当目标负载大于v时，竞争力强，可以防止出现单个控制器负载较重的情况；当目标负载小于v时，将优先权转让，兼顾传输时延与交换机重分配的指标。

实验二    比较IGS-SMS、PASMM与DSMA的负载均衡效果。首先采用实验一中交换机请求流量分布，为保证较好的负载均衡效果，IGS-SMS算法中阈值v设为0.7。实验结果如图 7。

计算交换机迁移执行后的负载均衡度：ρ(InitialState)=0.066 2，ρ(PASMM)=0.028 8，ρ(DSMA)=0.044 2，ρ(IGS-SMS)=0.010 4；在该实例中，初始状态，控制器3过载。交换机迁移策略执行后，3种算法均能缓解过载状况。其中，IGS-SMS最优，PASMM和DSMA较差。

然后增大交换机请求流量，再次进行实验，结果如图 8。

此时，控制器平均资源使用率为81.66%，负载集中于控制器2和控制器3。初始状态下，控制器2和控制器3过载。IGS-SMS执行后无控制器过载，而采用PASMM和DSMA没有缓解控制器过载。计算负载均衡度：ρ(InitialState)=0.177 7，ρ(PASMM)=0.315 8，ρ(DSMA)=0.044 6，ρ(IGS-SMS)=0.002 7。可以看出IGS-SMS的负载均衡度最优，DSMA较差，PASMM执行后的负载均衡度相对于初始状态反而有所增大。对于DSMA算法，固定的权值无法反映不同网络的需求，实验采用文献[6]中设定的1:1的权值，在网络局部负载较重时不能突出负载均衡的主要地位。在PASMM中，交换机对控制器的选择受距离影响较大，当网络局部负载较重时，算法收敛速度慢，实验中算法迭代10 000次仍然得不到合格的结果，这就陷入了与就近迁移策略相同的困境。

5 结语

本文提出了一种基于改进引力搜索算法的交换机迁移策略。采用基于模糊满意度的多目标决策方法，权衡负载均衡、传输时延和交换机重分配3个方面的代价，应用改进引力搜索算法进行求解。实验结果表明，提出的交换机迁移策略可以有效缓解控制器过载，实现较好的负载均衡效果。另外，阈值v可以根据负载状况及网络需求自适应选取，避免了人工操作的复杂性；而改进的引力搜索算法降低了算法随机性的影响，提高了求解的可靠性。但本文没有涉及交换机请求流量过大或过小，需要添加或减少控制器的情况，需要在以后的工作中进一步研究。