非稳态雾赋能网络中的在线任务卸载方法*

2020-09-17朱兆伟刘婷钱骅罗喜良

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

朱兆伟，刘婷，钱骅，罗喜良

(1 中国科学院上海微系统与信息技术研究所，上海 200050； 2 中国科学院大学，北京 100049；3 上海科技大学，上海 201210； 4 中国科学院上海高等研究院，上海 201210)

随着物联网的快速发展，各类移动智能设备需要处理的任务量不断提高。比如，应用增强现实技术的在线交互游戏设备需要大量计算和通信资源。因此，传统的个人电脑、智能手机等移动设备和物联网设备在电池和计算能力方面面临巨大的挑战。一个经典的解决方案是将这些任务卸载到能源、存储和计算资源丰富的云端服务器[1]，但是远距离云端传输将会带来额外的通信时间。为了满足低时延的服务要求，研究人员提出利用雾计算节点(如具有闲置可用资源的移动、物联网设备)数量庞大、无处不在的天然优势，将计算、存储、控制和通信服务分布在云到雾的连续体中。因此，为了更好地利用周围的雾节点，急需一个高效的算法，来决定在雾计算网络中哪些计算任务需要卸载以及应卸载到哪个节点。

一般来说，把高复杂度的计算任务卸载到其他的节点上能够有效地节约本地节点的计算资源与能量资源。在一些文献中，任务卸载被建模为确定性优化问题，例如，Dinh等[2]研究的能量和延迟的联合最小化，以及You等[3]研究的延迟约束下的能耗最小化。然而，一个实用的任务卸载策略需要依赖于用户和服务器的实时状态，例如，计算队列的长度等信息。从这个方面来说，因计算队列长度的不确定性，任务卸载是典型的随机规划问题，传统的基于确定性参数的优化方法并不适用。为了解决这个问题，在文献[4-7]中，研究人员调用李雅普诺夫(Lyapunov)优化方法，将具有挑战性的随机规划问题转换为顺序决策问题，其中包括每个时隙中的一系列确定性问题。此外，Chen[8]提出一种基于博弈论的分布式解决方案，每个用户可以自主地进行卸载决策。

上述文献中提出的任务卸载方案都假定可以获得关于系统参数的全部信息。但是，在实际系统中，存在参数在用户处未知或部分已知的情况。例如，一些特定的值可能只能作为后验信息，当特定节点被访问时才能获得。Chen和Giannakis[9]将每个任务的通信延迟和计算延迟视为后验信息。Tekin和Van Der Schaar[10]假设每个用户的移动性是不可预测的。在实际系统中，可用资源通常是有限的，从而导致每次决策可访问的节点数量非常有限。此时，若以最小化长期开销为目标，所做出的决策就必须平衡“探索”与“开发”之间的权重。一方面，为了减小眼前的开销，决策应偏向尽可能 “开发”经验最佳节点；另一方面，从长远角度考虑，用户需要“探索”其他节点以找到潜在的性能更优的节点。为了平衡这种关系，一种流行的方法是将“探索”与“开发”困境建模为多臂老虎机(MAB，multi-armed bandit)[11-13]问题。这一理论模型在统计学中受到广泛关注[13]。

在雾计算网络任务卸载的研究中，很少有先前的工作研究这种探索与开发权衡的关系，本文将详细探讨这个问题。首先，假设每个任务的准确的处理时延在任务处理之前是未知的。基于此，尝试基于有限的反馈提出一种高效的任务卸载算法，从而最小化用户长期时延。因此，引入一个非稳态多臂老虎机模型以捕捉随机且未知的时延变动。相比于以往如文献[2-7]中的确定性模型，该随机模型更加符合实际模型。之后，基于置信上界(UCB, upper-confidence bound)策略提出一种高效的任务卸载算法。由于该算法不是直接的UCB策略的应用，因此传统的理论分析无法直接适用。针对这一改进版的UCB算法，将从理论层面给出算法的性能保证。

1 系统模型

1.1 网络模型

考虑一个雾赋能的网络(参见图1)，其中雾节点按照其功能可分为任务节点和辅助节点两类。每个雾节点都有可能产生计算任务，也可以与附近的节点通信。假定每个节点未完成的任务被缓存在各自节点的先入先出(FIFO, first-input-first-output)队列中。由于单一节点内的计算和存储资源有限，在本地处理的任务通常会经历较高延迟，这会降低服务质量(QoS,quality of service)和体验质量(QoE, quality of experience)。为了实现低延迟处理，一个任务节点可以将其一些计算任务卸载到附近的辅助节点。这些辅助节点通常拥有更多的计算和存储资源，并且可以按需部署以帮助其他任务节点。在诸如在线游戏等典型应用中，任务通常是周期性地生成的，并且不能任意拆分。因此，假设每个节点在每个时隙t的开始生成一个任务t，该任务可以作为一个整体由本地节点计算或者分配给一个相邻的辅助节点。

图1 雾赋能网络的拓扑结构图Fig.1 Topography of a fog-enabled network

(1)

在本文中，假设任务节点不能将任务卸载到正在与其他节点通信的辅助节点。还假设每个任务都是独立生成的，且任务节点之间不合作。

用T(i)表示传输每一比特信息到节点i所需要的时间，它是一个依赖于距离的值，并且可以在传输前进行测量。在这里，假设不同任务节点占用预先分配的正交时间或频谱资源与辅助节点通信，如TDMA或FDMA。任务t的数据长度用Lt表示，假设任务大小传输延迟LtT(i)不超过一个时隙。在本地处理的任务传输延迟为零，即LtT(K)=0。

用Qt(i)表示节点i在时隙t开始时的任务队列长度。同时，Wt(i)表示节点i处理每一比特队列中的任务所需的时间，Pt(i)表示节点i处理任务t中每一比特所需的时间。在本文中，变量Wt(i)和Pt(i)被定义为随机变量，它们的数学期望分别为

(2)

假设每个任务的总时延主要由上述时延构成，即传输时延LtT(i)、队列中的等待时延Qt(i)Wt(i)以及处理时延LtPt(i)。传输计算结果等反馈信息所需要的时延在本文中不考虑。根据上述定义，将任务t分配给节点i处理所需的时延可以定义为

(3)

在进一步分析问题之前，给出下列假设：

· 假设1：时延Ut(i)在任务t处理完之前是未知的；

· 假设2：队列长度Qt(i)在每个时隙t开始时由节点i广播至各个雾计算节点；

与文献[2-7]中基于已知系统参数的模型的任务卸载问题不同，我们在假设1和假设3中对CPU频率等系统参数与处理延迟之间的关系没有任何限制，文献[9]中也体现出这一思想。这是更加实际的设置，原因如下。首先，任务的复杂度等变量应该被建模为一系列独立的随机变量。这是因为计算本身的不确定性，而且它们的分布可能会由于任务类型的变化而发生突变(1)例如，移动用户在使用不同应用程序时，任务类型、任务复杂度等参数会发生改变。。另外，节点的计算能力，例如每个节点所分配用于计算的CPU频率、CPU内核数目、内存大小等都有差异，而且也可能会发生突变。上面提到的所有这些不确定性使得系统难以预测单一节点处理不同任务的时延。而且，单个节点获取系统的全局节点的信息会花费大量通信开销。在传统模型中，如Mao等[5]假设时延简单地由任务数据长度和配置的CPU频率决定，然而在实际系统中，单个任务节点很难像传统模型那样准确地估计计算时延和等待时延。

式中：It表示处理任务t的节点的编号；1{·}为指示函数，当花括号内条件满足时，该函数取值为1，否则为0。

1.2 问题建模

一般的长期平均时延最小化问题可以被建模成如下形式：

(4)

解决上述问题有两个困难。首先，它是一个随机规划问题。在第t个任务完成之前，无法得到时延Ut(i)的确切信息。另外，即使Ut(i)为已知的先验信息，这个问题仍然是组合优化问题，复杂度为(KT)量级。这是因为先前的卸载决策确定了每个雾节点中的队列长度，并进一步影响未来任务的决策。有关示例，请参阅文献[10]。为使任务卸载策略具备在线更新、动态调整的能力，一种流行的方法是在每个时间段将这个具有挑战性的随机和组合优化问题转换为一个低复杂度的顺序决策问题[2-7]。基于在之前的(t-1)个时隙中做出的任务卸载决策，最优策略变为将任务t卸载到t时刻能够获得最低时延的节点。同时，在随机问题的框架下[12]，关注随机变量的期望是更自然的做法，即[Ut(i)]。因此，表达式(4)中的问题在第t个时隙中变成以下问题：

(5)

2 高效的任务卸载策略

2.1 基于SW-UCB的任务卸载

按照前面的假设，任务节点在每个时隙开始时产生一个任务。令τs≤s+τmax为收到第s个任务反馈的时间，其中τmax是最大容许时延。如果任务时延超过最大容许时延，即τs>s+τmax，该任务视为失败并被丢弃。根据文献[14]，随机变量Wt(i)和Pt(i)的估计值可以由历史观测值的滑动窗口平均值得到，即

(6)

式中τ>0表示滑动窗口的长度，以及

(7)

那么，时延Ut(i)就可以被估计为

(8)

注意到式(8)中的延迟是根据Ws(i)和Ps(i)的历史信息估算的，而不是之前的延迟值，即Us(i),s

(9)

我们用UCB算法来权衡探索和开发之间的关系。从本质上来说，这种折中关系由探索奖励ct(τ,i)来衡量，即探索节点i会有额外的奖励。在本文中，令

(10)

(11)

本文算法的具体流程见算法1。

算法1 TOS(task offloading with sliding-window-UCB)任务卸载算法

步骤2) 令It=t，卸载任务t至节点It；

步骤3)t=t+1；

步骤4) 若t>K，转至步骤5)；否则跳转至步骤2)；

步骤7) 根据式(11)做出决策It，卸载任务t至节点It；

步骤8)t=t+1；

步骤9) 若t>T，算法结束；否则跳转至步骤5)。

由算法1可知，本文算法的复杂度主要集中于步骤5)。若直接按照式(6)、式(7)执行步骤5)，则该步骤复杂度为(Kτ)。因此，在执行每一次任务卸载时，决策复杂度为(Kτ)。若步骤5)采取增量更新的方式，只关注最新移入或移出窗口的部分，每次决策的复杂度可进一步降低为(K)。根据假设2，为保障算法运行，每个节点广播其队列长度。因此，对于算法本身来说，功耗主要集中于广播队列长度以及执行决策的功耗。此外，任务卸载本身还包含实际卸载任务的功耗(任务节点承担)以及实际执行任务的功耗(按需部分由辅助节点承担)。

虽然上面提出的任务卸载模型本质上是一个非稳态的MAB模型，但与文献[14]中提出的传统模型相比，存在两个主要差异。首先，在传统模型中，决策的反馈是即时获得的。而在我们的模型中，如式(6)所示，在任务完成之前，即τs≤t时，反馈是无法得到的。而相应的延迟是无法忽略的，因为它恰好是我们需要的信息。值得注意的是，延迟的反馈会影响算法性能，这一现象被Joulani等指出并在文献[15]中分析。其次，常规的非稳态MAB模型[14]假设最好的节点只在断点处改变。但是，我们的模型允许最佳节点在不同时刻、处理不同任务时发生变化。因此，目前已有的SW-UCB算法的性能保证不能直接应用于我们提出的TOS。

2.2 理论分析

(12)

其中

证明见附录。显然，该上界取决于总任务数T、断点数ΥT以及窗长τ的选择。从式(12)中，可以看出第1项(TB(τ)lnτ)/τ随着τ增加而减少。另一方面，后面两项，即ΥT(τ+τmax)和(2(lnτ)2+2lnτ)/ln(1+η)，随着τ增加而增加。这种折中关系与我们的直觉一致，即更高的窗口长度τ有助于在稳定情况下更好地估计，但同时导致对环境突然变化的缓慢反应。因此，在式(12)中的不同项之间存在权衡。为了在稳定和突然变化的环境之间取得平衡，类似于文献[14]，将τ定义为

(13)

相应地，有以下推论。

推论2当ΥT=(Tβ),β∈[0,1)，以及T→∞时，期望的数量级为

为了证明所提出的算法的最优性，定义卸载前T个任务的伪后悔度为

(14)

关于ζT，有如下推论。

推论3当ΥT=(Tβ),β∈[0,1)时，算法1中的算法是渐进最优的，即

(15)

根据推论1和推论2，有

ζT=

那么对于任意ε>0，存在一个有限整数Nε，使得

因此，

推论3说明，在条件ΥT=(Tβ),β∈[0,1)下，当T→∞时，该算法的后悔度以概率为1趋近于零。由知，该算法线性收敛。

3 仿真实验

在这一章节中，通过仿真104次任务卸载来验证本文提出的算法。每次任务卸载时，任务节点产生一个任务。以下是各个场景中共同的仿真参数设定。

· 该雾赋能的网络包含1个任务节点和9个辅助节点；

· 每个时隙长度为20 ms。任务数据长度服从Unif(1,15)KB；

· 最大允许时延为τmax=20时隙，参数ξ=0.6；

· 每一比特任务的处理时延按照公式Pt(i)=

将算法TOS的性能与两个基本的策略(贪婪算法和轮询算法)、以及我们之前提出的基于折扣因子的在线任务卸载算法[16]，即TOD(task offloading with discounted-UCB)算法，进行比较(2)注意到本文的核心问题在于，当任务卸载的代价需通过在线学习获得时，如何权衡“探索”和“开发”之间的折中关系。因此，其他预知代价的算法，如文献[5-8]中提到的李雅普诺夫(Lyapunov)优化方法，在本文中难以直接适用。。在贪婪算法中，假设任务节点已知任务卸载相关随机变量的每一个样本值，并在每个时隙将任务卸载给时延最小的节点。值得注意的是，虽然贪婪算法代表每一时刻所能做出的最优决策，但该贪婪算法不是因果的，现实中不能实现。此外，由于当前时刻决策与下一时刻状态相互耦合，每一时刻的最优决策联合起来并不一定代表问题(4)的最优解。在轮询算法中，每个任务以循环的方式依次分配给各个雾节点。在TOD算法中，基于D-UCB框架，利用折扣因子γ应对非稳态环境。据我们所知，TOD算法为符合本文场景的最新算法。

在图2中，通过仿真不同的断点数目，TOS算法的有效性和稳定性得到证明。算法性能通过仿真中各个任务的时延的累积分布函数(CDF, cumulative distribution function)来体现。图中，TOD算法的折扣因子γ和TOS算法的滑动窗口长度τ各自按照其理论公式计算得到。图2中的两个场景都证明TOS算法的性能远远优于轮询算法，接近于贪婪算法，并且略微优于TOD算法。在图2(a)中，当断点数目ΥT设置成150时，平均每67个任务就会有一次系统参数的突变。这暗示着TOS算法能够快速学习并适应频繁的系统变化，并且适应能力在一定程度上优于TOD算法。同样值得注意的是，从图2(b)可以看出，当系统变化次数非常有限(ΥT=10)时，TOS甚至表现出比贪婪算法更小的平均时延。这一现象揭示每个时隙的最优决策组合起来并不一定是全局最优这一事实。同时，这也佐证了我们之前的分析，即节点的每一时刻的决策都会影响系统后续的状态，进而影响后续的决策。

图3 不同算法的平均后悔度曲线Fig.3 Average regret curves for different algorithms

4 结束语

本文研究雾赋能的网络中一种高效的在线任务卸载策略以及相应的性能保证。考虑到节点处理速度的期望可能在未知时刻发生突变，并且相关系统参数信息仅在完成相应任务之后才获得这一场景，将任务卸载问题建模成带有延迟老虎机反馈的随机优化问题。为解决这个问题，基于UCB算法提供一个高效的在线任务卸载方案，即TOS。给定特定数量的断点ΥT，证明卸载到非最佳节点的任务数量的上界是此外，还证明，当任务数量趋近于无穷大时，伪后悔度以概率为1趋近于零。数值仿真证明，所提出的TOS算法能够在非稳态环境中学习并选择正确的节点以卸载任务，且表现优于TOD算法。

附录

证明首先，根据定义做如下事件分解：