Machine Learning based Timeliness-Guaranteed and Energy-Efficient Task Assignment in Edge Computing Systems

基于机器学习具有实时高效任务分配的边缘计算系统

摘要

物联网(IoT)和机器学习(ML)技术在边缘计算系统中的广泛应用，为智能认知助手(ICA)在工作、学习、交通、医疗保健和其他活动中为人们提供帮助铺平了道路。一个挑战是，如何根据延迟、能量和带宽消耗等几个考虑因素，在边缘计算系统(即远程云、雾和边缘设备)的三层之间调度应用程序任务。然而，由于复杂的计算阶段，针对这一挑战的最新方法也无法为关键的ICA任务提供实时时间表。在本文中，我们提出了一种基于强化学习的任务分配新方法——RILTA，它保证了ICA任务的实时性和高效率的执行。首先，我们考虑ICA应用中的时效性和能量消耗，提出了边缘计算系统中的任务调度问题。在此基础上，我们提出了一种方法来解决该问题，并根据该方法的输出设计了牢固的模型。仿真结果表明，与现有方法相比，RILTA可以在保证较高实时性的前提下，分别减少任务处理时间和能量消耗13 ~ 22%和1 ~ 10%。

INTRODUCTION

物联网(IoT)设备(如智能手机、可穿戴智能设备、传感器、自动驾驶汽车)和人工智能(AI)和机器学习(ML)技术的快速发展，为未来使用智能认知助手(ICA)应用来帮助人们工作、学习、交通、医疗保健等等铺平了道路。这些具有高适应性的ICA应用程序将增强人类的性能和生产力，从而为面对日常挑战提供有用的数字之手。亚马逊的Alexa、CMU的SARA(具有社会意识的机器人助手)、苹果的Siri等这类ICA应用的出现就证明了这一点。

在许多情况下，ICA需要实时帮助人们，有些甚至会产生生死攸关的后果，可能使其人类同伴处于危险之中。例如，家庭中的医疗物联网设备必须能够及时预测居民的心脏病发作，并紧急告知患者或其医生。一辆自动驾驶汽车必须能够检测到在它前面过马路的人，并实时决定停下来。同时，边缘计算系统对于实时或低延迟的ICA任务越来越重要。云计算在远程集中存储和处理终端用户的数据，由于数据传输和网络拥塞会产生一定的延迟。而边缘计算可以帮助处理来自物联网设备的数据，并提供实时的本地数据分析。它通过集中网络边缘的可用资源(如智能手机、平板电脑、智能汽车、基站和路由器)来提供更多用户感知、资源高效、可扩展和低延迟的[1]服务，从而使服务的提供更接近最终用户。苹果公司在2017年宣布，将在其高端iPhone[2]上安装机器学习加速器。根据该声明，高德纳公司预测，到2022年，80%的智能手机将配备人工智能。据预测，近50%的物联网数据将在[3]网络的附近或边缘被存储、处理、分析和作用。

尽管利用边缘计算来实现ICA的未来面临着许多挑战，但一个关键的挑战是实现有及时性保证和节能的边缘处理[4]。正如[4]所指出的，在最先进的边缘系统架构中仍然存在差距，由于缺乏及时性，无法解决ICA的信息交付过载。此外，物联网设备受限于有限的电力资源，而ICA任务可能涉及密集的计算和通信，这给实现低功耗边缘处理带来了巨大的挑战。在边缘计算领域，已经提出了几种任务分配方案，通过决定哪一层(远程云、雾和边缘设备)分配任务，以减少任务延迟和(或)能量消耗。这些方法根据其目标可分为两类:(1)能量感知任务分配[5-11]和 (2)带宽感知任务分配[12-16]。然而，这些方案涉及复杂的计算(例如，解决动态规划问题)，这使得它们无法为关键的ICA任务提供实时(或及时保证)的能源效率时间表。此外，同时考虑任务延迟和能量效率等多个目标的分配调度，使得计算更加复杂，在寻找分配调度时产生更高的延迟和能量消耗。

为了提供具有时效性和高能效的边缘处理，我们使用机器学习来解决ICA应用中的任务分配问题。首先考虑数据传输和任务计算的时效性和能量消耗，提出了ICA应用中的任务分配问题。然后我们提出一个启发式的解决方案，最后在所有可能的结果的基础上，依据数据的特征和计算环境我们设计一个基于强化学习(RL)的任务分配方法(称为RILTA)。其特征包括计算任务的紧迫性、数据量、数据传输时延、任务计算时延和任务的资源需求。基于这些特征，RILTA确定任务的分配位置(边缘、雾或云)，以确保实时性和电力效率的实时保证。我们在本文中的贡献如下:

• 根据ICA应用的要求，制定一个任务分配问题，解决截止日期意识和能源效率的问题。
• 为了解决已制定的任务分配问题，我们提出了一个启发式的解决方案，其中节点(边缘，雾或云)获得利润执行ICA应用程序。该利润方案保证了利润最高的节点负责保证不同优先级的任务在截止日期下高效地执行。
• 最后，我们提出了一个强化学习系统RILTA基于我们提出的启发式在模拟环境中产生的结果。RILTA利用了RL中多个agent对环境的自主学习，减少了任务本身的运行时间。

据我们所知，这是边缘计算平台上第一个使用基于RL的方法进行任务分配决策的方案，几乎是实时的，具有较高的能源效率。

本文的其余部分组织如下。第二节介绍了边缘计算中雾/云任务分配的相关工作。在第三节中，我们将任务分配制定成一个数学问题，重点关注ICA应用的特点。在第四部分，我们提出了基于区域的期限感知和能源效率解决启发式的公式问题和RILTA。第五节介绍了RILTA在模拟环境中与其他方法的实验评价。最后，第六部分给出了结论并对未来的工作进行了讨论。

RELATED WORK

近年来，随着物联网和基于移动的应用系统的发展，雾/云任务卸载受到了广泛关注。许多最先进的工作提出了不同的任务卸载方案，这些方案的目标各不相同，同时还减少了计算延迟。根据目标的不同，可以将之前的工作分为两类:(1)能量感知型任务分配[5-11]，(2)带宽感知型任务分配[12-16]。

A. Energy-aware Task Assignment

Chun等人，[5]提出了克隆云，将静态分析和动态分析相结合，从边缘设备上卸载部分应用程序，同时优化与边缘云环境中的计算和通信相关的执行时间和能源使用。克隆云在传入的应用程序上运行代码分析，然后根据预期的工作负载和执行条件(CPU速度、网络性能)决定将应用程序的执行结果卸载到云上。

类似地，Kao等人[6]提出了网络边缘设备之间的任务分配问题，并提供了基于在线学习的算法Hermes，在一定的成本保证下，寻找边缘设备能耗最小的最优策略，该策略定义为边缘云环境中执行和传输延迟的函数。

同样，在边缘云环境中，Wang et al.[8]和Munoz et al.[7]提出了适合于应用的方案，例如人脸检测，它运行在一组固定的图像上，预先知道处理的数据量，并且执行可以并行化成多个过程。在这些方案中，他们考虑将部分应用程序卸载到云上，目的是优化边缘设备的能源消耗能耗。

Sardellitti等人[9]研究了在多个设备上的应用程序卸载，这些设备具有多个输入输出系统，可以卸载到一个共享的云服务器上。卸载方案的目标是在边缘云场景下，在延迟和能量预算约束下，最大限度地减少边缘设备的能量消耗。

对于同一环境，Lyu等[10]从系统任务完成时间和能量减少的角度出发，提出了一种卸载到附近云服务器的决策方案，以最大化体验质量(quality of experience, QoE)。

此外，Dong等人在智能手机节能框架下开发了两种卸载算法，决定卸载任务的云服务器，共同优化在一定置信区间内的保证响应时间性能和能源效率。

虽然上述方法都试图减少任务延迟和(或)提高边缘设备的能量效率，但在计算任务分配调度本身涉及大量的计算，不适合实时性和能量效率要求的ICA任务。在本地计算和远程通信的能量消耗之间的平衡在[17-19]中讨论。

B. Bandwidth-aware Task Assignment

Messaoudi等人[12]提出了一种将计算任务从移动边缘卸载到雾节点的框架，其目标是最小化边缘雾场景中基于低延迟计算卸载的应用程序的总任务完成时间。在他们提出的决策机制中，联合考虑了估计往返时间(RTT)(衡量可用带宽)和边缘设备的能量消耗，以将任务转移到具有高CPU可用性的候选雾节点。他们的系统能够根据带宽的变化不断估计预期的RTT，以满足设备的决定，以卸载部分应用程序计算任务。

yang等[14]研究了从多个边缘设备和雾节点到云的任务优化任务卸载决策，考虑了可用带宽，以实现较高的处理速度或吞吐量。

Fan等人[13]提出了一种边缘雾云环境的卸载机制，根据位于不同环境级别、主要目标节点的传输延迟计算利润，以确保每项任务都在规定的期限内完成。在这种方法中，利润是给计算实体(边缘设备、雾节点或远程数据中心)的收入，用于在截止期限内执行任务，并且它们在其环境的不同层的可用网络带宽上定义了它们的传输延迟。然而，他们使用了基于信息素（pheromone）值的遗传算法（genetic algorithm ）来做分配决策，这不能确保实时找到解决方案。

Wang等人[15]提出了一种称为HealthEdge的任务调度方法，该方法根据收集到的人类健康状态数据，在边缘云环境中为不同的任务设置不同的处理优先级。在他们所提出的方法中，他们估计队列中的总等待时间和传输延迟作为当前网络可用带宽的函数，并试图按照任务优先级的顺序减少总处理时间。

Choudhari等人[16]提出了一种边缘雾环境下的任务调度算法，该算法根据任务的延迟容忍程度有效地对任务进行优先级排序，从而降低了平均响应时间和任务卸载的总成本。在这里，它们通过将传输的数据量除以分配阶段的可用带宽来定义数据传输的成本。

然而，这些方法没有同时考虑到任务的截止日期意识和边缘设备的有限能量。

TASK ASSIGNMENT STRATEGY FOR ICA APPLICATIONS（策略）

ICA运行智能应用程序，帮助人们在许多领域，如医疗保健和智能交通[4]。这些应用程序通常是上下文感知的，从某种意义上说，它们需要根据特定时刻从环境中收集到的信息做出相应的决策。通常，一个收集的数据项用于多个ICA应用程序的决策。例如，道路拥堵数据被多个ICA应用程序用于路线推荐、最优速度计算等。此外，数据还可以在一个应用程序中的多个任务之间共享。例如，在医疗服务中，呼吸频率异常的数据可以用来预测心脏病和哮喘的发作。对于这样的数据共享，在设备之间传输数据会产生大量的流量，增加数据传输带来的任务延迟和能量消耗。然而，根据决策过程，这些任务中的大多数都需要快速响应。针对这些问题，我们制定了一个有目标的任务分配问题，以保证及时性和资源利用率。我们提出的系统考虑了一个类似[13]的三层云雾边缘环境，包括客户端或边缘设备层、雾层和云层。我们认为除云层外的每一层都由多个设备组成，本文将这些设备称为节点。在本节中，我们在引入与传入任务相关的特征和问题公式所考虑的资源之后，使用广义分配问题[20]来提出我们的任务分配问题。在我们的方法中，我们假设系统知道:

1. 底层节点和上层节点之间的映射。也就是说，每个边缘节点都知道雾节点的列表，或者一个云数据中心，它可以在那里卸载任务。类似地，fog节点知道它们需要发送计算结果的边缘节点列表，等等。
2. 现有的网络在不同层次的节点之间存在延迟。这些知识可以通过部署监控雾节点、延迟和应用程序实例状态的软件来获得，正如[21]中建议的那样。

A. Task Characteristics（任务特征）

在三层edge-fog-cloud环境中，任务是由运行在底层边缘设备上的不同ICA应用程序生成的。这些任务中的大多数都有一个特定的截止日期，因为它们根据服务水平协议(SLA)为人们在某些决策制定中提供支持。每个任务都有以下特点:

1. 任务到达时间。
2. 任务的截止日期。
3. 数据的大小。数据大小是指每个边缘节点需要处理的数据量。它用于计算任务的计算和传输的估计时间和能量消耗。
4. 能源消费需求
5. 对要执行的任务的处理器的需求。

B. Resource Characteristics（资源特征）

在我们的任务分配系统中，我们只考虑三种类型的资源:处理器、网络带宽和电池寿命。每个节点跟踪其处理器，以决定是否可以利用其可用的处理资源执行任务。此外，节点估计执行或传输任务所需的能量，以使处理能量更有效。每个节点还会跟踪可用带宽和连接到雾或云的路径的可靠性。这些资源信息用于估计数据和任务的传输延迟。如果我们将一个节点到雾或云之间的网络链路的单个故障概率设为P_fail，那么在存在n个节点和链路的情况下，网络链路的可靠性(用R_net表示) R_net= 1 − P_failⁿ。

在我们的模型中，我们将从边缘节点到雾的路径划分为一个网络，将从雾到云的路径划分为另一个网络。这两个网络的路径可靠性分别用$R_F$和$R_C$表示。路径可靠性的概念有助于捕获网络中的任何类型的抖动和由于边缘设备的移动性而引入的任何噪声。

C. Task Assignment Problem（任务分配问题）

在本节中，我们将为ICA应用程序制定时效性保障和节能计算任务分配问题。根据引入的任务和资源的不同特性，我们制定了一个问题，决定一个任务是由边缘设备自己执行还是卸载到任何一个雾节点/云。

D. Task Assignment Model（任务分配模型）

Profits Estimation：回想一下，我们的任务分配系统考虑及时性保证和能源效率。根据这两个因素的重要性，系统可以分别给出以β和1−β表示的不同权重。其中β(0≤β≤1)表示为保证时效性而赋予节点的一个权重。一般来说，β控制延迟和能源效率之间的权衡。延迟和能源效率之间的权衡是基于这样一种假设，即边缘设备比雾节点和云数据中心有更多的能源约束。如果一个任务要在期限内执行，最好在边缘节点本身执行，这样可以避免传输延迟。然而，如果任务在边缘节点上执行，则会因为计算而需要消耗大量资源。而且，由于只有边缘节点受到能量（资源）的约束，我们定义一个参数n_type，n_type表示节点n是否受到能源等的限制，n是否为云或雾数据中心。如果n_type = 0，那么表示这个节点为云计算或雾计算数据中心，否则n_type = 1.因此，n_type 决定了在计算利润时要考虑1−β的因素。

如果任务t到达时间a(t)，期限为d(t)，那么根据估计的任务结束时间(T_end(t))，估计的n节点执行任务需要消耗的能量E(t, n)，任务开始时节点中存储的能量E_stored(n)，分配到节点n上的任务t的利润计算如下：

在这里，β是为了节点在尽可能早的时间内完成任务的赋予的因子。d(t) - T_end(t)表示任务t在截止日期之前完成的时间长度。时间长度越大，在时效保障方面越好。分母d(t)−a(t)表示允许完成任务t的总时间。比率（d(t) - T_end(t)） / (d(t)−a(t))是指节点n执行任务t的速度比它有限的允许持续时间快多少。E_stored(n) / E(t, n)表示一个执行任务t的节点n相对于节点存储的能量被消耗的能量。估计的能源消耗越低，那么它的energy efficiency就越高。并且，存储的能量E_stored(n)越高，为了不消耗节点的能量，energy efficiency也就越高。

T_end(t)估计时间取决于三个因素:任务t的到达时间a(t)，任务t的估计执行时间T_exe(t)与任务t的估计传输时间T_trans(t):

这里，${\tau }_c$为当前时间戳，而T_exe(t)和T_trans(t)分别表示任务t的估计执行时间和任务t来自或到达节点n的估计传输时间。

根据[13]，T_exe(t)可以通过以下方式进行计算，通过一个单元的计算资源处理一个单元数据的执行时间T_exe(1)和执行任务t的CPU需求c(t)，具体如下:

其中，D(t)表示t的数据集大小，赋值给任意一层的节点后，任务执行时需要传输t的数据集大小。

传输延迟的估计，T_trans(t)是任务本身及其关联数据集从任务产生节点传输到任务分配节点，并将计算结果从任务生成节点传输到任务分配节点所需要的往返时间。这个估计的时间取决于数据集大小、带宽和源节点和目标节点之间网络的路径可靠性，以及由网络[22]的路由器或交换机引起的相关传输路径延迟。我们将边缘节点和雾节点之间的网络带宽和可靠性分别考虑为$B_F$和$R_F$。此外，考虑到雾和云之间网络的带宽和可靠性，为$B_C$和$R_C$，我们采用[13]中的传输时延计算公式。

其中，边缘到雾、雾到云层的延迟分别用$T_F$和$T_D$表示。如果一个任务被分配给一个二级雾,它需要传输到雾节点，传输时间主要取决于数据D(t)的大小以及边缘节点和雾节点之间的网络带宽和可靠性$B_F$和$R_F$。此外，还考虑了路由器、交换机等网络设备引起的路径延迟($T_F$)。在三位一体的雾云环境中，任何边缘设备到云数据中心的路径都必须经过二级雾数据中心。因此，当n是云数据中心时，我们需要同时考虑从边缘节点到雾和从雾到云的路径延迟和数据传输延迟[13,23,24]。因此,当一个任务从边缘节点转移到云端,我们需要另外考虑传输时间在雾和云之间网络的带宽和可靠性，$B_C$和$R_C$，和额外的路径延迟($T_D$)引发的网络设备。

E_exe(t, n)只取决于两个因素:数据集的传输时间和任务的执行时间。

上式中E_trans(1)和E_exe(1)分别表示单位时间内传输的能耗和基于单位计算资源处理单位数据的能耗。

在式(1)中，我们将一个任务t分配给一个节点所获得的总利润最大化，这个利润应该反映我们的及时性保障和能效目标。第一部分确保分配的节点负责在截止日期前完成任务。比截止日期d(t)更大的T_end(t)最终会导致一个节点被赋予负利润，意味着对违反及时性保证的节点进行惩罚。通过d(t) - T_end(t)，节点会因为尽早完成任务而获得更高的利润。同理，在式(1)的第二部分中，我们保证能效越高的节点获得的利润越高。一个节点执行一个任务所消耗的能量n越低，t相对于它当前存储的能量来说，这意味着这些节点对于这个任务的能量效率越高。因此，E_stored(n) / E(t, n)可以确保节点n因为能量效率而获得更高的利润。

问题公式化

这项任务分配的目标是通过保证能源效率和及时性保证，使利润最大化。

PROPOSED PROBLEM SOLUTION

A. Profit based Assignment（利润分配）

考虑了基于地理区域的划分问题。在划分区域之后，集中式云使用建议的启发式从可能的集合状态和行动中进行利润估计，并使用强化学习生成一个集中式表。随后，这个表分布在边缘节点中，这些节点用于对传入的任务进行分配决策。作为构建RL模型的第一步，我们估计了一个传入任务的所有可能任务分配节点的利润。估计完成后，根据式(1)计算节点可以获得的利润，并将任务分配给利润最大的节点，可以是边缘节点本身，也可以是雾或云。我们认为这种基于利润的分配是任务分配问题的最优解。

B. Machine Learning based Task Assignment（基于机器学习的任务分配）

为了实现实时的任务分配决策，我们提出了基于RL的任务分配方法(RILTA)。我们以利润为奖励，利用Q-learning[25]构建RL模型。

后面先不看了，大概了解一下，这篇文章主要是希望能够同时考虑到及时性（任务能够及时完成）以及能源效率（该节点能够承载任务并快速执行），设计了一种任务分配方法。有三层结构，云数据中心，雾数据中心与边缘设备节点。为每个节点赋予利润值，再通过强化学习实时更新节点的利润值，将任务分配给利润最大的节点。