近年来,Web服务的数量在不断增长,同时用户的需求也在增长,而单一的服务有时不能满足用户需求,于是要求Web服务合成,即将已有的Web服务连接与合并起来,生成新的Web服务,同时也为现有的服务集合增加价值。围绕Web 服务组合提出了众多的组合方法。比较典型的有基于工作流的服务组合方法[1];文献[2]将用DAML-S描述的Web服务转换为一组线性逻辑公式,使用线性逻辑定理证明的
方式来进行服务自动组合;文献[3]通过分层任务网络规划来实现服务的自动组合,利用SHOP2规划器进行求解。文献[4]给出了一种半自动的服务组合方法,将Web服务组合问题形式化为一个AND/OR图中的搜索问题,给出了一种搜索算法以用来确定满足服务请求的合成服务。以上方法都能得到满足用户需求的组合计划,但是这些组合计划都是服务组合的数据流模型 ,并没有给出服务组合的控制流结构,比如顺序、并行和循环等。同样的数据流模型,由于控制结构的组合方式不同,组合服务的性能会有差异。文献[5]611-612提出了一种算法来抽取并发关系,获取性能最佳的具有控制流结构的组合方案,但是算法存在很多的缺陷,而且选择性能最佳(耗时南粤论文中心(WWW.NYLW.NET)最低)的方案是通过人工计算得出,不能很好的实现整个流程自动化。
因此,本文提出一种基于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网可采用可达树法、不变量分析、约简等方法,其中可达标识图分析法直观简捷,利用生成算法得到可达标识图,然后利用可达标识图进行分析,提取网中变迁之间以及变迁序列之间的各种并发关系,之后根据相应算法,得到性能最优的组合结构;最后转换为业务过程执行语言抽象流程。 (责任编辑：南欧)转贴于南粤论文中心: http://www.nylw.net(南粤论文中心__代写代发论文_毕业论文带写_广州职称论文代发_广州论文网）
- 毕业论文定制
南粤论文中心提供本科/研究生/博士毕业论文，从提纲，开题到后期免费修改,免费指导答辩等 ，联系人：魏老师，电话：13450375436。 - 代写代发职称论文
南粤论文中心提供职称论文代写，报告总结，演讲致辞,心得体会,党团辅导等代写服务并推荐发表省级,国家级,核心杂志包发。联系QQ:631069747。
基于Petri网的Web服务组合优化方法研究
来源：南粤论文中心(WWW.NYLW.NET) 作者：张金朋 发表于：2010-11-30 16:36 点击：次
【关健词】Petri网;Web服务组合;并发;费用;组合优化
摘 要:在实际应用中,需要将各种Web服务进行组合和集成以创建动态Web应用。为了使服务组合性能最优,提出一种Web服务组合优化算法,该算法在满足用户需求的同时,根据已有的Web服务,自动获取性能最优的服务组合方案。利用Petri网进行建模,采用可达图进行分析,通过提取网中变
顶一下
(0)
0%
踩一下
(0)
0%
版权声明：因本文均来自于网络，如果有版权方面侵犯,请及时联系本站删除.
