南京大学学报(自然科学版) ›› 2022, Vol. 58 ›› Issue (1): 153–162.doi: 10.13232/j.cnki.jnju.2022.01.015

• • 上一篇    

面向IoT数据工作流的分割与调度方法

秦生辉1,2, 赵卓峰1,2(), 杨中国1,2   

  1. 1.北方工业大学信息学院，北京，100144
    2.大规模流数据集成与分析技术北京市重点实验室，北京，100144
  • 收稿日期:2021-09-22 出版日期:2022-01-30 发布日期:2022-02-22
  • 通讯作者: 赵卓峰 E-mail:edzhao@ncut.edu.cn
  • 作者简介:E⁃mail：edzhao@ncut.edu.cn.
  • 基金资助:
    国家重点研发计划(2018YFB1402500);国家自然科学基金国际合作与交流项目(62061136006);北京市自然科学基金(4202021)

Segmentation and scheduling method for IoT data workflow

Shenghui Qin1,2, Zhuofeng Zhao1,2(), Zhongguo Yang1,2   

  1. 1.Institute of Information Technology, North China University of Technology, Beijing, 100144, China
    2.Beijing Key Laboratory on Integration and Analysis of Large?Scale Stream Data, Beijing, 100144, China
  • Received:2021-09-22 Online:2022-01-30 Published:2022-02-22
  • Contact: Zhuofeng Zhao E-mail:edzhao@ncut.edu.cn

RichHTML

159

PDF (PC)

662

摘要：

物联网数据是当前一类典型的大数据，其应用正成为诸多行业领域的热点，围绕物联网数据的应用往往可以被表示为由一组大数据处理与分析任务构成的工作流.与传统工作流不同的是，IoT（Internet of Things）环境下这种数据驱动的工作流具有数据来源分散、数据规模大、云边协同分布执行等特点，给IoT数据工作流的执行带来了数据流控制管理、数据传输调度等方面的诸多挑战.针对IoT数据工作流的执行约束和数据传输优化问题，提出一种面向IoT数据工作流的分割与调度优化方法.首先对IoT数据工作流的执行约束条件、边缘节点负载以及数据传输量进行建模，进而以数据传输和执行时间优化为目标设计一种云边架构下IoT数据工作流的分割算法和子工作流执行调度算法.通过基于WorkflowSim的仿真实验结果表明，提出的算法与典型的HEFT和MINMIN算法相比，可以在保障边缘节点执行约束和负载均衡的条件下有效降低IoT数据工作流的执行时间.

关键词: IoT工作流, 分割调度, 数据传输优化, 多目标优化, 物联网服务

Abstract:

IoT (Internet of Things) data is a typical type of big data at present，and its application is becoming a hot spot in many industries. Applications surrounding IoT data can often be expressed as a workflow composed of a set of big data processing and analysis tasks. Differing from traditional workflows，this data?driven workflow in the IoT environment has the characteristics of scattered data sources，large data scale，and cloud?side collaborative distributed execution，which brings data flow control management，data transmission scheduling and many other challenges to the execution of IoT data workflows. Therefore，this article proposes a segmentation and scheduling method for IoT data workflow execution with considering the execution constraints and data transmission optimization problems. The method first models the execution constraints，edge node load and data transmission volume of IoT data workflow in a coherent way. And then，a segmentation algorithm for IoT data workflow and a sub?workflow execution scheduling algorithm under cloud?edge architecture with the goal of data transmission and execution time optimization are designed. The results of simulation experiments based on WorkflowSim show that compared with the typical HEFT and MINMIN algorithms，our algorithm effectively reduce the execution time of IoT data workflow under the conditions of guaranteeing edge node execution constraints and load balancing.

Key words: IoT workflow, split scheduling, data transmission optimization, multi?objective optimization, Internet of Things services

中图分类号: 

  • TP301

图1

IoT数据工作流分割调度方案"

图2

物联网云边系统架构"

图3

分割前的IoT数据工作流DAG"

图4

分割后的IoT数据工作流DAG"

图5

业务约束规则"

图6

节点资源约束规则"

图7

节点负载示意图"

图8

IoT数据工作流执行时间示意图"

表1

五个数据中心的配置"

数据中心主机数量宽带说明
Datacenter_011.5e7Edge
Datacenter_111.5e7Edge
Datacenter_211.5e7Edge
Datacenter_311.5e7Edge
Datacenter_430.75e7Cloud

表2

边缘节点及云计算中心的参数设置"

参数\节点边缘节点云中心
Mips30003000
Ram18002048
Storage1000010000
Bw1000010000

表3

虚拟机的参数配置"

参数\虚拟123
Size11008001100
Mips512512512
Ram10008001200
Bw10001200800

图9

仿真实验包含的两种工作流形式"

图10

本文算法和HEFT，MINMIN算法对工作流形式(1)的执行时间对比"

图11

本文算法和HEFT，MINMIN算法对工作流形式(2)的执行时间对比"

图12

本文算法和HEFT，MINMIN算法对工作流形式(1)的负载对比"

图13

本文算法和HEFT，MINMIN算法对工作流形式(2)的负载对比"

1 潘俊虹. 基于工作流和QoS的物联网服务组合技术研究. 武夷学院学报，2016，35(3)：59-62.
Pan J H. A reserch on IoT web service composition technology based on workflow and QoS. Journal of Wuyi University，2016，35(3)：59-62.
2 田倬璟，黄震春，张益农. 云计算环境任务调度方法研究综述. 计算机工程与应用，2021，57(2)：1-11.
Tian Z J，Huang Z C，Zhang Y N. Review of task scheduling methods in cloud computing environment. Computer Engineering and Applications，2021，57(2)：1-11.
3 陆艺雯. 基于智能电网的数据中心能源优化与任务调度方法研究. 硕士学位论文. 南京：南京航空航天大学，2019.
Lu Y W. Research on data center energy optimization and task scheduling methods based on smart grid. Master Dissertation. Nanjing：Nanjing University of Aeronautics and Astronautics，2019.
4 张龙信，王兰，肖满生，等. 异构云系统中预算成本约束下高效的工作流调度算法. 小型微型计算机系统，2020，41(6)：1182-1187.
Zhang L X，Wang L，Xiao M S，et al. Efficient work flow scheduling algorithm under cost budget constraint in heterogeneous cloud systems. Journal of Chinese Computer Systems，2020，41(6)：1182-1187.
5 Paknejad P，Khorsand R，Ramezanpour M. Chaotic improved PICEA?g?based multi?objective optimization for workflow scheduling in cloud environment. Future Generation Computer Systems，2021(117)：12-28.
6 Meena J，Vardhan M. Cost?effective heuristic workflow scheduling algorithm in cloud under deadline constraint. Recent Advances in Computer Science and Communications，2020，13(6)：1302-1317.
7 Qian Y F，Jiang Y Y，Hossain M S，et al. Privacy?preserving based task allocation with mobile edge clouds. Information Sciences，2020，507：288-297.
8 Chen P，Xia Y N，Yu C. A novel reinforcement?learning?based approach to workflow scheduling upon infrastructure?as?a?service clouds. International Journal of Web Services Research，2021，18(1)：21-33.
9 Dong T T，Xue F，Xiao C B，et al. Workflow scheduling based on deep reinforcement learning in the cloud environment. Journal of Ambient Intelligence and Humanized Computing，2021，12(12)：10823-10835.
10 陈俊宇，刘茜萍. 云环境下基于阶段划分的数据密集型工作流调度. 南京邮电大学学报(自然科学版)，2020，40(4)：103-110.
Chen J Y，Liu X P. Data?intensive workflow scheduling based on phase division in cloud environment. Journal of Nanjing University of Posts and Telecommunications (Natural Science Edition)，2020，40(4)：103-110.
11 李万清，刘辉，李忠金，等. 移动边缘计算环境下面向安全和能耗感知的服务工作流调度方法. 计算机集成制造系统，2020，26(7)：1831-1842.
Li W Q，Liu H，Li Z J，et al. Security and energy aware scheduling for service workflow in mobile edge computing. Computer Integrated Manufacturing Systems，2020，26(7)：1831-1842.
12 王柳婧，蒋一翔，徐元根. 基于多约束图分割机制的科学工作流调度. 计算机应用与软件，2019，36(10)：299-304.
Wang L J，Jiang Y X，Xu Y G. Scientific workflow scheduling algorithm based on multiple constraints graph division mechanism. Computer Applications and Software，2019，36(10)：299-304.
13 刘晓霞，李芳. 云环境中期限分割下工作流调度代价优化仿真. 实验室研究与探索，2018，37(10)：136-141，161.
Liu X X，Li F. Simulation on workflow scheduling cost optimization under deadline division in clouds. Research and Exploration in Laboratory，2018，37(10)：136-141，161.
14 薛凡. DAG分割模型下的云工作流调度策略. 计算机应用研究，2019，36(12)：3725-3728，3734.
Xue F. Cloud workflow scheduling strategy in DAG partition model. Application Research of Computers，2019，36(12)：3725-3728，3734.
15 Pei S J，Zhang Q G，Cheng X H. Workflow scheduling using graph segmentation and reinforcement learning. International Journal of Performability Engineering，2020，16(8)：1262-1270.
16 薛庆水，李凤英. 基于云环境的双QoS约束多目标工作流调度. 计算机工程与设计，2019，40(8)：2196-2203.
Xue Q S，Li F Y. Multi?objective workflow scheduling with Bi?QoS constraint based on cloud environment. Computer Engineering and Design，2019，40(8)：2196-2203.
17 袁友伟，黄锡恺，俞东进，等. 移动边缘计算环境下服务工作流容错调度算法. 计算机集成制造系统，2021，27(6)：1693-1702.
Yuan Y W，Huang X K，Yu D J，et al. Fault?tolerant scheduling algorithm for service workflow in MEC environment. Computer Integrated Manufacturing Systems，2021，27(6)：1693-1702.
18 钟诗奇，龚晓峰. 基于改进粒子群算法的云工作流调度. 电子设计工程，2019，27(20)：110-114.
Zhong S Q，Gong X F. Cloud workflows scheduling based on improved particle swarm optimization algorithm. Electronic Design Engineering，2019，27(20)：110-114.
19 薛凡，吴志健. 基于粒子群优化的云工作流任务调度. 微电子学与计算机，2018，35(8)：122-127，131.
Xue F，Wu Z J. Cloud workflow wasks scheduling based on particle swarm optimization. Microelec?tronics & Computer，2018，35(8)：122-127，131.
20 韩莉. 实时系统工作流的能量感知容错算法. 博士学位论文. 上海：华东师范大学，2020.
Han L. Fault?tolerant and energy?aware algorithms for workflows and real?time systems. Ph.D. Dissertation. Shanghai：East China Normal University，2020.
[1] 李二超，马玉泉. 基于就近取值策略的离散多目标优化[J]. 南京大学学报(自然科学版), 2018, 54(6): 1216-1224.
[2] 谢顺平1,2,3*，都金康1,2,3，冯学智1,2,3，李智广1 . 融雪径流模型参数渐进式优化率定方法[J]. 南京大学学报(自然科学版), 2015, 51(5): 1005-1013.
[3] 林忆南1，金 晓斌1*，李效顺2，郭贝贝1，周寅康1. 渭北黄土台塬区水资源约束下的种植业结构多目标优化研究[J]. 南京大学学报(自然科学版), 2014, 50(2): 211-.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!

版权所有 © 2021 《南京大学学报(自然科学)》

地址：江苏省南京市鼓楼区汉口路22号，南京大学学报编辑部，210093

电话：025-83592704 , 传真：025-83592704        技术支持：北京玛格泰克科技发展有限公司