Task offloading optimization algorithm based on Lyapunov optimization
-
摘要:
针对边缘计算环境下,任务卸载过程中任务的动态到达性和信道条件的不确定所引起的平均时延和能耗的优化问题,提出了一种基于李雅普诺夫优化的任务卸载优化算法.首先,采用李雅普诺夫优化方法把原问题转变为确定性的优化问题,将终端设备中待卸载的任务队列按照优先级传输至缓存基站,并对任务卸载过程中的队列长度进行约束和建模,使得队列长度可控,从而保证系统稳定性.其次,结合遗传算法正反馈机制、快速收敛性和蚁群算法全局快速搜索能力、求解精度效率高等优势,对缓存基站中带有优先级约束队列的实际状态来寻求近似最优的卸载路径,以便高效的将任务卸载到合适的移动边缘计算(Mobile Edge Computing,MEC)服务器中.最后,根据任务队列的约束和卸载路径的优化结果提出了一种启发式全局优化任务卸载算法.经过实验仿真,所提算法与现有的EEDOA研究方法相比,合理地约束队列长度与选择近似最优路径可有效降低任务的卸载能耗.
Abstract:Aiming at the optimization problem of average delay and energy consumption caused by the dynamic arrival of tasks and the uncertainty of channel conditions in the process of task unloading in edge computing environment, a task offload optimization algorithm based on Lyapunov optimization is proposed. Firstly, the original problem is transformed into a deterministic optimization problem by using Lyapunov optimization method, and the task queue to be unloaded in the terminal equipment is transmitted to the cache base station according to priority. The queue length in the process of task unloading is constrained and modeled, which make queue length controllable to ensure system stability. Secondly, combined with the positive feedback mechanism of genetic algorithm, fast convergence and the advantages of fast global search ability and high precision efficiency of ant colony algorithm, the approximate optimal unloading path is found for the actual state of the cache base station with priority constraint queue, so as to the task can be offloaded to the appropriate mobile edge computing server efficiently. Finally, according to the constraints of the task queue and the optimization results of the offloading path, a heuristic global optimization task offloading algorithm is proposed. Compared with the existing EEDOA research methods through experimental simulation, the proposed algorithm can effectively reduce the unloading energy consumption of tasks by reasonably constraining the queue length and choosing the approximate optimal path.
-
[1] SHI W S, CAO J, ZHANG Q, et al. Edge computing: vision and challenges[J]. IEEE Internet of Things Journal, 2016, 3(5): 637-646. DOI: 10.1109/JIOT.2016.2579198. [2] BI S Z, ZHANG Y J. Computation rate maximization for wireless powered mobile-edge computing with binary computation offloading[J]. IEEE Transactions on Wireless Communications, 2018, 17(6): 4177-4190. DOI: 10.1109/TWC.2018.2821664. [3] ZHANG J N, ZHAO X Y. An overview of user-oriented computation offloading in mobile edge computing[C]//Proceedings of 2020 IEEE World Congress on Services (SERVICES). Beijing: IEEE, 2020: 75-76. DOI: 10.1109/SERVICES48979.2020.00029. [4] BI S Z, HUANG L, WANG H, et al. Lyapunov-guided deep reinforcement learning for stable online computation offloading in mobile-edge computing networks[J]. IEEE Transactions on Wireless Communications, 2021, 20(11): 7519-7537. DOI: 10.1109/TWC.2021.3085319. [5] LI K Q. Heuristic computation offloading algorithms for mobile users in fog computing[J]. ACM Transactions on Embedded Computing Systems, 2021, 20(2): 11. DOI: 10.1145/3426852. [6] CHEN Y, ZHANG N, ZHANG Y C, et al. Energy efficient dynamic offloading in mobile edge computing for internet of things[J]. IEEE Transactions on Cloud Computing, 2021, 9(3): 1050-1060. DOI: 10.1109/TCC.2019.2898657. [7] CHANG Z, LIU L Q, GUO X J, et al. Dynamic resource allocation and computation offloading for IoT fog computing system[J]. IEEE Transactions on Industrial Informatics, 2021, 17(5): 3348-3357. DOI: 10.1109/TⅡ.2020.2978946. [8] GUO K, GAO R F, XIA W C, et al. Online learning based computation offloading in MEC systems with communication and computation dynamics[J]. IEEE Transactions on Communications, 2021, 69(2): 1147-1162. DOI: 10.1109/TCOMM.2020.3038875. [9] REN J, MAHFUJUL K, LYU F, et al. Joint channel allocation and resource management for stochastic computation offloading in MEC[J]. IEEE Transactions on Vehicular Technology, 2020, 69(8): 8900-8913. DOI: 10.1109/TVT.2020.2997685. [10] LIU C B, LI K L, LIANG J, et al. COOPER-MATCH: job offloading with a cooperative game for guaranteeing strict deadlines in MEC[J]. IEEE Transactions on Mobile Computing, 2019. DOI: 10.1109/TMC.2019.2921713. [11] HUANG L, BI S Z, ZHANG Y J A. Deep reinforcement learning for online computation offloading in wireless powered mobile-edge computing networks[J]. IEEE Transactions on Mobile Computing, 2020, 19(11): 2581-2593. DOI: 10.1109/TMC.2019.2928811. [12] DINH T Q, TANG J H, LA Q D, et al. Offloading in mobile edge computing: task allocation and computational frequency scaling[J]. IEEE Transactions on Communications, 2017, 65(8): 3571-3584. DOI: 10.1109/TCOMM.2017.2699660. [13] 李岩, 袁弘宇, 于佳乔, 等. 遗传算法在优化问题中的应用综述[J]. 山东工业技术, 2019, (12): 242-243. DOI: 10.16640/j.cnki.37-1222/t.2019.12.210.LI Y, YUAN H Y, YU J Q, et al. Survey on application of ant colony algorithm in optimization problem[J]. Shandong Industrial Technology, 2019, (12): 242-243. DOI: 10.16640/j.cnki.37-1222/t.2019.12.210. [14] DORIGO M, STVTZLE T. Ant colony optimization: overview and recent advances[M]. GENDREAU M, POTVIN J Y. Handbook of Metaheuristics. Cham: Springer, 2019: 311-351. DOI: 10.1007/978-3-319-91086-4_10. [15] ZHAN Y F, GUO S, Li P, et al. A deep reinforcement learning based offloading game in edge computing[J]. IEEE Transactions on Computers, 2020, 69(6): 883-893. DOI: 10.1109/TC.2020.2969148. [16] 梁金琳, 薛颂东, 赵静, 等. 基于蚁群-遗传融合框架的仓储群机器人任务分配[J]. 计算机系统应用, 2021, 30(11): 172-178. DOI: 10.15888/j.cnki.csa.008193.LIANG J L, XUE S D, ZHAO J, et al. Task allocation of warehouse swarm robots based on ant colony-genetic fusion framework[J]. Computer Systems & Applications, 2021, 30(11): 172-178. DOI: 10.15888/j.cnki.csa.008193. [17] 邵俊昌, 李旭东. AutoCAD ObjectARX 2000开发技术指南[M]. 北京: 电子工业出版社, 2000.SHAO J C, LI X D, AutoCAD ObjectARX 2000 development technology guide[M]. Beijing: Publishing House of Electronics Industry, 2000. [18] 工班. 遗传算法与蚁群算法结合[EB/OL]. (2019-11-19). https://www.cnblogs.com/wyf-1999-1-6/p/11891089.html.GONG B. Combination of genetic algorithm and ant colony algorithm[EB/OL]. (2019-11-19). https://www.cnblogs.com/wyf-1999-1-6/p/11891089.html. [19] LYU X C, NI W, TIAN H, et al. Optimal schedule of mobile edge computing for internet of things using partial information[J]. IEEE Journal on Selected Areas in Communications, 2017, 35(11): 2606-2615. DOI: 10.1109/JSAC.2017.2760186. [20] MAO Y Y, ZHANG J, SONG S H, et al. Stochastic joint radio and computational resource management for multi-user mobile-edge computing systems[J]. IEEE Transactions on Wireless Communications, 2017, 16(9): 5994-6009. DOI: 10.1109/TWC.2017.2717986. [21] LI K Q. Heuristic computation offloading algorithms for mobile users in fog computing[J]. ACM Transactions on Embedded Computing Systems, 2021, 20(2): 11. DOI: 10.1145/3426852. [22] 李世威, 王建强, 曾俊伟. 遗传算法调整蚁群算法参数模型研究[J]. 计算机工程与设计, 2011, 32(10): 3490-3493. DOI: 10.16208/j.issn1000-7024.2011.10.078.LI S W, WANG J Q, ZENG J W. Model of ant colony algorithm parameters optimization based on genetic algorithm[J]. Computer Engineering and Design, 2011, 32(10): 3490-3493. DOI: 10.16208/j.issn1000-7024.2011.10.078. [23] ZHANGK, MAO Y M, LENG S, et al. Energy-efficient offloading for mobile edge computing in 5G heterogeneous networks[J]. IEEE Access, 2016(4): 5896-5907. DOI: 10.1109/ACCESS.2016.2597169. -