HUO Yingand ZHANG Jiande

School of Computer Engineering,Nanjing Institute of Technology,Nanjing 211167,China

Abstract:The concept of service composition can provide the complex functionality for users.As the widespread application of cloud computing,the number of services grows exponentially.It becomes more difficult to find out the optimal service composition solution quickly.This paper proposes a nonlinear service composition method based on the Skyline operator.The Skyline operator is to find a collection of data that cannot be dominated by others,which is used to prune the redundant services to reduce the search space.Then the service composition problem is formulated as a nonlinear integer programming model by a mathematical programming language(AMPL),and solved by the existing nonlinear solvers Bonmin.The experiments show that the proposed method can effectively improve the efficiency of service composition,while ensuring the quality of solution.

Key words:quality of service,service composition,Skyline service,branch-and-bound Skyline.

1.Introduction

The concept of service oriented architecture(SOA)solves the problem of cross-platform resource sharing.In order to ensure the modularity and reusability,the functionality of individual services is often limited,thus they need to be composited to satisfy the complex demand of users.The widespread application of cloud computing promotes the development of SOA.As the number of services grows exponentially,the massive services with similar functionality present new challenges to the effectiveness and efficiency of the existing service composition methods.It has been a research focus to find out a service composition solution as quickly as possible,which has the best properties and also satisfies all the functional requirements[1,2].

The existing service composition methods include the local selection,the global optimization,the intelligent optimization,and the exhaustive method.The local selection method can only obtain a local optimization solution,but its efficiency is high.The global optimization method transforms the global service composition problem into the mixed integer linear programming problem,and it can get the solution with high quality in a relatively short time,but it requires all the objective functions and constraints to be linearized,which limits the application to a certain extent.Although the intelligent optimization method also has a high efficiency,it can only obtain the approximate optimal solution because of its randomness.Moreover,the exhaustive method can obtain the optimal solution certainly,but its time complexity is too high to be practical.

The surge of candidate services is the most important factor to reduce the efficiency of service composition[3].If we can select the potential services in advance,the search space can be reduced and the efficiency will be improved effectively.The concept of Skyline[4] first appeared in the field of data engineering,which is a collection of data that cannot be dominated by others.Based on this,we can select the non-dominated services from each service group,then just composite them to improve the efficiency.

The remainder of this paper is organized as follows.In Section 2,the related work is discussed.Section 3 gives the definition of the Skyline service and analyzes the calculation method.The service composition problem is modeled as a nonlinear integer programming problem in Section 4,and be solved by basic open-source nonlinear mixed integer programming(Bonmin).Experiments to validate the proposed model are presented in Section 5.Finally,Section 6 gives our conclusion.

2.Related work

2.1Service composition

Service composition is selecting the appropriate service components in each service group,then compositing them to satisfy the relevant constraints and make the service quality optimal.Currently,there are four existing service composition methods.

(i)Exhaustive method. Traversing all the composite service solutions,and find out the one with the maximal quality of service(QoS).This can obtain the optimal solution certainly,but its time complexity is too high to be practical.

(ii)Local selection method.Different QoS attribute values are mapped into a certain value,and the multiple criteria decision-making(MCDM)process is used to select the appropriate service from each group[5].It can only obtain a local optimization solution, whereas its efficiency is quite high.

(iii)Global optimization method.It transforms the global QoS service composition problem into the mixed integer linear programming problem,then be solved by the linear solvers,such as CPLEX[6,7]or IPSOLVE[5].It can get the solution with high quality in a relatively short time,but it requires all the objective functions and constraints to be linearized,which limits the application of this method to a certain extent.

(iv)Intelligent optimization method.It also can be called the global optimization method.The difference is that the problem is nonlinear and is solved by the intelligent optimization algorithms,such as genetic algorithm(GA)[8],particle swarm optimization(PSO)algorithm[9],ant colony optimization(ACO)algorithm[10],artificial bee colony(ABC)algorithm[11,12],and so on.Although the intelligent optimization method also has a high efficiency,it can only obtain the approximate optimal solution because of its randomness.

In some applications,the absolute optimal service composition solution needs to be obtained in a short period of time,and the model is complex and cannot be linearized.Therefore,this paper formulates the problem as a nonlinear integer programming model,and solves the problem by the existing nonlinear solvers.

2.2Skyline operator

Skyline is a collection of data that cannot be dominated by others[4].Some algorithms have been proposed to compute the Skyline set,like the branch and bound Skyline(BBS)algorithm[13].BBS is simple to implement and can be efficiently applied to a variety of alternative Skyline queries.

In the service composition problem,although all services in each service group are candidate services,not all of them are potential candidates for the optimal solution.Based on the notion of Skyline,Alrifai proposed a new service composition method[14].The Skyline operator is attached into the process of service composition,to filter out candidate services that cannot dominated by others in each service group,which can reduce search space and improve the efficiency.Yu presented a new concept,called p-dominant service Skyline,to deal with the uncertainty of the QoS[15].A p-R-tree indexing structure and a dualpruning scheme are presented to efficiently compute the pdominant Skyline.For the cloud-base web services,a fast service composition approach based on the Skyline operator and PSO is proposed,which is the combination of Skyline and the intelligent algorithm[16].For the large scale services with high-dimensional QoS attributes,Moradi applied the parallelism technique into the Skyline computing,to increase the speed of service composition[17].For building up cloud mashup applications, Zhang proposed an integrated Skyline query processing method,using a similarity test to achieve optimal localized Skyline[18].Guo proposed a service selection approach based on QoS prediction[19],the Skyline is also applied to prune redundant services and perform Skyline service selection using 0-1 mixed-integer programming.

According to the existing research work, the Skyline operator is widely used to prune the redundant services and improve the efficiency of the service composition.In this paper,the Skyline operator and the efficient algorithm BBS are used to compute the Skyline service set.

3.Service composition based on Skyline operator

3.1Definition of Skyline service

Alrifai gave the definition of Skyline service[14].Consider a service groupSiincludesnicandidate servicesSi={wsi,1,wsi,2,...,wsi,ni},and each candidate service considersrQoS attributesq(wsi,j)={q1,q2,...,qr}.In this paper,we suppose each attribute value preference for smaller values.We define the service dominance and Skyline services as follows.

Definition 1Service dominance

Ifwsi,jis as good as or better thanwsi,kin all parameters of attributes and better in at least one attribute,i.e.,?l∈[1,r],wsi,j(ql)?wsi,k(ql)and?l∈[1,r],wsi,j(ql)

Definition 2Skyline services

In the service groupSi={wsi,1,wsi,2,...,wsi,ni},the collection of all the candidate services that cannot be dominated by any other service is the Skyline services set,denoted bySkySi,i.e.,SkySi={wsi,j∈Si|??wsi,k∈Si:wsi,k?wsi,j}.

An example of reservation services is given below.In this case,the reservation service groupSiconsists of nine candidate serviceswsi,1towsi,9,such as booking,ctrip,agoda,hotelclub,and so on.Each candidate service considers two QoS attributes,the price and the response time.The price is the booking fee,ranging from 0 to$10.And the response time is the time for feedback after the service request be sent,ranging from 0 to 10 s.The QoS information for all candidate services is identified in a twodimensional space,as shown in Fig.1.

Fig.1Example of Skyline services in the reservation service group

As shown in Fig.1,because of 2=2 and 8<10,thenwsi,2?wsi,1.Besides,2<4 but 8>6,thus there is no domination relationship betweenwsi,2andwsi,4.In addition,there are no other services having a lower price and a shorter response time thanwsi,2,thuswsi,2∈SkySi.In the same way,the Skyline service set can be obtained as{wsi,2,wsi,4,wsi,6,wsi,8}.

In the calculation of the Skyline service of each service group,each QoS attribute of every candidate service needs to be compared.When there are a large number of candidate services,this calculation will cost too much time.

3.2Calculation of Skyline service

3.2.1Non-dominate algorithm

Non-dominate is a method of judging the domination of the solutions in the multi-objective optimization problem.The quality of solutions is evaluated by non-dominate sorting,to provide a reference for evolution and selection[20].We improve it and design the non-dominate algorithm for solving the Skyline set,as shown Algorithm 1.

Algorithm 1Non-dominate algorithm for solving the Skyline set

Input:MatrixA(It represents the QoS value of the whole services in a group,which has|Ncandidate|rows and|ATTRIBUTE|columns.|Ncandidate|indicates the number of the candidate services in the group.|ATTRIBUTE|represents the number of attributes considered for each service.)

Output:The Skyline service setSkyof this group

In the non-dominate algorithm,all the candidate services need to be traversed twice,and all the attributes need to be compared,thus its time complexity isO(|Ncandidate|2·|ATTRIBUTE|).

3.2.2BBS algorithm

The general procedure of the BBS algorithm is as follows.First,the R tree[21]is constructed,which is a balance tree with two types of nodes:the leaf node and the non-leaf node.Based on space segmentation,the minimum bounding rectangle(MBR)is used to divide the space from the leaf node to the rectangle.And the concept of node capacity is presented to represent the largest number of submatrix or points included in each matrix in the R tree.Let the node capacity be 3.The R tree of Fig.1 can be constructed as Fig.2.

Definition 3Minimum distanceMindist

Every node of the R tree can be a matrix or a point.For each node,Mindistof every point is equal to the sum of its attributes value.AndMindistof an MBR equalsMindistof the point in the lower left.

Fig.2Construction of R tree

The root node of the R tree is inserted into the heap.After computing theMindistof every node,the node with the minimumMindistwould be selected from heap,and judge whether it is dominated.If non-dominated,it expands all its sub MBR and inserts them into the heap one by one.If the selected node does not contain sub MBR and cannot be dominated by any other node inSkyR,it can be added into the Skyline setSkyR.

As for Fig.2,the elementandin the root node would be inserted into the heap first.Then based onMindist,e6should be shifted out first.Expande6since it is an MBR,and its child nodes,,would be added into the heap and be sorted.After that,the elemente3withMindistalso should be expanded and sorted.Now the element withMindistwould bewsi,4,which does not need to expand since it is a point,and it can be added intoSkyRsinceSkyRis empty now.At the next step,e2is expanded.Its child nodewsi,6is not dominated bywsi,4and has been added intoSkyR,whereaswsi,3is discarded since it is dominated bywsi,4.Similarly,e4,e5,e1would be expanded.Finally theSkyRis{wsi,2,wsi,4,wsi,6,wsi,8}.

Though the quick method of Skyline has been applied, it still costs time.Because service composition and the Skyline calculation are independent with each other,the calculation of Skyline can be completed in a off-line way.

When the service list updates,only the Skyline set in the corresponding service group needs to be recomputed.In addition,Skyline services reflect the tradeoff between the different QoS attributes and can satisfy the diverse QoS requirements of the users.

4.Nonlinear integer programming modeling

4.1A mathematical programming language(AMPL)modeling

In this section,we formulate the service composition problem as a nonlinear integer programming problem by AMPL.AMPL is a kind of modeling language to describe and solve and solve complex mathematical problems.Its main characteristic is to use simple mathematical expressions to describe the optimization problem,and solve the problem through the existing solvers[22].Now AMPL supports many popular solvers, such as CPLEX, Bonmin, and so on.

4.1.1Definition of set

In AMPL,Ncandidate indicates the number of the total services.And these services are divided intoNclass service groups.For each service,the QoS model is used to evaluate its quality.The quality attributes considered in this paper are response time,availability,throughput,price and reputation.

The service is evaluated according to these attributes from different aspects.The original information of evaluation can be obtained directly from the service provider such as price,or be derived from the users feedback such as reputation,or be calculated from the historical records such as response time,availability and throughput.

4.1.2Definition of parameters

The parameter matrixQOSis defined to describe the evaluation value of service,whereQOSi,jrepresents the evaluation value of theith candidate service at thejth attribute.

For each attribute,there are three parameters:Weight,Com status and Posi status,where Weight represents the different importance of each attribute,which can be set beforehand by users according to their preference.The sum of the weight of all attributes should be 1,i.e.,

When composing the services,the composite quality of each attribute can be aggregated by the attribute value of each service.According to the difference of attributes,there are four types of aggregation operations:AVERAGE,MIN,SUM and PRODUCT.In the AMPL model,the parameter Com status is defined to identify the composition state of each attribute.The meaning is shown in Table 1.

Table 1QoS attribute aggregation

In the normalization phase,the service attributes can be classified as positive and negative by their semantic meanings.The higher the value is,the better the quality of positive attributes is,such as availability,throughput and reputation.For negative attributes,the lower the value is,the better the quality is,such as the response time and the price.They should be handled separately when being normalized.In this paper,the parameter Posi status is defined as an attribute notation.When Posi statusj=1,thejth attribute is a positive attribute,while Posi statusj=?1 means it is negative.

4.1.3Definition of objective function and variables

The goal of the service composition is to find a solution to maximizing the QoS of the composite service ComSAW.Therefore,the objective function is as follows:

where Weightjrepresents the importance of each attribute,UniComScorejis the aggregation value of each attribute after being normalized,which is computed based on Posi status,the equation is as follows:

where MAXj(MINj)represents the maximum(minimum)value of thejthat tribute for all composition paths.If they are equal,i.e.,MAXj=MINj,then the normalized value is 1.ComScorejis the aggregation value of thejth attribute of the composite service,which is calculated by different aggregation operations according to Com status.The equation is as follows:

In(3),ComServicei,jis a matrix of|Nclass|rows and|ATTRIBUTE|columns,to store theQOSinformation of the selected composition path.Let|Ncandidate|dimension vectorusedescribe whether the service is selected,whenusej=1,thejth service is selected in the composite path,whileusej=0 is not.The selected composite path ComService can be obtained by multiplying the matrixQOSbyuse.

4.2Model solving

After the model is defined,it can be solved by the existing solvers.We choose the nonlinear integer programming solver Bonmin[22]to solve the problem.

5.Experiments

In this section,we verify the effectiveness of the proposed model and method through the experiments.The experimental environment is as follows:Intel Core i5-4590(3.3 GHz),4 GB RAM,Windows 7(32 bit)and MATLAB R2010b.

5.1Comparison of model

In order to verify the model proposed in this paper,we compare it with the existing methods described in Section 2.1,exhaustive,local,discrete gbest-guided artificial bee colony algorithm(DGABC),and Bonmin.DGABC is a kind of the intelligent optimization method proposed in our previous work[11].The colony size is 20 and the iterations number is 1 000.And the Bonmin method is proposed in this paper.

The experiments in this section are conducted on the Random dataset.Each service has five attributes and the values are randomly generated assuming a uniform distribution in the interval[0,1].Let|Nclass|be 5,and the number of candidate services in each service group|Ncandidate|/|Nclass|increases from 5 to 60.The weight of each attribute is equal to 0.2.The results of ComSAW based on the above model are shown in Fig.3.The exhaustive method only calculates the case of|Ncandidate|/|Nclass|=5,10,15 because the time complexity is too high.

Fig.3Comparison of ComSAW

As shown in Fig.3,the solution obtained by the local method is the worst.Because the local optimal service in each group cannot guarantee that the composite solution is the best.Although only three cases are calculated,the Bonmin method can obtain the same optimal solution as the exhaustive method.The DGABC method can obtain the optimal solution in most cases except two.The computation time of these methods is shown in Table 2.

Table 2Comparison of computation time s

As shown in Table 2,the time complexity of the exhaustive methodis too high to be practical.While that of the local method is the best,but its ComSAW is the worst.The computation time of DGABC is controlled by the number of iterations,thus it always stays around 0.55 s because of the same iterations.The Bonmin method proposed in this paper can obtain the optimal solution as the exhaustive method in the limited time,thus can be effectively applied in the service composition.

5.2Comparison of Skyline calculation

The following experiments are conducted to analyze the two Skyline calculation methods described in Section 3 from the effectiveness and efficiency aspects.

For more real data of QoS,the quality of web service(QWS)dataset is used in this section,which was collected by Eyhab Al-Masri[23–25].2507 real Web services are included and each one considers nine quality attributes.

5.2.1Skyline filtering service

As shown in Table 3,the remaining services increase as the considering attributes increase.The reason is that the dominance relation becomes less apparent as the attributes increase.Usually,five attributes would be considered in the service composition.

Table 3Skyline filtering service on different numbers of attributes

In addition,we analyze the Skyline filtering when the candidate services increase.The number of attributes is 5,and the candidate services increase from 250 to 2 500.The remaining number of services after filtering is shown in Table 4.

Table 4Skyline filtering service as the number of services increases

As shown in Table 4,there is a little growth of the number after filtering as the candidate services increase.Therefore,when the number of QoS attributes is determined,even if there are a huge number of candidate services,the Skyline set would not be too large after filtering.

5.2.2 Efficiency comparison of different Skyline methods

In this section,we analyze the efficiency of the two different Skyline methods.The calculation time is shown in Fig.4,where BBS Node represents the node capacity of the R tree,and we carry out the experiments respectively when BBS Node is 3 and 4.In addition,because the R tree can be constructed offline,the time of constructing the tree is not included.

Fig.4Calculation time with the number of QoS attributes

As shown in Fig.4,the computation time increases with the increase of the QoS attributes.When the number of QoS attributes is less than 6,the computation time can be within 0.3 s.However,when the QoS attributes are more that six,the BBS method performs worse because the performance of the R tree decreases in the high dimensional space.In contrast, the calculation time of the non-dominate method is stable,and its average time is around 2.6 s,but is worse than the BBS method.

Let the number of QoS attributes be 5,the number of candidate services increases from 250 to 2 500,and the step size is 250.The computation time is shown in Fig.5.

As shown in Fig.5,with the increase of the candidate services,the computation time of the BBS method is stable,while that of the non-dominate method increases significantly.It is because the time complexity of the nondominate method isO(|Ncandidate|2·|ATTRIBUTE|),thus there is an exponential growth of the running time with the increase of|Ncandidate|.

Fig.5Calculation time with the number of candidate services

Therefore,the Skyline computing methods can be selected flexibly.When the number of QoS attributes is over 9,we can choose the non-dominate method to get a higher efficiency.When there are a huge number of candidate services,the BBS algorithm can calculate the Skyline set more quickly.

5.3Comparison of service composition based on Skyline

The Bonmin method is used to calculate the original services set and the filtered Skyline set separately,and the computation time is shown in Fig.6.

Fig.6 Bonmin method on the original set and the Skyline set

As shown in Fig.6,when the number of candidate services in a group is less than 40,the efficiency of the two methods is close.However,when it is over 40,the time of the Skyline operator can decrease by at least 3/4.Therefore,the Bonmin method base on Skyline can effectively improve the efficiency of service composition,while ensuring the quality of solution.

6.Conclusions

With the development of cloud computing,the number of services is exponentially increasing,which brings new challenges for the existing service composition technology..In order to find out a service composition solution satisfying all the functional requirements as quickly as possible,this paper proposes a nonlinear service composition method based on the Skyline operator.The dominated services in each service group would be filtered out by Skyline,which can reduce the search space and improve the efficiency effectively.Then the service composition problem is formulated as a nonlinear integer programming problem by AMPL,and solved by Bonmin.The experimental results show that the proposed method can obtain the optimal solution similar to the exhaustive algorithm,and the efficiency is also excellent.Therefore,the service composition method based on Skyline can significantly improve the efficiency of service composition.

In the future work,we will conduct the service composition in the parallel architecture to further improve the efficiency.