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

doi:10.13232/j.cnki.jnju.2022.01.015

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

秦生辉¹^,², 赵卓峰^,¹^,², 杨中国¹^,²

1.北方工业大学信息学院，北京，100144

2.大规模流数据集成与分析技术北京市重点实验室，北京，100144

Segmentation and scheduling method for IoT data workflow

Qin Shenghui¹^,², Zhao Zhuofeng^,¹^,², Yang Zhongguo¹^,²

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

通讯作者: E⁃mail：edzhao@ncut.edu.cn.

收稿日期: 2021-09-22

基金资助:

国家重点研发计划.  2018YFB1402500
国家自然科学基金国际合作与交流项目.  62061136006
北京市自然科学基金.  4202021

Received: 2021-09-22

摘要

物联网数据是当前一类典型的大数据，其应用正成为诸多行业领域的热点，围绕物联网数据的应用往往可以被表示为由一组大数据处理与分析任务构成的工作流.与传统工作流不同的是，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.

Keywords： IoT workflow ; split scheduling ; data transmission optimization ; multi⁃objective optimization ; Internet of Things services

PDF (1002KB) 元数据多维度评价相关文章导出 EndNote| Ris| Bibtex 收藏本文

本文引用格式

秦生辉, 赵卓峰, 杨中国. 面向IoT数据工作流的分割与调度方法. 南京大学学报（自然科学）[J], 2022, 58(1): 153-162 doi:10.13232/j.cnki.jnju.2022.01.015

Qin Shenghui, Zhao Zhuofeng, Yang Zhongguo. Segmentation and scheduling method for IoT data workflow. Journal of nanjing University[J], 2022, 58(1): 153-162 doi:10.13232/j.cnki.jnju.2022.01.015

随着物联网建设的发展，逐渐产生并积累了大量各种各样的物联网数据，围绕这些数据的各类智能应用成为当前的热点.在物联网场景下，传感器数据、采集的实时视频数据等需要经过多个处理任务最终为智能决策服务.这些处理任务涉及数据采集、分布式数据查询和个性化数据分析等任务，这些任务可以以工作流的形式进行组织表示，这种形式的工作流被称为IoT（Internet of Things）数据工作流^［1］.同时，由于物联网应用系统网络拓扑分散、数据传输代价高等特点以及低处理时延和一定的数据隐私保护等需求，如何借助云边协同的方式对IoT数据工作流任务进行有效地划分和调度就成为此类IoT应用的关键.

区别于传统工作流，针对IoT数据处理的工作流具有诸多新的特点：IoT数据工作流的执行环境不再是集中的节点或集群，而是需要在IoT云边端网络架构下进行执行调度；IoT数据工作流任务涉及大量数据采集和处理工作，任务之间的数据流流量也较大；参与IoT数据工作流执行的节点资源及负载能力也不同.这些都给IoT数据工作流执行调度的研究带来了新的挑战^［2］.

例如，在智能电网业务中，终端传感器及监控设备不断产生大量数据，尤其是终端设备，产生的数据量大且有效信息较少，在传输过程中还会占用大量网络资源^［3］.而在大多数业务场景下，由于数据源等业务约束条件，部分任务需要指定节点执行，云边协同模式给这种业务场景提供了较好的执行环境.为了严格遵守约束条件，流程分割是一个有效的方法，在此基础上进行优化，可以有效地避免大量数据传输造成的时延.

为了应对上述挑战，一个基本的思路就是对IoT数据工作流进行有效切分并调度到合适的IoT节点执行，但将工作流切分成任务进行调度的方式往往会破坏工作流任务执行的关联依赖，而实际应用中往往存在一些业务约束^［4］，规定工作流的局部连续任务必须调度特定节点执行.所以，这部分任务应以工作流的形式进行调度执行，这样既可以保证局部连续任务的工作流模型不受破坏，保障任务之间的关联关系，又可以遵循业务约束将其调度到特定节点.基于这种方法的优势，工作流分割的概念被提出，即约束条件下的工作流分割.

基于上述思路，本文针对IoT数据工作流的执行约束和数据传输优化问题，提出一种面向IoT数据工作流的分割与调度优化方法.首先对IoT数据工作流的执行约束条件、边缘节点负载以及数据传输量进行建模，进而以数据传输和执行时间优化为目标设计一种云边架构下IoT数据工作流的分割算法和子工作流执行节点调度算法.算法将约束条件下的工作流依据数据传输量进行优化分割得到子工作流，进而对于子工作流根据节点资源及负载和业务约束情况设计调度算法，从而优化IoT数据工作流在云边协同模式下的数据传输、执行时间及执行节点负载.

1 相关工作

近年来，IoT数据量飞速增长，与其相关的工作流调度也成为一个非常重要的问题，许多学者对工作流调度进行了大量研究.文献［5-7］考虑用户对于时间的约束、服务质量的约束以及隐私保护，通过多目标优化提高了服务质量.Chen et al^［8］提出一种方法，可以为工作流的每个任务寻找最合适的资源以满足用户需求.Dong et al^［9］在任务优先级约束条件下实现了执行时间的最小化.陈俊宇和刘茜萍^［10］提出一种云环境下基于阶段划分的数据密集型工作流调度方法，基于数据依赖将工作流划分为多个阶段，然后对任务进行调度，优化工作流的执行时间.李万清等^［11］提出面向安全和能耗感知的服务工作流调度方法，在降低移动应用调度风险率的同时最小化设备能耗.王柳婧等^［12］提出一种基于多约束图分割的工作流调度算法，通过有向边的修剪，在所有维度上实现权重和的均衡，得到最小化的任务间数据传输量，降低通信代价.刘晓霞和李芳^［13］提出一种期限分割的工作流调度代价优化算法，将工作流任务的调度过程划分为四个阶段：工作流分层、期限分割、任务选择和实例选择，降低工作流执行代价.薛凡^［14］提出一种基于有向无环图分割的工作流调度算法，分割阶段确保任务的执行顺序依赖并对任务进行重分配，有效优化调度效率和调度代价.Pei et al^［15］提出一种基于云异构平台的数据密集型工作流调度采用图划分和强化学习的云调度算法，通过图划分算法将数据依赖性强的任务聚类成块以降低任务执行过程中的成本和时间开销.

以上研究大多考虑工作流的执行时间成本和诸多约束条件并以任务为实例进行调度，优化数据传输时延，也有效降低了移动边缘环境下工作流任务调度的隐私泄露风险.同时，也提出了一些基于约束工作流任务依赖和数据依赖的分割调度算法，但多是基于单目标的分割优化，对数据密集型且具有多约束条件的工作流并不适用.

工作流的本质是一种自动化的执行流程，其任务与任务间有相应的依赖关系，IoT数据工作流的调度约束往往在某几个相邻依赖的任务之间，即此部分关联任务有相同的业务约束和数据源依赖.因此本文提出一种IoT数据工作流分割调度方法，基于资源约束、业务约束和数据传输进行分割优化，并根据业务约束、节点资源及节点负载等进行调度优化，在保证业务约束的同时通过工作流分割的方法将服务调度之间的数据传输最小化，并保留工作流的局部依赖关系；然后根据约束条件对分割后的工作流进行调度优化，使节点负载保持均衡的同时最小化工作流的执行时间.

2 研究内容

针对目前IoT数据工作流调度领域存在的问题，本文将基于分割和调度两方面进行研究，最终通过实验证明该研究方案的有效性.整体的方案架构如图1所示.

图1

新窗口打开| 下载原图ZIP| 生成PPT

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

Fig.1 IoT data workflow segmenting and scheduling scheme

2.1　IoT数据工作流分割

基于任务的调度和基于工作流的调度有很大的不同.IoT数据工作流的部分任务有一定的业务约束，如部分连续任务由于执行环境约束或者为了保护一些隐私数据需要在特定节点执行，在这种情况下，工作流的部分连续任务需要调度到同一节点执行.若基于任务调度，在调度过程中就需要考虑每个任务的开始时间、结束时间以及两个连续任务之间的数据传输时间，以保证各个任务执行的先后关系；若基于工作流调度，这部分任务构成局部子工作流，在调度过程中，只需考虑此子工作流的开始时间以及结束时间，从而既满足约束条件又可以保证此部分任务的关联关系.

本文首先根据业务约束条件确定工作流分割位置的初始值，然后对工作流的分割位置进行优化.任务之间的数据传输量是一个重要的考虑因素，各个子工作流之间的数据传输量将极大影响后继工作流的开始时间，进而影响整个工作流的执行时间，故以各任务之间的数据传输量作为分割位置的优化目标，在约束条件下基于任务之间的数据传输量进行优化，得到工作流的最优分割位置，以确保约束条件下各个子工作流之间的数据传输量最小.

2.2　子工作流调度

IoT数据工作流的执行环境主要有两种：边缘协同模式和云边协同模式.边缘协同模式指应用在某边缘服务器提出形成工作流，由于边缘节点的位置优势，工作流在附近边缘节点调度执行；云边协同模式指应用在云端提出，不同业务可以调度到特定边缘节点执行，而对于业务量较大或者计算资源需求较高的子工作流可以在云中心执行.总体上，子工作流的调度基于业务约束，该业务约束指子工作流必须调度到特定的某个节点或某几个节点，在此约束的基础上需要考虑节点资源及负载，将子工作流优先调度到资源能力较高、负载较小的节点上执行.

2.3　总结

通过以上分析，得到如下结论：

（1）IoT数据工作流的分割主要考虑以约束条件下工作流各任务之间的数据传输量作为分割位置的优化目标.

（2）子工作流的调度主要考虑约束条件下子工作流执行节点的计算资源及负载.

本文考虑IoT数据工作流的分割调度优化问题，通过WorkflowSim仿真平台进行实验，证明该方法的可行性及有效性.

3 IoT数据工作流系统架构及相关定义

3.1　系统架构

如图2所示，在物联网环境下，IoT数据工作流系统涉及的数据存储和计算的主要参与者为云计算中心服务器集群和边缘计算节点，云中心和边缘节点均由多个虚拟机组成，其中边缘节点的计算能力有限，但IoT设备接收的数据可直接存储在最近的边缘服务器上，此数据传输时延可忽略不计，暂且认为边缘节点可以满足其附近IoT设备所接收数据的存储容量.此外，对于同一业务场景，其多个边缘节点距离较近，故其之间的数据传输时延较小.云计算中心服务器集群具有较强的计算能力，可以满足较大规模的计算任务，但边缘IoT设备的数据传输至云中心需要较高的传输开销.

图2

新窗口打开| 下载原图ZIP| 生成PPT

图2 物联网云边系统架构

Fig.2 IoT cloud⁃edge system architecture

3.2　相关定义

3.2.1　任务间的数据传输

分割前的IoT数据工作流采用有向无环图DAG （Directed Acyclic Graph）描述，记为ODAG，如图3所示.记为 $O G = (T, E)$ ，其中， $T$ 为任务顶点的集合， $T = \{T_{1}, T_{2}, T_{3}, \dots, T_{n}\}$ 表示云工作流由n个依赖任务组成； $E$ 为有向边的集合， $E = \{(T_{i}, T_{j}, D a t a_{i j}) :$

图3

新窗口打开| 下载原图ZIP| 生成PPT

图3 分割前的IoT数据工作流DAG

Fig.3 IoT data workflow DAG before segmentation

$(T_{i}, T_{j}) \in T\} . (T_{i}, T_{j}, D a t a_{i j})$ 表示任务和任务之间的依赖关系，任务 $T_{i}$ 是任务 $T_{j}$ 的前驱任务，任务 $T_{j}$ 是任务 $T_{i}$ 的后继任务， $D a t a_{i j}$ 表示任务 $T_{i}$ 传递给任务 $T_{j}$ 的数据量大小.

3.2.2　子工作流之间的数据传输

在IoT数据工作流分割之后形成子工作流，也采用有向无环图描述，记为SDAG，即将每个子工作流作为一个顶点，将各个子工作流之间的依赖关系作为一条边，从而将ODAG化简，如图4所示.记为 $O G = (P, R)$ ，其中， $P$ 为子工作流的集合， $P = \{P_{1}, P_{2},$

图4

新窗口打开| 下载原图ZIP| 生成PPT

图4 分割后的IoT数据工作流DAG

Fig.4 Segmented IoT data workflow DAG

$P_{3}, \dots, P_{m}\}$ 表示原工作由m个子工作流组成； $R$ 为表示各子工作流之间的依赖关系的边的集合， $R = \{(P_{i}, P_{j}, D a t a_{i j}) : (P_{i}, P_{j}) \in P\}$ . $(P_{i}, P_{j}, D a t a_{i j})$ 表示各子工作流之间的依赖关系，工作流 $P_{i}$ 是工作流 $P_{j}$ 的前驱工作流，工作流 $P_{j}$ 是工作流 $P_{i}$ 的后继任务， $D a t a_{i j}$ 表示工作流 $P_{i}$ 传递给工作流 $P_{j}$ 的数据量大小.

3.2.3　执行时间

分割之前的IoT数据工作流的执行时间取决于其执行环境模式、子工作流之间的数据传输量和节点资源计算能力.

每个子流程都会被分配到某个云中心或边缘节点的虚拟机，每个子流程都有执行的开始时间和结束时间，记为 $s c h e d (P_{i}) = (v m_{j}, S P_{P_{i}}, E P_{P_{i}})$ ，其中， $v m_{j}$ 表示子工作流 $P_{i}$ 分配到 $v m_{j}$ 类型的虚拟机上执行， $S P_{P_{i}} 表示子工作流 P_{i}$ 的开始时间， $E P_{P_{i}}$ 表示子工作流 $P_{i}$ 的结束时间.子工作流 $P_{i}$ 的开始时间 $S P_{P_{i}}$ 由 $P_{i}$ 所有的前驱子工作流执行完毕后将数据传输到子工作流 $P_{j}$ 所在虚拟机的时间决定，子工作流 $P_{i}$ 的结束时间 $E P_{P_{i}}$ 等于 $P_{i}$ 的执行时间加上其开始时间 $S P_{P_{i}}$ ，如式（1）和式（2）所示：

E P_{P_{i}} = S P_{P_{i}} + \frac{w o r k (P_{i})}{P_{v m_{j}}}

(1)

S P_{P_{i}} = m a x \{E P_{P_{h}} + \frac{D a t a (P_{h i})}{b} : P_{h} \in p r e (P_{i})\}

(2)

$E P_{P_{h}} 为前驱$ 工作流 $P_{h} 的结束$ 时间， $\frac{D a t a (P_{h i})}{b}$ 为数据从 $P_{h} 传输$ 到 $P_{i} 的$ 时间. $b$ 为节点之间的数据传输速率：边缘协同模式下数据传输速率较高，即 $b$ 较大；云边协同模式下由于节点距离较远，数据传输速率较低，即 $b$ 较小.

$w o r k (P_{i})$ 为工作流 $P_{i}$ 的指令数， $P_{v m_{j}} 为 v m_{j}$ 每秒处理的指令数.从第一个子工作流开始执行到最后一个子工作流完成的时间段称为整个IoT数据工作流的完成时间，因而整个IoT数据工作流的完成时间如式（3）所示：

m a k e s p a n = m a x \{E P_{P_{h}} : P_{i} \in P\}

(3)

4 IoT数据工作流分割调度方法

对于IoT数据工作流，通过基于约束条件下的分割调度方法，实现最小化IoT数据工作流执行时间的目标.本节首先对于执行环境及约束条件进行详细分析，抽象建模，形成系统模型和分割调度的约束模型；其次使用粒子群优化算法设计IoT数据工作流调度算法解决多目标优化问题.

4.1　IoT数据工作流分割调度问题

IoT数据工作流的调度具有诸多约束和可优化点，以下将给出具体模型.

4.1.1　业务约束

业务约束指数据隐私保护约束，即受约束任务的数据源或运行场景固定，必须在指定的一个或多个节点上执行.本文在业务约束的基础上进行IoT数据工作流的分割优化和调度优化.

将调度范围的位置进行独热编码，每个地理位置都是一个长度为N的串，N为所有的位置个数，该串中只有一个数为1，其他数均为0，如图5所示.在这种表示方式下，如果需要数据的位置决定计算任务的位置，就必须满足式（4）：

l o c a t i o n_{d a t a} \cdot l o c a t i o n_{t a s k} = 1

(4)

其中， $l o c a t i o n_{d a t a}$ 是受到约束的数据集的位置向量， $l o c a t i o n_{t a s k}$ 是对应该数据处理任务的位置向量.

图5

新窗口打开| 下载原图ZIP| 生成PPT

图5 业务约束规则

Fig.5 Business constraint rules

4.1.2　节点资源

边缘节点具有离数据源近的特点，但其计算能力有限，节点资源的计算能力是影响子工作流调度的重要因素.考虑边缘节点的计算能力不能满足某些子工作流的执行，表示为 $R_{P_{k}} \leq C_{i}$ ，如图6所示.

图6

新窗口打开| 下载原图ZIP| 生成PPT

图6 节点资源约束规则

Fig.6 Node resource constraint rules

4.1.3　节点负载

云中心集群和边缘节点集群作为IoT数据工作流的执行载体，必须保证其稳定正常运行，节点负载均衡可有效保障整个系统的正常平稳运行，所以在调度过程中保证集群各节点的负载均衡对于工作流执行的稳定性具有重要意义.节点负载如图7所示.

图7

新窗口打开| 下载原图ZIP| 生成PPT

图7 节点负载示意图

Fig.7 Node load balancing diagram

计算资源节点j （j=1，2，…，K，K为资源节点总数）上分配的子工作流数量来表示资源节点执行子工作流的频度，用 $N_{j}$ 表示.假定每个集群中的各个节点计算能力相同，则单个集群的资源节点利用率如式（5）所示：

r = \frac{\sum_{j = 1}^{k} N_{j}}{K \cdot \underset{j \leq K}{m a x} N_{j}} \times 100 %

(5)

这里采用均衡度来表示.在优化的过程中，需要让 $r$ 尽可能靠近1.

此外，本文使用多个集群（云中心集群及各个边缘集群）的平均负载 $\frac{r}{N}$ （ $N$ 为集群数量）作为优化目标.

4.1.4　数据传输时延

由于云中心集群和边缘节点位置分布不一致，云中心距离边缘节点较远，同一业务场景的边缘节点之间距离较近.计算方式如式（6）所示：

T_{h i} = \{\begin{matrix} 0 l_{h}^{i} = c_{1} \\ \frac{D a t a (P_{h i})}{b} l_{h}^{i} = c_{2} \\ d + \frac{D a t a (P_{h i})}{b} l_{h}^{i} = c_{3} \end{matrix}

(6)

其中，

$c_{1}$ ：子流程 $P_{h}$ 与 $P_{i}$ 部署在相同的边缘节点；

$c_{2}$ ：子流程 $P_{h}$ 与 $P_{i}$ 分别部署在不同的边缘节点；

$c_{3}$ ：子流程 $P_{h}$ 与 $P_{i}$ 分别部署云端及边缘节点.

d为受节点距离影响而增加的额外的传输时延，本文认为边缘节点之间无额外传输时延.图8为数据传输时延及执行时间示意图.

图8

新窗口打开| 下载原图ZIP| 生成PPT

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

Fig.8 IoT data workflow execution time diagram

4.2　分割算法

业务约束是分割位置优化的前提，当任务的 $l o c a t i o n_{t a s k}$ 相等时，则这些任务属于同一个约束集合.在约束条件的基础上给出以下分割优化算法，根据数据传输量对业务约束集合进行进一步优化，得到新的任务集合.

算法步骤如下：

（1）将与约束任务有关联关系的无约束任务并入约束任务集合：将每个约束任务集合中的内部数据传输量的平均值作为一个数据传输量的阈值 $W$ ，从约束任务集合的任务遍历ODAG中的无约束任务，若两个相邻任务之间的数据传输量大于该阈值 $W$ ，则将后继任务并入该约束任务集合，并继续遍历，若小于 $W$ ，则此次遍历结束.从下一个约束任务集开始遍历，重复以上步骤.

（2）未并入的有关联关系的无约束任务组成新的任务集合：从ODAG的开始节点遍历，将连续的无约束任务组成新的任务集合.

（3）在任务集合中进一步优化分割位置：若该任务集合允许被调度到多个服务节点，则可以进一步根据阈值 $W$ 将该集合分成多个.

4.3　子工作流执行调度方法

本文的研究目标是最小化IoT数据工作流的执行时间，并且使各个集群的节点利用率趋于均衡.

4.3.1　多目标优化调度

一般地，多目标优化问题是在多种约束条件下，为求解的多目标函数寻找一组决策变量值和目标函数值^［16］.比如，一个多目标最小化问题包括n个决策变量、r个优化目标以及m个约束条件，就可以表示为式（7）：

\{\begin{matrix} m i n f (x) = [f_{1} (x), f_{2} (x), \dots, f_{n} (x)] \\ g_{i} (x) \geq 0 (i = 1,2, \dots, k) \\ h_{j} (x) = 0 (j = 1,2, \dots, l) \end{matrix}

(7)

其中，r表示需要优化的目标数量.本文的调度优化中仅有一个优化目标：IoT数据工作流执行时间.问题中的每个解决方案x都包含两个变量：一个变量包含n个值 $(x_{1}, x_{2}, \dots, x_{n})$ ，n是一个IoT数据工作流实例中分割之后的子流程个数 $(n = |P|)$ ， $x_{i} = S (P_{i})$ 表示调度虚拟资源 $x_{i}$ 上的子工作流 $(P_{i} \in P)$ ；另一个变量是大小为n的数列，表示子工作流被调度的顺序. $g_{i}$ 和 $h_{j}$ 是问题的约束条件.如果x均达到这些约束条件的要求，就可以将这个x记为其一个可行解.因此，问题的可行解集合可以表示为式（8）：

Ω = \{x |g_{i} (x) \geq 0 (i = 1,2, \dots, k), h_{j} (x) = 0 (j = 1,2, \dots, l)\}

(8)

在此前的分割优化过程中已将具有相同约束条件的任务优化分割到同一子工作流中，因此在调度过程中，子工作流的约束条件即为它们指定服务节点进行调度.则调度优化算法的目标可以表示为式（9）：

\{\begin{matrix} f (x) = m i n (T w_{t o t a l}, S l_{t o t a l}) \\ S (p_{i}) = r_{m} p_{i} \in P, r_{m} \in d c_{p} \end{matrix}

(9)

其中， $T w_{t o t a l}$ 和 $S l_{t o t a l}$ 指算法的优化目标，即IoT数据工作流的执行时间和系统的平均负载； $S (p_{i})$ 是算法的约束条件， $p_{i}$ 和 $d c_{p}$ 分别是具有业务约束的子工作流和为其指定的服务节点， $r_{m}$ 是服务节点 $d c_{p}$ 上子工作流 $p_{i}$ 所需要的资源.

4.3.2　基于粒子群的子工作流调度算法

为了解决上述多目标优化问题，采用粒子群优化（Partical Swarm Optimization，PSO）算法^［17-19］.PSO采用群体智能搜索模式在搜索空间上逐步寻找解决优化问题的一个解决方案，通过该算法将得到子工作流和虚拟机的最佳映射.

类似其他进化算法，在PSO算法中，种群是求解空间中全部的粒子.粒子随机初始化，每个粒子都由一个适应值表示.在每一代优化时，适应值都由一个适应值函数进行评估，本文的适应值如式（10）所示：

F i t n e s s = (r t \times 5 + 1000 \times (1 - a l) \times 5) / 10

(10)

其中， $r t$ 为执行时间， $a l$ 为平均负载.

每个粒子知道它自己的最佳位置 $P_{b e s t}$ 和到目前为止整个种群中最佳的粒子位置 $G_{b e s t}$ ，因此在搜索过程中粒子总是趋向更好的搜索区域移动.一个粒子的 $P_{b e s t}$ 是该粒子迄今达到的最佳位置（适应值）， $G_{b e s t}$ 是对整个种群而言的最佳位置.粒子具有引导粒子移动的速度和评估粒子适应值的位置，每一次迭代过程中，粒子会通过追踪两个极值来更新自己.在每一代中，粒子的速度和位置会根据式（11）和式（12）更新：

\begin{array}{l} V_{i}^{k + 1} = ω V_{i}^{k} + \\ c_{1} r_{1} ({P_{b e s t}}_{i} - X_{i}^{k}) + c_{2} r_{2} (G_{b e s t} - X_{i}^{k}) \end{array}

(11)

X_{i}^{k + 1} = X_{i}^{k} + V_{i}^{k + 1}

(12)

其中， $V_{i}^{k + 1}$ 是粒子 $i$ 在第 $k + 1$ 次迭代时的速度， $V_{i}^{k}$ 是粒子 $i$ 在第 $k$ 次迭代时的速度， $ω$ 是惯性权重， $c_{1}$ 和 $c_{2}$ 是加速系数， $r_{1}$ 和 $r_{2}$ 是0到1之间的随机数， $X_{i}^{k}$ 是粒子 $i$ 在第 $k$ 次迭代时的位置， $X_{i}^{k + 1}$ 是粒子 $i$ 在第 $k + 1$ 次迭代时的位置， ${P_{b e s t}}_{i}$ 是第 $i$ 个粒子目前为止达到的最好位置， $G_{b e s t}$ 是对整个种群而言最佳的粒子位置.

算法过程如下：

（1）在搜索空间中，随机初始化粒子种群，每个粒子有自己的速度和位置.

（2）计算所有粒子的适应值，设置每个粒子的 ${P_{b e s t}}_{i}$ 等于它当前的位置，设置 $G_{b e s t}$ 等于最好的初始粒子.

（3）根据式（11）和式（12）更新每个粒子的速度和位置.

（4）将每个粒子的位置映射到求解空间并根据适应值函数式（10）评估粒子的适应值.

（5）比较每个粒子当前适应值和其个体最佳适应值 $P_{b e s t}$ .如果当前适应值更好，就更新 $P_{b e s t}$ 为当前的粒子.

（6）选取当前整个种群中拥有最佳适应值的粒子，如果当前粒子的适应值比 $G_{b e s t}$ 好，那么更新 $G_{b e s t}$ 为当前粒子.

符合停止条件输出 $G_{b e s t}$ 和它的适应值，否则，跳转到步骤（2）继续执行.正如式（11）和式（12）所示，最初的PSO用来解决连续的优化问题，但是任务分配问题是离散的，因此，速度更新的计算改为式（13）：

\begin{array}{l} V_{i}^{k + 1} = \\ ⌊ω V_{i}^{k} + c_{1} r_{1} ({P_{b e s t}}_{i} - X_{i}^{k}) + c_{2} r_{2} (G_{b e s t} - X_{i}^{k})⌋ \end{array}

(13)

其中，粒子速度的范围为 $[- v m N u m, v m N u m]$ ， $v m N u m$ 为虚拟机的数量，若速度更新后超出此范围则取其边界值；粒子位置的范围为 $[0, v m N u m - 1]$ ，若位置更新后超出此范围则取其边界值.

5 实验评估

5.1　实验设置

实验模拟IoT数据工作流在云边环境下的调度问题，模拟四个边缘节点以及一个云计算中心，并与工作流调度领域的经典算法HEFT算法和MINMIN算法^［20］作对比，以验证本文优化方法的正确性及有效性.

5.2　平台

实验设计和算法实现基于WorkflowSim仿真平台，该仿真平台在CloudSim平台的基础上增加了工作流应用的资源配置和任务调度的支持.算法实现和相关对比算法的实现用Java编程语言完成.所有实验在同一配置（Intel（R）Core（TM）i7⁃9750CPU@2.60 GHz，16 G内存）的Windows10机器上进行.

5.3　WorkflowSim中数据中心和虚拟机配置

实验在五个不同地理位置的数据中心下进行，前四个数据中心代表四个边缘计算节点，剩下的一个数据中心代表云计算中心.前四个数据中心每个数据中心配置一台主机，第五个数据中心配置三台主机，如表1所示.边缘节点及云计算中心的参数设置如表2所示.

表1 五个数据中心的配置

Table 1 Configuration of five data centers

数据中心	主机数量	宽带	说明
Datacenter_0	1	1.5e7	Edge
Datacenter_1	1	1.5e7	Edge
Datacenter_2	1	1.5e7	Edge
Datacenter_3	1	1.5e7	Edge
Datacenter_4	3	0.75e7	Cloud

新窗口打开| 下载CSV

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

Table 2 Parameter configuration of edge nodes and cloud computing centers

参数\节点	边缘节点	云中心
Mips	3000	3000
Ram	1800	2048
Storage	10000	10000
Bw	10000	10000

新窗口打开| 下载CSV

同时，实验还配置了三种类型的虚拟机，每种类型10个，随机分配给五个数据中心.虚拟机的参数配置如表3所示.

表3 虚拟机的参数配置

Table 3 Parameter configuration of virtual machines

参数\虚拟	1	2	3
Size	1100	800	1100
Mips	512	512	512
Ram	1000	800	1200
Bw	1000	1200	800

新窗口打开| 下载CSV

5.4　工作流实例配置

仿真实验采用WorkflowSim平台提供的工作流实例，包含两种形式的数据工作流，如图9所示.每种包含四种不同任务数量的工作流 $Q w \in \{30,50,100,1000\}$ ，在这两个工作流的基础上根据IoT数据工作流特征进行了扩展，为每个任务设置了随机的约束条件，使该任务在某服务节点上具有数据和业务约束.约束规则见4.1.1.

图9

新窗口打开| 下载原图ZIP| 生成PPT

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

Fig.9 Two workflow forms included in the simulation experiments

5.5　结果分析

通过对比实验可以发现，对于第一种形式的工作流，其各个任务之间的数据依赖较复杂，所以在具有业务约束时，本文的分割调度优化方法对工作流执行时间的优化效果比HEFT算法更明显，与MINMIN算法效果较为接近，如图10所示.而对于第二种形式的工作流，其任务之间的数据依赖较简单，在业务约束条件下，本文的分割优化方法对于工作流执行时间的优化效果与HEFT，MINMIN算法较接近，如图11所示.

图10

新窗口打开| 下载原图ZIP| 生成PPT

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

Fig.10 Execution time of our algorithm with HEFT and MINMIN algorithm for workflow form (1)

图11

新窗口打开| 下载原图ZIP| 生成PPT

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

Fig.11 Execution time of our algorithm with HEFT and MINMIN algorithm for workflow form (2)

此外，对节点平均负载也做了较明显的优化.与HEFT和MINMIN算法相比，本文优化方法使节点平均负载更接近1，从而更好地保障了节点稳定性，如图12和图13所示.

图12

新窗口打开| 下载原图ZIP| 生成PPT

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

Fig.12 Load balancing of our algorithm with HEFT and MINMIN algorithm for workflow form (1)

图13

新窗口打开| 下载原图ZIP| 生成PPT

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

Fig.13 Load balancing of our algorithm with HEFT and MINMIN algorithm for workflow form (2)

6 结论

在云边协同环境下，IoT数据工作流数据量大、数据源分散，所以IoT数据工作流各任务之间的数据依赖较复杂，且调度时数据传输不可避免.本文通过在IoT数据工作流的多目标优化调度之前加入分割优化方法来优化数据传输，通过实验评估，该方法可以有效优化IoT数据工作流在业务约束条件下调度时的执行时间，有效提高了服务质量，并且使各个节点的平均负载更加均衡，使得系统工作更加稳定.未来将针对具体的IoT工作流做进一步的分割和调度优化.

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

潘俊虹

基于工作流和QoS的物联网服务组合技术研究

武夷学院学报，2016，35(3)：59-62.