2.1 根据用户需求构造Petri网模型 在Web服务库中,选择合适的服务组合成满足用户需求的Web服务,可以通过算法1得到其Petri网模型。 算法1 构造组合服务的Petri网模型 输入:用户需求WS(IR,OR) 输出:满
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) 搜索结束,提示缺少的输入参数,反馈给用户知道。可能有多个南粤论文中心(WWW.NYLW.NET)操作都可以满足用户需求,把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 南粤论文中心(WWW.NYLW.NET)
算法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有一条抑止弧。 (责任编辑：南欧)转贴于南粤论文中心: http://www.nylw.net(南粤论文中心__代写代发论文_毕业论文带写_广州职称论文代发_广州论文网）
顶一下
(0)
0%
踩一下
(0)
0%
版权声明：因本文均来自于网络，如果有版权方面侵犯,请及时联系本站删除.
