1、一种Web服务关联图的构造方法,覃事刚1,刘建勋2,秦祖泽1,1.湖南电气职业技术学院汽车工程系1, 湖南 湘潭 411101;2.湖南科技大学 知识处理与网络化制造湖南省普通高等学校重点实验室2,湖南 湘潭 411201,提纲,问题提出,问题提出,很多Web服务之间存在联系,问题提出,互联网上的Web服务,Web Services Implicit Relationship Graph, WSIRG,挑战,如何搜集互联网上的Web服务,如何挖掘出这些Web服务中存在的调用关系,(本论文解决的主要问题),提纲,论文思路,一个Web服务是一个三元组ws(N,Im,Om),其中N是服务名,Im是该
2、服务的所有操作(Operation)的输入消息(input message)集合 imsg1,imsg2,imsgm ,Om是所有操作的输出消息(output message)集合 omsg1, omsg2,omsgm 。,给定一个Web服务集U。其中W表示服务名称的集合ws1,ws2,ws3,ws4, ws5,M表示W中的所有Web服务对应的消息的集合m1,m2,m3,m4,m5,为W中元素与M 中元素的对应关系,若存在且 r=1,则m是ws的输入消息;若存在边且r=-1,则m是ws输出(返回)消息;若不存在边且r=0,则m不是ws的消息(message)。,论文思路,给定一个Web服务集U
3、=ws1,ws2,ws3,ws4,ws5,该集合U对应的消息集合MSGset= inMSGset outMSGset =m1,m2,m3,m4,m5,其Web服务与消息之间的分配关系如图所示,这样做具有下优点: i) 可以建立Web服务集与输入/输出消息集之间的二元关系, 用以揭示Web服务间的潜在调用关系; ii) 可以可视化的方式直观的表达这种调用关系。,将给定的Web服务集U=分解为两个二元组:Ui=和Uo=。其中, Ui表示Web服务集与输入消息之间的二元关系, Uo表示Web服务集与输出消息之间的二元关系;,提纲,相关算法子项集F构造算法及分析,子项:iP1(m1,m2,m3,ws4
4、),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),在给定Web服务与消息二元关系上的子项集F的构建,P1 P2 (公式9)=( A1, B1) (A2, B2)=( A1 A2, B1 B2)=P3 (A3, B3) (服务集扩展运算,其中 P3 U 且满足f(A3)=B3) P1P2 (公式10)=( A1, B1) (A2, B2)=( A1, A2, B1 B2)= P3 (A3
5、, 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集合中,有且只
6、有|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的构造算法及分析,在这个算法中,函数执行时间由三部分组成:构造输入子项集时间、构造输出子项集时间和 FoFi所用时间。构造输入/输出子项集时间已经知道均为O(n2),而FoFi执行时间取决于|Fi|和|Fo|,在最坏的情况下,有|Fo|=| W*|和|Fi|=| W*|,假设
7、| W |=n,| W*|=n(n+1)/2,则有FoFi执行时间= n(n+1)/2* n(n+1)/2,因此该算法的时间复杂度为:O(n4)。,提纲,试验 (一),可以看出, 在服务总数比较小的两种逻辑结构的构建时间几乎差不多,但随着服务总数的增多,WSIRG的构建时间明显小于WSG的时间,体现了新方法的优势。,试验(二),基于WSG的服务发现方法和基于WSIRG的服务方法的服务发现时间的对比结果如图所示。可看出, 基于WSIRG的服务发现响应时间相对较少,并随着服务总数越来越多,服务发现的速度相对越来越快,优势明显。,结果分析,从以上的实验结果可以看出,新方法存在以下优势:WSIRG与基
8、于断言关系的WSG的构建方法相比,WSIRG优势比较明显,这主要是在WSIRG的顶点不是单个的Web服务,而是同类的Web服务集,在构造WSIRG时,先对给定的Web服务集进行分类划分为不同的顶点集,然后再构造成WSIRG,虽然,在理论上WSIRG的构造算法在最坏情况下的复杂度为O(n4),但在实际情况中几乎不可能出现或是接近最坏情况,实验证明亦是如此,因此,对给定的Web服务集,其WSIRG的顶点数远少于WSG的顶点数,所以,在服务发现响应的时间上基于WSIRG的服务发现也占有很大的优势,随着服务数量越多,优势越明显。同时,也发现基于WSIRG的服务发现实验过程中,返回的结果比较多,包含的输
9、入/输出消息等参数信息比较的明确,能很好的为服务组合提供数据参考。,本文小结,为了完成Web服务间自适应调用关联的问题,从服务间的逻辑调用关系出发,提出一种Web服务隐式逻辑关联图的构造方法。在该方法中,Web服务被简化为三元组,给定的Web服务集对应的三元关系集可分解为两个简单的二元关系:输出子项集和输入子项集,服务链是输出子项集和输入子项集连接运算的结果,构成Web服务关联图的边。本文并给出了子项集的构造算法和Web服务关联图的构造算法,并进行了相关实验。,实验结果证明WSIRG构造方法是可行的,并且,在WSIRG中进行服务发现,有利于提高服务发现效率。,谢 谢!,欢迎各位专家批评指正!,