具有边缘缓存机制的混合启发式任务卸载算法

doi:10.19678/j.issn.1000-3428.0064783

摘要/Abstract

摘要： 边缘计算因其与用户物理距离短、响应速度快等特点，被认为是可以解决未来大规模网络计算资源不足等问题的关键技术之一。在多进多出的边缘计算环境下，通过将部分服务缓存到边缘节点可以降低用户请求任务的执行时间。但以往工作或假设边缘节点具有无限的缓存空间，或忽略当前缓存列表和缓存替换机制对任务卸载的影响，导致卸载决策失效或任务执行时间变长。面向具有缓存机制的边缘计算环境，提出一种基于整数编码的混合启发式任务卸载算法IPSO_GA，将任务卸载问题建模为一个混合整数非线性规划问题。结合粒子群优化和遗传算法，使各粒子通过交配运算和变异运算不断寻优，在合理的时间复杂度内搜索任务卸载决策。实验结果表明，与随机算法、贪心算法、平均算法等经典算法和目前较新算法相比，IPSO_GA算法在设备数量居中环境中的任务执行时间减少了58%～298%，能适用于设备数量多、计算密集的边缘计算环境。

关键词: 边缘计算, 任务卸载, 边缘缓存, 粒子群优化算法, 遗传算法

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)

中图分类号:

TP391

桑永宣, 魏江坡, 王博, 宋莹. 具有边缘缓存机制的混合启发式任务卸载算法[J]. 计算机工程, 2023, 49(4): 149-158.

SANG Yongxuan, WEI Jiangpo, WANG Bo, SONG Ying. Hybrid Heuristic Task Offloading Algorithm with Edge Caching Mechanism[J]. Computer Engineering, 2023, 49(4): 149-158.

http://www.ecice06.com/CN/Y2023/V49/I4/149

图/表 12

20230417185135

20230417185138

20230417185141

20230417185144

20230417185148

20230417185151

20230417185155

20230417185158

20230417185201

20230417185204

20230417185207

20230417185211

参考文献

[1] 张依琳, 梁玉珠, 尹沐君, 等.移动边缘计算中计算卸载方案研究综述[J].计算机学报, 2021, 44(12):2406-2430. ZHANG Y L, LIANG Y Z, YIN M J, et al.Survey on the methods of computation offloading in mobile edge computing[J].Chinese Journal of Computers, 2021, 44(12):2406-2430.(in Chinese)
[2] Cisco 2020.Cisco annual Internet report (2018-2023)[EB/OL].[2022-04-20].https://www.cisco.com/c/en/us/solutions/executive-perspectives/annual-internet-report/index.html.
[3] 邝祝芳, 陈清林, 李林峰, 等.基于深度强化学习的多用户边缘计算任务卸载调度与资源分配算法[J].计算机学报, 2022, 45(4):812-824. KUANG Z F, CHEN Q L, LI L F, et al.Multi-user edge computing task offloading scheduling and resource allocation based on deep reinforcement learning[J].Chinese Journal of Computers, 2022, 45(4):812-824.(in Chinese)
[4] 黄冬晴, 俞黎阳, 陈珏, 等.面向移动边缘计算的联合计算卸载和资源分配策略研究[J].华东师范大学学报(自然科学版), 2021(6):88-99. HUANG D Q, YU L Y, CHEN J, et al.Research on joint computation offloading and resource allocation strategy for mobile edge computing[J].Journal of East China Normal University (Natural Science), 2021(6):88-99.(in Chinese)
[5] 郝璐璐, 谢辉, 宋康, 等.基于边缘计算的交叉路口无人驾驶车辆通行轨迹预测算法[J].汽车安全与节能学报, 2021, 12(2):163-172. HAO L L, XIE H, SONG K, et al.Trajectory prediction algorithm of unmanned vehicles at urban intersection based on edge computing[J].Journal of Automotive Safety and Energy, 2021, 12(2):163-172.(in Chinese)
[6] 刘婷, 罗喜良.移动边缘计算中的在线任务卸载方法[J].中国科学院大学学报, 2022, 39(2):267-274. LIU T, LUO X L.Online task offloading in mobile edge computing[J].Journal of University of Chinese Academy of Sciences, 2022, 39(2):267-274.(in Chinese)
[7] AKHIRUL, ISLAM.A survey on task offloading in multi-access edge computing[J].Journal of Systems Architecture, 2021, 118(4):25-35.
[8] 张秋平, 孙胜, 刘敏, 等.面向多边缘设备协作的任务卸载和服务缓存在线联合优化机制[J].计算机研究与发展, 2021, 58(6):1318-1339. ZHANG Q P, SUN S, LIU M, et al.Online joint optimization mechanism of task offloading and service caching for multi-edge device collaboration[J].Journal of Computer Research and Development, 2021, 58(6):1318-1339.(in Chinese)
[9] ZENG J, SUN J Y, WU B W, et al.Mobile edge communications, computing, and caching technology in the maritime communication network[J].China Communications, 2020, 17(5):223-234.
[10] HE Y, YU F R, ZHAO N, et al.Secure social networks in 5G systems with mobile edge computing, caching, and device-to-device communications[J].IEEE Wireless Communications, 2018, 25(3):103-109.
[11] 余翔, 石雪琴, 刘一勋.移动边缘计算中卸载策略与功率的联合优化[J].计算机工程, 2020, 46(6):20-25. YU X, SHI X Q, LIU Y X.Joint optimization of offloading strategy and power in mobile-edge computing[J].Computer Engineering, 2020, 46(6):20-25.(in Chinese)
[12] GUO H Z, LIU J J, ZHANG J.Computation offloading for multi-access mobile edge computing in ultra-dense networks[J].IEEE Communications Magazine, 2018, 56(8):14-19.
[13] ABBAS N, ZHANG Y, TAHERKORDI A, et al.Mobile edge computing:a survey[J].IEEE Internet of Things Journal, 2018, 5(1):450-465.
[14] ZHANG K, LENG S P, HE Y J, et al.Mobile edge computing and networking for green and low-latency internet of things[J].IEEE Communications Magazine, 2018, 56(5):39-45.
[15] PHAM Q V, LE L B, CHUNG S H, et al.Mobile edge computing with wireless backhaul:joint task offloading and resource allocation[J].IEEE Access, 2019, 7:16444-16459.
[16] POCHET Y, WOLSEY L A.Production planning by mixed integer programming[M].New York:Springer, 2006.
[17] WANG B, CHENG J Q, CAO J, et al.Integer particle swarm optimization based task scheduling for device-edge-cloud cooperative computing to improve SLA satisfaction[J].PeerJ Computer Science, 2022, 8:893-904.
[18] 姚泽玮, 林嘉雯, 胡俊钦, 等.基于PSO-GA的多边缘负载均衡方法[J].计算机科学, 2021, 48(S2):456-463. YAO Z W, LIN J W, HU J Q, et al.PSO-GA based approach to multi-edge load balancing[J].Computer Science, 2021, 48(S2):456-463.(in Chinese)
[19] 凌雪延, 王鸿, 宋荣方.多核服务器边缘计算系统中任务卸载调度和功率分配的研究[J].南京邮电大学学报(自然科学版), 2020, 40(2):81-88. LING X Y, WANG H, SONG R F.Joint task offloading scheduling and transmit power allocation for mobile edge computing systems with multi-core server[J].Journal of Nanjing University of Posts and Telecommunications (Natural Science Edition), 2020, 40(2):81-88.(in Chinese)
[20] 张苏豫, 江凌云.基于主动缓存的云边端协同卸载策略[J].计算机工程与设计, 2021, 42(8):2124-2129. ZHANG S Y, JIANG L Y.Cloud edge end collaborative offloading strategy based on active caching[J].Computer Engineering and Design, 2021, 42(8):2124-2129.(in Chinese)
[21] XIA X Y, CHEN F F, GRUNDY J, et al.Constrained app data caching over edge server graphs in edge computing environment[C]//Proceedings of IEEE Transactions on Services Computing.Washington.D.C., USA.IEEE Press, 2021:5-16.
[22] WEI X L, LIU J W, WANG Y G, et al.Wireless edge caching based on content similarity in dynamic environments[J].Journal of Systems Architecture, 2021, 115:102-110.
[23] 李波, 黄鑫, 牛力, 等.车载边缘计算环境中的任务卸载决策和优化[J].微电子学与计算机, 2019, 36(2):78-82. LI B, HUANG X, NIU L, et al.Task offloading decision in vehicle edge computing environment[J].Microelectronics & Computer, 2019, 36(2):78-82.(in Chinese)
[24] SHI X H, LIANG Y C, LEE H P, et al.An improved GA and a novel PSO-GA-based hybrid algorithm[J].Information Processing Letters, 2005, 93(5):255-261.
[25] BI R, LIU Q, REN J K, et al.Utility aware offloading for mobile-edge computing[J].Tsinghua Science and Technology, 2021, 26(2):239-250.
[26] YAN J, BI S Z, DUAN L J, et al.Pricing-driven service caching and task offloading in mobile edge computing[J].IEEE Transactions on Wireless Communications, 2021, 20(7):4495-4512.

选择文件类型/文献管理软件名称

选择包含的内容