基于聚类的非中心化工作流的适应性切片方法

叶 鑫，李 佳，梁继伟，尹智刚

（大连理工大学 信息与决策技术研究所，辽宁 大连116024）

0 引 言

非中心化工作流如何进行切片，以实现工作流片段在多个服务器间的调度问题已成为理论研究与实践中的热点问题［1］。非中心化的工作流根据其特点主要可分为计算和数据密集型［2－5］和实例密集型［6－9］两类。区别于计算和数据密集型工作流，实例密集型工作流的最大特点是实例中活动所需的计算能力较低、数据量较小，但存在大量需要运行的工作流实例，对响应时间和执行效率提出了严峻的挑战。文献 ［10］指出该类工作流广泛存在于连锁经营、在线零售、电子政务和医疗保险等行业中，由大量分散在不同服务器上的服务集之间复杂的交互来组成，最终将被数以万计的工作流实例来实现。

当前，一些学者为提升非中心化工作流的响应时间和执行效率，提出了相应工作流的切片方法，主要可以分为静态和动态的工作流切片方法两类。

静态工作流切片方法是在设计时而非工作流执行时进行切片的［11，12］，虽然可相对提高工作流执行效率，但是由于其主观性较强，而且没有考虑工作流的执行环境，因此无法根据执行环境的改变做出动态调整，而动态工作流切片方法可弥补这些不足［7，13］。如文献 ［13］提出一种基于流程挖掘的工作流分布方法，该方法根据流程日志，利用apriori算法挖据工作流中最相关的活动，并将这些活动封装在同一个代理上去执行；文献 ［14］提到了另外一种针对客户行为的工作流中频繁路径的挖据方法－GSP算法，以提升挖据效率；文献 ［8］在文献 ［13］的基础之上提出了HIPD （分层智能流程非中心化）方法，该方法将工作流的频繁路径挖掘和流程树分层结合起来进行工作流片段的切分，最后将频繁交互的活动封装为一个工作流片段，并分配在相同的代理中执行，从而减少活动间的通信时间，并使得工作流切片更具灵活性，以适应工作流执行环境的变化。

综上所述，动态的工作流切片方法为本文的研究提供了良好的基础与借鉴，但还主要存在以下问题：①部分方法主要考虑了活动的执行频次，忽视了活动间的依赖关系；②考虑因素不全面，缺少对工作流活动间的通信量的关注；③不能很好适应工作流的执行环境。这些问题的存在将会影响到工作流执行的响应时间和吞吐量。因此，本文针对这些问题的改进进行研究，旨在减少工作流的响应时间，提高工作流的执行效率。

1 基于层次聚类法的非中心化工作流的切片方法

为减少实例密集型非中心化工作流的响应时间并提升其执行效率，应在综合考虑活动执行频次等因素的前提下，尽可能的将通信频繁且通信量大的活动分配在同一台服务器上执行，亦即将这些活动划分到一个工作流片段中。而聚类分析是数据挖掘中的一种数据划分或分组处理的重要手段和方法。如果将通信频繁且通信量大的活动看作为相似，则可将聚类分析中的类别看作为工作流片段。因此，可应用聚类分析对工作流进行切片，但须对其类间距离的定义进行修订。另外，由于执行环境的不确定性等因素，因此借鉴凝聚层次聚类法的思路对工作流进行切片，以提高切片结果对执行环境的适应性。

1.1 基本定义

基于BPMN 规范，一个工作流模型可被抽象为一个有向无环图 （DAG）。图中的节点可分为活动和网关两类。相关的基本定义如下。

定义1 活动 （或任务）。活动是工作流中的最基本的元素，也是工作流切片的基本单元，令ai表示工作流中的第i个活动，则A＝｛ai｜i＝1，2…，n｝表示工作流中所有活动的集合。

定义2 工作流片段 （或类）。工作流片段表示切片过程中所产生的活动集合，亦可看作为聚类分析中的类。令ci表示第i 个工作流片段，则ciA。特别的，当某工作流片段只包含1 个活动时，该工作流片段等价与活动。令clusterk＝ ｛ci｜i＝1，2…，l｝，k＝1，2…m 表示第k次聚类时的所有工作流片段的集合。

定义3 活动间的偏序关系与工作流片段间的偏序关系。其中，如果在DAG 图中存在一条从ai指向aj的路，且除ai和aj外，路上无其它节点或只包含网关类型的节点，则称ai和aj之间存在偏序关系＜ai，aj＞。类似的，如果工作流片段ci中的活动和工作流片段cj中的活动存在偏序关系，则ci和cj之间存在偏序关系＜ci，cj＞。

定义4 活动间的依赖概率。基于工作流的结构和历史日志数据，如果ai和aj之间存在偏序关系＜ai，aj＞，则paiaj表示ai和aj之间的依赖概率，即ai被执行后aj被执行的概率，其计算公式如式 （1）所示

式中：countai、countaj——工作流历史日志信息中ai、aj的执行次数合计。

定义5 活动的预计执行频次。若令fai表示活动ai的预计执行频次，给定时间段内工作流实例的数量记为instanceNumber，则工作流中第一个活动 （即初始活动）的预计执行频次fa1＝instanceNumber，其余活动的预计执行频次的计算公式如式 （2）所示，并可通过遍历DAG 图计算得到

定义6 活动间的依赖频次。令faiaj表示活动ai和aj之间的依赖频次，即ai被执行后aj被执行的频次，其计算公式如式 （3）所示

定义7 活动间的距离和类间的距离。若令commaiaj表示活动ai和aj之间的通信量，daiaj表示活动ai和aj之间的距离，则daiaj可由式 （4）计算得到。即活动ai和aj之间的依赖频次越大，通信量越大，则二者之间的距离越小

若令dcicj表示类ci到cj之间的距离，可由式 （5）计算得到。若令Dcicj表示类ci和cj之间的距离，则可由式（6）计算得到

1.2 基于聚类的工作流切片算法

基于聚类的工作流切片算法如下：

输入：DAG，instanceNumber，Paiaj，comaiaj

输出：每次聚类的最小距离min（diatance）和相应的聚类结果clusterk

首先基于工作流的历史日志信息，根据式 （1）计算得到活动间的依赖概率，并基于工作流执行环境如instanceNumber等信息，执行上述算法。该算法的主要步骤解释如下：

步骤1 数据预处理。根据给定时间段内的工作流实例数量instanceNumber与式 （2）计算每个活动的预计执行频次，根据式 （3）计算活动间的依赖频次。

步骤2 聚类初始化。令每个活动自成一类，初始化clusterk且k＝1。

步骤3 根据式 （5）和式 （6）计算clusterk中两两类间距离，找出类间距离的最小值，然后将类间距离最小的类聚合在同一个类中，k递增，更新clusterk后执行步骤4。

步骤4 判断所有活动是否在同一个类中，如是，则聚类 （即切片）过程结束；否则，执行步骤3。

1.3 算例

以图1 所示的工作流为例，说明并验证算法。其中，活动间的关系包括：a1与a2、a2与a3构成顺序关系，a3与a4、a5、a6之间为Xor－split关系，a4、a5、a6与a7之间为Xor－join关系。假设从工作流的历史日志信息中计算得到活动间的依赖概率，如图1中各边上的权数所示。

图1 工作流

另假设已知即将要到达的工作流实例数目为10000，各活动间的通信量见表1。具体的切片过程如下：

步骤1 基于活动间的依赖概率、式（2）和式（3），可计算活动间的依赖频次见表1，如：fa1a2＝fa1×pa1a2＝10000。

步骤2 初始化：令k＝1，则cluster1＝ ｛ci｜i＝1，2，…7｝。其中，c1＝ ｛a1｝，c2＝ ｛a2｝，c3＝ ｛a3｝，c4＝｛a4｝，c5＝ ｛a5｝，c6＝ ｛a6｝，c7＝ ｛a7｝。

步骤4 重复步骤3直至所有活动都聚合在一个类中。

表1 活动间的依赖频次和通信量

最终的切片结果见表2。

2 模拟实验与分析

2.1 实验设计

为了体现切片方法的适应性，考虑了工作流执行环境的两个维度：①单位时间内实例的到达数目；②可执行资源 （服务器）的数目。由于篇幅有限，设计了2 组实验，见表3。其中，每一组实验均考虑HIPD 方法和本文所提出的方法，实验所使用的工作流如图1所示。

为了便于和HIPD 方法比较，效果指标包括响应时间和吞吐量。文献 ［8］中定义的响应时间是指从第一个工作流实例到达直到最后一个工作流实例获得响应的时间；吞吐量是指单位时间内，已执行结束的工作流实例数目占所请求执行的工作流实例数目的百分比。

表2 聚类过程与结果

表3 分组实验设计

另外，在所有的实验中，为使方法对比效果更加明显，假定每个服务器的执行能力相同，每个活动在服务器上的执行时间为0.005s，同一时间一个服务器只能执行一个活动，且单位时间内工作流实例均匀到达，服务器之间的网络带宽为10Mb／s，则根据相应公式可得活动间的通信时间见表4。

表4 活动间通信时间

2.2 工作流切片与服务器分配

针对图1所示的工作流，基于本文所提出的切片方法所得到的切片结果如1.3 节中的表2 所示。为了便于与HIPD 方法比较，令min＿support＝4000，则基于HIPD 对图1所示的工作流的切片结果见表5。

表5 基于HIPD 的工作流算例的切片结果

在模拟实验进行之前，仍需基于切片结果，将工作流片段分配到相应的服务器上。针对基于HIPD 所得到的切片结果，利用文献 ［8］中所使用的Round Robin算法将工作流片段分配到相应的服务器上。针对基于本文所提出的切片方法所得到的切片结果，在进行服务器的分配时，尽可能地将在后续聚类步骤中先被聚合的工作流片段分配在同一个服务器上，并同时考虑服务器的负载均衡等因素。例如，将表2中k＝2时所得聚类结果分配在2台服务器上时，因为首先 ｛a3｝和 ｛a4｝被聚合在一个类中，所以将片段 ｛a3，a4｝分配在同一台服务器上。然后针对剩余的工作流片段 ｛a1｝、｛a2｝、｛a5｝、｛a6｝、｛a7｝，考虑k＝3时｛a2｝、｛a3｝和 ｛a4｝被聚合在一个类中，所以将 ｛a2｝和｛a3，a4｝分配在同一台服务器上。进一步的，考虑到服务器的负载均衡因素，将剩余的 ｛a1｝、｛a5｝、｛a6｝、｛a7｝分配在另一台服务器上。这种分配方式既考虑了活动间的通信时间和偏序关系，也同时考虑了服务器的负载均衡。针对两组实验的工作流片段的分配结果，见表6和表7。

表6 实验组一的工作流片段分配

表7 实验组二的工作流片段分配

2.3 实验执行与结果分析

实验的软件环境为AnyLogic Professional 7.0.0。Any－Logic是一款应用广泛的，对离散，连续和混合系统建模和仿真的工具［15］，图1 所示的工作流在AnyLogic流程模型库中建模结果界面如图2所示。

实验结果如图3、图4所示。

基于以上两组实验结果，从以下几个方面进行比较分析：

（1）本文所提出的切片方法在响应时间和吞吐量两方面均优于HIPD 方法。

（2）当服务器数目为2时，由图3 可以看出，本文提出的切片方法明显优于HIPD 方法。并且当单位时间内工作流实例到达数目为600时，聚类2－6－2 （基于本文所提出的切片方法的最优方案）的响应时间为9.79s，相比于HIPD2－7－2 （基于HIPD 方法的最优方案）的响应时间13.77s，减少了31%。由此可见，在工作流切片时，考虑活动间的通信量比不考虑活动间的通信量更能减少工作流执行的响应时间。

图2 基于AnyLogic的图1所示的工作流算例的建模界面

图3 实验组一的实验结果

图4 实验组二的实验结果

（3）当服务器数目增加时，由图3和图4可以看出，本文所提出的切片方法和HIPD 方法在响应时间上均减少，在吞吐量上均提高。这是因为当服务器数目增加时，提高了工作流执行的并发性，减少了等待时间。但是本文所提出的切片方法在响应时间和吞吐量方面的改善程度均优于HIPD。

（4）纵观所有实验，随着单位时间内工作流实例数目的增加，本文提出的方法较之HIPD 方法在响应时间方面的优势越来越大，由此可以说明当实例数目越多时，通信量越大，本文提出的方法较HIPD 更能较少通信时间，从而减少响应时间。

综上，本文所提出的方法更能适应工作流执行环境。

3 结束语

本文针对当前非中心化工作流的切片方法中存在的问题，提出一种基于聚类的非中心化工作流的适应性切片方法。该方法是对经典的凝聚层次聚类法的改进，虽然思路上与经典方法相似，但是在类间距离的计算上区别于传统聚类方法。而且，该方法不仅考虑了工作流中活动间的偏序关系与依赖频次，还充分考虑了活动间的通信量与通信时间。通过模拟实验，与当前最好的动态流程切片方法HIPD 相比，所提出的方法在不同的工作流执行环境下，响应时间与吞吐量均有不同程度的优势，且更能适应工作流执行环境的动态变化。

该方法尚有不足，如切片结果与服务器的分配方面，尚未形成完整的方法体系；又如实验时做了若干假设，不能完全体现实际工作流执行环境的各种场景等。上述局限性将有待在未来的研究工作进一步完善。

［1］WANG Wenli.Event－based distributed workflow technology in cloud environment［D］.Harbin：Harbin Institute of Technology，2013 （in Chinese）.［王文莉.云环境下基于事件的分布式工作流技术 ［D］.哈尔滨：哈尔滨工业大学，2013.］

［2］Wan Cong，Wang Cuirong，Pei Jianxun.A QoS－awared scientific workflow scheduling schema in cloud computing ［C］／／IEEE International Conference on Information Science and Technology，2012：634－639.

［3］Tram Truong Huu，Guilherme Koslovski，Fabienne Anhalt，et al.Joint elastic cloud and virtual network framework for application performance－cost optimization ［J］.Journal of Grid Computing，2011，9 （1）：27－47.

［4］Eun－Kyu Byun，Yang－Suk Kee，Jin－Soo Kim，et al.BTS：Resource capacity estimate for time－targeted science workflows［J］.Journal of Parallel and Distributed Computing，2011，71（6）：848－862.

［5］Simon Ostermann，Radu Prodan.Impact of variable priced cloud resources on scientific workflow scheduling ［G］.LNCS 7484：Euro－Par 2012Parallel Processing，2012：350－362.

［6］LI Wenhao.The study on instance－intensive workflow schedule in algorithms in community cloud ［D］.Jinan：Shandong University，2010 （in Chinese）.［李文浩.面向社区云的实例密集型工作流调度方法研究 ［D］.济南：山东大学，2010.］

［7］Liu K，Jin H，Chen J，et al.A compromised－time－cost scheduling algorithm in SwinDeW－C for instance－intensive cost－constrained workflows on a cloud computing platform ［J］.International Journal of High Performance Computing Applications，2010，24 （4）：445－456.

［8］Faramarz Safi Esfahani，Masrah Azrifah Azmi Murad，Md Nasir B Sulaimanb，et al.Adaptable decentralized service oriented architecture［J］.Journal of Systems and Software，2011，84（10）：1591－1617.

［9］YANG Chengwei，MENG Xiangxu.Research on issues of dynamic process optimization scheduling under cloud computing environment ［D］.Jinan：Shandong University，2012 （in Chinese）.［杨成伟，孟祥旭.云计算环境下动态流程优化调度问题研究 ［D］.济南：山东大学，2012.］

［10］Li G，Muthusamy V，Jacobsen HA.A distributed service oriented architecture for business process execution ［J］.ACM Transactions on the Web，2010，4 （1）：1－33.

［11］Muthusamy V，Jacobsen HA，Chau T，et al.SLA－driven business process management in SOA ［C］／／Conference of the Center for Advanced Studies on Collaborative Research，2009：86－100.

［12］Daniel Wutke，Frank Leymann，Daniel Martin.A method for partitioning BPEL processes for decentralized execution ［C］／／Erster Zentraleurop ischer Workshop，2009：109－114.

［13］Faramarz Safi Esfahani，Masrah Azrifah Azmi Murad，Md Nasir Sulaiman，et al.Using process mining to business process distribution ［C］／／ACM Symposium on Applied Computing，2009：2140－2145.

［14］Alex Seret，Seppe KLM vanden Broucke，Bart Baesens，et al.A dynamic understanding of customer behavior processes based on clustering and sequence mining ［J］.Expert Systems with Applications，2014，41 （10）：4648－4657.

［15］Zhang Debin.Teaching case：Implementation of discrete event simulation using anylogic［C］／／Proceedings of International Symposium on Modeling and Simulation of Complex Management Systems，2013：98－101.