- Web service composition enables seamless and dynamic integration of business application on the web. The performance of the composed application is determined by the performance of the involved web services. Therefore, the selection of composite services is a very complex and challenging task, it becomes a decision problem on which component services should be selected so that user's preferences are satisfied, especially when it has to consider not only the user's QoS preferences (non-functional aspect) but also user's functional Preferences (functional aspect). In this paper we address this problem and present a solution that combines local selection with global optimization. The proposed solution consists of two steps: First, in the local selection, we take into account both of users' preferences and QoS requirements and use dominance relationship to select the top-k services and reduce the services involved in the composition. Second, we use a global optimization to fulfil the global requirement and select the Optimal composition by using the Tabu Search Algorithm. The experimental evaluation indicates that our approach significantly outperforms existing solutions in terms of optimality.
The Selection of an appropriate Web service for a particular task has become a difficult challenge due to the increasing number of Web services offering similar functionalities. The functional propertie mtd mmmzmzmb s describe what the service can do and the non-functional properties depict how the service can do it. The requirements of the user are rarely satisfied by one web service but generally we need more than one. The web service com-position consists in building a value-added ser-vices and web applications by integrating and composing existing elementary web services. A lot of approaches have been proposed, they include AI planning techniques [15], formal models [7] (finite states machines, petri nets,...) and metaheuristics[8][19]. The majority of them does not address the functional, the non functional aspects and the global constraints in the same time. Our purpose is to take into account both of the two aspects(functional, n-fonctional) and fulfill the global constraints. In order to explain our motivations let us consider the following example: The example [6] in Table-1 presents an ecommerce system supporting users to buy cars. Each service has its input i() and output o() parameters. Services providing the same functionality belong to the same class( S21; S22; S23 belong to S2). Each service has: i. Functional constraints on the data it manipulates, For instance the cars returned by S22 have prices between 5500 and 7000 euro. ii. N-functional constraints, Services set their values associated to three parameters q1,q2,q3 corresponding to price, response time and availability. Suppose that a user x wants to buy a french car preferably at an affordable price[5000,7000] with warranty between 12 and 18 months, having a power [60,80] and consumption [10,11]. The user preference concern also the global constraints, like the total price of the composition don’t exceed 10 euro.
The user will have to invoke S11, he can then invoke service one or more of services belongs to class S2 finally, he invoke one or more of services belongs to class S3.
How to find the optimal composition c that satisfy: i. The user preferences (functional Aspect) and at the same time satisfy (non functional Aspect) i.e the services involved in the composition c must maximize the positive QoS Criteria such as reliability and availability, and minimize the negative criteria such as cost and execution time. ii. The global constraints which relate to the QoS attributes of the composition.
To face theses challenges - We compute the matching degrees between services’ constraints and user’s preferences and in order to select the most relevants services and reduce space search, we use the concept of Fdominance relationship to select the top-k services of each class that will be involved in the composition process. - We satisfy the global constraints by using the tabu search algorithm which has been successfully applied to a wide variety of problems because of it’s simplicity and practical effectiveness.
Formally our proposal can be described as follows: i. we have to find the top-k services Sij in each class Si that match the user preferences QoS by using the matching degrees M and ranking them by considering both of QoS and Functional constraints by using the Fdominance score. ii. we have to search a composition c=(s1, ..., sn) such that we have to maximise the function U(c) and satisfy each global constraint, to this end we use the Tabu Search Algorithm. U(c): denotes the Fdominance Score of the functional and nfunctional properties of c. The Fdominance Score is detailed further.
The main contributions of this paper are summarized as follow : 1.We consider both of the functional and the nonfunctional user preferences at the same level. We notice that the best services which fulfill the functional properties are not always those which maximise the QoS properties and vice versa, so considering the two properties is a compromise to match as possible the two aspects at the same time. 2.We Combine the local and the global optimization. Since the number of candidate services for a composition may still too large, we use the FDominance relationship to reduce the search space and select the Top-k services. After that we use the Tabu Search for the global optimization to satisfy global constraints. We notice that the best service in each class produces the best composition, this one is not the best for the user if it violates the global constraints.
The rest of the paper is organized as follows. In the next section we discuss related work. In Section 3, we formalize the problem and present our approach. Section 4 presents performance analysis and experimentations. Finally, section 5 gives conclusions and an outlook on possible continuations of our work. 2
A lot of efforts have been devoted to the service selection/composition. We distinguish three major categories: the selection based on QoS, the selection based on functional preferences and the selection based on QoS and functional preferences. The first category takes only the user preferences into account to rank candidate services. Many searches have been made in this domain, some of them uses the Pareto dominance [18] [17], the others use the fuzzy set theory to models preferences to select top k dominant skylines [1] [5] [6]. The second category is based only on the QoS parameters, it can use two types of approaches [2] the multi-objective optimization and the monoobjective optimization. The multi-objective selection can be supported by using database techniques like the divide and conquer algorithm, the bitmap algorithm, the index based algorithm(b-tree, hash table) and the nearest neighbor algorithm (R tree). The mono-objective class involves several approaches [4][9] [16] [23], which can use global selection pattern[4] [23] or local selection pattern or hybrid selection pattern [11] The third category is based on the QoS constraints (non functional aspect) and Users preference constraints(functional aspect). The majority of research does not address the functional and the non functional aspects in the same time, especially for the workflow based composition. Our contribution belongs to this category. 3
Our proposed approach contains two phases. Phase 1 (The local selection): we compute the top k services and reduce the search space by using the FDominance. Phase2 (The global optimization): We find the near optimal composition that satisfy the global constraints by using Tabu search Algorithm. 3.1
Let be Rq a user’s request where Rq = ff c; gcg, f c is a vector of user preferences f c = ff c1; ::; f cmg and gc = fgc1; gc2; ::; gcng is a vector of n QoS global constraints like time, reputation.
Given a set of services classes S = fS1; ::; Sng where a class Sj regroups the services that had the same functionalities but different constraints. Let be Sij the j-th service of the class i. It is described as a set of two vectors : vector Q for QoS attributes and Vector f for Functional constraints. we use the vector f ci to represent the subset of f c that corresponds to the constraints involved in the services of the class Si.
The request of the example is Rq=fc(f c1=(),f c2=([5000; 7000]; [12; 18]),f c3=([60; 80] ,[10; 11]),gc(q1 < 10). 3.1.1
The service selection process starts with computing the matching degree between the request Rq and services Sij .
Given the users preferences on service description attributes f c, the degrees of match between a requested Rq and an available service (see e.g.,[10] ) are computed. In this work, we use the Jaccard coefficient for matching service descriptions. If I1; I2 are two intervals, their Jaccard coefficient is J (I1; I2) = jjII11\[II22j , where jIj measures the length of the interval.
We suppose that we have m functional constraint f (Sij ) = ff1(Sij ); ::; fm(Sij )g where fi(Sij ) is the value of the i-th functional constraint of the service Sij .
We use the Vector M (cfi; Sij ) = (m1(Sij ); ::; mn(Sij )) to represent the matching degrees between f (Sij ) and the subset vector of preference constraints f ci of the user’s query Rq where the function mk(Sij ) is the value of matching degrees (the Jaccard coefficient) between the k -th functional constraint off ci and the k-th functional constraint of fi(Sij ).The table 2 show the Jaccard value macthing of the example 1
Sij S11 S21 S22 S23 S31 S32 S33
M (f ci; f (Sij )) m1 m2 - 1 0; 5 0:75 1 0 0:33 0:6 0:14 0:50 0:25 0 0:1 3.1.2
We suppose that we have R quantitative QoS values for a service Sij . we use the vector Q(Sij ) = fN q1(Sij ); ::; N qr(Sij)g to represent the QoS attributes of a service Sij where the function N qk(Sij ) represent the k-th Normalized quality attribute of Sij . We convert the negative attributes(time, cost) into positive attributes by multiplying their values by -1 such that the higher value is the higher quality. To allow for a uniform measurement of Web service qualities independent of units, we normalize the different QoS values in the range [0, 1], as follow :
N qk(Sij ) =
qk(Sij ) Qmax(qk)
Qmin(qk)
Qmin(qk)
(
Let us consider the services in Table 3, to compute the Top-K services by taking into account the f ci f c1 f c2 f c3 functional and non- functional parameters,we have to compare the services of the same class by considering the vectors (M (); Q()) of each service Sij (see Table 3) .
Definition1 (Service Dominance) A Web service Sij is said to dominate (Pareto dominance) another Web service Sik if and only if Sij is better than or equal to Sik in all parameters and better than Sik in at least on one parameter.
Definition2 (User Preferences-aware Service Dominance) Given a user Functional-preference space M, and a user non-Functional space Q, a service Sij is said to dominate an other service Sik on M and Q if and only if 8mi 2 M , 8N qi 2 Q, (mi(Sij ) mi(Sik)) ^ (N qi(Sij ) N qi(Sik)) and 9N qt 2 Q, 9mt 2 M , (mt(Sij ) > mi(Sik))^ (qt(Sij ) > qi(Sik)) according to our example table 3 we have S21 dominates S23, let consider now S21 and S22, in fact neither S21 dominates S22 nor S22 dominates S21 because S21 is better than S22 in m1 and q2, and S22 is better than S21 in m2 and q3, so S22 and S22 are incomparable. However we can consider that S22 is better than S21 since q3(S22) = 0:75 is much higher than q3(S21) = 0, and q2(S22) = 0:75 is almost close to q2(S21 = 1). here for, it is more interesting to use the FuzzyDominance score(FDominance) relationship defined in [5] to express the extent to which a matching degree (more or less) dominates another one.
Definition3 (FDominance) given two d-dimentional point u and v the Fdominance express the extent to which u dominates v as deg(u > v) =
Pd
i=1
d
(ui; vi)
(
+ " 1 Si 1
X
Sik2Si F DS(Sij ) = deg(Sij > Sik) Let’s return to our example deg(S21 > S22) = 0:4 and deg(S22 > S21) = 0:29 with = 0:1 and = 0:2. This is more significative than S21 and S22 are not comparable.
We compute F DS(Sij ) of all services for each class in order to rank them. After that we take the Top-K services. Only the Top-k services will be considered in the global optimization step. 3.2
3.2.1
Let C = fS1i1 ; ::; Snin g be a composition of n services. The global QoS constraints gc may be expressed in term of upper and/or lower bound for the aggregated values of the different QoS criteria. we only consider positive QoS criteria to have only lower bound constraint. We say that a composition C is feasible if all the request’s global constraints are satisfied, this means that Qc(c) gc. where Qc(c) is the vector of the QoS value of a composite service c.
The QoS value of a composite service depends on the QoS values of its components as well as the composition model used. In this paper we consider the sequential composition. The QoS vector of composite service C is defined as Qc(C) = fQc1(C); ::Qci). Where Qci(c)g represents the value of the i-th QoS attribute of C and can be aggregated from the QoS values of its components services by using the aggregation function inspired from [22], see Table 4.
QoS Reponse Time Reputation Price Reliability Availability 3.2.2
Different service composition can be generated from different Si Top-K service Classes to answer a user query. In order to evaluate the service compositions, we need an objective function u(c) that associates a value to the composition.
u(c) = F DS(c) + P (c);
where F DS(c) is the FDominance(see
definition3) Score associate to a composition C =
fS1i1 ; ::; Snin g as follows
(
The Tabu list in our approach is the structure that contains the service composition used in the previous iterations. We use the objective function u(c) (see formula 1) to evaluate each neighbor solution.
We define the diversification strategy as restarting the process after a certain number of iterations when the Optimal local solution stagnates. c- The Tabu-Search optimization algorithm The algorithm, TSOptSelection, selects the Optimal or near optimal services composition according to the objective Function u(). The algorithm proceeds as follows.
tion compoition (line 6-13).
For each solution, we generate all the neighbor solutions by using SwapMoves() that defines all the possible moves, then we compute the score of all the composition solutions in Ls (line 8) and choose the best neighbor of Ls (line 10). The best neighbor is the one having the highest score. if the best neighbor solution is in the tabu list, we choose the next Best solution that not in the tabu list (line 12). This one will be used in the next iteration.
Solution (line 14).
Add the best neighbor solution to the tabu list (avoid a cycle)
if we reach p% of iteration and we have no amelioration of the optimality we restart the processing Algorithm.
The algorithm ends when it satisfies the stop condition (reach the number of iterations or the stagnation of the solution for it iterations) n u(c) = 1 X F DS(Siji ) n
i=1 The function p(c) is the penality function which decreases the utility score u(c) of the composition that violates the global constraints gc, it’s defined as follow P (c) = Pin=1 Dk(c) where
Dk = 0 jQk(c)
Gckj if Qk(c) otherwise
Gck 3.2.3
In this paper we apply metaheuristic optimization techniques to select the optimal or a near-optimal solution in Web service composition, we use the Tabu search-based method and propose The TSOptiSelection Algorithm to maximize the objective function u(c). Our algorithm (Algorithm1) uses a Tabu Search algorithm with diversification strategy. The Tabu search meta-heuristic relies on the principles of forbidding a set of elements which are stored in tabu list. The basic concepts defined in Tabu search are: The initial solution , neighborhood of a solution , tabu-active elements , tabu list, the objective function and diversification strategy. a- The initial Solution In our approach, the initial solution C0 is a random composition, we choose a random service from each class, for an efficient initial solution the services should not have the same rank in order to have different composition by moves services between classes let Co = fS1j1 ; ::; Snjn g be an initial solution, C0 is an efficient initial solution iff 8Sijk 2 Co; 8Smjl 2 Co=i 6= m; k 6= l b- The neighborhood The search space of our algorithm is the set of compositions obtained by moves applied to the Algorithm 1 TSOptiSelection CPU @ 1.40GHz 4 processors, 4.0GB of RAM, Input: T op-kRelevantsServices; t; it; p // t is the Ubuntu 13.10, Netbeans 7.4. several simulations lenght of Tabulist,it is the number of iterations, have been made to compare our Approach:hybridp is the stagnation rate Optimization(Tabu Search with Top-K).) to the Output: C the optimal composition Standard Tabu Search. For simplicity we denote 1: C0 ComposeServices(random(Sij ); ::random(Sij)) our approach (TS (Top-K)).
// an initial solution 2: C C0 We compare the optimality rate of TS (Top-K) and 3: Ls fC g // set of composition solution the standard Tabu Search . We consider several 4: LT abu fg // Set of composition Tabu top k (top 100, top 50, top 20 and top 10) The opti5: while N otStopCondition do mality Score is defined as follows: rate=the fitness 6: Ls SwapM oves(C0) // Generate all the of the current solution/the fitness of the optimal so
Neighborhood solutions of C lution. The optimal solution’s fitness for this base, 7: for all Cs in Ls do is equal to 0.62, therefore the optimality rate of a 8: score = ComputeU tililyScore(C) // use solution ’a’ is u(a)/0.62
the objectif function u(c) As depicted in the Figure 1 the use of the top-k se9: end for 10: C0 M axScoreComposition(lS) 11: while C0 is Tabu do 12: C0 N extM axScoreComposition(lS) 13: end while 14: LT abu LT abu [ C0 15: if Score(C0) > Score(C ) then 16: C C0 17: end if 18: if it = it*p and stagnation and Restart number
< threshold then 19: TTSOptiSelection(T op-k) 20: end if 21: end while Figure 1: The optimality rates of the Tabu Search/ 22: return C TS(Top-K) with constraints(it=500,p=0.2,t=10) 4
This section briefly reports our experiments
related to our approach. For this purpose we use a
data set by assigning arbitrary values to 2000
services , we have 10 classes of services and each
class contains 200 instances,each service has 02
functional-constraints and 5 QoS attributes. The
QoS value of each attribute is generated by a
uniform random process which respects the bound
specified as follow: Response time (0-300s),
Reputation (
All the experiments are taken on the same software and hardware, which were Intel i3-2365M lection combined with the tabu search largely outperforms the standard tabu search in term of optimality rate for all simulations, The main reason why the optimality rate of our aproach is better than the standard tabu search is the use of the Top-K services which reduces the search space of services composition and consider only the best services in each class. 5
In this paper, we have presented an optimization approach for web services composition. this latter takes into account the functional and n-functional properties at the same time. Our approach reduces the search space and handles the global constraints. Experimental results show that the proposed approach is effective and efficient. For future work, we will consider alternative algorithm like Particle Swarm Optimization with the use of dominance relation ship for efficient and fast Web Service Composition.