A Multi-node Task Scheduling Method via Risk Perception Strategy

LIU Bin; ZHAO Yixuan; WANG Hui; CHU Yongquan; FU Kun

doi:10.11999/JEIT210240

Volume 44 Issue 9

Sep. 2022

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2022 > 44(9): 3231-3240

LIU Bin, ZHAO Yixuan, WANG Hui, CHU Yongquan, FU Kun. A Multi-node Task Scheduling Method via Risk Perception Strategy[J]. Journal of Electronics & Information Technology, 2022, 44(9): 3231-3240. doi: 10.11999/JEIT210240

Citation:

LIU Bin, ZHAO Yixuan, WANG Hui, CHU Yongquan, FU Kun. A Multi-node Task Scheduling Method via Risk Perception Strategy[J]. Journal of Electronics & Information Technology, 2022, 44(9): 3231-3240. doi: 10.11999/JEIT210240

Citation:

PDF( 3824 KB)

A Multi-node Task Scheduling Method via Risk Perception Strategy

doi: 10.11999/JEIT210240

LIU Bin^{1, 2, 3, 4},
ZHAO Yixuan^{5
,
,},
WANG Hui⁶,
CHU Yongquan⁷,
FU Kun¹

1.
Aerospace Information Research Institute, Chinese Academy of Sciences, Beijing 100094, China
2.
University of Chinese Academy of Sciences, Beijing 100049, China
3.
School of Electronic, Electrical and Communication Engineering, University of Chinese Academy of Sciences, Beijing 100094, China
4.
Key Laboratory of Network Information System Technology, Aerospace Information Research Institute, Beijing 100094, China
5.
Information Engineering College, Capital Normal University, Beijing 100048, China
6.
State Key Laboratory of Software Development Environment, BeiHang University, Beijing 100191, China
7.
Edge Intelligence of CAS Co., Ltd, Beijing 100190, China

Funds: The Foundation and Enhancement Technology Fund (2020-JCJQ-JJ-517)

Received Date: 2021-03-25
Accepted Date: 2022-08-09
Rev Recd Date: 2022-08-08

Available Online: 2022-08-12

Publish Date: 2022-09-19

Abstract

Abstract

In order to solve the dynamic and unstable situation of each node in Unmanned Aerial Vehicle(UAV)cluster task scheduling, a multi computing node oriented task scheduling method is proposed, which can avoid task interruption as much as possible and has fault tolerance. Firstly, a task allocation strategy based on multi computing nodes is constructed to minimize the average completion time of tasks. Secondly, based on the probability distribution of the completion time of tasks and the retention time of edge computing nodes, the execution risk on task computing nodes is quantified as the extra overhead time. Finally, the sum of the completion time and the extra overhead time of tasks is calculated instead of the original completion time, a risk aware task allocation strategy is designed. In the simulation environment, the proposed task scheduling method is compared with three benchmark scheduling methods. The experimental results show that the proposed method can effectively reduce the average response time, the average execution times and the miss rate of task deadline. It is proved that the proposed method can reduce the additional cost of task rescheduling and re-execution, realize the task scheduling of distributed collaborative computing, and provide new technical support for UAV cluster network in complex scenarios.
- Task scheduling,
- Task allocation,
- Risk perception,
- Distributed computing

FullText(HTML)

References(15)

References

[1]	徐婷婷. 面向任务的无人机编队组网技术研究[D]. [硕士论文], 电子科技大学, 2020. XU Tingting. Research on task-oriented UAV formation networking technology[D]. [Master dissertation], University of Electronic Science and Technology of China, 2020.
[2]	王晓宇. 实时任务在集群计算中的自适应容错调度研究[D]. [硕士论文], 复旦大学, 2010. WANG Xiaoyu. The study of self-adaptive fault-tolerant scheduling for real-time tasks on cluster computing[D]. [Master dissertation], Fudan University, 2010.
[3]	向竹, 杨志伟, 杨克巍, 等. 基于双层稳定匹配的异构无人机集群“分布式”协同算法[J]. 控制与决策, 2022, 37(4): 871–880. doi: 10.13195/j.kzyjc.2020.1285 XIANG Zhu, YANG Zhiwei, YANG Kewei, et al. “Decentralized” collaborative algorithm for heterogeneous UAV swarm based on bi-level stable matching[J]. Control and Decision, 2022, 37(4): 871–880. doi: 10.13195/j.kzyjc.2020.1285
[4]	朱文捷. 基于动态组网和计算卸载的多无人机协作平台的设计与实现[D]. [硕士论文], 东南大学, 2019. ZHU Wenjie. Design and implementation of multi-UAV collaboration platform based on dynamic networking and computing offloading[D]. [Master dissertation], Southeast University, 2019.
[5]	董超, 沈赟, 屈毓锛. 基于无人机的边缘智能计算研究综述[J]. 智能科学与技术学报, 2020, 2(3): 227–239. doi: 10.11959/j.issn.2096-6652.202025 DONG Chao, SHEN Yun, and QU Yuben. A survey of UAV-based edge intelligent computing[J]. Chinese Journal of Intelligent Science and Technology, 2020, 2(3): 227–239. doi: 10.11959/j.issn.2096-6652.202025
[6]	肖作林, 秦枫, 陆明胜. 一种“云”导弹协同打击系统的构想[J]. 飞航导弹, 2013(7): 23–26. doi: 10.16338/j.issn.1009-1319.2013.07.005 XIAO Zuolin, QIN Feng, and LU Mingsheng. A conception of "cloud" missile cooperative strike system[J]. Aerodynamic Missile Journal, 2013(7): 23–26. doi: 10.16338/j.issn.1009-1319.2013.07.005
[7]	URGAONKAR R, WANG Shiqiang, HE Ting, et al. Dynamic service migration and workload scheduling in edge-clouds[J]. Performance Evaluation, 2015, 91: 205–228. doi: 10.1016/j.peva.2015.06.013
[8]	JIA Mike, LIANG Weifa, XU Zichuan, et al. Cloudlet load balancing in wireless metropolitan area networks[C]. The 35th Annual IEEE International Conference on Computer Communications, San Francisco, USA, 2016: 1–9.
[9]	HE Ting, KHAMFROUSH H, WANG Shiqiang, et al. It's hard to share: Joint service placement and request scheduling in edge clouds with sharable and non-sharable resources[C]. 2018 IEEE 38th International Conference on Distributed Computing Systems (ICDCS), Vienna, Austria, 2018: 365–375.
[10]	HABAK K, ZEGURA E W, AMMAR M, et al. Workload management for dynamic mobile device clusters in edge femtoclouds[C]. The Second ACM/IEEE Symposium on Edge Computing, San Jose, USA: 2017: 6.
[11]	邹立岩, 张明智. 马赛克战视角下的智能无人机集群作战概念研究[J]. 战术导弹技术, 2020(6): 67–74,86. doi: 10.16358/j.issn.1009-1300.2020.1.116 ZOU Liyan and ZHANG Mingzhi. Research on the concept of intelligent UAV swarm operation under mosaic warfare viewpoint[J]. Tactical Missile Technology, 2020(6): 67–74,86. doi: 10.16358/j.issn.1009-1300.2020.1.116
[12]	PARK J W, TUMANOV A, JIANG A, et al. 3Sigma: Distribution-based cluster scheduling for runtime uncertainty[C]. The Thirteenth EuroSys Conference, Porto, Portugal, 2018: 2.
[13]	LIM P, GOH C K, and TAN K C. A novel time series-histogram of features (TS-HoF) method for prognostic applications[J]. IEEE Transactions on Emerging Topics in Computational Intelligence, 2018, 2(3): 204–213. doi: 10.1109/TETCI.2018.2822836
[14]	LENSTRA J K, KAN A H G R, and BRUCKER P. Complexity of machine scheduling problems[J]. Annals of Discrete Mathematics, 1977, 1: 343–362. doi: 10.1016/S0167-5060(08)70743-X
[15]	TUMANOV A, JIANG A, PARK J W, et al. JamaisVu: Robust scheduling with auto-estimated job runtimes[R]. Technical Report CMU-PDL-16-104, 2016.