Anytime QoS-aware service composition over the GraphPlan

Springer Science and Business Media LLC - Tập 9 - Trang 1-19 - 2013
Yuhong Yan1, Min Chen1
1Department of Computer Science and Software Engineering, Concordia University, Montreal, Canada

Tóm tắt

Automatic service composition is the generation of a business process to fulfill business goals that cannot be fulfilled by individual services. Planning algorithms are frequently used to solve this problem. In addition to satisfying functional goals, recent research is geared toward selecting the best services to optimize the QoS of the result business process. Without considering QoS, the planning algorithm normally searches for the shortest plan, which actually implies the unit execution time for each service. With QoS, a longer plan may have better QoS values and thus is preferred over a shorter one. In this paper, we are motivated to combine a systematic search algorithm like Dijkstra’s algorithm with a planning algorithm, GraphPlan, to achieve both functional goals and QoS optimization at the same time. The planning graph generated by GraphPlan is a compact representation of all execution paths, which makes it feasible to apply Dijkstra’s principle. In our new QoSGraphPlan algorithm, we extend Dijkstra’s algorithm from working on a single-source graph to working on the planning graph whose nodes have multiple sources. Using our method, we can get the best QoS value for throughput and response time in polynomial time when they are the single criteria. For the other QoS criteria, such as execution time, reputation, successful execution rate, and availability, our algorithm is exponential for both single criterion problem and multiple criteria problem. In this case, we extend QoSGraphPlan with beam search to solve the combination explosion problem. As our algorithms search for an optimal solution during the process of constructing the planning graph, they belong to the category of anytime algorithms that return better solutions if they keep running for a longer time.

Tài liệu tham khảo

Berbner R, Spahn M, Repp N, Heckmann O, Steinmetz R (2006) Heuristics for qos-aware web service composition. In: Proceedings of ICWS, pp 72–82

Bleul S (2009) Web service challenge rules. http://ws-challenge.georgetown.edu/wsc09/downloads/WSC2009Rules-1.1.pdf

Blum AL, Furst ML (1997) Fast planning through planning graph analysis. Artif Intell J 90(1–2):225–279

Börzsönyi S, Kossmann D, Stocker K (2001) The skyline operator. In: Proceedings of ICDE, pp 421–430

Bouguettaya A, Qi Y (2011) Service-centric framework for a digital government application. IEEE Trans Serv Comput 4(1):3–16

Canfora G, Di Penta M, Esposito R, Villani ML (2005) An approach for qos-aware service composition based on genetic algorithms. In: Proceedings of GECCO, pp 1069–1075

Chen M, Yan Y (2012) Redundant service removal in qos-aware service composition. In: Proceedings of IEEE ICWS, pp 431–439

Cui LY, Kumara S, Lee D (2011) Scenario analysis of web service composition based on multi-criteria mathematical programming. Inf Serv Sci 3(3)

Fredman ML, Tarjan RE (1987) Fibonacci heaps and their uses in improved optimalization problems. J ACM, 34

Ghallab DNM, Traverso P (2004) Automated planning: theory and practice. Morgan Kaufmann Publishers, Los Altos

El Haddad J, Manouvrier M, Rukoz M (2010) Tqos: transactional and qos-aware selection algorithm for automatic web service composition. IEEE Trans Serv Comput 3(1):73–85

Hassine AB, Matsubara S, Ishida T (2006) A constraint-based approach to horizontal web service composition. In: Proceedings of ISWC, pp 130–143

Hoffmann J, Nebel B (2001) The FF planning system: fast plan generation through heuristic search. J Artif Intell Res 14:253–302

Huang Z, Jiang W, Hu S, Liu Z (2009) Effective pruning algorithm for qos-aware service composition. In: Proceedings of CEC, pp 519–522

Jiang W, Zhang C, Huang Z, Chen M, Hu S, Liu Z (2010) Qsynth: a tool for qos-aware automatic service composition. In: Proceedings of ICWS, pp 42–49

LaValle SM (2006) Planning algorithms, Cambridge

May Chan KS, Bishop J, Baresi L (2007) Survey and comparison of planning techniques for web service composition. Technical report Dept Computer Science, University of Pretoria

Nguyen XT, Kowalczyk R, Phan MT (2006) Modelling and solving qos composition problem using fuzzy discsp. In: Proceedings of ICWS, pp 55–62

OASIS (2007) Uddi version 2.04 api specification. http://uddi.org/pubs/ProgrammersAPI-V2.04-Published-20020719.htm

OASIS (2007) Web services business process execution language (ws-bpel). http://www.oasis-open.org/committees/tc_home.php?wg_abbrev=wsbpel

Papazoglou MP, Traverso P, Dustdar S, Leymann F (2008) Service-oriented computing: a research roadmap. Int J Co-op Inf Syst 17(2):223–255

Peer J (2005) Web service composition as AI planning—a survey. Technical report, University of St. Gallen

Pistore M, Traverso P, Bertoli P (2005) Automated composition of web services by planning in asynchronous domains. In: Proceedings of ICAPS, pp 2–11

Poizat P, Yan Y (2010) Adaptive composition of conversational services through graph planning encoding. In: Proceedings of IsoLA, pp 35–50

Qi Y, Bouguettaya A (2010) Computing service skyline from uncertain qows. IEEE Trans Serv Comput 3(1):16–29

Rao J, Su X (2004) A survey of automated web service composition methods. In: Proceedings of 1st Internationsl WS on semantic web services and web process composition, SWSWPC

Triantaphyllou E (2000) Multi-criteria decision making: a comparative study

W3C (2004) Owl web ontology language overview. http://www.w3.org/TR/owl-features/ Retrieved 2011–06-30

W3C (2007) Semantic annotations for wsdl and xml schema (sawsdl). http://www.w3.org/TR/sawsdl/ Retrieved 2011–06-30

W3C (2007) Soap version 1.2 part 1: messaging framework (second edition). http://www.w3.org/TR/soap12-part1/#intro. Retrieved 2011–06-30

W3C (2007) Web services description language (wsdl) version 2.0. http://www.w3.org/TR/wsdl20/ Retrieved 2011–06-30

Wikipedia. Beam search. http://en.wikipedia.org/wiki/Beam_search Retrieved 2011–09-02

Wikipedia. Dijkstra’s algorithm. http://en.wikipedia.org/wiki/Dijkstra’27_algorithm Retrieved 2011–06-30

Yan Y, Poizat P, Zhao L (2010) Repair vs. recomposition for broken service compositions. In: Proceedings of ICSOC, pp 152–166

Yan Y, Xu B, Gu Z (2008) Automatic service composition using and/or graph. In: Proceedings of CEC/EEE, pp 335–338

Yan Y, Xu B, Gu Z, Luo S (2009) A qos-driven approach for semantic service composition. In: Proceedings of CEC, pp 523–526

Yu T, Zhang Y, Lin K-J (2007) Efficient algorithms for web services selection with end-to-end qos constraints. ACM Trans Web, 1(1)

Zeng L, Benatallah B, Ngu AHH, Dumas M, Kalagnanam J, Chang H (2004) Qos-aware middleware for web services composition. IEEE Trans Softw Eng 30(5):311–327

Zeng L, Benatallah B, Dumas M, Kalagnanam J, Sheng QZ (2003) Quality driven web services composition. In: Proceedings of WWW, pp 411–421

Zheng X, Yan Y (2008) An efficient web service composition algorithm based on planning graph. In: Proceedings of ICWS, pp 691–699

Thông tin
Thông tin xuất bản

Springer Science and Business Media LLC

Tập 9

1-19

Thông tin tác giả