基于分布式工作流的时间管理模型信息系统与工程研究所课件.ppt

1、覃事刚，刘建勋，秦祖泽覃事刚覃事刚 湘潭大学湘潭大学Web服务关联语义索引的构建理论与实现方法的研究服务关联语义索引的构建理论与实现方法的研究提纲提纲本文结论本文结论问题提出问题提出论文思路论文思路相关算法相关算法覃事刚覃事刚 湘潭大学湘潭大学Web服务关联语义索引的构建理论与实现方法的研究服务关联语义索引的构建理论与实现方法的研究问题提出问题提出覃事刚覃事刚 湘潭大学湘潭大学Web服务关联语义索引的构建理论与实现方法的研究服务关联语义索引的构建理论与实现方法的研究问题提出问题提出n很多服务之间存在联系 买入卖出BCABCWeb Service1Web Service2覃事刚覃事刚 湘潭大学湘

2、潭大学Web服务关联语义索引的构建理论与实现方法的研究服务关联语义索引的构建理论与实现方法的研究问题提出问题提出A4A1A1A4A1A4A1A2A1A1A1A1B3A1A4A1A1A4A1A4A1A2A1A1A1A1B3A1B3A1A2A1B3A1A4A1A2A1B3A1A4A1A2A1B3A1A1B3A1A4A1A2A1B3A1A4A2A1B3A1A4A1A2B3A1A1B3A1A4A1A2A1B3A1A4A1A2A1B3A1A4A1A2A1B3A1A4A1A2A1A1A4A1A1A4A1A2B3A1A4A1A2A1B3A1A4A1A2A1B3A1A4A1A2B3A1A4A1A2A1B3A1

3、A4A1A2A1B3A1A4A1A2A1A4A4A1A4A1A1A4A1A2B3A1A4A1A2A1B3A1A4A1A2B3A1A4A1A2A1A4A1A4A1A1A4A1A2A1A1A4A1A2A1A1A4A1B3A1A1A1B3A1A4A1A2A1B3A1A4A1A2A1A1A2A1A4A2A4A2A2A1A1B3A1A4A1A2A1B3A1A2A1B3A1A4A1A2A1B3A1A4A1A2A1B3A1A1B3A1A4A1A2A1B3A1A4A2A1B3A1A4A1A2B3A1A1B3A1A4A1A2A1B3A1A4A1A2A1B3A1A4A1A2A1B3A1A4A1A2A1A1A4A1

4、A1A4A1A2B3A1A4A1A2A1B3A1A4A1A2A1B3A1A4A1A2B3A1A4A1A2A1B3A1A4A1A2A1B3A1A4A1A2A1A4A4A1A4A1A1A4A1A2B3A1A4A1A2A1B3A1A4A1A2B3A1A4A1A2A1A4A1A4A1A1A4A1A2A1A1A4A1A2A1A1A4A1B3A1A1A1B3A1A4A1A2A1B3A1A4A1A2A1A1A2A1A4A2A4A2A2A1A1B3A1A4A1A2A1A1A2A4C1A3n互联网上的服务 ,覃事刚覃事刚 湘潭大学湘潭大学Web服务关联语义索引的构建理论与实现方法的研究服务关联语义索引的构建理论

5、与实现方法的研究挑战挑战n如何搜集互联网上的服务n如何挖掘出这些服务中存在的调用关系(本论文解决的主要问题本论文解决的主要问题)覃事刚覃事刚 湘潭大学湘潭大学Web服务关联语义索引的构建理论与实现方法的研究服务关联语义索引的构建理论与实现方法的研究提纲提纲本文结论本文结论问题提出问题提出论文思路论文思路相关算法相关算法覃事刚覃事刚 湘潭大学湘潭大学Web服务关联语义索引的构建理论与实现方法的研究服务关联语义索引的构建理论与实现方法的研究论文思路论文思路一个一个Web服务是一个三元组服务是一个三元组ws(N,Im,Om)，其中，其中N是服务名，是服务名，Im是该服务是该服务的所有操作（的所有操作

6、（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的输入消息；若存

7、在边的输入消息；若存在边且且r=-1，则，则m是是ws输出（返回）消息；若不存在边输出（返回）消息；若不存在边且且r=0，则，则m不是不是ws的消息（的消息（message）。）。覃事刚覃事刚 湘潭大学湘潭大学Web服务关联语义索引的构建理论与实现方法的研究服务关联语义索引的构建理论与实现方法的研究论文思路论文思路n给定一个服务集，该集合对应的消息集合 ，其服务与消息之间的分配关系如图所示这样做具有下优点：这样做具有下优点：)可以建立服务集与输入输出消息集之可以建立服务集与输入输出消息集之间的二元关系间的二元关系,用以揭示服务间的潜在调用用以揭示服务间的潜在调用关系；关系；)可以可视化的方式直

8、观的表达这种调可以可视化的方式直观的表达这种调用关系。用关系。iF（W，M，i）oF（W，M，o）iP(ws3,ws4,m1,m3)oP(ws2,m1,m2,m3)AiPBiPBPoAPoiPPo.,.,.|1|1)(FonFimmniPPoFiFoGwsGwsn将给定的服务集分解为两个二元组：和。其中,表示服务集与输入消息之间的二元关系，表示服务集与输出消息之间的二元关系；覃事刚覃事刚 湘潭大学湘潭大学Web服务关联语义索引的构建理论与实现方法的研究服务关联语义索引的构建理论与实现方法的研究提纲提纲本文结论本文结论问题提出问题提出论文思路论文思路相关算法相关算法覃事刚覃事刚 湘潭大学湘潭大学

9、Web服务关联语义索引的构建理论与实现方法的研究服务关联语义索引的构建理论与实现方法的研究相关算法相关算法子项集构造算法及分析子项集构造算法及分析子项子项:(,)，(,)，(,)，(,)，(,)，(,)，(,)，(,)ws1ws3ws4m3ws4m1m2m3ws5m2m4ws1ws3ws4m3ws5ws2ws4m2ws3ws4m1m3ws2ws4m1m2ws2ws3ws4m1n 在给定服务与消息二元关系上的子项集的构在给定服务与消息二元关系上的子项集的构建建 （公式）（公式）(,)(,)(,)(,)(服务集扩展运算，其中服务集扩展运算，其中 且满足且满足()（公式）（公式）(,)(,)(,)(

10、,)(消息集扩展运算，其中消息集扩展运算，其中 且满足且满足()覃事刚覃事刚 湘潭大学湘潭大学Web服务关联语义索引的构建理论与实现方法的研究服务关联语义索引的构建理论与实现方法的研究相关算法相关算法子项集构造算法及分析子项集构造算法及分析n其基本思想是：在已存在的分组集合中，对所有的分组两两做服务对象集扩展运算或是消息集扩展运算，生成新的分组并添加到分组集合续继参与相应的扩展运算，直到所有分组均满足()的条件时结束。其中，初始分组集(),(),()。覃事刚覃事刚 湘潭大学湘潭大学Web服务关联语义索引的构建理论与实现方法的研究服务关联语义索引的构建理论与实现方法的研究相关算法相关算法子项集构

11、造算法及分析子项集构造算法及分析?在如图所示的函数中，初始集合中的元素个数在如图所示的函数中，初始集合中的元素个数，对任意一子项，对任意一子项()，满足，满足，,即任意的两个，即任意的两个，其相对应集合中，有且只有个消息元素其相对应集合中，有且只有个消息元素 相同，此时该算法的时间复杂度处于最坏情况。相同，此时该算法的时间复杂度处于最坏情况。那么，把某个那么，把某个()且扩展成且扩展成()且且需要执行需要执行()时间，依次对每个进行扩展的总的执行的时间为时间，依次对每个进行扩展的总的执行的时间为()时间，因此该算法的时间复杂度为：时间，因此该算法的时间复杂度为：()()。覃事刚覃事刚 湘潭大学

12、湘潭大学Web服务关联语义索引的构建理论与实现方法的研究服务关联语义索引的构建理论与实现方法的研究相关算法相关算法的构造算法及分析的构造算法及分析 在这个算法中，函数在这个算法中，函数执行时间由三部分组成执行时间由三部分组成：构造输入子项集时间：构造输入子项集时间、构造输出子项集时间、构造输出子项集时间和和 所用时间。构造输所用时间。构造输入输出子项集时间已经入输出子项集时间已经知道均为知道均为()，而，而执行执行时间取决于和，在最坏时间取决于和，在最坏的情况下，有的情况下，有*和和*，假设假设 ，*()，则有，则有执执行时间行时间()*()，因此，因此该算法的时间复杂度为该算法的时间复杂度为

13、：()。覃事刚覃事刚 湘潭大学湘潭大学Web服务关联语义索引的构建理论与实现方法的研究服务关联语义索引的构建理论与实现方法的研究提纲提纲试验分析试验分析问题提出问题提出论文思路论文思路相关算法相关算法覃事刚覃事刚 湘潭大学湘潭大学Web服务关联语义索引的构建理论与实现方法的研究服务关联语义索引的构建理论与实现方法的研究试验试验(一一)n可以看出，在服务总数比较小的两种逻辑结构的构建时间几乎差不多，但随着服务总数的增多，的构建时间明显小于的时间,体现了新方法的优势。覃事刚覃事刚 湘潭大学湘潭大学Web服务关联语义索引的构建理论与实现方法的研究服务关联语义索引的构建理论与实现方法的研究试验试验(二

14、二)n基于的服务发现方法和基于的服务方法的服务发现时间的对比结果如图所示。可看出，基于的服务发现响应时间相对较少，并随着服务总数越来越多，服务发现的速度相对越来越快，优势明显。覃事刚覃事刚 湘潭大学湘潭大学Web服务关联语义索引的构建理论与实现方法的研究服务关联语义索引的构建理论与实现方法的研究结果分析结果分析n从以上的实验结果可以看出，新方法存在以下优势：与基于断言关系的的构建方法相比，优势比较明显，这主要是在的顶点不是单个的服务，而是同类的服务集，在构造时，先对给定的服务集进行分类划分为不同的顶点集，然后再构造成，虽然，在理论上的构造算法在最坏情况下的复杂度为()，但在实际情况中几乎不可能

15、出现或是接近最坏情况，实验证明亦是如此，因此，对给定的服务集，其的顶点数远少于的顶点数，所以，在服务发现响应的时间上基于的服务发现也占有很大的优势，随着服务数量越多，优势越明显。同时，也发现基于的服务发现实验过程中，返回的结果比较多，包含的输入输出消息等参数信息比较的明确，能很好的为服务组合提供数据参考。覃事刚覃事刚 湘潭大学湘潭大学Web服务关联语义索引的构建理论与实现方法的研究服务关联语义索引的构建理论与实现方法的研究本文小结本文小结n为了完成服务间自适应调用关联的问题，从服务间的逻辑调用关系出发，提出一种服务隐式逻辑关联图的构造方法。在该方法中，服务被简化为三元组，给定的服务集对应的三元关系集可分解为两个简单的二元关系：输出子项集和输入子项集，服务链是输出子项集和输入子项集连接运算的结果，构成服务关联图的边。本文并给出了子项集的构造算法和服务关联图的构造算法，并进行了相关实验。n实验结果证明构造方法是可行的，并且，在中进行服务发现，有利于提高服务发现效率。覃事刚覃事刚 湘潭大学湘潭大学Web服务关联语义索引的构建理论与实现方法的研究服务关联语义索引的构建理论与实现方法的研究谢谢 谢！谢！欢迎各位专家批评指正！欢迎各位专家批评指正！