Inf Syst Front (2014) 16:143–152

DOI 10.1007/s10796-013-9455-4

Multi-user web service selection based on multi-QoS prediction

Shangguang Wang & Ching-Hsien Hsu & Zhongjun Liang &
Qibo Sun & Fangchun Yang

Published online: 4 October 2013

# Springer Science+Business Media New York 2013

Abstract In order to find best services to meet multi-user’s 1 Introduction

QoS requirements, some multi-user Web service selection
schemes were proposed. However, the unavoidable chal- Web services are designed as computational components to
lenges in these schemes are the efficiency and effect. Most build service-oriented distributed systems (Zeng et al. 2003).
existing schemes are proposed for the single request condition The rising development of service-oriented architecture makes
without considering the overload of Web services, which more and more alternative Web services offered with equiva-
cannot be directly used in this problem. Furthermore, existing lent or similar functions. Therefore, how to select a feasible
methods assumed the QoS information for users are all known service to meet the demands of different users has become a
and accurate, and in real case, there are always many missing popular research area.
QoS values in history records, which increase the difficulty of In order to improve the customer’s satisfaction, many studies
the selection. In this paper, we propose a new framework for (Zeng et al. 2003; Zeng et al. 2004; Canfora et al. 2005; Alrifai
multi-user Web service selection problem. This framework and Risse 2009; Alrifai et al. 2010) focused on the Quality of
first predicts the missing multi-QoS values according to the Service (QoS) optimization. However, most existing selection
historical QoS experience from users, and then selects the methods are proposed on the single request condition, which
global optimal solution for multi-user by our fast match ap- cannot be directly used on multi-user condition, due to the
proach. Comprehensive empirical studies demonstrate the unavoidable challenges in this problem are shown as follows.
utility of the proposed method.
1) Effect. As the ability of a service is limited, the service may
not be able to hold the guarantee as it provides, when the
Keywords Web services . Service selection . QoS .
requests are overloading. Specially speaking, if a single
Multi-user . QoS prediction
service instance takes requests more than its ability thresh-
old, then its QoS values may decline rapidly, which will lead
requesting users a bad QoS experience. Furthermore, due to
S. Wang (*) : Z. Liang : Q. Sun : F. Yang the various locations and communication links, different
State Key Laboratory of Networking and Switching Technology, users could have different QoS experiences when invoking
Beijing University of Posts and Telecommunications,
Beijing 100876, China even the same Web service, and the consuming time and
e-mail: [email protected] cost make it expensive to get all information by invocation.
Z. Liang In real case, there are always many missing QoS values in
e-mail: [email protected] history records; this will increase the difficulty of the selec-
Q. Sun tion. While existing methods always assume the QoS infor-
e-mail: [email protected] mation for users are all known and accurate, which might be
F. Yang something different with actual scenarios. Therefore, how to
e-mail: [email protected] efficiently select the Web service for multi-user is the first
challenge in our problem.
C.<H. Hsu 2) Efficiency. In practical world applications, users require
Department of Computer Science and Information Engineering,
Chung Hua University, Hsinchu 707, Taiwan less time-consumption in Web service selection.
e-mail: [email protected] However, the time complexity of existing methods for
144 Inf Syst Front (2014) 16:143–152

multi-user Web services selection problem is exponential 4) We conduct several experiments on real-world Web ser-
with the number of multi-user and candidate services. vice dataset and synthetic dataset. Comprehensive empir-
While with the extensive applications of Web services, ical studies demonstrate the utility of the proposed
the two numbers grow bigger and bigger, which leads the method.
expensive time cost. Therefore, how to efficiently select
The rest of paper is organized as follows: Section 2 high-
the Web service for multi-user is the second challenge in
lights the related work. Section 3 formulates the problem, and
our problem.
describes our framework. Section 4 details the multi-QoS
3) Simultaneity. In Web service selection applications, the
prediction method and Section 5 details the fast match ap-
users want to obtain multi-QoS at same time. However,
proach. Section 6 presents the experimental result. We con-
most existing methods cannot deal with this case, as they
clude the paper in Section 7.
had to predict each individual QoS value one by one, and
QoS- prediction is the foundation issue of Web service
selection. Therefore, how to simultaneously calculate the 2 Related work
multi-QoS for multi-user is the third challenge in our
problem. In this section, we will briefly introduce the related work in
Web service selection area. There is a line of work focused on
In this paper, we propose a new framework for multi-user
the Quality of Service (QoS) optimization and efficient Web
Web service selection problem, which aims to effectively and
service selection methods, aims to improve the customers
efficiently select feasible services to meet the demands of
satisfaction.
different users. In this framework, we first propose a multi-
Back to a decade ago, Zeng et al. in (Zeng et al. 2003; Zeng
QoS prediction method, which can predict personalized QoS
et al. 2004) first transferred the QoS-based service selection
values according to the historical QoS experience collected
problem into an optimization problem. They used (mixed)
from different users, and then we propose a fast match ap-
linear program ming techniques to find the optimal selection
proach to efficiently select the global optimal solution for
of component services. However, it suffered from poor scal-
multi-user. The contributions are listed as follows.
ability, due to the exponential time complexity of the applied
1) We propose a new framework for the multi-user Web search algo rithms. Motivate by real-time selection with large
service selection problem, which aims to effectively and number of service, Canfora et al. in (Canfora et al. 2005)
efficiently select feasible services to meet the demands of employed GA to solve Web service selection problem. Alrifai
different users. Using this framework, each user can be et al. in (Alrifai and Risse 2009) combined the global optimi-
provided with his/her suitable service, to avoid overload zation with local selection in order to find a close-to-optimal
of selected services in a short time. selection efficiently. After that, they in (Alrifai et al. 2010)
2) We design a multi-QoS prediction method, to simulta- proposed a new method to select and use representative skyline
neously predict the multi-QoS according to the historical services for the composition. However, all above works are
QoS experience from different users. In order to guarantee mainly focusing on service selection for a single user, when too
the accuracy effect, this method takes the relationship many requester select the same best Web service, the conflicts
between QoS attributes into consideration. Specially, it may occur.
first normalizes the QoS attribute values, then employs Recently, Shahand et al. (Shahand et al. 2010) and Dyachuk
the Non-negative Matrix Factorization to extract the fea- and Deters (Dyachuk and Deters 2006) considered the multiple
ture of users from all QoS attributes together, and last requests waiting in a queue, and Kang et.al.(Kang et al. 2011)
predicts the missing multi-QoS value observed from dif- used Euclidean distance with weights to measure degree of
ferent users via Multi-output Support Vector Regression matching of services based on QoS, they employed a 0–1
algorithm. integral programming model to solve problem of optimal service
3) We design a fast match approach (FMA for short) to select selection for multiple requesters (GOSSMR). However, the ex-
the global optimal solution for the multi-user. It first ponential time complexity of the applied search algorithms could
respectively calculates the optimal matching Web service influence the customers satisfaction. In addition, it supposed the
for each user, then checks the load conditions in this local QoS information for requesters are all known and accurate, and
selection plan. If any Web service could be overloaded, the real case is that it is very hard to get all requesters’ QoS
then we transform this problem to a maximum weight information from users’ perspective(Lo et al. 2012).
matching problem and employ the Kuhn-Munkres algo- To get personalized QoS, a few works attempted to predict
rithm (KM for short) to select the global optimal solution. the missing values. In (Shao et al. 2007), Shao et al. first
Its complexity of the time can be O (n ×m ) in the best employed collaborative filtering technique to predict the
situation, where n and m represent the number of users QoS of Web service. They proposed a user-based CF algo-
and Web services respectively. rithm to predict QoS values. Zheng et al.(Zheng et al. 2009)
Inf Syst Front (2014) 16:143–152 145

proposed a hybrid user-based and item-based CF algorithm to user Web selection problem, we first introduce some termi-
predict the personalized QoS, and they carried out a series of nology, and then define the problem.
large-scale experiments based on real Web services dataset.
1) QoS. QoS is the quantitative non-functional properties of
In (Jiang et al. 2011), Jiang et al. proposed that the influence
web services, which can be used to describe the quality
of personalization of Web service items should be taken into
criteria of a web service, such as response time, price and
account when computing degree of similarity between users.
availability etc..
That is, more popular services or services with more stable QoS
2) QoS Aggregation . QoS aggregation is to evaluate the
from user to user should contribute less to user similarity
utility for the user. It can map multi-dimension attributes
measurement. Zhang et al. (Zhang et al. 2010) suggested that
into one single real value from user’s perspective. In this
it was better to combine users’ QoS experiences, environment
paper, we employ an aggregation function to calculate the
factor and user input factor to predict Web services QoS values.
utility value by the following:
But how to obtain environment factor and user input factor

 Xm
were not discussed. Chen et al. (Chen et al. 2010) discovered Utility ui ; s j ¼ w  qkj ð1Þ
k¼1 ik
the great influence of user’s location to the accuracy of predic-
tion and proposed a region based hybrid Collaborative Filter where ∑ k=1m
wik =1, q jk is a QoS attribute value of the web
algorithm to predict the QoS of services. This method groups service sj, wik denotes for the weight of k-th QoS attributes on
users into a hierarchy of regions according to users’ locations user u1’s preference.
and their QoS records, so that the users in a region are similar. 3) Processing Capacity. Processing capacity of Web ser-
When identifying similar users for a target user, instead of vice pc j is the maximum request number that the Web
searching the entire set of users, the method only searches the service s j can be able to process at the present.
regions that the target user belongs to.
Assume multiple users U ={u 1, u 2, …, u n } request for the
Tang et al. (Tang et al. 2012) proposed a hybrid location-
same functional web service S with different QoS preference
aware QoS prediction method, which not only consider the
at same time, and there are m candidate Web service satisfied
location of users but also the services’ relationship. Lo et al. (Lo
that functional requirement, the multi-user Web service selec-
et al. 2012) proposed an extended Matrix Factorization frame-
tion problem is to select feasible services for the requestors
work with relational regularization to make missing QoS values
based on the personalized QoS values, and its objective is to
prediction. They added a user-based regularization term and a
maximize the following global utility function.
service-based regularization term in the minimizing objective
function. However, existing algorithms make QoS prediction X
n X
m


max Utility ui ; s j  xij ð2Þ
without considering the relationship between QoS attributes.
i¼1 j¼1
And they predicts value individual QoS one by one, which
cannot scale to multi-user service selection problem. where xij represents the select plan for user ui, if user select the
Different from previous research, we propose a new frame- Web service sj, then Xij =1; otherwise Xij = 0 (∑ i=1n
Xij ≤ pcj).
work for multi-user Web services selection problem. In this
framework, we first propose a prediction method by consid- 3.2 Our framework
ering the relationship between QoS attributes, which can
predict multi-QoS at same time, then propose a fast match As presented in the previous section, determining the best
approach to select the global optimal solution for multi-user. candidate services for different users is an optimization prob-
lem, which is based on the known multi-QoS values. However
this is unlikely in practical, different users will have different
3 Proposed framework QoS experiences when invoking even the same Web service,
due to their various locations and communication links, and it
In this section, we present the problem formulation and our is expensive to got all their QoS information from the users’
framework for multi-user Web service selection problem. perspective (Lo et al. 2012).
To address this problem, we propose a multi-user Web
service selection framework, which can predict missing
3.1 Problem formulation multi-QoS values to support the Web service selection. As
shown in Fig. 1, our framework includes following modules:
The goal of multi-user Web service selection is to select Web service search engine, Collector, Predictor and Selector .
feasible services to meet the demands of different users, which The Web service search engine searches Web services from the
not only do the global selection solution ensure that each user Internet and adds them into the Web service database. The
get his suitable service, but it also avoids QoS declining Collector collects the local QoS records feedback from differ-
caused by requests overloading. To better describe the multi- ent Web services users and stores them in the historical QoS
146 Inf Syst Front (2014) 16:143–152

Fig. 1 Our framework for multi-

user Web service selection

experience database. The Predictor predicts different users’ approach. It contains QoS normalization step, feature extrac-
personalized multi-QoS values. The selector gives the global tion step, and QoS prediction step.
optimal select plan for multiple requester, which can not only QoS normalization step, which aims to normalize the QoS
give the global solution for multi-users, but also avoid overload attribute values by Gaussian method (Ortega et al. 1997). This
of selected services. step can map the QoS values to the interval [0,1], which
In our framework, the Predictor and Selector are the key prepares for feature extraction.
modules to improve user experience, their performance are Feature extraction step, which aims to extract the feature of
depend on the prediction algorithm and search algorithm. users from existing multi-QoS values. This step can handle the
Next, we will give the detail in Section 4 and 5. acquired sparse multi-QoS information.
QoS prediction step, which aims to predict the missing
Multi-QoS values via Multi-output Support Vector Regression
4 Multi-QoS prediction algorithm. This step finally solves our problem based on the
extraction feature of users and the other users’ historical QoS
In multi-user Web service selection, the selector always wants experience for a target Web service.
to obtain multi-QoS value at same time since the global
optimal solution are given based on many attributes. 4.1 QoS normalization
However, existing QoS predicted algorithms are all focused
on predicting individual QoS one by one, which cannot scale To map the different QoS attributes to a same range of values, we
to the need of our selection. To dress this problem, we propose employ Gaussian method (Ortega et al. 1997) to normalize the
a new prediction algorithm which can not only predict multi- QoS attribute values for feature extraction. It can not only map
QoS value at same time, but also can provide a good the QoS values to the interval [0,1], but also can better avoid the
predicting precision for different users. influence of abnormal values (such as high value or low value)
The personalized QoS experience, obtained from a user compared with other normalization methods (such as Extremum
after the invocation, is co-determined by the feature of corre- Regularization Method). The detail can be described as follow.
sponding invoked Web service and the user. Therefore, for a
target Web service, the different feature of these users is the
main reason for the different QoS experience. In this paper, we
QoS Feature QoS
predict the missing multi-QoS based on the extracted feature
normalization extraction prediction
of users and historical QoS experience of users. Figure 2
shows the simplified procedure of our multi-QoS prediction Fig. 2 Procedure of multi-QoS prediction approach
Inf Syst Front (2014) 16:143–152 147

Fig. 3 Prediction example

First, we normalize the Multi-QoS attribute values in each QoS data, which represent the feature of Web service and user
dimension by the following: respectively.
Consider multi–QoS matrix Q={Q1,Q2,…,Qm1}(Q ∈R1×
b m ×n
qkij −qkij ) is consisting of l users, n Web services and m QoS
Qkij ¼ 0:5 þ ð3Þ attributes. The extraction step is to factorize Q into two matri-
2  3σ
ces C∈Rl×m×r and W ∊ R r×n , which satisfy the following:
b
Where Q ijk is normalized value of k-th QoS attribute, qkij
denotes the average vlue of k-th QoS attribute obtain from all ( )
n o Xr Xr Xr
users, σ is the standard deciation of k-th QoS attribute. Qij ¼ Q1ij ; Q2ij ; …; Qm
ij ≈ cik w1jk cik w2jk ; …; cik wm
jk
Second, assign Q ijk with 0 or 1 based on the distance with 0 k¼1 k¼1 k¼1
or 1, if it is out of the [0,1] interval.It has been proved that ð4Þ
99 % data can be directly mapped to the [0,1] interval (Ortega
et al. 1997).
Where Qij is the multi-QoS performance of Web service sj
observed by user u i , vector c i = [c i1, c i2, …c ir ] reflects the
4.2 Feature extraction feature of user u i , matrix wj = [w 1j ,w j2,…,w jm] reflects the
feature of Web service sj, vector w jd = [w jid ,w j2d ,…,w jrd ] is
Since the multi-QoS attributes reflect the feature of corre- its sub feature, r is the rank of matrix C and W,it generally
sponding invoked Web service and the user, we extract the satisfies (l ×m +n)×r <m ×l ×n.
feature based on the historical QoS experience. To better Based on the following equation, we put multi-QoS attri-
reflect the feature of user, we extract it with multi-QoS attri- bute values together and use NMF algorithm (Lee and Seung
butes together. Due to the existing QoS matrix is always 1999) to learn the feature of Web services. The detail can be
sparse, we employ matrix factorization to extract the features described as follow:
of users. The main idea of this method is to derive a high- First, we put normalized multi-QoS attribute values togeth-
quality low-dimensional matrix to approximate the historical er to form a supermatrix Q * = [Q 1, Q 2, …, Q m ]

Fig. 4 Transform example

148 Inf Syst Front (2014) 16:143–152

Table 1 Detail of QoS data set

Statistics Response time Throughput

Scale 1-20s 1-1000 kbps

Mean 0.910 s 47.386 kbps
Num. Users 339 339
Num. Web Services 5,825 5,825

Second, we decompose the Q* to extract the matrix C and

W with the objective function Minf(C, W) by the following:

X
l m Xn
 
Min f ðC; W Þ ¼ I ij Qih   logðCW Þih −ðCW Þih ð5Þ
h¼1 j¼1

Fig. 6 MAE of response time from different Web services

where Iij is the indicator function that is equal to 1,if user ui
invoked service sj and 0 otherwise. Then,an incremental gra-
feature of users and some personal QoS experience about
dient descent method is employed toextract the feature of Web
a target Web service, the key idea of this step is to learn
service by the following:
a map function with this information, then to predict the
X missing personal QoS by this map function, which rep-
Qih
Cia ¼ Cia wah ð6Þ resents the relation between the user’s feature and multi-
h
ðCW Þih QoS values obtained from that Web service.
For example, there are 7 users and a Web service shown in
Cia Fig. 3. If we have got the extracted feature of all users and
Cia ¼ X ð7Þ collected the QoS experience observed by the usersu 1, u 2, u 3,
C
k ka
u 4u 1, u 2, u 3, u 4, then we can learn a map function f(c) based
on these data, and predicted the miss QoS experience for the
X Qih 
Wah ¼ Wah Cia ð8Þ users u 5, u 6, u 7.
i
ðCW Þih In order to learn the map function, we employ the Multi-
output Support Vector Regression (MSVR for short) algo-
rithm (Yu et al. 2006) to predict the missing multi-QoS values
4.3 QoS prediction
at same time. The MSVR is a widely applied regression
prediction method, which can control the accuracy of approx-
In this step, we predict multi-QoS for different users
imate arbitrary nonlinear function. It not only has the global
based on the extracted feature of users and their histor-
optimum, good generalization ability, but also considers the
ical QoS experience. Consider we have got the extracted
correlation of outputs. It is suitable for predicting the multi-

Fig. 5 MAE of throughput from different Web services Fig. 7 RMSE of throughput from different Web services
Inf Syst Front (2014) 16:143–152 149

Fig. 8 RMSE of response time from different Web services Fig. 10 Computation Time with different number of users

QoS together. The whole predicting process can be described Last, we input the feature of user to predict his personalized
as follow: missing multi-QoS values for a targeted Web service. let c i is
First, we select the training data according to the invoked the feature of user u i , the predicted multi-QoS Q ij for a
experience for a targeted Web service. targeted Web service s j can be calculated by the following:
Suppose there are d usersU ={u 1, u 2, …, u d } have in-
voked a target Web services, then the training data can be Qij ¼ W T φðci Þ þ b ð10Þ
represented byT ={(c 1, y 2), …, (c d , y d )}, where c d ∊ W is the
obtained feature of user u d , y d represents personal QoS expe- 5 Web service selection approach
rience about this Web service, which observed by ud.
Second, we employ MSVR to build a function f, which In this section, we propose a fast match approach to select
represents the relation between the feature of user and Multi- Web services for multi-user based on the predicted multi-QoS
QoS values obtained from a target Web service. Consider R r is values. To better describe it, we first introduce theorem, and
the feature space of users, R m is the QoS space. The function f then give the detail of our fast match approach.
can be described by the following: Theorem 1. For given users’ preference weight and their
 personalized multi-QoS values for candidate Web service, the
f : Rr → Rm
ð9Þ multi-user Web service selection problem can be transformed
xk →W T φðxk Þ þ b to a maximum weight matching problem in bipartite graph.
Where W T φ (x k )+b reflects a map from the feature space of Proof. Consider the maximum weight matching problem,
user to the QoS space, which is learning from the training data defined by a weighted complete bipartite graph G =(U ∪ S, U ×
by MSVR. S ), where edge<i ,j >has weight w i ,j . We wish to find a
matching M from U to S with maximum weight. We show that
the multi-user Web service selection problem can be
transformed to a maximum weight matching problem by adding

Table 2 The effect of the paramter r in term of MAE and D RMSE

Web service QoS Performance r =2 r =4 r =6 r =8

attributes

Web service Response MAE 0.1657 0.1983 0.1836 0.1699

1 Time RMSE 0.2463 0.2773 0.2612 0.2445
Throughput MAE 4.8696 4.8280 5.2849 4.5330
RMSE 6.3578 6.3002 6.8054 6.0105
Web service Response MAE 0.0935 0.0952 0.0882 0.0906
2 Time RMSE 0.2878 0.2879 0.2869 0.2845
Throughput MAE 2.8130 2.9439 3.0751 3.6862
RMSE 3.4430 3.6000 3.8931 4.4909
Fig. 9 Computation time with different number of Web services
150 Inf Syst Front (2014) 16:143–152

virtual Web services according to their processing capacity. 6 Experiment

Given a bipartite graph G =(U ∪ S, U ×S) to represent the users,
services and their utility, if processing capacity of Web service s j To evaluate our methods for the multi-user Web service se-
∊ S is k, we can map it to k virtual Web service which can only lection problem, we conduct several experiments on publicly
service one user. So our problem can be viewed as a maximum available dataset and the synthetic data. In this section, we are
weight matching problem in the new bipartite graph. focusing on the prediction quality of our proposed approach
According to Theorem 1, the multi-user Web service selec- and the efficiency of fast match approach.
tion problem can be transformed to a maximum weight
matching problem in new bipartite graph. For example, if
we select candidate services for three requestors in the left of 6.1 Comparison results on QoS prediction
Fig. 4, the problem can be transform as a maximum weight
matching problem in the right of Fig. 4. Where vs 11 , vs 12 To study the prediction performance on multi-QoS, we con-
represent the virtual Web services, and their number equal to duct several experiments to show the prediction quality of our
the processing capacity of Web service-1. From a matrix point proposed approach on real-world Web service dataset (Zheng
of view, the utility matrix UM become as a new utility matrix et al. 2010). This dataset includes QoS performance of 5,825
NUM by the following: openly-accessible real-world Web services from 73 countries.
The QoS values are observed by 339 distributed computers
NUM ¼ PC  UM ð11Þ located in 30 countries from PlanetLab4. The detail can be
describe as Table 1.
Where PC ={pc 1, …, pc i , …, pc j } is a processing capacity In order to evaluate the performance of our approach, We
matrix of all the candidate Web service, vector pc i represents use Mean Absolute Error (MAE) and Root Mean Squared
the processing capacity of Web service s i . Error (RMSE) as our measurement criteria of prediction ac-
curacy. The metric MAE and RMSE can be calculate by the
following:
X  

 q k
− q e
k 
j ij ij
MAE ¼ ð12Þ
N
vffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
uX
u e
2
t j
q k
ij −q ij k
RMSE ¼ ð13Þ
N

where q ij k is the k-th QoS value of Web service observed by

user u i , qekij denotes the k-th QoS value of Web service would
be observed by this user as predicted by a method, and N is the
number of predicted QoS values. Both the MAE and RMSE
are negatively-oriented scores, Lower values are better.
In this section, we compare the prediction accuracy of our
proposed approach MEQP with single QoS value predict
approaches, including the following methods.
Algorithm 1 shows the whole procedure of our fast
matching approach. The main idea is to respectively calculate 1) UserMean. This method uses the mean QoS value of
the optimal matching Web service for each requester, and each user to predict the missing values.
check load conditions for each Web service, if number of 2) UPCC (User-based collaborative filtering method using
requests for any Web service is greater than the Web service’s Pearson Correlation Coefficient). This method employs
processing capacity, we transform our problem to a maximum PCC to calculate similarities between users and predicts
weight matching problem in a new bipartite graph and employ QoS value based on similar users (Shao et al. 2007;
the Kuhn-Munkres algorithm (KM for short) to select the Breese et al. 1998).
global optimal solution and avoid requests overloading. For 3) IPCC (Item-based collaborative filtering method using
time complexity of FMA, good behavior is O (n ×m), and bad Pearson Correlation Coefficient). This method employs
behavior is O (max{n , |P |}4), where n is the number of PCC to calculate similarities betweenWeb services and
requesters, m is the number of Web services, |P| is sum of predicts QoS value based on similar items (item refers to
all Web service’s processing capacity. Web service in this paper) (Resnick et al. 1994).
Inf Syst Front (2014) 16:143–152 151

To make our experiment more realistic, we randomly re- We random select two Web services with two QoS attri-
move 85 % multi-QoS experience of users and only use the butes (Response time and Throughput) in the experiment.
remaining 15 % entries to predict the removed multi-QoS Table 2 shows the following: 1) for the Response time attri-
experience of different user for a targeted Web service (which bute, the MAE and RMSE of our appraoch is very low with
is chosen by random). In this part, the above methods are differnet r values. This observation indicates that our QoS
compared with our proposed approaches given the same train- prediction appraoch is very good for predicting the Response
ing and test cases. The parameter settings of our proposed time attribute of Web services; 2) Our appraoch is also suitable
approaches are r =4, ε =0.02, C =678, σ =0.5. to preidct the Throughtput of Web servcies.
Figures 5, 6, 7 and 8 show the experimental results of
different approaches. From those figures, we can observe that
our approach can obtain smaller MAE and RMSE on both two 7 Conclusion
QoS attributes. It shows that our approach has better perfor-
mance on prediction accuracy on both response-time and In this paper, we propose a new framework for multi-user Web
throughput for different users. This indicates that our approach services selection problem. This framework first predicts the
suits better for predicting the personalized multi-QoS for missing multi-QoS values according to the historical QoS
different users. experience from different users, and then selects the global
optimal solution for multi-user by our fast match approach.
Comprehensive empirical studies demonstrate the utility of
6.2 Comparison results on service selection
the proposed approach.
To study the efficiency of Web service selection, we compare Acknowledgments The work presented is supported by the NSFC
our Web service selection approach, i.e., fast match approach (61202435); NSFC (61272521); Natural Science Foundation of Beijing
(FMA) with GOSSMR (Kang et al. 2011) in term of the under Grant No.4132048; Specialized Research Fund for the Doctoral
computation time. GOSSMR is a very famous Web service Program of Higher Education under Grant No. 20110005130001; Pro-
gram for New Century Excellent Talents in University of China under
seleciton appraoch and it employes a 0–1 integral program- Grant No.NCET-10-0263; Innovative Research Groups of the National
ming model to solve problem of optimal service selection for Natural Science Foundation under Grant No.61121061; and 863
multiple requesters). In the first experiment, we will investi- (2012AA111601).
gate how the execution time of following approach with the
number of candidate Web service increases. We varied the
number of candidate Web services from 10 to 60 with an
increment of 10, but fixed the number of requests is 40. The References
results of this experiment are presented in Fig. 9. It can be seen
that the computation time of FMA is less than the GOSSMR
Zeng, L., Benatallah, B., Dumas, M., Kalagnanam, J., Sheng, Q. (2003).
with different number of Web service. Quality-driven Web services composition. Proc. the 12th Interna-
In the second experiment, we will investigate how the tional Conference on the World Wide Web, pp.411–421.
execution time of following approach with the number of Zeng, L., Benatallah, B., Ngu, A.H.H., Dumas, M., Kalagnanam, J.,
Chang, H. (2004). QoS-aware middleware for Web services com-
candidate Web service increases. We vary the number of users
position, vol. 30, no.5. IEEE Transaction on Software Engineering,
from 10 to 60 with an increment of 10, but fixed the number of IEEE Computer Society, pp. 311–327.
candidate Web service is 100. The results in Fig. 10 display Canfora, G., Penta, M.D., Esposito, R., Villani, M.L. (2005). An ap-
that the computation time of FMA is less than the GOSSMR proach for QoS-aware service composition based on genetic algo-
rithms. Proc. the 2005 conference on Genetic and Evolutionary
with different number of users.
Computation, pp.1069–1075.
Based on the above two experiments, the conclusions can Alrifai, M., Risse, T. (2009). Combining global optimization with local
be drawn: 1) our fast match approach can scalable with change selection for efficient QoS-aware service composition. Proc. the
number of users and Web services; 2) compare with 18th International Conference on the World Wide Web, pp.881–890.
Alrifai, M., Skoutas, D., Risse, T. (2010). Selecting skyline services for
GOSSMR algorithms, our approach can spend less time to
QoS-based Web service composition. Proc. the 19th International
search a global solution; 3) our approach can meet the Web Conference on the World Wide Web, pp.11–20.
service selection for multi-users. Shahand, S., Turner, S. J., Cai, W., & Khademi, H. (2010). DynaSched: A
dynamic Web service scheduling and deployment framework for data-
intensive Grid workflows. Procedia Computer Science, 1(1), 593–602.
6.3 Effect of the parameter r Dyachuk, D., Deters, R. (2006). Scheduling of composite web services.
On the move to meaningful internet systems 2006: OTM 2006
Workshops, pp. 19–20.
Table 2 shows the effect of the r for our QoS prediction. To Kang, G., Liu, J., Tang, M., Liu, X., Fletcher, K.K. (2011) Web service
show its impact clearly, we vary the value of r from 2 to 8 with selection for resolving conflicting service requests. Proc. IEEE
a step value of 2. International Conference on Web Service, pp. 387–394.
152 Inf Syst Front (2014) 16:143–152

Lo, W., Yin, J., Deng, S., Li, Y., Wu, Z. (2012) .An extended matrix Sciences, The Computer Journal, IET Software, IJSS, JNCA, IEEE IC,
factorization approach for QoS prediction in service selection. Proc. International Journal of Web and Grid Services, etc.. URL: www.
IEEE Ninth International Conference on Services Computing sguangwang.com.
(SCC), pp. 162–169.
Shao, L., Zhang, J., Wei, Y., Zhao, J., Xie, B., Mei, H. (2007) Ching-Hsien Hsu is presently a visiting scholar in department of com-
Personalized QoS prediction for Web services via collaborative puter science at Virginia Tech. He is a professor in department of com-
filtering. proc. IEEE International Conference on Web Services, puter science and information engineering at Chung Hua University,
pp.439–446. Taiwan; and distinguished chair professor in school of computer and
Zheng, Z., Ma, H., Lyu, M.R., King, I. (2009). WSRec: A collaborative communication engineering at Tianjin University of Technology, China.
filtering based web service recommendation system. Proc. IEEE His research includes high performance computing, cloud computing,
International Conference on Web Services, pp.437–444. parallel and distributed systems, ubiquitous/pervasive computing and
Jiang, Y., Liu, J., Tang, M., Liu, X.F. (2011). An effective Web intelligence. He has published 200 papers in refereed journals, conference
service recommendation method based on personalized collab- proceedings and book chapters in these areas. He has been involved in
orative filtering. Proc. IEEE International Conference on Web more than 100 conferences and workshops as various chairs and more
Services, pp.211–218. than 200 conferences/workshops as a program committee member. He is
Zhang, L., Zhang, B., Liu, Y., Gao, Y., Zhu, Z. (2010). A Web the editor-in-chief of international journal of Grid and High Performance
service QoS prediction approach based on collaborative filter- Computing, and serving as editorial board for around 20 international
ing. Proc. IEEE Asia-Pacific Services Computing Conference, journals. He has been acting as an author/co-author or an editor/co-editor
pp.725–731. of 10 books from Springer, IGI Global, World Scientific and McGraw-
Chen, X., Liu, X., Huang, Z., Sun, H. (2010). RegionKNN: a scalable Hill. He has also edited a number of international journal special issues as
hybrid collaborative filtering algorithm for personalized Web a guest editor, such as IEEE Transactions on Services Computing, Future
service recommendation. Proc. IEEE International Conference Generation Computer Systems, Journal of Supercomputing, Concurrency
on WebServices, pp.9–16. and Computation: Practice and Experience, The Knowledge Engineering
Tang, M., Jiang, Y., Liu, J., Liu, X. (2012). Location-aware collaborative Review, Internet Research, Information System Frontiers, etc. He was
filtering for QoS-based service recommendation. Proc. IEEE Inter- awarded 5 times annual outstanding research award through 2005 to 2012
national Conference on Web Services, pp.202–209. and a distinguished award in 2008 for excellence in research from Chung
Ortega, M., Rui, Y., Chakrabarti, K., Mehrotra, S., Huang, T.S. (1997) Hua University. He has been serving as executive committee of Taiwan
Supporting similarity queries in MARS. proc. the ACM Multimedia, Association of Cloud Computing (TACC) from 2008-2011; executive
pp.403–413. committee of the IEEE Technical Committee of Scalable Computing
Lee, D. D., & Seung, H. S. (1999). Learning the parts of objects by non- (2008-2011). He is member of Phi Tau Phi Scholastic honor society;
negative matrix factorization. Nature, 401(6755), 788–791. IEEE senior member; regional director of the Future Technology Re-
Yu, S. P., Yu, K., & Volker, T. (2006). Multi-output regularized feature search Association (FTRA); and standing director of Taiwan Association
projection. IEEE Transactions on Knowledge and Data Engineer- of Cloud Computing (TACC).
ing, 18(12), 1600–1613.
Zheng, Z., Zhang, Y., Lyu, M. (2010). Distributed QoS evaluation for
real-world Web services. Proc. IEEE International Conference on Zhongjun Liang is a Ph.D. Students at the State Key Laboratory of
Web Services, pp.83–90. Networking and Switching Technology, Beijing University of Posts and
Breese, J., Heckerman, D., Kadie, C. (1998). Empirical analysis of Telecommunications (BUPT). His research interests include Service
predictive algorithms for collaborative filtering. Proc. the Fourteenth computing and Web services.
conference on Uncertainty in artificial intelligence, pp.43–52.
Resnick, P., Iacovou, N., Suchak, M., Bergstrom, P., Riedl, J., (1994) Qibo Sun received his Ph.D. degree in communication and electronic
GroupLens: An open architecture for collaborative filtering of system from the Beijing University of Posts and Telecommunication in
netnews. Proc. the 1994 ACM conference on Computer supported 2002. He is currently an associate professor at the Beijing University of
cooperative work, pp.175–186. Posts and Telecommunication in China. He is a member of the China
computer federation. His research interests include services computing,
Internet of things, and network security.
Shangguang Wang is an assistant professor at the State Key Laboratory
of Networking and Switching Technology, Beijing University of Posts Fangchun Yang received his Ph.D. degree in communication and electron-
and Telecommunications (BUPT). He received his Ph.D. degree at BUPT ic system from the Beijing University of Posts and Telecommunication in
in 2011. His PhD thesis was awarded as outstanding doctoral dissertation 1990. He is currently a professor at the Beijing University of Posts and
by BUPT in 2012. His research interests include Service Computing, Telecommunication, China. He has published 6 books and more than 80
Cloud Services, QoS Management. He has served as reviewers for papers. His research interests include network intelligence, services comput-
numerous journals, including IEEE Transactions on Parallel and Distrib- ing, communications software, soft switching technology, and network
uted Systems, IEEE Transactions on Services Computing, Information security. He is a fellow of the IET.