Project Topics
Get Complete Project Material File(s) Now! »
QoS-aware service selection strategies
Based on the models presented above, QoS-aware service-oriented middleware approaches proceed to the selection of services using different strategies. Like all the algorithms dealing with combinatorial problems, QoS-aware selection algorithms can be divided into two broad classes: (i) brute-force-like algorithms and (ii) heuristic algorithms. The first class of algorithms aim at determining the optimal service composition (i.e., with the highest QoS) by exploring all possible compositions of services. Amigo [Ben Mokhtar et al., 2005], COCOA [Ben Mokhtar et al., 2007], Daidalos [Funk et al., 2007] and the approach proposed by [Lee and Lee, 2006] fall under brute-force algorithms as they evaluate QoS of all possible compositions of services, and then select the optimal one. These algorithms have high computational cost (NP-hard [Yang et al., 2009]), thus they can not be executed in a timely manner with respect to spontaneous interactions with the user aimed at by pervasive computing. To cope with this issue, a se- cond class of solutions propose heuristic algorithms that find near-optimal compositions, i.e., compositions that meet global QoS constraints and maximize the QoS delivered to the user.
This class of algorithms do not explore all possible compositions of services ; they rather use different heuristics to explore the set of service compositions that most likely can lead to a satisfactory solution. For instance, the selection algorithm proposed by the Aura project [Sousa et al., 2006] uses the QoS utility to required resources ratio as a heuristic to determine near- optimal compositions, whereas PICO [Kalasapur et al., 2007] applies two heuristic algorithms (viz., the extended Dijkstra algorithm and Bellman Ford algorithm [Xiao et al., 2004]) to resolve QoS-aware service selection formulated as an MCPS problem.
QoS-aware service selection techniques
QoS-aware service selection algorithms use various techniques to explore and select service compositions. The goal of the selection technique is to reduce the number of service compositions to be investigated, thus enabling to enhance the timeliness of the algorithm. Several selection techniques have been proposed in the literature [Jaeger et al., 2005]. In our study, we identify three main selection techniques proposed by QoS-aware service-oriented middleware: (i) greedy selection, (ii) branch and bound and (iii) discarding subsets.
Greedy selection is a technique that selects, for each abstract activity in the user task, the service candidate with the highest QoS. The selection is performed for each abstract activity individually and it is generally used for QoS-aware selection under local QoS constraints [Jaeger et al., 2005]. Yang et al. [Yang et al., 2009] present a greedy selection algorithm called LOSSA (Local Optimal Service Selection Algorithm). LOSSA proceeds to the selection of services for each abstract functionality in the user required task through two steps: I-level selection that filters out service candidates that fail individual QoS constraints, and A-level selection that selects services resulting from the I-level selection based on a comprehensive score aggregating all QoS values of services. A second greedy selection approach is presented by Chang and Lee [Chang and Lee, 2009]. The authors use PROMOTHEE [Brans and Vincke, 1985], a multi-criteria decision making (MCDM) technique to select the best service for each abstract activity in the user task. Another interesting greedy selection approach is presented by the DAMS-SS middleware [Dutra and Junior, 2010]. This approach consists in three steps. First, the middleware clusters services based on their QoS properties using the Self-Organizing Map (SOM) algorithm. Second, it uses ADAPTREE which is an adaptive decision algorithm to generate a hierarchy of service clusters with respect to the importance of QoS properties. Finally, it decides about the best cluster of services in terms of QoS using the ANFIS (Adaptive Network-based Fuzzy Inference System) algorithm.
QoS-driven Composition Adaptation
Service composition adaptation is a key functionality of QoS-aware service-oriented middle- ware. It enables service compositions to evolve in dynamic pervasive environments and adequa- tely react to various changes in these environments. As we focus on QoS concerns in pervasive environments, in our work we concentrate on adaptation driven by QoS changes (e.g., QoS fluctuation), known as QoS-driven composition adaptation.
The goal of QoS-driven composition adaptation is to adjust running QoS-aware service com- positions in order to ensure meeting QoS requirements, and/or to optimize the QoS delivered to users [Kazhamiakin et al., 2010]. Towards this purpose, various approaches have been pro- posed by QoS-aware service-oriented middleware. To evaluate these approaches, we recall the survey proposed by Kazhamiakin et al.. The authors present a conceptual model and a detailed taxonomy of service adaptation in general (i.e., including QoS-driven composition adaptation).
The authors introduce a set of criteria for the comparison of adaptation approaches (the survey is interesting for the reader who would like to probe further). Based on this survey, we identify our main criteria allowing to assess QoS-driven composition adaptation approaches (see Figure II.4) : (i) adaptation model, (ii) adaptation timing, (iii) adaptation subject, (iv) adaptation mechanism, and (v) the scope of adaptation effect [Kazhamiakin et al., 2010].
A Semantic End-to-End QoS Model for Pervasive Environments
In our work, we concentrate on QoS knowledge representation rather than a language to specify QoS. To this extent, our approach is to provide a set of QoS ontologies that can be referenced by any appropriate QoS specification language, notably XML-based QoS languages supporting OWL semantic annotations Oldham et al. [2006]. This approach yields semantically enriched QoS descriptions that combine the accuracy of QoS description languages with the rich semantics of QoS ontologies, hence broadening QoS understanding among users and service providers in pervasive environments.
In this section, we present a QoS model formed of a set of QoS ontologies addressing QoS on an end-to-end basis. Our model covers quality factors associated with the main elements impacting QoS in pervasive environments. These elements are mainly about: (i) the environ- ment and its underlying network and system resources, (ii) application services, and (iii) users. Additionally, our model puts special emphasis on quality features related to the dynamics of the environment, application services and users (e.g., user mobility, adaptability and context awareness of application services).
Our model is designed according to a layered approach, thus aiming to provide distinct and easily manageable ontologies. As depicted in (Figure III.1), it comprehends four ontologies:
1. The QoS Core ontology incorporates general concepts needed for QoS description (e.g., quality group and quality factor). Most of the conceptual elements of this ontology are derived from WSQDL.
2. The Infrastructure QoS ontology specifies quality factors related to the environment and its underlying network and system infrastructure. More specifically, it defines inherent characteristics of the environment where users and services act. These characteristics are mainly about the service density and the number of active users that can be supported, in addition to the ability of the environment to offer functionally equivalent services that can replace each other. The Infrastructure QoS ontology defines also quality factors related to the capabilities of mobile devices and the connectivity of wireless networks.
Table of contents :
List of Figures
List of Tables
I Introduction
1 Pervasive Computing
2 QoS and QoS-awareness
3 QoS Issues in Pervasive Environments
3.1 QoS-enabling specifications
3.2 QoS-aware service discovery
3.3 QoS-aware service composition
3.4 QoS-driven composition adaptation
4 Towards QoS-aware Service-Oriented Middleware for Pervasive Environments
5 Thesis Contribution and Document Structure
II QoS-aware Service-Oriented Middleware: State of the Art
1 QoS-aware Service-Oriented Middleware
2 QoS-enabling specifications
2.1 Taxonomy of QoS models
2.2 Quality-Based Service Description (QSD)
3 QoS-aware Service Discovery
4 QoS-aware Service Composition
4.1 Service assembly approach
4.2 Scope of QoS constraints
4.3 QoS-aware service selection models
4.4 QoS-aware service selection strategies
4.5 QoS-aware service selection techniques
5 QoS-driven Composition Adaptation
5.1 Adaptation model
5.2 Adaptation timing
5.3 Adaptation subject
5.4 Scope of adaptation effect
5.5 Adaptation mechanism
6 Summary and Research Challenges
IIIQoS Modelling in Pervasive Environments
1 WSQM Overview
2 A Semantic End-to-End QoS Model for Pervasive Environments
2.1 QoS Core ontology
2.2 Infrastructure QoS ontology
2.3 Service QoS ontology
2.4 User QoS ontology
3 Discussion
IVQoS-aware Service Composition in Pervasive Environments
1 QASCO Overview
2 QoS-aware Service Composition Model
2.1 QoS model
2.2 Composition model
2.3 QoS aggregation
3 The QASSA Algorithm
3.1 Design Rationale
3.2 Local Selection Phase
3.2.1 Preliminary Investigation
3.2.2 Local Selection in QASSA
3.3 Global Selection Phase
3.4 Computational Complexity Analysis
4 Distributing QASSA
5 Evaluation and Discussion
V QoS-driven Composition Adaptation in Pervasive Environments
1 Approach Baseline
1.1 Global and Proactive QoS Monitoring
1.2 Service Substitution
2 Background and Definitions
3 Behavioural Adaptation Strategy: Overview
4 From a User Task to a Behavioural Graph
5 The Task Class Concept
5.1 Overview
5.2 Formal Definition
6 A Subgraph-Homeomorphism-based Approach to Behavioural Adaptation
6.1 Preliminary Verifications
6.2 Extended Vertex Disjoint Subgraph Homeomorphism
6.2.1 Semantic vertex matching
6.2.2 Data constraints
6.2.3 Particular vertex mappings
7 Evaluation and Discussion
VIQASOM: A QoS-Aware Service-Oriented Middleware for Pervasive Environments
1 SemEUsE Research Project
1.1 SemEUsE Architecture
1.2 Contribution to SemEUsE
1.2.1 QoS-enabled Composition
1.2.2 Reconfiguration
2 QASOM Middleware
2.1 QASOM Architecture
2.1.1 QoS-aware Service Composition Framework
2.1.2 QoS-driven Composition Adaptation Framework
2.2 Prototype Implementation
2.3 Specifying User Tasks
2.4 Specifying Executable Service Compositions
3 Experimental Results
3.1 Experimental set up
3.2 Performance of QASSA (the centralized version)
3.2.1 Impact of the Aggregation Approach
3.2.2 Impact of User QoS requirements
3.3 Performance of QASSA (the distributed version)
3.4 Performance of Transforming the User Task into a Behavioural Graph
VII Conclusion
1 Contributions
2 Perspectives
2.1 Short-term perspectives
2.2 Long-term perspectives
References
