A Multi-node Task Scheduling Method via Risk Perception Strategy
-
摘要: 为解决无人机(UAV)集群任务调度时面临各节点动态、不稳定的情况，该文提出一种面向多计算节点的可尽量避免任务中断且具有容错性的任务调度方法。该方法首先为基于多计算节点构建了一个以最小化任务平均完成时间为优化目标的任务分配策略；然后基于任务的完成时间和边缘计算节点的存留时间两者的概率分布，将任务计算节点上的执行风险量化成额外开销时间；最后以任务的完成时间与额外开销时间之和替换原本的完成时间，设计了风险感知的任务分配策略。在仿真环境下将该文提出的任务调度方法与3种基准调度方法进行了对比实验，实验结果表明该方法能够有效地降低任务平均响应时间、任务平均执行次数以及任务截止时间错失率。证明该文提出的方法降低了任务重调度和重新执行带来的额外开销，可实现分布式协同计算任务的调度工作，为复杂场景下的无人机集群网络提供新的技术支持。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.
-
Key words:
- Task scheduling /
- Task allocation /
- Risk perception /
- Distributed computing
-
表 1 右移和概率转换过程(算法1)
输入：1个直方图$ \{\left({v}_{1},{f}_{1}\right),\left({v}_{2},{f}_{2}\right),\cdots ,\left({v}_{B},{f}_{B}\right)\} $，1个位移
值$ \delta $输出：1个概率直方图$\{\left({u}_{1},{p}_{1}\right),\left({u}_{2},{p}_{2}\right),\cdots ,\left({u}_{B},{p}_{B}\right)\} $ (1) set $S=\sum _{i= 1}^{B}{f}_{i} $ (2) for $i=1\;{\rm{to}}\;B$ do (3) ${u}_{i}={v}_{i}+\delta $ (4) ${p}_{i}={f}_{i}÷\delta $ (5) end for 
下载: 导出CSV
表 2 从给定值开始概率转换过程(算法2)
输入：1个直方图$\{\left({v}_{1},{f}_{1}\right),\left({v}_{2},{f}_{2}\right),\cdots ,\left({v}_{B},{f}_{B}\right)\} $，1个位移
值$ \delta $输出：1个概率直方图$ \{\left({u}_{1},{p}_{1}\right),\left({u}_{2},{p}_{2}\right),\cdots ,\left({u}_{c},{p}_{c}\right)\} $ (1) 查找i以满足${f}_{i}\le \delta \le {f}_{i+1} $ (2) if $ {f}_{i}=\delta $ then (3) set $S=\sum _{j=i}^{B}{f}_{i} $ (4) else (5) set $S=\sum _{j=i+1}^{B}{f}_{i},i=i+1 $ (6) end if (7) for $j=i\mathrm{t}\mathrm{o}B,k=1\mathrm{t}\mathrm{o}B-i+1 $ do (8) ${u}_{k}={v}_{j}+\delta $ (9) ${p}_{k}={f}_{k}÷\delta $ (10) end for
下载: 导出CSV
表 3 计算节点硬件配置
设备类型 计算能力(MFLOPs) 带宽(Mbit/s) $ 2\times $树莓派3B+ 2.7 13.2 $ 3\times $树莓派4B 15.1 15.3 Surface Pro 4 ( M3 ) 8.7 95.9
下载: 导出CSV
-
[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.1285XIANG 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.202025DONG 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.005XIAO 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.116ZOU 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. -
下载:
点击查看大图
图(7) / 表(5)
计量
- 文章访问数: 528
- HTML全文浏览量: 423
- PDF下载量: 72
- 被引次数: 0
