Semantic web service compositions must be aligned with requirements from the target users in terms of quality requirements. Given a set of quality requirements, one can choose to either find the optimal composition or a “good enough” composition, which satisfies these requirements. Since optimizing compositions of semantic services under quality constraints is known to be NP-hard, it is unsuitable for realistic problems within large search spaces. The authors address the issue by using the “good enough” approach, selecting the first composition that passes their quality threshold. Firstly, this paper defines quality constraints within an innovative and extensible 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 descriptions of Web services parameters, while QoS focuses on non-functional criteria of services. User quality requirements are met by selecting a valid composition. To allow the use of this model with a large number of candidate services as foreseen by the strategic EC-funded project SOA4All the authors formulate the selection problem as a Constraint Satisfaction Problem and test the use of a stochastic search method.
TopIntroduction
Service composition aims to create new services out of existing ones, to satisfy needs for which there are no existing services. If we tag services with semantic information as found in the Semantic Web (Berners-Lee et al., 2001), we can automate composition since the description of functionality, inputs and outputs of services are now machine-processable, or we can now automate the reasoning with the semantics of services (Sycara et al., 2003). For example, the Web Ontology Language (OWL) (Smith et al., 2004), is based on concepts from Description Logics (Baader & Nutt, 2003) and uses formal conceptualizations of a particular domain (ontologies).
Composing semantic services under realistic assumptions of scale whilst under time constraints is the focus of this work. Scale comes from the current trends of growth in Internet and the Internet of Services, indeed we can expect thousands of candidate component services to choose from when composing. Time may be limited because people who compose services using mash-up environments expect to see results of their actions in a short time-frame to give them the needed feedback of their actions in a visual interactive mode of development.
Under these assumptions we can no longer search for optimal solution in respect to some quality and functional requirements. We have to resort to “good enough” composition, where we take the first composition to pass a minimum threshold of quality and functionality requirements. In this paper we demonstrate how this can be done when considering the semantic similarities between input and output parameters as indicators of service functionality, or functional aspects of service composition (Lecue et al., 2008), combined with non functional parameters such as Quality of Services (QoS) (Canfora et al., 2005; Berbner, 2006; Yu & Lin, 2005). To measure semantic similarity, we use the concept of (functional) semantic link (Lecue & Leger, 2006), defined as a semantic connection between an output and an input parameter of two services. Here we propose to unify both types of criteria in an innovative and extensible model that could be used to estimate, select and optimize the quality of any semantic Web service composition.
Maximizing the quality of service composition using this model is essentially a multi-objective optimization problem with constraints on quality of services and their semantic links. Such a problem is known to be NP-hard (Papadimtriou & Steiglitz, 1982) and intractable (Lecue et al., 2008; Zeng et al., 2004) in a context of a large number of services. Indeed most approaches have been shown to have poor scalability in terms of time taken to compute optimal compositions when the size of the initial set of services grows. Such a case can arise in the future semantic web, where millions of semantic services will be accessible globally. This is the vision of SOA4All, a strategic EC-funded project aiming to create the tools, languages and conceptual techniques where scalability is one of its main objectives.
Rapid computation of (non necessarily optimal) compositions is especially important for interactive systems providing service composition facilities for end users, where long delays may be unacceptable. A typical scenario would involve an end-user retrieving a template for a desired composition, and specifying some constraints in addition to the ones already in the template. The software should then propose a combination of services which satisfies these constraints. This should happen in real-time even for a very complex composition template with a large number of alternative matching services. In this work we address this scalability issue by selecting a composition (among a large number achieving the same goal) satisfying some constraints (defined along the innovative quality model) rather than computing the optimal composition. To this end we i) formulate quality-driven semantic web service composition as a Constraint Satisfaction Problem (CSP) and ii) test the use of a stochastic search method. Finally we compare the latter with state-of-the-art approaches.