面向边缘计算的改进混沌蝙蝠群协同调度算法

简琤峰,陈家炜,张美玉

(浙江工业大学 计算机学院数字媒体技术研究所,杭州 310023)

1 引 言

边缘计算作为一种新兴的计算模型,可以将具有有限计算资源和能量的物联网(IoT)设备的延迟敏感计算任务卸载到边缘云[1].在云环境下为多功能需求任务选取服务组合问题本质上是一个多目标优化问题[2,3],云计算系统中,由于计算资源的复杂性和不确定性[4],在资源管理与调度方面,边缘计算中的资源优化调度是核心问题之一,只有实现了资源的科学管理、合理调度与分配,才能面向实际需求,充分发挥出云、边缘服务器、终端的节点优势,实现利用率、能耗、带宽、存储等全方面优化[5],终端可以使用面向服务的方式调用云服务来异步完成资源密集,用于集中处理的任务.在本文中,我们研究了任务调度问题,以降低边缘计算系统的成本,我们将任务调度模型建模为优化问题,其目标在满足所有任务的延迟要求的同时最小化运行时间.

此外,硬件的日益增加已经允许这些微小设备执行的不仅仅是感测,例如将自己表示为服务(即设备作为服务).这样的演变中云在整个基础设施中起着核心作用,用于数据处理,存储和分析[6].但是,云计算模式面临着提供低延迟,高可用性和实时位置感知服务的挑战[7],而边缘计算在网络边缘处理大量临时数据，不再全部上传云端，这极大地减轻了网络带宽和数据中心功耗的压力[8].

集中式基础架构系统从我们当前高度虚拟化的无线网络平台和物联网(IoT)应用程序中执行现有的数据分析和决策流程.这些现有方法很可能会遇到与网络动态相关的更多挑战和问题,导致网络响应时间的高开销,从而导致延迟和流量[9].Hesham等人为了避免网络中的这些问题并实现最佳资源利用水平,提出了一种称为边缘计算(EC)的新范例,文中提到了提供升级和高效的服务,基于物联网应用的需求,需要结合适当的计算技术.

本文提出一种面向边缘计算的改进混沌蝙蝠群协同调度算法来进行边缘计算资源调度问题的优化,能够快速搜索到较优的调度解,减少任务完成时间(使用计算任务的平均完成时间来衡量云性能,完成时间越短,边缘云在单位时间内可以承担大量工作量,表明边缘云提供了更强大的计算能力).

2 相关工作

在云调度问题中,已有的策略有如下几种:

随机选择(RS)和轮询(RR)云调度将作业分配给虚拟机而不考虑虚拟机的当前负载[10-12].与其他调度算法相比,具有较小的调度开销,思路简单.但是其可能导致负载不均衡、资源利用率低、提交作业等待时间较长;RR即便每个虚拟机被分配到的任务数量相等,但是任务长度的不均同样会导致上述RS的问题.

此外,传统进化算法应用于调度问题有很好的效果[13],比如:

粒子群算法(PSO),包括带有自适应学习因子的粒子群(TDDALFPSO),量子粒子群(QPSO)等变体的粒子群算法的生物启发技术和群体智能能用于复杂问题的解决,以精度高、收敛快等优点获得了在云调度方面的广泛运用[14,15],此外粒子群算法还有其他很多变种,PSO具有快速收敛的优点,但是同时也存在容易陷入局部最优的问题.从基本概念入手,针对粒子群算法易陷入局部最优、收敛速度慢的缺陷,在算法中加入改进的惯性权重、学习因子和外部扰动因子等是一些常采用的方法.尽管PSO已广泛应用于科学和工程领域,但其稳健性,即其处理具有不同特征的问题的能力仍然不令人满意,因此,需要有更好的搜索能力和鲁棒性的改进PSO以有效地解决该问题[16],在这基础上[17]提出了量子粒子群(QPSO),在QPSO中,粒子行为遵循量子力学原理而不是PSO中强加的牛顿力学,QPSO使用了量子粒子代替牛顿粒子进行随机游走,在本地和全局搜索之间实现良好平衡,其中量子粒子群中的收缩扩张系数是唯一控制参数,用于调整算法,本文内使用的QPSO算法使用了[18]取的参数值.

蝙蝠群算法(BA)和改进的蝙蝠群算法(NBA)则在群组智能算法的基础上进行了改进,从生物学的角度改进算法,模拟蝙蝠的行为,通过模拟蝙蝠的回声,通过设定响度和发声频率属性模拟蝙蝠行为,同时NBA中更是加入了栖息地选择和多普勒效应均衡器的自适应补偿纳入了基本BA算法,提高了效率和稳定性,并提出了自适应局部搜索策略[19].文章[19]中,专注于进一步模仿蝙蝠的行为,并基于生物基础改善BA,设计了新的局部搜索策略,基于二十个基准问题和四个实际工程设计的模拟和比较证明NBA的有效性,效率和稳定性,清楚的表明了NBA对基本BA和一些众所周知的算法的优越性.在该算法中,个体模拟能够自适应地补偿回波中多普勒效应的蝙蝠.根据特定个体与全局最佳个体之间的相对距离,频率方程是自适应的.对于本地搜索,位置更新公式是自适应的,没有任何用户定义的参数.其次,该算法具有良好的分集和收敛性能.结合了蝙蝠的栖息地选择,该算法中的个体可以使用两种不同的搜索策略进化,从而增加个体的多样性.

混沌具有以下特征:对初始条件的敏感依赖性;存在众多不稳定的周期点;准随机性;普遍性等.这些属性使得混沌搜索算法成为有效的优化方法[20].混沌研究的是非线性动力系统的固有特性,是非线性系统普遍存在的现象,线性系统是非线性系统简化而来的,其行为表现为不定性——不可重复、不可预测,这就是混沌现象,应用于群组算法优化中,可以避免出现两次相同的调度情况,相比于其余的去局部最优的方法有更好的效果.

本文提出了一种改进混沌蝙蝠群算法(TDDCBA),加入了混沌因子和二维扰动因子,相比较上述算法有更强的寻优能力.

同时,关于云中心管理和边缘协同管理调度问题[21]由于对提高非通用设备的利用率以及降低成本来实现计算目标的高度兴趣,提出了一种用于在边缘异构云边环境中调度微服务的新模型,通过CloudSim仿真框架进行系统实验,实验发现在其使用面向微服务的方法时,一些非常简单的调度算法可能在云边缘环境中经常出现的特定情况下优于其他一些调度算法.其架构定义了云部署管理器,可确保部署在给定资源上执行任务,这个模块还处理云代理和作业执行单元之间的通信,其模拟架构为每台虚拟机代表某组微服务的能力,这些虚拟机由云管理器管理,被自动扩展模块的请求部署或销毁.

3 提出的调度算法

3.1 调度模型建立

为了达到满足用户QoE的前提下最好地将任务分配给边缘节点的目标,本文使用的边缘计算资源协同调度模型,大体可以描述如图1所示.

图1 边缘计算资源协同调度模型(三层)Fig.1 Edge computing resource collaborative scheduling model(three tier)

在将提交的任务进行分割后,提交到边缘设备,通过调度算法将分割后的任务通过边缘计算代理(ECA)调度放到边缘服务器上,服务器上的虚拟机代表用户进行处理卸载任务的工作.同时,中心云可以进行边缘服务器之间的调度,将超出边缘服务器的资源的任务调度给其他边缘服务器进行处理,对于超出虚拟机间带宽量的任务通过提交到云端来进行调度提速,从而达到云计算与边缘计算协同调度的效果.

计算卸载是一种技术,其中资源受限移动设备完全或部分地将计算密集型任务卸载到资源充足的云环境.计算卸载主要执行能量,电池寿命或由于终端设备无法处理计算量大的应用程序[22].

层次结构的第一层服务器通过无线链路直接从边缘设备接收工作任务进行调度.而边缘服务器收到的设备工作任务负载超过其计算容量那么过多的工作负载将进一步卸载到更高层的服务器,通过这种方式来提供服务大量的峰值负载[23].同时[1]文内已经证明在该调度模型可以被证明为一个无法在多项式时间内解决的NP难问题,而本文也将面向边缘计算的协同调度问题简化成了:在边缘服务资源有限的情况下,确定调度边缘服务执行请求的分配,从而让服务请求整体时间最少,提出一种调度优化算法优化调度过程获得最优解决方案.

在[1]文内第一阶段处理后,我们得到了初步的任务调度策略,但是在一些特殊情况下,可以进一步降低初步调度策略的系统成本,举例说明:考虑有两个任务T1,T2和两个边缘服务器S1,S2,资源需求矢量分别为(10,10,10)和(20,20,20),边缘服务器的可用资源向量分别是(15,15,15)和(50,50,50),根据第一阶段的调度,任务T1将会被调度到服务器S1,任务T2分配到S2,这种情况下,总成本是两个成本的总和,但是如果所有任务都放到S2服务器上进行,则总成本仅为服务器S2的成本.因此,在第一个阶段后,我们需要进一步优化调度策略以减少不必要的成本和运行时间,因此本实验将负载均衡也作为评判指标之一.

边缘计算调度问题可以简化为将m个任务分配到n个服务器上进行运算的问题,其中任务划分后的子任务长度描述为:T={t1,t2,t3,…,tm},其中ti表示第i个子任务总长度.同时假设有n个不均匀的边缘服务器(计算能力不同),边缘服务器上的虚拟机可以描述为:VM={vm1,vm2,vm3,…,vmn},其中vmj表示 第j个服务器(虚拟机)的计算能力.

VM间带宽描述为矩阵

(1)

其中vcij代表vmi和vmj之间的通信带宽,当i=j时vcij为0.

定义第p种调度方案的负载均衡度评价函数LBp为:

(2)

其中

(3)

Pij代表第i个任务是否分配给第j个服务器(虚拟机),如果分配就是1,否则为0.

具有以下约束:

(4)

定义第p种调度方案的运行时间评价函数RTp为:

(5)

由于每个服务器上的资源是优先的,调度约束条件需要满足(每个服务器中需要有重组的内存空间来存储处理的任务,否则就会丢失任务数据,任务带宽和也不能超过服务器总带宽):

(6)

(7)

其中,si为第i个任务的内存需求,bij为任务i分配给服务器j的带宽需求,Sj为服务器j的可用内存,Bj为服务器j和ECA之间的通信带宽.

3.2 云调度的蝙蝠群算法

蝙蝠群算法的思想来自于蝙蝠的回声定位,应用于调度方面的该算法的具体步骤如下:

Step 1.初始化信息,一个蝙蝠代表一个解决方案,一个蝙蝠具有位置信息xij和速度信息vij,其中i代表种群数量,j代表第j个任务.xij的值为小于服务器虚拟机编号(所有服务器的数量)的整数.位置更新公式如下:

xij=xmin+(xmax-xmin)×λ

(8)

其中xmax和xmin代表虚拟机编号的最大最小值,λ为0到1之间的均匀分布的随机数.

Step 2.生成新的解决方案,公式如下:

fi=fmin+(fmax-fmin)×β

(9)

(10)

(11)

其中β为0到1之间的服从均匀分布的随机数.fmin和fmax分别为频率的最大和最小,t代表迭代次数,gbest代表全局最优调度方案.

(12)

其中rand(-1,1)为-1到1之间的服从均匀分布的随机数,Ameant则是第t次迭代的平均响度.

Step 3.随机更新响度和脉冲发射率,生成一个服从均匀分布的随机数,若其小于响度Ai,且按照(9)生成的新的频率fnew小于之前的频率fi,则进行下列更新:

fi=fnew

(13)

(14)

(15)

其中α和γ在本文实验中均按照文献[8]取0.9.

Step 4.更新全局最优解gbest

3.3 二维扰动

BA的位置更新公式和PSO一致,为了进行波动调整,避免减小陷入局部最优的问题,对于(11)进行改进,加入二维扰动.同时为了避免振荡幅度过大导致偏离原来的位置,将振幅限制在20%之内,加入二维扰动后的位置更新公式如下:

(16)

其中ω和σ均为-1到1之间的服从均匀分布的随机数.

3.4 混沌理论

混沌变量在种群运动过程中起到控制粒子混沌程度的作用[24],本文拟通过混沌因子将系统从有序变为无序,从而更好地达到全局个体随机出现效果.初始化混沌变量为:

(17)

其中rid为0到1之间服从均匀分布的常数.

(18)

(19)

其中ψ和Mi分别表示为:搜索测度和搜索空间向负方向移动的比例,在本文的模型中两者的值分别为服务器数量n和0.

3.5 改进混沌蝙蝠群算法描述

本文的算法在BA算法的基础上加入了二维扰动因子和混沌因子,对于跳出局部最优和全局搜索能力进行了优化,具体步骤如下:

1)初始化参数:设置种群(速度初始化为0,位置全局随机初始化为小于虚拟机数量的正整数),迭代次数,设置任务长度和虚拟机的计算能力和混沌变量的各项参数,在本文的模型中搜索测度和搜索空间向负方向移动的比例分别取n和0.

2)根据初始化参数进行中间参数初始化:全局最优值gbest,即为初始化种群中适应度函数最小的值,响度A为[0,2]服从均匀分布的随机数,平均响度Amean的初始化,脉冲发射率ri和混沌因子中间变量rid均初始化为[0,1]服从均匀分布的随机数,初始化混沌变量C.

3)当前迭代次数iter小于规定的最大迭代次数gmax时循环执行Step 4和Step 5,循环结束后的gmax即为最终获得的值.

使用Secp256k1生成256位公钥/密钥，然后编译成64位长度的十六进制字符串；采用公钥的Keccak-256哈希算法，得到一个32字节的字十六进制字符串，接下来对该字符串进行取截，取字符串的最后20个字节（即删除前12个字节），得到了40个字节的字符串，在签名加上0x前缀，就可以得到一个42个字节长的地址，该地址就是以太坊用户全网唯一的账号。

4)根据公式(17)更新混沌变量C,公式(9)和公式(13)更新fi,公式(10)更新速度v,根据公式(12)、(16)、(17)、(18)、(19)更新蝙蝠所在位置,同时进行边界判断(速度值不超过n,位置值也不超过n,超过部分按照边界值取),这里速度值和位置值保留小数值不进行取整,但是进行适应度函数取值的时候进行四舍五入取整后计算适应度值,同时迭代次数iter加一.

5)根据公式(14)和公式(15)更新全局最优值,更新响度A,平均响度Amean和频率r.

算法中的各项参数设置见表1.

表1 算法中各项参数的值
Table 1 Value(v)of each parameter(p)in the algorithm

pvα0.9γ0.9fmin0fmax2A[0,2]r[0,1]pvω[-1,1]σ[-1,1]ψnMi0λ[0,1]β[0,1]pvri[0,1]

算法伪代码如下:

Input:gmax:the number of iteration

pop:random scheduling schemes(a swarm of bats)

cloudletlist:set of tasks to be scheduled

variables of TDDCBA

Initialize gbest

Initialize A Amean r riC

While(iter

update C(17)

update fi(9)

update v(8)

update position(12 16 17 18 19)

judge the border

update gbest

update A,Amean,r(14 15)

iter++

end while

find best in pop

4 实验仿真

4.1 算法性能对比

为了验证本文提出的改进混沌蝙蝠群协同算法在边缘计算资源协同调度模型中的有效性,本文挑选出效果较好的几种算法与本文算法进行比较,并使用CloudSim仿真平台[25]进行实验.通过比较不同的调度算法调度结果的执行时间和负载均衡度来比较算法的效果.

表2 算法对比情况
Table 2 Algorithm comparison

TDDCBABAnmTQTQ301014.509.3425.7712.9501022.4422.0942.0222.541001041.6165.7654.5565.4530010131.13365.16161.15364.8050010223.83793.20253.07793.01100010469.852260.24530.392259.62302010.093.2220.324.38502015.676.9833.637.911002028.1420.4985.3721.583002075.36124.00100.08123.750020127.91273.57187.99273.18100020255.29789.25293.53788.7230308.882.3029.9210.27503012.913.9152.0010.781003022.5510.1045.8011.623003055.1764.75149.7164.735003088.77145.31127.46145.04100030174.73424.34205.63424.03

在表2中,T为运行时间(ms),Q为负载均衡度(1),n代表任务数,m为服务器数(虚拟机数).

图2 虚拟机组的计算能力(MIPS)Fig.2 Computation power of VMs

实验运行环境为Windows10 64位操作系统,Intel Core i5-7500CPU,8GB内存.

为了描述更方便,下面将本实验中服务器上的虚拟机计算能力以图表方式列出来:10个服务器为一个组,后面的20、30是前10个服务器计算能力的复制.配置除了计算能力MIPS,即每秒可以执行多少百万的指令数量不同,其余数据都相同.本文使用虚拟机的MIPS具体数据设置见图2.

其中任务长度为初始化为500-10000的随机整数常数.几种算法的运行找到的最佳调度方案的运行时间和对应的负载均衡比较如下:(为了除去偶然性影响因素以及更好地观测全局效果,实验取10次的平均值,群组的迭代次数固定20次).

Cloudsim服务器主机参数设置为:10个服务器(虚拟机)的时候ram=8192,bw=10000,20个服务器(虚拟机)的时候ram=16384,bw=20000,30个服务器(虚拟机)的时候ram=24576,bw=30000.(ran即为内存,bw即为带宽)

表3 算法对比情况
Table 3 Algorithm comparison

QPSOGAnmTQTQ301018.739.1525.918.97501025.0021.6931.75123.851001044.4765.6254.1265.1630010131.34365.12139.23364.7850010231.43793.11233.09792.92100010476.752259.74471.252259.72302010.733.3020.583.80502016.647.0025.606.871002027.8320.6335.6820.323002076.02123.7879.17123.7250020128.63273.48131.82273.48100020258.26789.00262.79788.9930309.662.1716.262.65503014.693.7320.523.861003022.3810.4428.3910.113003055.44122.5660.8764.545003090.02145.2299.94145.00100030180.97424.14181.88424.91

从表2和表3可以看出,TDDCBA对于不同任务数和不同服务器数的边缘计算任务调度所产生的时间开销和负载均衡度绝大多数情况下均小于QPSO,GA和BA算法.在本文中,还加入了服务器之间的带宽因素,所以TDDCBA算法所要求解的问题复杂度更高.其他三种算法在较小的迭代次数和较小的种群数量情况下,对比寻优效率普遍小于TDDCBA,容易陷入局部最优状态,而加入了二维扰动因子和混沌因子的TDDCBA算法可以更好地跳出局部最优,实现在较少的迭代次数和较小的种群数量情况下获得更优解的效果.而表2和表3为了消除偶然性,取的是10次实验的平均值,较小的误差和个别的相较于TDDCBA更短的时间开销值不能较直观显示QPSO和TDDCBA算法之间的差别,接下来对于多次运行结果的数据进行对比,比较算法的稳定性.由于种群初始化是随机生成的,所以算法每次运行的时候初始种群数据都会不一样,所以这就要求算法需要有一定的稳定性,对于不同的初始化情况都有较好的收敛性.

4.2 算法稳定性对比

算法变化趋势对比图3所示.(为了查看全局效果运行10次):

图3中使用虚拟机数量为10,任务数量为30,迭代次数均设置为20,对比各算法多次运行结果,可以看到TDDCBA算法的稳定性较好,并且具有较强的寻优能力,与其对比的算法中GA寻优能力不够好,QPSO和BA算法变化起伏较大.

为了对比算法效率,再次减少种群迭代次数,迭代次数为10的结果见图4(任务数量为300,虚拟机数量为10,ram=8192,bw=10000为了查看全局效果运行21次).

图3 算法迭代趋势变化Fig.3 Algorithm iteration trend

图4 算法迭代趋势变化Fig.4 Algorithm iteration trend

从图4中能看出,TDDCBA算法在较小的群组迭代次数下同样有较好的效果,而在这方面,GA和BA算法明显较弱,而QPSO的波动范围较大,不能很好地稳定在一定的范围内,相比较于TDDCBA具有较差的稳定性.

同时对于服务器之间的负载均衡为主判断标准的实验效果如下,同样为了消除偶然性取10次结果平均值.

表4 算法对比情况
Table 4 Algorithm comparison

TDDCBABAnmQTQT30108.1737.8619.9270.9430010363.60219.63615.76736.51

表5 算法对比情况
Table 5 Algorithm comparison

QPSOGAnmQTQT30109.4231.558.9037.7330010363.66273.80363.84215.36

根据表4和表5可以看到,BA相比于TDDCBA效果非常差,而与GA相比,TDDCBA对于主要适应度函数具有较好的寻优效果,但是存在偶然性GA效果相比较于TDDCBA运行时间更短,在多目标优化的情况下TDDCBA算法与GA相比一定情况下存在一定的缺陷.与QPSO相比,在任务数量只有30的时候,由于虚拟机的MISP不相等和误差的存在,TDDCBA虽然负载均衡度高,但是某些情况下运行时间不是最佳.然而任务数量到了300后,时间上的优势被扩大,TDDCBA算法的优势被体现了出来.

4.3 算法负载均衡度对比

图5是对于30个任务分配给10台虚拟机的预测调度方案的负载均衡的效果比较.

图5 多次调度方案负载均衡度比较Fig.5 Comparison of load balancing degree of multiple scheduling schemes

可以看到当负载均衡度作为主要评判标准的时候,TDDCBA具有很好的稳定性,这是因为二维扰动因子和混沌因子具有较好的全局搜索能力,能够在迭代次数和种群数量限制下快速收敛从而能有效防止粒子早熟,所以多次实验结果适应度值基本不变.

综上TDDCBA在BA算法的基础上改进有很好的效果,同时对比其他效果较好的算法也能在较少的迭代次数下拥有更好的效果,应用到云计算和边缘计算的协同调度模型中能有效减少边缘服务器调度时间.

5 总结展望

本文针对边缘计算服务器之间通过云平台调度策略和调度速度深入分析当前较先进的调度算法,降低由于调度不均衡导致的速度长、负载不均问题,主要进行了以下改进:对于现有效果较好算法进行改进,使寻优能力增强,陷入局部最优概率大幅度降低,实验结果详细分析了在CloudSim云仿真平台上的仿真结果,接下来可以进行算法的更优值寻找改进,同时将算法应用到多目标优化中,实验证明混沌特性比量子具有较好的摆脱局部优势的能力,并且能够在较少的迭代次数下找到较优的解,同时一定程度的二维扰动对于跳出局部最优具有很好的效果.