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

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

作　　者：傅朝阳[1] 杨利娟[1] 华泽[1] 高济[2] 

机构地区：[1]苏州科技学院电子与信息工程学院,江苏苏州215011 [2]浙江大学计算机科学与技术学院,浙江杭州310027

出　　处：《南京理工大学学报》2012年第6期919-925,共7页Journal of Nanjing University of Science and Technology

基　　金：国家自然科学基金(60775029);国家'863'计划资助项目(2007AA01Z187);江苏省高校自然科学基金(10KJD510009);苏州科技学院项目(331111606;XKQ201205)

摘　　要：为提升自动服务组合效率,提出在新的服务图结构中实现线性服务组合。该方法使用有向带环加权多图描述服务关系。在深度与广度搜索相结合的组合路径查找过程中,基于语义包容关系将图中节点对之间的多边降级为单边。通过着色和时间戳判断、消除环。给出了具有线性时间复杂度的组合路径查找算法并对其时间复杂度予以理论证明。仿真结果表明:与同类方法相比,该方法能够在线性时间内,在不降低查全率的情况下,发现带环图中的组合路径,并具有查找时间与服务图规模无关的良好可扩展性。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 demon- strated. 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.

关 键 词：有向带环加权多图 服务组合 语义包容关系 着色 时间戳 环 时间复杂度 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]