高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

一种基于风险感知策略的多节点任务调度方法

刘斌 赵亦玄 王辉 楚涌泉 付琨

刘斌, 赵亦玄, 王辉, 楚涌泉, 付琨. 一种基于风险感知策略的多节点任务调度方法[J]. 电子与信息学报, 2022, 44(9): 3231-3240. doi: 10.11999/JEIT210240
引用本文: 刘斌, 赵亦玄, 王辉, 楚涌泉, 付琨. 一种基于风险感知策略的多节点任务调度方法[J]. 电子与信息学报, 2022, 44(9): 3231-3240. doi: 10.11999/JEIT210240
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

一种基于风险感知策略的多节点任务调度方法

doi: 10.11999/JEIT210240
基金项目: 基础加强计划技术领域基金(2020-JCJQ-JJ-517)
详细信息
    作者简介:

    刘斌:男,博士生,研究方向为边缘计算与人工智能

    赵亦玄:女,硕士生,研究方向为边缘计算

    王辉:男,博士生,研究方向为云计算与人工智能

    楚涌泉:男,硕士,研究方向为边缘计算

    付琨:男,研究员,研究方向为地理空间数据分析与挖掘、遥感图像智能解译

    通讯作者:

    赵亦玄 15901498629@163.com

  • 中图分类号: TN92; TP311

A Multi-node Task Scheduling Method via Risk Perception Strategy

Funds: The Foundation and Enhancement Technology Fund (2020-JCJQ-JJ-517)
  • 摘要: 为解决无人机(UAV)集群任务调度时面临各节点动态、不稳定的情况,该文提出一种面向多计算节点的可尽量避免任务中断且具有容错性的任务调度方法。该方法首先为基于多计算节点构建了一个以最小化任务平均完成时间为优化目标的任务分配策略;然后基于任务的完成时间和边缘计算节点的存留时间两者的概率分布,将任务计算节点上的执行风险量化成额外开销时间;最后以任务的完成时间与额外开销时间之和替换原本的完成时间,设计了风险感知的任务分配策略。在仿真环境下将该文提出的任务调度方法与3种基准调度方法进行了对比实验,实验结果表明该方法能够有效地降低任务平均响应时间、任务平均执行次数以及任务截止时间错失率。证明该文提出的方法降低了任务重调度和重新执行带来的额外开销,可实现分布式协同计算任务的调度工作,为复杂场景下的无人机集群网络提供新的技术支持。
  • 图  1  任务调度框架示意图

    图  2  各时间值概率分布的关系

    图  3  测试床实验结果

    图  4  任务到达速率的影响

    图  5  计算节点到达速率的影响

    图  6  计算节点异构性的影响

    图  7  计算节点平均存留时间的影响

    表  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.713.2
    $ 3\times $树莓派4B15.115.3
    Surface Pro 4 ( M3 )8.795.9
    下载: 导出CSV

    表  4  测试床参数设置

    设备类型到达间隔(min)平均存留时间(min)
    树莓派3B+1025
    树莓派4B515
    Surface Pro 4(M3)20
    下载: 导出CSV

    表  5  默认参数设置

    参数默认值
    任务到达速率120 任务/min
    平均存留时间15 min
    计算节点到达速率5 节点/min
    下载: 导出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.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.
  • 加载中
图(7) / 表(5)
计量
  • 文章访问数:  149
  • HTML全文浏览量:  88
  • PDF下载量:  38
  • 被引次数: 0
出版历程
  • 收稿日期:  2021-03-25
  • 录用日期:  2022-08-09
  • 修回日期:  2022-08-08
  • 网络出版日期:  2022-08-12
  • 刊出日期:  2022-09-19

目录

    /

    返回文章
    返回