边缘计算平台中面向分簇的半在线调度方法

doi:10.19665/j.issn1001-2400.20241004

西安电子科技大学学报 ›› 2024, Vol. 51 ›› Issue (6): 104-116.doi: 10.19665/j.issn1001-2400.20241004

• 计算机科学与技术 & 网络空间安全 • 上一篇下一篇

边缘计算平台中面向分簇的半在线调度方法

韩家曦¹^,²(), 赵辉¹^,²^,³(), 冯南之¹(), 王静¹(), 万波¹^,²^,³(), 王泉¹^,²()

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

收稿日期:2023-10-22 出版日期:2024-10-23 发布日期:2024-10-23
通讯作者: 王静(1981—),女,副教授,博士,E-mail:wangjing@mail.xidian.edu.cn
作者简介:韩家曦(2000—),男,西安电子科技大学硕士研究生,E-mail:22031212552@stu.xidian.edu.cn;
赵辉(1983—),男,副教授,博士,E-mail:hzhao@mail.xidian.edu.cn;
冯南之(1998—),男,西安电子科技大学硕士研究生,E-mail:20031211439@stu.xidian.edu.cn;
万波(1976—),男,教授,博士,E-mail:wanbo@xidian.edu.cn;
王泉(1970—),男,教授,博士,E-mail:qwang@xidian.edu.cn
基金资助:
陕西省重点研发计划(2024GX-YBXM-010);陕西省重点研发计划(2024GX-YBXM-140);陕西省重点研发计划(2024GX-YBXM-039);陕西省创新能力支撑计划(2023-CX-TD-08);陕西省秦创原“科学家+工程师”团队(2023KXJ-040);中央高校基本科研业务费专项资金(ZYTS24089)

Cluster-oriented semi-online task scheduling method in the edge computing platform

HAN Jiaxi¹^,²(), ZHAO Hui¹^,²^,³(), FENG Nanzhi¹(), WANG Jing¹(), WAN Bo¹^,²^,³(), WANG Quan¹^,²()

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

Received:2023-10-22 Online:2024-10-23 Published:2024-10-23

摘要/Abstract

摘要：

目前面向边缘计算的任务调度方法未考虑因网络延迟造成边缘节点性能不确定的问题,无法适应存在节点性能不确定的延迟敏感型边缘计算平台。针对此问题,提出了一种延迟敏感型边缘计算平台中面向分簇的半在线调度方法。首先,针对边缘计算平台中存在性能不确定的节点,设计了性能模糊度指标表示边缘节点的性能确定程度,为半在线调度算法提供额外信息;其次,以QoS保障和最小化任务完成时间为目标,提出了双段QoS保障模型和任务完成时间优化模型,建立任务调度双目标优化模型;再次,针对任务调度NP难问题,提出了一种基于映射的半在线任务调度算法MSSA,按照性能模糊度结合用户位置划分服务区域,建立面向分簇的边缘计算平台模型,并根据负载变化动态调整簇容量,实现高效的半在线任务调度。最后,基于真实边缘计算平台日志数据,通过仿真实验与其它方法进行对比,结果表明提出的算法能够减少26%的任务完成时间,并在QoS保障方面提升19%。

关键词: 边缘计算, 调度算法, 服务质量, 任务完成时间

Abstract:

The existing task scheduling methods for edge computing do not consider the problem of uncertain performance of edge nodes caused by network delay,and cannot adapt to the delay sensitive edge computing platform with uncertain node performance.To solve this problem,this paper proposes a cluster-oriented semi-online scheduling method for delay-sensitive edge computing platform.First,considering the nodes with uncertain performance caused by network delay,a performance uncertainty metric is designed to represent the degree of performance certainty of edge nodes.This metric provides extra pieces of information for the semi-online scheduling algorithm.Second,a dual-objective QoS guarantee model and a task completion time optimization model are proposed to establish a dual-objective optimization model for task scheduling,which focuses on guaranteeing QoS and minimizing makespan.Third,to address the NP-hard problem of task scheduling,a mapping-based semi-online task scheduling algorithm(MSSA) is proposed which divides the service area range based on the performance uncertainty metric and user location,establishes a cluster-oriented edge computing platform model,and dynamically adjusts cluster capacity based on load changes,thus enabling efficient semi-online task scheduling.Finally,by using trace data from a real edge computing platform,simulation experiments are conducted to compare the proposed algorithm with other methods.Experimental results demonstrate that the proposed algorithm can reduce the task completion time by 26% and improves the QoS guarantee by 19%.

Key words: edge computing, scheduling algorithms, quality of service, makespan

中图分类号:

TP301.6

韩家曦, 赵辉, 冯南之, 王静, 万波, 王泉. 边缘计算平台中面向分簇的半在线调度方法[J]. 西安电子科技大学学报, 2024, 51(6): 104-116.

HAN Jiaxi, ZHAO Hui, FENG Nanzhi, WANG Jing, WAN Bo, WANG Quan. Cluster-oriented semi-online task scheduling method in the edge computing platform[J]. Journal of Xidian University, 2024, 51(6): 104-116.

图/表 9

图1

图2

图3

图4

图5

图6

图7

图8

图9

参考文献 19

[1]	DWIBEDY D, MOHANTY R. Semi-Online Scheduling:A Survey[J]. Computers & Operations Research, 2022, 139(1):105646.
[2]	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.
[3]	SONG S, FANG Z, ZHANG Z, et al. Semi-Online Computational Offloading by Dueling Deep-Q Network for User Behavior Prediction[J]. IEEE Access, 2020, 8:118192-118204.
[4]	XIAO M, LIU X, LI W. Semi-Online Early Work Maximization Problems on Two Hierarchical Uniform Machines with Partial Information of Processing Time[J]. Journal of Combinatorial Optimization, 2023, 46:1-19.
[5]	LI G, CAI J. An Online Incentive Mechanism for Collaborative Task Offloading in Mobile Edge Computing[J]. IEEE Transactions on Wireless Communications, 2020, 19(1):624-636.
[6]	LV H, ZHENG Z, WU F, et al. Strategy-Proof Online Mechanisms for Weighted AoI Minimization in Edge Computing[J]. IEEE Journal on Selected Areas in Communications, 2021, 39(5):1277-1292.
[7]	MENG J, TAN H, LI X, et al. Online Deadline Aware Task Dispatching and Scheduling in Edge Computing[J]. IEEE Transactions on Parallel and Distributed Systems, 2020, 31(6):1270-1286.
[8]	XIAO M, LIU X, LI W, et al. Online and Semi-Online Scheduling on Two Hierarchical Machines with a Common Due Date to Maximize the Total Early Work[J]. International Journal of Applied Mathematics and Computer Science, 2024, 34(2):253-261.
[9]	江帆, 李妍, 宋琦琳. 车联网中时延感知的计算卸载和资源分配策略[J]. 西安邮电大学学报, 2023, 28(1):1-8.
	JIANG Fan, LI Yan, SONG Qilin. Delay-Aware Computation Offloading and Resource Allocation Strategy for Internet of Vehicles[J]. Journal of Xi'an University of Posts and Telecommunications, 2023, 28(1):1-8.
[10]	王红艳, 孙其博, 马骁, 等. 边缘辅助实时应用中信息年龄感知的任务调度[J]. 通信学报, 2024, 45(6):144-159. doi: 10.11959/j.issn.1000-436x.2024109
	WANG Hongyan, SUN Qibo, MA Xiao, et al. AoI-Aware Task Scheduling in Edge-Assisted Real-Time Applications[J]. Journal on Communications, 2024, 45(6):144-159. doi: 10.11959/j.issn.1000-436x.2024109
[11]	GE L, WANG Z, BAO W, et al. Semi-Online Multi-Machine with Restart Scheduling for Integrated Edge and Cloud Computing Systems[C]// Proceedings of the 51st International Conference on Parallel Processing. New York: ACM, 2023:1-13.
[12]	ZHENG F, CHEN Y, Liu M, et al. Semi-Online Scheduling on Two Identical Parallel Machines with Initial-Lookahead Information[J]. Asia-Pacific Journal of Operational Research, 2024(1):41.
[13]	DENNINNART C, GENTRY J, SALEHI M. Improving Robustness of Heterogeneous Serverless Computing Systems via Probabilistic Task Pruning[C]// IEEE International Parallel and Distributed Processing Symposium Workshops(IPDPSW). Piscataway:IEEE, 2019:6-15.
[14]	MENG J, TAN H, XU C, et al. Dedas:Online Task Dispatching and Scheduling with Bandwidth Constraint in Edge Computing[C]// IEEE INFOCOM 2019-IEEE Conference on Computer Communications. Piscataway:IEEE, 2019:2287-2295.
[15]	赵辉, 冯南之, 王泉, 等. 面向边缘计算平台的半线上任务动态调度方法[J]. 西安电子科技大学学报, 2021, 48(6):8-15.
	ZHAO Hui, FENG Nanzhi, WANG Quan, et al. Dynamic Semi-Online Task Scheduling Method for the Edge Computing Platform[J]. Journal of Xidian University, 2021, 48(6):8-15.
[16]	LI Q, MA X, ZHOU A, et al. User-Oriented Edge Node Grouping in Mobile Edge Computing[J]. IEEE Transactions on Mobile Computing, 2023, 22(6):3691-3705.
[17]	WANG X, NING Z, GUO S, et al. Imitation Learning Enabled Task Scheduling for Online Vehicular Edge Computing[J]. IEEE Transactions on Mobile Computing, 2022, 21(2):598-611.
[18]	WANG J, ZHU K, CHEN B, et al. Distributed Clustering-Based Cooperative Vehicular Edge Computing for Real-Time Offloading Requests[J]. IEEE Transactions on Vehicular Technology, 2022, 71(1):653-669.
[19]	MITZENMACHER M. The Power of Two Choices in Randomized Load Balancing[J]. IEEE Transactions on Parallel and Distributed Systems, 2001, 12(10):1094-1104.

边缘计算平台中面向分簇的半在线调度方法

Cluster-oriented semi-online task scheduling method in the edge computing platform

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

图/表 9

参考文献 19

相关文章 15

Metrics

本文评价

推荐阅读 0

[1]	支文韬, 赵辉, 孟繁鑫, 王静, 万波, 王泉. 面向WaaS平台的多工作流容错调度策略[J]. 西安电子科技大学学报, 2025, 52(1): 181-195.
[2]	唐汉秦, 赵辉, 宁竞莜, 王静, 万波, 王泉. 流行度感知的无线视频云边缓存策略研究[J]. 西安电子科技大学学报, 2024, 51(5): 97-109.
[3]	张超, 赵辉, 张智峰, 王静, 万波, 王泉. 边缘协作环境下最小化完工时间任务调度方法[J]. 西安电子科技大学学报, 2024, 51(4): 114-127.
[4]	吕翊,王焰斌,张鸿,王汝言,张普宁. 边缘增强H-CRAN中能耗感知的资源分配机制[J]. 西安电子科技大学学报, 2022, 49(2): 67-78.
[5]	朱思峰,孙恩林,柴争义. 移动边缘计算场景下基于免疫优化的任务卸载[J]. 西安电子科技大学学报, 2022, 49(1): 152-160.
[6]	张宇鹏,吴自力,陈鸣,张璐璐. 面向交叉微服务链的任务调度优化[J]. 西安电子科技大学学报, 2021, 48(6): 32-39.
[7]	赵辉,冯南之,王泉,万波,王静. 面向边缘计算平台的半线上任务动态调度方法[J]. 西安电子科技大学学报, 2021, 48(6): 8-15.
[8]	王汝言,吴和,崔亚平,吴大鹏,张鸿. 超密集网络中多基站博弈边缘卸载策略[J]. 西安电子科技大学学报, 2021, 48(4): 1-10.
[9]	马悦,张玉梅. 面向多接入边缘计算的VNFM分布式部署方案[J]. 西安电子科技大学学报, 2021, 48(4): 20-26.
[10]	凌敏,罗影,袁亮,靳传学. 一种面向智慧交通的车联网网络流量估计方法[J]. 西安电子科技大学学报, 2021, 48(3): 40-48.
[11]	张文柱,曹琲琲,余静华. 移动边缘计算中一种多用户计算卸载方法[J]. 西安电子科技大学学报, 2020, 47(6): 131-138.
[12]	陆继翔,方博雅. 移动边缘计算的多用户计算卸载研究及实验[J]. 西安电子科技大学学报, 2020, 47(4): 78-85.
[13]	王忍,王翊,胡艳军,蒋芳,许耀华. 超密集异构网络中过载MEC服务器的协作卸载[J]. 西安电子科技大学学报, 2020, 47(2): 126-134.
[14]	曹静;武君胜;杨文超;王硕晨. 认知无线ad hoc网的多尺度跨层路由协议[J]. 西安电子科技大学学报, 2018, 45(2): 77-83.
[15]	段瑞猛;马文平;罗维;赵飞飞. 一个毫微微小区网络中的全分布式资源分配策略[J]. 西安电子科技大学学报, 2017, 44(3): 36-42.