基于归约图的Web服务自动组合

Automatic Web Service Composition Based on Reduction Graph

针对给定的服务库及用户请求的一个输出对象,引入了归约图的概念,证明了完备归约图与输出对象的等价性,论证了裁剪规则、归约规则求解归约图的可行性,由此提出了一种基于归约图的Web服务自动组合方法。该方法根据给定的服务库,针对用户请求的每一个输出对象构造完备归约图,通过裁剪、归约,获取该输出对象的合成路径。将图的构造与搜索过程分开,图的构造过程中不会出现重复节点,归约过程利用了归约图两类节点间层出现的特点。与传统的图搜索算法相比,搜索空间小、算法简单,避免了循环搜索。仿真实验结果表明,该方法具有较好的时间复杂度。

In giving web service and an output object of user requestor,a reduction graph is inducted.The equivalence between complete reduction graph and output object is proved and the feasibility to search reduction graph through clipping rule and reduction rule is demonstrated.Therefore,an approach based on reduction graph to compose web service automatically is proposed.It creates a complete reduction graph for each output object of user requestor,and gets composition path by clipping and reduction.Compared with traditional graph-based methods,it separates graph-creation and graph-search,avoiding the repetition nodes during graph-creation.With the characteristics of two kinds of interlayer-appeared-nodes,the repetition search eliminated.Experimental results indicate that it has a good level of time complexity.