J. Cent. South Univ. Technol. (2009) 16: 0269-0274

DOI: 10.1007/s11771-009-0046-y

Dynamic services selection algorithm in Web services composition supporting cross-enterprises collaboration

HU Chun-hua(胡春华)^{1, 2}, CHEN Xiao-hong(陈晓红)¹, LIANG Xi-ming(梁昔明)³

 (1. School of Business, Central South University, Changsha 410083, China;

2. School of Computer and Electronic Engineering, Hunan University of Commerce, Changsha 410205, China;

3. School of Information Science and Engineering, Central South University, Changsha 410083, China)

Abstract: Based on the deficiency of time convergence and variability of Web services selection for services composition supporting cross-enterprises collaboration, an algorithm QCDSS (QoS constraints of dynamic Web services selection) to resolve dynamic Web services selection with QoS global optimal path, was proposed. The essence of the algorithm was that the problem of dynamic Web services selection with QoS global optimal path was transformed into a multi-objective services composition optimization problem with QoS constraints. The operations of the cross and mutation in genetic algorithm were brought into PSOA (particle swarm optimization algorithm), forming an improved algorithm (IPSOA) to solve the QoS global optimal problem. Theoretical analysis and experimental results indicate that the algorithm can better satisfy the time convergence requirement for Web services composition supporting cross-enterprises collaboration than the traditional algorithms.

Key words: Web services composition; optimal service selection; improved particle swarm optimization algorithm (IPSOA); cross- enterprises collaboration

Service oriented architecture is gradually adopted in the enterprise IT infrastructure, in order to meet the need of cross-enterprises collaboration. As a new distributed computational pattern, Web services have been largely attended by the academic and industrial domain in recent years [1]. In practice, a web service can only provide the single function. It cannot satisfy the requirement of the complex application. How to dynamically integrate the enterprises’ Web services to form a newly value-added and complex service to meet the requirement of different users is a popular research area [2].

Web services combination is an important means that makes the service resources in the enterprises cooperate with each other, in which Web service is discovered, selected and assembled into a much more granularity increment service or system to satisfy the application requirement of user [3]. The services combination may be divided into the static services combination and dynamic services combination according to dynamic combination performance. The services combination is of the following characteristics [4-6]: (1) the discreteness of the Web services, (2) the discreteness of services selection process, and (3) the rapid increase of Web services. Therefore, it is very difficult to dynamically select the Web service for services composition. In enterprises there are many Web services whose function is similar or the same, and whose non-function characters such as quality of service are different. A focused problem, which is called dynamic service selection problem in this work, is to choose idiographic service that satisfies the function requirement of each node from this abundant and dynamic web service, and form a feasible service composition instance to satisfy the individual requirements of users.

The methods of most Web services selection adopt the scheduling algorithms based on QoS local-best to choose the Web services now. In these algorithms, the choices of the corresponding idiographic service instances are unattached in each service node. So they cannot resolve the QoS global optimization problem of service composition. In Refs.[7-9], multi-restriction parameters of service QoS are transformed into a single-goal function by weighted linear method. In Refs.[2-3], a satisfying result is acquired using genetic algorithm to resolve the global optimization. But, with the rapid development of the Web service for choice, the time expansion of QoS scheduling is difficult to content the real-time demands of users in service composition supporting cross-enterprises collaboration.

In this work, a sort of QoS scheduling algorithm based on the improved particle swarm algorithm (IPSOA) was proposed to avoid the shortage of the algorithms referred above. A new equation was given by organically mixing the particle swarm optimization algorithm with the genetic algorithm, in order to decrease the iteration times for searching a better solution, eliminate the impact of a rapid increase services on the enterprises, and form the service composition routes which satisfy the service requirements.

2 Description of scheduling problem

In dynamic Web services composition supporting cross-enterprises collaboration, usual services composi- tion process model is made up of some service nodes. Every service node corresponds to a service set, in which there exist a lot of Web services whose function and transfer interface are similar, and whose non-function characters such as quality of service are different. The target layout algorithms and effective reasoning based on description logic are used to realize the dynamic composition of Web service supporting cross-enterprises collaboration.

Definition 1 The process of Web service composi- tion supporting cross-enterprises collaboration is usually described as a triple W≌, here, G denotes the Web service groups, N denotes the service nodes that only include function description, and not imply the idiographic Web services, and R is the mapping rule of Web service.

Definition 2 Give a network G(S, L, W), here, S denotes the node set, L denotes the link set, and W denotes the weight of links. If there are m (m≥2) restrictions C_i (i=1, …, m), also give n (n≥2) non- negative capability measure criterion f₁, …, f_n in every route P from the source node S to the terminal node T, and let f_i(P)＞=f_i(P_A) (i=1, …, n) to the all measure criteria only when there is P_A (P_A≠P) and P and P_A all satisfy restrictions C_i, where P_A denotes the average route. Then, P is called the multi-constrained, multi- objective optimal route.

In the cross-enterprises collaboration, the problem that the correlative services are assembled to form a service composition instance, can be expressed for the process of selecting QoS global optimization route. According to Definition 2, the problem, of which QoS global optimization route is dynamically selected in the process of services composition, can be transformed into the multi-objective optimization route problem, of which the best route is found from the source node to the terminal node with the QoS restrictions. Apparently, it is a NP complete problem. The particle swarm optimization algorithm (PSOA) has been widely used in multi- objective optimization problem, with a strong converg- ence. Therefore, in this work, an IPSOA was used to schedule QoS for the structure model to meet the relevant requirement of users.

3 Dynamic service selection algorithm

Lots of services with the same or similar function and different service quality exist in the network of enterpries at the same time [10]. How to find out the optimal QoS service instance to construct service composition route satisfying the requirement of users is the problem resolved in this section. The process of QoS scheduling is to select the optimal QoS service instances from the participant services with different service quality within the operation spanning graph, based on user individuation customization services composition [11]. In this work, we used the similar method mentioned in Ref.[12].

3.1 Theoretical foundation of IPSOA

The PSOA was proposed first by EBERHART and KENNEDY in 1995 [13-14], which is an evolution calculation algorithm based on iteration. However, the velocity is difficult to express according to the PSOA, and the local optimization occurs easily. So in this paper, an improved particle swarm optimization algorithm (IPSOA) is proposed to resolve the problem of finding the best QoS route and absorbing the idea of genetic algorithm. The improved particle swarm optimization algorithm (IPSOA) is to mix the PSO with genetic algorithms together, and bring the operations of the cross and the mutation in genetic algorithms into PSO. Then, the position, the velocity, the addition, the multiplication and the subtraction are redefined. The new definitions of the position and velocity are given as follows.

In the course of cross-enterprises collaboration, suppose that N=(n₁, n₂, …, n_m) denote a solution of the services composition route, here, m is the number of nodes in the network. Nodes of the graph from left to right and from top to bottom are ordered. That is, the first node is the first element of the array, the second node is the second element of the array, and so on. N_i=1 means that the corresponding node is selected into the route, or else, the node is not included in the route.

In IPSOA, the new definition of position is shown as follows:

N=(n₁, n₂, …, n_m)                             (1)

where  position N denotes a solution of the question. It includes m elements, and every element can be given one of the two values: 0 and 1. In this case, 1 means that the corresponding node is selected into the route, and 0 means the other way round.

In IPSOA, The new definition of velocity is shown as follows:

P=(p₁, p₂, …, p_m)                             (2)

The new velocity denotes the service selection direction of amelioration, that is, replacing the old route through the indexes and the corresponding elements shown in the velocity. It can be given to one of the three values: -1, 0 and 1. In this case, -1 means that the start index and the end index of link needed to be replaced, and 0 and 1 mean the values in the corresponding index location of the new route.

In IPSOA, the new definition of the addition (():) is given as follows. Suppose the values of the ith element and the jth element in B equal -1, then replace the values of the ()th element and the (j-1)th element in A with the values in the corresponding location of B. In fact, the addition implements the cross operation of the genetic algorithm, that is, a link of the old route is replaced with the new link, and the direction of replacing is guided by the better local information and the better global information.

In IPSOA, the new definition of the subtraction ((⊙): A⊙B) is given as follows. It means that the result is an array, and the value of an element is equal to -1 when the values of corresponding elements of A and B are the same. If there are more than two values of elements equal to -1, then select two of them randomly. Only when two values of elements equal -1, the values between the two -1 equal the corresponding values of A, and the other values of the result array are set to be 0. In fact, the subtraction implements the finding-direction operation, that is, to find out the differences among the current route, the better local route and the better global route, and then to find out the direction of route replacing.

The new definition of the multiplication () is given as follows. The multiplication is worthy only when it is used together with subtraction, for example, in C₁Rand()(P(t, i)⊙N(t, i)), the result of P(t, i)⊙N(t, i) may include values of -1 n times, then D₁ and D₂,  where D₁ has the same value of C₁%nth and D₂ has the same value of Rand()%nth, are reserved. The current route, when comparing with the better local route and the better global route, may include several links needed to be replaced, then select a link to be replaced according to the probability of C₁ and Rand().

Based on the basic expressions of the particle swarm algorithm, the new expressions of IPSOA are shown by variable replacement as follows:

P(t, i)=P(t-1, i)C₁Rand()(P(t, i)⊙N(t, i))

C₂Rand()(P(t, g)⊙N(t, i))              (3)

N(t, i)=N(t-1, i)P(t, i)                     (4)

Theorem 1 In the course of services composition, if the initial route for iteration is given, the better services composition route can be found after several iteration transformations using Expressions (3) and (4).

Proof Give a Web services composition route of the network service model, a new services composition route can be found after an iteration transformation. The new route is built by adding or deleting some nodes from the old route. We can estimate whether the new route is in accord with the rule by checking if the new route is within the services composition spanning tree of the logic composition. If the new route is in accord with the rule, then check if the capability of the new route is better than that of the old one. If so, the new route is reserved; otherwise, the old route is reserved. After several iterations, some routes within a scope can be visited, and the last result is the optimization of these routes. The optimization of the whole routes in the network can be found by increasing the iteration times.

Suppose that N(0, i), P(0, i), f(0, i), i=0, 1, …, m (m is the number of particles) denote the initial route in the course of services composition, the initial velocity and the function value of the route quality, respectively. Also, the function value of the route quality is used to evaluate the service quality of the route, and the higher the value, the better the service quality of the route. The new route is built by using Expression (4):

N(t, i)=N(t-1, i)P(t, i)                     (5)

The function value of the route quality f(t, i) in the new route can be calculated, and the new route is reserved only when f(t, i)≥f(t-1, i). The function value of the route quality is f(t_m, i)≥f(t_m-1, i), and t_m≥t_m-1. That is, the new route found after several iterations is better than (the same as at least) the former route.

According to Expression (3), the advantageous information is absorbed when the new route is found, and the velocity direction of finding consults the former velocity direction and the direction of the current better route.

C₁Rand()(P(t, i)⊙N(t, i))≥C₁Rand()

(P(t-1, i)⊙N(t-1, i))                     (6a)

C₂Rand()(P(t, i)⊙N(t, i))≥C₂Rand()

(P(t-1, i)⊙N(t-1, i))                     (6b)

Therefore, P(t, i)≥P(t-1, i), the better services selection route in the course of services composition can be quickly found using Expressions (3) and (4). Proof is completed.

3.2 Design of algorithm QCDSS

The dynamic services selection course of services composition is the process that selects suitable services to run from the services composition structure model shown in Fig.1, and its core function is service scheduling.

Fig.1 Instance of Web services composition

The services fitted to QoS requirement will be selected to satisfy the individual requirement of users while running the services composition, because lots of services with the same or similar function and different service quality exist in the cross-enterprises at the same time. Different services quality guidelines are provided with different properties, some with adding property, such as running cost and running time, and some with multiplying property, for instance, the reliability or usability value. In this work, the calculation rule of QoS for services composition refers to calculation algorithm in Ref.[4].

Commonly, user requires that the running time is as short as possible, the cost of route is as small as possible, the service usability is as high as possible, the calculation capability of route is as large as possible, and the service reliability is as large as possible. Suppose that g_j(n) (j=1, 2, …, m) denotes QoS of certain service selected while QoS scheduling route is running. The optimization goal of QoS in the course of services composition is expressed as follows:

g(x)=F(ming₁(n), ming₂(n), …, maxg₅(n))         (7)

In Expression (7), the minimum function can be changed into the maximum function [11]. Therefore, the synthesis service quality function of every link can be expressed as follows:

≥n∈N             (8)

where  g_j denotes different QoS requirement of users, and W_j denotes a weight given according to the scheduling goal, and it reflects the weight of each optimization goal. For QoS requirement of different users, the optimization weight is expected to set by users while submitting service composition logic structure.

Suppose that each route in service composition includes n links, its synthesis service quality is decided by each link, that is, the value of synthesis service quality function equals the sum of all links’ synthesis service quality function values. The synthesis service quality function is used to express fitness function.

                              (9)

In the course of cross-enterprises collaboration, according to the composition model and workflow logic, the services composition spanning tree should be firstly found. Every selected route should be checked whether it belongs to the composition model, and tested whether it is better than the old one only when it belongs to the composition model. Otherwise, another workflow route is found again. The links of the routes include some service quality guidelines. Estimate whether the route satisfies these guidelines, that is, whether the route satisfies Expression (7), and find another route if it does not satisfy the condition. Then, calculate the synthesis service quality function value of every link and the synthesis service quality function value of the route. Do evolution operation to these initial routes respectively, that is, change some links of the routes in each iteration, then the new routes will be built, and the better local route of each evolutionary switch can be found. At the same time, the better global route of all switches can be found. In the later iteration, the direction of evolution is close to the better local route and the better global route. The hybrid particle swarm optimization algorithm for finding a better route (IPSOA) is expressed as follows.

Algorithm 1(QCDSS) Dynamic services selection algorithm with multiple QoS constrains based on IPSOA.

Step 1 In the course of services composition, suppose that every service is substituted for a particle in IPSOA. Give a randomly initial position X(0, i) and an initial velocity p(0, i)(i=1, 2, …, N_max) to every particle, here, X(0, i) denotes the ith initial route, and p(0, i) denotes the replacing direction of link in the ith initial route. Therefore, the better local route P_i1=X(0, i) and the better global route P_g are the best route in P_i.

Step 2 Suppose that N_max and N_{I, max} denote the number of particles and the maximum number of iteration in IPSOA. If the times of current iteration is equal to N_{I, max}, then, go to Step 6.

Step 3 For each particle in the particle swarm, calculate the new velocity and position using Expressions (3) and (4). Estimate whether the new route is fit in with the limited conditions of logic services composition, if so, then, check whether each link of the route is fit in with the conditions given by Expression (7), and calculate the fitness function value when the former conditions are satisfied.

Step 4 Replace the current better local route with the new position if the fitness function value is less than that of the current better local route, and go to Step 5. Otherwise, the old positions are reserved, and go to Step 2.

Step 5 If the better local route of a particle is better than the current better global route, then, update the current better global route with the better local route. And go to Step 2.

Step 6 Output the optimal services selection route in the course of cross-enterprises collaboration and its fitness function value.

Because the introduction of evolution direction is added into Algorithm 1, the best solution can be more quickly found than that of the common random evolution strategy. The better service selection route which satisfi- es multi-QoS constrainsts can be found after several iterations, and all of QoS requirement supporting cross- enterprises collaboration will be satisfied. It is easy to prove that QCDSS algorithm based on IPSOA in the course of services composition is more effectively than genetic and eFlow algorithms.

Theorem 2 In the course of services composition, the fitness function of Algorithm 1 is better than that of the genetic algorithm.

Proof In Algorithm 1, at first N_max initial routes X(0, i), then, replace a link of each initial route using Expressions (3) and (4). The new velocity and route are obtained as follows.

v(1, i)=v(0, i)C₁Rand()(P(0, i)⊙X(0, i))

C₂Rand()(P(0, g)⊙X(0, i))           (10)

X(1, i)=X(0, i)P(1, i)                       (11)

According to Theorem 1, a new route can be built from each initial route after iterations, X(t+1, i)=      X(t, i)P(t+1, i), and the new route X(t+1, i) may be random in a sense, so the routes in a certain search space may be found. Also, inducting by the better local route and the better global route, the finding process will forward close to the best of the whole routes gradually. The new routes will not always accord with the rule of services composition logic and the requirements of QoS. But, once they satisfy the conditions, they will be reserved. Thus, the optimal service composition route f(t+1, i)≥f(t, i) can be found using Algorithm 1 after several iterations, and the fitness function of Algorithm 1 is better than that of the genetic algorithm.

In the course of services composition supporting cross-enterprises collaboration, Algorithm 1 will initialize swarm, use fitness function to estimate the property of each solution, and randomly search the optimal route according to the fitness function value. In each iteration, the difference between the better local route and the better global route of every evolutionary branch is taken into account, then the finding process forwards close to the better local route and the better global route with a certain probability. The efficiency is faster and the property of searching is better than that of the genetic algorithm since the introduction information is inducted in the direction of evolution. Its efficiency and search course are similar to those mentioned in Ref.[12]. It is shown that the IPSOA can not only availably solve the scheduling problem of grid workflow in Ref.[12], but also effectively resolve the problem of dynamic services selection in service composition supporting cross- enterprises collaboration.

4 Result and analysis of experiments

In order to better clarify the significance of the services selection algorithm proposed in this paper, a service workflow evaluation system (SWES) is built [15]. The SWES is made up of five parts, namely system input model, SRS register model, WSSP spanning model, route arrangement model and running setting model. The simulation services datum is used in this paper, whereas without a standard platform and related standard test data set in services composition. The generative elements of services consist of services classes, input interface, output interface, and the non-functional property of QoS. The service instances generated in this experiment belong to the service classes of the operation logic, according to the hypothesis of services matching.

In the experiment, the service composition instances are used, as shown in Fig.1. The instances include a sequence activities, a switch activity, a while activity, a flow activity, a pick activity and a prior activity. The experiment results are concluded by comparing the QCDSS algorithm proposed in this paper with the QoS scheduling algorithm based on genetic algorithm and GODS algorithm [4].

The convergence complexion of the fitness function in this experiment is shown in Fig.2, here, the algorithm will stop running when the individual of the swarm tends to stabilize, that is, the diversification of the individuals’ fitness values in the swarm tends to be 0, and the final fitness function value is -0.147. These results proved by experiment are close to those mentioned in Ref.[12].

Fig.2 Convergence of fitness function

Also, the running time of QCDSS algorithm, the genetic algorithm and GODS algorithm [2] is compared in this experiment. Give different network models with 100, 200, 300, 400 and 500 services respectively, then the time for finding out the best route is shown in Fig.3. It can be seen that the time astringency of QCDSS algorithm is better than that of other two algorithms.

Fig.3 Comparison of execution time

5 Conclusions

(1) The problem of dynamic services selection in the process services composition supporting cross- enterprises collaboration is transformed into a multi- objective services composition optimization with QoS constraints.

(2) Multiple QoS constraints scheduling algorithm based on IPSOA is proposed to resolve the problem of multi-objective services composition optimization with QoS constraints. The IPSOA is to mix the PSOA and genetic algorithms together, and to bring the operations of the cross and mutation in genetic algorithms into PSO.

(3) Theoretical analysis and experimental results indicate the feasibility and efficiency of the algorithm, and preferably satisfy the convergence requirement for Web services composition supporting cross-enterprises collaboration.

References

[1] PAPAZOGLOU M P, GEORGAKOPOULOS D. Service-oriented computing [J]. Communications of the ACM, 2003, 6(10): 25-65.

[2] DANILO A, BARBARA P. Adaptive service composition in flexible processes [J]. IEEE Transactions on Software Engineering, 2007, 33(6): 369-384.

[3] WANG Yong, HU Chun-ming, DU Zong-xia. QoS-aware grid workflow schedule [J]. Journal of Software, 2006, 17(11): 2341-2351. (in Chinese)

[4] LIU Shu-lei, LIU Yun-xing, ZHANG Fan. A dynamic Web services selection algorithm with QoS global optimal in Web services composition [J]. Journal of Software, 2007, 18(3): 646-656. (in Chinese)

[5] GRAFEN P, ABERER K, HOFFNER Y, LUDWIG H. Cross-low: Cross-organizational workflow management in dynamic virtual enterprises [J]. International Journal of Computer Systems Science and Engineering, 2000, 15(5): 277-290.

[6] WANG Pu-wei, JIN Zhi, LIU Lin, CAI Guang-jun. Building toward capability specifications for Web services based on an environment ontology [J]. IEEE Transactions on Knowledge and Data Engineering, 2008, 20(4): 547-561.

[7] LIU Y T, ANNE H H, ZENG L Z. QoS computation and policing in dynamic Web service selection [C]// Proceedings of the WWW 2004. New York: ACM Press, 2004: 66-73.

[8] JORGE C, AMIT S, JOHN M. Quality of service for workflows and Web service processes [J]. Journal of Web Semantics, 2004, 1(3): 281-308.

[9] ZENG L Z, BOUALEM B, ANNE H H, JAYANT K, HENRY C. QoS-aware middle ware for Web Services composition [J]. IEEE Transactions on Software Engineering, 2004, 30(5): 311-327.

[10] HU Chun-hua, WU Min, LIU Guo-ping. QoS scheduling based on trust relationship in web service workflow [J]. Chinese Journal of Computer, 2009, 32(1): 42-53. (in Chinese)

[11] HU Chun-hua, WU Min, LIU Guo-ping, XU De-zhi. An approach to constructing service workflow model based on business spanning graph [J]. Journal of Software, 2007, 18(8): 1870-1882. (in Chinese)

[12] HU Chun-hua, WU Min, LIU Guo-ping. QoS scheduling algorithm based on hybrid particle swarm optimization strategy for grid workflow [C]// Proceedings of the 6th International Conference on Grid and Cooperative Computing. New York: IEEE Computer Society, 2007: 330-337.

[13] EBERHART R C, KENNEDY J A. A new optimizer using particles swarm theory [C]// Proceedings of the 6th International Symposium on Micro Machine and Human Science. Nagoya: IEEE, 1995: 39-43.

[14] EBERHART R C, SHI Y. Particle swarm optimization: Developments applications and resources [C]// Proceedings of IEEE International Conference on Volutionary. New York: IEEE Computer Society, 2002.

[15] HU Chun-hua, WU Min, XIE Qing, WANG Jian-ming. SWES: Performance evaluation system for Web service workflow on QoS [J]. Journal of Central South University: Science and Technology, 2007, 38(5): 962-969. (in Chinese)

Foundation item: Project(70631004) supported by the Key Project of the National Natural Science Foundation of China; Project(20080440988) supported by the Postdoctoral Science Foundation of China; Project(09JJ4030) supported by the Natural Science Foundation of Hunan Province, China; Project supported by the Postdoctoral Science Foundation of Central South University, China

Received date: 2008-06-28; Accepted date: 2008-09-28

Corresponding author: HU Chun-hua, PhD; Tel: +86-731-8688270; E-mail: huchunhua777@163.com

(Edited by CHEN Wei-ping)