面向边缘计算平台的半线上任务动态调度方法

doi:10.19665/j.issn1001-2400.2021.06.002

西安电子科技大学学报 ›› 2021, Vol. 48 ›› Issue (6): 8-15.doi: 10.19665/j.issn1001-2400.2021.06.002

• 智能嵌入式系统结构与软件关键技术专栏 • 上一篇下一篇

面向边缘计算平台的半线上任务动态调度方法

赵辉^1,²(),冯南之^1,²(),王泉^1,²(),万波^1,²(),王静¹()

1.西安电子科技大学计算机科学与技术学院,陕西西安 710071
2.陕西省智能人机交互与可穿戴技术重点实验室,陕西西安 710071

收稿日期:2021-08-15 出版日期:2021-12-20 发布日期:2022-02-24
通讯作者: 冯南之
作者简介:赵辉(1983—),男,讲师,博士,E-mail: hzhao@mail.xidian.edu.cn|王泉(1970—),男,教授,博士,E-mail: qwang@xidian.edu.cn|万波(1976—),男,教授,博士,E-mail: wanbo@xidian.edu.cn|王静(1981—),女,副教授,博士,E-mail: wangjing@mail.xidian.edu.cn
基金资助:
国家自然科学基金(61972302);陕西省重点研发计划项目(2021GY-014);陕西省重点研发计划项目(2021GY-086);中央高校基本科研业务费专项资金(JB210309);中央高校基本科研业务费专项资金(JB210312)

Dynamic semi-online task scheduling method for the edge computing platform

ZHAO Hui^1,²(),FENG Nanzhi^1,²(),WANG Quan^1,²(),WAN Bo^1,²(),WANG Jing¹()

1. School of Computer Science and Technology,Xidian University,Xi’an 710071,China
2. Key Laboratory of Smart Human-Computer Interaction and Wearable Technology of Shaanxi Province,Xi’an 710071,China

Received:2021-08-15 Online:2021-12-20 Published:2022-02-24
Contact: Nanzhi FENG

摘要/Abstract

摘要：

当边缘计算平台中存在已知和未知性能的计算节点时,这一场景下的任务调度称为半线上任务调度。由于未知性能节点的影响,一般任务调度方法可能导致任务执行时间或传输时间过长,使得边缘计算平台高能耗的问题更加突出。针对此问题,以能耗优化为目标,提出了一种面向边缘计算平台的半线上任务动态调度方法。首先,考虑边缘计算平台中能耗的主要影响因素,从边缘节点的处理速度、路由延迟和队列长度三个角度,引入边缘节点的任务执行能耗、任务传输能耗和空闲能耗,建立了面向能耗优化的边缘计算平台任务调度模型;其次,对于边缘计算平台中的未知性能节点,先将其性能假设为某个已知节点,形成未知-已知节点之间的映射关系,再不断感知映射双方的任务队列长度来动态调整映射关系,充分利用已有先验知识,提出了一种基于动态映射的半线上任务调度算法,实现能耗优化;最后,在CloudSim平台完成对比试验。实验结果表明,所提方法相较其他方法能有效地降低边缘计算平台的能耗。

关键词: 边缘计算, 任务调度, 未知计算节点, 动态映射

Abstract:

When there are known and unknown computing nodes in the edge computing platform,the task scheduling in this scene is called semi-online task scheduling.Due to the influence of unknown nodes,the normal task scheduling method may lead to a long makespan or transmission time,which aggravates the problem of high energy consumption on the edge computing platform.To solve this problem,this paper proposes a Dynamic semi-online task Scheduling Strategy (DSS) for the edge computing platform,aiming at energy consumption optimization.First,by considering the main factors affecting the energy consumption on the edge computing platform,the energy consumption of task execution,task transmission and idle are introduced from the perspectives of the processing speed,routing delay and queue delay of the edge nodes,and then an energy consumption optimization-oriented task scheduling model is established.Second,for the unknown node,this paper proposes a dynamic mapping-based semi-online task scheduling algorithm which assumes that the performances of unknown nodes are equal to a certain given node to form the mapping between unknown and known nodes.Then this algorithm dynamically adjusts the mapping relation of both sides through continuous perception of their task queue lengths,thus making full use of prior knowledge and reducing the energy consumption.Finally,a comparative evaluation is performed on the CloudSim platform,with the results showing that the proposed method can effectively reduce the energy consumption on the edge computing platform.

Key words: edge computing, task scheduling, unknown computing node, dynamic mapping

中图分类号:

TP301.6

赵辉,冯南之,王泉,万波,王静. 面向边缘计算平台的半线上任务动态调度方法[J]. 西安电子科技大学学报, 2021, 48(6): 8-15.

ZHAO Hui,FENG Nanzhi,WANG Quan,WAN Bo,WANG Jing. Dynamic semi-online task scheduling method for the edge computing platform[J]. Journal of Xidian University, 2021, 48(6): 8-15.

图/表 7

图1

表1

表2

图2

图3

图4

图5

参考文献 12

[1]	XU K, LV L, LI T, et al. Minimizing Tardiness for Data-Intensive Applications in Heterogeneous Systems:A Matching Theory Perspective[J]. IEEE Transactions on Parallel and Distributed Systems, 2020, 31(1):144-158. doi: 10.1109/TPDS.71
[2]	SIAVOSHANI M J, POURMIRI A, SHARIATPANAHI S P. Storage,Communication,and Load Balancing Trade-off in Distributed Cache Networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2018, 29(4):943-957. doi: 10.1109/TPDS.2017.2781242
[3]	POURMIRI A, SIAVOSHANI M J, SHARIATPANAHI S P. Proximity-Aware Balanced Allocations in Cache Networks[C]// IEEE International Parallel and Distributed Processing Symposium.Piscataway:IEEE, 2017:1068-1077.
[4]	ANSELMI J. Combining Size-Based Load Balancing with Round-Robin for Scalable Low Latency[J]. IEEE Transactions on Parallel and Distributed Systems, 2020, 31(4):886-896. doi: 10.1109/TPDS.71
[5]	CHAMPATI J P, LIANG B. Semi-Online Algorithms for Computational Task Offloading with Communication Delay[J]. IEEE Transactions on Parallel and Distributed Systems, 2017, 28(4):1189-1201. doi: 10.1109/TPDS.2016.2605684
[6]	CHAMPATI J P, LIANG B. Single Restart with Time Stamps for Parallel Task Processing with Known and Unknown Processors[J]. IEEE Transactions on Parallel and Distributed Systems, 2020, 31(1):187-200. doi: 10.1109/TPDS.71
[7]	SONG S, FANG Z, CHU S, et al. Efficient Semi-online Algorithms for Multiple Objects in Computational Offloading[J]. International Journal of Pattern Recognition and Artificial Intelligence, 2020, 34(11):2058014. doi: 10.1142/S0218001420580148
[8]	DWIBEDY D, MOHANTY R. Semi-online Scheduling:A Survey[EB/OL]. [2020-05-18]. https://arxiv.org/pdf/2005.08614.pdf .
[9]	ALBERS S, HELLWIG M. Semi-Online Scheduling Revisited[J]. Theoretical Computer Science, 2012, 443:1-9. doi: 10.1016/j.tcs.2012.03.031
[10]	MITZENMACHER M. The Power of Two Choices in Randomized Load Balancing[J]. IEEE Transactions on Parallel and Distributed Systems, 2001, 12(10):1094-1104. doi: 10.1109/71.963420
[11]	DROZDOWSKI M. Scheduling for Parallel Processing[M]. London:Springer, 2009:9-29.
[12]	CALHEIROS R N, RANJAN R, BELOGLAZOVA, et al. Cloudsim:A Toolkit for Modeling and Simulation of Cloud Computing Environments and Evaluation of Resource Provisioning Algorithms[J]. Software:Practice and Experience, 2011, 41(1):23-50. doi: 10.1002/spe.v41.1

面向边缘计算平台的半线上任务动态调度方法

Dynamic semi-online task scheduling method for the edge computing platform

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 12

相关文章 9

Metrics

本文评价

推荐阅读 10

[1]	吕文凯,杨鹏飞,丁韵青,张鹤于,郑天洋. JEDERL:一种异构计算平台任务调度优化算法[J]. 西安电子科技大学学报, 2021, 48(6): 67-74.
[2]	王汝言,吴和,崔亚平,吴大鹏,张鸿. 超密集网络中多基站博弈边缘卸载策略[J]. 西安电子科技大学学报, 2021, 48(4): 1-10.
[3]	马悦,张玉梅. 面向多接入边缘计算的VNFM分布式部署方案[J]. 西安电子科技大学学报, 2021, 48(4): 20-26.
[4]	凌敏,罗影,袁亮,靳传学. 一种面向智慧交通的车联网网络流量估计方法[J]. 西安电子科技大学学报, 2021, 48(3): 40-48.
[5]	张文柱,曹琲琲,余静华. 移动边缘计算中一种多用户计算卸载方法[J]. 西安电子科技大学学报, 2020, 47(6): 131-138.
[6]	陆继翔,方博雅. 移动边缘计算的多用户计算卸载研究及实验[J]. 西安电子科技大学学报, 2020, 47(4): 78-85.
[7]	王忍,王翊,胡艳军,蒋芳,许耀华. 超密集异构网络中过载MEC服务器的协作卸载[J]. 西安电子科技大学学报, 2020, 47(2): 126-134.
[8]	王晓丽;王宇平;孟坤. 考虑处理机释放时间的可分任务调度优化模型[J]. J4, 2016, 43(1): 47-53.
[9]	袁博;汪斌强;王志明. 并行多流水绿色路由查找架构和算法[J]. J4, 2012, 39(2): 145-152+167.