TELKOM
NIKA
, Vol.12, No
.4, Dece
mbe
r
2014, pp. 10
53~106
3
ISSN: 1693-6
930,
accredited
A
by DIKTI, De
cree No: 58/DIK
T
I/Kep/2013
DOI
:
10.12928/TELKOMNIKA.v12i4.786
1053
Re
cei
v
ed Se
ptem
ber 2, 2014; Re
vi
sed
Octob
e
r 15, 2
014; Accepte
d
No
vem
ber
4, 2014
A Reliable Web Services Selection Method for
Concurrent Requests
Guiming Lu*, Yan Hai, Yao
y
ao Sun
Coll
eg
e of Information En
gi
ne
erin
g, North Ch
ina U
n
ivers
i
t
y
of W
a
ter
Reso
urces an
d
Electric Po
w
e
r
,
Z
hengzho
u, 4
500
00, Ch
ina
*Corres
p
o
ndi
n
g
author, e-ma
i
l
: lgm@nc
w
u
.
e
du.cn
A
b
st
r
a
ct
Current
meth
o
d
s of service s
e
lecti
on b
a
sed
on qu
a
lity of service (QoS) u
s
ually foc
u
s on
a singl
e
service
req
ues
t at a
ti
me,
or
let th
e
users
in
a
w
a
itin
g
que
ue
w
a
it for
W
eb s
e
rvices
w
hen
the
sa
me
function
al W
e
b
service has
more than
one r
equ
ests
, and then ch
oos
e the W
eb service
w
i
th the best Qo
S
for the curr
ent
requ
est accor
d
in
g to its ow
n
nee
ds. Ho
w
e
ver, there
are
mu
ltipl
e
serv
ic
e req
uests for
the
same functio
n
a
l w
eb service
at a time in pr
actice
an
d w
e
cann
ot choos
e
the best service for users every
time
b
e
caus
e
of the s
e
rvic
e
’
s lo
ad.
T
h
is
p
a
per
ai
ms
at so
l
v
ing
the W
e
b
Services
sel
e
ction
for co
ncurr
ent
requ
ests a
nd
deve
l
op
in
g a
glo
bal
o
p
ti
mal
sel
e
ction
met
hod
for
multip
l
e
si
mi
lar
servi
c
e re
quest
e
rs
to
opti
m
i
z
e
the
s
ystem r
e
so
urc
e
s. It prop
ose
s
the
i
m
prov
e
d
soc
i
al
co
gnit
i
ve (ISCO)
alg
o
rith
m w
h
ic
h u
s
es
gen
etic al
gorit
hm for
obs
ervation
al l
earn
i
ng a
nd
us
es
devi
a
ting
de
gree to
eval
u
a
te the so
luti
on.
F
u
rthermore, t
o
en
ha
nce th
e
efficiency
of ISCO, the el
it
e st
rategy is
use
d
in ISCO a
l
gor
ithm. W
e
eva
l
ua
te
perfor
m
a
n
ce
of the ISCO al
go
rithm
an
d the
selecti
on
meth
od thro
ug
h si
mulati
ons. T
he s
i
mulati
on r
e
su
lts
de
mo
nstrate th
at the ISCO is valid for o
p
ti
mi
z
a
t
i
o
n
prob
l
e
ms w
i
th discr
ete dat
a a
nd
mor
e
effective
than
ACO and GA
.
Ke
y
w
ords
:
w
eb service se
lec
t
ion, ISCO, deviatin
g
de
gree
1. Introduc
tion
With the
dev
elopme
n
t of
cloud
com
puti
ng te
chn
o
log
y
and Sa
aS
model, m
o
re
and m
o
re
Web
se
rvices are
used
un
der th
e cl
oud
enviro
n
ment
. In su
ch
ope
n and
dynam
ic envi
r
onm
e
n
t,
however, the
r
e are u
s
ually
many W
eb
service
s
i
n
sta
n
c
e
s
with si
milar fun
c
tion
bu
t great
differe
nt
perfo
rman
ce.
How to
cho
o
s
e the hi
gh q
uality servi
c
e
s
whi
c
h
are
most satisfie
d for users from
the vast a
m
o
unts
of Web
servi
c
e
s
, ha
s be
come
on
e
of the
hot i
s
sues in th
e
research
of
se
rvice
comp
uting an
d clou
d com
p
uting field .
Current method
s of servi
c
e selectio
n us
u
a
lly focus on a single
servi
c
e requ
est at a
time, or the
selectio
n of a
servi
c
e
with the be
st
QoS
at the user’
s
own
discretio
n
, or let the
u
s
ers
in a waitin
g
queu
e wait f
o
r Web
se
rvice
s
when
th
e sam
e
fun
c
tionality of a Web
se
rvice
ha
s
more than one
servi
c
e
request [1],[2], and then
ch
oose the
best Web
se
rvice for the
current
requ
est. T
h
is
method
do
es
not take th
e f
o
llowin
g
situa
t
ion into
a
c
co
unt whe
r
e th
e
r
e
are
multipl
e
u
s
er
r
e
qu
es
ts
for
a
W
e
b
s
e
r
v
ic
e a
t
the
sa
me time
. In
s
u
c
h
s
i
tua
t
io
n
,
co
n
f
lic
ts
occ
u
r
w
h
en to
o
many reque
st
ers sele
ct the
sam
e
b
e
st
web
servi
c
e
be
cau
s
e
the lo
a
d
cap
a
city of
each
se
rvice
i
s
limited. This
i
s
likely to lea
d
that
the re
q
ueste
d servi
c
e’s Q
o
S is re
duced, an
d t
he enti
r
e
service
system
cra
s
h
and the users’ nee
ds
can
not be met.
In additio
n
, di
fferent
Web
service
u
s
e
r
s
have diffe
rent
QoS
attribut
e p
r
eferen
ce.
So
we
don't
need
t
o
choo
se
th
e be
st
se
rvice for ea
ch
u
s
er.
The
co
mpetition a
n
d
conflict
am
ong
different users for the sa
me se
rvice
may lead to
the followin
g
situation
s
: Some Web
serv
ice
s
whi
c
h can satisfy use
r
s’ Q
o
s re
quiremen
t
s are u
n
u
s
ed
and so
me hi
gh QoS Web
servi
c
e
s
serv
e
the u
s
e
r
s wit
h
lo
w Q
o
S
re
quire
ment
s, b
u
t so
me
users
with hi
ghe
r
QoS requi
re
ments will
be
in
the
long tim
e
waiting
state
becau
se it t
e
mporarily
can
not get
the
hi
gh Q
o
S
se
rvice, a
n
d
thu
s
will
certai
nly cau
s
e uneve
n
di
stributio
n an
d waste of
the se
rvice re
sou
r
ces, affe
cting the ove
r
all
perfo
rman
ce
of the servi
c
e syst
em. As you can see
,
when many
use
r
s
call
th
e same
se
rvice,
the service’s
QoS and act
ual load
capacity will
r
educe. Therefore, in orde
r to
make the
higher
QoS se
rvice
can
be u
s
ed
most effectiv
ely and the
se
rvice
s
satisfi
ed u
s
ers’ n
e
e
d
not to be id
le,
effective
serv
ice sele
ction
method
s sho
u
ld
be
ad
opt
ed. At the
sa
me time it
ca
n maximize t
h
e
u
s
er
's
o
v
er
a
l
l s
a
tis
f
a
c
tion
as
fa
r as
po
ss
ib
le
, an
d gu
arantee
se
rvice
load
bala
n
ci
ng, an
d imp
r
o
v
e
the overall pe
rforma
nce
of the servi
c
e sy
stem.
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 12, No. 4, Dece
mb
er 201
4: 105
3 – 1063
1054
From the a
bove re
sea
r
ch situatio
n, the
existing servi
c
e selectio
n method ra
rely
con
s
id
ers th
e load bal
an
cing p
r
obl
em
. This pap
er
mainly studi
es ho
w to solve the con
f
lict
situation of the co
ncu
r
ren
t
service req
uest
s
, and propo
se
s a reli
able Web se
rvice
s
sel
e
cti
o
n
method for
concurrent re
que
sts.
Beca
use that the
optimal so
l
u
tion of the con
c
u
r
rent Web
serv
i
c
e
req
u
e
st
s i
s
a
set
of
se
rv
ice
s
seq
uen
ce
nu
mber
wh
ose
value is
discrete
data, a
nd
traditional
so
cial cognitive
optimization
only applie
s to contin
uou
s data. So this pape
r uses t
he
minimum val
ue of the deviating degre
e
which is
th
e deviation o
f
the candida
te Web se
rvi
c
e
s
’
QoS value
wi
th con
c
u
r
rent
req
u
e
s
ts’ Q
o
S con
s
trai
nts as th
e obj
ect
i
ve function,
and d
e
si
gn
s
an
improve
d
social co
gnitive
algorith
m
whi
c
h u
s
e
s
g
e
n
e
tic alg
o
rithm
for ob
se
rvation lea
r
nin
g
to
solve the
se
rvice optimi
z
a
t
ion problem.
And thu
s
ba
lance service
re
sou
r
ces
, i
m
prove
syste
m
perfo
rman
ce
and better m
eeting the effi
cien
cy of We
b servi
c
e sele
ction.
2. Related Work
With the
cont
inuou
s d
e
velopment of
cl
oud
comp
uting technol
og
y and the
wi
despre
a
d
use
of a la
rg
e numb
e
r
of Web
se
rvice
s
on the n
e
tw
o
r
k, the i
n
crea
se of the
nu
mber
ha
s bro
ught
great
conven
ience for software
develo
pers, but
m
ean
while ma
ke
s them fa
ce the
servi
c
e
informatio
n o
v
erload
p
r
obl
em. Ho
w to
provide
the
u
s
er with
the
approp
riate Web
service has
become a g
r
e
a
t challe
nge f
o
r develo
p
e
r
s.
In
rece
nt
years, the
Q
o
S
attribute
ha
s be
en
co
nsid
ered
in the
re
se
arch of
the
Web
se
rvice sel
e
ctio
n
field. Now some re
s
e
a
r
che
r
s ma
ke
rese
ar
ch o
n
a single
use
r
requ
est
s
a
functio
nal
We
b service b
a
s
ed
on
QoS
attribute, a
nd p
r
op
osed
som
e
servi
c
e
sele
ction
met
hod. Z
eng
et
al [3]
pre
s
e
n
t a mi
ddle
w
are
platform f
o
r
com
p
o
s
itio
n exp
r
e
s
sed
as
utility
functions over QoS
attr
ibutes, and using integer
progr
am
ming m
a
ke users
get the
best
Web
se
rvice
s
they need, maximize
s u
s
er satisfa
c
tio
n
. Liu, Anne, Ngu a
nd Ze
n
g
[4] propo
se
d a
QoS comp
utation
a
nd poli
c
ing
in dyna
mic we
b se
rvice
s
selection. In this way,
it transform
s
the
probl
em of service
comp
o
s
ition into a mixed
integer linear proble
m
and use
r
s can obtai
n their
best needed
servi
c
es. Yu and Lin [5],[6] proposed a
service sel
e
ction sy
stem with end-to-end
QoS co
nstrai
nts and p
u
t forwa
r
d a al
gorithm b
a
se
d on Multiple
Choi
ce Kna
p
sa
ck Probl
e
m
(MCKP) an
d
Multi-dime
nsi
on Multi
-
choi
ce
0-
1K
nap
sack Problem
(MMKP).Maxi
m
ilien a
nd Si
ngh
raised a
n
ind
epen
dent service sel
e
ctio
n
architectu
re based
on se
rvice
age
nt
in the
literature [7],
and
con
s
ide
r
ed the
cre
d
ib
ility of the service in th
e li
terature [8]. In the mod
e
l
of Danilo
an
d
Barba
r
a p
r
o
p
o
se
d [9], the local
and
gl
obal
con
s
trai
nts can b
o
th
be spe
c
ified
and they al
so
prop
osed opti
m
izing fo
rmul
a to make glo
bal optim
ization, without prior
to optimize each possi
ble
executio
n p
a
ths. In [1
0
], mixed integer p
r
og
ra
mming
wa
s utilize
d
to
find the
o
p
timal
decompo
sitio
n
from
QoS
global
co
nst
r
aints to
local
co
nstraints, and used
a
distrib
u
ted
l
o
cal
sele
ction to
find the
be
st
Web
service
whi
c
h
can
satisfy the lo
cal
con
s
trai
nts, a
nd then
p
r
op
ose
d
the local
opti
m
ization
and
enume
r
ation
method. Th
i
s
se
rvice co
mpositio
n me
thod de
sign
e
d
to
filter the
can
d
idate
s
of e
a
c
h ta
sk throu
gh lo
cal
co
nstraints, to
red
u
ce
the n
u
m
ber
of candi
d
a
te
servi
c
e
s
a
n
d
improve service q
uality, and
enum
erate all
com
p
ositing
solutions to find t
h
e
optimal o
ne.
Appro
a
che
s
prop
osed i
n
[
11] an
d [
12]
aim to
sele
ct
We
b servi
c
e
s
for u
s
ers ,
but
these existing
se
rvice
s
sele
ction studie
s
only
fo
cu
s o
n
a si
ngle
se
rvice
req
u
e
s
t a
function
al type
of Web servi
c
e, or is inte
nded to find
an e
ffective method to solve the co
mposite
se
rvice
sele
ction mo
del they prop
ose
d
.
The ab
ove m
e
thod
s do
no
t con
s
ide
r
th
e ca
se
wh
ere many u
s
e
r
s co
n
c
urre
ntly reque
st
the same fu
n
c
tion
We
b service at the
sa
me time. Alth
ough [1
3] an
d
[14] co
nsi
d
e
r
the con
c
u
rre
n
t
servi
c
e req
u
e
sters req
u
e
s
t
the same
servi
c
e at
the sa
me time,
the solution
is only to l
e
t the
multiple req
u
e
sters to wai
t
in the line
of queue in
the event of confli
ct. In fa
ct, beca
u
se the
different
req
u
e
sts have
diff
erent
QoS
co
nstrai
nts,
m
u
l
t
iple con
c
u
rre
nt re
que
sts can b
e
assign
ed
to multiple
se
rvice
s
simulta
neou
sly. In o
r
der
to avoid
t
he
Web
servi
c
e
overlo
adin
g
, and
imp
r
ov
e
the perfo
rma
n
ce
of the ov
erall
system.
This p
ape
r p
r
opo
se
s a reli
able
servi
c
e
sele
ction m
e
thod
for the pro
b
le
m of con
c
urre
nt us
ers requ
est for the Web se
rvice
s
.
3. The descri
p
tion of
Web
serv
i
ces selection for co
ncurre
nt req
u
ests
Web
servi
c
e QoS guideli
nes mai
n
ly include co
st, response tim
e
, service availability,
servi
c
e
relia
b
ility, and Succe
ssful
Rate,
etc. Ge
ne
ral
We
b servi
c
e
sele
ction
me
thods are giv
en
belo
w
. Assu
ming th
at th
e set of
ca
n
d
idate
We
b
servi
c
e
s
whi
c
h
ca
n
sati
sfy use
r
fu
ncti
onal
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
A Reliable
Web Services
Selection M
e
t
hod for Con
c
urrent Re
que
sts (Guim
i
ng Lu)
1055
requi
rem
ents alrea
d
y exists, and the
r
e
are n
We
b
servi
c
e
s
me
eting u
s
er
d
e
mand th
rou
gh
function m
a
tches. Th
e Qo
S attribute se
ts
of the can
d
idate Web
service
s
i
s
:
1
,
...,
,
...
ik
qq
q
.
Gene
ral Web
services
sele
ction process can
be divid
ed into the followin
g
main steps:
(1)
QoS Standardizatio
n
of Ca
ndidate
W
eb servi
c
e
s
and con
c
u
r
rent
re
que
sts
Web
service
QoS attrib
utes
can
be
di
vided
into t
w
o types [1
5]: One i
s
th
e
positive
criteria, i.e., the greater the value
the better its qualit
y, such as re
l
i
ability, availability, credibili
ty,
etc.; anoth
e
r
is n
egative
criteria,
i.e., the greate
r
the
value the
po
ore
r
the
quali
t
y, for examp
l
e,
rea
c
tion
time
and
cost
an
d so o
n
. To
make
the
Web
se
rvice
Q
o
S value
s
co
mparable, it i
s
necessa
ry to stand
ardi
ze
a
ll the QoS attribute valu
es
that all the Q
o
S values
are co
nverted i
n
to
a unified val
ue interval.
Comm
only u
s
ed Q
o
S sta
ndardization
formula h
a
s
the followin
g
tw
o
kind
s:
the positive o
nes a
s
defin
e
d
in (1):
mi
n
ma
x
m
i
n
ma
x
m
i
n
ma
x
m
i
n
0
(1
)
11
ij
j
jj
jj
ij
jj
QQ
if
Q
Q
QQ
V
if
Q
Q
(1)
the negative
one
s as d
e
fin
ed in (2
):
ma
x
ma
x
m
i
n
ma
x
m
i
n
ma
x
m
i
n
0
(2)
10
ji
j
jj
jj
ij
jj
QQ
if
Q
Q
QQ
V
if
Q
Q
(2)
In the formula (1) an
d (2
),
ma
x
j
Q
is the maximum of the j-th attribute in the mass ma
trix,
ma
x
()
,
1
ji
j
QM
a
x
Q
i
n
;
mi
n
j
Q
is the minimum of the
j-th attribut
e in the ma
ss m
a
trix,
mi
n
()
,
1
ji
j
QM
i
n
Q
i
n
. By
formula
(1) a
nd (2) can put all Qo
S values to the uniform value
interval, an
d
norm
a
lized
Q
o
S value
s
ind
i
cate th
at the
greate
r
th
e v
a
lue th
e b
e
tter the
qu
ality. By
the metho
d
s
of attribute v
a
lue
stan
dardizatio
n
, unifi
ed the
directi
on of th
e Q
o
S values,
ma
ke
s
for a Web
se
rvice QoS ev
aluation ha
s
the sci
entif
ic nature a
nd rationality. Similarly, for QoS
con
s
trai
nts of
user
req
u
e
s
ts to do the sa
me stand
ardi
zation.
(2) Mat
hemat
ical mod
e
l for global optim
al
Web
se
rvice
s
sele
ction n
eed to m
a
ke
choi
ce
s fo
r
each con
c
urrent user
a candid
a
te
Web
service
s
. In o
r
de
r to
maximize
th
e satisf
a
c
tion
of users a
n
d
optimi
z
e th
e depl
oymen
t
of
Web
se
rvice
s
re
sou
r
ce
s, the proble
m
s nee
d to be solved i
s
how to a
ssi
g
n
requ
est
s
Web
servi
c
e, ma
ki
ng the devia
ting degree
minimal
bet
ween ea
ch
ca
ndidate
servi
c
e
s
and thei
r
corre
s
p
ondin
g
requ
est
s
. Selectio
n mod
e
l sho
w
n in Fi
gure 1:
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 12, No. 4, Dece
mb
er 201
4: 105
3 – 1063
1056
Figure 1. Selection mo
del
of candi
date
servi
c
e
s
and
requ
est
s
Suppo
se n
repre
s
e
n
ts th
e numb
e
r
of W
eb
se
rvices, m rep
r
e
s
ent
s the n
u
m
ber
of
requ
est
s
, an
d
nm
. The user prefe
r
en
ce f
o
r QoS attri
b
utes i
s
)
W
W
W
k
W
,....,
2
，
1
(
, and
1
1
k
i
i
W
. So the global optimal m
a
thematical model
for
co
ncu
r
rent user reque
sts
with QoS
con
s
trai
nts can be defin
ed
as:
The obje
c
tive
function:
()
(
3
)
1
(
)
(
)
+
(
)
+
..
..
.+
(
)
11
1
2
2
2
m
Mi
n
D
e
v
R
W
S
ij
i
De
v
R
W
Sr
q
w
r
q
w
r
q
w
i
j
i
j
i
j
ik
jk
k
(3)
()
ij
D
ev
R
W
S
sho
w
s the
Q
o
S deviating
degree
between
th
e i-th
reque
sts an
d
the j-th
can
d
idate Web se
rvice.
Whe
r
e
ik
r
is th
e k-th QoS a
ttribute con
s
t
r
aint value fo
r the i-th use
r
requ
est
s
,
j
k
q
is the
k-th
QoS attrib
ute con
s
trai
nt value fo
r t
he j
-
th
can
d
i
date
se
rvice
,
kn
k
k
WS
WS
W
S
,....,
2
，
1
is
a s
o
lution,
i.e.,
kn
k
k
WS
WS
W
S
,....,
2
，
1
is
offered respec
tively to
m
R
R
R
,....,
2
1
，
. Ne
ed to
be
a
w
are of
is
the attribute value
s
in form
ula are
stand
ardi
zed, valu
es
betwee
n
0
-
1.
As the sol
u
tion of the Web se
rvice selectio
n for the co
ncurren
t
reque
sts i
s
a set of
seq
uen
ce nu
mber, an
d the seq
uen
ce
numbe
r belo
ngs to the di
screte data i
s
sue
s
. This p
ape
r
for this p
r
oble
m
usin
g gen
e
t
ic algo
rithms to obse
r
vatio
nal learning,
at the same ti
me, usin
g elite
reserve
d
stra
tegy, pro
p
o
s
ed a
n
im
prov
ed
so
cial
co
g
n
ition al
gorith
m
(ISCO) to
solve th
e
abo
ve
optimizatio
n probl
em.
4. Ser
v
ice selection meth
od based o
n
ISCO
Given the e
v
olutionary
algorith
m
wit
h
advantag
e
s
of parallel
computin
g, group
optimizatio
n,
doe
s not
nee
d to p
r
ovide i
n
formatio
n
a
s
so
ciated with appli
c
at
ion b
a
ckgroun
d,
et
c.,
so a vari
ety of evolution
a
ry algo
rithm
s
ca
n be u
s
ed to solve
the pro
b
lem
of Web
servi
c
e
sele
ction b
a
sed on QoS. T
h
is pa
per p
r
o
poses a
n
imp
r
oved soci
al cog
n
ition alg
o
rithm (ISCO
)
to
solve the ab
o
v
e optimizatio
n probl
em.
4.1. Impro
v
e
m
ent of the
social cognitiv
e
algorithm
1)Th
e use of geneti
c
algo
ri
thm:
Geneti
c
Algo
rithm (GA
)
simulates th
e
pro
c
e
ss of
natural sel
e
ction
a
nd biologi
cal
evolution by
comp
uter, an
d sea
r
che
s
th
e relatively
o
p
timal sol
u
tio
n
throu
gh survival of the fittest
mech
ani
sm. It adopts glo
bal parallel o
p
timiza
tion
search meth
o
d
, and doe
s not depend
on
gradi
ent info
rmation, ha
s the global
sea
r
ch ab
ilit
y. Compared
with traditio
nal optimization
method
s, it is simpl
e
to u
s
e, with g
ood
global
se
arch
ability and
other
ch
ara
c
te
ri
stics, and
is
o
ne
of the most effective ways t
o
so
lve the o
p
timization p
r
oblem today.
Since S
C
O
a
l
gorithm i
s
b
a
se
d on
the
fiel
d se
arch,
and the
opti
m
ization
prob
lem with
contin
uou
s
solution
sp
ace
within
the
scop
e of it
s
search
rul
e
s, i
t
doe
s n
o
t a
pply to
solve
the
probl
em
s of discrete
solut
i
on sp
ace. ISCO alg
o
rithm
resp
ectively use
s
cro
s
sover and m
u
tatio
n
operator of
g
enetic alg
o
rit
h
m for le
arni
n
g
ag
ents
an
d
the ne
w solution o
b
taine
d
t
h
rou
g
h
imitation
learni
ng. After ea
ch
cro
s
so
ver an
d muta
tion ope
ratio
n
s
i
s
pe
rforme
d, sele
ct b
e
tter
solutio
n
bo
th
before a
nd a
fter the operation ca
n
ma
ke search
sp
ace exp
a
n
s
io
n,
the rapid i
n
crea
se solving
rang
e diversit
y, at
the sam
e
time avoiding the local o
p
timum.
The
se
rvice
option
s
of
this al
go
rithm nee
d t
o
dete
r
mine
the chrom
o
som
e
rep
r
e
s
entatio
n, the calculation of fitne
ss fu
nctio
n
,
as
well a
s
t
he cro
s
sover and m
u
tation
operation
s
, e
t
c. Each
chro
moso
me is
repre
s
e
n
ted a
s
a Web
service sol
u
tion,
namely a Web
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
A Reliable
Web Services
Selection M
e
t
hod for Con
c
urrent Re
que
sts (Guim
i
ng Lu)
1057
servi
c
e
se
qu
ence ide
n
tity, comp
osed
by a n
u
m
ber
of ge
ne
tic lo
ci. Each ge
ne p
o
si
tion
corre
s
p
ond
s t
o
service id
e
n
tification; th
e value
of th
e i-th
gen
e bi
t is the
num
b
e
r of th
e
se
rvice
sele
cted
by the i-th
req
u
e
s
t in the
can
d
i
date set of
service
s
. Th
e fitness fun
c
tio
n
is the
devia
ting
degree in 5.
5.Cro
s
sove
r operation is t
o
take a cro
s
sover meth
od to two ch
romo
som
e
s
(two
different ki
nd
s of service compo
s
ition
schem
e)
while
mutation op
eration i
s
to
cha
nge th
e valu
e
of certain g
e
n
e
s bits in the
s
e two ch
rom
o
some, resulting in two ne
w chro
mo
some
s.
2)Th
e use of elite strategy:
GA gen
es d
o
not
ne
ce
ssarily
refle
c
t
the tru
e
n
a
t
ure of th
e
probl
em to
b
e
solved,
becau
se the cro
s
sove
r an
d mutation o
perato
r
s co
ul
d lead to the best individu
al of the current
popul
ation lo
st in the
ne
xt generation
,
and th
i
s
p
henom
eno
n
will cy
clically appe
ar i
n
t
he
evolutiona
ry
pro
c
e
ss.
So
it can
not
rea
c
h th
e p
u
rp
o
s
e
of cumula
ting better g
enetic,
but m
a
y
unde
rmin
e a
good
combin
ation, an
d
ca
nnot
conve
r
g
e
to th
e gl
ob
al optim
um.
For
elite
strat
egy,
the elite individual (the b
e
st individual
appea
red so
far in the
evolutiona
ry pro
c
e
s
s) dire
ctly
copi
ed to the next gene
ration inste
a
d
of matc
hing
and cro
s
so
ver, and can
avoid the b
e
st
individual bei
ng de
stroyed
for hybrid o
p
e
r
ation.
The elite
st
ra
tegy [16] (M
a
i
nt
ain the
be
st solution
fo
und
over tim
e
befo
r
e
sel
e
ction) is
put forward b
y
De Jong fo
r the geneti
c
a
l
gorithm.
Fo
r
Geneti
c
alg
o
rithms, the abi
lity to converge
to the global
optimal sol
u
tion is the primary
proble
m
. De Jo
ng
make
s the d
e
finition for e
lite
sele
ction met
hod
s as follo
ws [16]:
Whe
n
set to the first t-g
e
n
e
ration, a (t
) is t
he be
st ind
i
vidual in the grou
p. And set A (t +
1) a
s
the ne
w gene
ration o
f
group
s, if A (t +1
) in
the a
b
se
nce of a (t), t
hen add a
(t) to A (t + 1
)
as the n + 1 i
ndividual in th
e A (t + 1)
, where n i
s
the size of the group
s.
Elite strategy
gene
rated
a
signifi
cant ro
le
to improve
the global
converg
e
n
c
e
ability of
stand
ard
ge
netic al
go
rithm, and
Rud
o
lph h
a
s th
eoreti
c
ally p
r
oved the
st
anda
rd
gene
tic
algorith
m
wit
h
elite st
rate
gy is glo
bal
conve
r
ge
nce. He
re p
u
t forward
an
improve
d
socia
l
cog
n
itive alg
o
rithm (IS
C
O
algorith
m
) ,
w
hi
ch ta
ke
s
each ag
ent
with the
kno
w
led
ge p
o
int to do
cro
s
sove
r an
d mutation, p
r
odu
ce the
bet
ter solution in
to the next ge
neratio
n of kn
owle
dge
ba
se,
rega
rd
the o
p
timal solutio
n
of e
a
ch ite
r
ation
as
elit
e individu
als,
and
avoid th
e be
st in
dividual
being d
e
stroyed be
cau
s
e o
f
hybrid ope
ra
tion.
3)Th
e use of dynamic le
arning ag
ent:
Acco
rdi
ng
to
SCO algo
rith
m,
the sele
cti
on
of
the age
nt's own kno
w
led
ge point is static
each time lib
rary up
date
s
itself. Becau
s
e that
the knowl
edge
ba
se is
co
nsta
ntly updated,
to
enha
nce the learni
ng abilit
y of
the algorithm, this
pap
er ado
pts dy
namic le
arni
n
g
agent, that is
,
rand
omly sel
e
ct
kno
w
led
g
e
lea
r
nin
g
a
s
the ne
w l
earning a
gent
s
after ea
ch
up
date of the
b
a
se
so th
at the a
gent o
w
n
kn
owle
dge
poin
t
s evolve
wi
th the evol
ution of the
kno
w
led
ge b
a
se
an
d
the algorithm can improve t
he overall learning ability.
4.2. The algo
rithm descri
p
tion of
Web
serv
i
ces selection for co
ncurre
nc
y
re
ques
t
s
In
We
b
servi
c
e sele
ction
optimizatio
n probl
em
s for co
ncurrent
use
r
s’
dem
a
nds, th
e
kno
w
le
dge p
o
ints co
rre
sp
ond
s
to
the seque
nce
num
ber
of We
b service
sel
e
cti
on, and
po
sition
level corre
s
p
ond
s to the evaluating V
a
lue of
We
b
service sel
e
ction which is the deviati
ng
degree. Thi
s
pape
r uses a
rando
m met
hod to gen
er
ate initial sol
u
tions. Web
servi
c
e
sele
ction
pro
c
e
ss b
a
se
d on ISCO al
gorithm
can b
e
descri
bed a
s
:
Algorithm. Web se
rvice
sel
e
ction al
gorit
hm for co
ncurrent re
que
sts
input: QoS values of candi
date We
b se
rvices a
n
d
use
r
re
que
sts
，
the Maxim
u
m numb
e
r o
f
iterations
ma
x
N
，
The number of initial solution
P
OP
N
output
：
the o
p
timal solutio
n
of Web service sel
e
ctio
n
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 12, No. 4, Dece
mb
er 201
4: 105
3 – 1063
1058
Step1: the initializatio
n pro
c
ess:
(1)
PO
P
N
sol
u
tion
s a
r
e
ran
domly g
e
nerate
d
whe
r
e ea
ch
sol
u
tion i
s
a
set
of se
que
nce nu
mbe
r
for Web
se
rvice, and the d
e
viating deg
rees of
re
que
sts with We
b service
s
a
r
e calcul
ated as
evaluation val
ue of the solu
tion.
(2)
c
N
is rand
omly
sele
cted fro
m
P
OP
N
solution
s as the learning ag
ents,
but the sa
me
solutio
n
is not
allowe
d to be assign
ed to
multiple age
nts.
Step 2: Vicari
ous le
arni
ng
pro
c
e
s
s
for i=
1 to
c
N
//
For
c
N
learning
agent
s
{
Imitation learning //
A numbe
r of solutio
n
s a
r
e
rand
omly ge
nerate
d
, and
find
c
N
better solutions
from them.
Observation
a
l
learning
// Let
1
X
be th
e
c
N
learnin
g
ag
en
cy's o
w
n
soluti
ons,
2
X
be the
c
N
better soluti
ons, the
n
divided them i
n
to seve
ra
l
se
ctions. Sele
ct intersectio
n
randomly a
n
d
do crossove
r operation for
12
X
,X
to get two new solutio
n
s
12
'
X
', X
using ge
netic
algorith
m
, and
then ch
oo
se
the better on
e as
3
X
, and co
ntinue to mut
a
te
3
X
to get ne
w sol
u
tion
3
'
X
which i
s
store
d
in the databa
se.
(Where the o
b
se
rvational l
earni
ng p
r
o
c
e
s
ses di
agram
as sh
own in Figure 2)
}
Step 3: datab
ase u
pdate p
r
oce
ss
Remove
the
same
am
ount
of worst
solu
tion with
lea
r
ning
age
nt; mean
while,
ch
o
o
se
the
optimal sol
u
tion of this with
the previou
s
gene
ration.
Step4: Dyna
mic Proxy
A plurality of mutually different lea
r
nin
g
agent
s is ra
n
domly gene
ra
ted.
Step5: End of algorithm ju
d
g
ment
IF (to achieve
a pre-determ
i
ned num
be
r of iterations)
Output optim
al solutio
n
ELSE
Incre
a
se the numbe
r of iteration
s
1, retu
rn to the step
2.
2
X
1
X
'
1
X
'
2
X
3
X
'
3
X
4
X
n
X
1
n
X
'
1
n
X
'
n
X
t
X
'
t
X
4
X
5
X
Figure 2. Sch
e
matic dia
g
ra
m of obse
r
vational lea
r
nin
g
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
A Reliable
Web Services
Selection M
e
t
hod for Con
c
urrent Re
que
sts (Guim
i
ng Lu)
1059
5. Simulations
5.1 The exp
e
r
iment desig
n
Suppo
se the
r
e are 300
can
d
idate
Web se
rv
ices.
Con
s
ide
r
th
e five comm
on QoS
attributes:
Co
st, Re
sp
on
se
Time, Availa
bility, Reliabil
i
ty, Load, a
n
d QoS
value
s
of
candid
a
tes
Web
servi
c
e
s
are g
ene
ra
ted rand
omly within a
ce
rtain ran
ge. The ran
ge of them as follo
ws:
0
300
$
C
,
03
0
T
s
ec
,
0.
7
1
A
va
,
0.
75
1
R
el
,
03
0
0
Lo
a
. Meanwhi
le set
6 co
ncurrent
use
r
s,
and it
s QoS val
u
e
s
a
r
e fixed
a
s
sho
w
n in
T
able 5.1, the
attribute
weig
hts
were s
e
t
to:
0.
2
,
0.
1
,
0.
15
,0.
2
5
,
0.
3
W
; The
experi
m
ent a
c
hiev
es th
e ISCO
algo
rithm
throug
h
C
+
+ p
r
og
ram
m
i
ng la
ngu
age
, and th
e
co
nfiguratio
n of
the P
C
which is ru
n by t
h
e
algorith
m
is: CPU
：
P
entiu
m(R)4 2.66
G
H
Z
，
Me
m
o
r
y
：
4G
；
OS
：
M
i
cro
s
oft Wi
nd
ows 7
。
Table 1. The
QoS co
nstrai
nts of con
c
u
r
rent use
r
s
UserID
C
T
A
v
a
Rel
Loa
1 50
10
0.75
0.80
200
2 150
20
0.85
0.90
100
3 80
15
0.80
0.85
150
4 200
10
0.95
0.80
250
5 75
25
0.90
0.95
50
6 150
10
0.85
0.75
100
5.2 The dete
rmination of
ISCO algorithm parameters
The value
s
of key para
m
eters i
n
the ISCO
alg
o
rith
m have a great influen
ce
on the
perfo
rman
ce
of the algorit
hm, and so t
he app
rop
r
iat
e
values
sho
u
ld be set in the algorith
m
para
m
eters b
e
fore a
pplyin
g
ISCO to so
lve Web
se
rvice sele
ction
probl
em in o
r
der to give fu
ll
play to the al
gorithm'
s
a
b
il
ity. The key para
m
et
ers o
f
ISCO algori
t
hm inclu
de:
popul
ation si
ze,
namely the numbe
r of initial solutio
n
s
P
OP
N
, the number of learnin
g
agent
s
c
N
, m
a
ximum
numbe
r of iteration
s
M
AX
N
, the numbe
r of optimal sol
u
tions
what a
r
e dra
w
in th
e imitation
learni
ng com
petition
λ
.
1)
Determine th
e para
m
eters: Population size
P
OP
N
Population si
ze
P
OP
N
is the number of initial solution
s. In the experiment, set the
numbe
r of ex
celle
nt solutio
n
s p
r
e
s
ente
d
as
λ
= 3; Because
3*
P
OP
c
NN
in ISCO
algorithm,
so
P
OP
N
,
c
N
are co
nsi
d
e
r
ed setting diff
erent value
s
of the followin
g
:
(1)
100
,
3
0
;
PO
P
c
NN
(2)
150
,
5
0
;
PO
P
c
NN
(3)
200
,
7
0
;
PO
P
c
NN
(4)
250
,
8
0
;
PO
P
c
NN
(5)
30
0
,
1
0
0
;
PO
P
c
NN
The m
a
ximu
m num
bers
of iteration
s
M
AX
N
are ta
ken
respectively 1
0
,100,10
00,10
0
00,
then execute the algo
rithm and record th
e sea
r
ched
solution in alg
o
rithm. The
result
s are sh
own
in Figure 5.4, abscissa axi
s
re
p
r
e
s
e
n
ts different valu
es
of
P
OP
N
, vertical axis rep
r
e
s
ent
s the
evaluation val
ues of solutio
n
s t
hat are se
arched by alg
o
rithm when
P
OP
N
have differen
t
values.
It is fou
nd i
n
expe
riment
s that rega
rdl
e
ss
what
is the valu
e of
maximum
nu
mber of
iteration
s
of the algorithm
M
AX
N
, when
20
0
,
70
;
PO
P
c
NN
the algorithm search ability i
s
s
t
ronges
t, that is
to s
a
y
M
AX
N
has no effect on the sel
e
ctio
n of
P
OP
N
.
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 12, No. 4, Dece
mb
er 201
4: 105
3 – 1063
1060
Figure 3. The
influence of the numb
e
r of
initial
solutio
n
s on the p
e
rf
orma
nce of the algorith
m
2)
Determine th
e para
m
eters: The num
be
r of excellent solution
s pro
p
o
se
d
λ
At
the initial moment, set
the
am
ount
of
the
pop
ul
ation, na
mel
y
the n
u
mbe
r
of i
n
itial
solut
i
o
n
s
20
PO
P
N0
, the num
ber
of learnin
g
agent
70
;
c
N
the maximum number of
iteration
s
of t
he alg
o
rithm
ma
x
500
0
N
.In ob
servatio
nal lea
r
ni
ng,
each time
do
crossove
r o
n
2
node
s an
d then do vari
atio
n on that 2 n
ode
s wh
ere
crossove
r an
d variation poi
n
t
s are
rand
o
m
ly
gene
rated, in
orde
r to improve the algo
ri
thm'
s
sea
r
ch ability and co
nverge
nce sp
eed, it need t
o
determi
ne th
e value
of
λ
(the
n
u
mbe
r
of
excelle
nt solutio
n
s extracted
)
.
λ
is
set from 1 to
10,
execute the
algorith
m
an
d record the
soluti
on
s that are se
arched
by the algorith
m
. The
experim
ental
results
are
sh
own i
n
Fig
u
re
4,, and the
a
b
scissa axis repre
s
e
n
ts different
valu
es of
λ
, the o
r
dinat
e axis
rep
r
e
s
ents the
eval
uation valu
es of the sol
u
tions th
at
are sea
r
ched by
the
algorith
m
. As can be
see
n
from Figure 4, when
λ
=
7 the algorith
m
has
the st
ronge
st se
arching
capabilities, and
therefore determi
ne
λ
= 7.
Figure 4. The
influence of
λ
(the num
ber
of solution
s e
x
tracted
)
on the perfo
rma
n
c
e of the
algorith
m
3.0
3.2
3.4
3.6
3.8
4.0
4.2
4.4
4.6
4.8
100
150
200
250
300
ev
aluating
v
a
lue
the num
ber o
f
initial so
lutio
ns
i
t
e
r
ati
n
g 10
i
t
e
r
ati
n
g 100
i
t
e
r
ati
n
g 1000
i
t
e
r
ati
n
g 10000
3.2
3.3
3.3
3.4
3.4
3.5
3.5
12345
6789
1
0
evaluating value
the
number
of solutions
extracted
λ
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
A Reliable
Web Services
Selection M
e
t
hod for Con
c
urrent Re
que
sts (Guim
i
ng Lu)
1061
5.3 Compari
s
on
w
i
th o
t
h
e
r algorithm
s
Basic
gen
etic alg
o
rithm
(GA algo
rithm
)
ha
s a
stro
ng pa
ralleli
sm and gl
oba
l sea
r
ch
capability
in solving Web servi
c
e
selection problem.
Ant colony
optimization (ACO algorithm)
usin
g meta
-knowl
edge
an
d he
uri
s
tics t
o
gui
de the
search, i
s
a
n
e
v
olutionary
al
gorithm
ba
se
d on
swarm
intelli
gen
ce h
a
ving
the adva
n
ta
ges of r
obu
st
ness, p
a
rall
el
ism a
nd
ea
sy to impleme
n
t,
etc. In view t
hat these two evolution
a
ry al
gorithm
s
for solving o
p
timization
problem
s pe
rfo
r
m
relatively mo
re
excelle
ntly, the expe
riment
s co
mp
are
the
accura
cy an
d t
he
runni
ng t
i
me
adoptin
g thre
e algorith
m
s t
o
verify the effect of IS
CO algorith
m
s. After determinin
g
the values
of
the paramete
r
s, this exp
e
ri
m
ent at the initial time set
20
PO
P
N0
,
70
c
N
,
λ
=7, while
using the
improve
d
so
cial cognitive
algorith
m
s (I
SCO al
go
rith
m), geneti
c
algorith
m
(G
A algorithm),
ant
colo
ny alg
o
ri
thm (A
CO
a
l
gorithm
) to
solve
th
e a
bove
servi
c
e
sel
e
ctio
n p
r
oble
m
. Th
re
e
algorith
m
s h
a
d
the sa
me
experim
ental
environ
m
ent,
and all of th
em use C
+
+ prog
rammi
ng
langu
age.
We ran
domly reco
rde
d
thre
e algo
ri
thm
s
’
runni
ng time,
the co
rrespo
nding
numb
e
r
of
iteration
s
, the
evaluatio
n v
a
lue
s
of
solutions se
a
r
che
d
by th
ree
al
gorithm
s,
wh
ere
the
units of
evaluation val
ue and runni
n
g
time are se
con
d
s.
Experi
m
ental re
sult
s are
sho
w
n i
n
Table 2:
Duri
ng th
e e
x
perime
n
t, each
algo
rith
m wa
s ite
r
at
ed 10,1
00,50
0,1000,2
000,
4000,5
000
times
，
and t
he
sea
r
ched
sol
u
tion
s a
nd the
ru
nni
ng time
of the al
gorithm
s
were
re
corded
.
Comp
ari
s
o
n
on se
archin
g perfo
rman
ce
of three algo
ri
thms a
s
sh
own in Figure 5:
Figure 5. Co
mpari
s
o
n
on
sea
r
ching p
e
rforman
c
e of three al
go
rith
ms
Comp
ari
s
o
n
on
run
n
ing
time of th
e th
ree al
gorith
m
s
in th
e
ca
se
o
f
the
same
nu
mber of ite
r
ati
ons
as sho
w
n in
Figure 6:
ISCO al
gorit
hm
G
A
al
gorit
hm
A
C
O
a
l
gori
t
h
m
iterations
Evaluation
value
Running
time
Evaluation
value
Running
time
Evaluation
value
Running
time
10 3.87672
0.016
4.2256
0.009
4.52553
0.064
100 3.60277
0.156
3.92734
0.101
4.48333
0.756
500 3.46542
0.797
3.72554
0.617
4.32179
3.781
1000
3.4545
1.563
3.60842
1.264
4.22138
7.428
2000
3.41747
3.125
3.57311
2.581
4.16251
13.951
4000
3.36525
6.265
3.41491
5.129
4.06817
28.001
5000
3.23241
7.796
3.35182
6.451
3.91255
35.279
convergence
3.2
3241
convergenc
e 3.3
5182
convergence 3.9
1255
3
3.2
3.4
3.6
3.8
4
4.2
4.4
4.6
4.8
10
100
500
1000
2000
4000
5000
eva
l
uting va
l
u
e
the num
b
e
r
of
iter
a
tions
I
S
C
O
al
gor
i
t
h
m
G
A
al
gor
i
t
h
m
A
C
O
al
gor
i
t
h
m
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 12, No. 4, Dece
mb
er 201
4: 105
3 – 1063
1062
Figure 6. Co
mpari
s
o
n
on runnin
g
time of the
three alg
o
rithm
s
with the sam
e
num
ber of
iteration
s
As can b
e
se
en from Tabl
e 1 and Fig. 6, IS
CO algorithm outperfo
rms GA alg
o
rithm and
GA algo
rithm
outpe
rform
s
ACO al
gorith
m
throu
gh
th
e analy
s
is f
r
o
m
the searchi
ng pe
rforman
c
e;
GA algorithm
outperforms ISCO and ISCO algo
rith
m outperfo
rm
s the ACO al
gorithm throu
gh
the an
alysi
s
f
r
om th
e
conv
erge
nce
rate;
It ca
n b
e
se
en from th
e
cal
c
ulatio
n p
r
oce
s
s of
ISCO
that ISCO ha
ve advantage
s of low comp
lexity, less pa
ramete
rs, an
d easy to imp
l
ement.
As ca
n be
se
en from Fi
g. 6, in the wh
ol
e experim
ent, when th
re
e algorith
m
s a
r
e in the
same
situ
atio
n iteratio
ns, t
he time
used
by ISCO
al
gorithm
to
se
arch the
opti
m
al solution
is
7.796
s, the time used by
GA algo
rithm
is 6.45
1s
, an
d the time of
ACO alg
o
rith
m is 35.2
7
9
s
, the
differen
c
e
be
tween th
e
ru
nning tim
e
of
ISCO a
nd G
A
is n
o
t larg
e und
er th
e
same
num
be
r of
iteration
s
; Th
ree al
go
rithm
s
sea
r
ch for the optimal
solutio
n
in th
e iteration
times
5000,
a
nd
conve
r
ge
nce
ha
s b
egu
n;
Although
th
e time
use
d
by ISCO
alg
o
rithm to
se
arch the
opti
m
al
solutio
n
is a l
i
ttle inferior
to that used
by
the GA al
gorithm; But
more i
m
po
rta
n
tly, the solut
i
on
sea
r
ched by I
S
CO is the b
e
st and the
solution s
earched by GA is
the se
con
d
a
nd that sea
r
ched
by ACO
algo
rithm is the
worst. By com
parin
g,
it ca
n
be
con
c
lu
de
d that the
co
nverge
nce
sp
eed
and o
p
timiza
tion ability of ISCO alg
o
ri
thm are
better than th
ose of GA an
d
ACO alg
o
rit
h
m
gene
rally.
6. Conclusio
n
In ord
e
r to
so
lve the
confli
ct of
con
c
u
r
rent
re
que
sts,
this pap
er prese
n
ts a We
b
service
sele
ction met
hod for
con
c
u
rre
nt deman
d
.
Throug
h
the
simulation, it can b
e
co
ncl
uded that ISCO
algorith
m
con
s
tru
c
ted in thi
s
pa
per i
s
a
n
optimiz
atio
n
algorith
m
wit
h
relatively st
rong
se
archin
g
cap
abilities a
nd faster
se
arching
spe
e
d
, is an
efficient ne
w e
v
olutionary a
l
gorithm
solvi
ng
discrete o
p
timization p
r
o
b
lems. Algo
rithm rule
s are sim
p
le, easy to imple
m
ent, and the
execution time is l
e
ss i
n
the same
number of
it
erations, whi
c
h prov
e the feasibility of
the
algorith
m
. The alg
o
rithm
has
a stro
ng expa
ndin
g
ca
pa
city, can
be exte
nded to
oth
e
r
appli
c
ation
s
.
Therefore, IS
CO al
gorith
m
ca
n
meet
the
actu
al appli
c
ation requireme
nts and
efficien
cy req
u
irem
ents tha
t
the Wed se
rvices
sele
ctio
n for co
ncu
r
rent requ
est
s
need
ed.
Referen
ces
[1]
T
.
Y
u
, KJ. Lin. Service sele
ction alg
o
rithm
s
for W
eb se
rvices
w
i
t
h
en
d-to-en
d
QoSconstrai
nts.
Information Sy
stems a
nd Eb
u
s
iness Ma
nag
e
m
e
n
t
. 2005; 3:
103-
126.
Evaluation Warning : The document was created with Spire.PDF for Python.