基于WSDG的Web服务组合可靠性预测

谢春丽 李必信 苏志勇

(1东南大学计算机科学与工程学院，南京 211189)(2江苏师范大学计算机科学与技术学院，徐州 221116)

基于WSDG的Web服务组合可靠性预测

谢春丽1，2李必信1苏志勇1

(1东南大学计算机科学与工程学院，南京 211189)(2江苏师范大学计算机科学与技术学院，徐州 221116)

为了更好地对基于SOA的Web服务组合进行可靠性预测，提出了基于服务依赖图的可靠性模型.首先介绍了Web服务组合的描述语言WS－BPEL，以及用来描述服务业务流程的原子活动和结构化活动;其次在传统的控制流图的基础上提出了Web服务依赖图的概念，Web服务依赖图用来描述Web服务组合的执行行为和结构信息，包括服务名、服务类型和服务的可靠性，以及服务之间的转移概率、转移可靠性等信息;然后分析BPEL的原子活动和结构化活动的控制依赖关系，并在此基础上构造相应的Web服务依赖图.最后基于服务依赖图的遍历，应用可靠性预测算法计算Web服务组合的可靠性.实例分析结果表明，基于依赖图的可靠性预测方法具有简便性和易处理性.

Web服务;可靠性;Web服务依赖图;BPEL

Web服务是自包含的、模块化的应用程序，它可以在网络中被描述、发布、查找以及调用，具有良好的封装性、耦合松散及高度可集成等一些特征.在商业应用中，为了满足用户的功能需求需要将多个Web服务组合起来，同时服务组合还需要满足用户对可靠性、安全性和性能等服务质量(QoS)的要求.由于这些Web服务由不同的服务提供者提供，具有物理上分布分散、运行于不同的平台等一些特征，并且满足某个功能需求的可供选择的服务越来越多，使得Web服务组合的服务质量控制更加复杂.同时Web服务组合的复杂性及执行失效的高昂代价也使得Web服务组合的可靠性建模和预测变得更加重要和复杂.

软件可靠性研究的基本问题是如何将系统结构更好地表现出来，其中使用最多的是控制流图(CFG)［1－3］.用 CFG 表示软件系统的结构，通常假设系统各组件之间的转移关系满足Markov性，结合组件的失效行为(可以用可靠性或者失效率来表示)，构建基于状态的模型，软件系统的可靠性描述为从初始状态转移到最终成功状态的概率.但是对于松耦合的Web服务来说，消息交换是各服务之间进行交互的主要机制［4］，CFG只能表示服务之间简单的控制流关系(顺序、选择、循环等)，但实际上对Web服务来说，由于服务之间的松耦合性，用传统的构建控制流的方法很难将服务之间的关系完整地表达出来，尤其是消息传递时，例如，虽然活动A和B之间没有显式控制关系，但是活动A发送消息到活动B，其中隐含了活动A和B之间的控制关系［5］.本文将对已有的CFG进行扩展，构成服务依赖图(WSDG)，用于描述服务之间的控制流、消息流，并增加服务的可靠性、服务的转移概率、服务的转移可靠性等一些有关可靠性的属性信息.

目前关于构件和Web服务的可靠性预测的研究有许多成果［6－11］. 文献［7］介绍了基于场景的构件系统可靠性分析方法.使用构件依赖图(CDG)来表示基于构件的软件的执行场景，属于基于路径的方法.本文的Web服务依赖图的思想来源于构件依赖图，但是本文从BPEL文档出发，建立服务组合系统的依赖图，基于BPEL的可靠性模型比基于场景的更具有确定性和可应用性.文献［1］将基于构件系统的可靠性预测方法分为2类:基于状态的方法和基于路径的方法.文献［10－11］应用Markov模型对软件系统的可靠性进行建模，主要是对模块或构件之间的结构和它们之间的转移信息进行建模，属于基于状态的方法.但是转移矩阵通常都是稀疏矩阵，应用效率不高.本文则将转移可靠性、转移概率和服务可靠性相结合，将服务之间的结构关系转换为图的形式，借助于图的遍历过程计算组合服务的可靠性，提高了计算效率.

1 WS－BPEL

Web服务作为SOA的应用实例，其体系结构是基于3种角色(服务提供者、服务注册中心和服务请求者)之间的交互.基于现有的SOA，服务提供者在服务注册中心发布各自的Web服务，服务请求者通过UDDI注册中心查询所需服务时，注册中心返回该服务的描述文件(包括WSDL文档、服务质量信息等)，服务请求者可以从描述文件中获取服务质量或绑定信息，根据服务质量标准选定服务并绑定到所需服务的接口上.服务请求者通常请求调用多个Web服务，并使用WS－BPEL(简称BPEL)来描述多个Web服务的调用和交互.Web服务使用WSDL将其描述为服务端口的集合，然后BPEL以业务流程活动的形式集成多个Web服务，构成复杂的Web服务组合.BPEL描述的业务流程的每一步称为一个活动，主要分为原子活动和结构化活动.下面将简要介绍这些活动.

1)原子活动

原子活动描述业务流程行为的基本步骤，是流程定义中所使用的活动原语，与服务进行交互，操作传输数据或处理异常.BPEL包含8种类型的原子活动:〈receive〉、〈reply〉、〈invoke〉、〈assign〉、〈throw〉、〈exit〉、〈wait〉和〈empty〉.原子活动中与外界进行交互的活动是:〈invoke〉、〈reply〉和〈receive〉.流程的伙伴之间通过使用这3种活动发生交互，通过指定端口类型、操作以及伙伴，这些活动中的每一种活动被标识出它所属于的Web服务调用.

2)结构化活动

结构化活动描述了一系列活动的执行次序.通过BPEL所提供的结构化活动，可以将各种活动进行组合，形成活动有序执行的流程.这些结构化活动，类似于传统编程语言中的控制结构，表达业务协议中所涉及的控制模式、数据流、故障和外部事件的处理以及在流程实例之间进行消息交换的协调.BPEL包含8种类型的结构化活动:顺序活动〈sequence〉，选择活动〈if〉，循环活动〈while〉、〈repeatUntil〉、〈forEach〉，并行活动〈flow〉，事件选择活动〈pick〉，BPEL语句块〈scope〉.

下面将从Web服务的角度出发，集中关注与Web服务的调用、消息交互相关的活动，它们为Web服务描述了输入消息、输出消息以及Web服务组合的执行行为和结构信息等.

2 Web服务依赖图

依赖图起源于CFG，CFG是程序代码中用来描述程序流程、分支结构等的典型方法.Yacoub等［6］将CFG引用到基于构件的应用程序中，用来表示构件间的结构关系以及可能的执行路径，称之为CDG.本文将传统的构件依赖图的原理应用到Web服务中，对Web服务及消息传递路径进行描述，称之为Web服务依赖图(WSDG)，其定义如下:

定义1(服务依赖图)WSDG定义为四元组〈N，E，s，t〉，其中〈N，E〉为有向图，s为开始节点，t为终止节点.N为节点的集合E为有向边的集合

定义2(节点n)n∈N用来表示Web服务，ni表示 Web 服务Wi，ni=〈Wi〉，其中Wi是第i个Web服务，且

定义3(服务Wi)Web服务由三元组〈Ni，Ti，Ri〉定义，其中Ni为服务名，Ti为服务类型，Ti指明当前服务所属的类型，可以是基本服务，也可以是包含结构化活动的服务，Ti={s，t，basic，structure，while，scope}.其中，s表示起始节点，t表示终止节点，basic活动包含了〈invoke〉、〈reply〉和〈receive〉，而结构化活动〈sequence〉、〈if〉、〈flow〉、〈pick〉和〈forEach〉最终可以进一步拆分为若干个basic活动的组合.〈while/repeatUntil〉，〈scope〉等结构化活动也可以进一步拆分为一个活动的多次循环调用.Ri为服务的可靠性，指服务在被调用时能够正确执行的概率R且 0≤Ri≤1.

定义4(有向边e) 有向边e表示从一个服务转移到另外一个服务的控制流，由三元组表示，其中Tij表示从节点ni到nj的转移路径名，RT

ij表示从节点ni转移到节点nj的可靠性，Pij表示从节点ni到转移到节点nj的转移概率

3 基于WSDG的可靠性模型

3.1 BPEL活动分析

BPEL中包含了原子活动和结构化活动，活动之间存在依赖关系［12］.本文所关注的是活动之间的控制依赖关系.BPEL中影响活动之间的控制依赖的因素主要有3个:

1)如果活动之间有消息传递，即活动A发送消息到活动B，那么称活动B控制依赖于A［5］.如BPEL程序中实现服务消息交换机制的语句调用，同步服务机制的receive－reply语句，说明了原子活动receive和reply活动之间的控制依赖关系.

2)结构化活动定义了其所包含的原子活动或结构化活动的控制依赖关系.BPEL的结构化活动主要有〈sequence〉、〈if〉、〈pick〉、〈flow〉、〈for Each〉、〈while〉/〈repeatUntil〉和〈scope〉.

·sequence包含一组顺序执行的活动1，2，…，n.

·if根据条件表达式的结果进行不同活动的选择.

·pick结构包含n个互斥的消息事件，当任意一个消息到达时，相应的活动被触发.

·flow结构中的n个活动并发执行.

· forEach，while，repeatUntil都是循环结构，反复执行活动.

3)BPEL中的变量(variable)和链接(link).变量不仅可以用于〈if〉、〈while〉/〈repeatUntil〉活动的条件表达式中，也可以用于〈flow〉活动中source元素的条件中［8］，而链接是〈flow〉活动中的布尔变量，用来在〈flow〉活动中定义更多的控制结构.如下面的BPEL程序片段中定义了结构化活动flow中，活动X和活动Y之间的控制依赖关系，这种控制依赖关系通过source和target元素获取.

3.2 Web服务依赖图的构造

根据3.1节给出的3个因素来分析BPEL文档，获得活动之间的控制依赖关系，进而构造服务组合的Web服务依赖图.图1中给出了BPEL到对应的WSDG的转换.对于原子活动中与Web服务交互的〈invoke〉、〈receive〉和〈reply〉活动而言，它们调用了Web服务的操作，是执行的实体，所以将其看作是依赖图中的节点，节点类型Ti=basic，如图1中的服务依赖图(1)所示.〈assign〉，〈empty〉，〈wait〉，〈throw〉和〈exit〉这5个原子活动不需要调用具体的服务，因此不予考虑.对于结构化活动而言，它们将各种基本活动或者其他结构化活动进行组合，形成活动有序执行的流程.本文仅讨论有多个基本活动组成的结构化活动，根据3.1节将BPEL的结构化活动转化为相应的依赖图.〈sequence〉、〈if〉、〈pick〉、〈flow〉和〈forEach〉活动由多个活动组成，其中每个活动既可以是基本活动也可以是结构化活动，因此在依赖图的定义中，这几个结构化活动可进一步分解成多个节点和边的表示形式，如图1中服务依赖图(2)～(4)所示.如果结构化活动〈sequence〉、〈if〉、〈pick〉、〈flow〉和〈forEach〉中包含其他结构化活动，可以按照上述方法进一步递归分解，最终可以分解为若干个基本活动的组合.循环结构〈while〉/〈repeatUntil〉是自身包含的活动反复执行，为了便于表示依赖图，将〈while〉/〈repeatUntil〉和〈scope〉活动也用节点来表示，并分别定义节点类型Ti为while和scope，表明Wi包含Web服务依赖图Wi－WSDG，如图1中服务依赖图(5)和(6)所示.

图1BPEL到WSDG的转换

3.3 可靠性预测算法

对于给定的BPEL文档，首先根据3.1节的3种因素，构造出包含基本活动和各种结构化活动的WSDG，除了scope和while结构活动之外其余的所有结构化活动根据图1逐步分解为基本服务的组合，最终得到的WSDG中有基本服务、scope结构和while结构.WSDG中Web服务之间的依赖关系已经给出，但是WSDG中节点和边的信息参数并不完整，需要对这些参数进行预测.下面讨论WSDG中的参数问题.

1)Web服务的可靠性RiWeb服务可靠性的来源有很多，如:服务提供者可以提供可靠性值作为参考;服务请求者可以对该服务进行可靠性测试获得可靠性值;根据Web服务器所记录的历史数据计算可靠性.本文假设basic类型的Web服务的可靠性已知.对于服务类型为while/repeatUntil和scope的Web服务，则基于其所包含的Web服务依赖图来计算.Scope类型的Web服务可靠性用它所包含的Web服务的可靠性R1来表示，即

假设while类型的Web服务包含的循环服务为W1，P为while结构中继续循环的概率，R1为W1的可靠性，则while类型的Web服务的可靠性计算公式为

2)转移的可靠性RTijWeb服务的分布性使得服务之间的转移失效率在可靠性预测中起着关键作用，因此必须考虑Web服务之间的转移失效率.关于参数RTij的分析，在文献［9］中已经有所讨论，本文不再进行讨论，均假设转移可靠性已知.

3)转移概率PijPij表示从Web服务Wi转移到Wj的概率.通过对依赖图的分析，发现并不需要考虑各个服务之间的转移情况，而是根据依赖图得出可靠性预测所需要的转移概率参数.这里通过转移次数来计算转移概率.

给定WSDG以及所需要的参数后，就可以预测Web服务组合的可靠性.下面给出Web服务组合的可靠性预测算法.

算法1 Web服务组合可靠性预测算法

该可靠性预测算法将服务组合的Web服务依赖图作为输入，从起始节点开始并使用堆栈存贮节点，通过节点的依赖关系，找出当前节点的所有后续节点，来进行图的深度优先遍历.在对图中每个节点进行遍历的同时计算服务的可靠性.假设每个服务在同一层次只能出现在一个结构化活动中，那么组合服务的依赖图其实就是一个图的最小生成树，有n－1条边，根据深度优先遍历的算法，可知该算法的复杂度为O(n).

如果当前活动Wi的后续节点是由基本服务w1，w2，…，wn组成的 sequence 结构或者串行的for－Each结构，则根据上述算法，其结构化活动的可靠性可用下式计算:

其中，Pj(j+1)=1，j=1，2，…，n.如果当前活动Wi执行后，接下来执行的活动是由基本服务w1，w2，…，wn组成的forEach，flow，if，pick结构，则结构化活动的可靠性可按下式计算:

如果是并行的forEach或者flow结构，式(4)中的Pij=1，若是if或pick结构，则

4 应用实例分析

本文以文献［13］的申请贷款服务这一Web服务组合为例，分析该应用的BPEL文档，生成依赖图，最后预测该应用的可靠性.申请贷款的场景描述如下:用户需要申请贷款，将个人信息和贷款信息提交给申请贷款服务.应用接收到用户请求后，将执行一个评估验证流程，以决定批准或拒绝贷款.评估验证流程根据用户申请贷款额度和用户信用信息，分为2种情况:首先进行评估，贷款额度低(小于10 000美元)且信用好的用户将自动批准;对高额度贷款或者贷款额度低但信用差的用户将进行进一步验证，决定是否批准贷款.最终应用将是否批准贷款的结果以消息的形式通知用户.该Web服务组合的依赖图如图2所示.

通过对依赖图的分析，需要进行预测的参数主要有:每个服务的可靠性、每个转移的可靠性、转移概率.使用软件Matlab对这些参数进行模拟，如表1和表2所示.最后采用可靠性预测算法，得到申请贷款应用的可靠性为Rcomp=0.807 1.

图2 申请贷款服务的WSDG

表1 申请贷款服务的可靠性参数

表2 服务转移参数

5 结语

本文介绍了Web服务组合的一种可靠性预测方法.首先将BPEL转化为Web服务依赖图，然后根据依赖图得到需要预测的参数，最后基于WSDG和参数估计值计算Web服务组合的可靠性.本文主要贡献是基于Web服务组合语言BPEL构造用于可靠性预测的Web服务依赖图;依赖图中处理了选择、并发、循环和scope结构.本文所提出的Web服务依赖图也可以应用于Web服务组合执行时间、价格等的计算.接下来将进一步研究Web服务的可靠性参数的多种预测方式和依赖图的精确建立.

［1］ Gokhale S S.Architecture－based software reliability analysis:overview and limitations［J］.IEEE Transactions on Dependable and Secure Computing，2007，4(1):32－40.

［2］ Hansen K M，Brønsted J.RH－02－2010 Modeling service composition reliability in pervasive computing［R］.Reykjavik，Iceland:Science Institute，University of Iceland，2010.

［3］ Cheung R C.A user－oriented software reliability model［J］.IEEE Transactions on Software Engineering，1980，6(2):118－125.

［4］ Object Management Group，Inc.Business process modeling notation，V1.1 ［EB/OL］.(2008－01)［2011－10－31］.http://www.omg.org/spec/BPMN/1.1/.

［5］ Pautasso C，Alonso G.Visual composition of Web services［C］//Proc of Human Centric Computing Languages and Environments.Auckland，New Zealand，2003:92－99.

［6］ Yacoub S，Cukic B，Ammar H H.A scenario－based reliability analysis approach for component－based software［J］.IEEE Transactions on Reliability，2004，53(4):465－480.

［7］苏志勇，周颖，李必信.面向用户的Web服务可靠性计算模型［J］.东南大学学报:自然科学版，2008，28(4):605－610.

Su Zhiyong，Zhou Ying，Li Bixin.User－oriented Web services reliability computing model［J］.Journal of Southeast University:Natural Science Edition，2008，28(4):605－610.(in Chinese)

［8］ Hsu C J，Huang C Y.An adaptive reliability analysis using path testing for complex component－based software systems［J］.IEEE Transactions on Reliability，2011，60(1):158－170.

［9］ Huang C Y，Lin C T.Analysis of software reliability modeling considering testing compression factor and failure－to－fault relationship［J］.IEEE Transactions on Computers，2010，59(2):283－288.

［10］ Wang Lijun，Bai Xiaoying，Zhou Lizhu，et al.A hierarchical reliability model of service－based software system［C］//Proc of33rd Annual International Computer Software and Applications Conference.Seattle，USA，2009:199－208.

［11］ Wang W L，Pan D，Chen M H.Architecture－based software reliability modeling ［J］.The Journal of Systems and Software，2006，79(1):132－146.

［12］ Zheng Y Y，Krause P.Automata semantics and analysis of BPEL［C］//Proc of the2007Inaugural IEEE International Conference on Digital EcoSystems and Technologies.Carins，Australia，2007:147－152.

［13］ OASIS.Web services business process execution language，Version 2.0［EB/OL］.(2007－04－01)［2012－04－19］.https://www.oasis－open.org/committees/download.php/23964/wsbpel－v2.0－primer.htm.

WSDG-based reliability prediction approach for Web service composition

Xie Chunli1，2Li Bixin1Su Zhiyong1

(1School of Computer Science and Engineering，Southeast University，Nanjing 211189，China)
(2School of Computer Science and Technology，Jiangsu Normal University，Xuzhou 221116，China)

In order to estimate the reliability for Web service compositions based on service－oriented architecture(SOA)，a Web services dependency graph(WSDG)－based reliability prediction model is proposed.First the description language for web service composition WS－BPEL is introduced，and the atomic activity and structural activity which describe business process for web services are presented.Then the concept of WSDG is proposed based on the traditional control flow graph(CFG).WSDG is used to describe the execution behavior and the structural information for web services composition，such as service name，service type，service reliability，transition probability of service and reliability of transition.Moreover，control dependencies of basic activities and structured activities of business process execution language(BPEL)are analyzed and the WSDG of compositions are constructed.Finally，an algorithm for predicting the reliability of Web service compositions is presented based on the WSDG traversal.An example shows that the approach is simple and tractable.

Web services;reliability;Web services dependency graph(WSDG);business process execution language(BPEL)

TP311

A

1001－0505(2012)06－1074－06

10.3969/j.issn.1001－0505.2012.06.010

2012－05－17.

谢春丽(1979—)，女，博士生;李必信(联系人)，男，博士，教授，博士生导师，bx.li@seu.edu.cn.

国家自然科学基金资助项目(60973149)、教育部博士点基金资助项目(20100092110022)、江苏省高校科研成果产业化推进项目(JHB2011－3).

谢春丽，李必信，苏志勇.基于WSDG的Web服务组合可靠性预测［J］.东南大学学报:自然科学版，2012，42(6):1074－1079.［doi:10.3969/j.issn.1001 －0505.2012.06.010］