Abstract: The Web service composition system with static configuration can not adapt to the failure-prone environment and the variable Quality-of-Service (QoS) of component services. Therefore, a dynamic configuration method of Web service composition, Service Selection Constraint Model, is presented in this study. The candidate component services with same functionality are organized as a service class. The functional dependency relationships between component services are reflected as the service selection constraints. The optimal configurations conforming to multi-objective QoS constraints, known as the Pareto optimal solutions, are searched by a special ant colony optimization algorithm for Web service (ACO4WS). The feasibility and soundness of the method are proved by simulation experiments and corresponding analysis. By using the presented method, not only the QoS of service composition system is greatly improved, but also the multiple functional and non-functional constraints are satisfied.
INTRODUCTION
The Web service composition provides a mechanism to construct a new value-added service via the integration and interaction of the existing component services. In contrast with the traditional component systems, in Web service composition, there probably exist a lot of candidate component services, which provide the same functionality but differ in QoS attributes. The service composition becomes a decision problem on which component services should be selected such that the user’s functional and non-functional requirements can be satisfied. In the Internet-based environment, the QoS of composite service is fluctuating due to the quality of the component services are subject to change with the variation of workload or communication delay (Chafle et al., 2007). In error-prone environment, most services are third party services whose QoS is not guaranteed. The malfunction of component service can disable a composite service. Therefore, the Web service composition system must have the ability of dynamic reconfiguration in order to adapt to the dynamic change of run-time environment (Yen et al., 2008).
In this study, in order to satisfy the requirements of self-adaptive Web service composition and automatic management, a method of service selection constraint for Web service composition is presented. Each abstract activity of service composition is respectively associated to a corresponding service class. Each service class is comprised of the concrete candidate component services with same functionality. The functional dependency relationships between component services are reflected as the service selection constraints between service classes. Finally, a special ant colony optimization algorithm for Web service (ACO4WS) is designed and applied to detect the optimal configurations which satisfy the service selection constraints and multi-objective QoS requirements.
RELATED WORKS
Although the problem of Web service composition optimization has been extensively researched in the past few years, most works regard each service selection as an independent process. However, in actual applications, there often exist dependent relationships between component services. Xiong et al. (2008) presented a functional dependency configuration net to reflect the functional dependency relationships (Xiong et al.,2008). An optimal configuration can be dynamically got under the precondition that the functional dependency relationships are satisfied. Unfortunately, their research is only suitable for mono-objective QoS optimization. Gooneratne et al. (2007) classified the QoS constraints as local and global constraints. The former restricts the values of a particular attribute of a single service, whereas the latter simultaneously restricts the values of two or more attributes of multiple candidate services. A global constraint is strictly dependent if the values of restricted QoS attributes can be uniquely determined once a value is assigned to one of them. A composite service which conforms to strictly dependent global constraints can be easily optimized in polynomial time (Gooneratne et al., 2007; Fang et al., 2009). Associate Petri net (APN) (Fang et al., 2009) and extended color Petri net (eCPN) (Liu et al., 2009a) are used to describe the independent global constraints. Genetic algorithm is applied to search an optimal service composition (Liu et al., 2009a; Fang et al., 2009). The solutions presented in these works still remain some obvious flaws. First, the optimization processes are often dependent on some simplified QoS evaluation functions. These functions are too rough to well evaluate whether the user’s QoS requirements are satisfied or not. Second, the functional dependency relationships are hard to be reflected according to above mentioned works. Because the connection relationships between component services are determined by the flow structure of service composition and because the flow constraints are not enough considered in these works, it is difficult to make certain that between which component services there exist functional dependency relationships.
Many meta-heuristic algorithms, such as genetic algorithm (Fang et al., 2009), particle swarm optimization (Liu et al., 2008) and simulated annealing (Liu et al., 2009b), have been applied to accelerate the detection of the optimal service composition. These approaches exhibit the same flaws, i.e., the weak modeling of service constraints and the rough algorithm implementation. The important problem of service selection conflict (Huang et al., 2009) is not solved in these algorithms. Because the meta-heuristic algorithms are only some algorithm frameworks, they often need some modifications to adapt to the special problems. In the above mentioned works, it is not clear what algorithm modifications have been done to adapt to the web service composition optimization. The performance of these algorithms also needs to be improved.
THE SERVICE SELECTION CONSTRAINT MODEL
The service selection constraint model is used to reflect the service selection constraints between component services. We organize the services with same functionality as a service class. The service selection of a service class is often dependent on the service selection of its previous service class. These related concrete services should be selected as a whole in this situation.
Definition 1: The service class: A service class is a service set which is comprised of a number of candidate component services with same functionality.
Definition 2: The service connection: Let C1 and C2 represent two service classes which are related to service transition tq1 and tq2 respectively. If there is a path from tq1 to tq2 and if there are no other service transitions in this path, then there is a service connection C1 → C2, which means that C1 and C2are adjacent and C1 is a previous service class of C2.
Definition 3: The service selection constraint model of composite service: A service selection constraint model of composite service is a tuple (S, C, Rc, RS), where:
| • | S is a set of component services. C is a set of service classes |
| • |
| • | Rc⊂CxC is a set of service connections. If <C1, C2>∈Rc, then there is a service connection C1 → C2 |
| • | Rs⊂SxS is a set of functional dependency relationships of component services |
| • | If<s1,s2>∈Rs, then ∃Ci,. Cj, εC, siεCi, s2εCj, Ci≠Cj, <Ci, Cj>εRc. Two component services with functional dependency relationship respectively belong to two different service classes with service connection |
| • | To ∀ C1, C2 ∈ C, if C1 → C2, then ∀s1 ∈ C1, |{<s1, s>| s∈C2}|$1 and ∀s2∈C2, |{<s, S2>|s∈C1}| ≥1. To any component service, there exist at least one pre-service and one post-service which have functional dependency relationships with this component service |
The service selection constraint model is illustrated in Fig. 1b. It is a directed acyclic graph (DAG). In Fig. 1a, the process model is used to reflect the flow constraints of composite service and it can be regarded as a composition plan which is comprised of some abstract services. In the process model of composite service, the system states and the execution conditions are represented by places. The logical control activities are represented by dummy transitions. The activities of component services are represented by service transitions. The task of composite service is represented by token. Every service transition is associated with multiple QoS attributes. The flow constraints are compactly reflected by the process model. A process model of composite service can be transformed to a DAG.
| Fig. 1: | The illustration of the service selection constraint model. (a) The process model and (b) the service selection constraint model |
In the DAG, the set of vertexes is C and the set of directed edges is Rc. There are two kinds of constraints between service classes, mono-constraint and multi-constraint. For example, C2 is only constrained by C2 while C9 are simultaneously constrained byC3, C4 and C8. A service connection includes many service functional dependency relationships. The problem of composite service is how to select a suitable component service from each service class under the precondition that functional dependency relationships and multi-objective QoS constraints are satisfied simultaneously.
ACO4WS
Ant Colony Optimization (ACO) (Dorigo and Caro, 1999) has exhibited its effectiveness to solve several different NP-hard combinatorial optimization problems, such as traveling salesman problem (TSP) (Dorigo and Gambardella, 1997). In ACO, the optimization problems are often modeled by a construction graph. The artificial ants lay pheromone on edges and/or vertices when they walk randomly on the graph. The probability to select a path is determined by the pheromone which has been laid on the path by the ant colony. The pheromones decrease progressively via., evaporation. The optimal solutions are detected through pheromone-based indirect communications between artificial ants. In this study, a special ant colony optimization algorithm ACO4WS is designed to achieve service composition optimization under multiple functional and non-functional constraints. We suppose the readers have the basic concepts of ACO. The characteristics of ACO4WS are presented as:
The multi-objective programming of service composition: The selection of optimal service configuration can be described as a multi-objective programming (MOP):
| (1) |
| (2) |
| (3) |
Vector x = (x1, x2, . . . , xn)T is called decision variable. xi (I = 1,2, . . . ,n) represents the service class Ci. The value of xi is determined by which component service is selected from Ci. Vector function f(x) is comprised of multiple QoS objective functions fi(x) (i = 1,2, . . . .,p). gi (x) represents multiple QoS constraint functions. The set of constrained QoS attributes is denoted by Γ. Fi (x) and gi (x) can be constructed with the help of the QoS model of composite service. Condition (3) indicates the functional dependency relationships between component services need to be satisfied. Rs has been defined in Definition 3. Given a feasible solution x*, if there does not exist another feasible solution x satisfying f (x) � f (x*), then x* is an efficient solution of MOP (i.e., the Pareto optimal solution) (Guntsch and Middendorf,2003). ACO4WS is designed to find the Pareto optimal solutions in this study.
The construction of optimal service configuration: When selecting the services in DFS&SSCA, the QoS of component service is not considered. In order to search the service configuration with optimal QoS, ACO4WS is designed through adding pheromone-based optimization mechanism (Dorigo et al., 1996) to DFS&SSCA. In DFS&SSCA, the set of current candidate component services is determined by following expression:
| (4) |
where, Cc is the service class being visited by the ant. M is a set of component services. Every m∈M is a component service which has been selected from visited service class Cm. There must exists service connection relationship between Cm and Cc, i.e., Cm →Cc or Cc →Cm.
The service selection based on pheromone: Because the goal of ACO4WS
is to select suitable component services for service composition, pheromone
is attached to every component service in ACO4WS.
| (5) |
where, τi represents the pheromone of service i. ηi = 1/ξi represents the heuristic information of service i. α and β are two parameters, which determine the power of influence of pheromone and heuristic information respectively. ξ is a weighted sum of multiple QoS attributes. The smaller is the value of ξ, the better is the QoS. The weights and ξ can be calculated as following steps (Hwang and Yoon, 1998):
| • | Construct a matrix Q = (qij) nxm. qij represents the QoS attribute j of service i. M is the quantity of QoS attributes. N is the quantity of all component services. To larger-is-better QoS attributes, such as throughput and reliability, qij is the reciprocal of these QoS attributes’ values. For example, qij = 1/throughput |
| • | Normalize Q to R = (rij) nxm to allow a comparable scale for all QoS attributes |
| • | CalculateR to get a column normalization matrix: |
| • | Calculate the information entropy of every QoS attribute: |
| • | Calculate the weight of every QoS attribute: |
| • | After getting the weights of QoS attributes, ξi is calculated as: |
The initial pheromone τ0 needs to be set as a value which is slightly larger than the average pheromone laid by the ants in an iteration cycle (Dorigo and Caro, 1999). The value of τ0 can be estimated as τ0 = m/ξnm. m represents the quantity of ants. ξnm can be calculated as following steps:
Step 1: Run DFS&SSCA once and select the component service with the smallest ξ in every selection
Step 2: Calculate the value of every QoS attribute of composite service according to the selected component services and corresponding QoS model
Step 3: Calculate the ξ of composite service and let ξnm equal the result value
Every ant k keeps a memory unit Qk which records the visited service classes and selected component services.
The pheromone updating: At the end of an iteration cycle, when every ant has constructed a solution, the pheromone of every service will be updated. First, the pheromone of every service decreases a value through the evaporation of pheromone. Second, pheromones are added to the services, which have been selected by the ants. The evaporation of pheromone is accomplished according to following expression:
| (6) |
where, ρ represents the evaporation rate of pheromone. 0<ρ≤1.After the evaporation of pheromone, every ant lays pheromone on the services selected by it:
| (7) |
where,
| (8) |
where, ξk represents the QoS of the service configuration selected by ant k. If a service is selected by many ants and the configurations including this service have better QoS, then more pheromone will be laid on this service.
| Algorithm 1: | The implementation of ACO4WS |
The implementation of ACO4WS: The implementation of ACO4WS is described in Algorithm 1. In ACO4WS, the ants construct the solutions via DFS and SSCA, which guarantees these constructed solutions satisfy the MOP constraint condition (3). In addition, whether the solutions satisfy the MOP QoS constraint condition (2) is verified in ACO4WS. Only when a solution satisfies the MOP QoS constraint condition (2), the corresponding ant is permitted to add pheromone to the services selected by it. After running ACO4WS, we can get an optimal service configuration.
EXPERIMENTS ON SERVICE CONFIGURATION OPTIMIZATION
To evaluate the efficiency of the proposed modeling method and ACO4WS, we take Fig. 1a as an abstract service composition example and optimize its configuration through simulation. We generate a number of candidate component services for each activity of service composition. In every service class, suppose the QoS attributes of services conform to normal distribution, we randomly generate the values of QoS attributes for each service. Two kinds of QoS attributes, response time and cost, are considered in the experiments. The distribution parameters of QoS attributes are shown in Table 1.
In the experiment example, the probabilities to choose t3 and t4 are set to 0.5. The loop probability to choose t6 is set to 0.5. We can define the corresponding QoS mode as follow:
| (9) |
| (10) |
The QoS constraints of composite service are set as Response time<35 and Cost<50. We randomly generate the functional dependency relationships between the component services with service connections. A service is associated to a random number of post services. According to the research in (Dorigo and Caro,1999), α and β in expression (5) are set as 9 and 10, respectively.
When the evaporation rate of pheromone is set as ρ = 0.3, the quantity of ants is set as m = 3 and the quantity of candidate services in each service class is set as 5, the optimization process of ACO4WS is shown in Fig. 2. After each iteration cycle, three service configurations are selected by the ants. The average QoS values of the selected configurations are calculated. ξ is a weighted sum of multiple QoS attributes. The experiment results indicate that the multi-objective QoS optimization of service composition can be achieved by using ACO4WS. Along with the increase of iteration times, the service configurations selected by the ants gradually tend to an optimal configuration.
In order to evaluate the performance of ACO4WS, we set the quantity of candidate services in each service class as different values and record the average execution time of an iteration cycle. The quantity of ants (m) is changed in each group of experiments. The experiments are made on a desktop computer with 2.4 GHz CPU and 1 GB RAM. The experiment results are shown in Fig. 3. The experiments indicate that the execution time of algorithm is mainly determined by the quantity of candidate services in each service class. Along with the increase of candidate services in each service class, the execution time of algorithm increases rapidly due to the exponential growth of service dependency relationships.
| Table 1: | The distribution parameters of response time and cost |
| Fig. 2: | The optimization process of ACO4WS |
| Fig. 3: | The performance of ACO4WS |
Therefore, ACO4WS still need to be improved to adapt to the situation that there are a lot of candidate services in each service class.
CONCLUSIONS
Due to the failure-prone run-time environment and the inconstant QoS of component services, a composite service must be able to be configured dynamically. In order to satisfy the multiple functional and non-functional constraints, suitable component services need to be selected for service orchestration process. We propose a service selection constraints configuration modeling method, which synthetically reflects the flow constraints and the functional dependency relationship constraints of composite service. Due to the complexity of multiple constraints, a special ant colony optimization algorithm ACO4WS is designed to accelerate the detection of optimal configuration. By using ACO4WS, We can get an optimal service configuration which strictly conforms to multi-objective QoS constraints and service functional dependency relationships.
ACKNOWLEDGMENT
This research was partially sponsored by the National High-Tech Research and Development Plan of China under Grant No.2007AA010305 and Science and technology project of Shaanxi Province under Grant No.2006K04-G10.