Search-based QpS ranking prediction for web services in cloud environments

摘要

Unlike traditional quality of service (QoS) value prediction, QoS ranking prediction examines the order of services under consideration for a particular user. To address this NP-Complete problem, greedy strategy-based solutions, such as CloudRank algorithm, have been widely adopted. However, they can only produce locally approximate solutions. In this paper, we propose a search-based prediction framework to address the QoS ranking problem. The traditional particle swarm optimization (PSO) algorithm has been adapted to optimize the order of services according to their QoS records. In real situations, QoS records for a given consumer are often incomplete, so the related data from close neighbour users is often used to determine preference relations among services. In order to filter the neighbours for a specific user, we present an improved method for measuring the similarity between two users by considering the occurrence probability of service pairs. Based on the similarity computation, the top-k neighbours are selected to provide QoS information support for evaluation of the service ranking. A fitness function for an ordered service sequence is defined to guide search algorithm to find high-quality ranking results, and some additional strategies, such as initial solution selection and trap escaping, are also presented. To validate the effectiveness of our proposed solution, experimental studies have been performed on real-world QoS data, the results from which show that our PSO-based approach has a better ranking for services than that computed by the existing CloudRank algorithm, and that the improvement is statistically significant, in most cases.