摘要
边缘计算因其与用户物理距离短、响应速度快等特点,被认为是可以解决未来大规模网络计算资源不足等问题的关键技术之一。在多进多出的边缘计算环境下,通过将部分服务缓存到边缘节点可以降低用户请求任务的执行时间。但以往工作或假设边缘节点具有无限的缓存空间,或忽略当前缓存列表和缓存替换机制对任务卸载的影响,导致卸载决策失效或任务执行时间变长。面向具有缓存机制的边缘计算环境,提出一种基于整数编码的混合启发式任务卸载算法IPSO_GA,将任务卸载问题建模为一个混合整数非线性规划问题。结合粒子群优化和遗传算法,使各粒子通过交配运算和变异运算不断寻优,在合理的时间复杂度内搜索任务卸载决策。实验结果表明,与随机算法、贪心算法、平均算法等经典算法和目前较新算法相比,IPSO_GA算法在设备数量居中环境中的任务执行时间减少了58%~298%,能适用于设备数量多、计算密集的边缘计算环境。
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.
作者
桑永宣
魏江坡
王博
宋莹
SANG Yongxuan;WEI Jiangpo;WANG Bo;SONG Ying(College of Software Engineering,Zhengzhou University of Light Industry,Zhengzhou 450001,China;Computer School,Beijing Information Science and Technology University,Beijing 100101,China)
出处
《计算机工程》
CAS
CSCD
北大核心
2023年第4期149-158,共10页
Computer Engineering
基金
国家自然科学基金面上项目(61872043)
河南省重点研发与推广专项(科技攻关)(232102211084)
河南省高等学校重点科研项目(21A520050)。
关键词
边缘计算
任务卸载
边缘缓存
粒子群优化算法
遗传算法
edge computing
task offloading
edge caching
particle swarm optimization
Genetic Algorithm(GA)
