• 北大核心期刊(《中文核心期刊要目总览》2017版)
  • 中国科技核心期刊(中国科技论文统计源期刊)
  • JST 日本科学技术振兴机构数据库(日)收录期刊

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于李雅普诺夫优化的任务卸载优化算法

马丽丽 张文东 李智威 莫王昊

马丽丽, 张文东, 李智威, 莫王昊. 基于李雅普诺夫优化的任务卸载优化算法[J]. 微电子学与计算机, 2022, 39(11): 19-26. doi: 10.19304/J.ISSN1000-7180.2022.0242
引用本文: 马丽丽, 张文东, 李智威, 莫王昊. 基于李雅普诺夫优化的任务卸载优化算法[J]. 微电子学与计算机, 2022, 39(11): 19-26. doi: 10.19304/J.ISSN1000-7180.2022.0242
MA Lili, ZHANG Wendong, LI Zhiwei, MO Wanghao. Task offloading optimization algorithm based on Lyapunov optimization[J]. Microelectronics & Computer, 2022, 39(11): 19-26. doi: 10.19304/J.ISSN1000-7180.2022.0242
Citation: MA Lili, ZHANG Wendong, LI Zhiwei, MO Wanghao. Task offloading optimization algorithm based on Lyapunov optimization[J]. Microelectronics & Computer, 2022, 39(11): 19-26. doi: 10.19304/J.ISSN1000-7180.2022.0242

基于李雅普诺夫优化的任务卸载优化算法

doi: 10.19304/J.ISSN1000-7180.2022.0242
基金项目: 

新疆维吾尔自治区自然科学基金资助项目 2020D01C033

详细信息
    作者简介:

    马丽丽  女,(1999-),硕士研究生.研究方向为边缘计算、任务卸载

    李智威  男,(1998-),硕士研究生.研究方向为边缘计算、任务卸载

    莫王昊  男,(1997-),硕士研究生.研究方向为边缘计算、任务卸载

    通讯作者:

    张文东(通讯作者)   男,(1975-),博士,副教授,硕士生导师.研究方向为物联网技术、Ad Hoc网络. E-mail: zwdxju@163.com

  • 中图分类号: TN929.5

Task offloading optimization algorithm based on Lyapunov optimization

  • 摘要:

    针对边缘计算环境下,任务卸载过程中任务的动态到达性和信道条件的不确定所引起的平均时延和能耗的优化问题,提出了一种基于李雅普诺夫优化的任务卸载优化算法.首先,采用李雅普诺夫优化方法把原问题转变为确定性的优化问题,将终端设备中待卸载的任务队列按照优先级传输至缓存基站,并对任务卸载过程中的队列长度进行约束和建模,使得队列长度可控,从而保证系统稳定性.其次,结合遗传算法正反馈机制、快速收敛性和蚁群算法全局快速搜索能力、求解精度效率高等优势,对缓存基站中带有优先级约束队列的实际状态来寻求近似最优的卸载路径,以便高效的将任务卸载到合适的移动边缘计算(Mobile Edge Computing,MEC)服务器中.最后,根据任务队列的约束和卸载路径的优化结果提出了一种启发式全局优化任务卸载算法.经过实验仿真,所提算法与现有的EEDOA研究方法相比,合理地约束队列长度与选择近似最优路径可有效降低任务的卸载能耗.

     

  • 图 1  任务卸载模型

    Figure 1.  Task offloading model

    图 2  不同算法下的最优路径

    Figure 2.  Optimal path under different algorithms

    图 3  平均队列长度

    Figure 3.  The average queue length

    图 4  任务卸载能耗

    Figure 4.  Task offloading energy consumption

  • [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.
  • 加载中
图(4)
计量
  • 文章访问数:  78
  • HTML全文浏览量:  62
  • PDF下载量:  17
  • 被引次数: 0
出版历程
  • 收稿日期:  2022-04-12
  • 修回日期:  2022-05-01
  • 网络出版日期:  2022-11-29

目录

    /

    返回文章
    返回