For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
FAQS: Fast Web Service Composition Algorithm Based on QoS-Aware Sampling
Wei LU Weidong WANG Ergude BAO Liqiang WANG Weiwei XING Yue CHEN
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2016/04/01
Online ISSN: 1745-1337
Type of Manuscript: PAPER
Category: Mathematical Systems Science
web service composition, quality of service, sampled services, near-optimal composition,
Full Text: PDF(2.6MB)>>
Web Service Composition (WSC) has been well recognized as a convenient and flexible way of service sharing and integration in service-oriented application fields. WSC aims at selecting and composing a set of initial services with respect to the Quality of Service (QoS) values of their attributes (e.g., price), in order to complete a complex task and meet user requirements. A major research challenge of the QoS-aware WSC problem is to select a proper set of services to maximize the QoS of the composite service meeting several QoS constraints upon various attributes, e.g. total price or runtime. In this article, a fast algorithm based on QoS-aware sampling (FAQS) is proposed, which can efficiently find the near-optimal composition result from sampled services. FAQS consists of five steps as follows. 1) QoS normalization is performed to unify different metrics for QoS attributes. 2) The normalized services are sampled and categorized by guaranteeing similar number of services in each class. 3) The frequencies of the sampled services are calculated to guarantee the composed services are the most frequent ones. This process ensures that the sampled services cover as many as possible initial services. 4) The sampled services are composed by solving a linear programming problem. 5) The initial composition results are further optimized by solving a modified multi-choice multi-dimensional knapsack problem (MMKP). Experimental results indicate that FAQS is much faster than existing algorithms and could obtain stable near-optimal result.