基于服务更新的异构任务卸载方法

摘 要：边缘计算将存储和计算资源下沉到网络边缘，用户可将时延敏感型和计算密集型应用程序的任务卸载到边缘服务器执行，从而降低时延和能耗。已有的任务卸载研究通常忽略卸载任务的异构性，且默认边缘服务器缓存的服务能够长期满足用户的服务需求。然而，不同的任务需要不同的服务提供执行环境，且边缘服务器资源受限只能部署少量服务。因此，为了最小化时延和能耗（即成本），提出了一种联合服务更新和云边端协作的异构任务卸载方法。首先，通过改进的页面置换算法，预测出潜在的用户服务需求量，及时更新边缘服务器的服务。其次，在云边端协作基础上，通过改进的贪婪算法完成任务卸载，且使得成本最小。最后，基于真实数据集进行了充分的实验，实验结果表明，与对比方法相比，所提方法能够降低成本7%～16%。

关键词：边缘计算； 云边端协作； 服务更新； 改进的页面置换算法； 改进的贪婪算法

中图分类号：TP393 文献标志码：A

文章编号：1001-3695（2024）08-033-2481-08

doi：10.19734/j.issn.1001-3695.2023.12.0605

Heterogeneous task offloading method based on service update

Han Chaochen， Zhang Junna， Wang Xinxin， Yuan Peiyan， Zhao Xiaoyan， Liu Chunhong

（College of Computer & Information Engineering， Henan Normal University， Xinxiang Henan 453007， China）

Abstract：Edge computing brings storage and compute resources down to the edge of the network. Users can offload latency-sensitive and compute-intensive applications to the edge server for execution， thereby reducing latency and energy consumption. Existing task offload studies often fall short. The first point is that the existing research on task offloading often overlooks the heterogeneity of offloading tasks. The second point is that the default edge server caching service can meet the long-term service needs of users. However， different tasks require different services to provide execution environments. And the finite resources of edge servers can only deploy a small number of services. Therefore， to minimize latency and energy consumption（i.e.cost）， this article proposed a heterogeneous task offloading method that combined service updates and cloud edge collaboration. The method consisted two following main parts. The first part was an improved page replacement algorithm. The algorithm could predict the potential user service demand and updated the service of the edge server in time. The second part was the collaboration between the cloud-side ends， offloading tasks through collaboration and keeping minimum total costs. Finally， it conducted thorough experiments using real datasets. The experimental results show that the proposed method can reduce the total cost by 7% to 16% compared to the comparison methods.

Key words：edge computing; cloud edge collaboration; service update; improved page replacement algorithm; improved greedy algorithm

0 引言

随着通信技术的快速发展和万物互联时代的到来，推动了认知辅助、虚拟现实和增强现实等时延敏感型和计算密集型应用程序的发展，也使得智能移动设备的数量呈指数增长［1］。根据思科最新的《年度互联网报告》的分析和预测，2023年将有293亿台联网移动设备，预计至2030年将有5 000亿台［2］。然而，由于移动设备有限的电池容量、计算和存储资源，直接运行上述应用程序会产生较高的时延和能耗，使得用户体验极差［3］。边缘计算（edge computing，EC）通过在网络边缘部署边缘服务器（edge server，ES），为用户提供计算和存储资源。移动设备可将部分或全部任务卸载到ES处理，缓解移动设备在电池容量、计算和存储资源等方面的不足，从而提升用户体验。

近年来，许多研究人员针对任务卸载进行了研究。文献［4］研究了边缘计算中的单一类型任务卸载问题，为了提升用户体验，以最小化所有移动终端的时延和能耗为目标，提出了一种粒子群优化任务调度算法，获得了最优的任务卸载决策。Chu等人［5］针对物联网环境下的单一类型任务卸载问题，提出了一种基于深度学习的任务卸载算法，对每个用户的任务卸载比例进行动态微调，从而降低成本。然而，上述文献只考虑了单一类型卸载的任务，而没有考虑到卸载任务的异构性，即同一用户或不同用户在不同区域、不同时间内会产生不同类型的卸载任务。对于不同类型的卸载任务来说，需要不同类型的服务为其提供执行环境。也就是说，同一用户或者不同用户在不同区域、不同时间内的服务需求不同。因此，为了更好地满足用户的服务需求，本文综合考虑用户卸载任务的异构性，通过在ES缓存不同类型的服务，可以及时执行用户的卸载任务，从而提高用户的服务满意度。

Chen等人［6］认为ES可以满足用户所有的服务需求，针对动态边缘计算系统中的任务卸载调度问题，提出了一种在线动态任务卸载算法，通过权衡系统成本和队列稳定性来作出任务卸载决策，从而得到了最优任务卸载决策。文献［7］针对动态任务卸载问题，在ES缓存有大量流行度较高的服务场景下，以最大化任务完成率和最小化能耗为目标，提出了一种基于深度强化学习的动态任务卸载算法，可以根据复杂的环境调整并获得最优的任务卸载决策，提高用户体验。然而，上述文献只考虑到ES缓存了大量流行度较高的服务，而没有考虑用户的服务需求会发生改变，且忽略了ES是否具有充足的存储资源。现实生活中，由于用户的卸载任务具有异构性，即随着时间的推移和用户的移动，用户的服务需求处于动态变化之中；且ES的存储资源受限，仅能缓存部分服务，只能为部分卸载任务提供执行环境。所以，本文将时间划分为时间片，根据上一时间片内用户的服务偏好，在满足ES存储资源的约束下更新ES缓存的服务，保证ES缓存有流行度较高的服务，可以及时为卸载任务提供执行环境，从而促进EC的长期发展。

在默认ES具有无限资源的情形下，文献［8］研究了边缘计算中的服务缓存和任务卸载问题，考虑到任务请求的异构性，以最小化系统的平均时延为目标，提出了一种高效的协同服务缓存和任务卸载算法，获得了最优的服务缓存和任务卸载决策。Tian等人［9］研究了边缘计算中服务缓存问题，其认为ES资源不受限制，提出了一种分布式协作服务缓存方案。通过将服务缓存问题建模为马尔可夫决策过程，优化时延和提高命中率，从而提高服务质量并减轻核心网络的负担。然而，上述文献均认为ES的资源是无限的，而没有考虑到ES的计算资源是否足以执行用户的卸载任务。事实上，ES的计算资源是有限的，在满足ES服务约束的前提下，还需要考虑ES是否具有充足的计算资源。因此，本文通过ES之间的水平协作和计算节点（云服务器、边缘服务器和移动设备）之间的垂直协作，为用户的卸载任务分配到最佳的计算节点执行，可以充分利用ES的资源，同样，也可以保证用户所有卸载任务都能被成功执行，从而不仅可以提高用户服务满意度，也可以促进EC的长期发展。

综上所述，任务卸载的相关研究往往忽略卸载任务的异构性，没有考虑到用户的服务需求是动态变化的，且默认ES具有无限的资源。为了解决上述局限性，本文在ES服务缓存有限和资源受限的情况下，兼顾服务更新和云边端协作，研究了权衡时延和能耗（即成本）的异构任务卸载问题。由于该问题是NP-hard问题，无法直接在多项式中求解，所以本文提出了一种联合服务更新和协作任务卸载的方法（joint service update and collaborative task offloading，JSU-TO），来求解该问题的近似最优解。

本文的主要贡献包括以下四个方面：

a）考虑到卸载任务的异构性以及用户的服务偏好，根据服务的流行度提出了ILFU算法。根据提出的ILFU算法来比较上一时间片内服务的流行度，筛选出流行度较高的信息，在满足ES存储资源的约束下更新ES的服务，使ES缓存有多种类型且流行度较高的服务，从而可以执行更多卸载任务，降低任务执行成本。

b）在ES存储和计算资源受限的约束下，建立了云边端网络模型；通过ES之间的水平协作和云边端之间的垂直协作执行用户的卸载任务。不仅可以充分利用ES的资源，也可以保证用户所有卸载任务都能被成功执行，从而进一步提高用户服务满意度，促进EC的长期发展。

c）若一个任务可以卸载到多个ES执行，为了降低任务的执行时延和能耗，且充分利用ES的资源，利用IGA算法为用户选择当前服务部署下最佳的任务卸载决策，最小化任务执行成本。

d）基于真实数据集，对本文方法与已有的方法进行了充分的性能评估，实验结果表明，本文方法比对比方法在成本上减少了7%～16%。

1 系统建模和问题描述

1.1 云边端网络模型

本文建立的云边端网络模型如图1所示，模型由云服务器、ES和移动设备三种不同计算节点组成，三者形成协作域，均可执行用户的卸载任务。用户在运行单个应用程序时生成若干个不同的任务，每个任务需要特定的服务支持才能被成功执行。云服务器缓存有所有类型的服务，可以为所有卸载任务提供执行环境。ES因资源受限只能缓存少量服务，仅能执行部分卸载任务。ES无法执行的任务，可通过将任务转发到云服务器执行。用户的任务也可以在移动设备执行。图1虚线框内表示ES缓存的服务，颜色形状各不相同的图形表示不同的服务。

云服务器用C表示，云服务器的位置距离用户较远，意味着用户与云服务器之间会产生较大的传输时延和能耗。ES的集合用E={e1，e2，e3，…，eL}表示，L表示ES的数量。不同ES具有不同的通信能力、计算和存储资源，每个ES缓存有不同数量的服务。处于同一集群内的ES通过无线信道连接，彼此贡献缓存服务，形成共享资源池，通过水平协作执行卸载任务［10］。若ES没有缓存卸载任务所需的服务，或其计算资源不足以执行卸载任务，ES可通过有线网络将任务转发到云服务器，通过垂直协作执行［11］。

用户的集合用U={u1，u2，u3，…，un}表示，n为用户数量。用户随机分布，若用户处于多个ES的覆盖范围内，则用户可以通过移动或无线网络向ES卸载任务。

用户运行应用程序时生成I个不同的任务，所有用户产生卸载任务的集合用I={i1，i2，i3，…，iq}表示，q表示任务的数量。由于任务具有异构性，即同一用户或不同用户在不同区域、不同时间内会产生不同类型的卸载任务，所以，需要提供不同类型的服务支持，同样需要根据ES缓存的服务，卸载任务的特征以及ES的响应时间、工作负载、延迟和能耗等参数［12］，将用户的任务卸载到一个最佳的计算节点执行。且不同任务需要不同的服务支持，任务只能被卸载到缓存有与卸载任务对应服务的ES执行［13］，任务之间彼此独立，若计算节点资源允许，任务之间可以并行执行。

1.2 时延能耗模型

在本文的任务和时延能耗模型中，首先，所有用户可以并行执行运行程序，产生卸载任务，从而本文网络模型可以并行执行卸载任务。然后，在时延和能耗模型中具体对一个用户运行一个应用程序产生的任务进行分析，根据具体情况计算出任务的时延和能耗；所有用户运行应用程序产生的卸载任务被成功执行的过程都符合上述时延能耗分析过程。最后，计算出所有用户运行应用程序时产生的卸载任务的时延和能耗。具体分析过程如下：

用户的任务可选择在移动设备、卸载至ES或云服务器执行，因此讨论任务在三种不同计算节点产生的执行时延和能耗，以及任务在传输过程中产生的传输时延和能耗。

a）任务在移动设备执行

移动设备u具有一定的计算能力，可以执行卸载任务i，其中i∈I，此时产生的执行时延Tloci和执行能耗Eloci分别为

Tloci=Rifu，Eloci=PuTloci（1）

其中：Ri为任务i所需的计算量；fu为移动设备u的计算能力，受最大计算能力fmax的限制；Pu为移动设备u的计算功率。

b）任务卸载至ES执行

当任务i被卸载到ej执行时，需要考虑任务i上传到ej的传输时延和能耗，在ej的执行时延和能耗。与任务的上传数据量相比，返回任务结果的数据量较小，产生的返回时延和能耗也相对较小，因此，本文忽略返回时延和能耗。那么，任务i卸载至ej的传输时延TCeji和传输能耗ECeji分别为

TCeji=GiRej（2）

ECeji=PuTCeji（3）

其中：Gi表示任务i的输入数据量；Pu为移动设备u向ES上传的功率；Rej表示移动设备u至ES的传输速率，可通过香农公式［14］计算得到，即

Rej=Wi，ejlog2（1+Pi，ejHi，ejN）（4）

其中：Wi，ej为信道带宽；Pi，ej为移动设备的发射功率；Hi，ej为移动设备和ej的信道增益；N为数据传输时产生的信噪功率。同时，在ES执行时产生的执行时延TReji和执行能耗EReji分别为

TReji=Rifej（5）

EReji=PejTReji（6）

其中：Ri表示任务i所需的计算量；fej表示ej的计算能力；Pej为ES的计算功率。因此，任务i在ej执行时产生的总时延Teji和总能耗Eeji分别为

Teji=TCeji+TReji（7）

Eeji=ECeji+EReji（8）

若ej无法执行任务i，但是协作域中的ek可以执行，由ej将任务i转发到ek，通过ES之间的水平协作执行。此时产生的时延和能耗包括：任务i上传到ej的传输时延和能耗、ES之间的传输时延和能耗、在ek的执行时延和能耗，以及将任务结果反馈给用户的返回时延和能耗四部分。与任务的上传数据量相比，返回任务结果的数据量较小，产生的返回时延和能耗也相对较小，本文同样也忽略返回时延和能耗。因此，由ej将任务i转发到ek产生的传输时延TCej，eki和传输能耗ECej，eki分别为

TCej，eki=GiRej，ek（9）

ECej，eki=PtTCej，eki（10）

其中：Rej，ek表示ej到ek的传输速率，可由香农公式计算得到，Pt为ES之间的传输功率。

Rej，ek=Wej，eklog2（1+Pej，ekHej，ekN）（11）

其中：Wej，ek为ej和ek之间的信道带宽;Pej，ek为ej和ek之间的发射功率;Hej，ek为ej和ek之间的信道增益。在ek的执行时延TReki和执行能耗EReki分别为

TReki=Rifek（12）

EReki=PekTReki（13）

其中：fek表示ek的计算能力；Pek为ek的计算功率。

那么，任务i由ej转发到ek执行时产生的总时延Tiej，ek和总能耗Eiej，ek分别为

Tiej，ek=TCiej+TCiej，ek+TRiek（14）

Eej，eki=ECeji+ECej，eki+EReki（15）

综上所述，当任务i在ES执行时存在两种情形：a）用户处于ej的覆盖范围内，且ej可以执行任务i；b）用户处于ej的覆盖范围内，而ej无法执行任务i，需要将任务i转发给协作域中其他的ES，通过ES之间的水平协作执行。因此，本文用二进制变量γei（γei∈{0，1}）表示任务i在ES的执行方式。γei=1时，表示任务i可以在ej执行；γei=0时，表示任务i通过ES之间的协作执行。所以，任务i卸载到ES执行时产生的总时延和总能耗包括两部分，分别是在ej执行产生的总时延Teji和总能耗Eeji，及ES之间协作执行产生的总时延Tej，eki和总能耗Eej，eki。因此，在ES执行产生的总时延Tesi和总能耗Eesi分别为

Tesi=γeiTiej+（1-γei）Tiej，ek（16）

Eesi=γeiEeji+（1-γei）Eej，eki（17）

c）任务卸载至云服务器执行

当任务i被卸载到云服务器执行时，首先将任务i上传至附近的ES，再由ES通过有线信道转发给云服务器。当任务i需要转发至云服务器时，相对于ES到云的传输时延，ES转发任务前的等待时延相对较小可以忽略不计［15］。考虑到云服务器有着较强的计算能力，执行时延相对于传输时延来说可以忽略不计。因此，本文忽略在云服务器执行时产生的执行时延和能耗。当任务卸载到云服务器执行时，产生的时延和能耗主要包括：将任务i上传到ES的传输时延TCeji和传输能耗TCeji，及ES和云服务器之间转发任务和返回任务结果产生的往返时延和能耗。由于云服务器距离ES较远，ES和云服务器之间转发任务和返回任务结果的时延会产生相近的往返时延和能耗［16］，且产生的时延和能耗与任务大小无关［17］。因此，ES和云服务器之间产生的往返时延TCej，ci和往返能耗ECej，ci分别为

TCej，ci=2Tc，off（18）

ECej，ci=PcTCej，ci（19）

其中：Tc，off表示ES将任务i转发到云服务器产生的时延；Pc为ES和云服务器之间的传输功率。所以任务i卸载到云服务器执行时产生的总时延Tci和总能耗Tci分别为

Tci=TCeji+TCej，ci（20）

Eci=ECeji+ECej，ci（21）

本文采用二进制变量αi、βei、ηi表示任务的卸载决策，其中，αi、βei、ηi∈{0，1}。αi=1时表示任务i在本地执行，αi=0时表示任务i不在本地执行；βei=1表示任务i在ES执行，βei=0表示任务i不在ES执行；ηi=1表示任务i在云服务器执行，ηi=0表示任务i不在云服务器执行。由于任务i在ES执行时存在两种情形，所以用二进制变量γei（γei∈{0，1}）表示任务i在ES的执行方式。γei=1表示任务i可以在ej执行，γei=0表示任务i通过ES之间的协作执行。根据任务的卸载决策得出任务i的完成时延Ti为

Ti=αiTloci+βeiTesi+ηiTci（22）

在计算资源允许的情况下，用户产生的多个卸载任务可以同时执行。由于用户在运行应用程序时产生多个任务，应用程序的完成时间由最晚完成的任务来确定，从而可以得到应用程序的完成时延Tiu和完成能耗Eiu为

Tiu=maxi∈I{Ti}（23）

Eiu=∑i∈I{αiEloci+βeiEesi+ηiEci）（24）

因此，在该模型下所有用户运行应用程序产生的卸载任务的总完成时延T（τ）和总完成能耗T（τ）可以表示为

T（τ）=∑u∈UTiu（25）

E（τ）=∑u∈UEiu（26）

其中：本文分别用αi、βei、ηi表示任务的卸载情况，αi、βei、ηi∈{0，1}。当αi=1时表示任务i在本地执行，αi=0时表示任务i不在本地执行；βei=1表示任务i在ES执行；βei=0表示任务i不在ES执行；ηi=1表示任务i在云服务器执行；ηi=0表示任务i不在云服务器执行。

1.3 问题描述

本文的用户任务具有异构性，在ES服务和资源受限的约束下，研究权衡68d6b2b4355a1153379b60bcf948f3c1时延和能耗（即成本）的异构任务卸载问题。引入时延和能耗的权重参数ω（ω∈［0，1］），其取值由用户对时延和能耗的偏好程度确定［18］。如果用户对时延的需求超过能耗时，ω>0.5；反之ω<0.5。因此，根据式（25）（26），权衡时延和能耗的用户总成本可表示为

EC=ωT（τ）+（1-ω）E（τ）（27）

因此，本文研究问题可形式化为如下优化问题：

minαi、βei、γei EC

s.t. C1：∑Ii=1Xe，S·rS≤Rn

C2：αi+∑e∈Eβei+ηi=1 i∈I

C3：αi+∑e∈ESiβei+ηi=1i∈I

C4：∑Ii=1βei·Tesi·Ci≤Cm i∈I（28）

其中：C1表示服务受ES存储资源约束，Xe，S∈（0，1）表示服务是否放置在ES，rS表示服务所需的存储资源，ES的存储资源为Rn；C2表示每个任务只能在一个计算节点执行；C3表示任务被卸载到ES执行时服务的约束问题，即ES必须缓存有与卸载任务对应的服务；C4表示ES自身计算资源的约束，βei∈（0，1）表示任务是否卸载到ES上，ES的计算资源（CPU周期数）为Cm，任务每单位时间消耗Ci的CPU周期［19］。

文献［20］研究了边缘环境中异构任务卸载和ES资源受限的约束下，最小化时延问题，并证明了研究问题为NP-hard问题。与文献［20］研究的问题相比，本文在优化目标中加入了能耗问题，因此，本文研究的问题也属于NP-hard问题。

2 基于服务更新的任务卸载方法

为了求解本文研究的异构任务卸载问题，本章结合改进的贪婪算法（improved greedy algorithm，IGA）和改进的页面置换算法（improved least frequently used，ILFU），提出了一种JSU-TO方法来解决异构任务卸载问题。JSU-TO方法总体架构如图2所示，主要分为两部分。第一部分是在云边端协作的基础上，通过IGA为用户的卸载任务确定最佳的卸载位置（可以是移动设备、ES或者云服务器）。由于用户周围部署有多个ES，当任务选择在ES执行时，需要考虑ES是否缓存有与卸载任务对应的服务，以及是否具有充足的计算资源，才能挑选出满足条件的ES。然后，通过比较在三种不同计算节点执行产生的成本，为用户的卸载任务选择最佳的卸载位置。第二部分是通过ILFU算法更新ES的服务。根据时间片di内的任务卸载情况得到服务流行度信息，并收集时间片di内的服务信息和ES的信息。收集的信息包括服务的流行度Sd（i）和服务大小、ES的计算和存储能力等。根据收集到的服务信息筛选并保存流行度较高的服务Sd（i+1），并将其回送给ES并更新ES的服务，使得ES在时间片di+1内缓存有流行度较高的服务，供时间片di+1内执行卸载任务使用。

2.1 任务卸载算法

本文采用贪婪算法求解任务卸载决策。贪婪算法的基本思想是指在对问题进行求解时，寻求当前状态下的最优解。因此，贪婪算法求得的解可能不是全局最优解。为此，本文在贪婪算法中加入启发式信息和引入回溯机制，提出了一种改进的贪婪算法IGA，可以更灵活、更全面地求解问题的最优解，使算法更加智能化，从而提高算法的效率和准确性。

由于ES的计算资源受限，当任务卸载到ES执行时，需要挑选计算资源充足的ES执行用户的卸载任务。为了挑选满足条件的ES，在贪婪算法中加入启发式信息，即在贪婪算法中加入ES的计算资源约束。通过比较ES剩余的计算资源，判断ES的计算资源是否足以执行卸载任务，从而为用户的卸载任务选择计算资源充足的ES。ES的计算资源约束为

r（m）=r（m）-TesiCi（29）

ei（r）=ei∩{e|r（m）≥TesiCi，ei∈E}（30）

其中：ES剩余的计算资源用r（m）表示；Tesi表示任务在ES执行时产生的总时延；Ci表示任务单位时间消耗的CPU周期；ei（r）表示同时满足条件的ES集合。

由于云服务器、ES和移动设备都可以执行用户的卸载任务，为了充分利用三种计算节点的资源，在贪婪算法中引入回溯机制，即通过比较任务在不同计算节点执行时产生的成本，为用户的卸载任务选择成本最小的计算节点，从而确定最佳的卸载位置。在移动设备、ES和云服务器执行产生的成本分别用ECi，l、ECi，e、ECi，c表示。如下式所示。

ECi，l=ωTloci+（1-ω）Eloci（31）

ECi，e=ωTesi+（1-ω）Eesi（32）

ECi，c=ωTci+（1-ω）Eci（33）

其中：ω（ω∈［0，1］）表示时延和能耗的权重参数，其取值由用户对时延和能耗的偏好程度确定。

IGA的具体实现过程如算法1所示。首先，初始化ES的剩余计算资源和任务在不同计算节点的执行成本。然后，判断任务是否可以在ES执行，并判断ES是否具有充足的计算资源，将满足条件的ES保留至集合ei（r）中，用集合Resedge存放ek的计算资源。接着，从集合Resedge中挑选出计算资源充足的ES，并从集合ei（r）中找到对应的ES编号（第1～8行）。然后，计算任务在移动设备、ES和云服务器执行时产生的成本，即ECi，l、ECi，e、ECi，c，并比较任务在三种计算节点的执行成本，判断任务在哪个计算节点执行时产生的成本最小，选择成本最小的计算节点作为任务i最优的卸载位置。重复上述过程，直到所有任务均执行完毕（第9～18行）。其中，r（m）表示ES剩余的计算资源，Cm表示ES的计算资源。

算法1 IGA

输入：任务集合I;ES集合E。

输出：最优的任务卸载决策αi、βei、ηi，执行成本EC。

1 初始化ES的剩余计算资源r（m）=Cm

2 将EC、ECi，l、ECi，e、ECi，c初始化为0

3 for i=1 to I

4 for每个边缘服务器ek in E do

5 if判断任务是否可以在ek执行，then ei（r）←ek并将ek剩余的处理资源r（m）保存至集合Resedge

6 end if

7 挑选出计算资源充足的ES，并找到对应的编号

8&nbsp; end for

9 根据式（31）～（33）计算出ECi，l、ECi，e、ECi，c

10 筛选出成本最小的计算节点：

11 if ECi，l=min{ECi，l、ECi，e、ECi，c} then αi←1，保存ECi，n←ECi，l

12 else if ECi，e=min{ ECi，l、ECi，e、ECi，c} then βei←1，保存ECi，n ←ECi，e

13 else ηi←1，保存ECi，n ←ECi，c

14 end if

15 执行成本EC=EC+ECi，n

16 end for

17 输出每个任务的卸载决策αi、βei、ηi

18 输出最小的成本EC

2.2 服务更新算法

本文将时间划分为时间片，一个时间片表示一段时间，例如十分钟、一个小时、一天等。在不同时间片内，用户的服务需求会发生变化，从而影响服务流行度，应根据不同时间片内的服务流行度来更新ES的服务。服务流行度表示服务的受欢迎程度，服务的受欢迎程度越高，表示需要该服务提供执行环境的卸载任务越多。ES将服务信息上传到云服务器，云服务器根据服务流行度的高低更新ES的服务。

服务的集合用S={S1，S2，S3，…，Sv}表示，v表示服务的数量，表示一个时间片内与用户卸载任务对应的所有服务请求，rS表示每个服务所需的存储空间。本文将一个时间片划分为一天，那么时间片的集合用D={d1，d2，d3，…，dp}表示，其中p表示时间片的个数。在不同时间片内，服务流行度会发生变化，集合Sd（i）表示在时间片di内服务的流行度信息，集合Sd（i+1）表示在时间片di+1内ES要更新的服务。

虽然经典LFU算法可以用于更新ES的服务，但仍面临两个问题。第一，由于LFU算法只能比较ES已缓存服务的流行度，不能比较ES没有缓存服务的流行度，从而无法对所有服务的流行度进行对比。第二，若存在多个服务的流行度相同，且缓存所有流行度相同的服务将超出ES存储空间，经典LFU算法将无法准确更新ES的服务。为了解决上述两个问题，本文提出了一种改进的服务更新算法ILFU算法。

ILFU的算法思想为：收集时间片di内所有被成功执行的卸载任务信息以及对应的服务信息，并将服务信息放入集合Sd（i）中，同时，根据集合Sd（i）中的服务信息建立一个二元组Sd（i）=（CNTik，RTik）。其中，CNTik表示服务的请求次数，RTik表示服务的响应时间。通过比较相关的服务信息，比较所有服务的流行度。ILFU算法的具体实现过程如算法2所示。首先，根据服务的使用频率降序排列放入集合Sd（i+1）中。若存在两个服务的流行度相同，通过比较两者最后一次响应时间RTik来判断服务流行度的高低。根据时间局部性原理，最晚被请求的服务再次被请求的概率较大，将响应时间最晚的服务赋予较高的流行度，将流行度较高的服务放入集合Sd（i+1）中（第1～6行）。然后，计算Sd（i+1）中服务所需的存储资源，并判断集合Sd（i+1）中的服务是否满足ES的存储资源约束。在满足ES存储资源约束的条件下，更新集合Sd（i+1）中的服务。最后，集合Sd（i+1）中存放的服务就是时间片di+1内ES要更新的服务（第7～13行）。用rS表示服务所需的存储资源，ES的存储资源为Rn。

算法2 ILFU

输入：服务集合Sd（i）;服务信息Sd（i）=（CNTik，RTik）;ES的集合E。

输出：时间片di+1内ES要部署的服务集合。

1 为服务二元组编号S={S1，S2，S3，…，Sv}

2 for每个二元组中CNTik in Sd（i） do

3 将集合Sd（i）中服务使用频率降序排列并放入集合Sd（i+1）

4 if CNTik=CNTik+1 then RTik<RTik+1

5 将服务Sk+1放入集合Sd（i+1）

6 end if

7 for每个Si in Sd（i+1）

8 判断服务是否满足ES存储资源约束

9 if Rn-（Si·rs）>0 then将Si放入集合Sd（i+1）

10 end if

11 end for

12 end for

13 输出在时间片di+1内ES部署的服务集合

2.3 JSU-TO方法

本文方法可以为用户的卸载任务选择当前服务部署下最优的卸载决策，最小化任务的完成时延和能耗，从而降低用户成本。JSU-TO的具体实现过程如算法3所示。首先，根据ILFU算法得到时间片di+1内流行度较高的服务集合Sd（i+1），在满足ES存储资源约束的前提下更新ES的服务（第1～4行），在时间片di+1内ES缓存有流行度较高的服务。然后，对于时间片di+1内用户的每个卸载任务i∈I，通过IGA为任务选择当前服务部署下成本最小的计算节点，并选择最优的卸载决策。重复上述过程，直到所有任务均执行完毕（第5～16行）。其中，用r（m）表示ES剩余的计算资源，Cm表示ES的计算资源。

算法3 JSU-TO方法

输入：用户集合U;任务集合I;服务集合Sd（i+1）。

输出：最优的任务卸载决策αi、βei、ηi;执行成本EC。

1 for e=1 to E

2 根据ILFU算法得到时间片di+1内ES部署的服务集合Sd（i+1）

3 在满足ES存储资源的约束下更新ES的服务

4 end for

5 for u=1 to U

6 for i=1 to I

7 在当前ES的服务部署下

8 通过IGA筛选出成本最小的计算节点

9 并保存其卸载决策和执行成本

10 执行成本EC=EC + ECi，n

11 end for

12 end for

13 输出每个任务的卸载决策αi、βei、ηi

14 输出执行成本EC

2.4 时间复杂度分析

假设ES的数量为L，用户的数量为n，用户运行应用程序时生成的任务数量为q。算法3中的第1～4行调用算法2，根据ILFU算法得到时间片di+1内流行度较高的服务，在满足ES存储资源的约束下更新ES的服务，使得ES在时间片di+1内缓存有流行度较高的服务。其中，ILFU算法根据时间片di内的服务流行度信息，得到时间片di+1内流行度较高的服务，其时间复杂度为O（v×v′×L×（k-1））。因此，算法3中第1～4行的时间复杂度为O（v×v′×L2×（k-1））。算法3中的第5～14行调用算法1，通过IGA为用户的卸载任务选择成本最小的计算节点，从而为用户的卸载任务选择当前服务部署下最优的卸载决策。其中，IGA根据卸载任务选择计算资源充足的ES，然后选择执行成本最小的计算节点，其时间复杂度为O（n×q）。因此，算法3中第5～14行的时间复杂度为O（L×n×q）。综上所述，JSU-TO方法的时间复杂度为O（v×v′×L3×（k-1）×n×q）。

3 实验验证

3.1 实验设置

在云边端网络模型中，用户运行应用程序会产生不同类型的任务。本文使用谷歌数据集模拟用户产生的任务，谷歌数据集中每个任务都有详细的参数，包括任务特征和所需服务类型［21］。为了执行异构任务，需要不同类型的服务为其提供执行环境；为了得到最小成本，需要为用户选择最优的卸载决策。

本实验在一台计算机上运行，具体配置为：Intel CoreTM i5-7300HQ CPU@ 2.50 GHz， Windows 10 中文版64位，实验环境为Python 3.9.0。

3.2 对比方法

本文选择以下四种方法，与本文方法进行对比：

a）文献［22］提出的MMTO方法，其在车辆计算资源受限的约束下，优化卸载任务的执行时延和计算成本。根据本文的研究问题，在MMTO方法的优化目标中加入能耗，同时将其约束条件改为本文方法的约束条件。

b）文献［23］提出的OJTR方法，是在满足服务需求和资源的约束下，以最小化所有车辆总任务处理时延为目标。为了使OJTR方法能与本文方法作对比，在其优化目标中加入能耗。

c）文献［24］提出的GA，其目标是最小化任务的处理时延和能耗。将GA的约束条件修改为本文方法所提的约束条件。

d）经典的页面置换算法LFU，根据用户的服务偏好更新ES的服务，从而可以为更多卸载任务提供执行环境。

3.3 权重参数ω的影响

在本节实验中，设定实验环境中ES的数量为5，用户的数量为100，假设每个用户产生10个卸载任务，此时卸载任务的数量为1 000个。其中，ω取值为［0，1］，改变ω的取值，在本文方法下进行实验。从图3中可以看出，ω的取值与能耗成正比， 取值与时延成反比。也就是说，当ω<0.5时，意味着用户对能耗需求比较高，此时，计算节点可通过延长卸载任务的完成时间，从而降低计算节点的能耗；相反，当ω>0.5时，意味着用户更偏好时延，此时，通过增大计算节点之间的传输功率，可以降低任务的传输时延。为了验证本文方法既能满足用户对能耗的需求，也能满足时延偏好，实验中ω分别取值为0.2和0.8。

3.4 对比实验

1）用户数量对成本、时延和能耗的影响

边缘环境中用户数量对实验结果会产生影响，随着用户数量的增加，用户产生的卸载任务也增加，为了执行用户的卸载任务，ES要消耗更多的计算资源和带宽资源，从而会增加用户成本。为了找到某一特定边缘环境中最佳容纳用户的数量，本节通过变化用户数量，探究同一边缘环境中用户数量对任务时延、能耗和成本的影响，从而为该边缘环境确定最佳容纳用户的数量，使得用户成本最小化，提升用户体验。

设定实验环境中ES的数量为5，权重参数ω取值分别为0.2和0.8。变化用户的数量，采用五种方法分别进行实验，实验结果如图4和5所示。随着用户数量的增加，在五种方法下，时延、能耗和成本都逐渐上升。主要是因为随着用户数量的增加，用户产生的卸载任务数量增加。由于ES的服务和资源是有限的，只能为部分任务提供执行环境；ES无法执行的任务则需要转发到其他ES或云服务器执行，产生额外的传输时延和能耗，增加成本。本文方法首先通过ILFU算法，根据服务流行度更新ES的服务，使其缓存有流行度较高的服务，从而可以为更多卸载任务提供执行环境；然后通过IGA为卸载任务选择成本最小的计算节点，降低成本。与其他四种方法相比，本文方法总成本最小。通过观察可知，当用户数量小于160时，总成本增加的速度较慢。此时，既可以充分利用ES的资源，也可以及时执行用户的卸载任务，降低用户成本。当用户数量超过160时，该边缘环境不能为用户提供足够的资源。因此，该边缘环境中最佳容纳用户数量为160。

2）任务数据量大小对成本的影响

设定用户数量为160，产生的任务数量为1 600个，以每次增加5的规律，变化任务的数据量从5至30，采用五种方法分别进行实验，实验结果如图6所示。随着任务数据量的增大，ES处理任务的时延和能耗也会增大，且ES处理任务时所需的资源也在增加，因此，五种方法的成本也随之增加。

由于MMTO和OJTR方法都不考虑更新ES的服务，导致ES缓存的服务不能长期为用户的卸载任务提供执行环境。主要是因为随着时间的变化，相同用户会产生不同的卸载任务；由于用户的移动性，边缘环境中会出现不同的用户，不同用户会产生不同的卸载任务；不同卸载任务需要不同的服务提供执行环境，导致用户的服务需求发生改变。且随着任务的平均数据量增大，产生的传输时延和能耗也随之增加，从而产生较高的成本。与前两种方法不同，LFU算法通过更新ES的服务，使得ES缓存有较高流行度的服务，从而可以为更多卸载任务提供执行环境。但是LFU算法只能比较ES已缓存服务的流行度，不能比较用户新的服务请求，即ES没有缓存服务的流行度；若多个服务的流行度相同，且缓存所有流行度相同的服务将超出ES存储空间，LFU算法将无法准确更新ES的服务。此时，ES缓存的服务无法为任务选择最佳的卸载决策，从而产生较高的时延和能耗，增加成本。在GA方法中，随着数据量的增加，产生的成本逐渐增加。从图6中可以看到，相比于其他四种方法，本文方法可以为用户分配当前服务部署下最优的卸载决策，从而使得成本最小。

3）ES的存储和计算资源对成本和命中率的影响

边缘环境中ES的存储和计算资源大小对实验结果也会产生影响，当任务卸载到ES执行时会竞争ES有限的服务和资源。本节通过变化ES的存储和计算资源，探究ES存储和计算资源对成本和命中率的影响，从而为ES确定最佳的存储和计算资源。

设定用户任务数量为1 600个，变化ES的存储资源从5至30。ω分别取值为0.2和0.8，采用五种方法分别进行实验。图7中，随着ES存储资源的增加，成本逐渐降低。这是因为在ES数量和用户任务数量不变的情况下，随着ES存储资源的增加，ES可以缓存更多的服务，从而可以为更多卸载任务提供执行环境，使得转发到其他ES或者云服务器执行的任务减少，传输成本减少，进一步降低成本。同样，如图8所示，随着ES存储资源逐渐增加，ES缓存的服务较多，可以更好地满足用户的服务需求，提高命中率。

从图7和8可以看出，当ES存储资源增长到20，五种方法成本降低趋势减缓，命中率上升速率渐缓。在卸载任务数量不变的情况下，此时ES可以最大程度地降低成本，提高命中率。若继续增加ES的存储资源，既不会显著降低用户成本，也不能明显提高命中率。因此ES存储资源最佳设置应为20。

同样，设定用户任务数量为1 600个，变化ES的计算资源从20至120。ω分别取值为0.2和0.8，采用五种方法分别进行实验。在图9中，随着ES计算资源逐渐增加，成本逐渐降低。这是因为在ES数量和用户任务数量不变的情况下，随着ES计算资源的增加，在满足ES服务约束前提下，ES可以执行更多的卸载任务，使得转发到其他ES或者云服务器执行的任务减少，传输成本和用户成本降低。

同样，如图10所示，随着ES计算资源的增加，在ES满足服务约束的前提下，ES可以执行更多的卸载任务，从而提高命中率。从图9和10可以看出，当计算资源增长到80时，五种方法的成本降低趋势减缓，命中率上升速率变慢，此时ES可以最大程度地降低成本，提高命中率。若继续增加ES的计算资源，既不会明显降低用户的成本，也不会显著提高命中率。因此，ES的计算资源最佳设置应为80。从图7～10中可以看出，无论为ES配备多大的存储和计算资源，本文方法性能均为最优，都能为卸载任务选择当前服务部署下最佳的卸载决策，从而降低用户成本，提高命中率。

4 结束语

本文联合考虑服务更新和云边端协作，研究了在ES服务缓存和资源受限约束下，权衡时延和能耗的异构任务卸载问题，并提出了JSU-TO方法。JSU-TO通过ILFU算法，预测出潜在的用户服务需求量，及时更新ES的服务；在云边端协作的基础上，通过IGA为用户选择当前服务部署下最佳的卸载决策，完成任务卸载，且保持成本最小。实验结果表明，所提方法有效降低了用户成本。

虽然本文方法具有较好的效果，但还存在局限性：a）用户的移动性对服务的流行度也会产生影响，本文却忽略了这一点；b）本文没有考虑服务的放置。从网络运营商的角度考虑，服务的放置需要成本，如何解决服务的放置问题，使其不仅可以满足用户的服务需求，同时也可以最大化网络运营商的收益。因此，下一步的工作重点将尝试在服务更新过程中，根据用户的移动性来进行服务的更新，制定更优的服务更新策略，使网络运营商的收益达到最大化。

参考文献：

［1］Duan Sijing， Wang Dan， Ren Ju， et al. Distributed artificial intelligence empowered by end-edge-cloud computing： a survey［J］. IEEE Communications Surveys & Tutorials， 2022，25（1）：591-624.

［2］Koot M， Wijnhoven F. Usage impact on data center electricity needs： a system dynamic forecasting model［J］. Applied Energy， 2021，291：116798.

［3］Xiang Zhengzhe， Deng Shuiguang， Taheri j， et al. Dynamical service deployment and replacement in resource-constrained edges［J］. Mobile Networks and Applications， 2020， 25（2）： 674-689.

［4］Wei Zhe， Yu Xuebin，Zou Lei. Multi-resource computing offload stra-tegy for energy consumption optimization in mobile edge computing［J］. Processes， 2022，10（9）： 1762.

［5］Chu Xiao， Leng Ze. Multiuser computing offload algorithm based on mobile edge computing in the Internet of Things environment［J］. Wireless Communications and Mobile Computing， 2022， 2022： 1-9.

［6］Chen Ying， Zhao Fengjun， Lu Yanghuang， et al. Dynamic task offloading for mobile edge computing with hybrid energy supply［J］. Tsinghua Science and Technology， 2022， 28（3）： 421-432.

［7］Chen Ying， Gu Wei， Li Kaixin. Dynamic task offloading for Internet of Things in mobile edge computing via deep reinforcement learning［J/OL］. International Journal of Communication Systems. （2022-03-30）. https：//onlinelibrary.wiley.com/doi/abs/10.1002/dac.5154.

［8］Zhong Shijie， Guo Songtao， Yu Hongyan， et al. Cooperative service caching and computation offloading in multi-access edge computing［J］. Computer Networks， 2021， 189： 107916.

［9］Tian Hao， Xu Xiaolong， Lin Tingyu， et al. DIMA： distributed coop-erative microservice caching for Internet of Things in edge computing by deep reinforcement learning［J］. World Wide Web， 2022， 25（5）： 1769-1792.

［10］Liu Chenfeng， Bennis M， Debbah M， et al. Dynamic task offloading and resource allocation for ultra-reliable low-latency edge computing［J］. IEEE Trans on Communications， 2019， 67（6）： 4132-4150.

［11］Chen M H， Dong Min， Liang Ben. Resource sharing of a computing access point for multi-user mobile cloud offloading with delay constraints［J］. IEEE Trans on Mobile Computing， 2018，17（12）： 2868-2881.

［12］Zhang Xinglin， Li Zhenjiang， Lai Chang， et al. Joint edge server placement and service placement in mobile-edge computing［J］. IEEE Internet of Things Journal， 2021， 9（13）： 11261-11274.

［13］Almashhadani H A， Deng Xiaoheng， Abdul L S N， et al. An edge-computing based task-unloading technique with privacy protection for Internet of connected vehicles［J］. Wireless Personal Communications， 2022， 127（2）： 1787-1808.

［14］Cao Kun， Cui Yangguang， Liu Zhiquan， et al. Edge intelligent joint optimization for lifetime and latency in large-scale cyber-physical systems［J］. IEEE Internet of Things Journal， 2021， 9（22）： 22267-22279.

［15］Wang Changyu， Yu Weili， Zhu Fusheng， et al. UAV-aided multiuser mobile edge computing networks with energy harvesting［J］. Wireless Communications and Mobile Computing， 2022， 2022： 6723403.

［16］Xu Xiaolong， Fang Zijie， Qi Lianyong， et al. A deep reinforcement learning-based distributed service offloading method for edge computing empowered Internet of Vehicles［J］. Chinese Journal of Computers， 2021， 44（12）： 2382-2405.

［17］Singh P， Singh R. Energy-efficient delay-aware task offloading in fog-cloud computing system for IoT sensor applications［J］. Journal of Network and Systems Management， 2022， 30： 1-25.

［18］Ko S W， Kim S J， Jung H， et al. Computation offloading and service caching for mobile edge computing under personalized service prefe-rence［J］. IEEE Trans on Wireless Communications， 2022， 21（8）： 6568-6583.

［19］Zhang Junna， Chen Jiawei， Bao Xiang， et al. Dependent task offloading mechanism for cloud-edge-device collaboration［J］. Journal of Network and Computer Applications， 2023， 216： 103656.

［20］Liu Yu， Mao Yingling， Liu Zhenhua， et al. Joint task offloading and resource allocation in heterogeneous edge environments［C］//Proc of IEEE Conference on Computer Communications. Piscataway，NJ：IEEE Press， 2023.

［21］Reiss C， Tumanov A， Ganger G R， et al. Heterogeneity and dynamicity of clouds at scale： Google trace analysis［C］ //Proc of the 3rd ACM Symposium on Cloud Computing. New York： ACM Press， 2012： 1-13.

［22］Liu Lei， Zhao Ming， Yu Miao， et al. Mobility-aware multi-hop task offloading for autonomous driving in vehicular edge computing and networks［J］. IEEE Trans on Intelligent Transportation Systems， 2022， 24（2）： 2169-2182.

［23］ Fan Wenhao， Su Yi， Liu Jie， et al. Joint task offloading and resource allocation for vehicular edge computing based on V2I and V2V modes［J］. IEEE Trans on Intelligent Transportation Systems， 2023， 24（4）： 4277-4292.

［24］Chakraborty S， Mazumdar K. Sustainable task offloading decision using genetic algorithm in sensor mobile edge computing［J］. Journal of King Saud University-Computer and Information Sciences， 2022， 34（4）： 1552-1568.