应急管理场景下的边缘计算卸载策略

赵宏伟，张子祺，尤静月，王阳阳，赵西珂

(沈阳大学 信息工程学院，辽宁 沈阳 110044)

0 引 言

在传统的云计算架构下，全部数据传输到云端，不仅会带来带宽资源浪费和延时等问题[1]，更可能导致任务处理不及时，造成严重后果。针对这些问题，为缓解云服务器的压力，减少主干网络的占用，边缘计算应运而生[2]。边缘计算是一种新型的网络架构，将部分服务器下沉到网络边缘[3]，就近处理计算任务[4]。而随着“数字中国”建设的推进[5]，应急管理现代化建设变得越来越重要。文献[6]提出采用集中控制的方式进行资源调度，在所有节点中选择少量的节点，降低端到端的时间延迟。文献[7]提出了一种优化算法，该算法基于粒子群算法，面向多种资源匹配，用以优化边缘终端设备的能耗问题。文献[8]将FWA算法和模拟退火算法相结合，提高了FWA的全局搜索能力。本文研究应急管理场景下，多计算任务卸载及调度问题，提出了多MEC服务器集群协作计算卸载模型。该模型考虑不同应急监控场所终端设备数量不同，同时不同MEC服务器所具有的计算资源也不尽相同，由此对计算卸载决策与资源分配方案进行设计。当发生突发事件时，该模型能充分利用分布在不同地区的MCE服务器，提高计算数据的处理速度。主要贡献包括：①提出一种多终端多MEC服务器的集群协作计算卸载模型，该模型综合考虑了时延和成本。②提出一种引入凸优化[9]和遗传算法思想[10]的改进的烟花算法(improved firework algorithm based on convex optimization and genetic algorithm，COGA-FWA)，来对模型进行求解，实现对任务的卸载与计算资源的分配。③将改进后的算法与原始算法以及其它群体智能算法进行对照，在不同参数下进行仿真实验，结果表明COGA-FWA在多MEC服务器与多任务规模下都能取得更好的求解质量。

1 网络场景

每个应急监控场所均设置一个或多个监控设备，与本地的MEC服务器相连接，进而通过光纤连入广域网。分散在各个应急监控场所的MEC服务器，不仅再仅仅为本地设备提供计算资源，通过资源分配，还可作为视频监控设备的计算任务卸载目的地，为其它应急健康场所的监控设备分配计算资源。

一般情况下，MEC服务器会将监控设备产生的视频原始数据存储至本地，并以较低的画质传输至应急管理中心，以此缓解带宽压力和节约计算资源。当发生突发事件，需要实时上传高清视频数据时，需要较大的计算资源来对视频进行视频流计算，此时本地的MEC服务器可能出现算力不足的情况，而其它相邻地区MEC服务器存在剩余计算资源。因此，为了提高视频流计算的速度，并充分利用相邻地区MEC服务器上的剩余计算资源，本文考虑多应急场所协作共同完成突发事件下的高清视频流计算任务的网络场景，MEC服务器与相邻地区其它MEC服务器均接入广域网，通过光纤相连，构成服务器集群，服务器集群中的MEC服务器协作完成突发事故点的监控设备视频流计算任务。视频流计算任务发布到本地MEC服务器中后，再以完全卸载的方式被卸载到服务器集群中某个合适的MEC服务器中，每个MEC服务器在完成本地计算任务的同时，可以接受其它MEC服务器的计算请求。

计算任务的卸载过程如图1所示，当“某高校”发生火灾时，将部分视频监控设备的视频流计算任务分配到其它MEC服务器，本地MEC服务器根据各MEC服务器的传输时延和计算资源情况，决定计算任务的卸载方案。

图1 多应急监控场所计算卸载网络场景

2 计算卸载模型

2.1 资源分配模型

在前文设想的网络场景下，既需要解决视频流计算任务的卸载问题，又需要解决卸载后如何分配计算资源的问题。而解决这些问题的关键在于计算任务的处理时长以及在处理计算任务的过程中所产生的费用之间的平衡，处理一项计算任务所需时长越长，所消耗的费用往往越高。因此，综合考虑以上两点，本文提出了一种集群协作计算卸载模型，在对计算任务进行卸载时，根据各MEC服务器计算资源以及其所预期产生的费用来对计算任务进行分配，实现突发事件发生时，在满足任务处理要求的同时，使计算成本达到最小。在此计算卸载模型中，本文假设当有突发事件发生时，应急监控场所的监控设备会在短时间内产生急需解决的计算任务，假设监控设备的集合为

N={1,2,…,n}

(1)

每个设备均对应有一个计算任务需要服务器进行处理，计算任务集合记作

U={U1,U2,…,Un}

(2)

每个计算任务表示为

(3)

其中，i代表第i个计算任务。C、D、Tmax分别代表计算量、数据量以及任务所允许的最大的响应时延，包括传输时延和处理时延。

假设有m台MEC服务器，其集合记作

M={M1,M2,…,Mm}

(4)

(5)

式中：Bx为本地MEC服务器与MEC服务器Mx之间的带宽。

设Rxi为Mx分配给Ui的计算资源，则Ui在Mx上完成任务处理的时间为

(6)

则任务Ui的总时延为

(7)

其它任务也通过本地MEC服务器被卸载到合适的MEC服务器上。

各个服务器在使用过程中，不同的服务器之间性能可能存在差异，性能越高的服务器，单位时间内所产生的费用越高。故当第i个计算任务被分配到第x台服务器上进行计算时所支付的费用为

Pi=θ*Rxi

(8)

式中：θ为MEC服务器的计费系数，使得当任务的计算量Ci不变的情况下，任务处理所支付的费用随计算资源Rxi的变化而变化。

假设MEC服务器集群中m个MEC服务器集群的可分配计算资源集合表示为

R={R1,R2,…,Rm}

(9)

其中MEC服务器Mx上分配了k个视频流处理任务，分别是

UX={UX1,UX2,…,UXk}

(10)

MEC服务器Mx分配给各计算任务的计算资源分别是

{αx1Rx,αx2Rx,…,αxkRx}

(11)

Rx为MEC服务器Mx的可分配计算资源，其中

αxj∈[0,1]，j∈{1,2,…,k}

(12)

为资源分配比例系数

(13)

故而

(14)

设任务Uxi所允许的最大响应时延为

(15)

为了保证第i个任务能在允许的时间内完成计算，任务的处理时延应不超过

(16)

任务所需的最小计算资源

(17)

则MEC服务器Mx分配给第j个计算任务的计算资源应满足

(18)

2.2 卸载优化模型

在计算资源约束下，以最小化所有计算任务总时延成本值为目标，可以得到MEC服务器上资源分配优化目标表达式为

(19)

满足

(20)

(21)

j∈{1,2,…,k},x∈{1,2,…,m}

(22)

其中，γ和δ为权重系数。

式(19)～式(22)所描述的问题为凸优化问题，证明过程如下

minf(x)

(23)

subjectto.

gi(x)≤0,i=1,2,…,m

(24)

hi(x)=0,i=1,2,…,n

(25)

设x为凸集，且该集合闭合，当f(x)是x上的凸函数时，f(x)可用凸优化来求解最小值。

若gi(x)是凸函数，那么可知 {x|gi(x)≤b} 也是一个凸集。

令

(26)

约束函数为

(27)

(28)

gi(α) 均为一元函数，对gi(α) 二次求导得

(29)

又知对于一元函数，对其二次求导，若结果不为负，则该函数为凸函数，故gi(α) 均为凸函数。

定义若一个值函数可以表示为

h0(x1,x2,…,xn)=Α1x1+Α1x2+…+Αnxn+b

(30)

则称h是仿射函数。由定义可知

(31)

为仿射函数。

式(26)的黑塞矩阵为

(32)

因为变量αxj，j∈{1,2,…,k} 独立，因此该矩阵为对角矩阵，计算得

(33)

由此可知该矩阵特征值均为正值。

因为对角矩阵是对称矩阵，而该矩阵特征值均为正值，故该矩阵为正定矩阵。又知对于多元函数，当其黑塞矩阵为正定矩阵时，该函数为凸函数，所以式(26)为凸函数。故式(19)～式(22)所描述的问题为凸优化问题。

令bix为卸载决策变量

bix∈{0,1}

(34)

当bix=1时，表示计算任务i卸载到MEC服务器Mx上执行。

综上所述，问题优化目标表达式为

(35)

3 求解方法

第2章分析了服务器和计算任务之间的关系，综合考虑计算任务的处理时长和花费，构建了计算卸载模型。由该模型可以看出，计算卸载的问题在求解的过程中，首先要制定计算任务的卸载方案，即卸载决策，而卸载决策的制定，又受制于资源分配的方案。因此两个问题互相影响，是耦合的。若单独考虑卸载决策问题，该问题为多项式复杂程度的非确定性问题，在求解多项式复杂程度的非确定性问题时，选择使用群体智能优化算法，具有良好的求解效率。在卸载决策确定以后，便需要考虑如何对计算资源进行分配，由前文所述，在每个独立的服务器上，计算资源的分配问题，均为凸优化问题。

3.1 烟花算法

烟花算法(fireworksalgorithm，FWA)是由Tan和Zhu提出的一种群体智能优化算法，受到烟花爆炸产生火花这一现象的启发而得出[11]。算法的思想简单，但具体实现起来比较复杂。近年来已经有了很多的改进研究和应用。

烟花算法在搜索空间上随机产生N个个体作为初始解记作

S={X1,X2,…,XN}

(36)

每个烟花

Xi={Xi1,Xi2,…,XiD}

(37)

代表一个可能存在的解，烟花的适应度由根据模型中的适应度函数来计算得出，在烟花爆炸后，若爆炸半径小且产生数量较多的火花粒子，便认为适应度较好，应该在该结果附近进行搜索；同理，若半径较大且产生的火花粒子较少，则认为适应度较差，应该扩大搜索范围。半径Ai与数量Bi的求解方式如式(38)、式(39)所示

(38)

(39)

3.2 烟花算法的改进

在原始的烟花算法中，原始烟花粒子的值会在爆炸操作时被丢弃，与此同时，在不断进行烟花个体的挑选后，包含在烟花粒子中的可行解可能会丢失，进而导致无法快速获得全局最优解。针对这一问题，本文使用遗产算法的思想替代原有的策略，以此来提高算法的全局寻优速度，提高求得最优解的速度。改进后的烟花算法流程如图2所示。

图2 改进后的烟花算法流程

可以看出，改进后的烟花算法具体步骤如下：

步骤1 初始化

基于本文的多场所视频监控计算任务卸载及调度问题，首先随机在解空间初始化N个烟花位置并对其进行符号编码，设置染色体长度等于任务数量，以保证每个任务都能被分配到MEC服务器上并且不会被重复分配；之后确定中群内部烟花例子的数目和维度。

如表1所示，该烟花粒子表示有5台MEC服务器执行7项任务。其中1号MEC服务器执行1号、6号任务，2号MEC服务器执行2号任务，3号MEC服务器执行4号任务，4号MEC服务器执行3号任务，5号MEC服务器执行5号、7号任务。

表1 编码方式

步骤2 求适应度

在本次循环所确定的卸载决策下，通过式(26)求解资源分配变量，进而得到系统的总开销，作为此个体的适应度值。以一定概率接受次优解，求解所有个体的适应度值，保留适应度最高的个体到下一代。

步骤3 爆炸

在求解本文中写在决策和资源分配问题时，需要对原始算法进行改进，以适应本文的问题。首先，应针对模型中的解进行适配，经典的烟花算法在求解过程中，产生的解为非负实数，而模型中由于计算任务和服务器均不可再分，因此针对这两项的解应为非负整数；其次，由式(38)、式(39)可知，若适应度比较好，则Ai的值会非常小，而Bi此时取得一个比较大的值。

针对此模型中的问题，当Ai小于1时无法搜索到其它解，并且会因为陷入局部最优，导致服务器的资源被浪费。本文对原计算公式进行了修改，增加了参数θ，令θ=1保证Ai取值大于1，如下式所示

(40)

根据爆炸式(39)、式(40)得到Ai与Bi，并根据得到的值，在该范围内产生Bi数量的子代烟花。

因为存在这种可能：适应度较好的烟花，在爆炸时，产生了过多的火花，而适应度值较差的烟花，在爆炸时产生的烟花过少。为了避免这种情况的发生，需要对于产生的个数进行限制

(41)

在爆炸操作完成后，还需要进行位移操作

(42)

步骤4 产生变异烟花个体

在标准烟花算法中，变异算子爆炸范围比较大，并且对粒子进行变换时会对粒子的整体进行变换，变换后会导致可行解信息丢失，因此算法的搜索速度比较低，搜索精度不高。针对这些问题，在原有的算法基础上，利用遗传算法的思想来增强寻优能力。以一定的概率在所有个体中选择最优个体，然后进行随机位置的变异，如表2所示。

表2 变异操作

步骤5 选择下一代烟花个体

在父代种群、子代种群和变异个体当中选择最优个体进入到下一代，并更新种群最优值。

步骤6 判断是否满足终止条件

退出循环的条件有两个：①若循环次数已达到设定的最大次数，则退出循环。②若在达到设定的最大循环次数之前，已经搜索到最小值以及对应的卸载决策与资源分配方案，则退出循环，否则重复执行步骤2到步骤6。

步骤7 输出最优解。

算法伪代码见表3。

表3 算法伪代码

4 实验与结果分析

4.1 实验环境

软件环境：本文实验所使用的仿真环境为Python，操作系统为64位Windows10，开发工具为PyCharm，使用MATLAB库进行仿真实验。

硬件环境：本文所使用的计算机内置CPU型号为Intel Core i7-8750H，CPU主频为2.2 GHz运行内存为16 GB，硬盘为1 TB。

4.2 对比算法介绍

本小节主要介绍本文所提出的COGA-FWA算法的对比算法，我们选取的对比算法主要有烟花算法(FWA)和人工蜂群算法(ABC)，将COGA-FWA算法与FWA和ABC在收敛速度标准下进行对比，以验证本文所提出的算法的优越性。

烟花算法是一种智能算法，该算法的并行性与鲁棒性较强。但原始算法存在一些缺点，例如在求解资源分配问题时，需要进行分配的资源量较大，该算法的求解速度会降低，并且容易陷入局部最优。

人工蜂群算法也是一种智能优化算法，该算法模仿蜜蜂行为提出，有着较快的收敛速度。但人工蜂群算法在局部搜索能力方面较弱，对于计算资源分配问题处理能力不足。

4.3 实验结果分析

本文利用Python进行仿真实验。采用改进后的算法对模型进行求解，设置人工蜂群算法(ABC)与烟花算法(FWA)作为对照。

4.3.1 收敛过程分析

本次实验设置10台服务器，计算任务数量设置为100个，每个任务的数据量随机设置为1 GB～10 GB。各MEC服务器计算资源随机分配200 GHz/s～500 GHz/s、服务器间带宽随机分配500 Mb/s～1000 Mb/s。分别采用ABC与FWA、COGA-FWA算法对模型进行求解。3种算法所对应的计算结果曲线如图3所示。

图3 3种算法求解结果对比

从图3可以看出，3种算法得到的总时延成本值与迭代次数在一定的取值范围内呈负相关，并随着迭代次数的增加，最终趋于稳定。其中，ABC与FWA求解资源分配问题时使用的是随机搜索的方式，因此，求解效率不高，算法收敛速度较慢，需要较长的时间才能趋于稳定。而COGA-FWA采用凸优化的方式对资源分配问题进行求解，同时又引入了遗传算法的思想，因此在初始几代便能快速收敛，且趋于稳定时的时延成本值比ABC与FWA均有较大提升。

4.3.2 MEC服务器的数量对求解质量的影响

为了探寻服务器数量、用户任务数量与时延成本值之间的关系，分析服务器数量对求解质量的影响，本次实验设置任务数为50个，每个任务的数据量设置为5 GB。各MEC服务器计算资源分配200 GHz/s、服务器间带宽设置为500 Mb/s。改变MEC服务器的数量分别取5、10、15、20、25。在3种求解算法下，不同MEC服务器所对应的总时延成本值如图4所示。

图4 MEC服务器数量对总时延成本值的影响

从图4可以看出，3种算法求解得到的总时延成本值与服务器数量呈负相关，服务器数量即计算资源越多，完成任务所需要的总时延成本值也越少。在不同的服务器数量下进行对比，与ABC、FWA相比，COGA-FWA均得到了更低的总时延成本值。

4.3.3 用户任务数量对总时延成本值的影响

为了验证用户任务数量对总时延成本值的影响，设置MEC服务器数量为10个，每个任务的数据量设置为10 GB。各MEC服务器计算资源分配500 GHz/s、服务器间带宽设置为500 Mb/s。改变用户任务数量分别取5个、10个、25个、50个、100个。在3种求解算法下，不同用户任务数量所对应的总时延成本值如图5所示。

图5 用户任务数量对总时延成本值的影响

从图5可以看出，若只改变用户任务数量的取值，3种算法求解得到的总时延成本值与用户任务数量呈正相关，在不同的用户任务数量下进行对比，COGA-FWA均取得了更低的时延成本值。因此可以推断，采用COGA-FWA的求解方案可以减少时延成本值，得到更优的资源分配方案，进而减少计算资源的浪费。

4.3.4 MEC服务器计算资源对总时延成本值的影响

为了验证MEC服务器计算资源对总时延成本值的影响，设置10台MEC服务器，用户任务数为50个，每个任务的数据量设置为5 GB。服务器间带宽设置为500 Mb/s。改变MEC服务器的计算资源分别取100 GHz/s、200 GHz/s、300 GHz/s、400 GHz/s、500 GHz/s。在3种求解算法下，不同MEC服务器计算资源所对应的总时延成本值如图6所示。

图6 MEC服务器计算资源对总时延成本值的影响

从图6可以看出，在当其它条件确定时，随着MEC服务器计算资源增多，3种算法求解得到的时延成本值逐渐减小。在不同的MEC服务器计算资源条件下，COGA-FWA均取得了更低的时延成本值。采用COGA-FWA的求解方案可以降低系统的总时延成本值，进而还可以减少网络带宽占用。

5 结束语

本文针对应急管理场景下的计算任务卸载及服务器资源分配问题，建立了综合考虑时延和成本的MEC服务器集群协作计算卸载模型，提出了多计算任务的卸载与计算资源分配的优化策略，引入凸优化和遗传算法思想改进了烟花算法。实验结果表明，本文提出的计算卸载模型能加快计算任务的处理速度，降低MEC服务器间的带宽占用，减少资源占用和资源浪费；本文采用改进后的烟花算法对所提问题进行求解，将多个设备上的不同计算任务分配到不同的MEC服务器中执行，提高了MEC服务器计算资源的利用率，能够很好地减少成本和降低时延，提高资源调度效率。COGA-FWA算法和MEC服务器集群协作计算卸载模型对于解决应急管理场景下的资源调度和任务分配问题具有重要意义[12]。