基于分布式工作流的时间管理模型

一种Web服务关联图的构造方法覃事刚1，刘建勋2，秦祖泽11.湖南电气职业技术学院汽车工程系1,湖南湘潭411101;2.湖南科技大学知识处理与网络化制造湖南省普通高等学校重点实验室2，湖南湘潭411201提纲本文结论问题提出论文思路相关算法问题提出问题提出很多Web服务之间存在联系买入卖出BCABCWebService1WebService2问题提出A4A1A1A4A1A4A1A2A1A1A1A1B3A1A4A1A1A4A1A4A1A2A1A1A1A1B3A1B3A1A2A1B3A1A4A1A2A1B3A1A4A1A2A1B3A1A1B3A1A4A1A2A1B3A1A4A2A1B3A1A4A1A2B3A1A1B3A1A4A1A2A1B3A1A4A1A2A1B3A1A4A1A2A1B3A1A4A1A2A1A1A4A1A1A4A1A2B3A1A4A1A2A1B3A1A4A1A2A1B3A1A4A1A2B3A1A4A1A2A1B3A1A4A1A2A1B3A1A4A1A2A1A4A4A1A4A1A1A4A1A2B3A1A4A1A2A1B3A1A4A1A2B3A1A4A1A2A1A4A1A4A1A1A4A1A2A1A1A4A1A2A1A1A4A1B3A1A1A1B3A1A4A1A2A1B3A1A4A1A2A1A1A2A1A4A2A4A2A2A1A1B3A1A4A1A2A1B3A1A2A1B3A1A4A1A2A1B3A1A4A1A2A1B3A1A1B3A1A4A1A2A1B3A1A4A2A1B3A1A4A1A2B3A1A1B3A1A4A1A2A1B3A1A4A1A2A1B3A1A4A1A2A1B3A1A4A1A2A1A1A4A1A1A4A1A2B3A1A4A1A2A1B3A1A4A1A2A1B3A1A4A1A2B3A1A4A1A2A1B3A1A4A1A2A1B3A1A4A1A2A1A4A4A1A4A1A1A4A1A2B3A1A4A1A2A1B3A1A4A1A2B3A1A4A1A2A1A4A1A4A1A1A4A1A2A1A1A4A1A2A1A1A4A1B3A1A1A1B3A1A4A1A2A1B3A1A4A1A2A1A1A2A1A4A2A4A2A2A1A1B3A1A4A1A2A1A1A2A4C1A3互联网上的Web服务WebServicesImplicitRelationshipGraph,WSIRG挑战如何搜集互联网上的Web服务如何挖掘出这些Web服务中存在的调用关系(本论文解决的主要问题)提纲本文结论问题提出论文思路相关算法论文思路一个Web服务是一个三元组ws(N,Im,Om)，其中N是服务名，Im是该服务的所有操作（Operation）的输入消息（inputmessage）集合{imsg1,imsg2,…,imsgm}，Om是所有操作的输出消息（outputmessage）集合{omsg1,omsg2,…,omsgm}。给定一个Web服务集U＝<W,M,

>。其中W表示服务名称的集合{ws1,ws2,ws3,ws4,ws5，……}，M表示W中的所有Web服务对应的消息的集合{m1,m2,m3,m4,m5，……}，

为W中元素与M

中元素的对应关系，若存在<ws,m>且r<ws,m>=1，则m是ws的输入消息；若存在边<ws,m>且r<ws,m>=-1，则m是ws输出（返回）消息；若不存在边<ws,m>且r<ws,m>=0，则m不是ws的消息（message）。论文思路给定一个Web服务集U={ws1,ws2,ws3,ws4,ws5}，该集合U对应的消息集合MSGset=inMSGset

outMSGset={m1,m2,m3,m4,m5}，其Web服务与消息之间的分配关系如图所示这样做具有下优点：i)可以建立Web服务集与输入/输出消息集之间的二元关系,用以揭示Web服务间的潜在调用关系；ii)可以可视化的方式直观的表达这种调用关系。iF（W，M，

i）oF（W，M，

o）iP({ws3,ws4},{m1,m3})oP({ws2},{m1,m2,m3})Gws将给定的Web服务集U=<W,M,

>分解为两个二元组：Ui=<W,M,

i>和Uo=<W,M,

o>。其中,Ui表示Web服务集与输入消息之间的二元关系，

Uo表示Web服务集与输出消息之间的二元关系；提纲本文结论问题提出论文思路相关算法相关算法——子项集F构造算法及分析子项:iP1({m1,m2,m3},{ws4})，iP2({m3,m5},{ws1})，

iP3({m2,m4},{ws5})，iP4({m1,m3},{ws3,ws4})，iP5({m1,m2},{ws2,ws4})，iP6({m1},{ws2,ws3,ws4})，iP7({m2},{ws2,ws4,ws5})，iP8({m3},{ws1,ws3,ws4})

ws1ws3ws4m3ws4m1m2m3ws5m2m4ws1ws3ws4m3ws5ws2ws4m2ws3ws4m1m3ws2ws4m1m2ws2ws3ws4m1在给定Web服务与消息二元关系上的子项集F的构建

P1

P2

（公式9）=(A1,B1)

(A2,B2)=(A1

A2,B1

B2)=P3(A3,B3)(服务集扩展运算，其中P3

U

且满足f(A3)=B3)P1

P2

（公式10）=(A1,B1)

(A2,B2)=(A1,

A2,B1

B2)=P3(A3,B3)(消息集扩展运算，其中P3

U且满足k(B3)=A3)相关算法——子项集F构造算法及分析其基本思想是：在已存在的分组集合中，对所有的分组两两做服务对象集扩展运算或是消息集扩展运算，生成新的分组并添加到分组集合续继参与相应的扩展运算，直到所有分组均满足f(A)=B的条件时结束。其中，初始分组集={({w1},f({w2})),({w1},f({w2})),……,({w|W|},f({w|W|}))}。相关算法——子项集F构造算法及分析在如图5所示的函数ConstructF中，初始集合中的元素个数|

|=|W|=n，对任意一子项(Ai,Bi)，满足|Ai|=1，|Bi|=|B|-1,即任意的两个ei，其相对应Bi集合中，有且只有|Bi|-1个消息元素msg

Bi相同，此时该算法的时间复杂度处于最坏情况。那么，把某个(A0,B0)且|A0|=1扩展成(A’,B’)且|A’|=|A|-1需要执行f(n-1)时间，依次对每个ei进行扩展的总的执行的时间为f(n(n-1))时间，因此该算法的时间复杂度为：O(f(n(n-1))=O(n2)。相关算法——WSIRG的构造算法及分析

在这个算法中，函数执行时间由三部分组成：构造输入子项集时间、构造输出子项集时间和Fo×Fi所用时间。构造输入/输出子项集时间已经知道均为O(n2)，而Fo×Fi执行时间取决于|Fi|和|Fo|，在最坏的情况下，有|Fo|=|W*|和|Fi|=|W*|，假设|W|=n，|W*|=n(n+1)/2，则有Fo×Fi执行时间=[n(n+1)/2]*[n(n+1)/2]，因此该算法的时间复杂度为：O(n4)。提纲试验分析问题提出论文思路相关算法试验(一)可以看出，在服务总数比较小的两种逻辑结构的构建时间几乎差不多，但随着服务总数的增多，WSIRG的构建时间明显小于WSG的时间,体现了新方法的优势。试验(二)基于WSG的服务发现方法和基于WSIRG的服务方法的服务发现时间的对比结果如图所示。可看出，基于WSIRG的服务发现响应时间相对较少，并随着服务总数越来越多，服务发现的速度相对越来越快，优势明显。结果分析从以上的实验结果可以看出，新方法存在以下优势：WSIRG与基于断言关系的WSG的构建方法相比，WSIRG优势比较明显，这主要是在WSIRG的顶点不是单个的Web服务，而是同类的Web服务集，在构造WSIRG时，先对给定的Web服务集进行分类划分为不同的顶点集，然后再构造成WSIRG，虽然，在理论上WSIRG的构造算法在最坏情况下的复杂度为O(n4)，但在实际情况中几乎不可能出现或是接近最坏情况，实验证明亦是如此，因此，对给定的Web服务集，其WSIRG的顶点数远少于WSG的顶点数，所以，在服务发现响应的时间上基于WSIRG的服务发现也占有很大的优势，随着服务数量越多，优势越明显。同时，也发现基于WSIRG的服务发现实验过程中，返回的结果比较多，包含的输入/输出消息等参数信息比较的明确，能很好的为服务组合提供数据参考。本文小结为了完成Web服务间自适应调