苏建姜 苏 亮
(包头职业技术学院 计算机与信息工程系，内蒙古 包头 014030)
随着大数据时代的到来，网络建设规模变得更加复杂以及网络用户不断增加，传统网络体系结构是以IP为核心的分层体系结构，其弊端逐渐明显，网络设备包含多种协议，相互通信处理数据的速率也不同，不利于网络的管理，尤其在网络中瀑布式流量，出现灵活度差，容易出现资源利用不均衡和网络堵塞的问题。
近年来SDN网络负载均衡的研究也越来越多，刘海客等提出基于一种OpenFlow网络的动态负载均衡方法[1]；
罗晨提出一种基于面向负载均衡的软件定义网络最优路径算法研究[2]；
许红亮等提出一种基于自适应多路径负载均衡算法。[3]上述网络负载研究主要面向服务器，在网络拓扑链路之间负载均衡差别。本文重点研究SDN网络数据传输是链路之间负载均衡问题，提出一种基于SDN的数据传输路径负载均衡策略研究，将每条链路带宽空闲率作为蜂群进化型遗传算法(BEGA)的变异因子，利用SDN控制器可以获得全网拓扑结构来实现基于链路的负载均衡，主要从链路利用率、网络吞吐量和网络时延等方面来改善网络性能，并通过实验仿真验证本方法的有效性和可行性。
1.1 SDN架构
SDN(Software Defined Network)是一种逻辑集中控制的新网络架构，其关键属性包括：数据平面和控制平面分离；
控制平面和数据平面之间有统一的开放接口OpenFlow。一般称控制器开放的API为北向接口，而控制器与底层网络之间的接口为南向接口。SDN网络体系结构主要包括SDN网络应用、北向接口、SDN控制器、南向接口和SDN数据平面五部分[4],如图1所示。
图1 SDN体系架构图
1.2 负载均衡
服务器负载均衡是指直接在服务器和外部网络之间安装负载均衡设备，将处理后负载平均分配到多台服务器上，最大程度增强服务器数据包的处理能力、提高数据传输效率、增强网络稳定性和利用率。[5]服务器端负载均衡框架如图2所示。
图2 服务器负载均衡架构
链路层负载均衡策略是指通过合理调度网络链路策略，如在链路层增加冗余链路来提高链路数据处理传输能力同时可应对单点故障，进而调节网络拓扑中冗余链路带宽资源，达到负载均衡效果，如图3所示。
图3 数据链路负载均衡架构
1.3 SDN与负载均衡技术
在传统网络中为实现负载均衡,需要使专门的软件或硬件设备，存在扩展性较差和费用高等问题。相比于传统网络，基于SDN的网络体系结构为解决网络数据链路负载均衡提供新的解决方法且有三大优势：SDN架构中的控制器通过OpenFlow协议收集全局资源信息；
SDN架构中所有OpenFlow转发设备抽象为一个整体，由控制器统一下发至交换机等转发设备中实现集中化的逻辑控制；
SDN架构中可用软件方式制定负载均衡策略。
2.1 改进蜂群算法
2.1.1 蜂群算法实现
蜂群算法(Bee Colony Algorithm)是以仿生自然界中蜂群的自组织模型和群体智能行为的一种算法。Bitam等，Derelict和Marinali[6-8]根据蜂群的蜜蜂繁殖(reproductive)行为(或过程)与采蜜(foraging)行为启发，蜂群算法主要分为蜂群进化型算法(Bee evolutionary algorithm)与人工蜂群算法(Artificial Bee Colony Algorithm)。
2.1.2 蜜蜂进化机制抽象模型
BCA影响蜂群进化方向的重要因素是引入蜂群最优个体和外来蜂群，基于此提出蜜蜂进化型遗传算法(BEGA)，以给定概率将算法中最优个体(蜂王)与一般个体(雄蜂)进行交叉操作，从而增强对蜂群最优个体信息开采能力，降低陷入局部最优解概率[9]，BEGA实质是对遗传算法的一种改进。
(1)蜜蜂繁殖进化过程简介
蜜蜂的繁殖方式为孤雌生殖。蜜蜂蜂群中有三个阶层：蜂王、工蜂、雄蜂。蜂王一个，为雌蜂，领导蜂群，负责繁衍，蜂王在小蜂房中产的卵将来发育为工蜂，产在大蜂房的受精卵发育成蜂王；
雄蜂，由蜂王产在中蜂房中的未受精的卵发育而来，任务是负责与蜂王交配，任务完成后生命就结束了；
蜂王具体交配过程为：蜂王雄蜂出巢飞舞，最强壮雄蜂与蜂王交配，雄蜂死去，蜂王回巢，蜂王产卵孵化有且仅有一个蜂王。
(2)蜜蜂进化过程的抽象模型
在遗传算法中引入蜜蜂繁殖进化机制，包括最优个体(蜂王)、一般个体(雄蜂)和随机蜂群将提高遗传算法性能，我们得到蜜蜂进化机制在GA中的抽象模型，如图4所示。
图4 蜂群繁殖进化抽象模型
2.1.3 BEGA算法
蜜蜂进化型遗传算法(BEGA)吸取蜜蜂进化机制的优点，同时优化遗传算法的进化结构，蜂王存在可提高遗传算法全局收敛性能，随机蜂群引入避免算法陷入最优解。
(1)自适应交叉率、变异率
基本遗传算法SGA(Simple Genetic Algorithms)是基于自然选择的生物进化，模仿生物进化过程的随机方法，采纳了自然进化模型，其基本操作主要有选择、交叉和变异。传统的简单遗传算法收敛速度慢很难得到全局最优解，且在求解复杂多峰值优化问题容易陷入局部最优解。GA算法中交叉率和变异率产生方法的选择很大程度上会影响遗传算法行为和性能[10]，若交叉率越大，产生新个体的速度就越快，且容易破坏高适应值的个体结构；
但过小，搜索过程缓慢、收敛速度慢。若变异率过小，新个体不易产生；
若越大，遗传算法失去本来算法意义，沦为纯粹的随机搜索算法。
1994年，Srinivas等人提出了一种根据适应度值动态调整交叉概率和变异概率的自适应遗传算法AGA(Adaptive Genetic Algorithm)，和能随个体适应度自适应调整。此Pc和Pm按如下在公式(1)和(2)基础上自适应调整。
(1)
(2)
式中：fmax为种群中最大适应度；
favg为每代种群中的平均适应度；
f′为将要交叉的两个体的较大适应度值；
f为变异个体的适应度值；
Pc1=0.9，Pc2=0.6，Pm1=0.1，Pm2=0.01。
改进后的基本遗传算法除了具有基本遗传算法的特点之外，还有以下新的特点：避免了算法早熟问题，提升全局搜索能力；
避免了锯齿问题，提升局部搜索能力；
遗传算子的进化更具方向性，具有较强的收敛能力。
(2)适应度尺度变换
在遗传算法中用适应度值来衡量个体优劣的程度。本文用到的为适应度线性变换法，假设原适应度为函数f，变换后的适应度函数为f′，则线性变换可用式(3)表示：
f′=α*f+β
(3)
其中α,β为变换系数。
(3)算子设定
① 选择算子
由于BEGA算法中蜂王的存在，其实质作用为“最优个体保留”策略，而我们通常认为为“最优个体保留”策略是导致GA算法“早熟”的原因之一，但从算法全局收敛性角度考虑，“最优个体保留”策略是必要的。在卫星舱布局优化实践中发现，若GA群体规模越小，则“最优个体保留”策略对GA的影响越大(收敛速度快)；
反之越小。适当控制GA种群的规模即可控制GA的早熟又保证算法具有全局收敛性。结合上述，选择策略为锦标赛选择算子，因为随机锦标赛操作简单，具有很强的通用性和鲁棒性。
② 交叉算子
GA算法中常用到的交叉算子有单点交叉、两点交叉、均匀交叉、多点交叉等，针对本文布局设计问题而言两点交叉操作是比较合适的。两点交叉的操作与单点交叉类似，只是随机设置两个交叉点。
考虑如下两个11位变量的个体：
父个体1 01110011001 父个体2 10101100101
交叉点位置为2、6，则产生的个体为：
子个体1 01101111001 子个体2 10110000101
③ 变异算子
在进化过程中，变异算子作用大于选择和交叉算子。进化前期，种群中个体之间差异较大，进化速度较快，此阶段选择和交叉操作的作用明显；
进化后期，种群中个体差异越来越小，选择和交叉操作的作用不明显，变异操作的作用明显，提高变异率可以增加种群的多样性，降低算法陷入局部最优解。本文采用高斯变异，高斯分布在原数值附近随机产生数值，有利于提高布局优化局部寻优和全局搜索能力。具体变异方式如下：设个体的每个基因有均等的变异机会，若某位基因的变异几率小于设定的变异概率，则按式(4)对该基因位进行变异：
(4)
2.1.4 BEGA算法描述
基于BEGA算法SDN网络负载均衡策略的步骤如下：
Step 1 随机生成初始种群A(0)，t=0，分别对参数r、交叉概率和变异概率及最大进化代数、种群规模进行赋值。
Step 2 计算种群A(0)中个体适应度，将最优个体(第0代蜂王)保存到Queen中。
Step 3 如果满足停止准则，算法输出结果并停止运行；
否则，继续。
Step 4 利用选择方式，A(t-1)中自适应选出N*r/2个。随机生成N(1-r)/2个。
Step 5 计算此代交叉概率，Queen分别与Step 4得到的N*r/2个个体进行两点交叉运算，得到子代种群，记为B (t)。
Step 6 计算此代自适应变异概率，对B(t)执行变异操作，得到种群C(t)。
Step 7 计算种群C (t)中个体的适应度，从父代中选出的Nr?0/2个个体执行免疫检测操作，将适应度最大的个体记为Queen_New。
Step 8 如果f(Queen_New) >f(Queen)，Queen = Queen_New，C(t)即为第t代种群A(t)；
否则，用Queen中的个体替代C(t)中的最差个体，得到种群A(t)。转到Step3。
算法的代进化过程如图5所示，蜜蜂进化型遗传算法流程图6。
图5 蜜蜂进化型遗传算法代进化图
图6 蜜蜂进化型遗传算法流程图
3.1 负载均衡仿真环境与方案
本文采用Mininet网络仿真工具和Ryu控制器，在Linux操作系统搭建仿真平台。Mininet仿真器用于模拟网络拓扑，Ryu控制器实现负载均衡算法。
本文采用仿真测试网络拓扑，K=4的Fat-tree拓扑作为数据中心网络结构，包含20台OpenFlow交换机，其中8个边缘层交换机、8个汇聚层交换机和4个核心层交换机，16台主机。该网络中所有链路均为全双工链路，链路带宽设置为1Gbps，流量统计时间间隔为1秒，监控负载时间为5秒，参数r=0.6，两点交叉、自适应交叉概率，高斯变异均值为0、标准差为5，自适应变异概率最大值0.1、最小值0.01，锦标赛选择、联赛规模为2，最大进化代数100、种群规模30进行赋值。网络数据链路流量由iperf工具模拟产生，主机h1-h8向主机h9-h16发送数据流，拓扑如图7所示。
图7 网路拓扑图
根据蜜蜂进化型遗传算法计算出最优负载链路，在SDN中通过Ryu控制器把该链路的动作指令补充到链路相应Openflow流表项中，然后把流表项下发给对应SDN交换机。SDN交换机根据流表项指定动作选择数据路径完成报文数据的转发。基于蜜蜂进化型遗传算法SDN负载均衡的方案如图8所示。
图8 BEGA的SDN负载均衡方案
3.2 仿真结果
本文的目标是数据在网络设备链路间传输时，可根据控制器指令选择链路实现负载均衡，选取评价指标是网路的链路平均利用率和网络吞吐量。
如图9所示，BEGA算法和ECMP算法的网络链路平均利用率在仿真开始阶段0～10s差别较小。但随着时间推移，本文算法依据链路实时信息进行选路，而ECMP算法是随机选路，二者在网络中的各条链路的状态不再一样，因此在利用多路径的链路资源方面，BEGA算法比ECMP算法更加有效，链路的平均利用率也高于ECMP算法。
图9 链路平均利用率对比图
如图10所示，BEGA算法和ECMP算法在0～500Mb/s发包速率之间，网络吞吐量差距不大。随着时间推移，当发包速率大于530Mb/s时，BEGA算法的网络吞吐量逐渐增加到680Mb/s左右，而ECMP算法吞吐量无明显变化，因此，根据链路的实时状态进行选路的新算法能有效提高网络性能。
图10 网络吞吐量对比图
为提高多路径网络拓扑负载均衡分配能力，本文提出一种基于SDN体系结构的蜜蜂进化型遗传算法，Ryu控制器获取网络链路数据实时状态和数据传输信息，针对负载均衡较高的路径，重新选定数据传输路径。本文选用胖树网络拓扑进行实验结果表明，BEGA算法在链路平均利用率和网络吞吐量等方面有一定提高。
猜你喜欢蜂王适应度蜂群改进的自适应复制、交叉和突变遗传算法计算机仿真(2022年8期)2022-09-28权力至上的蜂王第二课堂(课外活动版)(2021年11期)2021-01-18“蜂群”席卷天下小哥白尼(军事科学)(2020年4期)2020-07-25蜂王入群意林·少年版(2019年5期)2019-04-18一种基于改进适应度的多机器人协作策略郑州大学学报（工学版）(2018年2期)2018-04-13迁移蜂群优化算法及其在无功优化中的应用自动化学报(2017年1期)2017-03-11基于空调导风板成型工艺的Kriging模型适应度研究中国塑料(2016年11期)2016-04-16改进gbest引导的人工蜂群算法现代计算机(2016年17期)2016-02-28中蜂王生长周期中国蜂业(2014年6期)2014-01-25蜂王剪翅的弊端中国蜂业(2011年12期)2011-02-10