Future Generation Computer Systems 28 (2012) 1080–1089
Contents lists available at SciVerse ScienceDirect
Future Generation Computer Systems
journal homepage: www.elsevier.com/locate/fgcs
A quality of service (QoS)-aware execution plan selection approach for a service
composition process
Min Liu
a,∗
, Mingrui Wang
a
, Weiming Shen
a,b
, Nan Luo
a
, Junwei Yan
a
a
The Key Laboratory of Embedded System and Service Computing (Ministry of Education), School of Electronic and Information Engineering, Tongji University,
Shanghai 201804, China
b
National Research Council Canada, London, Ontario, N6G 4X8 Canada
a r t i c l e i n f o
Article history:
Received 1 November 2010
Received in revised form
12 April 2011
Accepted 11 August 2011
Available online 10 November 2011
Keywords:
QoS
Service composition
Flexible constraint
Web services
a b s t r a c t
The quality of service (QoS)-aware service composition (QSC) problem is to find an execution plan of a
service composition process which can ensure that the quality of service meets given user requirements.
This paper proposes a branch and bound for execution plan selection (BB4EPS) algorithm to solve the QSC
problem. In the proposed BB4EPS algorithm, a universal QoS model is used to evaluate the QoS parameters
for service composition, and the QSC problem is modeled as an extended flexible constraint satisfaction
framework, in which the utility function is applied to build the objective function. Numerical simulation
results show that the proposed algorithm is feasible and effective.
Crown Copyright © 2011 Published by Elsevier B.V. All rights reserved.
1. Introduction
The service-oriented computing paradigm and its realization
through web service technologies provide a promising solution
for the seamless integration of enterprise applications to create
new value-added services [1]. Industrial practice witnesses a
growing interest in the service composition for supply chains,
dynamic alliances, e-businesses, extended enterprises, and virtual
organizations [2–5]. However, with the wide deployment of web
services on the Internet, many service providers register a large
number of service components with similar or identical functions,
which have different levels of quality of service (QoS). QoS is a
set of non-functional parameters of a service, such as service time,
service price, success rate, reliability, and security.
QoS plays an important role in the dynamical selection and
composition process of services, and it also affects the evaluation
and optimization of composite services. When the functional
requirements of services are met, more attention can be paid
to non-functional QoS parameters. For an available composite
service generated automatically by a user’s target and verified by
composition algebra, it is necessary to choose a service satisfying
the user’s QoS requirements from a group of feasible services with
the same function.
∗
Corresponding author.
E-mail address: lmin@tongji.edu.cn (M. Liu).
QoS has always been a very hot research topic in the field
of computer networks and real-time computing [5–8]. With
the development of web service technologies, QoS became an
important factor of successful web service applications in various
domains. Therefore, how to provide web services and composition
services with QoS guarantees is attracting more attention in both
academia and industry.
In this paper, we propose a branch and bound for execution
plan selection (BB4EPS) algorithm for the QoS-aware service
composition problem. QoS awareness means that the selected
service must maximize the QoS performance of the composition
service while satisfying user preferences and constraints. The
QoS-aware service composition (QSC) problem is to look for an
execution plan of composition process which can ensure that the
quality of service composition meets given user requirements. In
this paper, the QSC problem is modeled as an extended flexible
constraint satisfaction framework and the objective function is
designed using utility theory. The proposed BB4EPS algorithm is
used to address the service execution plan selection problem.
The rest paper is organized as follows. Section 2 reviews
related work; Section 3 defines a universal QoS model and a QoS
computation method of composition service; Section 4 describes
a flexible constraint satisfaction-based formal method for service
composition; Section 5 proposes a heuristic algorithm to solve
the global QoS optimization; Section 6 presents analysis and
simulation results; Section 7 provides some conclusions.
0167-739X/$ – see front matter Crown Copyright © 2011 Published by Elsevier B.V. All rights reserved.
doi:10.1016/j.future.2011.08.017