一种受时间约束的Web服务流程挖掘方法

摘要

本发明公开了Web服务流程挖掘技术领域中的一种受时间约束的Web服务流程挖掘方法。该方法首先为Web流程库中的所有候选Web服务流程和请求Web服务流程建立受时间约束的Web服务流程的图描述；然后计算候选与请求Web服务流程之间的任务相容性值；之后分别为请求Web服务流程图描述和与之任务相容的每一个候选Web服务流程图描述建立标准化矩阵，并计算请求Web服务流程图描述和与之任务相容的每一个候选Web服务流程图描述之间的差异度值；最后选择与请求Web服务流程图描述差异度值最小的候选Web服务流程图描述，并对该图描述在Web流程库中所对应的Web服务流程进行重复使用。本发明能确保所挖掘出的服务流程能够满足客户所要求基本任务需求和用户所期望的时间约束需求。

说明书

技术领域

本发明属于Web服务流程挖掘技术领域，尤其涉及一种受时间约束的Web 服务流程挖掘方法。

背景技术

随着面向服务的体系结构(Service Oriented Architecture，简称SOA) 和技术的不断发展，Web服务(Web Service)已经在电子商务、企业应用集成 等领域扮演着越来越重要的角色。Web服务是通过Web访问的外部可用的分布 式应用程序构件。通过Web服务的组合技术，企业能够把已有的相对简单的Web 服务，按一定的业务流程逻辑组合成Web服务流程。当今企业为了适应复杂多 变的、激烈的市场竞争需求，一方面，企业在执行具体的Web服务流程时，企 业内部各部门必须尽可能有效地协同工作以满足企业客户所期望的服务质量和 时间约束要求，才能在激烈的市场竞争中立于不败之地。因此，企业针对不同 业务需求所提供的各种Web服务流程往往都是受时间约束的。对于电子商务企 业尤为如此。另一方面，企业应用系统必须能够依据业务需求，尽可能快速、 灵活地实现业务流程，以节约服务成本、提高效益。因此，企业需要采用流程 挖掘技术从已有的受时间约束的Web服务流程中找出能够满足当前最新用户需 求的Web服务流程。通过实现Web服务流程的重复使用，从而尽可能地节约服 务成本、实现Web服务流程的增值。

用于描述Web服务流程的描述语言有BPEL4WS、WSFL、XLANG、WSCI、WSCL、 BPML等，它们具有XML语言的语法，在描述能力上彼此相近。国内外几年来开 发和设计了许多支持Web服务流程建模的系统和方法。其中具有代表性的系统 包括HP实验室开发的eFlow系统和澳大利亚新南威尔士大学开发的SERV系统。 前者支持图形化的流程建模和动态的服务组合，后者使用状态图建模服务流程 逻辑。然而，当前的Web服务流程研究和应用主要关注基于工作流技术的服务 流程建模、验证、仿真和执行，而不是服务流程的挖掘。当前用于流程挖掘的 工具和方法，如ProM流程挖掘框架和DAGAMA流程发现工具，主要为了确保所 挖掘出的服务流程能够满足客户所要求基本任务需求，但是不能确保被挖掘出 的服务流程能够满足用户所期望的高效服务的需求，即满足客户期望的时间约 束需求。对于以服务质量和效率为生存之本的电子商务等企业来说，这无疑是 亟待解决的一个重要问题。

发明内容

针对上述背景技术中提到的目前流程挖掘技术不能满足用户的要求等不 足，本发明提出了一种受时间约束的Web服务流程挖掘方法。

本发明的技术方案是，一种受时间约束的Web服务流程挖掘方法，其特征 是该方法包括以下步骤：

步骤1：为Web流程库中的所有Web服务流程和请求Web服务流程建立受时 间约束的Web服务流程的图描述；

步骤2：计算请求Web服务流程图描述与每一个候选Web服务流程图描述的 任务相容性值，当相容性值大于指定阈值时，则两者任务相容；

步骤3：在步骤2的基础上，分别为请求Web服务流程图描述和与之任务相 容的每一个候选Web服务流程图描述建立标准化矩阵；

步骤4：基于标准化矩阵，计算请求Web服务流程图描述和与之任务相容的 每一个候选Web服务流程图描述之间的差异度值；

步骤5：基于差异度值，选择与请求Web服务流程图描述差异度值最小的候 选Web服务流程图描述，并对该图描述在Web流程库中所对应的Web服务流程 进行重复使用。

所述Web服务流程的图描述可通过节点的集合和边的集合确定，节点为服 务流程中的Web服务名，边为两个节点之间的带时间约束标记的有向边。

所述任务相容性值的计算公式为：

$\mathrm{taskcomp}\left({R,Q}_i\right)=\frac{|V_R\cap V_{Q_i}|}{|V_R\cup V_{Q_i}|}$

其中：

R为请求Web服务流程图描述；

Q_i为第i个候选Web服务流程图描述；

taskcomp(R，Q_i)为R和Q_i的任务相容性值；

V_R为R中所包含的结点集合；

为Q_i中所包含的结点集合。

所述请求Web服务流程图描述的标准化矩阵的计算公式为：

其中：

M(i，j)为请求Web服务流程图描述的标准化矩阵的元素；

v_i为R和Q_i所包含的Web服务名集合的并集中的第i个结点；

v_j为R和Q_i所包含的Web服务名集合的并集中的第j个结点。

所述候选Web服务流程图描述的标准化矩阵的计算公式为：

其中：

M′(i，j)为候选Web服务流程图描述的标准化矩阵的元素；

v_i为R和Q_r所包含的Web服务名集合的并集中的第i个结点；

v_j为R和Q_r所包含的Web服务名集合的并集中的第j个结点；

[a，b]表示边(v_i，v_j)在R中对应的时间约束标记；

[a′，b′]表示边(v_i，v_j)在Q_r中对应的时间约束标记；

[a，b]∩[a′，b′]表示[a，b]和[a′，b′]在时间上重叠的那部分时间约束标

记，如[2，5]∩[3，7]＝[3，5]；

Dur([a，b])表示时间标记[a，b]的间隔时间值，即Dur([a，b])＝b-a；

如果[a，b]∩[a′，b′]在时间上没有重叠的部分，那么

Dur([a，b]∩[a′，b′])＝0。

所述差异度值的计算公式为：

d_r＝DiagonalSum((M-M′)×(M-M′)^T)

其中：

d_r为差异度值；

M-M′为矩阵M与矩阵M′的对应元素值进行相减运算后所得的矩 阵；

(M-M′)^T表示矩阵M-M′的转置矩阵。

本发明不但可以确保所挖掘出的服务流程能够满足客户所要求基本任务需 求，而且能确保被挖掘出的服务流程能够满足用户所期望的时间约束需求。

附图说明

图1为受时间约束的Web服务流程挖掘算法的示意图；

图2为请求Web服务流程和2个候选Web服务流程的图描述；

图3为请求Web服务流程与第1个候选Web服务流程的矩阵差异度计算；

图4为请求Web服务流程与第2个候选Web服务流程的矩阵差异度计算。

具体实施方式

下面结合附图，对优选实施例作详细说明。应该强调的是，下述说明仅仅 是示例性的，而不是为了限制本发明的范围及其应用。

本发明的目的在于针对现有Web服务流程挖掘技术的不足，提出一种受时 间约束的Web服务流程挖掘方法，确保被挖掘出的服务流程能够满足客户所要 求的基本任务需求和客户所期望的时间约束需求，从而促进企业内部各业务相 关部门之间的有效协同工作，在高质量地完成客户需求的情况下节约企业服务 运营成本、提高企业经济效益。

本发明的技术方案是，一种受时间约束的Web服务流程挖掘方法。该方法 通过将Web服务流程转换成图描述形式，进而转换成对应的标准化流程矩阵进 行差异度计算，进一步通过Web服务流程之间的差异度值，选取最可能满足客 户需求的Web服务流程重复使用。

本发明提出的一种受时间约束的Web服务流程挖掘方法，主要包括以下步 骤：

1.为Web流程库中的所有Web服务流程以及请求Web服务流程建立受时间 约束的Web服务流程的图描述。

一个Web服务流程的图描述可以通过其结点集合和边集合来确定，其中， 图描述的结点是服务流程中的Web服务名，图描述的边是两个结点之间的有向 边，用来表示这两个结点所对应的Web服务之间的激活关系，有向边上的形如 [a，b]的时间约束标记表示始端Web服务需要在a到b个时间单位内完成才能进 一步激活末端Web服务，a≤b。图描述的结点集合和边集合可以分别通过两个数 据库表进行存储。

具体包括如下子步骤：

1.1直接使用图描述来表示请求Web服务流程。请求Web服务流程是针对 给定客户需求(包括基本任务需求和时间约束需求)所制定的一个理想的Web 服务流程。

1.2对于Web服务流程库中通过流程描述语言描述的所有的候选Web服务 流程，采用当前常用的XML解析器工具从该Web服务流程描述中提取出所有的 Web服务名和服务激活关系，再根据该Web服务流程以前所执行的系统记录日志， 提取服务激活之间的时间约束关系，从而为每一个候选的Web服务流程建立并 存储其图描述。用Q₀，Q₁，…Q_m-1表示所有候选的Web服务流程的图描述。

2.计算请求Web服务流程图描述R与每一个候选Web服务流程图描述 Q₀，Q₁，…Q_m-1的任务相容性值。

具体包括如下子步骤：

2.1设定计数器i初值为0。

2.2任务相容性值taskcomp的计算公式为：

$\mathrm{taskcomp}\left({R,Q}_i\right)=\frac{|V_R\cap V_{Q_i}|}{|V_R\cup V_{Q_i}|}$

其中：

R是请求Web服务流程图描述；

Q_i是第i个候选Web服务流程图描述(0≤i≤m-1)；

taskcomp(R，Q_i)为R和Q_i的任务相容性值；

V_R和分别表示R和Q_i中所包含的结点集合。

设定任务相容性阈值为0.6。任务相容性主要是为了检验两个服务流程所包 含的相同服务名的比率。如果R和Q_i的taskcomp值大于等于这个阈值，说明它 们是任务相容的；否则，任务不相容。

2.3如果R和Q_i是任务相容的，那么将Q_i加入任务相容Web服务流程图描 述队列。

2.4如果此时i＜m-1，那么令i＝i+1，然后转去执行子2.2，从Web服务 流程库中选择下一个候选Web服务流程Q_i与R进行任务相容性比较。否则，如 果i≥m-1，则停止流程图描述的相容性计算。

3.分别为请求Web服务流程图描述和与之任务相容的每一个候选Web服务 流程图描述建立标准化矩阵。

与请求Web服务流程图描述R任务相容的Web服务流程图描述队列中的服 务流程图描述记为Q₀，Q₁，…Q_k-1，0≤k≤m。

R和Q_r(0≤r≤k-1)的标准化矩阵分别用M和M′表示，它们都是n×n矩阵。 其中，即R和Q_r的标准化矩阵中的行和列元素来自R和Q_r的节点 集的并集。该并集中的n个元素记为v₀，v₁，…v_n-1。

具体包括如下子步骤：

3.1基于Web服务流程的图描述，建立请求Web服务流程图描述R的标准 化矩阵。

请求Web服务流程图描述R的标准化矩阵记为M，其中的每一个元素 M(i，j)的值按照如下方式计算：

其中：

v_i和v_j表示R和Q_r所包含的Web服务名集合的并集(即)中 的第i个结点和第j个结点，且i和j满足条件0≤i，j≤n-1，且 即并集的基数。

3.2基于Web服务流程的图描述，为每一个候选Web服务流程图描述建立 标准化矩阵。

候选Web服务流程Q_r图描述的标准化矩阵记为M′，其中的每一个元素 M′(i，j)的值按照如下方式计算：

其中：

v_i和v_j分别表示R和Q_r所包含的Web服务名集合的并集中的第i个结 点和第j个结点，且i和j满足条件0≤i，j≤n-1；

[a，b]表示边(v_i，v_j)在R中对应的时间约束标记；

[a′，b′]表示边(v_i，v_j)在Q_r中对应的时间约束标记；

[a，b]∩[a′，b′]表示[a，b]和[a′，b′]在时间上重叠的那部分时间约束标 记，如[2，5]∩[3，7]＝[3，5]；

Dur([a，b])表示时间标记[a，b]的间隔时间值，即Dur([a，b])＝b-a。

如果[a，b]∩[a′，b′]在时间上没有重叠的部分，那么

Dur([a，b]∩[a′，b′])＝0。

4.基于标准化矩阵，计算请求Web服务流程图描述和与之任务相容的每一 个候选Web服务流程图描述之间的差异度值。

4.1设定计数器r处置为0。

4.2计算R与Q_r之间的差异度值d_r，差异度值d_r值可以通过如下的公式进 行计算：

d_r＝DiagonalSum((M-M′)×(M-M′)^T)

其中：

M-M′表示矩阵M与矩阵M′的对应元素值进行相减运算后所得的 矩阵；其矩阵相乘，结果仍为一个矩阵；

(M-M′)^T表示矩阵M-M′的转置矩阵；

DiagonalSum用于计算矩阵的对角线元素值的加和，该加和就是R和 Q_r之间的差异度值，即d_r。

4.3如果r＜k-1，那么r＜r+1，并转4.2，从Web服务流程库中选择下一 个候选流程Q_r与R进行任务相容性计算和差异度计算。

5.基于差异度值，选择与请求Web服务流程图描述差异度值最小的候选Web 服务流程图描述，并对该图描述的在Web流程库中所对应的Web服务流程重复 使用。

所有与R任务相容的候选Web服务流程图描述与R的差异度值记为 d₀，d₁，…d_k-1。与R最相似的候选Web服务流程记为Q_x，其中下标x通过d_x来确 定，公式如下：

d_x＝min{d₀，d₁，…d_k-1}

也即是说，所有的差异度值中最小的那个值所对应的候选Web服务流程将 是与请求服务最相似的、可重复使用服务流程。

本发明所提出的受时间约束的Web服务流程挖掘方法的特点就是，通过将 Web服务流程转化成它们的图描述，进而通过比较请求Web服务流程的流程矩阵 与候选Web服务流程的流程矩阵之间的差异度，最终挖掘出与请求Web服务流 程差异最小的候选Web服务流程进行流程重复使用。本发明所提出的方法符合 相似度越大则差异度越小的人类基本认知。该方法所涉及到的流程信息的提取、 相关矩阵运算等操作都可以通过当前一些主流的软件开发工具实现，也具有较 低的计算复杂度，最坏情况下的复杂度为O(m*n³)，其中，m是流程库中候选 Web服务流程的总数，n是流程库中Web服务的总数。该方法的应用可以达到我 们预期的目标，不但可以确保所挖掘出的服务流程能够满足客户所要求基本任 务需求，而且能确保被挖掘出的服务流程能够满足用户所期望的时间约束需求。

本实施例包括两个大的方面：

1.受时间约束的Web服务流程的图描述的生成

可重复使用的Web服务流程通常是通过Web服务流程描述文件保存在服务 流程库中的。以BPEL服务描述语言为例，一个Web服务流程文件以XML格式文 件进行存储，其中包含了该流程中所涉及的所有的Web服务名以及Web服务之 间的相互激活关系。因此，可以通过XML解析器解析一个BPEL描述的Web服务 流程文件生成该服务流程的图描述。目前可用的XML解析器很多，如IBM的 XML4J、Oracle的XML Parser for Java等。

具体步骤如下：

1.1按顺序依次解析Web流程库中的每一个Web服务流程文件，根据服务 流程描述语言的结构化活动描述，从Web服务流程提取出所有的Web服务名和 Web服务激活关系。结构化活动描述通过<case>标签指定Web服务活动名，通过 <sequence>、<switch>、<flow>、<loop>等标签来指出不同的服务活动之间的 顺序、OR-split、AND-split及循环等条件关系。1.1具体可分成如下子步骤：

1.1.1通过<case>标签从结构化活动描述中提取出所有Web服务(活动) 名。所有提取的服务名保存在一个1维数组中，数组中每一个元素就是一个服 务名。

1.1.2通过上述条件关系标签从结构化活动描述中提取出服务活动之间所 有的激活关系。所有服务活动之间的关系保存在一个4维数组中。该4维数组 的每个列向量的前两个分量表示两个服务活动之间的激活关系。

1.2根据该Web服务流程以前所执行的系统记录日志，提取服务激活之间 的时间约束关系。系统记录日志保存了流程中的Web服务执行的开始时间、结 束时间。对于一个服务激活关系边的时间约束[a，b]，a等于边的始端服务的结 束时间减去开始时间，b等于边的末端的服务的开始时间减去始端服务的开始时 间。进一步，将a和b值分别存储在4维数组中对应激活关系的列向量的后两个 分量中。

1.3通过保存Web服务名的1维数组和保存服务激活关系以时间约束的4 维数组，可以确定一个Web服务流程的图描述。图2a是本发明实施例的请求Web 服务流程图描述，记为R。图2b和图2c是2个候选Web服务流程的图描述， 分别记为Q₀和Q₁。它们分别可以通过一个1维数组和4维数组确定。例如，R的 存储方式如下：

R的Web服务名1维数组RNode[]＝{A2，A3，A4，A5，A6，A7，A9，A10}， R的激活关系4维数组RRel[][4]＝{{A2，A3，2，3}，{A2，A4，2，5}，{A3，A5， 4，6}，{A3，A6，3，4}，{A5，A9，3，4}，{A6，A9，2，3}，{A4，A7，3，4}， {A7，A10，4，6}，{A9，A10，2，7}}。也可相应建立Q0和Q1的相关存储数组 Q0Node、Q0Rel、Q1Node和Q1Rel等。

其中：

Q0Node[]＝{A1，A2，A3，A4，A5，A7，A8，A9，A10，A11}；

Q0Rel[][4]＝{{A1，A2，3，5}，{A2，A3，2，4}，{A2，A4，3，5}，{A3， A5，4，6}，{A4，A7，3，5}，{A4，A8，6，9}，{A5，A9，3，5}，{A1，A2，3， 5}，{A7，A11，4，5}，{A8，A11，2，3}，{A9，A10，3，6}，{A11，A10，2，3}}；

Q1Node[]＝{A1，A2，A3，A4，A6，A7，A8，A9，A10}；

Q1Rel[][4]＝{{A1，A2，2，3}，{A2，A3，2，4}，{A2，A4，2，4}，{A2， A8，4，6}，{A3，A6，3，5}，{A4，A7，3，4}，{A6，A9，2，3}，{A9，A10，2， 6}，{A8，A10，5，7}，{A7，A10，6，8}}。

2.基于Web服务流程的图描述，从服务流程库中挖掘出与请求Web服务流 程R最相似的候选Web服务流程。本实施例将使用Q₀和Q₁作为候选Web服务流 程的图描述，从Q₀和Q₁中找出与R最相似的Web服务流程。该方面具体分为如 下几个步骤：

2.1计算R与所有候选Web服务流程的任务相容性值taskcomp。包括如下 几个子步骤：

2.1.1将Q₀和Q₁加入Web流程图描述队列，此时m＝2。设置一个计数器i， 初始值为0；

2.1.2计算taskcomp(R，Q_i)的值；

2.1.3如果R和Q_i的相容性值不小于0.6，那么将Q_i加入任务相容Web服务 流程图描述的队列；

2.1.4如果i＜m-1，那么令i＝i+1，然后返回2.1.2；否则执行2.2；

在本实施例中，通过上述子步骤，R和Q₀的相容性值为：

taskcomp(R，Q₀)＝7/11＝0.636≥0.6

R和Q₁的相容性值为：

taskcomp(R，Q₁)＝7/10＝0.7≥0.6

因此，Q₀和Q₁都加入到任务相容Web服务流程图描述的队列。

2.2计算R与所有候选的任务相容Web服务流程图描述的差异度值。该步 骤包括如下几个子步骤：

2.2.1为计数处理方便，按顺序命名与R任务相容的候选Web服务流程队 列中的流程图描述：Q₀，Q₁，…Q_k-1，并设定计数器r，初始值为0。本实施例中的 任务相容服务流程队列中，k＝2，并同时包含Q₀和Q₁；

2.2.2建立Q_r的标准化矩阵M′；

2.2.3针对Q_r建立R的标准化矩阵M；

2.2.4计算d_r的值，并将d_r加入差异度值队列；

2.2.5如果r＜k-1，那么计数器r加1，然后返回2.2.2继续下一个任务相 容的Web服务流程的差异度计算。否则，那么进入2.3；

在本实施例中，按照前面提到的产生服务流程的标准化矩阵的定义，给出 了R与Q₀进行差异度计算的标准化矩阵，分别见图3a和图3b。也给出了R与Q₁进行差异度计算的标准化矩阵，分别见图4a和图4b。

在计算R和与之任务相容的每一个Web服务流程Q_r的差异度值的过程中， 还会产生两个辅助性矩阵。一个是矩阵M与矩阵M′的对应元素进行减运算后的 矩阵，为方便起见记为矩阵M″。另一个辅助矩阵是M″与M″的转置矩阵进行矩 阵相乘后所得的矩阵，为方便起见记为M′″。在本实施例中，Q₀所对应的两个 辅助矩阵M″和M′″分别见图3c和图3d，Q₁所对应的两个辅助矩阵M″和M′″分 别见图4c和图4d。

计算d₀的差异度值就是将Q₀的M′″矩阵中对角线上的元素(即矩阵中灰色 标记的元素)的值加和，得到d₀＝8.27。类似的，d₁的值是分别将Q₁的M′″矩阵 中对角线上的元素的值加和，得到d₁＝5.4；

2.3从差异度值队列d₀，d₁，…d_k-1，选择差异度值最小的一个差异度值d_x； 那么，Q_x则是与R最为相似的任务相容的Web服务流程图描述。具体选择最小 差异度值的子步骤如下：

2.3.1设定计数器q，初始值为1；设定变量x，其初始等于0；

2.3.3如果d_q＜d_x，那么把q的值赋给x；

2.3.4如果q＜k-1，那么令q＝q+1，返回2.3.3；否则，结束。

在本实例中，差异度值队列只包含两个差异度值，即d₀，d₁。通过执行2.3 以后，d_x中的整型变量x中保存的是差异度值队列中的差异度值最小的服务流 程的编号。本实施例中，d₁的值最小，故x的值为1。因此，在Web服务流程库 中，与任务相容的Web服务流程图描述Q₁对应的候选Web服务流程与请求Web 服务流程最为相似。因此，所有的差异度值中最小的那个值所对应的候选Web 服务流程将是与请求服务最相似的、可重复使用服务流程。

以上所述，仅为本发明较佳的具体实施方式，但本发明的保护范围并不局 限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，可轻易 想到的变化或替换，都应涵盖在本发明的保护范围之内。因此，本发明的保护 范围应该以权利要求的保护范围为准。