|Table of Contents|

Linear Composition of Service Based on Directed Cyclic Weighted Multigraph


Research Field:
Publishing date:


Linear Composition of Service Based on Directed Cyclic Weighted Multigraph
FU Zhaoyang1YANG Lijuan1HUA Ze1GAO Ji2
1.College of Electronic and Information Engineering,Suzhou University of Science and Technology,Suzhou 215011,China; 2.College of Computer Science and Technology,Zhejiang University,Hangzhou 310027,China
directed cyclic weighted multigraphservice compositionsemantic subsumptioncoloringtiming stampcyclestime complexity
To promote the efficiency of automatic service composition,a linear service composition realization is proposed in a new service graph structure.The service relationship is modeled as a directed cyclic weighted multigraph.In the searching process of composition paths combining depthfirst traveling and breadthfirst traveling,the multiedges of node pairs are degraded to uniedges based on semantic subsumption.Cycles are discovered and eliminated via both coloring and timing stamp.A composition path searching algorithm with linear time complexity is presented and theoretically demonstrated.The simulation results prove:compared with other similar methods,this method can find combination paths in cyclic graphs with linear time complexity without loss of the ratio of recall,and has good expansibility that the searching time is independent with scales of servicing graphs.


[1]徐猛,崔立真,李庆忠.基于扩展图规划的TopK服务组合方法研究[J].电子学报,2012,40(7):1404-140 Xu Meng,Cui Lizhen,Li Qingzhong.An extended graphplanning based TopK service composition method[J].Chinese Journal of Electronics,2012,40(7):1404-1409.
[2]Lin S Y,Lin Guanting,Chao Kuoming,et al.A costeffective planning graph approach for largescale web service composition[J].Mathematical Problems in Engineering,2012:1024-123X.
[3]付鹏斌,李利波,杨惠荣.基于图规划的语义Web服务自动组合方法[J].计算机应用研究,2011,28(12):4597-4603. Fu Pengbin,Li Libo,Yang Huirong.Automatic composition of semantic Web services based on planning graph[J].Application Research of Computers,2011,28(12):4597-4603.
[4]卢锦运,张为群.一种基于与或图的语义Web服务自动组合方法研究[J].计算机科学,2010,37(3):188-190. Lu Jinyun,Zhang Weiqun.Method of automatic semantic Web services composition based on AND/OR graph[J].Computer Science,2010,37(3):188-190.
[5]Talantikite H N,Aissani D,Boudjlidac N.Semantic annotations for Web services discovery and composition[J].Computer Standards Interfaces,2009,31(6):1108-1117.
[6]张佩云,黄波,孙亚民.基于语义与模板的Web服务混合合成[J].南京理工大学学报,2008,32(4):425-428. Zhang Peiyun,Huang Bo,Sun Yamin.Web services hybrid composition based on semantics and template[J].Journal of Nanjing University of Science and Technology,32(4):425-428.
[7]Omer A M,Schill A.Dependency based automatic service composition using directed graph[A].International Conference on Next Generation Web Services Practices[C].Prague,Czech Republic:IEEE Computer Society,2009:76-81.
[8]傅朝阳,高济,郭航,等.基于散列的语义服务匹配算法[J].南京理工大学学报,2010,34(4):473-481. Fu Zhaoyang,Gao Ji,Guo Hang,et al.Hashingbased semantic service matchmaking[J].Journal of Nanjing University of Science and Technology,2010,34(4):473-481.
[9]Cormen T H,Leiserson C E,Rivest R L,et al.Introduction to algorithms[M].Cambridge,MA:MIT Press,2001:245-247,225-228.
[10]Yan Y,Poizat P,Zhao L.Selfadaptive service composition through graphplan repair[A].IEEE International Conference on Web Services[C].Washington DC,USA:IEEE Computer Society,2010:624-627. 
[11]Georgetown University.SCA[OB/OL].http://ws-〖JP3〗challenge.georgetown.edu/ws-challenge/WSChallenge.htm,2012-08-25. 
[12]Georgetown University.WSC 2010 Testset Generator[EB/OL].http://ws-challenge.georgetown.edu/wsc10//technical_details.html,2012-08-20.
[13]Zheng X,Yan Y.An efficient syntactic Web service composition algorithm based on the planning graph model[A].Proceedings of the 2008 IEEE International Conference on Web Services[C].Beijing:IEEE Computer Society,2008:691-699.
[14]SwscWIKI.Semantic Web service challenge:Evaluating semantic Web services mediation,choreography and discovery[OB/OL].http://sws-challenge.org/,2012-07-16.
[15]李曼,王大治,杜小勇,等.基于领域本体的Web服务动态组合[J].计算机学报,2005,28(4):644-650. Li Man,Wang Dazhi,Du Xiaoyong,et al.Dynamic composition of Web services based on domain ontology[J].Chinese Journal of Computers,2005,28(4):644-650.


Last Update: 2012-12-29