边缘计算中最大化服务价值的任务卸载算法*

王 恒 蒋大成 宋晓华

（西安工业大学电子信息工程学院 西安 710021）

1 引言

随着微电子和通信技术的不断发展，出现了大量新的应用，如基于人脸识别的智能门禁［1］、智能车辆网络［2］和虚拟现实［3］。这些应用程序通常是计算密集型的，并且对延迟敏感［4～5］。但物联网设备通常体积较小（如智能手机），这进一步导致设备的计算和通信能力有限。为了提高物联网系统的计算和通信能力，边缘计算作为一种新兴的计算架构来解决这一问题［6］，旨在网络边缘提供计算资源，为资源受限的物联网设备提供处理计算能力［7］。物联网任务首先上传到边缘网络，然后在边缘网络中进行处理。之后，结果将返回到相应的物联网设备［8］。通过将任务从资源受限的设备转移到功能强大的边缘设备上，可以减少系统整体延迟和能耗。因此，如何将边缘计算中的任务进行合理地卸载是一个关键问题。

针对边缘计算下的任务卸载，提出了HBTS算法，该算法更多的面向用户，以实现最大化服务价值为目标，从而有效地降低系统延迟和能耗。

2 系统模型

2.1 场景描述

本文研究了边缘计算中的任务卸载方案，该方案适用于高度集成的任务，这些任务必须作为一个整体卸载到边缘设备上。卸载场景如图1所示，其中网关任务队列中的一些等待任务如箭头所示，边缘设备由一个正方形来表示。每个任务由一个矩形表示，其模式表示不同的任务类型。此外，还有一个报头设备，它在有等待任务和可用边缘设备时执行卸载决策。当没有空闲的边缘设备时，为了确保高优先级任务具有优先执行权并有足够的计算性能，需要停止就近边缘设备上当前优先级较低的任务，将资源分配给优先级最高的任务。如果所有网关中的任务总数不超过边缘设备的数量，则每个任务可以获得一个执行机会。否则，每个边缘设备将被分配一个任务，其余任务必须等待即将空闲的设备，这将触发新一轮决策。否则，每个边缘设备将被分配一个任务，其余任务必须等待即将空闲的设备，这将触发新一轮决策。

图1 二进制卸载场景

2.2 边缘计算系统模型

边缘计算系统的模型图如图2所示。每个网关负责从与其相连的物联网传感器或终端设备收集数据。物联网设备通常具有较低的计算能力［9～10］，因此主要负责数据收集和预处理。通过这些数据，网关可以根据传感器或终端设备的要求启动计算任务。每个网关都设置一个任务队列，用来缓存在等待中的任务。然后，网关将任务卸载到分布式协作的边缘设备组中，其中有一个负责管理资源的报头，如果有可用的边缘设备并且任何网关的任务队列都不为空，报头就会执行一个卸载方案。

图2 边缘计算系统模型

2.3 服务价值定义

针对二进制的任务卸载，设计了面向用户的最大化服务价值的评价指标来说明用户获得的量化的价值与性能（延迟或能耗）之间的关系。

服务价值是最终用户获得的总价值的总和，通过应用程序的实际性能（如响应时间或能耗）进行评估。本文提出了一个价值函数来表示价值和性能之间的联系，可以表示为

其中，p，Pe和Pa分别表示价值的数值、应用性能和动态性能参数。Pa反映了用户获得的价值和应用程序性能之间的时间变化关系。

式（1）定义了服务价值的一般模型，将其应用于实际应用时，值函数可以实现应用程序的主要特性，包括给用户带来的功能收益和性能指标。对于本文研究的边缘计算系统，重点研究任务完成延迟和设备能耗的性能。

2.4 问题定义

使用D，G和T表示所有网关上的边缘设备、网关和任务的数量。所有边缘设备和网关的集合由D={1，2，3，…，d}和G={1，2，3，…g}表示。网关g中的任务集合表示为T={1，2，3，…，t}。使用pt(S)表示任务t的价值函数，其中S是总任务延迟并且t∈T。同样，设备d的价值函数表示为pd(E)，其中E是执行给定任务边缘设备的能量损耗。

任务t到边缘设备d分配所获得的总价值是相应的任务值和设备值之和，可以表示为

任务和边缘设备之间的分配关系可以用一个D×T的顺序矩阵X。二进制变量x(d，t)表示元素是否位于第d行和第t列，表示任务是否分配给边缘设备d。x(d，t)=1表示任务t将被卸载到边缘设备d中，x(d，t)=0则相反。如果有多余的边缘设备，也就是当T＜D时，将会有D-T个边缘设备无需分配任何任务，因此无需卸载导致的能耗。根据价值函数的定义，一个边缘设备d无需能耗即可获得最大值pmax(d)，其中d∈D~，D~表示未分配任务的边缘设备集合。相反，如果任务数量超过边缘设备数量，即T＞D，将会有T-D个未分配的任务，由于完成时间的不确定性而无法获得价值。服务价值是所有任务和边缘设备的总价值之和，表示为

在式（3）的右项中，第一部分是已分配任务和设备的值总和，第二部分是未分配任何任务的空闲边缘设备获得的总值。

综上，针对边缘计算中的任务卸载问题可以形式化表示为

式中，约束（4）表示x(d，t)是一个二进制变量。约束条件（5）和（6）意味着给定的任务不能卸载到多个设备上，给定的设备最多只能分别分配一个任务。约束（7）确保方案能够充分利用可用设备来完成等待任务。如果有足够的边缘设备，每个任务都可以获得执行的机会。否则，每个设备都应该加载一个任务，剩下的任务必须等待更多空闲设备。

3 HBTS算法

针对边缘计算系统中的任务卸载问题，提出了一种启发式算法，即HBTS算法。该算法可以在多项式时间内找到问题P的局部最优解，从一个随机初始化开始，并重复进行一个本地操作，即传输操作和交换操作，如果它们可以提高目标值ν(x)。转移操作则将未分配任务或边缘设备的任务重新分配，交换操作改变了两个任务或者两个边缘设备之间以前的分配，因此它们都可以满足P的条件约束，该算法的伪代码如下：

转移操作的流程图如图3所示，首先将HBTS算法的卸载策略进行保存，如果任务数量大于边缘设备数量，将所有未被分配的任务检索出来，由于任务未被分配，此时的二进制变量为0，再对所有未被分配的任务进行遍历，将其二进制变量置为1，如果可以提高平均服务价值，则更新卸载策略，再将二进制变量置为0。如果任务数量小于边缘设备数量，将所有未被分配任务的边缘设备检索出来，由于边缘设备上未被分配任务，此时的二进制变量为0，再对所有未被分配任务的边缘设备进行遍历，将其二进制变量置为1，如果可以提高目标值ν(x)，则更新卸载策略，再将二进制变量置为0，最终输出最新的卸载策略X′。

图3 转移操作流程图

交换操作的流程图如图4所示，首先将HBTS算法的卸载策略进行保存，如果任务数量大于等于边缘设备数量，遍历所有任务，交换两个边缘设备上原有的分配，如果可以提高平均服务价值，则进行交换，更新卸载策略。如果任务数量小于边缘设备数量，遍历所有的边缘设备，将部署在两个边缘设备上原有的任务进行交换，如果可以提高平均服务价值，则进行交换，更新卸载策略，最终输出最新的卸载策略X′。

图4 交换操作流程图

4 实验和评估

4.1 实验设置

实验使用Matlab平台实现，为了简化模拟，假设有10种类型的任务。同一类型的任务在任务值函数中有相同的最大值和最小值，它们是从集合{0.1，0.2，…，1.0}中随机抽样的［11］。每种类型也分配了不同的正态分布，以确定单个任务的大小。每个任务都有其特定的硬阈值和软阈值［12］，它们在(，)范围内均匀采样，和分别是所有可用边缘设备中任务的最短和最长可能完成时间。类似地，对于每个设备的值函数，最大值和最小值也从集合{0.1，0.2，…，1.0}中随机选择。每个边缘设备值函数在（，）范围内均匀分布。其中和，是设备在等待处理的所有任务中可能消耗的最低和最高能量。每个网关的任务队列中的任务数是一个均匀分布在［1，5］内的随机正整数值［13］。每个任务从10种任务类型中随机选择，然后根据与其类型相关的正态分布分配大小。此外，让所有任务的处理密度都为Ct=737.5cycle/bit，t∈T。

将本文提出的HBTS算法的性能与以下算法进行比较。

穷举法（Exhaustion）［14］：这是一种蛮力方法，通过穷举搜索所有可能的决策来找到最优卸载方案；由于其计算复杂度非常高，因此该方法仅适用于小型网络环境。

贪心算法（Greedy）［15～16］：如果D≥T，所有任务都被排序成一个随机序列，然后每个任务按顺序被贪婪地分配一个目标设备，该设备可以在所有可用设备上最大限度地提高操作系统的性能。如果D＜T，因为每个设备都可以被分配一个任务，所以首先随机地对设备进行排序，然后轮流贪婪地为每个设备选择任务，这样就可以在所有未分配的任务中最大程度地提高服务价值。

随机算法（Random）［17］：所有任务按随机顺序排序，然后从所有可用设备中随机选择一个设备，直到分配完所有任务或没有可用设备为止。

考虑到实际边缘计算环境的随机性，比较了4种算法在500个随机生成的环境设置下的统计性能，包括平均服务价值、平均运行时间、性能方差。性能方差定义为给定方法的解与穷举法的解之比的方差，用来衡量最优解的稳定性。

4.2 实验结果

4.2.1 HBTS算法与主流算法的对比

为了表示本文提出的算法的较优性，将其性能与其他3个算法进行了比较。由于穷举法搜索所有可能的解，其运行时间非常长。因此，测试了一个小规模环境，包括D=8和G=3智能网关。图5（a）、（b）、（c）分别显示了服务的平均值、性能差异和平均运行时间。可以看出，所提出的HBTS算法比最优穷举算法的性能更好，并且在平均服务价值和性能方差显示的解的稳定性方面显著优于其他基线。HBTS算法的平均运行时间也低于其他算法，证明了该算法具有较高的效率。

图5 算法对比

4.2.2 边缘设备数量的影响

根据边缘计算系统中可用的不同数量的边缘设备来评估服务价值，如图6（a）、（b）所示。将空闲边缘设备的数量从2变为10，并比较平均服务价值和性能差异。网关G的数量设置为3，每个网关中等待任务的数量从1到5进行统一采样，这意味着总任务的数量T在［3，15］的范围内变化。从图6可以看出，所提出的HBTS算法带来了最优的解决方案，可以提供最大的服务价值，性能方差显示了最高的稳定性。此外，平均服务价值随着服务器数量的增加而显著增加。这是因为随着边缘设备数量的增加，有着更大的解决方案空间，因此改进解决方案的可能性更高。

图6 边缘设备数量的影响

4.2.3 任务数量的影响

根据等待任务的数量来评估平均服务价值性能。如图7（a）、（b）显示了任务数从2增加到11时的平均服务价值和性能差异。对于每个生成的环境设置，将可用边缘设备的数量固定为8，将网关的数量固定为5，其中给定数量的任务是随机分布的。可以看出，本文提出的HBTS算法可以得到最优的服务价值且方差最低的解，并且平均服务价值随着任务数的增加而增加。

图7 任务数量的影响

5 结语

为了使边缘计算网络中各种应用程序可以更好地给用户带来实际价值，提出了服务价值作为性能指标，主要包括延迟和能耗，并建立边缘计算系统的模型，针对边缘计算的任务卸载问题，提出了HBTS算法，该算法旨在最大化服务价值，仿真结果表明，与其他主流算法相比，本文提出的HBTS算法可以实现最大化服务价值，效率显著提高。