李誉昌; 吴晓斌; 朱苏皖; 邱健; 骆开庆; 韩鹏

doi:10.6054/j.jscnun.2015.03.037

摘要: 摘要：通过实验，系统研究了103nm/225nm，103nm/388nm两种双分散颗粒系在不同光强贡献比例下的动态光散射特性，包括平均粒径、分散度poly、自相关函数及其斜率变化与光强贡献的关系。发现双指数法和最小二乘法反演平均粒径比较接近理论值，累积量法反演的平均粒径整体偏小；在大颗粒光强贡献较大时，poly的变化受小颗粒光强的影响较大，反之在小颗粒的光强贡献较大时，poly的变化受大颗粒光强的影响相对较小；在本文研究情况下，光强贡献比和自相关函数斜率最小值对应的延迟时间具有较好的线性关系；指出在光强贡献比改变时，poly与自相关函数曲线斜率的最小值有相同的变化趋势。研究结果对双分散颗粒系动态光散射特性的精确测量及测量系统的优化有参考价值。

关键词:

自相关函数曲线

近些年来，云计算得到了迅速发展和广泛应用，云计算平台拥有很好的可扩展性和无限制的计算资源，它可以提供高度可靠和可用的服务。然而，由于在地理上呈现分布式布置的各种数据采集设备所产生的数据量快速增长，庞大的数据量在远程云数据中心进行处理和分析是不现实的，远程云通常距离终端用户很远，移动设备可能会面临很大的通信延迟。尽管计算密集型应用可以通过云资源得到极大的支持，但在大多数情况下，长时间的延迟是难以接受的，尤其是对于延迟敏感型和数据密集型的应用。面对低延迟和高性能的矛盾，边缘云计算作为一种新的计算模式应运而生。在边缘计算系统中，一些智能而价格低廉的边缘服务器被配置在网络边缘，通过将任务从移动终端卸载到边缘服务器或云服务器，服务效率可以得到很好的提升。在边缘云计算中，如何有效地安排和调度任务到具有多种约束限制的服务器是非常重要的，有效的任务调度算法可以将任务卸载到合适的目的地，同时充分考虑到所需的传输延迟和计算时间。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]内，有n_q个相互独立的任务T_q={T_{1, q}, T_{2, q}, …T_{n_q, q}}到达，其中T_{i, q}代表T_q中的第i个任务。

云服务器上有J个计算实例C=I₁^c, I₂^c, …, I_J^c，边缘服务器上有K个计算实例E=I₁^e, I₂^e, …, I_K^e。计算实例可以是容器或者虚拟机，假设它们是单线程的，每个实例同时只能加工1个任务，每个任务每次只能在1个实例上加工。本文不考虑多租户的情况。这些计算实例是异质性的，具有不同的计算能力和用于上传和下载任务数据的带宽，具体来说，远程云服务器具有较强的计算能力，而边缘服务器具有较低的传输延迟。

用向量 < α_{i, q}, β_{i, q}, p_{i, q}(I), l_{i, q}^↑(I), l_{i, q}^↓(I)>描述任务T_{i, q}，其中，α_{i, q}是到达时间且满足α_{i, q}∈[q-1×t, q×t]；β_{i, q}是权重，代表任务的延迟敏感度、紧急情况或是否属于VIP级别的任务，权重是任务的一个静态属性，假设有M个级别，权重范围是1到M，级别越高表明任务的优先级越高；p_{i, q}(I)，l_{i, q}^↑(I)和l_{i, q}^↓(I)是与计算实例相关的变量，p_{i, q}(I)是任务在实例I上的处理时间，l_{i, q}^↑(I)是上传任务数据到实例I的时间，l_{i, q}^↓(I)是从实例I返回计算结果到移动终端的时间。为了避免迁移开销，任务在执行过程中不能在服务器之间迁移，但它可以在执行过程中被中断，也就是说，在所考虑的问题中允许任务抢占。

对于任务T_{i, q}的分配a_{i, q}，可用向量 < I_{i, q}, b_{i, q}^↑, e_{i, q}^↑, B_{i, q}, E_{i, q}, b_{i, q}^↓, e_{i, q}^↓>描述，其中，I_{i, q}是分配给任务的计算实例且满足I_{i, q}∈C∪E；b_{i, q}^↑和e_{i, q}^↑是任务上传数据至I_{i, q}的开始和结束时间；b_{i, q}^↓和e_{i, q}^↓是任务从I_{i, q}下载数据的开始和结束时间；B_{i, q}和E_{i, q}是任务在I_{i, q}上的计算开始和结束时间。如果任务被抢占，二者可能不是一个单一的值，因此，任务的执行时间区间可以表示为[b_{i, q, h}, e_{i, q, h}](b_{i, q, h}∈B_{i, q}, e_{i, q, h}∈E_{i, q})。响应时间r_{i, q}是从任务到达时间到计算结果下载结束的时间间隔，定义为

$r_{i, q}=e_{i, q}^{\downarrow}-\alpha_{i, q} \circ$

(1)

等待时间w_{i, q}是任务在执行过程中被打断的总时间，定义为

$\begin{aligned} & w_{i, q}=\max \left\{e_{i, q, h} \mid e_{i, q, h} \in E_{i, q}\right\}-\min \left\{b_{i, q, h} \mid b_{i, q, h} \in\right. \\ & \ \ \ \ \left.B_{i, q}\right\}-p_{i, q}\left(I_{i, q}\right) 。 \end{aligned}$

(2)

S_Q是在[0, Q×t]期间到达的任务分配集合。随着时间的推移，S_Q不断被更新，因为新到达的任务可能会导致S_Q发生变化，例如一些未完成的旧任务可能被新任务打断。S_Q只有在满足以下约束条件的情况下才是可行的。

$\begin{array}{l} \max \left\{ {{b_{i, q, h}}, {b_{{i^\prime }, {q^\prime }, {h^\prime }}}\mid {I_{i, q}} = {I_{{i^\prime }, {q^\prime }}}} \right\} \ge \min \left\{ {{e_{i, q, h}}, {e_{{i^\prime }, {q^\prime }, {h^\prime }}}\mid {I_{i, q}} = } \right.\\ \ \ \ \ \left. {{I_{{i^\prime }, {q^\prime }}}} \right\}, \end{array}$

(3)

$b_{i, q}^{\uparrow} \geqslant \alpha_{i, q},$

(4)

$b_{i, q} \geqslant e_{i, q}^{\uparrow},$

(5)

$b_{i, q}^{\downarrow} \geqslant e_{i, q},$

(6)

$e_{i, q}^{\uparrow}=b_{i, q}^{\uparrow}+l_{i, q}^{\uparrow}\left(I_{i, q}\right),$

(7)

$e_{i, q}^{\downarrow}=b_{i, q}^{\downarrow}+l_{i, q}^{\downarrow}\left(I_{i, q}\right),$

(8)

$p_{i, q}\left(I_{i, q}\right)=\sum\limits_{e_{i, q, h} \in E_{i, q}, b_{i, q, h} \in B_{i, q}}\left(e_{i, q, h}-b_{i, q, h}\right),$

(9)

其中，b_{i, q, h}∈B_{i, q}, e_{i, q, h}∈E_{i, q}, I_{i, q}∈C∪E(i=1, …, n_q, q=1, …, Q)。约束条件(3)确保在同一实例上的任务之间执行时间不重叠；约束条件(4)表示任何任务不能在其到达之前开始；约束条件(5)表示任务的计算只有在数据传输完成后才能开始；约束条件(6)表示任务的计算结果只有在实例上计算完成后才能传回移动终端；方程(7)~(8)分别定义了任务数据的上传和下载结束时间；约束条件(9)确保任务的处理时间是完整的。

本文的研究目标是生成一个可行调度S_Q，使所有任务总加权响应时间之和(W)S_Q最小，(W)S_Q可表示为

$W\left(S_Q\right)=\sum\limits_{q=1}^Q \sum\limits_{i=1}^{n_q}\left(\beta_{i, q} \times r_{i, q}\right) 。$

(10)

2. 问题求解

2.1 SAOF算法

本文提出一个基于贪婪模拟退火(SA)启发式算法的在线卸载框架(SAOF)，用于解决边缘云计算中动态和抢占式任务卸载问题。假设一个可行调度S_Q在初始时刻ϵ=0时为空，S_Q在ϵ=t, 2t, …，Q×t期间迭代更新，系统按照时间周期逐一安排随机到达的任务。在每个时间周期，首先，系统会实时监测任务的执行进度，并更新边缘服务器和云服务器资源的可用性；收集在此次时间周期(即[ϵ-t, ϵ])内到达的任务，以便对它们进行安排；然后根据任务的权重将其分为M组，按照权重非递增的顺序，依次对每个组执行SA算法，以获得可行的分配，其实质是为保证权重较大的任务能够得到更快的响应。

SAOF算法的框架见算法1。

算法1 SAOF算法

S_Q←ø；

For q=1 to Q

监测任务的执行进度，并更新边缘服务器和云服务器资源的可用性；

收集在时间间隔[ϵ-t, ϵ]内需要调度的任务T_{1, q}, T_{2, q}, …, T_n_q, q；

根据任务的权重将其分为M组G₁, G₂, …, G_M；

For m=M to 1

对每个G_m执行SA算法，获得G_m中任务的安排；

S_Q←S_Q∪{a_{i, q}|T_{i, q}∈G_m}；

返回S_Q，算法结束。

2.2 SA算法

贪婪模拟退火(SA)启发式算法是SAOF算法的关键组成部分。对于需要安排的一组具有相同权重的任务，首先随机产生一个初始任务安排序列π₀，作为迭代开始的初始解；其次调用ARRANGE算法计算给定序列中任务的分配，计算任务的总加权响应时间之和，记录最优的任务安排序列π^*并初始化为π₀；然后由产生函数N生成π₀的邻域，这些邻居解是通过交换序列中任意一对任务的位置来构造的; 最后接收新解。新解的接收准则使用常用的Metropolis准则：若目标函数差Δ < 0，则接收新解，否则以概率P接收新解，P的计算公式：

$P=\frac{1}{1+\mathrm{e}^{-\Delta / \lambda}},$

(11)

其中，λ为控制参数。随着算法的运行逐渐减小，退火过程中的冷却机制设置为λ_s+1=λ_s×r(0 < r < 1)，以维持计算速率与达到低能态二者之间的平衡。贪婪模拟退火过程是在最优序列的邻域上反复进行的，直到满足终止条件，从而在保证收敛的情况下以一定的概率跳出局部最优。设置3个终止条件：(1)在当前迭代中没有找到更好的解决方案；(2)计算时间超过了预定的阈值，在线卸载时每个时间周期的调度计算时间不能超过t/M，否则在下一个时间周期到达的任务将被推迟；(3)控制参数λ低于下限值λ_min，若λ下降到λ_min，则停止搜索。迭代过程中，最优调度S^*和最优任务安排序列π^*不断被更新。

SA算法的具体描述见算法2。

算法2 SA(G_m)算法

生成初始任务安排序列π₀=T₁, T₂, …T_n_g, T_i∈G_m；

S^*←ARRANGE(π₀)；

W^*←W(S₀)；

π^*←π₀；

生成邻域Π=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(S_Q)；

For i=1 to n_g do

a_i←OFFLOADING(T_i, W)；

将T_i分配给计算实例I_i；

S←S∪{a_i}；

返回S，算法结束。

2.4 OFFLOADING算法

在ARRANGE算法中，每次迭代执行OFFLOADING步骤以确定给定任务的最优执行实例，并将该任务插入到该实例等待队列中的适当位置。对于需要卸载的任务T和已知的当前总加权响应时间W，OFFLOADING算法的基本思想是将任务卸载到能够使W增量达到最小的实例上。用Δ_min表示W的最小增量值，a_best记录任务的最优分配，假设在OFFLOADING算法开始时，a_best为空，Δ_min为无穷大。

任务的最优分配通过以下步骤确定：(1)当前时刻为ϵ时，实例I在时刻ϵ′接收到任务T的数据后，计算并比较任务T和当前正在执行的任务T^*的剩余密度；在时刻ϵ′，任务T在实例I上的剩余密度是指任务权重和任务剩余执行时间的比值，即

$R\left(I, \epsilon^{\prime}\right)=\beta / p\left(I, \epsilon^{\prime}\right),$

(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和a_best。迭代过程中更新总加权响应时间W′。

OFFLOADING算法的具体描述见算法4。

算法4 OFFLOADING(T, W)算法

a_best←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←Δ；

a_best←a；

返回a_best，算法结束。

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, %)分析算法的实例性能。

$\mathrm{ARPD}=\frac{W-W_{\text {best }}}{W_{\text {best }}} \times 100 \% ,$

(13)

其中，W是相应算法获得的目标函数值，W_best是获得的最优目标值。

主要参数设置：根据Google cluster^[21]的数据跟踪来设定任务的到达时间、权重和在边缘服务器上的处理时间；一个调度周期大小t设置为1 s；根据文献[22]，任务T_{i, q}在云服务器上处理时间与T_{i, q}在边缘服务器上的处理时间具有相关性(一般情况下约为T_{i, q}在边缘服务器上处理时间的0.75倍)，本文考虑到计算资源的异构特性和远程云较强的计算能力，设置T_{i, q}在云服务器上的处理时间为θ_p×p_{i, q}(I)(I∈E)，设置θ_p为服从均匀分布, U(0.60, 0.80)；权重β_{i, q}在1至11中随机设置；根据文献[22]对边缘云计算任务完成延迟特性的分析结果，任务与边缘服务器之间的上传延迟l_{i, q}^↑(I)和下载延迟l_{i, q}^↓(I)(I∈E)设置服从均匀分布U(0.01, 0.03)，相较于边缘服务器，任务与远程云服务器之间具有较长的传输延迟，设置任务与远程云服务器之间的上传延迟l_{i, q}^↑(I)和下载延迟l_{i, q}^↓(I)(I∈C)为服从均匀分布，U(0.2, 0.4)；将边缘服务器的数量K设置为10、15、20、25、30；将云服务器的数量J设置为2、4、8、12；将总任务数

$N=\sum\limits_{q=1}^Q n_q$

设置为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

下载: 导出CSV

| 显示表格

图 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] Pecora R. Dynamic light scattering measurement of nanometer particles in liquids [J]. Journal of Nanoparticle Research, 2000, 2(2): 123-131
[2] 喻雷寿，杨冠玲，何振江，等. 用于动态光散射颗粒测量的迭代CONTIN算法 [J]. 光电工程，2006，33(1)：64-69.
[3] 任师波，韩鹏，杨冠玲. 用于光子相关光谱颗粒粒度测量的实数编码混合遗传算法 [J]. 计算物理，2011，28(1): 87-93.
[4] 邱健，杨冠玲韩鹏，等. 光子相关光谱的自寻优累积反演算法的实现 [J]. 计算物理，2011,28(2): 268-273.
[5] Hui X, Yuan Y X, Hao H, et al. Particle sizing of colloidal suspensions by low-coherence fiber optic dynamic light scattering [J]. Journal of Colloid Interface Science, 2012, 367(1): 367-530.
[6] Sch?tzel K, Drewel M, Ahrens J. Suppression of multiple scattering by photon cross-correlation techniques [J]. Journal of Modern Optics, 1991, 38(9): 1849-1865.
[7] Chu B. Laser Light Scattering: Basic Principles and Practice [M]. 2nd edn. New York: Dover Publication, 2007.
[8] Pecora R. Dynamic Light Scattering: Application of Photon Correlation Spectroscopy [M]. New York: Plenum Press, 1985.
[9] Instruction Manual for BI-9000AT Digital Autocorrelation [M]. Brookhaven Instruments Corporation, 1989.
[10] ISO 13321. Particle Size Analysis: Photon Correlation Spectroscopy [S].

通讯作者:
韩鹏

计量