移动边缘计算环境下基于移动感知的工作流调度算法

魏泽丰，周元元

(1.杭州电子科技大学 计算机学院，浙江 杭州 310018； 2. 合肥师范学院 电子信息系统仿真设计安徽省重点实验室，安徽 合肥 23009)

随着智能移动设备和人工智能技术[1]的高速发展，人脸识别、自然语言处理、虚拟现实、深度学习模型压缩[2]等新兴技术逐渐被布局在移动设备上，这对移动设备的计算能力、内存、电池容量提出了挑战[3-4]。传统方法中，移动用户可以将工作流任务卸载到云端服务器，从而提高服务质量，但是这种方式存在延迟过高、带宽有限、极度中心化等缺点，大幅度降低了用户服务质量(Quality of Service，QoS)。近年来，研究人员对云计算技术进行了优化，提出了移动边缘计算[5](Mobile Edge Computing，MEC)的概念。在MEC环境下，用户将计算密集型应用卸载到基站(evolved Node B，eNB)配置的边缘服务器中，从而降低任务的响应时间，减少本地能源消耗并增强隐私保护。

移动边缘计算也受到学术界的广泛关注。任务调度是移动边缘计算研究中最核心的部分，是向用户提供优质服务的关键。因此，研究人员对移动边缘计算环境下的任务调度问题进行了一系列研究。文献[6]考虑了任务执行者之间的默契程度，并将其定义为协作相容性，提出了一种兼顾协作相容性和任务负载的任务分配算法，提高了整个工作流的执行效率。为了实现最大收益和服务利用率，文献[7]在考虑延迟容忍和延迟约束的前提下，对任务进行优先级排序以优化任务分流，有效降低了服务延迟。文献[8]提出了一种基于凸函数优化的迭代搜索算法，将移动设备电池的剩余容量引入到能耗和等待时间的加权因子中，优化了网络和计算资源的分配，达到减少能耗的目的。文献[9]提出了一种多维博弈算法，避免用户同时集中卸载任务到同一个基站，优化了移动端能耗和任务的排队延时。文献[10]设计了一种针对保密设置、计算分流、网络资源的联合优化卸载方案，避免在任务卸载过程中遭遇恶意窃听，提高了任务的卸载成功率。文献[11]研究了混合边缘云环境下工作流任务的运算符放置问题，提出了一种启发式方法来制定任务执行方案，缩短了应用程序的响应时间。文献[12] 提出了一种基于平均场博弈(Mean Field Game，MFG) 和深度强化学习的负载均衡调度算法，将任务合理分配给每个边缘服务器，降低了平均服务延迟。

然而，移动用户通常具有较高的移动性，如果在任务卸载时忽略用户的移动性，将降低任务的卸载成功率，例如用户卸载任务到边缘服务器之后，离开了eNB的通信范围，这将导致任务卸载失败。因此，捕获用户的移动性并执行有效的任务卸载策略来避免任务失败，并减少任务执行时间，降低移动端能耗已成为主要问题。本文提出了基于移动感知的工作流调度MaWS(Mobility-aware Workflow Scheduling)算法。首先，该算法通过STGAT[13]预测用户的行为轨迹，得到每个时间段内的可卸载eNB；然后，通过遗传算法制定全局卸载策略，避免卸载工作流失败。相比于几种经典调度算法，MaWS能够显著减少工作流的完工时间并降低移动端能耗。

1 模型以及问题描述

1.1 工作流模型

用户执行的工作流W表示为一个有向无环图(Directed Acyclic Graph)，记为W={wi|wi=(T，V)}。其中，T为工作流任务的集合T={ti|ti=(IDti，ODti，W(ti))}， IDti、ODti和W(ti)分别表示ti的输入数据大小、输出数据大小和计算量。V表示工作流任务之间的依赖关系，V= {(ti，tj)| (ti，tj)∈T}，其中ti是tj的前驱任务，tj是ti的后继任务，ti的前驱任务表示为pre(ti)，tj的后继任务表示为succ(tj)。

1.2 网络信号模型

用户在移动过程中移动设备(Mobile Device，MD)与每个eNB之间的蜂窝信号也在不断改变。在本文环境中，假设时间系统是离散的并按等长间隔变化，如图1所示，即τ=0，1，…，每个时间间隔的时长为Tslot。在每个时间段τ内，MD与eNB的蜂窝信号的强度为恒定值R(τ)。

图1 每个时间段的信号状态Figure 1. Signal status for each time period

R(τ)的大小取决于MD与eNB之间的距离以及信噪比，MDi与eNBj的传输信噪比为

(1)

Rn=Blog2(1+fSNR(di，n(τ)))

(2)

1.3 轨迹预测模型

本文采用STGAT[13](Spatial-Temporal Graph Attention network)算法预测用户的未来轨迹。STGAT基于序列到序列(Sequence to Sequence)架构，通过图注意力网络[14](Graph Attention Network，GAT)获取每个时间段τ内行人之间的空间交互信息，并利用额外的长短时记忆网络[15](Long Short Term Memory Network，LSTM)解析轨迹之间的时间相关性，进一步提高轨迹预测的准确率。

(3)

式中，ex和ey表示eNB的位置坐标；maxDis为MD与eNB的最大通信距离。

1.4 任务执行模型

MEC环境下，用户产生的工作流任务可以卸载到eNB或在MD本地执行。如果任务ti在MD执行，则需要从eNB或MD获取任务ti的输入数据。若任务ti的前驱任务pre(ti)在eNB中执行，则先要从eNB中接收输出数据。假设当前时间段为τ=h，此时MD从eNB接收数据的传输时间为

(4)

(5)

式中，D(ti，tj)表示前驱任务tj需要传输给任务ti的数据大小。

MD通过蜂窝网络接收输入数据的同时，产生了接收能耗，表示为式(6)。

(6)

当所有前驱任务的输出数据都传输到MD时，任务ti即可开始在MD执行，所需执行时间如式(7)所示。

(7)

MD在执行任务ti时所消耗的能源如式(8)所示。

(8)

若要将任务卸载到eNB执行，则需要将MD中的数据发送到目标eNB。MD发送数据的传输时间为

(9)

(10)

eNB在接收完数据之后，即可开始执行任务，执行时间为式(11)。

(11)

MD在将任务卸载到eNB执行时将产生传输能耗，表示为式(12)。

(12)

由上述任务执行过程的分析可知，MD的能源消耗主要由发送、接收数据的传输能耗以及MD执行任务的能耗3部分组成。工作流的执行时耗主要由MD接收和发送数据的传输时间、MD本地执行任务的耗时以及任务在eNB的执行耗时4部分组成。

1.5 问题描述

缩短工作流的完工时间和降低移动端能耗，是本文工作流调度的优化目标。为了计算工作流的完工时间，需要计算每个任务的开始时间和结束时间。通常情况下，任务ti的前驱任务可能在eNB或MD执行，那么任务ti的开始时间即为所有前驱任务中的最晚完成时间，即式(13)。

Tstart(ti)=maxtj∈pre(ti){Tend(ti)}

(13)

在计算任务的结束时间时，分两种情况，若任务ti在MD本地执行，则结束时间为任务开始时间、MD接收数据的传输时间和任务在MD的执行时间的总和，即

(14)

同理，若任务ti在eNB执行，则任务ti的结束时间为式(15)。

(15)

(16)

综合式(14)～式(16)，工作流的完工时间和移动端能耗分别如下所示。

(17)

(18)

基于以上分析，本文MEC环境下的工作流调度问题可总结为：在执行工作流任务前，根据预测轨迹计算MD与每个eNB之间的通信状态，根据这些先验信息利用算法得到调度策略Γ，通过该调度策略最小化MD的能耗和工作流的完工时间，如下式所示。

F(Γ)=(energy，makespan)

(19)

s.t. makespan

(20)

dist(u，e)

(21)

2 算法设计

本文提出的MaWS算法基于遗传算法[16]，其执行流程如图2所示。

图2 MaWS算法执行流程图Figure 2. Flow chart of MaWS execution

2.1 编码方案

在进行遗传算法编码时，需要分别考虑工作流任务的执行顺序以及卸载位置。图3表示本文遗传算法的编码示例。集合E={e0，e1，…，en-1}表示任务的执行顺序集合，其中，ei表示工作流中的某个任务，在理论上，ei∈{t0，t1，…，ti，tn-1}。但是任务的排序需要满足先序限制关系，即只有当任务t0的前驱任务全部完成时，t0才能开始执行，因此开始任务tstart和结束任务tend必须分别排在第1位和最后。集合L={L1，L2，…，Ln}用来表示工作流任务卸载位置的集合，li=0表示任务ti在本地执行，li=n(n>0)表示任务卸载到相应eNB执行。

图3 编码方案Figure 3. Coding scheme

2.2 适应度

在评价基因的适应度时，需要同时考虑用户设备的能耗以及工作流的完成时间。如式(22)所示，WE和WT分别表示能耗和完工时间的优化权重。在制定调度策略时，可根据工作流任务对能耗和完工时间的需求，调整这两个优化权重。

fitness(x)=WEenergy+WTmakespan

(22)

2.3 初始化

MaWS算法中，任务执行的排序和位置均采用随机的方式生成。如算法1所示，集合T表示所有工作流任务，集合R用来记录已排序任务，集合S表示当前没有前驱或者其前驱排序完毕的任务。执行算法时，每次都从T中选取符合条件的任务加入到S中(第7～11行)；然后根据STGAT预测的用户轨迹得到每个时间段τ内可以卸载的eNB集合(第12～13行)；之后为S中的任务随机分配卸载的eNB或本地执行(第14～16行)；当T中的任务为空时，基因生成完毕。

算法1 生成初始基因输入:工作流W, 轨迹数据TrajData。输出: 基因G。1. S =Ø; /∗可排序任务集合∗/2. R = {t0}; /∗已排序任务∗/3. T= T -{t0};4. E = {}; /∗基因中任务的执行位置部分∗/5. while T ≠ Ø do6. S= {};7. for each ti in T do8. if pre(ti)∈R or pre(ti).size == 09. S.add(ti);10. end if;11. end for12. Trajτ= TrajData.get(τ); /∗得到时刻τ的轨迹数据∗/13. eNBSet = geteNBSet(Trajτ); /∗得到可卸载基站∗/14. for each task ti in S do15. E(ti) = random{eNBSet, MD};16. End for17. T = T-S;18. R = R + S;19. S = {};20. end while

2.4 选择

MaWS算法中采用轮盘赌算法选择需要进行交叉和变异的两个基因。

2.5 交叉

交叉算子能够通过将两个染色体交换组合，将父染色体的优秀特征遗传给子染色体，并避免局部最优解。MaWS算法中的交叉算子，如算法2所示。两个基因的任务排序集合分别为E1和E2，通过随机数的方式确定基因的交叉区域E12和E21，然后在E12和E21的交叉区域后分别加上集合E1和E2，得到两个新的临时个体(第7～8行)，并删除两个临时个体中的重复任务。此时，E12和E21即为交叉完成后的新个体。新个体的任务排序仍旧满足先序限制关系，不会因为任务的错误排序导致任务死锁。

算法2 基因交叉算法输入:旧基因G1、G2。输出:新基因G′1、G′2。1.Generate a random number r in [0,n-1]2.E12=E21=Ø; 3.for k = 0 to r do4. E12=E12 +e1k; 5. E21=E21 +e2k;6.end for7.E12=E12 + E2;8.E21=E21 + E1;9.remove duplicate tasks in E12, E21;10.L12=L21= Ø;11.for k = 0 to r do 12. L12=L12 + lk1;13. L21=L21 + lk2;14.end for15.for i = 0 to n do 16. if L12(i) not in availableeNB17. L12(i) = random(availableeNB, local);18. end if19. if L21(i) not in availableeNB20. L21(i) = random(availableeNB, local);21. end if22.end for

完成任务执行顺序部分的交叉之后，需要对任务的执行位置部分进行交叉，假设两个基因的执行位置部分分别为L1、L2。首先，根据随机数确定L1和L2的交叉区域，并对基因进行交叉(第11～14行)；然后，需要对任务执行位置进行遍历，判断任务ti能否卸载到对应执行位置上的eNB，如果无法卸载，需要从MD和可卸载eNB集合中随机选出一个位置，这样能够保证卸载的可靠性(第15～22行)。

2.6 变异

MaWS算法中的变异算子，如算法3所示。首先，通过随机数的方式确定变异任务ei，并从任务排序集合E向前遍历，当某个任务eb使得任务ei的全部前驱都在集合{e0，…，eb}内，则停止搜索(第2～4行)。同理，从集合E逆向进行遍历，当某个任务ea使得任务ei的全部后继都在{ea，…，en-1}内，则停止搜索(第5～7行)；然后，可以任意改变集合E′={eb+1，…，ea-1}中任务执行位置，并且保证集合E中任务之间的先序限制关系；最后，将任务ei随机插入一个新的位置(第9行)。

完成基因的任务执行顺序部分变异后，通过随机数的方式确定执行位置部分的变异点，并更改该点对应任务的执行位置。由于基因执行顺序和执行位置的对应关系会随着变异而改变，所以需要对任务执行顺序进行遍历，判断任务ti能否有效卸载(第12～16行)。

算法3 排序变异算法输入:变异前基因G。输出:变异后基因G′。1.Generate a random number r in [0,n-1];2.for i = 0 to n-1 do3. find ebst pre(ti)∈{e0,…,eb};4.end for5.for i = n-1 to 0 do6. find ea st succ(ti)∈{e0,…,eb};7.end for8.Get set E′ ={eb+1,…,ea-1};9.Select the insertion position in set E′;10.Get new set E = {e0,…,eb} + E′+ {eb+1,…,ea-1};11.L(r) = random(availableeNB, local);12.for i = 0 to n do 13. if L(i) not in availableeNB14. L(i) = random(availableeNB, local);15. end if16.end for

3 模拟实验

本节进行了实验评估，并分析了MaWS算法的性能，通过改变调度策略与卸载策略，对MaWS算法与传统算法的完工时间以及移动端能耗进行了比较分析。

3.1 参数设置

本文用户生成的工作流的任务个数范围为4～20，每个任务的工作量服从[1，10]均匀分布(单位为GHz)，每个任务的输入输出数据大小服从[1，10]均匀分布(单位为MB)，每个任务的最大完成时长都为1 s。移动设备的计算能力为2.4 GHz，计算功耗为0.5 W。数据的发送、接收功率分别为0.1 W和0.05 W，边缘服务器的计算能力为5 GHz。移动设备与eNB的通信范围为50 m。路径损耗因子δ=-174 dBm·Hz-1，传输带宽B=10 MHz，路径损耗指数g0=-40 dB。

3.2 数据集

本文使用预处理后的斯坦福大学行人数据集[17]来模拟移动边缘计算环境。该数据集中记录了斯坦福大学校区内行人的运动轨迹，本文选择Bookstore的行人轨迹数据作为STGAT的训练集，鸟瞰图和轨迹预测结果如图4所示。

(a)

(b)图4 鸟瞰图及轨迹预测结果图 (a)Bookstore鸟瞰图 (b)轨迹预测结果图Figure 4. Bird′s-eye view and trajectory prediction results (a)Bird′s-eye view of bookstore (b)Trajectory prediction results

3.3 对比实验

本节通过改变调度策略与卸载策略，比较了MaWS与传统算法的完工时间和能耗，验证了MaWS算法的优化效果。

不同调度策略下，工作流完工时间、移动端能耗与工作流任务数的关系如图5和图6所示。通过对比可以观察到，相比GA算法和HEFT算法，MaWS算法能够减少10%～15%的工作流完工时间以及8%～13%的移动端能耗。当工作流任务数量小于8时，MaWS算法与GA算法的优化效果相近。这是因为当任务数量较小时，工作流的整体执行时间较短，即使不考虑用户未来与基站的通信情况，对最终结果的影响也不大。当工作流任务数量大于8时，MaWS算法优势开始体现。这是因为随着任务数量的增加，会导致任务所需执行时间增加。用户由于移动与基站断开连接，使得任务卸载失败，因此需要重新传输数据，导致GA算法制定的调度方案从近似最优解退化到不可行解。当工作流变得更加复杂时，这一劣势将更加明显。而MaWS算法在制定卸载策略时考虑了用户的移动轨迹，得出用户未来与基站的通信情况，最大程度避免了通信中断导致的任务卸载失败。

图7和图8给出了不同卸载位置情况下，工作流完工时间、移动端能耗与工作流任务数的关系。由结果可知，MaWS算法的优化效果明显优于其他算法。Greedy算法只考虑将任务卸载到与用户设备传输收益最大的eNB，但由于用户具有移动性，可能会导致设备在卸载任务的过程中与eNB失联，从而导致任务重传，增加了设备能耗并延长了完工时间。Random算法由于具有随机性，最终的效果也不稳定。MaWS算法通过STGAT预测的用户轨迹制定最优卸载策略，相比于其他算法可以有效地减少工作流执行时间并降低移动端能耗。

图5 不同调度策略下的工作流耗时Figure 5. Workflow time-consuming under different scheduling strategies

图6 不同调度策略下的设备能耗Figure 6. Equipment energy consumption under different scheduling strategies

图7 不同卸载位置下的工作流耗时Figure 7. Workflow time-consuming in different offloading positions

图8 不同卸载位置下的设备能耗Figure 8. Equipment energy consumption under different offloading positions

4 结束语

本文对移动边缘环境下的工作流调度问题进行研究，针对其中存在的工作流时间较长和能耗较高的问题，提出了基于移动感知的工作流调度算法，即MaWS。该算法根据预测用户未来轨迹得出用户未来与eNB的通信状态，并将这些信息融入遗传算法，制定合理的任务执行顺序以及位置。本文通过仿真实验将MaWS算法与传统调度算法进行对比，实验表明本文提出的MaWS算法能够有效地降低移动端能耗并减少工作流完工时间。未来将在算法中引入 D2D 卸载的调度方案，并对容错、调度优化等问题进行探索。