具有边缘缓存机制的混合启发式任务卸载算法_桑永宣.pdf

第 49卷 第 4期2023年 4月Computer Engineering 计算机工程具有边缘缓存机制的混合启发式任务卸载算法桑永宣1，魏江坡1，王博1，宋莹2（1.郑州轻工业大学 软件学院，郑州 450001；2.北京信息科技大学 计算机学院，北京 100101）摘要：边缘计算因其与用户物理距离短、响应速度快等特点，被认为是可以解决未来大规模网络计算资源不足等问题的关键技术之一。在多进多出的边缘计算环境下，通过将部分服务缓存到边缘节点可以降低用户请求任务的执行时间。但以往工作或假设边缘节点具有无限的缓存空间，或忽略当前缓存列表和缓存替换机制对任务卸载的影响，导致卸载决策失效或任务执行时间变长。面向具有缓存机制的边缘计算环境，提出一种基于整数编码的混合启发式任务卸载算法 IPSO_GA，将任务卸载问题建模为一个混合整数非线性规划问题。结合粒子群优化和遗传算法，使各粒子通过交配运算和变异运算不断寻优，在合理的时间复杂度内搜索任务卸载决策。实验结果表明，与随机算法、贪心算法、平均算法等经典算法和目前较新算法相比，IPSO_GA算法在设备数量居中环境中的任务执行时间减少了 58%298%，能适用于设备数量多、计算密集的边缘计算环境。关键词：边缘计算；任务卸载；边缘缓存；粒子群优化算法；遗传算法开放科学（资源服务）标志码（OSID）：中文引用格式：桑永宣，魏江坡，王博，等.具有边缘缓存机制的混合启发式任务卸载算法 J.计算机工程，2023，49（4）：149-158.英文引用格式：SANG Y X，WEI J P，WANG B，et al.Hybrid heuristic task offloading algorithm with edge caching mechanism J.Computer Engineering，2023，49（4）：149-158.Hybrid Heuristic Task Offloading Algorithm with Edge Caching MechanismSANG Yongxuan1，WEI Jiangpo1，WANG Bo1，SONG Ying2（1.College of Software Engineering，Zhengzhou University of Light Industry，Zhengzhou 450001，China；2.Computer School，Beijing Information Science and Technology University，Beijing 100101，China）【Abstract】Edge computing is considered one of the key technologies that can solve the problem of insufficient computing resources in large-scale networks in the future due to its short physical distance from users and fast response speed.In the multi-in multi-out edge computing environment，some services can be cached at the edge nodes to reduce the execution time of user-requested tasks.However，previous studies assumed that the edge nodes have infinite cache space or ignored the fact that the current cache list and cache replacement mechanism impact task offloading.This may invalidate the offloading decision and delay the execution of tasks.Therefore，a hybrid heuristic algorithm called IPSO_GA based on integer coding is proposed for the edge computing environment with the caching mechanism.The task offloading problem is modeled as a mixed-integer nonlinear programming problem.Combined with particle swarm optimization and Genetic Algorithm（GA），each particle constantly searches for an optimal solution through mating and variational operations，which can search for task offloading decisions within a reasonable time complexity.Experimental results show that the IPSO_GA algorithm reduces task execution time by approximately 58%to 298%compared with classical algorithms such as the Random algorithm，Greedy algorithm，Even algorithm，and the current newer algorithms，and can be applied to edge computing environments with a large number of devices and intensive computation.【Key words】edge computing；task offloading；edge caching；particle swarm optimization；Genetic Algorithm（GA）DOI：10.19678/j.issn.1000-3428.00647830概述物联网（Internet of Things，IOT）将人、进程、数据和事物彼此连接到网络，目前已风靡全球1。思科年度互联网在报告中预测，到 2023年底，连接到 IP网络的设备数量将是全球人口的 3倍多，人均网络设备将基金项目：国家自然科学基金面上项目（61872043）；河南省重点研发与推广专项（科技攻关）（232102211084）；河南省高等学校重点科研项目（21A520050）。作者简介：桑永宣（1982），女，副教授、博士，主研方向为云计算、网络空间安全；魏江坡，硕士研究生；王博、讲师、博士；宋莹（通信作者），副教授、博士。收稿日期：2022-05-23 修回日期：2022-07-15 Email：先进计算与数据处理文章编号：1000-3428（2023）04-0149-10 文献标志码：A 中图分类号：TP3912023年 4月 15日Computer Engineering 计算机工程从2018年的2.4台增加到3.6台，网络设备将从2018年的184亿台增加到293亿台2。与此同时，人工智能3、虚拟现实4、无人驾驶5等技术也得到了快速发展，对算力的需求也持续激增。在这样的背景下，传统的云计算因为受到计算能力、存储能力和网络传输能力的限制，用户对数据处理速率、服务质量（Quality of Service，QoS）与体验质量（Quality of Experience，QoE）的要求往往无法得到满足6。为解决该问题，边缘计算作为一种新的范式被提出7。它将具有一定计算和存储能力的小型服务节点（即边缘）通过无线网络部署在移动设备附近。借助缓存在边缘节点的服务应用，允许终端用户将自身产生的计算密集型和时延敏感型的计算任务卸载到边缘设备处执行8。边缘计算利用边缘的数量优势、用户靠近边缘的物理距离优势以及边缘节点的存储能力9-10，对云计算进行扩展，降低数据传输时间，提高计算能力、存储能力，也在很大程度上提高了服务质量和体验质量11。因此，边缘计算被认为是可以解决未来大规模网络计算资源不足等问题的关键技术之一12-14。但是，当移动设备和边缘设备较多时，不合理的任务调度可能导致任务阻塞、响应时间延长、资源浪费等情况。最优任务卸载问题可以被归结为在正确的时间将正确的任务卸载到正确的计算节点，这显然 是 一 个 多 目 标 优 化 问 题，已 被 证 明 是 NP 难题15-16。因此，在寻求合理的任务调度决策方面，研究人员做了大量工作，主要集中在元启发式算法方面。文献 17 提出一种基于整数编码的元启发式算法，来提高任务完成数量和资源利用效率两个目标，从而尽可能地提高用户满意度。文献 18 提出一种结合粒子群算法和遗传算法（Genetic Algorithm，GA）的元启发式算法，解决多边缘负载均衡问题，使计算节点的资源利用得更充分。文献 19 基于混合流水车间模型对调度问题建模，并考虑了能耗和系统时延之间的权重关系，最后利用混合编码方式的遗传算法来求解系统实验和能耗的加权最小化问题。但是，上述工作的前提是所有服务均可在边缘服务器上部署，即边缘服务器具有无限的缓存空间，这在现实环境中很难实现。事实上，边缘服务器只能响应预缓存的应用程序，且缓存资源极为有限。当边缘服务器没有缓存对应的服务应用时，任务不能被正常执行。因此，在寻求调度方案时，如果忽略缓存限制，则可能会对系统的正常执行造成影响。这些影响主要包括网络资源利用不足，调度方案失效等，最终将导致服务质量与体验质量不达标。文献 20 使用最近一周的缓存访问信息对线性回归模型进行训练，并提前缓存预测到将来要访问的服务，以此提高缓存命中率。然而，在现实世界中，要访问的服务分布更复杂，仅依靠线性回归模型预测可能会导致结果失准。此外，在固定时间范围内的热点服务可能变更多次，这可能进一步导致预测出现偏差。文献 21 通过对比获取数据的跳数带来的收益判断一种决策的优良，从而在候选决策中选取收益较大的决策作为缓存决策。但是当服务数量较多时，选取候选决策的方法不够灵活，这可能会影响系统的性能。文献 22 考虑了系统的动态性（移动设备可以动态接入和离开系统），设计了基于相似度的流行度缓存。但是，同文献 20-21 一样，文献22只考虑了缓存问题，没有考虑任务调度问题。本文在考虑边缘计算环境中已有缓存机制的情况下，以最小化任务执行时间为目标（在多数情况下，任务响应时间与服务质量和体验质量紧密相关23），寻求最优调度策略。通过对任务卸载问题进行建模，找到优化目标的数学表达式，并结合粒子群算 法 和 遗 传 算 法24，设 计 一 种 基 于 整 数 编 码 的IPSO_GA 算法，在合理的时间复杂度内搜索任务卸载决策。1系统建模本文主要研究边缘计算环境，边缘计算环境由移动设备层、边缘服务器层和云服务器层组成25。在移动设备层，由用户发出一系列任务请求，每一个请求对应于一个服务应用。当计算节点（包括边缘服务器和云服务器）接收到用户发出的请求后，只有当服务器本地已经缓存了对应的服务应用后才能处理该请求26。也就是说，只有缓存命中后任务才可以被执行，如果缓存未命中，则边缘服务器需要向云服务器请求下载应用服务，之后才可以执行该任务。边缘服务器具有有限的缓存容量，当边缘服务器需要下载服务应用时，本地剩余缓存空间可能无法承受更多服务应用，此时边缘服务将通过 LRU 算法执行替换决策。假设云服务器有无穷大的缓存空间，即云服务器可以缓存整个边缘计算