Open and dynamic environments lead to inher- ent 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...Open and dynamic environments lead to inher- ent 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 empiri- cal distribution function to describe the uncertainty of scores obtained from historical transactions. We then propose an approach to discovering the admissible set of services in- cluding 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 pro- gressively. 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 im- proved. We make a comprehensive experimental study using real datasets to evaluate the effectiveness, efficiency, and scal- ability of the proposed algorithm.展开更多
基金This work was partially supported by the National Natural Science Foundation of China （Grand No. 71161015, 61462056, 61163003, 61472345 and 61462051）, the Applied Fundamental Re- search Project of Yunnan Province （2014FA028, 2014FA023, 2014FB133, 2013FA013 and 2013FA032）, and the Yunnan Provincial Foundation for Leaders of Disciplines in Science and Technology （2012HB01M）. The au- thors appreciate the reviewers for their extensive and informative comments for the improvement of this paper.
文摘Open and dynamic environments lead to inher- ent 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 empiri- cal distribution function to describe the uncertainty of scores obtained from historical transactions. We then propose an approach to discovering the admissible set of services in- cluding 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 pro- gressively. 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 im- proved. We make a comprehensive experimental study using real datasets to evaluate the effectiveness, efficiency, and scal- ability of the proposed algorithm.
