QoS-Aware Automatic Service Composition: A Graph View

doi:10.1007/s11390-011-0183-2

	QoS-Aware Automatic Service Composition: A Graph View
	Jiang, Wei 1,2; Wu, Tian 3; Hu, Song-Lin 1; Liu, Zhi-Yong 1
	2011-09-01
发表期刊	JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY
ISSN	1000-9000
卷号	26 期号:5 页码:837-853
摘要	In the research of service composition, it demands efficient algorithms that not only retrieve correct service compositions automatically from thousands of services but also satisfy the quality requirements of different service users. However, most approaches treat these two aspects as two separate problems, automatic service composition and service selection. Although the latest researches realize the restriction of this separate view and some specific methods are proposed, they still suffer from serious limitations in scalability and accuracy when addressing both requirements simultaneously. In order to cope with these limitations and efficiently solve the combined problem which is known as QoS-aware or QoS-driven automatic service composition problem, we propose a new graph search problem, single-source optimal directed acyclic graphs (DAGs), for the first time. This novel single-source optimal DAGs (SSOD) problem is similar to, but more general than the classical single-source shortest paths (SSSP) problem. In this paper, a new graph model of SSOD problem is proposed and a Sim-Dijkstra algorithm is presented to address the SSOD problem with the time complexity of O(n log n m) (n and m are the number of nodes and edges in the graph respectively), and the proofs of its soundness. It is also directly applied to solve the QoS-aware automatic service composition problem, and a service composition tool named QSynth is implemented. Evaluations show that Sim-Dijkstra algorithm achieves superior scalability and efficiency with respect to a large variety of composition scenarios, even more efficient than our worklist algorithm that won the performance championship of Web Services Challenge 2009.
关键词	Web service automatic service composition QoS-aware single-source optimal DAGs
DOI	10.1007/s11390-011-0183-2
收录类别	SCI
语种	英语
资助项目	National Basic Research 973 Program of China[2007CB-310805] ; National Natural Science Foundation of China[61070027] ; Beijing Natural Science Foundation[4092043] ; State Grid Information & Telecommunication Company Ltd.[SGIT[2010]449] ; Planned Science and Technology Project of Guangdong Province, China[2010B050100009]
WOS研究方向	Computer Science
WOS类目	Computer Science, Hardware & Architecture ; Computer Science, Software Engineering
WOS记录号	WOS:000297212300010
出版者	SCIENCE PRESS
引用统计	被引频次：18[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/13143
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Hu, Song-Lin
作者单位	1.Chinese Acad Sci, Inst Comp Technol, Beijing 100190, Peoples R China 2.Chinese Acad Sci, Grad Univ, Beijing 100190, Peoples R China 3.State Grid Informat & Telecommun Co Ltd, Beijing 100190, Peoples R China
推荐引用方式 GB/T 7714	Jiang, Wei,Wu, Tian,Hu, Song-Lin,et al. QoS-Aware Automatic Service Composition: A Graph View[J]. JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY,2011,26(5):837-853.
APA	Jiang, Wei,Wu, Tian,Hu, Song-Lin,&Liu, Zhi-Yong.(2011).QoS-Aware Automatic Service Composition: A Graph View.JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY,26(5),837-853.
MLA	Jiang, Wei,et al."QoS-Aware Automatic Service Composition: A Graph View".JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY 26.5(2011):837-853.