[1]傅朝阳,杨利娟,华泽,等.基于有向带环加权多图的线性服务组合[J].南京理工大学学报(自然科学版),2012,36(06):0.
 FU Zhao yang,YANG Li juan,HUA Ze,et al.Linear Composition of Service Based on Directed Cyclic Weighted Multigraph[J].Journal of Nanjing University of Science and Technology,2012,36(06):0.
点击复制

基于有向带环加权多图的线性服务组合
分享到:

《南京理工大学学报》(自然科学版)[ISSN:1005-9830/CN:32-1397/N]

卷:
36卷
期数:
2012年06期
页码:
0
栏目:
出版日期:
2012-12-31

文章信息/Info

Title:
Linear Composition of Service Based on Directed Cyclic Weighted Multigraph
作者:
傅朝阳 1杨利娟 1华泽 1高济 2
1.苏州科技学院 电子与信息工程学院,江苏 苏州 215011;2.浙江大学 计算机科学与技术学院,浙江 杭州 310027
Author(s):
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
关键词:
有向带环加权多图服务组合语义包容关系着色时间戳时间复杂度
Keywords:
directed cyclic weighted multigraphservice compositionsemantic subsumptioncoloringtiming stampcyclestime complexity
分类号:
TP311
摘要:
为提升自动服务组合效率,提出在新的服务图结构中实现线性服务组合。该方法使用有向带环加权多图描述服务关系。在深度与广度搜索相结合的组合路径查找过程中,基于语义包容关系将图中节点对之间的多边降级为单边。通过着色和时间戳判断、消除环。给出了具有线性时间复杂度的组合路径查找算法并对其时间复杂度予以理论证明。仿真结果表明:与同类方法相比,该方法能够在线性时间内,在不降低查全率的情况下,发现带环图中的组合路径,并具有查找时间与服务图规模无关的良好可扩展性。
Abstract:
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.

参考文献/References:

[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.

备注/Memo

备注/Memo:
收稿日期:2012-09-21修回日期:2012-11-26 基金项目:〖国家自然科学基金(60775029);国家“863”计划资助项目(2007AA01Z187);江苏省高校自然科学基金(10KJD510009);苏州科技学院项目(331111606;XKQ201205) 作者简介:傅朝阳(1977-),男,博士,讲师,主要研究方向:人工智能、网络计算、模型检测,Email:zhaoyangfu@gmail.com。
更新日期/Last Update: 2012-12-29