Stochastic and Preemptive Task Offloading for Edge-cloud Computing
-
摘要: 边缘云计算系统被广泛用于支持各种计算服务。针对边缘云计算环境中的任务卸载调度问题, 考虑边缘云系统下的动态性和抢占式任务卸载调度，提出一个基于贪婪模拟退火启发式算法的在线卸载框架(SAOF)，根据任务所需的传输延迟以及计算时间，进行周期性的卸载和调度计算，考虑独立任务的随机到达性和资源的异构性，动态地将新到达的任务分配到合适的目的地(边缘服务器或云服务器)，并根据每个任务的延迟敏感性，抢占式地为其分配计算资源，使所有任务的总加权响应时间最小化。最后，在多组参数组合下生成测试实例并进行性能评估实验，将SAOF算法与3种优秀的卸载调度优化算法(Selfish算法、Nearest算法和OnDisc算法)进行对比，实验结果表明，SAOF算法能更有效降低所有任务的总加权响应时间。Abstract: The edge-cloud computing systems are widely used to support various computation services. Aiming at the problem of task offloading and scheduling in edge-cloud computing environments, a stochastic task offloading problem in the edge-cloud computing system is considered. A greedy simulated annealing heuristic algorithm based online offloading framework(SAOF)is proposed for the problem under study, which periodically schedules and offloads tasks according to the required transmission delays and computation times. In consideration of the stochastic arrival of independent tasks and the heterogeneity of resources, SAOF assigns tasks to the appropriate destination (edge servers or cloud servers) dynamically and allocates computing resources to each task preemptively according to its latency-sensitivity. The goal is to minimize the sum of weighted response times of all the tasks. Testing instances are generated under the combination of various parameter settings for evaluation experiments. SAOF is compared with three excellent scheduling optimization algorithms(Selfish algorithm, Nearest algorithm and OnDisc algorithm). Experimental results indicate that SAOF can more effectively reduce the total weighted response time of all tasks.
-
近些年来，云计算得到了迅速发展和广泛应用，云计算平台拥有很好的可扩展性和无限制的计算资源，它可以提供高度可靠和可用的服务。然而，由于在地理上呈现分布式布置的各种数据采集设备所产生的数据量快速增长，庞大的数据量在远程云数据中心进行处理和分析是不现实的，远程云通常距离终端用户很远，移动设备可能会面临很大的通信延迟。尽管计算密集型应用可以通过云资源得到极大的支持，但在大多数情况下，长时间的延迟是难以接受的，尤其是对于延迟敏感型和数据密集型的应用。面对低延迟和高性能的矛盾，边缘云计算作为一种新的计算模式应运而生。在边缘计算系统中，一些智能而价格低廉的边缘服务器被配置在网络边缘，通过将任务从移动终端卸载到边缘服务器或云服务器，服务效率可以得到很好的提升。在边缘云计算中，如何有效地安排和调度任务到具有多种约束限制的服务器是非常重要的，有效的任务调度算法可以将任务卸载到合适的目的地，同时充分考虑到所需的传输延迟和计算时间。AWS IoT Greengrass[1]、Google Cloud IoT Edge[2]和Azure IoT Edge[3]等著名的边缘云项目，通过卸载数据处理和机器学习服务到数十亿的边缘设备来增强其云平台能力，从而对大量传感器收集到的数据进行实时处理。
在云计算系统中，大规模的移动用户可以将计算密集型任务提交给具有丰富计算资源的远程云平台，因此在云平台上实施有效的任务调度是至关重要的，这一问题已经得到了广泛研究。XIONG等[4]建立了一个云数据中心两阶段任务调度的数学模型，提出基于Johnson规则的遗传算法，该算法考虑到了云数据中心多处理器调度的特点；SAHOO等[5]研究了最小化能量消耗和完工时间任务调度问题，提出自动学习(LA)调度框架和基于LA的调度算法，该算法利用了任务和虚拟机的异质性，同时确保任务的截止日期要求。这些研究中的任务大多是计算密集型的，即传输时间可忽略。但是，由于用户和远程数据中心之间有很长的距离，这些适用于计算密集型任务的算法可能不适用于对数据密集型任务的调度，因为长时间的传输延迟可能会大大降低调度方案的有效性。
边缘云计算技术的出现是对上述限制的一种解决方案。通过在网络边缘并且靠近移动用户的位置部署一些能力有限的服务器，可以在满足用户需求的同时，大大减少传输延迟[6]。近些年来，已经有许多关于边缘云计算系统所带来的关键技术研究。JONATHAN等[7]开发了名为Nebula的分散边缘云基础设施，该基础设施将自愿资源用于计算和数据存储，并具有轻量级的架构，可以通过一些优化技术(包括基于位置感知数据、计算放置、复制和恢复)实现分布式数据密集型计算。PAN等[8]研究了边缘云计算系统的关键原理、关键技术、最先进的研究工作以及从边缘云计算中受益的典型物联网应用。边缘云计算中有效和高效的任务卸载是目前新兴的研究问题之一。对于该问题的研究可以根据任务之间的依赖性分为两类：有依赖性的任务卸载和无依赖性的任务卸载。前者通常被称为DAG任务调度，对于DAG任务调度问题，SAHNI等[9]提出联合调度任务和网络流使应用程序的整体完成时间最小化，设计了多阶段的贪婪调整算法，并考虑任务的放置和网络的调整；CHEN等[10]基于任务依赖性约束和设备预算约束，提出移动边缘计算系统下基于依赖性感知的卸载方案，将卸载问题划分为2个NP hard子问题，考虑2种不同的合作模式(第一个子问题只涉及边缘-云合作模式，而第二个子问题涉及边缘-云合作模式和边缘-边缘合作模式)，并针对这些子问题，设计了2种高效的贪婪算法。上述研究中的问题场景大多是静态的。对于无依赖性的任务卸载问题，MENG等[11]提出一种在线任务调度和分派方案，目的是最小化逾期任务的数量和平均响应时间；FANG等[12]考虑了任务的随机到达时间和异构的边缘服务器，提出一种下限近似的离线算法，该离线算法可以很容易地转化为分布式系统中的在线算法。此外，根据问题场景的实时性，边缘云计算中的任务卸载还可分为静态问题和动态问题。对于静态任务卸载，CHEN等[13]采用深度学习网络方法和顺序二次规划(SQP)技术来处理任务卸载决策和传输功率分配问题，目的是最小化延迟和能量消耗的加权总成本；NAOURI等[14]提出一个三层任务卸载框架，该框架由设备层、小云层和云层组成，设计了贪婪任务图分区卸载算法以达到最小化任务通信成本的目标；黄冬晴等[15]为实现能耗和时延的均衡优化，利用拉格朗日乘子法求解最佳计算资源分配，提出一个基于贪心算法的卸载算法求解最佳卸载决策。对于动态任务卸载，DING等[16]研究了边缘云中的动态任务分配问题，其中任务是任意到达的，服务器的状态会随着时间的推移而变化，从服务器联盟的角度创新地引入了动态联盟的算法，以减少用户成本；YUAN等[17]采用在线任务调度和公平调度方法，将任务动态地分配给最佳服务器，同时将轮回(RR)机制与深度强化学习(DRL)相结合，为任务分配适合的资源；WU等[18]基于区块链支持的物联网-边缘-云计算架构，开发了一种节能的动态任务卸载算法；吴学文等[19]提出了一种基于博弈论的资源分配与任务卸载方案(GRATO)以及一种基于博弈论的分布式任务卸载算法(GDTOA)，利用凸优化条件求解最优解，实现时延、能耗及系统效用最大化。现有大多数研究都假设需要卸载的任务是给定的，或者任务的到达率是已知的，在此基础上，高效的调度算法可以根据给定的任务静态信息或统计知识来实现[13-14]。然而，在实际场景下，任务的到达率可能会随着时间的推移而急剧变化，适用于静态问题的任务卸载算法可能不再适用于动态问题。因此，有必要提出一个有效的在线分配和调度方案。
本文探讨了边缘云计算系统中的在线任务卸载问题，目标是最小化所有任务的总加权响应时间。讨论了2个主要问题：(1)根据传输延迟和服务器的异构性，将随机到达的任务有效地卸载到合适的服务器上；(2)确定分配至同一目的地的任务优先级，并为其分配合适的计算资源，以使所有任务的总加权响应时间达到最小。在给定的任务集合中，静态任务卸载问题被证明是NP hard问题[20]，因此，动态任务卸载问题也是NP hard问题。所考虑的问题存在几个主要挑战：边缘和云的资源是异构的；云资源的效率很高，但成本和传输延迟也很高；边缘资源的效率低，但成本和传输延迟也较低；如何平衡成本和效率具有挑战性。本文主要研究：首先研究边缘云计算系统下的动态任务卸载问题，任务之间相互独立且随机到达，每个任务被分配一个权重，权重代表其延迟敏感度，问题目标是使所有任务加权响应时间的总和最小化；其次针对此问题，提出一个在线任务卸载框架，根据资源的可用性，周期性地调度和卸载任务到合适的服务器，资源的时间段占用和闲置情况也被周期性地管理并更新；然后根据权重将任务划分为不同的组，对每个组执行贪婪模拟退火启发式算法，以确定这些任务的卸载次序和卸载目的地，在卸载过程中，使用最高剩余密度优先(HRDF)原则以确定计算实例上的任务执行序列；最后基于Google Cluster[21]的工作负载跟踪，对所提算法进行评估，以证明算法的有效性，实验结果表明，所提算法可以有效减少总加权响应时间，与对比方案相比，在所设计算法下求解得到的解决方案中，高权重的任务一般可以获得较短的响应时间。边缘云计算系统中，动态任务卸载问题更为普遍和现实。文献[22]中的研究提出了一个更通用的问题模型，其中，任务在移动设备上按任意顺序和时间生成并卸载到服务器上，考虑任务和服务器之间的上传延迟和下载延迟，设计一种在线算法来最小化所有任务的总加权响应时间。本文以文献[22]中的研究作为研究基线。
1. 问题描述
在本文所考虑的问题中，任务到达系统的时间是随机的。假设系统在零点开始，并且周期性地进行任务调度，调度周期大小被设定为t，考虑存在Q个调度周期。在第q个调度周期，即在时间段[(q-1)×t, q×t]内，有nq个相互独立的任务Tq={T1, q, T2, q, …Tnq, q}到达，其中Ti, q代表Tq中的第i个任务。
云服务器上有J个计算实例C=I1c, I2c, …, IJc，边缘服务器上有K个计算实例E=I1e, I2e, …, IKe。计算实例可以是容器或者虚拟机，假设它们是单线程的，每个实例同时只能加工1个任务，每个任务每次只能在1个实例上加工。本文不考虑多租户的情况。这些计算实例是异质性的，具有不同的计算能力和用于上传和下载任务数据的带宽，具体来说，远程云服务器具有较强的计算能力，而边缘服务器具有较低的传输延迟。
用向量 < αi, q, βi, q, pi, q(I), li, q↑(I), li, q↓(I)>描述任务Ti, q，其中，αi, q是到达时间且满足αi, q∈[q-1×t, q×t]；βi, q是权重，代表任务的延迟敏感度、紧急情况或是否属于VIP级别的任务，权重是任务的一个静态属性，假设有M个级别，权重范围是1到M，级别越高表明任务的优先级越高；pi, q(I)，li, q↑(I)和li, q↓(I)是与计算实例相关的变量，pi, q(I)是任务在实例I上的处理时间，li, q↑(I)是上传任务数据到实例I的时间，li, q↓(I)是从实例I返回计算结果到移动终端的时间。为了避免迁移开销，任务在执行过程中不能在服务器之间迁移，但它可以在执行过程中被中断，也就是说，在所考虑的问题中允许任务抢占。
对于任务Ti, q的分配ai, q，可用向量 < Ii, q, bi, q↑, ei, q↑, Bi, q, Ei, q, bi, q↓, ei, q↓>描述，其中，Ii, q是分配给任务的计算实例且满足Ii, q∈C∪E；bi, q↑和ei, q↑是任务上传数据至Ii, q的开始和结束时间；bi, q↓和ei, q↓是任务从Ii, q下载数据的开始和结束时间；Bi, q和Ei, q是任务在Ii, q上的计算开始和结束时间。如果任务被抢占，二者可能不是一个单一的值，因此，任务的执行时间区间可以表示为[bi, q, h, ei, q, h](bi, q, h∈Bi, q, ei, q, h∈Ei, q)。响应时间ri, q是从任务到达时间到计算结果下载结束的时间间隔，定义为
ri,q=e↓i,q−αi,q∘ (1) 等待时间wi, q是任务在执行过程中被打断的总时间，定义为
wi,q=max{ei,q,h∣ei,q,h∈Ei,q}−min{bi,q,h∣bi,q,h∈ Bi,q}−pi,q(Ii,q)。 (2) SQ是在[0, Q×t]期间到达的任务分配集合。随着时间的推移，SQ不断被更新，因为新到达的任务可能会导致SQ发生变化，例如一些未完成的旧任务可能被新任务打断。SQ只有在满足以下约束条件的情况下才是可行的。
max{bi,q,h,bi′,q′,h′∣Ii,q=Ii′,q′}≥min{ei,q,h,ei′,q′,h′∣Ii,q= Ii′,q′}, (3) b↑i,q⩾αi,q, (4) bi,q⩾e↑i,q, (5) b↓i,q⩾ei,q, (6) e↑i,q=b↑i,q+l↑i,q(Ii,q), (7) e↓i,q=b↓i,q+l↓i,q(Ii,q), (8) pi,q(Ii,q)=∑ei,q,h∈Ei,q,bi,q,h∈Bi,q(ei,q,h−bi,q,h), (9) 其中，bi, q, h∈Bi, q, ei, q, h∈Ei, q, Ii, q∈C∪E(i=1, …, nq, q=1, …, Q)。约束条件(3)确保在同一实例上的任务之间执行时间不重叠；约束条件(4)表示任何任务不能在其到达之前开始；约束条件(5)表示任务的计算只有在数据传输完成后才能开始；约束条件(6)表示任务的计算结果只有在实例上计算完成后才能传回移动终端；方程(7)~(8)分别定义了任务数据的上传和下载结束时间；约束条件(9)确保任务的处理时间是完整的。
本文的研究目标是生成一个可行调度SQ，使所有任务总加权响应时间之和(W)SQ最小，(W)SQ可表示为
W(SQ)=Q∑q=1nq∑i=1(βi,q×ri,q)。 (10) 2. 问题求解
2.1 SAOF算法
本文提出一个基于贪婪模拟退火(SA)启发式算法的在线卸载框架(SAOF)，用于解决边缘云计算中动态和抢占式任务卸载问题。假设一个可行调度SQ在初始时刻ϵ=0时为空，SQ在ϵ=t, 2t, …，Q×t期间迭代更新，系统按照时间周期逐一安排随机到达的任务。在每个时间周期，首先，系统会实时监测任务的执行进度，并更新边缘服务器和云服务器资源的可用性；收集在此次时间周期(即[ϵ-t, ϵ])内到达的任务，以便对它们进行安排；然后根据任务的权重将其分为M组，按照权重非递增的顺序，依次对每个组执行SA算法，以获得可行的分配，其实质是为保证权重较大的任务能够得到更快的响应。
SAOF算法的框架见算法1。
算法1 SAOF算法
SQ←ø；
For q=1 to Q
监测任务的执行进度，并更新边缘服务器和云服务器资源的可用性；
收集在时间间隔[ϵ-t, ϵ]内需要调度的任务T1, q, T2, q, …, Tnq, q；
根据任务的权重将其分为M组G1, G2, …, GM；
For m=M to 1
对每个Gm执行SA算法，获得Gm中任务的安排；
SQ←SQ∪{ai, q|Ti, q∈Gm}；
返回SQ，算法结束。
2.2 SA算法
贪婪模拟退火(SA)启发式算法是SAOF算法的关键组成部分。对于需要安排的一组具有相同权重的任务，首先随机产生一个初始任务安排序列π0，作为迭代开始的初始解；其次调用ARRANGE算法计算给定序列中任务的分配，计算任务的总加权响应时间之和，记录最优的任务安排序列π*并初始化为π0；然后由产生函数N生成π0的邻域，这些邻居解是通过交换序列中任意一对任务的位置来构造的; 最后接收新解。新解的接收准则使用常用的Metropolis准则：若目标函数差Δ < 0，则接收新解，否则以概率P接收新解，P的计算公式：
P=11+e−Δ/λ, (11) 其中，λ为控制参数。随着算法的运行逐渐减小，退火过程中的冷却机制设置为λs+1=λs×r(0 < r < 1)，以维持计算速率与达到低能态二者之间的平衡。贪婪模拟退火过程是在最优序列的邻域上反复进行的，直到满足终止条件，从而在保证收敛的情况下以一定的概率跳出局部最优。设置3个终止条件：(1)在当前迭代中没有找到更好的解决方案；(2)计算时间超过了预定的阈值，在线卸载时每个时间周期的调度计算时间不能超过t/M，否则在下一个时间周期到达的任务将被推迟；(3)控制参数λ低于下限值λmin，若λ下降到λmin，则停止搜索。迭代过程中，最优调度S*和最优任务安排序列π*不断被更新。
SA算法的具体描述见算法2。
算法2 SA(Gm)算法
生成初始任务安排序列π0=T1, T2, …Tng, Ti∈Gm；
S*←ARRANGE(π0)；
W*←W(S0)；
π*←π0；
生成邻域Π=N(π*)；
While(不满足终止条件)
For ∀π∈Π do
S←ARRANGE(π)；
W←W(S)；
Δ←W-W*；
If Δ < 0 then S*←S；W*←W；π*←π；
Else
P←1/(1+e-Δ/λ)；
If P>random(0, 1) then S*←S；W*←W；π*←π；
λ=λ×r；
Π∈N(π*)；
返回S*，算法结束。
2.3 ARRANGE算法
SA算法中的ARRANGE算法决定了给定序列π中任务的分配，其基本思想是依次对π中的每个任务执行OFFLOADING算法以获得π中任务的分配。
ARRANGE算法的具体描述见算法3。
算法3 ARRANGE(π)算法
S←ø；
W←W(SQ)；
For i=1 to ng do
ai←OFFLOADING(Ti, W)；
将Ti分配给计算实例Ii；
S←S∪{ai}；
返回S，算法结束。
2.4 OFFLOADING算法
在ARRANGE算法中，每次迭代执行OFFLOADING步骤以确定给定任务的最优执行实例，并将该任务插入到该实例等待队列中的适当位置。对于需要卸载的任务T和已知的当前总加权响应时间W，OFFLOADING算法的基本思想是将任务卸载到能够使W增量达到最小的实例上。用Δmin表示W的最小增量值，abest记录任务的最优分配，假设在OFFLOADING算法开始时，abest为空，Δmin为无穷大。
任务的最优分配通过以下步骤确定：(1)当前时刻为ϵ时，实例I在时刻ϵ′接收到任务T的数据后，计算并比较任务T和当前正在执行的任务T*的剩余密度；在时刻ϵ′，任务T在实例I上的剩余密度是指任务权重和任务剩余执行时间的比值，即
R(I,ϵ′)=β/p(I,ϵ′), (12) 其中，β为任务T的权重，p(I, ϵ′)为任务T在实例I上的剩余执行时间。任务T*的剩余密度也是以类似方式计算。如果T具有更高的剩余密度，则T将中断T*并立即在时刻ϵ′开始计算，T*被抢占并移到等待队列Q中；否则T被放入Q中。(2)计算Q中任务的剩余密度，将等待的任务根据其剩余密度按非递增的顺序排列。(3)计算所有任务(包括T、T*和Q中的其他任务)在I上的分配，T的分配a取决于T本身在时刻ϵ′的状态，如果T在时刻ϵ′中断了T*，那么T的开始时间为ϵ′，否则T的开始时间由T在等待队列中的顺序决定。(4)计算任务T在每个实例上的W增量，如果得到更小的增量，则更新Δmin和abest。迭代过程中更新总加权响应时间W′。
OFFLOADING算法的具体描述见算法4。
算法4 OFFLOADING(T, W)算法
abest←NULL；
Δmin←+∞；
For ∀I∈C∪E do
ϵ′=ϵ+l↑(I)；
获取在时刻ϵ′，I上正在执行的任务T*；
计算在时刻ϵ′，T*的剩余密度R*；
计算在时刻ϵ′，T的剩余密度R；
If R>R* then
在时刻ϵ′中断T*并将其移入等待队列Q中；
在时刻ϵ′开始计算T；
Else
将T放入Q中；
计算Q中任务在时刻ϵ′的剩余密度；
将Q中任务根据剩余密度按非递增顺序排列；
计算I上所有任务的分配；
计算并更新总加权响应时间W′；
Δ←W′-W；
If Δ < Δmin then
Δmin←Δ；
abest←a；
返回abest，算法结束。
3. 实验评估及性能分析
为分析本文算法的性能，将SAOF算法同Sel-fish算法、Nearest算法以及文献[22]中的OnDisc算法进行比较，其中，Selfish算法[23-24]作为边缘云计算环境中常用的卸载调度方法，充分考虑每个任务自身的完成情况，将任务分配给能够使任务的处理最快结束的计算服务器；Nearest算法是边缘云计算系统中的经典卸载优化算法，有许多研究工作(例如文献[25]、[26])采用Nearest算法作为卸载调度策略，任务会被分配到距离数据源头(即终端设备)最近的计算服务器。所有算法均用Eclipse JDK 11.0.8实现并在1.5 GHz、16 G RAM PC机上执行，采用平均相对偏差ARPD(Average Relative Percentage Deviation, %)分析算法的实例性能。
ARPD=W−Wbest Wbest ×100%, (13) 其中，W是相应算法获得的目标函数值，Wbest是获得的最优目标值。
主要参数设置：根据Google cluster[21]的数据跟踪来设定任务的到达时间、权重和在边缘服务器上的处理时间；一个调度周期大小t设置为1 s；根据文献[22]，任务Ti, q在云服务器上处理时间与Ti, q在边缘服务器上的处理时间具有相关性(一般情况下约为Ti, q在边缘服务器上处理时间的0.75倍)，本文考虑到计算资源的异构特性和远程云较强的计算能力，设置Ti, q在云服务器上的处理时间为θp×pi, q(I)(I∈E)，设置θp为服从均匀分布, U(0.60, 0.80)；权重βi, q在1至11中随机设置；根据文献[22]对边缘云计算任务完成延迟特性的分析结果，任务与边缘服务器之间的上传延迟li, q↑(I)和下载延迟li, q↓(I)(I∈E)设置服从均匀分布U(0.01, 0.03)，相较于边缘服务器，任务与远程云服务器之间具有较长的传输延迟，设置任务与远程云服务器之间的上传延迟li, q↑(I)和下载延迟li, q↓(I)(I∈C)为服从均匀分布，U(0.2, 0.4)；将边缘服务器的数量K设置为10、15、20、25、30；将云服务器的数量J设置为2、4、8、12；将总任务数
N=Q∑q=1nq 设置为100、200、500、800、1 000，其中Q在5、10、20、50中随机设置。在SAOF算法中，将控制参数λ的初始值设置为100，将下限λmin设置为10-8以及下降速度r设置为0.98。
对于实验评估共有5×4×5=100种实例参数的组合，N∈{100, 200, 500, 800, 1 000}, J∈{2, 4, 8, 12}, K∈{10, 15, 20, 25, 30}，为每种组合随机生成5个实例，在这些实例上测试比较4种算法的性能，因此共有100×5×4=2 000个实验结果。表 1给出了在ARPD评判标准下，算法在全部测试实例上的运行结果；图 1给出了在95.0%的Tukey HSD区间不同实例参数与算法之间的相互作用。
表 1 算法的平均相对偏差比较Table 1. The comparison of average relative percentage deviation of algorithms% 参数 参数值 ARPD Nearest Selfish OnDisc SAOF N 100 24.446 14.446 3.459 0 200 25.613 15.598 4.953 0 500 27.647 17.646 6.690 0 800 27.211 17.236 6.228 0 1 000 26.624 16.650 5.889 0 J 2 27.028 16.307 5.231 0 4 27.158 16.849 5.658 0 8 27.573 17.260 5.859 0 12 27.610 17.269 5.866 0 K 10 24.223 15.210 2.937 0 15 25.417 16.388 4.119 0 20 27.531 18.363 5.196 0 25 28.894 20.353 6.637 0 30 30.298 20.935 8.226 0 平均 — 27.020 17.179 5.496 0 ![]()
图 1 95.0% Tukey HSD区间下实例参数与算法之间的相互作用Figure 1. The interactions between instance parameters and the compared algorithms with 95.0% Tukey HSD intervals由表 1可以看出，SAOF算法在所有实例中都有最好的ARPD值，ARPD平均值为0.000%，优于OnDisc算法(5.496%)、Selfish算法(17.179%)和Nearest算法(27.020%)，原因可能在于：OnDisc算法在有多个任务同时到达系统的情况下，随机选择某个任务进行分配，而缺乏高效的任务分配序列，并且在任务安排过程中注重贪婪策略，从而过早地收敛到局部最优；Selfish算法只会考虑每个任务自身的性能表现情况，而不考虑任务为其他任务带来的影响，比如当前执行的任务给其他任务带来等待时间等；Nearest算法以服务器与任务数据之间的传输延迟作为任务分配原则，导致任务更多地被分配到传输延迟更小、但同时计算能力也更弱的边缘服务器，而很少使用到远程云上强大的计算资源；而SA算法调整了任务分配方案，旨在寻找更有效的任务分配序列，SAOF算法具有优势的地方在于，SAOF算法在搜索最优解的过程中，借助邻域搜索，并且会以一定的概率接受一个比当前解更差的解，因此有可能会跳出局部最优解，找到全局最优解。
由图 1A可以看出，在不同数量的任务中，SAOF算法在ARPD评判标准下的性能表现最优，在任务规模越来越大的情况下，SAOF算法依然能够保持很好的性能，说明SAOF算法在面对大规模任务时，依然能达到动态收敛，具有很好的全局收敛性和鲁棒性。由图 1B可以看出，随着边缘服务器数量的增加，SAOF算法在ARPD评判标准下的性能表现稳定且最优，尤其是在边缘服务器数量较多时，更能体现出优势，与其他对比算法的性能表现具有统计意义上的差异，说明SAOF算法能够很好地适应计算资源的变化。由图 1C可以看出，随着远程云服务器数量的增加，SAOF算法在ARPD评判标准下性能表现依然最优，当远程云服务器数量增大到一定规模时，数量的改变对实验结果的影响微弱(远程云服务器数量由8增大至12时，SAOF算法的ARPD仅增加0.007%)，因为当计算资源充裕时，部分远程云服务器会由于其很大的传输延迟而导致远程云服务器的使用率降低，此时远程云服务器数量的增长对实验结果的影响微小。综上，SAOF算法在不同参数变化的情况下，性能表现总能保持最优，反映了SAOF算法对参数变化较不敏感。
基于实验结果可以得出结论：SAOF算法更适合且可以更有效地解决本文所考虑的问题。
4. 结论
考虑边缘云计算系统中的动态和抢占式任务卸载问题，使所有任务加权响应时间之和最小化，提出基于贪婪模拟退火启发式算法(SA)的在线卸载框架(SAOF)，该框架由SA算法、ARRANGE算法和OFFLOADING算法组成。SA算法用于提升解的质量；在SA中，ARRANGE算法用于确定一个指定任务序列的安排；OFFLOADING算法用于确定指定任务的最优卸载目的地以及该任务的最优分配方案。实验结果表明SAOF算法在所研究问题上的性能优于对比算法。
在本文考虑的问题场景中，任务在服务器上的处理时间是确定的，在今后的研究中可以考虑对具有不确定性资源模型的问题进行求解。
-
![]()
图 1 95.0% Tukey HSD区间下实例参数与算法之间的相互作用
Figure 1. The interactions between instance parameters and the compared algorithms with 95.0% Tukey HSD intervals
表 1 算法的平均相对偏差比较
Table 1 The comparison of average relative percentage deviation of algorithms
% 参数 参数值 ARPD Nearest Selfish OnDisc SAOF N 100 24.446 14.446 3.459 0 200 25.613 15.598 4.953 0 500 27.647 17.646 6.690 0 800 27.211 17.236 6.228 0 1 000 26.624 16.650 5.889 0 J 2 27.028 16.307 5.231 0 4 27.158 16.849 5.658 0 8 27.573 17.260 5.859 0 12 27.610 17.269 5.866 0 K 10 24.223 15.210 2.937 0 15 25.417 16.388 4.119 0 20 27.531 18.363 5.196 0 25 28.894 20.353 6.637 0 30 30.298 20.935 8.226 0 平均 — 27.020 17.179 5.496 0 
下载: 导出CSV
-
[1] AMAZON. Aws IoT greengrass[R/OL]. (2017-06-07)[2022-12-26]. https://docs.aws.amazon.com/zhcn/greengrass/latest/developerguide/what-is-gg.html.
[2] GOOGLE. Google cloudiot edge[R/OL]. (2018-08-06)[2022-12-26]. https://cloud.google.com/iot-edge.
[3] AZURE. Azureiot edge[R/OL]. (2017-11-16)[2022-12-26]. https://github.com/Azure/iotedge.
[4] XIONG Y H, HUANG S Z, WU M, et al. A Johnson's-rule based genetic algorithm for two-stage-task scheduling problem in data-centers of cloud computing[J]. IEEE Transactions on Cloud Computing, 2019, 7(3): 597-610. doi: 10.1109/TCC.2017.2693187
[5] SAHOO S, SAHOO B, TURUK A K. A learning automata-based scheduling for dead-line sensitive task in the cloud[J]. IEEE Transactions on Services Computing, 2021, 14(6): 1662-1674. doi: 10.1109/TSC.2019.2906870
[6] ABBAS N, ZHANG Y, TAHERKORDI A, et al. Mobile edge computing: a survey[J]. IEEE Internet of Things Journal, 2018, 5(1): 450-465. doi: 10.1109/JIOT.2017.2750180
[7] JONATHAN A, RYDEN M, OH K, et al. Nebula: distributed edge cloud for data intensive computing[J]. IEEE Transactions on Parallel and Distributed Systems, 2017, 28(11): 3229-3242. doi: 10.1109/TPDS.2017.2717883
[8] PAN J, MCELHANNON J. Future edge cloud and edge computing for internet of things applications[J]. IEEE Internet of Things Journal, 2018, 5(1): 439-449. doi: 10.1109/JIOT.2017.2767608
[9] SAHNI Y, CAO H N, YANG L. Data-aware task allocation for achieving low latency in collaborative edge computing[J]. IEEE Internet of Things Journal, 2019, 6(2): 3512-3524. doi: 10.1109/JIOT.2018.2886757
[10] CHEN L, WU J G, ZHANG J, et al. Dependency-aware computation offloading for mobile edge computing with edge-cloud cooperation[J]. IEEE Transactions on Cloud Computing, 2020, 10(4): 2451-2468.
[11] MENG J Y, TAN H S, LI X Y, et al. Online deadline-aware task dispatching and scheduling in edge computing[J]. IEEE Transactions on Parallel and Distributed Systems, 2020, 31(6): 1270-1286. doi: 10.1109/TPDS.2019.2961905
[12] FANG X L, CAI Z P, TANG W Y, et al. Job scheduling to minimize total completion time on multiple edge servers[J]. IEEE Transactions on Network Science and Engineering, 2020, 7(4): 2245-2255. doi: 10.1109/TNSE.2019.2958281
[13] CHEN Q L, KUANG Z F, ZHAO L. Multiuser computation offloading and resource allocation for cloud edge heterogeneous network[J]. IEEE Internet of Things Journal, 2022, 9(5): 3799-3811. doi: 10.1109/JIOT.2021.3100117
[14] NAOURI A, WU H X, NOURI N A, et al. A novel framework for mobile-edge computing by optimizing task offloading[J]. IEEE Internet of Things Journal, 2021, 8(16): 13065-13076. doi: 10.1109/JIOT.2021.3064225
[15] 黄冬晴, 俞黎阳, 陈珏, 等. 面向移动边缘计算的联合计算卸载和资源分配策略研究[J]. 华东师范大学学报(自然科学版), 2021(6): 88-99. https://www.cnki.com.cn/Article/CJFDTOTAL-HDSZ202106010.htm [16] DING S Y, LIN D H. Dynamic task allocation for cost-efficient edge cloud computing[C]//IEEE Proceedings of the International Conference on Services Computing (SCC). Beijing: IEEE, 2020: 218-225.
[17] YUAN H, TANG G M, LI X Y, et al. Online dispatching and fair scheduling of edge computing tasks: a learning-based approach[J]. IEEE Internet of Things Journal, 2021, 8(19): 14985-14998. doi: 10.1109/JIOT.2021.3073034
[18] WU H M, WOLTER K, JIAO P F, et al. Eedto: an energy-efficient dynamic task offloading algorithm for blockchain-enabled IoT-Edge-cloud orchestrated computing[J]. IEEE Internet of Things Journal, 2021, 8(4): 2163-2176. doi: 10.1109/JIOT.2020.3033521
[19] 吴学文, 廖婧贤. 云边协同系统中基于博弈论的资源分配与任务卸载方案[J]. 系统仿真学报, 2022, 34(7): 1468-1481. https://www.cnki.com.cn/Article/CJFDTOTAL-XTFZ202207009.htm [20] DINH T Q, TANG J H, LA Q D, et al. Offloading in mobile edge computing: task allocation and computational frequency scaling[J]. IEEE Transactions on Communications, 2017, 65(8): 3571-3584.
[21] REISS C, WIKES J, HELLERSTEIN J L. Google cluster-usage traces: format+schema[R]. Google Inc. White Paper, 2011.
[22] HAN Z H, TAN H S, LI X Y, et al. OnDisc: online latency-sensitive job dispatching and scheduling in heterogeneous edge-clouds[J]. IEEE ACM Transactions on Networking, 2019, 27(6): 2472-2485. doi: 10.1109/TNET.2019.2953806
[23] MA X, LIN C, ZHANG H, et al. Energy-aware computation offloading of IoT sensors in cloudlet-based mobile edge computing[J]. Sensors, 2018, 18(6): 1945-1950. doi: 10.3390/s18061945
[24] MA X, LIN C, XIANG X D, et al. Game-theoretic analysis of computation offloading for cloudlet-based mobile cloud computing[C]//ACM International Conference. Mexico: ACM, 2015: 271-278.
[25] JIA M, CAO J N, LIANG W F. Optimal cloudlet placement and user to cloudlet allocation in wireless metropolitan area networks[J]. IEEE Transactions on Cloud Computing, 2017, 5(4): 725-737. doi: 10.1109/TCC.2015.2449834
[26] TAWALBEH L, JARARWEH Y, ABABNEH F, et al. Large scale cloudlets deployment for efficient mobile cloud computing[J]. Journal of Networks, 2015, 10(1): 70-76.
-
期刊类型引用(2)
1. 周伟，丁雪莹，谢志强. 考虑柔性设备加工能力的综合调度算法. 华南师范大学学报(自然科学版). 2024(02): 110-118 . 
百度学术
2. 胡欣，沈伟，李伟，王兴龙，陈逸君. 基于改进边缘算法的通信光缆设备智能检测技术研究. 粘接. 2024(10): 140-144 . 百度学术
其他类型引用(0)
计量
- 文章访问数: 199
- HTML全文浏览量: 55
- PDF下载量: 61
- 被引次数: 2
