基于层次状态机的服务组合

张 飒，朱雪峰

(中国石油大学(北京) 石油数据挖掘北京市重点实验室，北京 102249)

0 引 言

Web服务组合方案设计分为组合方案设计和组合方案优化两个阶段。如何将不同的服务有效地组合在一起，实现功能需求，继而在优化阶段，针对非功能性属性对候选服务进行筛选，是web服务组合研究的重点。

文献[1]采用扩展工作流模型，将抽象服务替换为实际的wsc(web service composition)方案。基于工作流模型研究的重点之一在于如何克服动态环境的影响。文献[2]利用petri网建模，建立了服务组合描述与状态图的一一映射关系。但是petri不易理解，不能在网中体现数据流。文献[3]的研究基于π演算是进程代数在wsc研究中应用的代表。根据文献[4]，局部优化方法从所有候选服务中，可以找到局部较优的服务方案，但是会忽略非功能属性的需求；全局优化方法可以找到最优方案，但这个方法的时间花销随规模增大；运用启发式算法的优化方法，可以以较小的开销找到较优的结果，但没有考虑到服务之间的逻辑关系。

通过对比web组合方案的研究现状可以发现，对web服务组合设计建模，进行服务组合优化的研究存在以下问题：①已有的服务自动组合的研究工作主要集中在通过形式化描述、图例方法得到服务的组合和执行顺序，在这种情形下，由于空间有限和状态过多就有可能造成状态爆炸；②关于组合优化的研究，上述方法并没有考虑到用户对于服务提出的约束条件，忽略了服务之间的逻辑关系。

1 Web服务组合及相关技术

单一的web服务可以实现一定的功能，但是单一的服务所能起到的作用相对而言还是有限的。通过服务组合，可以构建出应用场景更加多样，功能更加强大的服务系统。web服务组合方案设计分为组合方案设计和组合方案优化两个阶段。组合方案设计阶段主要为业务流程建模，优化阶段主要是基于QoS或者是用户的其它非功能性需求进行研究分析。

组合优化阶段，设计者主要针对用户的非功能性需求进行优化，在衡量用户的满意程度上，除了主观因素，QoS作为一种非功能性的标准，可以客观的、量化的衡量满意程度。QoS的属性指标有各种各样的，其中的内容也是多种多样的。常用的QoS属性可以分为两类，一类是优势属性，另外一类是劣势属性。其中服务花费、响应时间等属于劣势属性，它们的值越小越好；而服务安全、可靠性等属于优势属性，它们的值越大越好。

用QoS对web服务组合模型进行评定时，可以选取的备选方案往往有多个。但是各个QoS属性的取值单位和范围是不统一的，举例来说，服务花费的取值范围是服务提供者提出的，取值单位是数值类型的；而可靠性的取值单位是比率类型的，取值范围在[0,1]之间。因此如果想要进行web服务组合中QoS属性的比较，首先要对各个QoS属性进行归一化处理，避免取值单位和取值范围造成的影响。优势属性采用式(1)来计算

(1)

劣势属性采用式(2)计算

(2)

式(1)和式(2)中的m表示web服务未经处理的QoS属性值，而m′代表着经过归一化处理的QoS属性值。经过归一化处理后，原来的QoS属性值的值域会一一映射到范围[0,1]中去。

在web服务组合之中存在4种服务运行逻辑。在计算web服务组合的QoS属性值时，要用不同的方法对4种运行逻辑的web服务组合进行不同的聚合。顺序、循环、选择和并行，这4种运行逻辑的计算公式见表1。

表1 服务组合QoS计算模型

2 状态机与服务组合建模

2.1 服务状态机

用简单的服务状态机互相组合最终形成的状态图可能存在状态爆炸的情况，因此引入层次状态机对服务进行组合。假设用户的需求为输入 {1,2,3}， 输出为 {7,8,9,10}。 那么层次状态机中的超状态如图1所示。其中矩形为层次状态机中的超状态， {A,B,C}、 {D,E} 是分别属于两个超状态的服务。

2.2 基于状态机的服务社区

存在很多接口参数相似、功能相似的服务，将他们组成一个服务社区。基于状态机的服务社区为一个四元组 (ID,S,I,O) 其中：ID为服务社区的唯一标示，S为服务的集合，I=(Ipub,Ipri) 为输入参数的结合，Ipub为公共参数即所有服务输入参数的交集、Ipri为非公共参数即所有服务除公共参数的输入参数。O=(Opub,Opri) 为输出参数的结合，Opub为公共参数即所有服务输出参数的交集、Opri为非公共参数即所有服务除公共参数的输出参数。

3 基于层次状态机的服务组合过程

通过用户的输入参数发现服务，得到的服务暂时作为层次状态机的H0层。将H0层的输出作为下一层的输入参数，找到下一层的服务，有则选择该服务，无则不能选择。直到所有层的输出参数的并集与用户需求的输出参数相吻合。

基于层次状态机的服务组合定义如下

3.1 基于层次状态机的服务发现

由于公共参数是一个服务社区所有服务都需要的输入参数，所以先匹配每个服务社区的服务参数，再匹配非公共参数可以提高效率。

划分超状态的服务步骤如下：

步骤1 查找服务社区，如果输入满足服务社区的公共参数，下一步。

步骤2 进入这些服务社区，找到输入满足的服务集，获得它们的输出参数，如果满足用户需求，返回组合方案；不满足，将该层的输出与输入并集作为下一次的输入集。

步骤3 获取已经匹配的服务社区的后续服务社区，循环步骤1～步骤2，直到满足用户需求，或者达到停止条件。

3.2 服务状态机的组合

(1)QP(A,B)=QA∪QB∪s0P(A,B)；

(2)EP(A,B)=EA∪EB∪ε；

(4)s0P(A,B)=s0P(A,B)；

(5)FP(A,B)=FA∪FB；

3.3 服务组合的验证

所有服务是否能正确且高效地组合成目标服务，需要对服务组合的存在性及等价性进行验证。其中，存在性验证实质上就是对服务的可达性进行验证。

3.3.1 服务存在性验证

由定义2可知，从最终状态开始寻找前继节点，再继续寻找前继节点的前继节点，直到找到起始节点q0， 每个在路径上的节点都是可达的。第4节中通过反向搜索保证了状态图的可达性。

3.3.2 服务等价性验证

(1)q0=s0；

(3)qn∈F；

则服务状态机接受t。如果L={t|m接受t}， 则称服务状态机m识别语言L，记为：L(F)。

由以上的定义，可以得到如下性质：

性质1 对于状态节点，当且仅当q0*t→qi+1～q2*t→qi+1时，q1～q2。

性质2 终止状态一定不等价于非终止状态。

根据以上内容，结合第4节的构建过程，如果层次状态机的所有终止状态都可以在服务社区中找到对应的终止状态，那么验证目标服务与原服务是等价的。

4 服务优化过程

4.1 基于最优QoS优化过程

以时间花费属性为例，采用正向执行顺序，起始状态看作一个只有输出的虚拟服务，其QoS为0。对每一层的输入参数I循环。在候选服务中选出QoS最小的服务s。根据2.1节的内容，由于服务都是并行的，s的前序服务的QoS为上一层所有输入参数最小值中选出的最大值。将最大值与s的QoS相加，即得到选择s服务的服务组合QoS最小值。直到最后的终止状态。终止状态可以看作是一个只有输入的虚拟服务。虚拟服务的QoS即为服务组合的最终值。基于最优QoS优化过程如算法1所示。

算法1

输入：候选服务s

输出：候选服务的组合最优QoS表

(1)创建变量qosmax=0， 变量qosmin=极大值， map结构的QoS最优表map。

(2)循环s.I:

(3)创建队列sersrc；

(4)sersrc.push(能输出该参数的服务)；

(5)循环sersrc{

(6)查QoS最优表中该元素的值， 若值为null或者值比qosmin小， 将值赋给qosmin；

}

(7)if (qosmax

(8)取s.qos中时间花费的属性值与qosmax相加， 得到的值存入QoS最优表s键值对应的位置。

层次状态机的终止状态可以看作是一个只有输入的虚拟服务，它的最优QoS值即为服务组合的最终QoS值。算法1不仅得到了服务组合的最终QoS值，选择每个服务时的最优QoS值也在组合过程中记录下来。

4.2 基于约束条件的去冗余服务过程

采用第3节中的超状态构建过程，会导致组合服务中存在冗余服务。3种情况下会存在冗余服务：①k层的服务s，其输出并没有被后续服务利用；②k层存在被重复计入的服务；③k层的多个服务互相组合，输出的参数对于后续服务的作用是相同的。

针对情况①，最终采取反向搜索排除无用服务。针对情况②、情况③采用算法2去除冗余服务。

为了减小运算规模，应对组合按照约束条件去除冗余服务。结合算法2，得到符合约束条件的服务组合最简集。由于最终采取反向搜索，输入应包含上一层的服务，算法开始时输入的即为终止状态的虚拟服务。

算法2

输入：输出一层参数的服务集集合sersrclist，上一层的服务组合方案slast

输出：基于约束条件的去冗余服务方案集合

(1)循环sersrclist：

(2)将服务集集合的元素两两对比{

(3)检查是否存在元素A是元素B的子集；

(4)若存在， 删除规模大的集合；

}

(5)取sersrclist的队头元素s， 把s中的每个服务作为集合存入res；

(6)forj=1循环sersrclist：

(7)比较res中的每个元素和sersrclist[j], 存在交集的每一项移入resR并在res中删除, 并把交集元素存入serU；

(8)对serU的每个元素{

(9)if(map无这个元素)存入map，key值为serU[i]，value为res中每一项与serU[i]组合的服务。

(10)elsevalue追加res中每一项与serU[i]组合的服务}

(11)res中剩余没有交集的元素sres：

(12)判断sersrclist[j]中的每个服务s：

(13)从map中取key为s的值， 检查其中的元素， 如果不存在sres的子集， 将sres与组合作为一个元素进入到resR中；

(14)将resR的值赋给res；

(15)循环res{

(16)取上一层服务的约束服务的集合slast.s.∂；

(17)对比元素留下符合约束要求的组合方案。}

4.3 服务方案选择

将上述过程结合可得到基于层次状态机的服务组合优化算法。算法1得到了各个服务在组合中的最优QoS值，取服务状态机本身QoS的时间维度的值，用服务的最优QoS减去服务本身的值，得到前序服务组合的最优QoS值，来对所有前序候选服务进行筛选。

采用反向搜索，排除输出参数无用的服务，也使层次状态机是可达的。首选对终止状态进行处理。把终止状态看作是一个只有输入参数的虚拟服务，输入参数为用户的目标输出参数。将输出这些参数的服务存入变量sersrc，利用算法1得到的最优QoS筛选服务。得到的参数服务候选集经过算法2，得到去冗余符合约束的服务组合方案存入listLeaf。循环服务组合方案集合：创建listTree队列；list-Tree.push(服务方案)；创建树集合listTrees；listTrees.push(listTree)。以上流程如算法3所示。

算法3

输入：listLeaf,listTrees,result

输出：result

(1)检查listLeaf是不是只包含一个方案且方案中只有一个起始状态的虚拟服务；

(2)是的话将listTrees[0]加入result终止递归， 返回结果， 不是的话继续；

(3)循环listLeaf中的元素；

(4)分别找到元素的输入参数对应的前服务， 存入；

(5)利用算法1得到的QoS筛选符合最优QoS的服务；

(6)利用算法2对筛选后的各个参数的服务集去冗余组合， 得到元素的前序服务组合方案集合存入listTreenew；

(7)循环listTreenew： {

(8)创建listTree数组；

(9)listTree.push(listTreenew元素)；

(10)listTree.push(listTrees[0])；

(11)listTrees.push(listTree)；

(12)listLeaf.push(listTreenew元素)；

}

(13)listLeaf队头元素出队；

(14)listTrees队头元素出队；

(15)继续用新的listLeaf,listTrees,result调用本程序；

算法3是由终止状态出发，以其为根结点，找到它的前序服务组合方案，然后再以前序服务为结点，不断添加叶子结点，树的每条路径就是一个组合方案。算法3采用广度优先，算法第(1)行～第(2)行是终止条件，即组合方案到达了起始状态，满足了用户的输入参数需求。算法第(3)行～第(6)行获得它们符合约束的前序服务组合方案存入listTreenew。算法第(7)行～第(12)行把前序服务挂在相应的父节点下，将这条路径保留在listTrees中，将新的需要找前序服务的服务进入队列listLeaf。第(13)行～第(15)行将已有叶子节点的父节点出队，继续递归。

4.4 仿真实验与结果分析

实验主要验证上述算法在寻找组合方案时的有效性，将其与传统的枚举组合树法进行对比。采用选择不同的服务社区数量和候选服务数量，比较两种算法在此情况下运行时间的变化。本实验采取的服务数据来自QWS数据集，但由于QWS数据集不存在约束条件以及服务参数的信息，因此采取随机生成法为这些服务生成约束条件和服务参数。初始化服务数据的过程如下：首先设置模拟参数数据建立服务社区之间的参数依赖关系，再根据每个服务社区参数构造一批参数类似的服务，其中候选服务来自QWS数据集，每个服务的参数参考服务社区的参数随机生成。为了模拟在组合过程中各个服务之间的约束逻辑，同样采用随机生成法，为这些服务生成一些随机的约束逻辑和用户请求。

表2、表3分别是两种算法在候选服务保持10、20、30的状态下，服务社区分别为3时、4时的时间花费情况。针对每种实验参数设置，随机生成不同的约束条件实验50次，以50次实验的平均运行时间作为结果进行对比。

由表2、表3可以看出，层次筛选法明显优于传统组合树法，根据任务的增多，在表3中，20个任务时传统方法已经达到秒级单位，层次筛选法时间增长的趋势明显低于传统方法。

表2 3个服务社区下算法的时间花费/ms

表3 4个服务社区下算法的时间花费

5 结束语

选择状态机进行服务组合的情况下，当转移过多、状态爆炸时，可以进一步选用层次状态机。提出描述服务状态机和服务社区的概念，根据用户的输入以及目标输出，提出方法不断划分超状态，直至最后超状态输出的参数并集符合用户的要求。在这个过程中，会产生冗余服务，而且也没有考虑用户的非功能性需求。与此同时考虑到服务之间的约束逻辑，基于这三方面对服务组合方法进行优化，构建过程中筛选符合要求的候选服务，最终得到符合约束条件的最优QoS组合方案。经过仿真实验的对比，验证该方法是行之有效的。

研究取得了一定的成果，但是工作仍然有待完善。研究主要在模拟好的服务社区数据的基础上，基于层次状态机对服务进行组合和优化，并没有考虑到如何对相似的服务进行聚合形成服务社区。未来的研究工作中，应完善服务聚合的方法。