Modeling And Optimization Methods Of Multi-objective Web Service Composition

With the extreme increase in the number of services released across the Internet and the various attributes of services,the problem of Web Service Composition in the field of service-oriented computing has been increasingly challenging.Effectively combining various services distributed over the Internet to build enterprise applications with comprehensive functionalities is the goal of web service composition.The various attributes of services require that web service composition method optimizes multiple objectives at the same time,which cannot be satisfied by Web Service Composition or QoS-aware Web Service Composition technologies.Consequently,more and more scholars begin to pay attention to Multi-objective Web Service Composition Problem.Most of the currently available methods have to explicitly build web service dependency graphs.However,building a large web service dependency graph may incur extreme inefficiency problem.Moreover,a common problem is that there are some redundant services in the composition results of many researches.The problem of redundant services not only leads to the extra overhead for users but also makes it more difficult to manage and maintain web services.To address these issues,this paper aims at modeling and optimization technologies of Multi-objective Web Service Composition,and the redundant service removal mechanism.The main contributions are:Firstly,we propose a Mixed Integer Linear Programming(MILP)model for the inefficiency problem arising from building service dependency graphs.In this paper,we formalize the Multi-objective Web Service Composition Problem as a novel MILP model with no need to build a web service dependency graph.In the MILP model,various objectives are combined with different weights to obtain a single objective.Then we add some constraints to the MILP model according to the functional and nonfunctional attributes of services,which ensure a feasible solution of the MILP model can be transformed into a valid composition of the original problem.Moreover,some effective technologies are given to solve the MILP model approximately.The results of experiments show that the MILP model with approximate technologies can be solved very fast by applying a standard solver,and the solutions output by the solver are closed to the solutions other methods produce.Secondly,the composition result of the MILP model is not at an advantage in QoS objectives compared with current works,for which a composition-segment candidates optimization method is proposed to solve this problem.By generating much various composition-segment candidates,these candidates can be used to optimize the score segment candidate obtaining an ideal composition result.Compared with current technologies,this method not only runs sharply fast but also achieves much a better tradeoff between QoS attributes and the number of services than others.Moreover,it shows outstanding efficiency while applied in large-scale scenarios.Finally,we propose a redundancy removal mechanism for Multi-objective Web Service Composition due to redundant services in the target composition.We design an algorithm building service composition graph to construct an efficient data structure,and then propose a reverse redundancy detecting algorithm and a recursive redundancy removal algorithm.The detecting algorithm and the removal algorithm take full advantage of the elaborate data structure,which avoids rebuilding a service composition graph.The experimental results show that the mechanism can remove redundant services efficiently without affecting each QoS attribute.