广东工业大学学报 ›› 2022, Vol. 39 ›› Issue (04): 9-16.doi: 10.12052/gdutxb.220010

• • 上一篇    下一篇

改进多种群进化算法求解移动边缘计算中任务调度问题

朱清华, 鹿安邦, 周俭铁, 侯艳   

  1. 广东工业大学 计算机学院, 广东 广州 510006
  • 收稿日期:2022-01-17 出版日期:2022-07-10 发布日期:2022-06-29
  • 作者简介:朱清华(1974–)，男，副教授，博士，主要研究方向为云计算/边缘计算、半导体制造的调度优化，E-mail：zhuqh@gdut.edu.cn
  • 基金资助:
    国家自然科学基金资助项目（61673123）；广东省自然科学基金资助项目(2020A151501482)

An Improved Multi-population Evolutionary Algorithm for Task Scheduling in a Mobile Edge Computing Environment

Zhu Qing-hua, Lu An-bang, Zhou Jian-tie, Hou Yan   

  1. School of Computer Science and Technology, Guangdong University of Technology, Guangzhou 510006, China
  • Received:2022-01-17 Online:2022-07-10 Published:2022-06-29

HTML

PDF (PC)

2248

摘要： 移动边缘计算通过在靠近用户端的网络边缘部署服务器，为用户提供低时延的网络通信服务和类似云的计算服务。移动设备通过网络接入点将任务卸载到边缘服务器进行处理，能够有效地减少移动设备的能耗以及任务的完成时间。然而，用户在卸载任务时需要支付一定的通信成本。本文在构建包含多个用户和多个边缘计算节点的移动边缘计算环境的基础上，建立了最小化移动设备的任务完成时间、能耗以及通信成本的数学模型。为了解决上述问题，本文提出了一种改进多种群进化算法的任务调度优化算法。该调度算法通过优化卸载决策和资源分配决策来达到降低移动设备综合成本的目的。大量仿真实验说明，该任务调度算法与其他几种的任务调度算法相比，能够更有效地降低移动设备的综合成本。

关键词: 移动边缘计算, 任务调度, 多种群进化算法

Abstract: Mobile edge computing (MEC) can provide users with low-latency network services and cloud-like computing services by deploying servers at the edge network which is close to users. Mobile devices (MDs) offload their tasks to edge servers for computing via the network access points, which can effectively reduce the power consumption of MDs and the completion time of their tasks. However, users have to pay for communications when they offload their tasks to edge servers. A MEC system is studied which contains multiple users and multiple edge computing nodes. Mathematical models are built for task completion time, power consumption, and communication cost of MDs, and the problem is formulated to minimize these objectives. A task scheduling algorithm based on a multi-population evolutionary algorithm is proposed to solve this problem. The scheduling algorithm minimizes the comprehensive cost of MDs by optimizing the offloading decisions and resource allocation decisions for MDs. Lots of simulations are conducted to verify that the proposed algorithm can reduce the comprehensive cost of MDs better compared with other scheduling algorithms.

Key words: mobile edge computing, task scheduling, multi-population evolutionary algorithm

中图分类号: 

  • TP393
[1] MAHMOODI S E, UMA R N, SUBBALAKSHMI K P. Optimal joint scheduling and cloud offloading for mobile applications [J]. IEEE Transactions on Cloud Computing, 2019, 7(2): 301-313.
[2] CHEN M, GUO S, LIU K, et al. Robust computation offloading and resource scheduling in cloudlet-based mobile cloud computing [J]. IEEE Transactions on Mobile Computing, 2021, 20(5): 2025-2040.
[3] SATYANARAYANAN M, BAHL P, CACERES R, et al. The case for VM-based cloudlets in mobile computing [J]. IEEE Pervasive Computing, 2009, 8(4): 14-23.
[4] MACH P, BECVAR Z. Mobile edge computing: a survey on architecture and computation offloading [J]. IEEE Communications Surveys & Tutorials, 2017, 19(3): 1628-1656.
[5] XU Y, GU B, HU R Q, et al. Joint computation offloading and radio resource allocation in MEC-based wireless-powered backscatter communication networks [J]. IEEE Transactions on Vehicular Technology, 2021, 70(6): 6200-6205.
[6] MUKHERJEE A, DE D, ROY D G. A power and latency aware cloudlet selection strategy for multi-cloudlet environment [J]. IEEE Transactions on Cloud Computing, 2019, 7(1): 141-154.
[7] BI J, YUAN H, DUANMU S, et al. Energy-optimized partial computation offloading in mobile-edge computing with genetic simulated-annealing-based particle swarm optimization [J]. IEEE Internet of Things Journal, 2021, 8(5): 3774-3785.
[8] BOZORGCHENANI A, MASHHADI F, TARCHI D, et al. Multi-objective computation sharing in energy and delay constrained mobile edge computing environments [J]. IEEE Transactions on Mobile Computing, 2021, 20(10): 2992-3005.
[9] LI H, XU H, ZHOU C, et al. Joint optimization strategy of computation offloading and resource allocation in multi-access edge computing environment [J]. IEEE Transactions on Vehicular Technology, 2020, 69(9): 10214-10226.
[10] MAO Y, ZHANG J, LETAIEF K B. Dynamic computation offloading for mobile-edge computing with energy harvesting devices [J]. IEEE Journal on Selected Areas in Communications, 2016, 34(12): 3590-3605.
[11] CHEN Y, ZHANG N, ZHANG Y, 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.
[12] CHEN X, JIAO L, LI W, et al. Efficient multi-user computation offloading for mobile-edge cloud computing [J]. IEEE/ACM Transactions on Networking, 2015, 24(5): 2795-2808.
[13] MAZOUZI H, ACHIR N, BOUSSETTA K. Dm2-ecop: an efficient computation offloading policy for multi-user multi-cloudlet mobile edge computing environment [J]. ACM Transactions on Internet Technology (TOIT), 2019, 19(2): 1-24.
[14] DINH T Q, TANG J, 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.
[15] WU J, CAO Z, ZHANG Y, et al. Edge-cloud collaborative computation offloading model based on improved partical swarm optimization in MEC[C]//IEEE 25th International Conference on Parallel and Distributed Systems (ICPADS). TianJin: IEEE, 2019: 959-962.
[16] HUANG L, FENG X, ZHANG L, et al. Multi-server multi-user multi-task computation offloading for mobile edge computing networks [J]. Sensors, 2019, 19(6): 1446.
[17] CHEN M H, LIANG B, DONG M. Joint offloading decision and resource allocation for multi-user multi-task mobile cloud[C]//2016 IEEE International Conference on Communications (ICC). Kuala Lumpur: IEEE, 2016: 1-6.
[18] 杨天, 杨军. 移动边缘计算中的卸载决策与资源分配策略[J]. 计算机工程, 2021, 47(2): 19-25.
YANG T, YANG J. Offloading decision and resource allocation strategy in mobile edge computing [J]. Computer Engineering, 2021, 47(2): 19-25.
[19] DEB K, AGRAWAL R B. Simulated binary crossover for continuous search space [J]. Complex Systems, 1995, 9(2): 115-148.
[20] DEB K, GOYAL M. A combined genetic adaptive search (GeneAS) for engineering design [J]. Computer Science and Informatics, 1996, 26(4): 30-45.
[21] KENNEDY J, EBERHART R. Particle swarm optimization[C]// Proceedings of International Conference on Neural Networks (ICNN'95). Perth: IEEE, 1995, 4: 1942-1948.
[22] YANG X S, DEB S. Cuckoo search via Lévy flights[C]//2009 World Congress on Nature & Biologically Inspired Computing (NaBIC). Coimbatore: IEEE, 2009: 210-214.
[23] PARSOPOULOS K E, VRAHATIS M N. Particle swarm optimization method for constrained optimization problems [J]. Intelligent Technologies–Theory and Application:New Trends in Intelligent Technologies, 2002, 76(1): 214-220.
[24] ZHANG C, LIU Z, GU B, et al. A deep reinforcement learning based approach for cost- and energy-aware multi-flow mobile data offloading [J]. IEICE Transactions on Communications, 2018, E101.B(7): 1625-1634.
[1] 王丰, 李宇龙, 林志飞, 崔苗, 张广驰. 基于计算吞吐量最大化的能量采集边缘计算系统在线资源优化配置[J]. 广东工业大学学报, 2022, 39(04): 17-23.
[2] 刘竹松， 陈洁， 田龙. 基于改进布谷鸟搜索算法的云计算任务调度[J]. 广东工业大学学报, 2016, 33(03): 32-36.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 2017 《广东工业大学学报》编辑部
地址：广州市东风东路729号广东工业大学 邮编：510090
电话：020-37626653,020-37626139,020-37626396
邮箱：xbzrb@gdut.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发