A scalable approach for QoS-based web service selection

verfasst von: Mohammad Alrifai, Thomas Risse, Peter Dolog, Wolfgang Nejdl
Abstract: QoS-based service selection aims at finding the best component services that satisfy the end-to-end quality requirements. The problem can be modeled as a multi-dimension multi-choice 0-1 knapsack problem, which is known as NP-hard. Recently published solutions propose using linear programming techniques to solve the problem. However, the poor scalability of linear program solving methods restricts their applicability to small-size problems and renders them inappropriate for dynamic applications with run-time requirements. In this paper, we address this problem and propose a scalable QoS computation approach based on a heuristic algorithm, which decomposes the optimization problem into small sub-problems that can be solved more efficiently than the original problem. Experimental evaluations show that near-to-optimal solutions can be found using our algorithm much faster than using linear programming methods.
Organisationseinheit(en): Forschungszentrum L3S
Externe Organisation(en): Aalborg University
Typ: Aufsatz in Konferenzband
Seiten: 190-199
Anzahl der Seiten: 10
Publikationsdatum: 2009
Publikationsstatus: Veröffentlicht
Peer-reviewed: Ja
ASJC Scopus Sachgebiete: Theoretische Informatik, Allgemeine Computerwissenschaft
Elektronische Version(en): https://doi.org/10.1007/978-3-642-01247-1_20 (Zugang: Geschlossen)

BibTeX

@inproceedings{6c2ab38c62bb419c8ce36d408801112a,
title = "A scalable approach for QoS-based web service selection",
abstract = "QoS-based service selection aims at finding the best component services that satisfy the end-to-end quality requirements. The problem can be modeled as a multi-dimension multi-choice 0-1 knapsack problem, which is known as NP-hard. Recently published solutions propose using linear programming techniques to solve the problem. However, the poor scalability of linear program solving methods restricts their applicability to small-size problems and renders them inappropriate for dynamic applications with run-time requirements. In this paper, we address this problem and propose a scalable QoS computation approach based on a heuristic algorithm, which decomposes the optimization problem into small sub-problems that can be solved more efficiently than the original problem. Experimental evaluations show that near-to-optimal solutions can be found using our algorithm much faster than using linear programming methods.",
author = "Mohammad Alrifai and Thomas Risse and Peter Dolog and Wolfgang Nejdl",
year = "2009",
doi = "10.1007/978-3-642-01247-1_20",
language = "English",
isbn = "978-3-642-01246-4",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Berlin Heidelberg",
pages = "190--199",
booktitle = "Service-Oriented Computing",
note = "International Conference on Service-Oriented Computing, ICSOC 2008 ; Conference date: 01-12-2008 Through 01-12-2008",
}