一种面向移动边缘计算的多用户细粒度任务卸载调度方法

doi:10.12263/DZXB.20201039

电子学报 ›› 2021, Vol. 49 ›› Issue (11): 2202-2207.DOI: 10.12263/DZXB.20201039

一种面向移动边缘计算的多用户细粒度任务卸载调度方法

崔玉亚¹^,², 张德干¹^,², 张婷³, 杨鹏¹^,², 朱浩丽¹^,²

^1.天津理工大学天津市智能计算及软件新技术重点实验室, 天津 300384
^2.天津理工大学计算机视觉与系统省部共建教育部重点实验室, 天津 300384
^3.天津体育学院体育经济与管理学院，天津 301617

收稿日期:2020-09-21 修回日期:2021-05-13 出版日期:2021-11-25 发布日期:2021-11-25
作者简介:崔玉亚男，1992年生，江苏淮安人，天津理工大学计算机科学与工程学院在读博士生，研究兴趣为网络通信、物联网、无线传感器网络、移动边缘计算等．E-mail:844511468@qq.com
张德干男，1970年生，湖北黄冈人，天津理工大学计算机科学与工程学院教授/博士，博导，研究兴趣为物联网、无线传感器网络、移动边缘计算、云计算等.E-mail:zhangdegan@tsinghua.org.cn
张婷(通信作者) 女，1972年，河北唐山人，天津体院学院体育经济与管理学院教授/博士，硕导，研究兴趣为物联网、无线传感器网络、移动边缘计算、大数据等.E-mail:zhangtingts@163.com
基金资助:
国家自然科学基金(61571328);天津市重大科技专项(15ZXDSGX00050);天津市科技支撑重点项目(17YFZCGX00360);天津市自然科学基金(18JCZDJC96800);天津市科技创新和131人才团队(TD13-5025)

A Multi-User Fine-Grained Task Offloading Scheduling Approach of Mobile Edge Computing

Yu-ya CUI¹^,², De-gan ZHANG¹^,², Ting ZHANG³, Peng YANG¹^,², Hao-li ZHU¹^,²

^1.Tianjin Key Laboratory of Intelligent Computing & Novel Software Technology，Tianjin University of Technology，Tianjin 300384，China
^2.Ministry of Education Key Laboratory of Computer Vision and System，Tianjin University of Technology，Tianjin 300384，China
^3.School of Sports Economics and Management，Tianjin University of Sport，Tianjin 301617，China

Received:2020-09-21 Revised:2021-05-13 Online:2021-11-25 Published:2021-11-25

摘要/Abstract

摘要：

在移动边缘计算中(Mobile Edge Computing, MEC)，任务卸载可以有效地解决移动设备资源受限的问题，但是将全部任务都卸载到边缘服务器并非最优.本文提出一种面向移动边缘计算的多用户细粒度任务卸载调度新方法，把计算任务看作一个有向无环图(Directed Acyclic Graph, DAG)，对节点的执行位置和调度顺序进行了优化决策.考虑系统的延迟把计算卸载看作一个约束多目标优化问题(Constrained Multi-object Optimization Problem, CMOP)，提出了一个改进的NSGA-Ⅱ算法来解决CMOP.所提出的算法能够实现本地和边缘的并行处理从而减少延迟.实验结果表明，算法能够在实际应用程序中做出最优决策.

关键词: 移动边缘计算, 计算卸载, 约束多目标优化问题, 细粒度卸载调度, NSGA-Ⅱ

Abstract:

In mobile edge computing (MEC), task offloading can solve the problem of resource constraint on mobile devices effectively, but it is not optimal to offload all tasks to edge servers. In this paper, a multi-user fine-grained task offloading scheduling approach of mobile edge computation is proposed. The computation task is regarded as a directed acyclic graph (DAG), and task nodes’ execution location and scheduling order are optimized. Considering the delay of the system, the computation offloading is considered as a constrained multi-objective optimization problem (CMOP), and an improved NSGA -Ⅱ algorithm is proposed to solve the CMOP. The proposed algorithm can realize local and edge parallel processing to reduce delay. The experimental results show that the algorithm can make the optimal decision in practical applications.

Key words: mobile edge computing, computation offloading, constrained multi-objective optimization problem(CMOP), fine-grained task offloading scheduling, NSGA-Ⅱ

中图分类号:

TP393

崔玉亚, 张德干, 张婷, 杨鹏, 朱浩丽. 一种面向移动边缘计算的多用户细粒度任务卸载调度方法[J]. 电子学报, 2021, 49(11): 2202-2207.

Yu-ya CUI, De-gan ZHANG, Ting ZHANG, Peng YANG, Hao-li ZHU. A Multi-User Fine-Grained Task Offloading Scheduling Approach of Mobile Edge Computing[J]. Acta Electronica Sinica, 2021, 49(11): 2202-2207.

图/表 2

参考文献 18

1	GAO J X. Novel approach of distributed & adaptive trust metrics for MANET[J]. Wireless Networks, 2019, 25(6):3587 - 3603.
2	CHEN C, CUI Y Y. New method of energy efficient subcarrier allocation based on evolutionary game theory[J]. Mobile Networks and Applications, 2021, 26(2): 523 - 536.
3	Liu S, Liu X H, Zhang T. Adaptive repair algorithm for TORA routing protocol based on flood control strategy[J]. Computer Communications, 2020, 151(1): 437 - 448.
4	GE H. New multi-hop clustering algorithm for vehicular Ad Hoc networks[J]. IEEE Transactions on Intelligent Transportation Systems, 2019, 20(4):1517 - 1530.
5	ZHANG T. A new method of data missing estimation with FNN-based tensor heterogeneous ensemble learning for Internet of vehicle[J]. Neurocomputing, 2021, 420(1): 98 - 110.
6	LIU S. Novel unequal clustering routing protocol considering energy balancing based on network partition & distance for mobile education[J]. Journal of Network and Computer Applications, 2017, 88(15):1 - 9.
7	ZHANG T. Novel self-adaptive routing service algorithm for application of VANET[J]. Applied Intelligence, 2019, 49(5):1866 - 1879.
8	YANG J N, MAO G Q. Optimal base station antenna downtilt in downlink cellular networks[J]. IEEE Transactions on Wireless Communications, 2019, 18(3):1779 - 1791.
9	ZHANG T. Novel optimized link state routing protocol based on quantum genetic strategy for mobile learning[J]. Journal of Network and Computer Applications, 2018, (122):37 - 49.
10	张德干. 一种基于前向感知因子的WSN能量均衡路由方法[J]. 电子学报, 2014, 42(1): 113 - 118.
	ZHANG De-gan. A kind of routing protocol based on forward-aware factor for energy balance[J]. Acta Electronica Sinica, 2014, 42(1): 113 - 118. (in Chinese)
11	张德干. 一种基于Q-Learning策略的自适应车联网路由新算法[J]. 电子学报, 2018, 46(10): 2325 - 2332.
	ZHANG De-gan. A kind of new routing algorithm with adaptivity for mobile IoT based on Q-Learning[J]. Acta Electronica Sinica, 2018, 46(10): 2325 - 2332. (in Chinese)
12	Wang X, Song X D. A new clustering routing method based on PECE for WSN[J]. EURASIP Journal on Wireless Communications and Networking, 2015, (162): 1 - 13.
13	Liu S, Liu X H. Novel dynamic source routing protocol (DSR) based on genetic algorithm bacterial foraging optimization (GA-BFO)[J]. International Journal of Communication Systems, 2018, 31(18): 1 - 20.
14	Tang Y M, Cui Y Y. Novel reliable routing method for engineering of Internet of vehicles based on graph theory[J]. Engineering Computations, 2019, 36(1): 226 - 247.
15	Liu S. Dynamic analysis for the average shortest path length of mobile Ad Hoc networks under random failure scenarios[J]. IEEE Access, 2019, 7: 21343 - 21358.
16	Wu H, Zhao P Z. New approach of multi-path reliable transmission for marginal wireless sensor network[J]. Wireless Networks, 2020, 26(2): 1503 - 1517.
17	Cui Y Y, Zhang T, Chen L. Novel method of mobile edge computation offloading based on evolutionary game strategy for IoT devices[J]. AEU-International Journal of Electronics and Communications, 2020, 118(5): 1 - 13.
18	Rui L L. 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, 1(1): 99.

[1]	刘雷, 陈晨, 冯杰, 肖婷婷, 裴庆祺. 车载边缘计算卸载技术研究综述[J]. 电子学报, 2021, 49(5): 861-871.
[2]	覃剑, 石昌伟, 张媛, 贾云健, 胡浩星. 边缘视频处理的细粒度划分与重组部署算法[J]. 电子学报, 2021, 49(11): 2152-2159.

一种面向移动边缘计算的多用户细粒度任务卸载调度方法

A Multi-User Fine-Grained Task Offloading Scheduling Approach of Mobile Edge Computing

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 2

参考文献 18

相关文章 2

编辑推荐

Metrics