动态雾计算网络中基于在线学习的任务卸载算法*

2020-09-17谭友钰陈蕾周明拓王昆仑杨旸张武雄

中国科学院大学学报 2020年5期

谭友钰，陈蕾，周明拓，王昆仑，杨旸，张武雄

(1 中国科学院上海微系统与信息技术研究所，上海 200050； 2 国网浙江省电力有限公司，杭州 310007；3 中国科学院大学，北京 100049； 4 上海科技大学，上海 201210； 5 上海雾计算实验室，上海 201210)

随着智能物联网、5G与人工智能等技术的兴起与发展，处理海量且多样性的数据、满足超低的服务时延需求，成为越来越亟待解决的问题[1]。传统的基于集中式的云计算架构由于终端设备与云服务器的遥远距离而产生较大时延，已难以满足时延敏感性服务的需求；同时，基于集中式的管理也难以支撑海量设备的接入。在这种情况下，雾计算(fog computing)[2]应运而生。雾计算技术将通信、计算、控制和存储等能力从云端推向网络边缘(如(小)基站、无线接入点及其他有计算能力的终端设备)[3]，通过资源共享机制和协同服务架构帮助资源有限的移动设备执行具有超低延迟限制的计算密集型应用程序，从而有效提升用户体验或者生产效率，有望成为支撑未来智能物联网、5G和人工智能应用的关键技术[4-5]，受到广泛的关注与研究。

任务卸载(task offloading)是雾计算的主要技术之一，计算资源有限的节点在难以独立支持应用服务时，可将计算任务卸载到网络中资源充足的节点帮助计算。需要进行任务卸载的节点叫做任务节点(task node)，提供计算帮助的节点叫做帮助节点(help node)。时延和能耗是任务卸载过程中两个重要的指标，有大量学者对其进行了研究[2-11]，本文主要考虑时延。

一方面，目前大多数学者考虑的都是静态网络里的任务卸载，即在任务卸载过程中，网络中的移动设备处于静止状态，且帮助节点所提供的计算资源保持不变[6-7]。在文献[6]的研究模型里，终端设备可以通过基站将任务卸载给附近的云，为多设备的任务卸载场景提出一种基于博弈论的任务卸载算法。Dinh等[7]通过联合优化任务分配和节点的计算频率，最小化时延和能量总消耗。然而在实际中，任务节点和帮助节点往往都不是静止的，而是处在移动状态，经历着多变的无线信道；并且，帮助节点可提供的计算资源也可能发生变化。

另一方面，现有的研究大都假设系统中的节点状态信息已知，或者这些信息可以实时广播到网络中[8-9]。由于任务的卸载决策通常需要帮助节点状态相关信息，比如任务队列长度、可共享资源大小等，因此任务卸载过程本身便可看作典型的随机决策过程。对此，许多研究工作利用李亚普诺夫优化(Lyapunov optimization)等方法解决这种随机决策问题，从而实现任务或计算资源的近似最优分配[8-9]。不停在网络中广播及监听节点的状态信息会产生大量的能量开销，影响设备使用时长，在未来超大规模体系中，节点个数倍数增加的场景下，这个问题将更加突出。

为减少由于多次沟通信息导致的能量损耗，基于学习 (learning) 的方法被提出[10]。文献[10]使用马尔可夫决策方法动态地进行服务资源的配置和卸载决策。Tan等[11]为雾计算网络设计基于学习的任务卸载算法，但未建模考虑任务的排队情况，此外，该工作也未考虑任务本身的时延需求，可能过多地导致任务不满足时延需求。

在实际情况中，节点会动态出入网络，帮助节点可共享的计算资源也会随情况发生变化；同时，实时在网络中传输或广播节点状态信息又会造成大量的能量开销。这样一个最贴近实际需求又有待解决的问题，却鲜有学者研究。本文旨在为这样的动态雾计算网络设计任务卸载算法，最优化设备的任务卸载时延，同时尽量满足其任务时延需求，任务节点无需实时请求网络中帮助节点的状态信息，如队列信息及计算资源信息等，而是以很小的计算代价根据自己的历史卸载经验学习和判断得来。本文动态雾计算网络中的“动态”有3个含义：1)网络中的节点运动状态可变；2)网络大小可变：节点可自由出入网络；3)帮助节点可提供的计算资源可变。

本文首先为稳定状态下的动态网络提出任务卸载算法TOD(online learning-based task offloading algorithm for the dynamic fog networks under stationary status)。在稳定状态里，网络中节点的参数达到稳定。稳定状态一般适用于以下场景：节点静止或缓慢移动，可自由出入网络，帮助节点可提供稳定的计算资源。接着，扩展TOD算法到非稳定网络状态下，提出TOD-N算法(online learning-based task offloading algorithm for the dynamic fog networks under non-stationary status)，以动态追踪网络中变化的最优资源和节点。在非稳定环境中，系统参数会随着时间而变化。非稳定状态可能包含有以下场景：节点(快速)移动，可自由出入网络，信道环境变化较大，帮助节点可提供计算资源随时间改变。然后，针对所提出的两个算法进行详细的性能分析，包括算法与理想算法的近似情况、算法复杂度分析以及存储空间占用分析等。仿真结果表明，本文算法所能达到的卸载时延与理想情况下的最优卸载时延十分相近，且任务卸载服务的时延满足率显著提升；此外，TOD-N算法在非稳定的网络状态下能够追踪计算资源与环境的变化，与贪心 (Greedy) 算法相比，性能显著提升。

1 系统模型与问题建模

1.1 系统模型与目标

本文考虑单对多(单个任务节点，多个帮助节点)任务卸载，且任务不可拆分的情况，即一个任务节点可从多个帮助节点中选择一个来卸载任务。将时间划分为若干个时隙，假设从时隙t=0开始，UE在每个时隙的开始产生一个卸载请求Rt，表示为Rt={xt,Δt}，其中xt为Rt任务大小，Δt表示任务Rt可容忍的最大时延。通常，由于返回的结果很小(几到几十个比特)，结果的返回时延可忽略不计[3]。每当有卸载请求时，UE从愿意共享计算资源的候选帮助节点里选择一个来完成任务卸载。将t时隙里UE的候选节点表示为集合H(t)，H(t)={H1,H2,…,Hh(t)}，其中h(t)=|H(t)|。由于UE不能实时掌握或请求网络中帮助节点的节点状态信息，因此，UE需要根据自己的历史卸载数据等对当前帮助节点Hk∈H(t)进行学习，以便找到优秀的帮助节点进行任务卸载。如图1所示，UE选择H2卸载任务Rt。

图1 t时隙下的动态雾网络图示Fig.1 Illustration of the dynamic fog network at time t

本文以最小化平均任务卸载时延、提高任务卸载成功率为目标设计任务卸载算法。任务的卸载时延包含3个部分[3]：传输时延、等待时延和计算时延。

(1)

式中rk(t)为UE到Hk的传输速率，根据香农公式可得

(2)

(3)

(4)

最终，UE将Rt卸载到Hk的卸载服务时延可表示为

(5)

令Π表示在从t=1到t=T所有可能的卸载策略，则直到t=T为止，UE的任务平均卸载时延为

(6)

1.2 将原模型建模为MAB问题

(7)

与传统的MAB问题相比，本文的研究问题有如下挑战：1) 传统的MAB问题动作空间恒定，本文由于节点移动出入网络或是否愿意继续共享资源，使问题具有动态变化的动作空间，更加复杂。2) 传统MAB问题中通常系统参数稳定，如某个动作的平均收益稳定，本文中节点的自由移动、信道环境变化，以及共享计算资源的变化，可能导致系统参数实时发生变化。

2 基于UCB的在线任务卸载算法

本文考虑任务本身的时延需求，在上节所述的2个挑战下，基于UCB(upper confidence bound)[13]提出在线任务卸载算法解决问题P1。首先提出TOD算法，适用于节点的参数稳定，处在稳定状态下的雾计算网络。由于帮助节点可共享的计算资源可能随着时间发生变化，节点的任务队列信息也可能会发生一系列改变，在这种情况下，节点处理单位任务的时延会相应发生变化。为应对和处理这些情况，将算法TOD进行扩展，为处在非稳定状态的雾计算网络提出TOD-N算法。值得注意的是，TOD算法与TOD-N算法并不对系统参数分布做出限制。

2.1 稳定网络状态下的任务卸载算法

算法1 稳定雾计算网络状态下基于在线学习的任务卸载算法TOD初始化:输入参数ζ,初始化t=1 WHILEUE有任务卸载请求 DO更新候选帮助节点集合H(t)IF ∀Hk∈H(t)是未选择过的帮助节点 THEN向Hk请求信息Xqk(t), Xek(t)初始化uek=Xek(t), Qk=Xqk(t), Nk(t)=1, Γak(t)=1ELSE∀Hk∈H(t),根据式(8)计算决策索引值u⌒k(t)选择节点ϕ(t)=argminHk∈Η(t)u⌒k(t)卸载Rt,收到反馈Xqϕ(t)(t)与Xeϕ(t)(t),卸载服务完成后收到返回结果∀Hk∈H(t),Nk(t)=Nk(t-1)+1,Γak(t)=Γak(t-1)+1t=t+1END IF END WHILE

(8)

(9)

(10)

(11)

2.2 非稳定网络状态下的任务卸载算法

(12)

(13)

(14)

(15)

(16)

TOD-N算法的伪代码如算法2所示。

算法2 非稳定网络状态下基于在线学习的任务卸载算法TOD-N初始化:输入参数: ζ, γ, Δmax,初始化t=0 WHILEUE有任务卸载请求 DO更新候选帮助节点集合H(t)IF∀Hk∈H(t)是未选择过的帮助节点 THEN向Hk请求初始信息Xqk(t),Xek(t)初始化uek(t,γ)=Xek(t),Qk(t,γ)=Xqk(t),Nnk(t,γ)=γ,Γnk(t,γ)=γELSE∀Hk∈H(t),据式(12)计算决策索引值u⌒nk(t,γ)选择节点ϕ(t)=argminHk∈Η(t)u⌒k(t,γ)卸载Rt,收到即时反馈Xqϕ(t)(t),Xeϕ(t)(t),卸载服务完成后收到返回结果∀Hk∈H(t),Γnk(t,γ)=Γnk(t-1,γ)γ+γ,∀Hk∈H(t),根据式(15)更新Nnk(t,γ)END IF END WHILE

3 算法性能分析

本节将对TOD算法、TOD-N算法进行性能分析，包括算法的最优近似情况、算法的计算复杂度以及内存占用情况。

(17)

3.1 算法的Regret分析

3.1.1 TOD算法的Regret分析

令Δmax=maxtΔt，则当φ=TOD时,有如下结论：

结论1若动态调整Δ+和Δ-，使得∀t，τ(Rt)=1，则

3.1.2 TOD-N算法的Regret分析

证明见附录B。

(18)

结论3当φ=TOD-N，存在常数C′,使得下式成立

(19)

证明见附录C。

3.2 算法复杂度及内存占用情况分析

(20)

(21)

(22)

4 仿真结果与分析

本节对TOD算法以及TOD-N算法进行性能仿真验证。主要考察采用所提出算法后的任务卸载的时延情况、任务卸载成功率以及算法的学习性能。

4.1 TOD算法仿真结果

图2 稳定网络状态下不同算法的任务卸载成功情况Fig.2 Task offloading success ratios for different algorithms under stationary status

图2中RR算法为轮询调度(round-robin)算法，轮流选择帮助节点进行任务卸载。Oracle算法表示理想算法，UE实时地对帮助节点处的排队情况、计算资源情况以及信道环境情况了如指掌，这在实际中是不现实的。当调节Δ+和Δ-使τ(Rt)始终为1的时候，TOD就变成TOD0算法，注意到此时相当于TOD0算法未考虑任务本身的时延需求。从图2可以看出，相比RL算法与TOD0算法，TOD算法能够有效地提升任务卸载的成功率，所达到的累计概率和Oracle算法十分接近，且随着任务卸载次数增加，卸载成功率也会越来越靠近理想状态下的任务卸载成功率。

图3所示为TOD算法在网络中有节点自由出入时的性能表现。时隙长度为20 ms。∀t，xt=x，图3中有两种输入任务大小，分别为x=0.5 Mbit和x=0.8 Mbit。∀k,rk=48 Mbit/s。仿真过程中有3个等长时段：T1，T2和T3，长度分别为5 s。节点在网络中的存在情况如表1所示，此时，ue，a和b分别为：ue=[0.08, 0.2, 0.2, 0.4, 0.5, 0.5, 0.7, 0.8]，a=[3.1, 1.6, 0.6, 0.4, 0.25, 0.007, 0.06, 0.015]，b=[2.9, 1.4, 0.4, 0.2, 0.15, 0.005, 0.05, 0.005]。

图3 TOD算法在稳定状态下的时延表现Fig.3 Average offloading delays under stationary status by TOD algorithm

表1 TOD算法候选帮助节点Table 1 Candidate help nodes by TOD algorithm

从图3可以看出，在网络动态变化后，TOD算法能快速找到新的最优帮助节点，且采用TOD算法的时延与理想算法的时延十分接近。进一步对比时段1与时段2发现，两种大小的任务平均时延差距变小，这是因为帮助节点的队列长度不同，因此当任务大小不同时，相应的最优节点可能不同。

4.2 TOD-N算法仿真结果

接下来检验算法在非稳定网络状态下的表现。仿真过程中共出现过6个帮助节点，各个帮助节点可提供的共享计算资源随时间改变，如图4(a)所示。时隙长度为20 ms。仿真过程可分为两个时段：T1和T2，长度各为5 s，各节点在各时段的存在情况如表2所示。∀t，xt=0.6 Mbit。参考文献[7]，任务的计算密度设置为330 Cycls/bit。∀k，∀t，Qk(t)(单位：Mbit)有：Qk(t)～U(0.25，0.35)，且Δt(单位：s)有：Δt/xt～U(1.3e-6,1.5e-6)，Δ+=6e-6，Δ-=0。此外，为了体现出算法对网络中节点计算资源的学习情况，需要尽量减少传输试验带来的影响，因此假设∀k,rk=72 Mbit/s。本节将TOD-N算法与Greedy算法和理想Oracle算法进行对比。Greedy算法每次决策时均选择目前的最优节点，Oracle算法则依然实时地对所有帮助节点的排队情况、计算资源情况等了如指掌。同时，为进一步分析γ参数对算法性能的影响，本节给出TOD-N算法在不同γ值下的性能表现。根据图4(a)，最优节点和次优节点不可分的时隙个数在T1和T2时段分别为1和2，根据式(18)可得，相应的参数γ分别为0.999 5和0.999 3。实验中另外给出的实验数据值分别为γ=1，0.999，0.99，0.9。TOD-N算法在非稳定网络状态下的性能表现如图4～图6所示。

图4 不同算法对网络中最优计算资源的追踪情况Fig.4 Learning performance on computing resource for different algorithms

图5 不同算法下的卸载时延及学习RegretFig.5 Average offloading delays and learning regrets for different algorithms

图6 非稳定网络状态下不同算法的任务卸载成功情况Fig.6 Task offloading success ratios for different algorithms under non-stationary status

表2 TOD-N算法候选帮助节点Table 2 Candidate help nodes by TOD-N algorithm

图4(b)为TOD-N算法对网络中计算资源的学习追踪与利用情况，结合图4(a)、4(b)可以看出，当γ=0.999 5和0.999 3时，TOD-N算法均能较好地追踪学习到最佳CPU资源，Greedy算法则无法做到。进一步地，可发现，当γ=1和0.999时，TOD-N总体表现比前两个值要逊色一些，但在某些局部时段里表现却要好一些。例如，在刚开始的一段时间里γ=1要比γ=0.999 3时性能好一些，在最后一段时间里γ=0.999要比γ=0.999 5稍微好一点。这是因为刚开始网络状态相对较稳定，因此γ选择大一些；在最后一段时间里，网络状态变化相对较快，因此γ选择可相对减小一些。以上结论与3.1.2节分析的结论一致。但当γ=0.99，甚至γ=0.9，TOD-N算法无法很好地适应非稳定网络状态，同时，图5(b)也同时表明，此时Regret增长很快，算法表现较差。这是因为γ值选择过小的话，算法基本丢掉了历史有用的数据信息，而过于依赖当前的数据。根据以上分析发现，参数γ的选择确实会对TOD-N算法性能造成影响，具体选择可参考式(18)。但是在实际情况中，很难提前知道网络情况，因此很难实时地对γ做出最优判断，但是如图4～图6所示，根据实验结果与分析，本文建议选用γ∈(0.99,1)，在这个范围内，均可有较为良好的结果，具体值可结合实际情况做出调整。

图5(a)表明，当合理选择γ，TOD-N在非稳定状态下可达到的时延和理想最优时延十分接近，可达5 ms以内，同时从图6可知，此时任务卸载成功率也明显比贪心算法高，且与最优成功率之差在1%以内。

5 总结

本文将动态雾计算网络中的任务卸载问题建模为具有动态动作空间的MAB问题，并为稳定状态雾网络提出基于在线学习的任务卸载算法TOD，该算法能够最优化平均卸载时延，并提高任务卸载成功率。再将TOD扩展到非稳定网络状态情况，提出TOD-N算法，TOD-N算法能动态追踪到网络中节点的计算资源。接着对TOD算法和TOD-N算法进行详细的性能分析。并同时对TOD-N中的参数γ进行一定讨论和实验。仿真结果验证了所提出算法的优异性能。未来将进一步考虑任务可拆分以及节点之间可协作的场景。

附录A

根据式(17)的定义，当φ=TOD，RTOD(T)可写作