基于云边协同多任务计算卸载策略

钟云峰，宋伟宁

(东华理工大学 信息工程学院，江西 南昌 330013)

0 引 言

近年来，随着互联网、无线接入技术和智能终端技术的发展，极大推动了物联网(Internet of Things，IoT)产业的发展。物联网垂直应用领域的研究也在快速推进，产生了许多的应用场景[1]。随着工业4.0、“中国制造2025”的提出，工业互联网成为解决智能工厂中许多问题的主要方案[2]。作为云计算的拓展和补充，边缘计算受到越来越多人的重视[3]。针对由于云计算采用集中式计算造成的网络拥塞以及传输时延较大的问题，边缘计算采用了分布式计算方式，由分布在网络中的多个服务器接受用户的计算任务，从而降低设备上传数据至云服务器的需求，减小了网络拥塞[4]。边缘计算是工业互联中的关键技术，云计算和边缘计算优势互补，共同促进整个工业IT和OT的深度融合。

目前大多数研究针对的都是移动边缘计算，计算卸载技术解决了用户等待时延高和电池电量快速消耗的问题。叶桓宇[5]利用边缘计算(Edge Computing，EC)和软件定义网络(Software Defined Networks，SDN)的技术特点，提出了一种新型SDIN架构，并在该架构的基础上，设计实现多QoS的优先级队列计算卸载算法。Liu Juan等人[6]根据建立的模型，使用马尔可夫决策过程对每个任务的平均能耗和平均时延进行分析，并提出了一种有效的一维搜索算法，以找到最佳的任务调度策略，降低了任务时延。Mao Y等人[7]提出了一种基于Lyapunov优化的动态计算卸载(LODCO)算法，有效降低了时延。还有Jia M、Kao Y H[8-9]也提出了以优化时延为目标的在线任务卸载算法。以上是以优化时延为目标的，还有以权衡时延和能耗为目标的研究。例如，代美玲等人[10]以最小化任务时延和设备能耗为目标，把问题描述为资源约束下的最小化能耗和时延加权和的凸优化问题，提出基于乘子法的计算卸载与资源分配解决该问题。孟陈融[11]提出了权衡时延和能耗的任务卸载模型，设计了一种启发式算法来解决该问题，有效降低了任务的时延和设备的能耗。Nan Y、Wang W、Liu L Q[12-14]等人也提出了能耗和时延的权衡优化的卸载方案。周鹏等人[15]提出了一种工业物联网中计算任务跨域卸载模型，将资源分配与计算卸载分为两个子问题，分别得出两个子问题的最优解，最终就是整个优化问题的最优解。

以上大多数研究都是针对移动边缘计算的，在工厂中大多数设备都是有线供电，移动边缘计算的模型和卸载策略不适用。该文设计了一种基于云边协同的工业互联网环境下多任务计算卸载模型和以优化时延为目标的计算卸载策略。首先融合边缘云与远端云构建了一种面向多终端的网络架构，依此建立系统模型；在此模型基础上，构造了以优化卸载时延的目标函数；最后，设计求解算法，求出最优解，合理实施计算卸载。

1 系统模型及问题描述

1.1 系统模型

基于云边协同的计算卸载框架如图1所示，由一个远端的云计算中心、多个近处的边缘服务器以及多个工厂中的终端设备组成。在工厂中的边缘服务器不一定只有一个，可以根据终端设备数量或者任务请求量来划分出几个区域，在每个区域放置一个边缘服务器。远端云服务中心与边缘服务中心、边缘服务中心与终端设备分别存在着一对多的映射关系，边缘服务器通过互联网接入云服务中心，终端设备通过有线网或者无线网接入到边缘服务器。终端设备把要执行的任务信息发送到边缘服务器，包括任务需要上传的数据量大小、需要的CPU时钟周期数、任务的返回数据量大小等信息，服务器根据任务信息和边缘服务器的资源信息来作出决策，下发至终端。

图1 基于云边协同的计算卸载框架

1.2 时延模型

采用边缘计算的目的就是为了任务能够快速响应，所以能耗优化不是该文考虑的方面，系统优化的目标是时延。系统时延由计算时延和通信时延组成，计算时延有本地计算时延、边缘计算时延、云端计算时延；通信时延有数据上传传输时延和结果返回传输时延。由于一般回传的数据量相对较小，所以该文不考虑结果回传时延。

1.3 终端计算模型

假设一个区域内有N个终端设备，表示为N=[1,2,…,n]，其中每个终端都有M个任务需要执行，表示为M=[1,2,…,m]。每个计算任务定义为元组Ai,j=(Di,j,Wi,j,Ri,j)(i∈N,j∈M)，Di,j表示当前任务的数据量，Wi,j表示当前计算任务所需要的CPU时钟周期数，Ri,j表示响应数据大小。任务在终端设备上执行的时延为计算时延tlocal，可表示为：

(1)

1.4 边缘计算模型

任务卸载到边缘服务器的时延有数据上传时延、计算时延、等待时延，所以任务在边缘服务器上执行的时延tedge可表示为：

(2)

其中，twait为基于排队论的等待时延预测[16]。

根据排队论的Little法则，在平衡条件下，任务在服务器等待的平均时间为系统的平均等待队长除以任务的平均进入率，即：

(3)

在时长为t的时间段内，等待的任务数为Nt-S，随着时间的增加，计算平均等待队长为：

(4)

其中，Nt为t时刻的全部任务数，S为边缘服务器同时服务的最大任务数。同时得到任务平均进入率。

(5)

其中，N0为决策开始时系统内的任务数。由此，可以得到排队等待时间的预测值。

1.5 云端计算模型

任务卸载到云服务中心的时延有数据上传时延和计算时延，所以任务在云服务器上执行的时延tcloud可表示为：

(6)

1.6 问题描述

一个任务Ai,j有可能在本地执行或者卸载到边缘服务器、云服务器，设xi,j为1表示在本地执行，xi,j为0表示卸载执行；yi,j为0表示没有卸载到边缘服务器，yi,j为1表示卸载到边缘服务器；zi,j为0表示没有卸载到云服务器，zi,j为1表示卸载到云服务器。所以任务Ai,j的执行时延ti,j可表示为：

(7)

优化的目标是总时延最小即：

(8)

约束条件为：

xi,j+yi,j+zi,j=1，xi,j,yi,j,zi,j∈0,1

(9)

变量标识如表1所示。

表1 变量标识

续表1

2 卸载策略

根据上面描述，问题变成了一个01整数规划问题，只需要求得最优解然后按照最优解进行任务卸载。求解01规划的方法有很多，一般的有分支定界法、枚举法和模拟退火法，当M和N比较大时分支定界法和枚举法会出现收敛速度慢的问题。所以该文选取了混合整数线性规划算法来求解上述问题，混合整数线性规划算法具有求解速度快且是精确解的优点。

混合整数线性规划算法求解步骤：

01整数规划是特殊的整数规划，这类问题被分类为NP困难问题。混合整数线性规划算法使用此基本策略来求解混合整数线性规划。混合整数线性规划算法可以在任一阶段完成问题的求解。如果它在某个阶段成功求解了问题，算法不会执行后面的阶段。

(1)使用线性规划预处理缩减问题的规模。预处理步骤旨在消除冗余变量和约束，改善模型的尺度和约束矩阵的稀疏性，加强变量的边界，检测模型的原始和对偶不可行性。

(2)使用线性规划求解初始松弛(非整数)问题。

(3)执行混合整数规划预处理以收紧混合整数问题的LP松弛。混合整数规划预处理的主要目标是简化后续的分支定界计算。预处理包括快速预检查和消除一些无用的子问题候选项，以免分支定界算法对其进行分析。

(4)尝试切割生成以进一步收紧混合整数问题的LP松弛。

(5)尝试使用启发式方法求得整数可行解。

(6)使用分支定界算法系统地搜索最优解。

最后根据求解出来的最优解来执行卸载策略。

3 仿真结果与分析

为了验证云边协同多任务计算卸载策略的有效性，首先比较文中方法与局部卸载方法的差异，即任务只在本地或者边缘服务器执行，不卸载到云服务中心；再将文中的卸载时延策略与最小时延能耗策略[10]进行比较；然后研究在用上述两种方法求解的情况下，计算任务总时延和任务数量的关系；最后比较模拟退火算法和混合整数线性规划算法在计算任务的总时延和算法执行时间方面的差异。

仿真实验在Matlab环境下进行，系统的各个仿真参数如表2所示。表2中给出了任务数据量大小、任务所需要的CPU时钟周期数、终端设备的计算能力、边缘服务器的计算能力、云服务器的计算能力、终端到边缘服务器的传输速率、边缘服务器到云服务器的传输速率。

表2 系统的仿真参数设置

首先，通过设置不同的任务数量，来比较不同卸载策略完成任务的总时延。计算任务总时延与任务数量的关系如图2所示。图2比较了云边协同多任务计算卸载策略(文中方法)与局部卸载方法完成任务的总时延，从图中可以看出文中方法优于局部卸载方法，相比局部卸载方法时延降低了4%。所以在实际的部署中，将边缘服务器与云服务器联动起来能够有效地降低任务时延，提高服务质量。

图2 不同卸载策略下任务完成时间的比较

再将文中卸载策略与最小时延和能耗卸载策略进行比较，比较结果如图3所示。从图3可以看出，与最小时延和能耗的卸载策略相比，文中的最小时延卸载策略完成任务的时延更低，时延降低了10%。在时延要求很高的情况下，不考虑能耗的卸载策略能够更好地降低时延。

图4为不同任务数量下文中策略分配任务的情况。从图中可以看到任务会卸载到不同的位置，卸载策略会根据任务的数据量大小、计算量大小等信息将任务卸载到最适合的位置来减小时延。随着任务数量的增加，边缘设备的压力会增加，所以会有更多的任务卸载到云端和设备终端。

图3 不同卸载策略下任务完成时间的比较

图4 任务卸载位置分配

模拟退火算法与混合整数线性规划算法的比较如图5所示。从图5可以看出，两种算法中时延都随着任务数量的增加而增加。混合整数线性规划算法在不同任务数量下的性能都优于模拟退火算法，这是因为混合整数线性规划算法能够求解出01整数规划的最优解，而模拟退火算法作为启发式算法，不一定能够求出最优解。

图5 模拟退火算法与混合整数线性规划算法的比较

当设备数量增加时，假设每台设备有10个任务，比较模拟退火算法与混合整数线性规划算法的算法执行时间，如表3所示。从表3可以看出，模拟退火算法的执行时间随着设备数量的增多而增加，随着设备规模的增加，混合整数线性规划算法的算法执行时间基本没太大的增加。因此，仿真结果表明混合整数线性规划算法明显优于模拟退火算法。

表3 模拟退火算法与混合整数线性规划

4 结束语

研究了基于云边协同的多任务计算卸载问题，设计了基于云边协同的计算卸载框架；基于此系统模型，以最小化任务时延为目标，设计了一种多任务计算卸载方法。针对现实中任务排队时延计算问题，采用了一种基于排队论的等待时延预测方法。针对根据系统模型建立的01整数规划问题，提出了混合整数线性规划算法的解法。仿真结果表明，与局部卸载方法和最小时延和能耗卸载方法相比，提出的基于云边协同的计算卸载方法在时延上有所优化，在算法执行时间上也有很大的提升。