Comprehensive quality-aware automated semantic web service composition is an NP-hard problem, where service composition workflows are unknown, and comprehensive quality, i.e., Quality of services (QoS) and Quality of semantic matchmaking (QoSM) are simultaneously optimized. The objective of this problem is to find a solution with optimized or near-optimized overall QoS and QoSM within polynomial time over a service request. In this paper, we proposed novel memetic EDA-based approaches to tackle this problem. The proposed method investigates the effectiveness of several neighborhood structures of composite services by proposing domain-dependent local search operators. Apart from that, a joint strategy of the local search procedure is proposed to integrate with a modified EDA to reduce the overall computation time of our memetic approach. To better demonstrate the effectiveness and scalability of our approach, we create a more challenging, augmented version of the service composition benchmark based on WSC-08 bansal2008wsc and WSC-09 kona2009wsc . Experimental results on this benchmark show that one of our proposed memetic EDA-based approach (i.e., MEEDA-LOP) significantly outperforms existing state-of-the-art algorithms.
Automated web service composition aims to loosely couple web services to fulfill a service request, without strictly obeying a pre-given abstract workflow. Instead, composition workflows are gradually built up while its component services are selected. Existing works in fully automated web service composition can be categorized into two approaches --- direct approaches and indirect approaches @cite_37 . The direct approaches represent composition solutions explicitly in the representation that displays actual execution flows of composite services, while the indirect approaches often represent composite services implicitly as permutations, which require a decoding process to build up actual execution workflows.
@cite_37
2605603844
Web services have become increasingly popular in recent years, and they are especially suitable to the process of Web service composition, which is when several services are combined to create an application that accomplishes a more complex task. In recent years, significant research efforts have been made on developing approaches for performing Quality of Service -aware Web service composition. Evolutionary computing (EC) techniques have been widely used for solving this problem, since they allow for the quality of compositions to be optimised, meanwhile also ensuring that the solutions produced have the required functionality. Existing EC-based composition approaches perform constrained optimisation to produce solutions that meet those requirements, however these constraints may hinder the effectiveness of the search. To address this issue, a novel framework based on an indirect representation is proposed in this work. The core idea is to first generate candidate service compositions encoded as sequences of services. Then, a decoding scheme is developed to transform any sequence of services into a corresponding feasible service composition. Given a service sequence, the decoding scheme builds the workflow from scratch by iteratively adding the services to proper positions of the workflow in the order of the sequence. This is beneficial because it allows the optimisation to be carried out in an unconstrained way, later enforcing functionality constraints during the decoding process. A number of encoding methods and corresponding search operators, including the PSO, GA, and GP-based methods, are proposed and tested, with results showing that the quality of the solutions produced by the proposed indirect approach is higher than that of a baseline direct representation-based approach for twelve out of the thirteen datasets considered. In particular, the method using the variable-length sequence representation has the most efficient execution time, while the fixed-length sequence produces the highest quality solutions. Automated Web service composition, which refers to the creation of a complex application from pre-existing building blocks (Web services), has been an active research topic in the past years. The advantage of having an automated composition system is that it allows users to create new applications simply by providing the required parameters, instead of having to manually assemble the services. Existing approaches to automated composition rely on planning techniques or evolutionary computing (EC) to modify and optimise composition solutions directly in their tree graph form, a complex process that requires several constraints to be considered before each alteration. To improve the search efficiency and simplify the checking of constraints, this work proposes an indirect Particle Swarm Optimisation (PSO)-based approach. The key idea of the indirect approach is to optimise a service queue which is then decoded into a composition solution by using a planning algorithm. This approach is compared to a previously proposed graph-based direct representation method, and experiment results show that the indirect representation can lead to a greater (or equivalent) quality while requiring a lower execution time. The analysis conducted shows that this is due to the design of the algorithms used for building and evaluating the fitness of solutions. Run-time service discovery and late-binding constitute some of the most challenging issues of service-oriented software engineering. For late-binding to be effective in the case of composite services, a QoS-aware composition mechanism is needed. This means determining the set of services that, once composed, not only will perform the required functionality, but also will best contribute to achieve the level of QoS promised in service level agreements (SLAs). However, QoS-aware composition relies on estimated QoS values and workflow execution paths previously obtained using a monitoring mechanism. At run-time, the actual QoS values may deviate from the estimations, or the execution path may not be the one foreseen. These changes could increase the risk of breaking SLAs and obtaining a poor QoS. Such a risk could be avoided by replanning the service bindings of the workflow slice still to be executed. This paper proposes an approach to trigger and perform composite service replanning during execution. An evaluation has been performed simulating execution and replanning on a set of composite service workflows. Web service orchestrations-expressed in the Web service business process execution language (WS-BPEL or BPEL for short)-are a manifestation of the two-level-programming paradigm where services, i.e. the business functions used by the composite application, are composed through BPEL's control flow constructs. BPEL processes Web service orchestrations, business functions therefore can be transparently accessed remotely, allowing to build composite applications that integrate business functions provided by different partners on different locations. As of today, execution of BPEL processes, i.e. the evaluation of the processes' control flow, is performed by a central workflow engine. In certain scenarios, such as complex collaborative cross-partner interactions, this approach of centralized workflow enactment leads to "un-natural" process models; process models that are not driven by the processes' original business goal but by infrastructural or organizational reasons. In this paper, we propose an alternative approach to enacting BPEL process control flow in a distributed, decentralized manner. We present the overall process lifecycle and give a detailed description of the underlying process model. Service-Oriented Computing (SOC) enables the composition of loosely coupled services provided with varying Quality of Service (QoS) levels. Selecting a (near-)optimal set of services for a composition in terms of QoS is crucial when many functionally equivalent services are available. With the advent of Cloud Computing, both the number of such services and their distribution across the network are rising rapidly, increasing the impact of the network on the QoS of such compositions. Despite this, current approaches do not differentiate between the QoS of services themselves and the QoS of the network. Therefore, the computed latency differs substantially from the actual latency, resulting in suboptimal QoS for service compositions in the cloud. Thus, we propose a network-aware approach that handles the QoS of services and the QoS of the network independently. First, we build a network model in order to estimate the network latency between arbitrary services and potential users. Our selection algorithm then leverages this model to find compositions that will result in a low latency given an employed execution policy. In our evaluation, we show that our approach efficiently computes compositions with much lower latency than current approaches. In recent times, automated business processes and web services have become ubiquitous in diverse application spaces. Efficient composition of web services in real time while providing necessary QoS guarantees is a computationally complex problem and several heuristic based approaches have been proposed to compose services optimally. In this paper, we present the design of a scalable but approximate QoS-aware service composition mechanism which balances the computational complexity of service composition with the QoS guarantees of the composed service and achieves scalability for dynamic service composition. We present experimental results to show the efficiency of our proposed mechanism. Service Oriented Architectures and web service technology are becoming popular in recent years. As more web services can be used over the Internet, the need to find efficient algorithms for web services composition that can deal with large amounts of services becomes important. These algorithms must deal with different issues like performance, semantics or user restrictions. In this paper we present an A* algorithm which solves the problem of semantic input-output message structure matching for web service composition. Given are quest, a service dependency graph with a subset of the original services from an external repository is dynamically generated. Then, the A*search algorithm is used to find a minimal composition that satisfies the user request. Moreover, in order to improve the performance, a set of dynamic optimization techniques has been implemented over the search process. A full experimental validation with eight different public repositories has been done showing a good performance as in all tests as the algorithm finds a valid solution with minimal number of services and execution path. Web service composition has been a prevailing research direction in recent years. There are two major challenges faced by researchers, semantic matchmaking and Quality of Service (QoS) optimisation. Semantic matchmaking aims to discover interoperable web services that can interact with each other by their resources described semantically. QoS optimisation aims to optimise the non-functional requirements of service users, such as minimum cost and maximum reliability. To meet the requirements of service users, both semantic matchmaking quality and QoS should be considered simultaneously. Most existing works on web service composition, however, focus only on one of these two aspects. Therefore, we propose a comprehensive quality model that takes both semantic matchmaking quality and QoS into account with the aim of achieving a more desirable balance of both sides. Further, we develop a PSO-based service composition approach with explicit support for the proposed comprehensive quality model. We also conduct experiments to explore the effectiveness of our PSO-based approach and the desirable balance achieved by using our comprehensive quality model. Interoperability and loose coupling requirements are pushing the next generation of distributed applications towards more decentralized and more dynamic interaction schemes, which the classic request response communication paradigm can hardly accommodate. Hence, sound foundations and mechanisms for the establishment of unanticipated peer-to-peer interactions across organizational boundaries are of significant importance to upcoming middleware platforms. The executable choreography framework (ECF) is a middleware-level framework that targets dynamic and decentralized service compositions. The ECF combines transparent context propagation with aspect-oriented software composition techniques to dynamically refine the default control and data flow of service invocations. The framework provides a ground for experimentation with dynamic and distributed workflows, and a base to assess their safety and applicability when deployed across organizational boundaries. Composite Web services (WS) can be seen as software systems designed according to workflow-based orchestration of building blocks or simpler WS. Each block has its own specifications concerning both functional and non-functional properties. While the characteristics of each block have a scope limited to its domain, the WS must guarantee service levels that are usually described by global end-to-end metrics. The problem of relating local to global objectives in WS orchestration is hard to approach. In this context, some WS components have to be deployed in distributed service oriented infrastructure mixing heterogeneous systems belonging to private and or public providers. In this paper we propose a performance-driven technique for designing and deploying composite WS on heterogeneous service oriented infrastructure. Users having different requirements in terms of resource demands and performance objectives are considered. Several WS deployment alternatives, involving both physical and virtual resources provided by the infrastructure, are evaluated to identify the logical (workflow) and physical (deployment) configuration allowing to meet the requirements. In order to demonstrate the suitability of the proposed approach to the service oriented context, an example of a travel management WS is described and the optimal deployment of the components in a hybrid infrastructure is investigated. The paradigmatic shift from a Web of manual interactions to a Web of programmatic interactions driven by Web services is creating unprecedented opportunities for the formation of online business-to-business (B2B) collaborations. In particular, the creation of value-added services by composition of existing ones is gaining a significant momentum. Since many available Web services provide overlapping or identical functionality, albeit with different quality of service (QoS), a choice needs to be made to determine which services are to participate in a given composite service. This paper presents a middleware platform which addresses the issue of selecting Web services for the purpose of their composition in a way that maximizes user satisfaction expressed as utility functions over QoS attributes, while satisfying the constraints set by the user and by the structure of the composite service. Two selection approaches are described and compared: one based on local (task-level) selection of services and the other based on global allocation of tasks to services using integer programming. Web service composition has become a promising technique to build powerful business applications by making use of distributed services with different functions. Due to the explosion in the volume of data, providing efficient approaches to composing data intensive services will become more and more important in the field of service-oriented computing. Meanwhile, as numerous web services have been emerging to offer identical or similar functionality, web service composition is usually performed with end-to-end Quality of Service QoS properties which are adopted to describe the non-functional properties e.g., response time, execution cost, reliability, etc. of a web service. In this paper, a hybrid approach that integrates the use of genetic programming and tabu search to QoS-aware data intensive service composition is proposed. The performance of the proposed approach is evaluated using the publicly available benchmark datasets. A full set of experimental results show that a significant improvement of our approach over that obtained by the simple genetic programming method and several traditional optimization methods, has been achieved. Web service composition enables seamless and dynamic integration of business applications on the web. The performance of the composed application is determined by the performance of the involved web services. Therefore, non-functional, quality of service aspects are crucial for selecting the web services to take part in the composition. Identifying the best candidate web services from a set of functionally-equivalent services is a multi-criteria decision making problem. The selected services should optimize the overall QoS of the composed application, while satisfying all the constraints specified by the client on individual QoS parameters. In this paper, we propose an approach based on the notion of skyline to effectively and efficiently select services for composition, reducing the number of candidate services to be considered. We also discuss how a provider can improve its service to become more competitive and increase its potential of being included in composite applications. We evaluate our approach experimentally using both real and synthetically generated datasets. Web services make information and software available programmatically via the Internet and may be used as building blocks for applications. A composite web service is one that is built using multiple component web services and is typically specified using a language such as BPEL4WS or WSIPL. Once its specification has been developed, the composite service may be orchestrated either in a centralized or in a decentralized fashion. Decentralized orchestration offers performance improvements in terms of increased throughput and scalability and lower response time. However, decentralized orchestration also brings additional complexity to the system in terms of error recovery and fault handling. Further, incorrect design of a decentralized system can lead to potential deadlock or non-optimal usage of system resources. This paper investigates build time and runtime issues related to decentralized orchestration of composite web services. We support our design decisions with performance results obtained on a decentralized setup using BPEL4WS to describe the composite web services and BPWS4J as the underlying runtime environment to orchestrate them. Services in cloud computing can be categorized into two groups: Application services and Utility Computing Services. Compositions in the application level are similar to the Web service compositions in SOC (Service-Oriented Computing). Compositions in the utility level are similar to the task matching and scheduling in grid computing. Contributions of this paper include: 1) An extensible QoS model is proposed to calculate the QoS values of services in cloud computing. 2) A genetic-algorithm-based approach is proposed to compose services in cloud computing. 3) A comparison is presented between the proposed approach and other algorithms, i.e., exhaustive search algorithms and random selection algorithms. Optimizating semantic web service compositions is known to be NP-hard, so most approaches restrict the number of services and offer poor scalability. We address the scalability issue by selecting compositions which satisfy a set of constraints rather than attempting to produce an optimal composition. Firstly, we define constraints within an innovative and extensible quality model designed to balance semantic fit (or functional quality) with quality of service (QoS) metrics. The semantic fit criterion evaluates the quality of semantic links between the semantic description of Web services parameters, whilst QoS focuses on non-functional criteria of services. Coupling these criteria allows us to further constrain and select valid compositions. To allow the use of this model in the context of millions of services as foreseen by the strategic EC-funded project SOA4All, we i) formulate the selection problem as a Constraint Satisfaction Problem and ii) test the use of a stochastic search method. Finally we compare the latter with state-of-the-art approaches. The increasing availability of web services necessitates efficient discovery and execution framework. The use of xml at various levels of web services standards poses challenges to the above process. OWL-S is a service ontology and language, whose semantics are based on OWL. The semantics provided by OWL support greater automation of service selection, invocation, translation of message content between heterogeneous services, and service composition. The development and consumption of an OWL-S based web service is time consuming and error prone. OWL-S IDE assists developers in the semantic web service development, deployment and consumption processes. In order to achieve this the OWL-S IDE uses and extends existing web service tools. In this paper we will look in detail at the support for discovery for semantic web services. We also present the matching schemes, the implementation and the results of performance evaluation. This paper describes how to generate compositions of semantic Web services using social trust information from user ratings of the services. We present a taxonomy of features, such as interoperability, availability, privacy, security, and others. We describe a way to compute social trust in OWL-S style semantic Web services. Our formalism exploits the users' ratings of the services and execution characteristics of those services. We describe our service-composition algorithm, called Trusty, that is based on this formalism. We discuss the formal properties of Trusty and our implementation of the algorithm. We present our experiments in which we compared Trusty with SHOP2, a well-known AI planning algorithm that has been successfully used for OWL-S style service composition. Our results demonstrate that Trusty generates more trustworthy compositions than SHOP2. Web services are rapidly changing the landscape of software engineering. One of the most interesting challenges introduced by web services is represented by Quality Of Service (QoS)--aware composition and late--binding. This allows to bind, at run--time, a service--oriented system with a set of services that, among those providing the required features, meet some non--functional constraints, and optimize criteria such as the overall cost or response time. In other words, QoS--aware composition can be modeled as an optimization problem.We propose to adopt Genetic Algorithms to this aim. Genetic Algorithms, while being slower than integer programming, represent a more scalable choice, and are more suitable to handle generic QoS attributes. The paper describes our approach and its applicability, advantages and weaknesses, discussing results of some numerical simulations. In recent years, quite a few search algorithms have been used to solve Web service composition problem. However, it is still lack of systematic analysis about these methods. In the paper, we attempt to analyze the effect of three typical meta-heuristic search algorithms. The experimental analysis is performed according to the search-based Web service composition framework. In the experiments, we mainly carry out the analysis as follows: different abstract service number, different candidate service number and different QoS constraint strength. Based on the above analysis, some guidelines of realizing Web service composition via search algorithms are yielded. For example, EDA is suitable for the composition problem with large abstract service number. PSO is more effective for the case of large candidate service number. GA is a good choose for the little-scale Web service composition problem. In addition, EDA can effectively settle the composition problem with strong QoS constraint. GA is suitable for the problem with medium constraint strength, and PSO has the poor ability to tackle the QoS constraint with high strength.