BPM组合服务匹配算法优化研究

2018-12-10黄秋波余宁波

软件导刊 2018年9期

黄秋波　余宁波

摘要：智能制造中BPM需要匹配符合要求的服务实现服务组合。目前服务匹配研究主要集中在对单个服务的匹配，而对于组合服务匹配的研究相对较少。如何从服务库中找到满足服务模型要求的服务组合是目前服务匹配研究的难点。为加快匹配搜索速度，引入索引机制，并给出基于索引机制的组合服务匹配算法，再对算法进行模拟并给出对比算法匹配时间结果。实验结果表明，基于索引机制的组合服务匹配算法能显著加快匹配速度、提高匹配效率。

关键词：服务模型；组合服务；匹配；索引；智能制造

DOIDOI：10.11907/rjdk.181169

中图分类号：TP312

文献标识码：A文章编号文章编号：16727800（2018）009008804

英文标题Research on Optimization of Composite Service Matching Algorithm in BPM

--副标题

英文作者HUANG Qiubo，YU Ningbo

英文作者单位（School of Computer Science and Technology，Donghua University，Shanghai 201620，China）

英文摘要Abstract：In smart manufacturing BPM needs to match the services that meet the requirements to composite existing services.The research on service matching is mainly focused on the matching of individual services，and the research on the matching of composite service is relatively limited.At the same time，how to find a composite service that meets the requirements of a service model from a large number of individual services is a difficult problem for the research of service matching.In order to speed up the matching search procedure，the index mechanism is introduced in this paper，and a composite service matching algorithm based on the index mechanism is given.Finally the algorithm is simulated and the results of the algorithm matching time are given.The experimental results show that the composite service matching algorithm based on index mechanism can speed up the matching speed significantly and improve the efficiency of matching.

英文关键词Key Words：service model；composite service；matching；index；intelligent manufacturing

0引言

近年来，工业与信息技术领域发生了深刻变革，带来了制造业新一轮革命，特别是作为信息化与工业化高度融合产物的智能制造得到了长足发展[1]。智能制造通过工业自动化与信息技术（IT）的融合，很快提升工厂的生产灵活性，并可节约能源、保护环境、降低成本、提高质量和人身安全，从而使工厂生产效率和质量得到大幅优化提高[2]。制造业中的业务流程管理BPM（Business Process Management，BPM）作为智能制造的一个方面，目前将中心主要集中在生产过程中。对业务流程管理的实质是对过程的管理[3]。2003年，IBM提出了一种以数据为中心的业务流程管理思想[4]。在BPM中，服务模型是目前研究的重点。本文服务模型和Web Service[56]有一些相似性，也有很大不同。首先，服务模型通常可以并发自运行，服务模型的前后之间往往不存在线性调用关系，服务模型一旦接收到满足条件的输入就会开始自运行；其次，后继服务可以接受前驱服务的部分输出，也可组合多个服务作为其前驱服务；最后，由于服务模型是现实生产的抽象，因此服务之间传递的数据可以进行加工后再使用。

目前對于BPM中以数据为中心的组合服务模型的匹配研究较少。文献[7]提出了基于操作树的服务模型匹配算法。该算法通过将服务模型的一系列操作描述为一棵操作树，比较服务模型操作的影响相似度判断服务模型是否匹配。使用该算法需要明确了解服务模型操作产生的影响及操作间层次关系，在实际应用中并不具备很高的可用性。文献[8]提出了FrontBack和BackFront两种组合服务匹配算法。FrontBack算法是通过将前面一个服务的输出作为后面一个服务的输入进行匹配，而BackFront是知道一个服务的输入，然后去寻找前一个服务的输出。FrontBack的时间复杂度为O（N2），当候选集很大时效率很低。BackFront算法匹配时找到的结果较少。本文试图使用本体树，通过正向与反向搜索相结合的方式对服务模型进行匹配，并使用索引加快匹配速度。

1服务模型及匹配

服务模型包括服务、输入参数集（可理解為原材料）及输出参数集（可理解为生产的产品）。

用户提供一个服务模型（r），需要到服务库中查找是否有候选服务（s）能满足其输入、输出要求，如果找到，用户可使用已有服务完成自己的功能。

只有当服务模型与候选服务的输入参数集合和输出参数集合各自匹配，才能认为服务模型和候选服务是匹配的。进行匹配时，单个服务模型和单个候选服务进行匹配最简单，但发生频率较低。复杂服务模型通常需要将多个候选服务组合成复杂组合服务[9]。单个服务模型与单个候选服务的匹配是该组合服务匹配的特例。

对于服务模型（r）和组合服务（s1，s2，s3...sn）匹配需要满足两个条件：①siin（rin∪s1out∪s2out∪s3out...∪si-1out），1in；

②rout（rin∪s1out∪s2out∪s3out...∪snout）。

其中，rin表示服务模型输入参数集合，rout表示服务模型输出参数集合，siin表示候选服务si输入参数集合，siout表示si输出参数集合。

2服务索引机制

以上描述的匹配过程需要到服务库中反复搜索满足条件的服务，由于服务库中通常存在大量服务，从中找到合适的服务需要花费较长时间。采用对服务参数建立索引的方式可以加快搜索过程。通过使用索引机制加快BPM中组合服务模型的匹配速度是本文的一个创新点。索引结构可通过哈希表实现。对服务建立索引时需要明确索引的key值。由于参数命名差异和参数排列顺序，可能造成key命名无法统一。如“书”和“书籍”含义相同，建立的索引却不相同。使用本体树可以解决命名问题。本体是对世界上任何真实存在的事物作出的客观描述[10]。在本体树中，一个概念只有一个名称，这样能够实现命名的统一[11]。而参数排列顺序的差异可使用规约的方式确保不同排列顺序的参数能得到唯一序列。文献[12]提出一个规约定理，该定理内容包括：设有n个字符串s1，s2，...，sn，按字母顺序从小到大排序后得到s′1，s′2，...，s′n，则s′1，s′2，...，s′n具有唯一确定性。

由该定理可知，不管原有的参数排列如何，经过排序后都能得到唯一规约序列。将该序列作为key值能够使key得到统一。

对于服务的输入参数和输出参数分别建立索引，会产生两类索引[13]。分别使用输入参数索引和输出参数索引进行匹配查找，在经过匹配之后产生两个候选服务的集合。一个候选服务集合是经过输入参数匹配之后找到的满足输入参数要求的集合，另一个候选服务集合是经过输出参数匹配之后找到的满足输出参数要求的集合。最后求得两个参数交集，可以得到同时满足输入参数和输出参数要求的候选服务。

对服务输入、输出参数分别建立索引，如图1所示。其中S1，S2...表示服务库中的候选服务。i1，i2，i3...in表示输入参数，o1，o2，o3...on表示输出参数。

对于服务模型r，输入参数集合为rin={r1in，r2in，r3in，…}，输出参数集合为rout={r1out，r2out，r3out，…}。在建立索引之前需要对参数集合的子集进行划分，得到多个索引的Key值。

ripinrin，0

ripoutrout，0

例如，服务输入参数集合是{a，b，c }。则对其划分后得到子集：{a，b，c }、{a，b }、{b，c}、{a，c}、{a}、{b}、{c}。空集不能作为索引Key值。

本文假设用户希望能以尽量少的服务来组合满足自己的要求。因此在通过索引查询服务时，首先查询元素数目较多的参数子集，如果不满足要求，再查询元素数目较少的参数子集。因此，优先找到的是最大程度满足要求的服务。

3服务匹配算法

基于参数集合子集索引的匹配

算法ServiceMatchOnSubset用于从候选服务集中匹配合适的组合服务集。服务模型r输入参数集合为rin，输出参数集合为rout。

输入：服务模型r，服务集Rep

输出：组合服务集

步骤1：初始化一个结果队列Q，然后初始化一个组合服务集合S，并将S放入Q尾部。

步骤2：从Q的队头选取一个组合服务集S。

步骤3：将S中的服务的输入参数和输出参数以及rin放入参数集合R。

步骤4：取R的子集R1，R2，R3...Rn。其中R1为R的全集，Rn参数为1个。Ri中参数随i值增大而减少（1≤i≤n）。

步骤5：依次选取Ri，通过索引从Rep中找到输入参数与Ri集合相同的候选服务，组成集合Rsad。

步骤6：依次取Rsad中的服务sad，用sad的输入参数与Ri的参数进行语义匹配。如果sad匹配成功且sad产生了不同于R的参数则进入步骤7。

步骤7：将sad和S的所有元素保存进一个新组合服务集Snew并删除sad。如果Snew中服务输出参数和rin组成的参数集Rnew等于或者包含rout，则进入步骤8，否则将Snew放入Q的队尾，进入步骤6。

步骤8：初始化一个空的参数集合Rpara，标记Snew中服务输出参数和与rout有交集的的服务并将这些服务输入参数放入Rpara。

步骤9：标记Snew中输出参数与Rpara有交集的服务，清空Rpara并将新标记的服务输入参数放入Rpara。

步骤10：重复步骤9直到Snew中输出参数与Rpara没有交集，输出Snew中被标記的服务。

步骤11 重复步骤6-10，直到Rsad中元素为空。

步骤12 重复步骤5-10，直到R中元素为空。

步骤13 重复步骤2-10，直到Q中元素为空。

步骤1-7通过选取服务模型输入参数集合的子集，找到能够使用划分后参数并且产生了不同于R参数的服务，从而扩大组合服务输出参数的类型，直到能够满足rout的需求。步骤8同样采用自下而上回溯的方法排除掉多余服务。

算法的思想是建立一棵结果树，然后进行广度优先搜索[14]。每次向下一层建立节点时，都能在组合服务集中添加一个新的服务，并从服务库中删除一个服务，直到最后整棵树的输出能够满足rout。之后选出哪些单个服务能输出rout和哪些服务能够产生这些服务的输入，一直向上回溯。最后找到的服务就是整个生产必需的服务，组合服务集中的其它服务是多余服务。

为了更好地理解上述算法，本文通过以下例子加以说明。

假设服务模型的输入参数集合rin={a，b，c}，输出参数rout={x，y，z}。通过算法进行匹配时，首先需要对参数集合进行划分。参数集合R中的元素为rin。对R进行划分，R的子集包括{a，b，c }、{a，b }、{b，c}、{a，c}、{a}、{b}、{c}。查询索引表时，依据参数集中的元素个数从多到少选择子集进行查询。因此，最开始使用{a，b，c }进行查询。如果通过索引表没有查到候选服务，则选择下一个子集进行查询，如{a，b}。如果找到了一个服务并且该服务产生了新参数，则将该服务加入到服务集中。例如，通过{a，b}查到候选服务S1。S1的输出参数集合S1out={d，e}，其元素并不在参数集合R={a，b，c}中，此时需将S1加入到结果集中，同时R={a，b，c，d，e}。由于参数集合R并没有包含服务模型输出参数集合rout全部参数，则需要继续进行查询并对R重新进行划分。此时R={a，b，c，d，e}。R划分的的子集为{a，b，c，d，e}、{a，b，c，d}、{a，b，c，e}...。当R包含了rin中的全部元素时，正向搜索结束，此时，结果集为{S1，S2，S3，S4，S5}。这些服务进行组合后能够接收服务模型输入参数并产生服务模型输出参数。但是，这些服务并不一定都对最终服务模型的参数有用。其中某些服务可能成为多余服务，例如S3的输出参数集合S3out={m，n}，对于多余服务需要进行自底向上的回溯去掉。在对结果集进行回溯时，首先需要标记包含服务模型输出参数集合中元素的候选服务，例如S2、S4、S5。但是此时候选服务输入参数并非全部来自服务模型输入参数，有些还需要其它服务输出参数集合作为输入参数，例如S2的输入参数集合部分来自S1。因此继续回溯，标注能产生S2、S4、S5输入参数的候选服务S1。此时，S1、S2、S4、S5的输入参数全部来自服务模型输入参数集合，并且能够产生服务模型的全部输出参数。而没有标记的候选服务S3则会被作为多余的候选服务被删除。最后{S1，S2，S4，S5}就作为最终的组合服务输出。

4实验分析

为了验证算法差异，通过仿真实验从服务匹配的时间和匹配到的服务数目进行比较。

随机生成包含纺织行业中“纺布”、“剪裁”、“染色”、“印花”4个流程共10 000个服务模型，放入候选服务库中作为本实验的数据。平均每个服务有3个输入参数和3个输出参数。

算法匹配时间的比较如图2所示。其中，算法1是使用基于划分子集的索引的匹配算法，算法2是BackFront算法，算法3是FrontBack算法。从中可以看出前两种算法在时间上增长缓慢。算法3在时间上存在加速上涨趋势。算法1在匹配时间上最低。当服务的数量只有100个时，第1种算法的匹配时间只有第2种算法的1/2，第3种算法的1/3。但当服务数量增加到10 000个时，第1种算法的匹配时间只有第2种算法的1/2，第3种算法的1/328。

5结语

本文提出了基于索引的组合服务匹配算法。首先将服务模型输入参数集合作为集合R，然后依次取集合R划分的子集匹配候选服务，从匹配到的候选服务中产生了不同于集合R参数的输出参数，并被添加到集合R中。重复以上步骤直至集合R包含服务模型的所有输出参数。最后，通过自下而上的回溯去掉多余候选服务，从而找到最终服务组合。通过实验比较，该方法相较于已有的组合服务匹配算法能够在较大程度上加快匹配速度、提高匹配效率。

参考文献参考文献：

[1]张洁，吕佑龙.智能制造的现状与发展趋势[J].高科技与产业化，2015，11（3）：4247.

[2]邹方.智能制造中关键技术与实现[J].航空制造技术，2014，458（14）：3237.

[3]张大伟.ArtiFlow管理器的设计与实现[D].秦皇岛：燕山大学，2010.

[4]NIGAM A，CASWELL N S .Business artifacts：an approach to operational specification[J].IBM Systems Journal，2003，42（3）：428445.

[5]陈建虎，肖成龙，宋好，等.基于SOA架构的Web Service体系研究[J].电脑知识与技术，2017（29）：2628.

[6]何倩，李佳，胡启伟，等.基于QoS和多级索引的Web服务发布订阅[J].计算机科学，2016，43（4）：106110.

[7]李婷.ArtiFlow向BPEL转换过程中服务匹配技术的研究[D].秦皇岛：燕山大学，2010.

[8]刘壮，张娟娟，郭荷清.Web Services发现和集成句法匹配算法研究[J].计算机工程与应用，2006，42（20）：190192.

[9]庄亚欧，徐汉川，徐晓飞，等.基于服务模式的快速服务组合方法研究[J].计算机工程与应用，2016，52（1）：16.

[10]金海涛，张琳.基于领域本体映射的综合相似度计算方法[J].现代计算机：专业版，2017（14）：3439.

[11]徐英卓，贾欢.基于树结构的本体概念相似度计方法[J]. 计算机系统应用，2017，26（3）：275279.