论文部分内容阅读
摘 要:在实际应用中,需要将各种Web服务进行组合和集成以创建动态Web应用。为了使服务组合性能最优,提出一种Web服务组合优化算法,该算法在满足用户需求的同时,根据已有的Web服务,自动获取性能最优的服务组合方案。利用Petri网进行建模,采用可达图进行分析,通过提取网中变迁之间以及变迁序列之间的各种并发关系,得到费用最廉的组合结构。
关键词:Petri网;Web服务组合;并发;费用;组合优化
中图分类号:TP391.9文献标识码:A
文章编号:1672-1098(2010)03-0058-05
收稿日期:2010-03-04
基金项目:国家自然科学基金资助项目(60873144);安徽省教育厅青年教师基金资助项目(2006jq1077)
作者简介:张金朋(1986-),男,安徽安庆人,在读硕士,研究方向:Web服务,Petri网及应用。
Study on Optimization Methods of Web Services Composition
Based on Petri Net
ZHANG Jin-peng, FANG Xian-wen
(School of Computer Science and Engineering, Anhui University of Science and Technology,
Huainan Anhui 232001, China)
Abstract:In practice dynamic web application is built by combination and integration of all kinds of Web services. In order to optimize performance of web services composition, an optimization composition algorithm was proposed, which meets client requirements, simultaneity according to current web services automatically obtains optimal solution of web services composition. The algorithm was modeled by using Petri net, reachable marking graph was adopted to analyze the performance. The cheapest composition structure was obtained by extraction of concurrency among transitions and among transition sequences.
Key words:Petri net; web services composition; concurrency; coast; composition optimization
近年来,Web服务的数量在不断增长,同时用户的需求也在增长,而单一的服务有时不能满足用户需求,于是要求Web服务合成,即将已有的Web服务连接与合并起来,生成新的Web服务,同时也为现有的服务集合增加价值。围绕Web 服务组合提出了众多的组合方法。比较典型的有基于工作流的服务组合方法[1];文献[2]将用DAML-S描述的Web服务转换为一组线性逻辑公式,使用线性逻辑定理证明的
方式来进行服务自动组合;文献[3]通过分层任务网络规划来实现服务的自动组合,利用SHOP2规划器进行求解。文献[4]给出了一种半自动的服务组合方法,将Web服务组合问题形式化为一个AND/OR图中的搜索问题,给出了一种搜索算法以用来确定满足服务请求的合成服务。以上方法都能得到满足用户需求的组合计划,但是这些组合计划都是服务组合的数据流模型 ,并没有给出服务组合的控制流结构,比如顺序、并行和循环等。同样的数据流模型,由于控制结构的组合方式不同,组合服务的性能会有差异。文献[5]611-612提出了一种算法来抽取并发关系,获取性能最佳的具有控制流结构的组合方案,但是算法存在很多的缺陷,而且选择性能最佳(耗时最低)的方案是通过人工计算得出,不能很好的实现整个流程自动化。
因此,本文提出一种基于Petri网的服务组合优化方法。首先针对用户需求,用Petri网建立Web服务组合模型;然后利用可达标识图进行分析,提取网中变迁之间以及变迁序列之间的各种并发关系,之后根据相应算法,得到性能最优的组合结构;最后转换为业务过程执行语言(BPEL)抽象模板,便于组合服务的执行,以方便用户使用。
1 基本概念
Petri网是一个良好的过程建模工具,一个Petri网图是一个双枝有向多重图,图中节点代表库所和变迁。Petri网有严格的数学基础,可以广泛应用于描述和研究具有并发、异步、分布式、并行、非确定性和随机性质的信息系统。
一个Web服务的行为基本上是一个偏序的操作集。因此,它可以直接被映射为一个Petri网。操作被映射为变迁,Web服务的一组输入参数被映射为库所,库所与变迁之间的流关系反映了Web服务构架中消息驱动行为的基本特性。
设描述Web服务的Petri网包括一个输入库所i(一个没有输入弧的库所)和一个输出库所o(一个没有输出弧的库所)。一个Petri网的输入库所用来接收信息,而输出库所则用来发送信息。在任何时候,一个Web服务将处于下列状态之一:未实例化 、就绪、执行、阻塞或完成。当一个Web服务处在就绪状态,就意味着在相应输入库所中的托肯使得输入库所的后集(变迁集)可以发生。而完成状态则意味着输出库所的前集已经发生,并且在相应的输出库所中产生了托肯。
定义1Web服务[6]2873-2873:Web服务是一组操作的集合,一个Web服务S定义为五元组S=(Id,SName,Desc,URL,Oper),其中,Id为Web服务的唯一标识;SName为web服务的名称;Desc为服务的描述;URL为服务的调用地址;Oper为服务的操作集合。一个操作用OPi(Ii,Oi)表示,Ii,Oi分别是操作OPi的输入、输出参数集合。
定义2两个服务操作有数据依赖关系:对于两个操作OPi(Ii,Oi)和OPj(Ij,Oj),如果Oi∩Ij≠,则称OPj(Ij,Oj)依赖于OPi(Ii,Oi),OPi(Ii,Oi)被OPj(Ij,Oj)依赖。
定义3用户组合服务需求用WSR(IR,OR)描述, 其中IR是用户提供的数据集合,OR是用户期望得到的数据集合。
定义4[6]2 874-2 875 服务组合模型是合理的,必须满足以下基本要求:
(1) 每个模型都存在一个输入库所i和一个输出库所o;
(2) 每个变迁、库所都在一条从输入库所i到输出库所o的路径上;
(3) 在任何情况下,服务组合总能最终终止,在终止的时候,只有输出库所中有token,而其它库所是没有token存在的;
(4) 在组合模型中没有死组合的存在,即任何一个变迁都有执行的可能。
本文只列出密切相关的定义,有些定义是通过扩展得来的,其它Petri网定义见文献[7]。
A+:的输出矩阵,A-:的输入矩阵,A:的关联矩阵。矩阵A的第i行向量简写为A(i)。一个变迁序列q=T1 T2 T3 …Tk, A(q)=A(1)+
A(2)+…+A(k)。 Price(Ti)表示变迁Ti发生的费用(这里指耗时), Price(q)表示发生变迁序列q的费用。
变迁之间的顺序关系:=(P,T;F,M0)是一个Petri网系统,M1∈R(M0),T1,T2,…,Tn∈T在标识M1下有顺序关系,当且仅当M1[T1>M2[T2…Mn[Tn>M′,且Ti∈T,i∈[2,n]在标识M1,M2,…,Mi-1下都没有发生权,仅仅在Mi下可以发生。即如果M1≥A-(1) and且M1+A(1)≥
A-(2)and…andM+A(1)+A(2)+…+A(n-1)≥A-(n)且i∈[2,n],M1+A(1)+…+A(i-1)≥
A-(i)andM1+A(1)+…+A(i-1)≯A-(j) ,j∈[i+1,n]。(不大于等于即不能满足每一个分量都大于等于A-(j)的每一个分量,此时不等价小于),则称为顺序的,记为T1·T2·…·Tn。
变迁之间的并发关系:=(P,T;F,M0)是一个Petri网系统,M∈R(M0),T1,T2,…,Tn∈T ,在标识M1下有并发关系,当且仅当(1)M[T1>且M[T2>…且M[Tn>;(2)对于每个Ti,M[Ti>M1,M1[T2>…且M1[Ti-1>且M1[Ti+1>…且M1[Tn>。即M≥A-(1)+A-(2)+…+A-(n)且i∈[1,n]M[Ti>M1,M1≥A-(1)+A-(2)+…+A-(n)],则称为可并发的,记为T1‖T2‖…‖Tn。
2Web服务组合模型
为了考虑费用(消耗时间),本文Web服务组合的Petri网模型在网模型=(P,T;F,K,W,M0)上稍作扩展,=(P,T;F,K,W,M0,λ),λ=(λ1,λ2,…,λn)为变迁发生的持续时间,Pi∈P,K(Pi)=1;M0(i)=1,其它库所的标识为0,所有库所容量为1。建立Petri网模型之后,分析Petri网可采用可达树法、不变量分析、约简等方法,其中可达标识图分析法直观简捷,利用生成算法得到可达标识图,然后利用可达标识图进行分析,提取网中变迁之间以及变迁序列之间的各种并发关系,之后根据相应算法,得到性能最优的组合结构;最后转换为业务过程执行语言抽象流程。
2.1 根据用户需求构造Petri网模型
在Web服务库中,选择合适的服务组合成满足用户需求的Web服务,可以通过算法1得到其Petri网模型。
算法1 构造组合服务的Petri网模型
输入:用户需求WS(IR,OR)
输出:满足用户需求的Petri网模型
(1) 选择一组操作OP,它们产生的输出可以满足用户需求即Or∈OR。组合服务W.Oper开始为空;
(2) 判断W是否满足WS(IR,OR)即由输入参数IR通过W得到OR.满足跳转到(5),否则下一步;
(3) 在OP中按顺序选择一个操作OPi,对OPi的每个输入参数IK,查看是否能由用户IR提供.如果可以,则将OPi加入W.Oper;如果不能,则选择一个操作OPj,它的某个输出能提供这个参数。如果这个操作的输入参数始终得不到满足,则需要回溯,去掉该操作,并在服务库中选择另一个操作替代OPi。如果某个输入参数始终得不到满足,跳转到(6);
(4) 跳转回(2);
(5) 搜索结束,对每个操作用一个变迁和两组库所表示,一组库所表示操作的输入参数,作为变迁的前集; 另一组库所表示操作的输出结果,作为变迁的后集。然后将它们组合起来形成一个大的网系统,库所i里放入一个标记,λi=Price(OPi),i=1,2,…,n;
(6) 搜索结束,提示缺少的输入参数,反馈给用户知道。可能有多个操作都可以满足用户需求,把Qos[8]纳入考虑范围,选择费用最低的组合服务Wopt。
2.2 构造最廉价控制流结构的组合方案
在不考虑并发,仅仅顺序执行的情况下,组合后服务运行消耗的时间大于等于各个原子服务消耗时间之和,而且现实中总是大于时间之和(服务之间传递参数消耗时间,分发数据、组装数据也要消耗一定的时间)。当某些原子操作间没有数据依赖的时候,可以让它们并发执行,消耗时间为耗时最多操作的运行时间。如果尽可能让没有数据依赖关系的操作并发执行,就可以大大提高服务组合的性能,从而抽取出具有最大并发数且费用最低(运行消耗时间最少)的组合结构有很不错的现实意义。
算法2 考虑并发情况改造可达标识图
输入:Petri网的可达标识图RG()
输出:带并发标记的可达标识图
(1) 构造A+,A-,A;
(2) for each 标识M∈RG() do
(3) 选择在该标识M下满足并发条件的最大的变迁集合,并把它放入集合S中;
(4) for each 集合C={Ti1,Ti2,…,Tik}∈Sdo
(5) M′=M+A(i1)+A(i2)+…+A(ik);
(6) 用虚线连接标识M→M′,并标记为“Ti1 ‖Ti2‖…‖Tik”,费用Priec为;Max(λi1,λi2,…,λik);
(7) for each Ti∈C do
(8)搜索在M下所有从Ti开始的最长顺序发生序列,qi=Ti·Ti1·…·Tim;
(9) 令q=Ti1·…·Tim;即去掉Ti后的序列, ifq≠ then 放入集合Q,Price (q)=λi1+λi2+…+λim;
(10) end for
(11) for each 集合Cq={q1,q2,…,qn}∈ Q do
(12) 选择在该标M识下满足并发条件的最大的变迁序列集合, 用虚线连接标识M→M′并标记为“q1‖q2‖…‖qn”,费用Price为Max(Price(q1),Price(q2),…,Price(qn));
(13) end for
(14) end for
算法3 抽取费用最廉的组合结构序列
输入:带并发标记的可达标识图,即算法2的输出
输出:费用最廉的组合结构序列
(1) 由带并发标记的可达标识图,生成有向图的带权邻接矩阵G,权值为弧上变迁(序列)的费用Price,如果从Vi到Vj有路到达,则G[i,j]=Price;否则G[i,j]=∞;
(2) 定义一个矩阵D用来记录所插入点的信息,D[i,j]表示从Vi到Vj需要经过的点,初始化D[i,j]=j;
(3) 把各个顶点插入图中,比较插点后的距离与原来的距离,G[i,j]=min{G[i, j], G[i, k]+G[k, j]},如果G[i, j]变小,则D[i,j]=k;
(4) 经过n次比较后最后必求得M0到终止标识的最短路径,D中包含了最短路径的信息,通过搜索D可以找到M0到终止标识的路径,作为算法返回结果。
3 实例分析
对于上述算法,可以举例说明。修改文献[5]610-611中的例子,假设在股票行业中,用户想通过一个“跨国公司名称”和“特定时刻”找出该公司在某一股市的股票折合人民币价格以及该公司总部所在城市。假设有一个Web服务库包括三个Web服务以及若干操作,相关情况如表1所示。
表1web服务库
编号服务名称操作输入参数输出参数耗时/ms
1ExchangeServiceUs2RmbUsPriceDateTimeRmbPrice55
Uk2RmbUkPrice DateTimeRmbPrice44
2StockServiceSearchPriceCompanyId DateTimeUsPrice30
3YellowPageServiceGetCompanyInfoCompanyName CompanyId AddressCityId60
GetCityInfoCityIdCityName45[BG)F]
假设某用户需要的组合服务是WSR({CompanyName,DateTime},{RmbPrice,CityName},根据算法1得到如图1所示的Petri网模型。
图1 服务组合的petri网模型
图1表示一个满足用户需求的服务组合模型,其中T1表示分发数据,记为 Distribute;T4表示组装数据,记为Assembly.这是两个瞬时变迁,即从发生到完成时间为0.T2,T3,T5,T6分别代表操作GetCompanyInfo,GetCityInfo,SearchPrice,Us2Rmb。P1,P2,P3,P4,P5,P6,P7,分别代表相应操作的输入输出参数CompanyName,CompanyId,CompanyId,CityName,DateTime,UsPrice,RmbPrice。i中的标记代表IR,o表示OR.P4到T2有一条抑止弧。
之后,可以得出可达标识图(见图2)。图2中三条虚线暂时可以不考虑,是为了后面的分析。对该可达图进行可达性、有界性、活性、完整性及前进性分析如下:
(1) 该组合服务是完全可达的 从M0开始的状态可达集R(M0)={M0,M1,M2,M3,M4,M5,M6,M7,M8}。状态集MS={M0,M1,M2,M3,M4,M5,M6,M7,M8}。可见,Mi∈MS,均有Mi∈R(M0),即该组合服务中任一个状态都是从M0可达。
图2 服务组合实例的可达标识图
(2) 该组合服务是有界的 在可达树中,每一个位置上的托肯数未超过1,因此该组合服务是安全的。
(3) 该组合服务是活的 从图2可以看出,从M0开始,Ti∈T(T是所有变迁的集合)都至少可以被从M0开始的激发序列fire一次,可见该组合服务的Petri网是活的。
(4) 该组合服务具有完整性 由图2可见,该组合服务的所有状态都从M0可达并且可以到达终止状态M8。
(5) 该组合服务具有前进性 在可达树中,任意状态之间没有出现无意义的循环。
由定义4知,该服务组合模型是合理的。
执行算法2后,可以得到如图2所示的带并发标记可达标识图(虚线即并发标记),把虚线等同普通弧考虑,费用作为弧上的权值,目标问题转化为求i到o的最短路径问题。采用Floyd(弗洛伊德)算法[9]找出最短路径,也就是最终所得,费用最廉的组合结构序列。
算法3复杂度为O(n3), 根据此算法, 图2得到的组合结构序列为T1·T2·((T5·T6)‖T3)·T4,G[0,8]=135(0代表M0,8代表M8),由组合结构序列,参照变迁所指原子服务,可以生成BPEL抽象流程模板。抽象流程可以用来呈现可执行流程的某些方面,通过抽象手段使得人们易于理解和沟通;同时以简单的抽象流程作为设计流程的起点,通过不断精化和改进,构建出复杂的可执行流程。抽象流程还可以用来实现协议匹配,来判断两个业务伙伴是否能够互相交互。BPEL抽象流程模板如下
4结论
Web服务组合是Web服务的一个重要研究方向。本文采用了Petri网技术对Web组合进行描述,并对组合服务的可达性、安全性、有界性、活性、完整性和前进性等特性进行了验证分析,利用可达标识图抽取变迁之间以及变迁序列之间的并发关系,它能够根据用户需求自动设计出性能最优的组合方案,从而转换为BPEL抽象模板。
参考文献:
[1] 董文莉, 胡建华.基于 BPEL 的 Web Service组合的数据流分析测试方法[J].软件学报, 2009, 20(8):2 102-2 112.
[2] RAO J, KUNGAS P,MATSKIN M. Logic-based Web services composition:From service description to process model[C]∥Proceedings of the IEEE International Conference on Web Services(ICWS),San Diego,California,2004:446-453.
[3] SIRIN E,PARSIA B,WU D,et al.HTN planning for Web Service composition using SHOP2 [J]. Journal of Web Semantics,2004,1(4):377-396.
[4] LANGQHA,SUSYW.AND/OR graph and search algorithm for discovering composite Web services[C]∥Int’1 Journal of Web Services Research,2005,2(4):46-64.
[5] 门鹏,段振华.一种基于Petri网的自动Web服务组合算法[J].西安电子科技大学学报:自然科学版, 2008, 35(4):609-613.
[6] 张佩云,黄波,孙亚民. 基于Petri网的Web服务组合模型描述和验证[J].系统仿真学报, 2007,19(12):2 872-2 876.
[7] 吴哲辉.Petri网导论[M]青岛:机械工业出版社,2006:80-130.
[8] 刘文彬,刘美桃.一种费用最廉的Web服务动态组合算法[J].科学技术与工程,2008,8(1):159-161.
[9] 严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,2006:45-98.
(责任编辑:李 丽)
关键词:Petri网;Web服务组合;并发;费用;组合优化
中图分类号:TP391.9文献标识码:A
文章编号:1672-1098(2010)03-0058-05
收稿日期:2010-03-04
基金项目:国家自然科学基金资助项目(60873144);安徽省教育厅青年教师基金资助项目(2006jq1077)
作者简介:张金朋(1986-),男,安徽安庆人,在读硕士,研究方向:Web服务,Petri网及应用。
Study on Optimization Methods of Web Services Composition
Based on Petri Net
ZHANG Jin-peng, FANG Xian-wen
(School of Computer Science and Engineering, Anhui University of Science and Technology,
Huainan Anhui 232001, China)
Abstract:In practice dynamic web application is built by combination and integration of all kinds of Web services. In order to optimize performance of web services composition, an optimization composition algorithm was proposed, which meets client requirements, simultaneity according to current web services automatically obtains optimal solution of web services composition. The algorithm was modeled by using Petri net, reachable marking graph was adopted to analyze the performance. The cheapest composition structure was obtained by extraction of concurrency among transitions and among transition sequences.
Key words:Petri net; web services composition; concurrency; coast; composition optimization
近年来,Web服务的数量在不断增长,同时用户的需求也在增长,而单一的服务有时不能满足用户需求,于是要求Web服务合成,即将已有的Web服务连接与合并起来,生成新的Web服务,同时也为现有的服务集合增加价值。围绕Web 服务组合提出了众多的组合方法。比较典型的有基于工作流的服务组合方法[1];文献[2]将用DAML-S描述的Web服务转换为一组线性逻辑公式,使用线性逻辑定理证明的
方式来进行服务自动组合;文献[3]通过分层任务网络规划来实现服务的自动组合,利用SHOP2规划器进行求解。文献[4]给出了一种半自动的服务组合方法,将Web服务组合问题形式化为一个AND/OR图中的搜索问题,给出了一种搜索算法以用来确定满足服务请求的合成服务。以上方法都能得到满足用户需求的组合计划,但是这些组合计划都是服务组合的数据流模型 ,并没有给出服务组合的控制流结构,比如顺序、并行和循环等。同样的数据流模型,由于控制结构的组合方式不同,组合服务的性能会有差异。文献[5]611-612提出了一种算法来抽取并发关系,获取性能最佳的具有控制流结构的组合方案,但是算法存在很多的缺陷,而且选择性能最佳(耗时最低)的方案是通过人工计算得出,不能很好的实现整个流程自动化。
因此,本文提出一种基于Petri网的服务组合优化方法。首先针对用户需求,用Petri网建立Web服务组合模型;然后利用可达标识图进行分析,提取网中变迁之间以及变迁序列之间的各种并发关系,之后根据相应算法,得到性能最优的组合结构;最后转换为业务过程执行语言(BPEL)抽象模板,便于组合服务的执行,以方便用户使用。
1 基本概念
Petri网是一个良好的过程建模工具,一个Petri网图是一个双枝有向多重图,图中节点代表库所和变迁。Petri网有严格的数学基础,可以广泛应用于描述和研究具有并发、异步、分布式、并行、非确定性和随机性质的信息系统。
一个Web服务的行为基本上是一个偏序的操作集。因此,它可以直接被映射为一个Petri网。操作被映射为变迁,Web服务的一组输入参数被映射为库所,库所与变迁之间的流关系反映了Web服务构架中消息驱动行为的基本特性。
设描述Web服务的Petri网包括一个输入库所i(一个没有输入弧的库所)和一个输出库所o(一个没有输出弧的库所)。一个Petri网的输入库所用来接收信息,而输出库所则用来发送信息。在任何时候,一个Web服务将处于下列状态之一:未实例化 、就绪、执行、阻塞或完成。当一个Web服务处在就绪状态,就意味着在相应输入库所中的托肯使得输入库所的后集(变迁集)可以发生。而完成状态则意味着输出库所的前集已经发生,并且在相应的输出库所中产生了托肯。
定义1Web服务[6]2873-2873:Web服务是一组操作的集合,一个Web服务S定义为五元组S=(Id,SName,Desc,URL,Oper),其中,Id为Web服务的唯一标识;SName为web服务的名称;Desc为服务的描述;URL为服务的调用地址;Oper为服务的操作集合。一个操作用OPi(Ii,Oi)表示,Ii,Oi分别是操作OPi的输入、输出参数集合。
定义2两个服务操作有数据依赖关系:对于两个操作OPi(Ii,Oi)和OPj(Ij,Oj),如果Oi∩Ij≠,则称OPj(Ij,Oj)依赖于OPi(Ii,Oi),OPi(Ii,Oi)被OPj(Ij,Oj)依赖。
定义3用户组合服务需求用WSR(IR,OR)描述, 其中IR是用户提供的数据集合,OR是用户期望得到的数据集合。
定义4[6]2 874-2 875 服务组合模型是合理的,必须满足以下基本要求:
(1) 每个模型都存在一个输入库所i和一个输出库所o;
(2) 每个变迁、库所都在一条从输入库所i到输出库所o的路径上;
(3) 在任何情况下,服务组合总能最终终止,在终止的时候,只有输出库所中有token,而其它库所是没有token存在的;
(4) 在组合模型中没有死组合的存在,即任何一个变迁都有执行的可能。
本文只列出密切相关的定义,有些定义是通过扩展得来的,其它Petri网定义见文献[7]。
A+:的输出矩阵,A-:的输入矩阵,A:的关联矩阵。矩阵A的第i行向量简写为A(i)。一个变迁序列q=T1 T2 T3 …Tk, A(q)=A(1)+
A(2)+…+A(k)。 Price(Ti)表示变迁Ti发生的费用(这里指耗时), Price(q)表示发生变迁序列q的费用。
变迁之间的顺序关系:=(P,T;F,M0)是一个Petri网系统,M1∈R(M0),T1,T2,…,Tn∈T在标识M1下有顺序关系,当且仅当M1[T1>M2[T2…Mn[Tn>M′,且Ti∈T,i∈[2,n]在标识M1,M2,…,Mi-1下都没有发生权,仅仅在Mi下可以发生。即如果M1≥A-(1) and且M1+A(1)≥
A-(2)and…andM+A(1)+A(2)+…+A(n-1)≥A-(n)且i∈[2,n],M1+A(1)+…+A(i-1)≥
A-(i)andM1+A(1)+…+A(i-1)≯A-(j) ,j∈[i+1,n]。(不大于等于即不能满足每一个分量都大于等于A-(j)的每一个分量,此时不等价小于),则称为顺序的,记为T1·T2·…·Tn。
变迁之间的并发关系:=(P,T;F,M0)是一个Petri网系统,M∈R(M0),T1,T2,…,Tn∈T ,在标识M1下有并发关系,当且仅当(1)M[T1>且M[T2>…且M[Tn>;(2)对于每个Ti,M[Ti>M1,M1[T2>…且M1[Ti-1>且M1[Ti+1>…且M1[Tn>。即M≥A-(1)+A-(2)+…+A-(n)且i∈[1,n]M[Ti>M1,M1≥A-(1)+A-(2)+…+A-(n)],则称为可并发的,记为T1‖T2‖…‖Tn。
2Web服务组合模型
为了考虑费用(消耗时间),本文Web服务组合的Petri网模型在网模型=(P,T;F,K,W,M0)上稍作扩展,=(P,T;F,K,W,M0,λ),λ=(λ1,λ2,…,λn)为变迁发生的持续时间,Pi∈P,K(Pi)=1;M0(i)=1,其它库所的标识为0,所有库所容量为1。建立Petri网模型之后,分析Petri网可采用可达树法、不变量分析、约简等方法,其中可达标识图分析法直观简捷,利用生成算法得到可达标识图,然后利用可达标识图进行分析,提取网中变迁之间以及变迁序列之间的各种并发关系,之后根据相应算法,得到性能最优的组合结构;最后转换为业务过程执行语言抽象流程。
2.1 根据用户需求构造Petri网模型
在Web服务库中,选择合适的服务组合成满足用户需求的Web服务,可以通过算法1得到其Petri网模型。
算法1 构造组合服务的Petri网模型
输入:用户需求WS(IR,OR)
输出:满足用户需求的Petri网模型
(1) 选择一组操作OP,它们产生的输出可以满足用户需求即Or∈OR。组合服务W.Oper开始为空;
(2) 判断W是否满足WS(IR,OR)即由输入参数IR通过W得到OR.满足跳转到(5),否则下一步;
(3) 在OP中按顺序选择一个操作OPi,对OPi的每个输入参数IK,查看是否能由用户IR提供.如果可以,则将OPi加入W.Oper;如果不能,则选择一个操作OPj,它的某个输出能提供这个参数。如果这个操作的输入参数始终得不到满足,则需要回溯,去掉该操作,并在服务库中选择另一个操作替代OPi。如果某个输入参数始终得不到满足,跳转到(6);
(4) 跳转回(2);
(5) 搜索结束,对每个操作用一个变迁和两组库所表示,一组库所表示操作的输入参数,作为变迁的前集; 另一组库所表示操作的输出结果,作为变迁的后集。然后将它们组合起来形成一个大的网系统,库所i里放入一个标记,λi=Price(OPi),i=1,2,…,n;
(6) 搜索结束,提示缺少的输入参数,反馈给用户知道。可能有多个操作都可以满足用户需求,把Qos[8]纳入考虑范围,选择费用最低的组合服务Wopt。
2.2 构造最廉价控制流结构的组合方案
在不考虑并发,仅仅顺序执行的情况下,组合后服务运行消耗的时间大于等于各个原子服务消耗时间之和,而且现实中总是大于时间之和(服务之间传递参数消耗时间,分发数据、组装数据也要消耗一定的时间)。当某些原子操作间没有数据依赖的时候,可以让它们并发执行,消耗时间为耗时最多操作的运行时间。如果尽可能让没有数据依赖关系的操作并发执行,就可以大大提高服务组合的性能,从而抽取出具有最大并发数且费用最低(运行消耗时间最少)的组合结构有很不错的现实意义。
算法2 考虑并发情况改造可达标识图
输入:Petri网的可达标识图RG()
输出:带并发标记的可达标识图
(1) 构造A+,A-,A;
(2) for each 标识M∈RG() do
(3) 选择在该标识M下满足并发条件的最大的变迁集合,并把它放入集合S中;
(4) for each 集合C={Ti1,Ti2,…,Tik}∈Sdo
(5) M′=M+A(i1)+A(i2)+…+A(ik);
(6) 用虚线连接标识M→M′,并标记为“Ti1 ‖Ti2‖…‖Tik”,费用Priec为;Max(λi1,λi2,…,λik);
(7) for each Ti∈C do
(8)搜索在M下所有从Ti开始的最长顺序发生序列,qi=Ti·Ti1·…·Tim;
(9) 令q=Ti1·…·Tim;即去掉Ti后的序列, ifq≠ then 放入集合Q,Price (q)=λi1+λi2+…+λim;
(10) end for
(11) for each 集合Cq={q1,q2,…,qn}∈ Q do
(12) 选择在该标M识下满足并发条件的最大的变迁序列集合, 用虚线连接标识M→M′并标记为“q1‖q2‖…‖qn”,费用Price为Max(Price(q1),Price(q2),…,Price(qn));
(13) end for
(14) end for
算法3 抽取费用最廉的组合结构序列
输入:带并发标记的可达标识图,即算法2的输出
输出:费用最廉的组合结构序列
(1) 由带并发标记的可达标识图,生成有向图的带权邻接矩阵G,权值为弧上变迁(序列)的费用Price,如果从Vi到Vj有路到达,则G[i,j]=Price;否则G[i,j]=∞;
(2) 定义一个矩阵D用来记录所插入点的信息,D[i,j]表示从Vi到Vj需要经过的点,初始化D[i,j]=j;
(3) 把各个顶点插入图中,比较插点后的距离与原来的距离,G[i,j]=min{G[i, j], G[i, k]+G[k, j]},如果G[i, j]变小,则D[i,j]=k;
(4) 经过n次比较后最后必求得M0到终止标识的最短路径,D中包含了最短路径的信息,通过搜索D可以找到M0到终止标识的路径,作为算法返回结果。
3 实例分析
对于上述算法,可以举例说明。修改文献[5]610-611中的例子,假设在股票行业中,用户想通过一个“跨国公司名称”和“特定时刻”找出该公司在某一股市的股票折合人民币价格以及该公司总部所在城市。假设有一个Web服务库包括三个Web服务以及若干操作,相关情况如表1所示。
表1web服务库
编号服务名称操作输入参数输出参数耗时/ms
1ExchangeServiceUs2RmbUsPriceDateTimeRmbPrice55
Uk2RmbUkPrice DateTimeRmbPrice44
2StockServiceSearchPriceCompanyId DateTimeUsPrice30
3YellowPageServiceGetCompanyInfoCompanyName CompanyId AddressCityId60
GetCityInfoCityIdCityName45[BG)F]
假设某用户需要的组合服务是WSR({CompanyName,DateTime},{RmbPrice,CityName},根据算法1得到如图1所示的Petri网模型。
图1 服务组合的petri网模型
图1表示一个满足用户需求的服务组合模型,其中T1表示分发数据,记为 Distribute;T4表示组装数据,记为Assembly.这是两个瞬时变迁,即从发生到完成时间为0.T2,T3,T5,T6分别代表操作GetCompanyInfo,GetCityInfo,SearchPrice,Us2Rmb。P1,P2,P3,P4,P5,P6,P7,分别代表相应操作的输入输出参数CompanyName,CompanyId,CompanyId,CityName,DateTime,UsPrice,RmbPrice。i中的标记代表IR,o表示OR.P4到T2有一条抑止弧。
之后,可以得出可达标识图(见图2)。图2中三条虚线暂时可以不考虑,是为了后面的分析。对该可达图进行可达性、有界性、活性、完整性及前进性分析如下:
(1) 该组合服务是完全可达的 从M0开始的状态可达集R(M0)={M0,M1,M2,M3,M4,M5,M6,M7,M8}。状态集MS={M0,M1,M2,M3,M4,M5,M6,M7,M8}。可见,Mi∈MS,均有Mi∈R(M0),即该组合服务中任一个状态都是从M0可达。
图2 服务组合实例的可达标识图
(2) 该组合服务是有界的 在可达树中,每一个位置上的托肯数未超过1,因此该组合服务是安全的。
(3) 该组合服务是活的 从图2可以看出,从M0开始,Ti∈T(T是所有变迁的集合)都至少可以被从M0开始的激发序列fire一次,可见该组合服务的Petri网是活的。
(4) 该组合服务具有完整性 由图2可见,该组合服务的所有状态都从M0可达并且可以到达终止状态M8。
(5) 该组合服务具有前进性 在可达树中,任意状态之间没有出现无意义的循环。
由定义4知,该服务组合模型是合理的。
执行算法2后,可以得到如图2所示的带并发标记可达标识图(虚线即并发标记),把虚线等同普通弧考虑,费用作为弧上的权值,目标问题转化为求i到o的最短路径问题。采用Floyd(弗洛伊德)算法[9]找出最短路径,也就是最终所得,费用最廉的组合结构序列。
算法3复杂度为O(n3), 根据此算法, 图2得到的组合结构序列为T1·T2·((T5·T6)‖T3)·T4,G[0,8]=135(0代表M0,8代表M8),由组合结构序列,参照变迁所指原子服务,可以生成BPEL抽象流程模板。抽象流程可以用来呈现可执行流程的某些方面,通过抽象手段使得人们易于理解和沟通;同时以简单的抽象流程作为设计流程的起点,通过不断精化和改进,构建出复杂的可执行流程。抽象流程还可以用来实现协议匹配,来判断两个业务伙伴是否能够互相交互。BPEL抽象流程模板如下
4结论
Web服务组合是Web服务的一个重要研究方向。本文采用了Petri网技术对Web组合进行描述,并对组合服务的可达性、安全性、有界性、活性、完整性和前进性等特性进行了验证分析,利用可达标识图抽取变迁之间以及变迁序列之间的并发关系,它能够根据用户需求自动设计出性能最优的组合方案,从而转换为BPEL抽象模板。
参考文献:
[1] 董文莉, 胡建华.基于 BPEL 的 Web Service组合的数据流分析测试方法[J].软件学报, 2009, 20(8):2 102-2 112.
[2] RAO J, KUNGAS P,MATSKIN M. Logic-based Web services composition:From service description to process model[C]∥Proceedings of the IEEE International Conference on Web Services(ICWS),San Diego,California,2004:446-453.
[3] SIRIN E,PARSIA B,WU D,et al.HTN planning for Web Service composition using SHOP2 [J]. Journal of Web Semantics,2004,1(4):377-396.
[4] LANGQHA,SUSYW.AND/OR graph and search algorithm for discovering composite Web services[C]∥Int’1 Journal of Web Services Research,2005,2(4):46-64.
[5] 门鹏,段振华.一种基于Petri网的自动Web服务组合算法[J].西安电子科技大学学报:自然科学版, 2008, 35(4):609-613.
[6] 张佩云,黄波,孙亚民. 基于Petri网的Web服务组合模型描述和验证[J].系统仿真学报, 2007,19(12):2 872-2 876.
[7] 吴哲辉.Petri网导论[M]青岛:机械工业出版社,2006:80-130.
[8] 刘文彬,刘美桃.一种费用最廉的Web服务动态组合算法[J].科学技术与工程,2008,8(1):159-161.
[9] 严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,2006:45-98.
(责任编辑:李 丽)