Constraint-based QoS-aware Web Service Composition in Cross-organizational Collaboration

TAN Wenan,ZHAO Yao,JIN Ting

(1.School of Computer and Information Engineering,Shanghai Polytechnic University,Shanghai 201209,China; 2.School of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 211106,China)

【Abstract】 To improve the Quality of Service (QoS)-aware Web service compositions considering constraints between cross-organizational business,this paper analyzes the types of constraints,and accordingly proposes a Chaos Genetic Algorithm (CGA).The algorithm creates an initial population of service compositions based on the chaos theory,and then processes individuals which violate constraints in the initial population using repair strategies.Next,a new fitness function is designed to gradually eliminate the infeasible compositions generated in evolution.Finally,the algorithm makes minor chaotic disturbances on the evolved group to accelerate convergence and avoid local optimum.Experimental results demonstrate the effectiveness of the proposed algorithm.

【Key words】 cross-organizational; chaos; genetic algorithm; Quality of Service (QoS); Web service composition; constraint; disturbance

0 Summary

Different organizations can achieve business goals through cross-organizational collaboration,which has become the mainstream model of building complex business applications in the current Business to Business (B2B) environment[1].To implement B2B cross-organizational collaboration,Web service is widely adopted as services computing acquires promotion.Web service is featured by high versatility,platform independence,and programming language independence.

For the cross-organizational business process collaboration,it is urgent to use service composition for developing business applications.Web service can be composed using existing Web services provided by multiple business partners in the light of business processes.This is so called Web service composition[2].A reliable and flexible service composition can increase the effectiveness of cross-organizational collaboration.

In the cross-organizational business process,the Quality of Service (QoS)[3]attributes,such as response time,price,reliability,availability and so on,are critical factors to consider in the selection of an appropriate Web service that meets the non-functional requirements of users.The steps of implementing a QoS-aware Web service composition can be outlined as follows.Firstly,the Web service Business Process Execution Language (BPEL)[4]is used to describe an abstract combination request for the cross-organizational business process,forming a process flow diagram that includes many composite structures,such as sequential,loop,parallel,conditional and so on.Secondly,a service discovery engine finds suitable Web services through the syntactic or semantic functional match between the service description and the task in the cross-organizational business process.Thirdly,each task in the cross-organizational business process matches a series of candidate services (concrete service).Finally,a Web service composition execution engine is used to select and bind concrete services to each task.

1 Preliminary

Given the tasks to be bound,this paper focuses on how to select a specific service for each task to reach composition QoS optimization under constraints.QoS-aware Web service composition has been intensively studied in the past few years and several effective approaches have been proposed[5-7],but the studies have rarely considered the constraints between services,which is common in real-world scenarios.Constraints can be categorized into political constraints and standard system constraints.Political constraint means that some political relevance exists between services.Political constraints may lead to conflicts or dependency relations between services.Standard system constraints mean that some Web services cannot or must be combined into a composite service because of technical compatibility or business compatibility.Standard system constraints can also lead to conflict or dependency relations between services.To simplify,we divide the constraints into conflict relations and dependency relations.Figure 1 is an example of such constraints.

Fig.1 Travel planner Web service

As shown in Figure 1,a travel planner Web service can be built by aggregating transportation reservation Web service (provided by providers A,B,C),hotel reservation Web service (provided by D,E),and ticket booking Web service (provided by F,G).However,there are some technical incompatibilities or business incompatibilities of service providers in the cross-organizational business process.For example,if we have selected the service provider A to provide transportation reservation Web services,then we could not choose the service provider D to provide hotel reservation servicebecause there are technical incompatibilities between them.We can say that there is a conflict relation between the service that A provides and the service that D provides.Another type of constraint is dependency relations.For example,if the ticket booking service (provided by G) and the hotel reservation service (provided by E) form a political alliance,then the two services must be chosen together when either is selected.These examples indicate that selection of a Web service is not a standalone operation,as it may constrain the selection of other services.In other words,the conflict relations and dependency relations between Web services should be considered in Web service composition.

This paper considers not only the QoS characteristics of service composition in the cross-organizational business process,but also the constraints between services.The first innovative point of this paper is the analysis of the constraints that affect the Web service composition in the cross-organizational business process.The second innovative point is the creatively designed Chaos Genetic Algorithm (CGA).The third innovative point is the repair strategy designed to deal with the individuals in the initial population that violate different constraints.The fourth innovative point is a new fitness function to realize CGA.Genetic Algorithm (GA) is a common method applied in combinational optimization[8].Chaos Optimization Algorithm (COA) is used to overcome the deficiency of GA,such as the tendency of falling into local optimal solution easily and lower convergence speed[9].This paper combines GA and COA to achieve a CGA which has better versatility and scalability and can work more effectively in dealing with the issues of complex large-scale QoS-aware Web service composition optimization in the cross-organizational business process.

The rest of this paper is organized as follows.In Section 2,a review of the literature is provided.Section 3 describes the problem in a formalized way.Section 4 elaborates on the CGA approach.Section 5 reports and discusses results obtained in the simulations.Finally,Section 6 concludes this research and outlines our future work.

2 Related work

This paper introduces related work done by predecessors in the following two aspects:Web service composition and CGA.There are many available papers about Web service composition and CGA,but few of them deals with the particular requirements of constraints between services in the cross-organizational business process.

2.1 Web service composition

Most of the existing Web service composition methods do not consider a variety of political constraints and the standard system constraints that are common in the cross-organizational business process,and only a few have been exceptions.Reference [10]presents a correlation-aware manufacturing cloud service description model to describe the constraints between services and uses the GA for the correlation-aware optimal service selection.Reference [11]uses a two-stage approach to solve this problem:describes inter-service constraints in mathematical expressions and then employs integer programming to achieve dynamic Web service composition,which is efficient but not intended for large-scale Web service composition.Reference [12]views Web service composition as a multi-objective optimization model,in which the multi-objective GA is used to deal with inter-service constraints.Reference [13]uses the penalty function method to impose penalties on the infeasible individuals in the population that have violated the constraints,so that the next generation can eliminate infeasible individuals as soon as possible.Reference [14]uses domain knowledge to repair infeasible individuals to minimize the number of services that violate the constraints.Reference [15]views service composition as a multi-objective optimization model,and uses GA to deal with inter-service constraints.The penalty function method is also used to impose penalties on the individuals that violate the constraints between services.The similarity between individuals is also calculated to maintain population diversity.Reference [16]uses a local optimizer to improve the quality of individuals in the population.The knowledge-based crossover operator is used to deal with the individuals that violate the constraints between services.

2.2 Traditional CGA

There are some literatures combining GA with chaos theory.Different combining methods have different characteristics.Reference [17] optimizes the mutation operator of GA by using the chaos theory to determine the optimal allocation of resources.It improves the performance of resource allocation.Reference [18] uses the GA and the chaos theory in data hiding algorithm.Before the GA performs crossover operation,the chaotic map is used to select individuals with better performance,helping improve the performance of the GA.Reference [19] considers the spectrum and power allocation problem for device-to-device communication in underlaying cellular network,and proposes a heuristic CGA associated with four color theorems to solve this problem.Reference [20] focuses on the GA with chaotic crossover operator,which has more efficient computation in comparison with the traditional GA.Reference [21] proposes a novel method based on the manifold learning and CGA optimized kernel extreme learning machine for the application of face recognition.The evolved individual of the GA is used as the input of the COA to perform the quadratic optimization.Reference [22] uses logistic chaotic mapping model to simulate chaotic natural populations in GA populations to study whether there is an advantage over traditional GA with fixed-scale populations.It is found that chaotic population GA can obtain the optimal results faster than traditional GA.Reference [23] uses the chaos theory to improve the convergence of GA for Web service selection.Chaotic time series are adopted in crossover and mutation process phases instead of random ones.At present,few people apply the CGA to the domain of Web service composition.This paper uses CGA to solve the problem of Web service composition.

3 Problem formulation

The problem of QoS-aware Web service composition considering the constraints in cross-organizational business process can be modeled in a quintuple formCS= (T,S,C,D,QoS).

1)Task Set:T= (t1,t2,…,tn) is a collection of all tasks in the cross-organizational collaboration that make up a composite service.These tasks may belong to multiple organizations.tirepresents thei-th sub-task in the cross-organizational business process.nrepresents the number of tasks in the cross-organizational collaboration.Many literatures have researched how to decompose a composite service into sub-tasks.This paper assumes that the sub-tasks have been given.

2)Service Set:S= (s1,s2,…,sn) is a set of abstract services.Each sub-tasktiin the cross-organizational business process has an abstract service setsi= (si1,si2,…,sim).Each abstract service containsmconcrete services (candidate services) which have identical functionality and different QoS.

3) Service Conflict Set:C= (c1,c2,…,cl) represents the conflict relations between services.Each element in the collection is a business rule.A business rule system is a system in which the rules are separated logically and perhaps physically from the other parts[24].A constraint rule is a statement that expresses an unconditional circumstance that must be true or false[25].The following rule can be used to represent conflicts between services.

Ifservicemis selected in a service composition

Thenthe servicencannot be chosen as part of the composite service

The element in a service conflict set can be represented asci= {(m,n) | if servicemis selected,then servicencannot be chosen}.E.g., in Figure 1,the conflict relation can be represented asci= {(A,D) | if service A is selected,then service D cannot be selected}.

4)Service Dependency Set:D=(d1,d2,…,dr) represents the dependency relations between services.The following rule can be used to represent dependency relation between services.

Ifservicemis selected in a service composition

Thenthe servicenmust be chosen as the part of the composite service

The element in the service dependency set can be represented asdi= {(m,n) | if servicemis selected,then servicenmust be chosen}.E.g., in Figure 1,the dependency relation can be represented asdi= {(E,G) | if service E is selected,then service G must be selected}.Reference [26] proposes a mechanism that can be used to examine the internal conflict and dependency relations between Web services.In this paper,the constraints have been identified and considered as input of the problem.

5)QoS Constraint Set:QoS= (q1,q2,…,qk) represents the global QoS constraints.QoS attributes are divided into positive attributes (e.g.availability,reliability) and negative attributes (e.g.time,price).The former is proportional to QoS,and the latter grows in inverse proportion to QoS.

The problem of Web service composition considering the conflicts and dependencies between services can be described as how to select a concrete servicesijfrom an abstract service setsifor each sub-tasktiin the cross-organizational business process to form a composite service that meets the cross-organizational collaboration requirements,satisfies the QoS constraint setQoS,and does not violate the service conflict setCand service dependency setD.

4 CGA in this paper

The basic idea of the CGA algorithm proposed in this paper is as follows.Firstly,the chaos theory is used to generate the initial population,and the repair strategy is adopted in the initial population to deal with individuals that violate the constraints.Secondly,a new fitness function is designed to eliminate the infeasible individuals after selection,crossover,and mutation operations as soon as possible.Thirdly,a minor chaotic disturbance is imposed on individuals in the population after the evolution.Repeat the above steps until the algorithm reaches the maximum iteration time or the individual fitness is no longer improved,and then output the optimal individual.The process of CGA algorithm is as Algorithm 1.

Algorithm1CGA Algorithm

Inputcross-organizational collaboration business process,service setS,service conflict setC,service dependency setD,QoS constraint setQoS

Outputoptimal combination result

Step1Chaos initialization.

Step2If the population has infeasible initial individuals,repair strategy should be used.

Step3Calculating fitness function for all individuals in the population.

Step4Using single-point crossover operation and the random mutation strategy to realize population evolution.

Step5Calculating the fitness value of the individual in the population and sorting them.

Step6Some individuals with the smallest fitness value and the greatest fitness value are imposed with small-scale chaotic disturbance to realize individual chaos optimization.

Step7Convergence judgement.If the maximum number of iterations reached by the algorithm or the optimal individual fitness is no longer improved,the algorithm is stopped and the optimal solution is turned out;otherwise switch to Step 3.

4.1 Chaos initialization

The initial population of GA is generated at random,so individuals scatter unevenly,which causes repeated local optimization.The convergence speed of the algorithm is uncertain.Chaos is characterized by randomness and ergodicity,so it can be used for the global search.At the initialization stage of GA,based on the chaos theory,a better initial population that improves the efficiency of GA can be generated.This paper employs logistic mapping[27]to obtain the initial population.

(1)

whereβiis the chaotic variable andiis the sequence number of the chaotic variable,i=1,2,…,n.nis the number of tasks in the composite service.uis the sequence number of the individual,u=0,1,…,N-1.Nis the number of individuals in the population.λis an adjustment factor,usually set to 4.As shown in Figure 2,as theλvalue increases,the system grows into a chaotic state,and chaotic variables can be evenly distributed between 0 and 1[28].

Fig.2 Logistic mapping

TheNinitial chaotic individuals are mapped into the concrete service obtainingNinitial individuals according to

(2)

4.2 A strategy for repairing infeasible initial individuals

To speed up the convergence,as shown in Algorithm 2,a repair strategy is proposed to quickly repair the individuals that violate the constraints in the initial population.

Algorithm2Repairing Infeasible Initial Individuals

Inputmaximum number of iteration;initial population;service conflict setC;service dependency setD

Outputoptimized initial population

1.r=0

2.While (r

3.If (initial population has infeasible individuals)

4.randomly choose an individual from infeasible individuals

5.randomly choose a concrete service from the set of conflict or dependency in selected individual

6.The selected concrete service←other concrete service in the same abstract service set

7.End

8.Else

9.return optimized initial population

10.break

11.End

12.r++

13.End

In the initialization phase,we manage to eliminate infeasible individuals.If the initial population has infeasible individuals,we randomly choose an individual from those individuals that cause conflicts or dependencies,and a concrete service from the set of conflict or dependency.The selected concrete service is replaced by another concrete service in the same abstract service set.If there are still infeasible individuals in the initial population,the repairing process is continued.To avoid the endless repairing,a maximum iteration time can be set,and the iteration would stop when reaching the limit.

4.3 Fitness function

The fitness function can be used to measure the quality of individuals in the population,which supports the business execution of cross-organizational collaboration.In this paper,only the positive attributes are considered.To facilitate the comparison and analysis,all QoS attribute values are normalized in scale of 0 to 1[30].In cross-organizational collaboration,there is a variety of composite structures of each task but this paper only discusses the sequential structure,and other composite structures can be converted into the sequential structure by the method presented in Reference [31].

A new fitness function can be designed as

Q′(CS)=Q(CS)-μ×

(3)

(4)

(5)

(6)

During evolution,if there is few difference between the fitness of individuals in the population,the convergence speed of the algorithm becomes very slow.So,the fitness of individuals can be adjusted as[33]

(7)

4.4 Individual chaos optimization

In the current population,some individuals with the smallest fitness value and the greatest fitness value are given small-scale chaotic disturbance,which can escape from local optimum and induce the iteration times.Applying small-scale chaotic disturbance to the individuals with the smallest fitness value can reduce the iteration of the GA.Applying small-scale chaotic disturbance to the individuals with the greatest fitness value can help the GA jump out of local optimization.Using the individual that is given small-scale chaotic disturbance to replace the original individual can achieve the second optimization of population.The chaotic disturbance can be calculated as

(8)

(9)

5 Experiment

To verify the accuracy and efficiency for the proposed CGA,the CGA is compared with the correlation-aware GA (CAGA) in Reference [10],the penalty-based GA (PGA) proposed in Reference [11],and the repair GA (RGA) in Reference [14].

All experiments are carried out on an ASUS PC with Intel (R) Core TM i5-7200U,with 2.5 GHz processor and 8 GB RAM.They are run on Windows 10 and Java 7 using QWS real datasets[34].12 concrete services are selected.Two attributes of QoS,reliability and availability,are used (as shown in Table 1).

Table1Selectedconcreteservicesandtheirreliabilitiesandavailabilities

Concrete ServiceReliabilityAvailabilitys110.890.73s120.850.73s130.800.67s140.760.60s210.910.67s220.860.73s230.800.53s240.830.83s310.720.73s320.940.73s330.560.73s340.830.83

Suppose that the composite service consists of three abstract services (S1,S2,S3) with sequential structure.Each abstract service has four concrete services,such asS1= (s11,s12,s13,s14),S2= (s21,s22,s23,s24),S3= (s31,s32,s33,s34).The weight of reliability and availability are 0.5 and 0.5.The reliability’s global constraint is (0.7,1) and the availability’s global constraint is (0.8,1).Assume that servicess11ands23have the conflict relation and servicess12ands34have the dependency relation.Three algorithms have same crossover probability,mutation probability and population size.In the form of binary encoding,the algorithm terminates by reaching the maximum iteration times.The maximum number of iteration times is 30.Each experiment is conducted 30 times.

As shown in Table 2,the proposed CGA algorithm is compared with PGA,RGA,and CAGA in five aspects.They refer to the average optimal fitness,the average iterations required to reach the optimal fitness,the number of violation of conflicts,the number of violation of dependencies,and run time.The comparison of average value of each aspect is lacked statistically significant,so T-test is used to analyze whether there are significant differences between the three sets of data.The test results show that there is a significant difference between three sets of data.

Table 2 Comparison offour algorithms

5.1 Comparison of the optimal fitness

As shown in Figure 3,by using the CGA proposed in this paper,only 5 groups in 30 groups do not reach,yet not far off,the global optimal fitness.By using PGA,13 out of 30 groups do not achieve the global optimal fitness.The RGA has 13 groups that do not achieve the global optimal fitness.The CAGA also has 12 groups that do not achieve the global optimal fitness.The optimal fitnesses of PGA,RGA and CAGA are very different from the global optimal fitness.Table 2 shows that the average optimal fitness of CGA is better than that of RGA,PGA and CAGA.This is because the CGA algorithm uses chaos to avoid local optimal solution obtaining the global optimal solution.Thus,the quality of the solution is improved.

Fig.3 Comparison of the optimal fitness

5.2 Comparison of the iterations required to achieve optimal fitness

As shown in Figure 4,the number of iteration times required for CGA to achieve optimal fitness is mostly between 0 and 5 times.The iteration times of CAGA are ranging from 10 to 20,and these numbers for PGA and RGA are ranging from 20 to 30.Table 2 shows that the number of average iteration times required for CGA to achieve optimal fitness is about 4,much smaller than those of CAGA (14) and PGA and RGA (both 21).The reason is that the CGA algorithm uses the chaos theory for initialization to help reduce the number of iterations.Therefore,the CGA algorithm is more efficient.

Fig.4Comparisonoftheiterationsrequiredtoachieveoptimalfitness

5.3 Comparison of the number of individuals that violate the constraints between services

RGA has a repair strategy in each iteration so it does not produce infeasible individuals.By comparing CGA with PGA and CAGA,as shown in Figure 5,it can be seen that CGA produces fewer individuals that violate the conflict relations between services than that of the PGA and CAGA.The number of individuals that violate the dependency relations between services is also smaller than those of PGA and CAGA.From Table 2,it can also be seen that the CGA′s average number of violating conflict relations and the average number of violating dependency relations are about 12 and 0.067,much smaller than PGA and CAGA.In the CGA algorithm,if the initial population has infeasible individuals,then the repair strategy is used to eliminate them,so the CGA algorithm proposed in this paper violates fewer constraints.

Fig.5Comparisonofthenumberofindividualsthatviolatetheconstraintsbetweenservices

5.4 Comparison of run time

Table 2 shows that the average run time of CGA is 17.733 ms,longer than those of PGA and RGA but shorter than that of CAGA.As shown in Figure 6,the run time of CGA is ranging from 13 to 17 ms.The cause of this phenomenon is that the CGA has early chaos initialization and late chaotic disturbance.From Figure 6,it can be concluded that the difference is within the acceptable range.

Fig.6 Comparison of run time

6 Conclusion

How to realize QoS-aware Web service composition considering constraints in the cross-organizational business process is still an open issue.This paper analyzes the types of constraints between services in the cross-organizational business process,constructs a CGA by creatively integrating the chaos theory into GA,proposes a new method to repair infeasible initial individuals,and designs a new fitness function.The experimental results show that the proposed method has better performance.Still,more work is needed to shorten the run time of the CGA algorithm and repair infeasible individuals with more diverse strategies,which will be the focus of further studies.