1. Yunnan Provincial Key Laboratory of Computer Technology Application, Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, China 2. School of Information Science and Engineering, Yunnan University, Kunming 650091, China 3. Faculty of Management and Economics, Kunming University of Science and Technology, Kunming 650093, China
Open and dynamic environments lead to inherent uncertainty of Web service QoS (Quality of Service), and the QoS-aware service selection problem can be looked upon as a decision problem under uncertainty. We use an empirical distribution function to describe the uncertainty of scores obtained from historical transactions. We then propose an approach to discovering the admissible set of services including alternative services that are not dominated by any other alternatives according to the expected utility criterion. Stochastic dominance (SD) rules are used to compare two services with uncertain scores regardless of the distribution form of their uncertain scores. By using the properties of SD rules, an algorithm is developed to reduce the number of SD tests, by which the admissible services can be reported progressively. We prove that the proposed algorithm can be run on partitioned or incremental alternative services. Moreover, we achieve some useful theoretical conclusions for correct pruning of unnecessary calculations and comparisons in each SD test, by which the efficiency of the SD tests can be improved. We make a comprehensive experimental study using real datasets to evaluate the effectiveness, efficiency, and scalability of the proposed algorithm.
Papazoglou M, Traverso P, Dustdar S, Leymann F. Service-oriented computing: state of the art and research challenges. Computer, 2007, 40(11): 38-45
https://doi.org/10.1109/MC.2007.400
2
Sanati F, Lu J. An ontology for e-government service integration. Computer Systems Science and Engineering, 2012, 27(2): 89-101
3
Dou W, Lv C, Zhang X, Chen J. A collaborative QoS-aware service evaluation method among multi-users for a shared service. International Journal of Web Services Research, 2012, 9(1): 30-50
https://doi.org/10.4018/jwsr.2012010102
4
Zheng Z, Zhang Y, Lyu M R. Investigating QoS of real-world Web services. IEEE Transactions on Services Computing, 2014, 7(1): 32-39
https://doi.org/10.1109/TSC.2012.34
5
Candan K S, Li W S, Phan T, Zhou M. Frontiers in information and software as services. In: Proceedings of the 2009 IEEE International Conference on Data Engineering. 2009, 1761-1768
https://doi.org/10.1109/ICDE.2009.168
6
Alrifai M, Skoutas D, Risse T. Selecting skyline services for QoS-based Web service composition. In: Proceedings of the 19th International Conference on World Wide Web. 2010, 11-20
https://doi.org/10.1145/1772690.1772693
7
Zeng L, Benatallah B, Ngu AHH, Dumas M, Kalagnanam J, Chang H. QoS-aware middleware for Web services composition. IEEE Transactions on Software Engineering, 2004, 30(5): 311-327
https://doi.org/10.1109/TSE.2004.11
8
Yu T, Zhang Y, Lin K J. Efficient algorithms for Web services selection with end-to-end QoS constraints. ACM Transactions on the Web, 2007, 1(1): 6
https://doi.org/10.1145/1232722.1232728
9
Alrifai M, Risse T. Combining global optimization with local selection for efficient QoS-aware service composition. In: Proceedings of the 18th International Conference on World Wide Web. 2009, 881-890
https://doi.org/10.1145/1526709.1526828
10
Hwang S Y, Wang H, Tang J, Srivastava J. A probabilistic approach to modeling and estimating the QoS of Web-services-based workflows. Information Sciences, 2007, 177(23): 5484-5503
https://doi.org/10.1016/j.ins.2007.07.011
11
Rosario S, Benveniste A, Haar S, Jard C. Probabilistic QoS and soft contracts for transaction-based Web services orchestrations. IEEE Transactions on Service Computing, 2008, 1(4): 187-200
https://doi.org/10.1109/TSC.2008.17
12
Jurca R, Faltings B, Binder W. Reliable QoS monitoring based on client feedback. In: Proceedings of the 16th International Conference on World Wide Web. 2007, 1003-1012
https://doi.org/10.1145/1242572.1242708
13
Barbon F, Traverso P, Pistore M, Trainotti M. Run-time monitoring of instances and classes of Web service compositions. In: Proceedings of the 4th International Conference on Web Services. 2006, 63-71
https://doi.org/10.1109/ICWS.2006.113
14
Porter R B, Gaumnitz J E. Stochastic dominance vs. mean-variance portfolio analysis: an empirical evaluation. American Economic Review, 1972, 62(3): 438-446
15
Cynthia B L, Allan E S. Precise and realistic utility functions for usercentric performance analysis of schedulers. In: Proceedings of the 16th International Symposium on High Performance Distributed Computing. 2007, 107-116
16
Arrow K J. Essays in the theory of risk-bearing. North-Holland Publishing Company, 1976
17
Zheng H, Yang J, Zhao W. QoS probability distribution estimation for Web services and service compositions. In: Proceedings of the IEEE International Conference on Service-Oriented Computing and Applications. 2010, 1-8
https://doi.org/10.1109/SOCA.2010.5707144
18
Wiesemann W, Hochreiter R, Kuhn D. A stochastic programming approach for QoS-aware service composition. In: Proceedings of the 8th IEEE International Symposium on Cluster Computing and the Grid. 2008, 226-233
https://doi.org/10.1109/CCGRID.2008.40
19
Fu X D, Yue K, Zou P, Wang F. Risk-driven Web services selection based on stochastic QoS. ICIC Express Letters, 2011, 5(7): 2269-2274
20
Klein A, Ishikawa F, Bauer B. A probabilistic approach to service selection with conditional contracts and usage patterns. In: Proceedings of the 7th International Conference on Service Oriented Computing. 2009, 253-268
https://doi.org/10.1007/978-3-642-10383-4_17
21
Schuller D, Lampe U, Eckert J, Steinmetz R, Schulte S. Cost-driven optimization of complex service-based workflows for stochastic QoS parameters. In: Proceedings of the 10th IEEE International Conference on Web Services. 2012, 66-73
https://doi.org/10.1109/ICWS.2012.50
22
Zheng Z, Zhang Y, Lyu M. Distributed QoS evaluation for real-world Web services. In: Proceedi<?Pub Caret?>ngs of the 8th IEEE International Conference on Web Services. 2010, 83-90
https://doi.org/10.1109/ICWS.2010.10
23
Yu Q, Bouguettaya A. Computing service skyline from uncertain QoWS. IEEE Transactions on Services Computing, 2010, 3(1): 16-29
https://doi.org/10.1109/TSC.2010.7
24
Levy H. Stochastic dominance and expected utility: survey and analysis. Management Science, 1992, 38(4): 555-593
https://doi.org/10.1287/mnsc.38.4.555
25
Chakraborty S, Yeh C H. A simulation based comparative study of normalization procedures in multiattribute decision making. In: Proceedings of the 6th Conference on Artificial Intelligence, Knowledge Engineering and Databases. 2007, 102-109
26
van der Vaart A W. Asymptotic statistics. London: Cambridge University Press, 2000.
27
Kroll Y, Levy H. Stochastic dominance: areview and some new evidence. Research in Finance, 1980, 2: 163-227
28
Kuosmanen T. Efficient diversification according to stochastic dominance criteria. Management Science, 2004, 50(10): 1390-1406
https://doi.org/10.1287/mnsc.1040.0284
29
Hadar J, Russell W R. Rules for ordering uncertain prospects. American Economic Review, 1969, 59(1): 25-34
30
Hanoch G, Levy H. The efficiency analysis of choices involving risk. The Review of Economic Studies, 1969, 36(3): 335-346
https://doi.org/10.2307/2296431
31
Whitmore G A. Third-degree stochastic dominance. American Economic Review, 1970, 60(3): 457-459
Hu F, Wang G, Feng L. Fast knowledge reduction algorithms based on quick sort, In: Proceedings of the 3rd International Conference on Rough Sets and Knowledge Technology. 2008, 72-79
https://doi.org/10.1007/978-3-540-79721-0_15
34
Haddad J E, Manouvrier M, Rukoz M. TQoS: transactional and QoSaware selection algorithm for automatic Web service composition. IEEE Transactions on Services Computing, 2010, 3(1): 73-85
https://doi.org/10.1109/TSC.2010.5
35
Lecue F. Optimizing QoS-aware semantic Web service composition. In: Proceedings of the 8th International Semantic Web Conference. 2009, 375-391
36
Borzsonyi S, Kossmann D, Stocker K. The skyline operator. In: Proceedings of the 17th International Conference on Data Engineering, 2001, 421-430
https://doi.org/10.1109/ICDE.2001.914855
37
Yu Q, Bouguettaya A. Efficient service skyline computation for composite service selection. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(4): 776-789
https://doi.org/10.1109/TKDE.2011.268
38
Skoutas D, Sacharidis D, Simitsis A, Sellis T. Serving the sky: discovering and selecting semantic Web services through dynamic skyline queries. In: Proceedings of the 2008 IEEE International Conference on Semantic Computing. 2008, 222-229
https://doi.org/10.1109/ICSC.2008.65
39
Skoutas D, Sacharidis D, Simitsis A, Sellis T. Ranking and clustering Web services using multicriteria dominance relationships. IEEE Transactions on Services Computing, 2010, 3(3): 163-177
https://doi.org/10.1109/TSC.2010.14
40
Rosario S, Benveniste A, Jard C. Flexible probabilistic QoS management of orchestrations. International Journal of Web Services Research, 2010, 7(2): 21-42
https://doi.org/10.4018/jwsr.2010040102
41
Fourneau J M, Mokdad L, Pekergin N. Stochastic bounds for performance evaluation of Web services. Concurrency and Computation: Practice and Experience, 2010, 22(10): 1286-1307
https://doi.org/10.1002/cpe.1580
