基于两阶段优化的并发流任务计算卸载策略

doi:10.19678/j.issn.1000-3428.0065163

摘要/Abstract

摘要： 计算卸载作为移动边缘计算中最关键的技术之一而备受研究人员的关注，然而现有研究较少同时考虑拓扑结构、优化目标多样性及计算资源竞争的特性。针对移动边缘计算场景下的并发型数据流任务计算卸载及资源竞争问题，设计一种基于并发型数据流任务的多目标计算卸载混合整数模型，并给出一种基于多目标优化和多属性决策的两阶段优化框架对该模型进行求解。在多目标优化阶段，提出改进动态多种群并行NSGA-II（DMP-NSGA-II）算法，包括多种群多交叉策略、动态调整种群规模与二次局部搜索的改进策略，以解决局部收敛和全局搜索难以平衡的问题，同时设计一种基于混合式求解框架的DMP-NSGA-II算法求解多目标混合整数模型。在多属性决策阶段，提出一种基于模糊C均值聚类和灰关联投影法的后验选解方法，以选出在不同偏好下具有代表性的最优卸载决策。在测试函数和模型实例上的实验结果表明，设计的两阶段优化框架能够有效地求解所提出的模型，在ZDT系列测试函数上DMP-NSGA-II算法的HV和SP指标表现全面优于NSGA-II、MOEA/D和MOEA/D-DE算法，在模型实例上DMP-NSGA-II算法的Meantime和Meanenergy指标相较于基于混合式求解框架的NSGA-II算法，分别提升了30.1%和8.9%。

关键词: 并发流任务, 计算资源竞争, 偏好多目标, 移动边缘计算, 模糊C-均值聚类

Abstract: Recently, computing offloading has attracted the attention of researchers as one of the most critical technologies in mobile edge computing. However, the existing research rarely considers the application topology, diversity of optimization objectives, and characteristics of the computing resource competition simultaneously.Therefore, a multi-objective computing offloading mixed integer model based on concurrent data-flow tasks is designed in this study to solve the problem of the computing offloading and resource competition of concurrent data-flow tasks in the Mobile Edge Computing (MEC) scene, and a two-stage optimization framework based on multi-objective optimization and multi-attribute decision-making is designed to solve it. First, an improved Dynamic Multi-Population parallel NSGA-II (DMP-NSGA-II) algorithm is proposed in the multi-objective optimization stage, including a multi-population multi-crossover strategy, a dynamic adjustment of the population size, and an improved strategy for quadratic local search, to solve the problem of the difficult balance between the local convergence and global search.Second, a DMP-NSGA-II algorithm based on a hybrid solution framework is designed to efficiently solve the multi-objective mixed integer model.Finally, a posterior solution selection method based on the Fuzzy C-Means clustering and Grey Relational Projection (FCM-GRP) method is designed to select the representative optimal unloading decision under different preferences.The results of the two simulation experiments on the test function and model example show that the designed two-stage optimization framework can effectively solve the proposed model.For the ZDT series of test functions, the HV and SP performances of the DMP-NSGA-II algorithm are significantly better than those of the NSGA-II, MOEA/D and MOEA/D-DE algorithms.For the model examples, the mean time and mean energy performances of the DMP-NSGA-II algorithm based on the hybrid solution framework are increased by 30.1% and 8.9%, respectively, compared with the NSGA-II algorithm based on the hybrid solution framework.

Key words: concurrent flow tasks, computing resource competition, prefer multi-objective, Mobile Edge Computing(MEC), Fuzzy C-Means(FCM) clustering

中图分类号:

TP393

姚政, 吴怀宇, 陈洋. 基于两阶段优化的并发流任务计算卸载策略[J]. 计算机工程, 2022, 48(12): 62-71.

YAO Zheng, WU Huaiyu, CHEN Yang. Computing Offloading Strategy for Concurrent Flow Tasks Based on Two-stage Optimization[J]. Computer Engineering, 2022, 48(12): 62-71.

http://www.ecice06.com/CN/Y2022/V48/I12/62

图/表 10

20230112182615

20230112182619

20230112182623

20230112182627

20230112182632

20230112182636

20230112182639

20230112182643

20230112182647

20230112182652

参考文献

[1] LI B, LIU Z, PEI Y J, et al.Mobility prediction based opportunistic computational offloading for mobile device cloud[C]//Proceedings of the 17th IEEE International Conference on Computational Science and Engineering.Washington D.C., USA:IEEE Press, 2014:786-792.
[2] SHIRAZ M, SOOKHAK M, GANI A, et al.A study on the critical analysis of computational offloading frameworks for mobile cloud computing[J].Journal of Network and Computer Applications, 2015, 47:47-60.
[3] 周业茂, 李忠金, 葛季栋, 等.移动云计算中基于延时传输的多目标工作流调度[J].软件学报, 2018, 29(11):3306-3325. ZHOU Y M, LI Z J, GE J D, et al.Multi-objective workflow scheduling based on delay transmission in mobile cloud computing[J].Journal of Software, 2018, 29(11):3306-3325.(in Chinese)
[4] PATEL Y S, REDDY M, MISRA R.Energy and cost trade-off for computational tasks offloading in mobile multi-tenant clouds[J].Cluster Computing, 2021, 24(3):1793-1824.
[5] PATEL M, NAUGHTON B, CHAN C, et al.Mobile-edge computing introductory technical white paper[J].Mobile-edge Computing, 2014, 29:854-864.
[6] LIU J, MAO Y Y, ZHANG J, et al.Delay-optimal computation task scheduling for mobile-edge computing systems[C]//Proceedings of 2016 IEEE International Symposium on Information Theory.Washington D.C., USA:IEEE Press, 2016:1451-1455.
[7] ZHANG W W, WEN Y G, GUAN K, et al.Energy-optimal mobile cloud computing under stochastic wireless channel[J].IEEE Transactions on Wireless Communications, 2013, 12(9):4569-4581.
[8] KWAK J, KIM Y, LEE J, et al.DREAM:dynamic resource and task allocation for energy minimization in mobile cloud systems[J].IEEE Journal on Selected Areas in Communications, 2015, 33(12):2510-2523.
[9] KAMOUN M, LABIDI W, SARKISS M.Joint resource allocation and offloading strategies in cloud enabled cellular networks[C]//Proceedings of 2015 IEEE International Conference on Communications.Washington D.C., USA:IEEE Press, 2018:5529-5534.
[10] SARDELLITTI S, SCUTARI G, BARBAROSSA S.Joint optimization of radio and computational resources for multicell mobile-edge computing[J].IEEE Transactions on Signal and Information Processing Over Networks, 2015, 1(2):89-103.
[11] 余翔, 刘一勋, 石雪琴, 等.车联网场景下的移动边缘计算卸载策略[J].计算机工程, 2020, 46(11):29-34, 41. YU X, LIU Y X, SHI X Q, et al.Mobile edge computing offloading strategy under Internet of vehicles scenario[J].Computer Engineering, 2020, 46(11):29-34, 41.(in Chinese)
[12] 欧阳逸风, 刘明波.暂态电压安全多目标混合整数最优控制模型及凸松弛方法[J].中国电机工程学报, 2015, 35(23):6018-6027. OUYANG Y F, LIU M B.Multi-objective/mixed-integer optimal control model and convex relaxation method for transient voltage security[J].Proceedings of the CSEE, 2015, 35(23):6018-6027.(in Chinese)
[13] RUIZ A B, SABORIDO R, BERMUDEZ J D, et al.Preference-based evolutionary multi-objective optimization for solving fuzzy portfolio selection problems[J].Revista Electrónica De Comunicaciones y Trabajos De ASEPUMA, 2017, 18(1):1-15.
[14] SUN J, YAN X, HENG Z, et al.Interval multi-objective programming methods for solving multi-period portfolio selection problems[C]//Proceedings of IEEE CDCʼ20.Washington D.C., USA:IEEE Press, 2020:367-378.
[15] BUI L T, ALAM S.An introduction to multi-objective optimization[M].[S.1.]:IGI Global, 2008.
[16] EMMERICH M T M, DEUTZ A H, YEVSEYEVA I.A Bayesian approach to portfolio selection in multicriteria group decision making[J].Procedia Computer Science, 2015, 64:993-1000.
[17] ZHOU X Y, WANG L Q, LIAO H C, et al.A prospect theory-based group decision approach considering consensus for portfolio selection with hesitant fuzzy information[J].Knowledge-Based Systems, 2019, 168:28-38.
[18] DEB K, PRATAP A, AGARWAL S, et al.A fast and elitist multi-objective genetic algorithm:NSGA-II[J].IEEE Transactions on Evolutionary Computation, 2002, 6(2):182-197.
[19] BEKELE E G, NICKLOW J W.Multi-objective automatic calibration of SWAT using NSGA-II[J].Journal of Hydrology, 2007, 341(3/4):165-176.
[20] MAHDI S, NINI B.Improved memetic NSGA-II using a deep neighborhood search[J].International Journal of Applied Metaheuristic Computing, 2021, 12(4):138-154.
[21] ZHANG P, QIAN Y Y, QIAN Q.Multi-objective optimization for materials design with improved NSGA-II[J].Materials Today Communications, 2021, 28:102709.
[22] BEZDEK J C, EHRLICH R, FULL W.FCM:the fuzzy c-means clustering algorithm[J].Computers & Geosciences, 1984, 10(2/3):191-203.
[23] DENG J L.Introduction grey system theory[J].Journal of Grey System, 1989, 1(1):191-243.
[24] XIE H P, JIANG J H, SHEN G L, et al.Estimation of the chemical rank for the three-way data:a principal norm vector orthogonal projection approach[J].Computers & Chemistry, 2002, 26(2):183-190.
[25] ZITZLER E, DEB K, THIELE L.Comparison of multiobjective evolutionary algorithms:empirical results[J].Evolutionary Computation, 2000, 8(2):173-195.
[26] ZHANG Q F, LI H.MOEA/D:a multiobjective evolutionary algorithm based on decomposition[J].IEEE Transactions on Evolutionary Computation, 2007, 11(6):712-731.
[27] TAN Y Y, JIAO Y C, LI H, et al.A modification to MOEA/D-DE for multiobjective optimization problems with complicated Pareto sets[J].Information Sciences, 2012, 213:14-38.
[28] ZHANG S G, LIU X, WANG J X, et al.Accurate range-free localization for anisotropic wireless sensor networks[J].ACM Transactions on Sensor Networks, 2015, 11(3):1-28.
[29] JAFARI A H, LÓPEZ-PÉREZ D, SONG H, et al.Small cell backhaul:challenges and prospective solutions[J].EURASIP Journal on Wireless Communications and Networking, 2015, 2015:206.
[30] RUI L L, YANG Y T, GAO Z P, et al.Computation offloading in a mobile edge communication network:a joint transmission delay and energy consumption dynamic awareness mechanism[J].IEEE Internet of Things Journal, 2019, 6(6):10546-10559.

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

选择包含的内容