Internati
o
nal
Journal of Ele
c
trical
and Computer
Engineering
(IJE
CE)
V
o
l.3
,
No
.1
, Feb
r
u
a
r
y
2
013
,
pp
.
64
~72
I
S
SN
: 208
8-8
7
0
8
64
Jo
urn
a
l
h
o
me
pa
ge
: h
ttp
://iaesjo
u
r
na
l.com/
o
n
lin
e/ind
e
x.ph
p
/
IJECE
AC-RDVT: Acyclic Resource Di
st
ance Vect
or Routing T
a
bles
for Dynamic Gri
d
Re
source Discovery
Nafiseh B
a
hr
ami, Ah
mad H
a
bibiz
a
d
Navi
n,
Mi
na
Al
avi
ghi
,
Al
i
A
s
gh
a
r
Po
urh
a
ji
k
a
z
e
m
Departement of
Computer Engin
eering
,
Islam
i
c
Azad Un
iv
ersity o
f
Tabriz,
Iran
Article Info
A
B
STRAC
T
Article histo
r
y:
Received Nov 22, 2012
Rev
i
sed
Jan 10, 201
3
Accepte
d
Ja
n 22, 2013
Since the ob
jective of grid
is sharing the n
u
merous and heterog
e
neous
res
ources
,
res
o
u
r
ce d
i
s
c
over
y
i
s
a ch
all
e
nging
is
s
u
e. R
e
c
e
ntl
y
appe
ared
,
Ontosum, is a
resource d
i
scov
er
y
method b
a
sed on semantically
link
e
d
organizations
an
d a rou
ting
algor
ithm Re
s
ource
Dis
t
ance
Vecto
r
(RDV), has
been pres
ent
e
d
to forward res
ource dis
c
over
y
queri
es
into the clus
t
e
rs
.
Although this f
r
amework is
ef
ficient for
larg
e-scale g
r
ids and
nodes are
cluster
e
d
auto
m
a
tica
l
l
y
b
a
sed
on sem
a
nti
c
at
tribut
es to
consti
tute
a
semantically
lin
ked overlay
n
e
twork, but the d
ynamic behavio
r
of grid isn’t
considered
. In this method, deceptiv
e
information is stored in
RDV tables
(RDVT) which
cause som
e
problem
s
in
routing process. In this paper, a
method is propo
sed to improve the d
y
n
a
mism of
RDV routing algorithm, so
the consistency with grid
en
vironm
ents
is incre
a
sed. The
develop
e
d
algorithm
is assessed b
y
inv
e
sti
g
atin
g
the success probability
,
number of
hops and routing
time of
resour
ce discover
y
.
Keyword:
Gri
d
Resource Disc
ove
ry
RDV R
o
uting
Tables
Copyright ©
201
3 Institut
e
o
f
Ad
vanced
Engin
eer
ing and S
c
i
e
nce.
All rights re
se
rve
d
.
Co
rresp
ond
i
ng
Autho
r
:
Nafise
hBah
ra
m
i
,
Depa
rt
em
ent
of C
o
m
put
er
En
gi
nee
r
i
n
g,
Islamic Azad
Uni
v
ersity of
Tabriz
Pasda
r
an
hi
gh
way
,
Ta
bri
z
,
I
r
a
n.
Em
ail: n_ba
hra
m
i@gm
ail.com
1.
INTRODUCTION
Gri
d
i
s
a speci
fi
c t
y
pe of paral
l
e
l
and d
i
st
ri
but
ed
syst
e
m
that enables th
e selection, sha
r
ing,
excha
n
ge, an
d
agg
r
e
g
at
i
on
of
geo
g
ra
p
h
i
cal
l
y
di
st
ri
but
ed a
u
t
o
nom
ous re
s
o
u
r
ces su
ch as
com
put
ers, so
ft
ware
,
cat
al
ogu
ed dat
a
and dat
a
base
s, speci
al
devi
ces/
i
n
st
rum
e
nt
s (e.g
. radi
o t
e
l
e
scope
), pe
o
p
l
e/
col
l
a
borat
or
s [1]
.
Since grid e
n
vironm
ent is dyna
m
i
c and res
ources can be
c
o
nnect
e
d
a
nd
di
sco
nnect
e
d
to t
h
e system
, efficient
r
e
sour
ce d
i
scov
er
y m
e
th
od
is r
e
q
u
i
r
e
d
to enable users to a
ccess the grid
resources. In this study a res
o
urce
di
sco
v
ery
m
e
tho
d
,
O
n
t
o
s
u
m
[2]
,
i
s
di
scus
se
d t
o
s
o
l
v
e its prob
lem
s
. No
des in
On
tosu
m
o
r
g
a
n
i
ze th
emselv
es
au
to
m
a
tical
ly
b
a
sed
o
n
sem
a
n
tic attrib
u
t
es an
d
co
n
s
titu
te
clu
s
ters. Th
ese clu
s
ters form
an
ov
erlay n
e
t
w
ork. A
rou
ting
algo
rit
h
m
,
RDV, is ap
p
lied to
fo
rward resou
r
ce
di
scovery
reques
ts inside t
h
e cl
usters
[3].Each node
in
th
e syste
m
main
tain
s a ro
u
tin
g
tab
l
e th
at
in
clu
d
e
s th
e i
n
fo
rm
ati
on o
f
l
o
cal
resou
r
ces a
nd
nei
g
hb
or
s. One
o
f
th
e
m
o
st i
m
p
o
r
tan
t
p
r
ob
lem
s
o
f
ro
u
ting
tables in
th
is
m
e
t
h
od
is th
e ex
isten
ce o
f
so
m
e
ad
d
ition
a
l d
e
cep
tiv
e
inform
ation that cause cycles
in
resource di
scovery m
echa
n
ism
.
Deceptive
inform
ation in RDVT
m
a
y
lead to
so
m
e
req
u
e
sts wro
n
g
l
y
d
i
rected
to
o
f
flin
e reso
urce wh
ich
co
u
l
d
in
crease false p
o
s
itiv
e.
Thu
s
b
y
requ
estin
g
a
sp
ecial resou
r
ce, th
e sam
e
reso
urce
will b
e
reach
e
d se
v
e
ral ti
m
e
s th
roug
h d
i
fferen
t
n
e
ig
hb
ors.Th
erefo
r
e by
g
o
i
n
g
a
reso
urce to
offlin
e
m
o
d
e
, in
fo
rm
atio
n
on
th
e ta
bles will g
u
i
d
e
th
e req
u
e
st t
o
th
at o
f
flin
e reso
urce
again.
Th
e m
a
in
con
t
ribu
tio
n of t
h
is p
a
p
e
r is to elimin
ate th
e cycles b
y
m
o
d
i
fyin
g RDVT. Elimin
atio
n
of
cycles in
th
e tab
l
es en
sures t
h
at th
e informatio
n
stored
in th
e tab
l
es,
will n
o
t
g
u
i
d
e
th
e requ
ests to
t
h
e sam
e
of
fl
i
n
e
res
o
u
r
c
e
. S
o
by
c
h
an
g
i
ng t
h
e m
ode
of
a
reso
u
r
ce t
o
of
fl
i
n
e m
ode
, an
ot
h
e
r
res
o
u
r
ce
of
t
h
e
sam
e
t
y
pe
can
be fo
und
i
n
stead
of
v
i
sitin
g
t
h
at of
f
lin
e r
e
sour
ce
frequ
e
n
tly.Sim
u
l
ati
o
n
resu
lts show th
at th
e
prop
o
s
ed
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE I
S
SN
:
208
8-8
7
0
8
AC-RDVT: Ac
yclic Resource
Distance Vect
or Routing
T
a
bl
es f
o
r
Dy
na
mi
c
Gri
d
…
.
(
N
af
i
s
eh B
a
hr
ami
)
65
m
e
t
hod
has be
t
t
e
r perf
o
r
m
a
nce t
h
an
pre
v
i
o
us o
n
e i
n
c
o
m
p
ari
s
on
of t
h
e
num
ber o
f
fai
l
ed re
que
st
s, r
o
ut
i
n
g
ti
m
e
an
d
nu
m
b
er
o
f
ho
ps.
The rest
o
f
t
h
i
s
pape
r i
s
orga
ni
zed as f
o
l
l
o
w:
sect
i
on 2 revi
e
w
s t
h
e
previ
o
u
s
wo
r
k
s, p
r
op
ose
d
m
e
t
hod a
p
pear
s i
n
sect
i
o
n
3.
S
i
m
u
l
a
t
i
on res
u
l
t
s are
prese
n
t
e
d i
n
sect
i
o
n
4.
Sect
i
on
5 c
o
nc
l
udes
t
h
e
pa
per
.
2.
RELATED WORKS
Acco
r
d
i
n
g t
o
t
h
e
di
ver
s
i
t
y
an
d
num
erou
s n
u
m
bers of
res
o
u
r
ces i
n
g
r
i
d
,
fi
ndi
ng
sui
t
a
bl
e
reso
u
r
ces i
s
im
port
a
nt
i
n
t
h
ese envi
ro
nm
ent
s
. A
n
o
v
e
r
vi
ew o
f
som
e
im
po
rt
ant
res
o
urc
e
di
sco
v
ery
m
e
t
h
o
d
s i
s
gi
ve
n i
n
t
h
i
s
section. Resource
discovery
mechanism
s
may be ce
ntra
liz
ed
or dece
ntral
i
zed. T
h
e m
o
st significant
problem
o
f
cen
tralized
ap
pro
ach
es is
b
o
ttlen
e
ck
s and
also
b
y
in
creasin
g th
e
num
b
e
r o
f
no
d
e
s in
system
scalab
ilit
y
becom
e
s anot
her p
r
obl
em
[
4
-
9
]
.
To o
v
erc
o
m
e
t
o
t
h
i
s
di
ffi
cul
t
y
peer
-t
o-
peer (
P
2
P
) t
echni
que
s i
n
t
r
od
uce
d
decent
r
alized m
e
thods [10, 11].
Rero
uting table
m
echanism
[
12], is one of the dece
ntralized m
e
thods i
n
whi
c
h,
gri
d
en
vi
r
onm
ent
i
s
com
p
ri
sed by
ro
ut
ers a
nd
res
o
u
r
ces. R
out
i
n
g
p
r
oces
s i
n
t
h
i
s
a
p
p
r
oach
uses
r
out
i
n
g
t
a
bl
es i
n
or
de
r t
o
di
rect
t
h
e re
que
st
s fo
r avai
l
a
bl
e reso
urce
s
i
n
t
h
e sy
st
em
. A m
e
t
hod
has
been
pr
op
ose
d
[
13]
t
o
fi
nd
sui
t
a
bl
e
res
o
u
r
ce i
n
gr
i
d
w
h
i
c
h
i
s
bas
e
d
on
re
serv
atio
n algo
rith
m
.
Th
is al
gorith
m con
s
ists of
forward
p
a
th
an
d b
a
ckward
p
a
th
.
In
fo
rward
p
a
th
, ap
pro
p
riate
resou
r
ces will
b
e
reserv
ed
an
d on
e of th
ese reso
urces
will be chos
en in backward
path to
re
ply the request. T
h
e m
e
thod
propos
ed
in [14] uses
tree architecture for
gri
d
re
so
urce
di
sco
v
ery
,
i
n
whi
c
h que
ry
d
o
es
n’t
fo
rwa
r
d
t
o
al
l
no
des u
n
l
i
k
e
t
h
e
fl
oo
d
i
ng
-base
d
t
e
c
h
nol
ogy
.
Two pas
s
es are
require
d
in se
archi
ng t
h
e tre
e
. To find a
m
a
t
c
h res
o
urce i
n
a n
ode
o
r
s
ubt
ree o
f
t
h
at
n
o
d
e
, fi
rst
pass i
s
st
art
i
n
g
from
l
eaf nod
e t
o
war
d
t
h
e r
oot
an
d ne
xt
from
t
h
i
s
m
a
t
c
hed
no
de t
o
wa
rd l
eaf n
ode
s (
i
f t
h
e
requested res
o
urce
is in a
s
u
btree of a
node
).
To m
a
ke t
h
e s
earch ea
si
er re
cent
y
ears [
1
5-
18]
t
h
ey
m
a
ke di
ffe
re
nt
set
s
of
n
odes
by
us
i
ng si
m
i
l
a
r
co
n
t
en
ts.
Nod
e
s with
t
h
e same in
terests are clu
s
tered
irrespective t
o
the form
ing of t
h
e cluste
rs
[16]. The
m
e
t
hod
p
r
o
p
o
s
e
d
by
N
g
et
a
l
[1
8]
, S
earc
h
i
n
g
i
s
base
d
on
pe
ri
o
d
i
c
m
e
ssages
bet
w
ee
n
no
des
i
n
w
h
i
c
h t
h
e
messag
e
s im
p
o
se a heav
y
ov
erh
e
ad
to
th
e syste
m
. Se
m
a
n
tic Ov
erlay Netwo
r
k
(SON) m
o
d
e
l [1
9
]
relies on
central serve
r
s
to cluster
nodes
whic
h is c
onsi
d
ere
d
bot
t
l
eneck
f
o
r t
h
e
sy
st
em
. [20
,
2
1
,
22]
a
dd
se
m
a
nt
ic
sho
r
t
c
ut
s
t
o
t
h
e g
r
o
u
p
s
of
n
o
d
es.
S
h
o
r
t
c
ut
a
p
p
r
oaches
are
base
d
on
p
r
oxi
m
i
ty
of i
n
t
e
res
t
s. A
l
i
s
t
of
s
h
ort
c
ut
s
is
m
a
de by eac
h pee
r
for
nodes that ha
ve re
sponde
d
to
pre
v
ious re
quests. To access
th
e conte
n
t,
the pe
er
will
search th
e list o
f
sho
r
tcu
t
s
for a requ
est
an
d
i
f
it
d
o
es
n’t
fi
n
d
any
r
e
sp
onse t
h
e
n
t
h
e re
que
st
wi
l
l
be
br
oa
dcast
e
d t
o
every
no
de
.SL
N
(
S
em
ant
i
c
Li
nk
Net
w
or
k
)
[
2
3
,
24
, 2
5
-
2
7
]
i
s
pr
o
v
i
d
e
d
by
Zh
uge a
s
a se
m
a
nt
i
c
dat
a
m
odel
t
o
or
ga
ni
ze t
h
e
va
ri
o
u
s
web
res
o
urces
.
Sem
a
ntic clustering is
use
d
to organize t
h
e ne
twork topology and
re
ducing the sea
r
ch s
p
ace i
n
ont
os
um
Syste
m
[6] which is
com
p
letely decentralized
a
nd autom
a
tically
creates sem
a
ntic groups
. T
h
e
r
efore
b
o
ttlen
e
ck
is
prev
en
ted and
n
o
d
e
s are cl
u
s
tered
b
a
sed
o
n
certain
in
terests and
ind
e
x
e
d
in
sp
ecial form
at
s
whic
h are
use
d
for routing in
the ne
twork. Algorithm
s
in previous work
s [2, 3]
contai
n
d
eceptive information
in
rou
ting
tab
l
es th
at
m
a
y le
ad
to
cycles in
reso
urce
dis
c
ove
ry m
echanism
.
Thus by
requesting a
special
resource, th
e sa
m
e
reso
urce
will b
e
reach
e
d sev
e
ral tim
es
t
h
rou
g
h
d
i
fferen
t
no
d
e
s. So
by ch
ang
i
ng
th
e state o
f
a resource to
offline m
ode the reques
t is fo
rward
e
d
to
th
e
sam
e
o
fflin
e reso
urce acco
r
d
i
n
g
t
o
th
e i
n
fo
rmatio
n
o
f
tab
l
es. Elimin
atin
g
th
e cycles in
tab
l
es will reso
lv
e t
h
is prob
lem
wh
ich
will b
e
discu
ssed
in
the n
e
x
t
sect
i
on.
3.
PROP
OSE
D
METHO
D
The p
r
o
p
o
se
d m
e
t
hod ai
m
s
to im
pro
v
e R
D
V t
a
bl
es i
n
sem
a
nt
i
c
rout
i
n
g
archi
t
ect
ure t
o
o
v
erc
o
m
e
som
e
of t
h
e
pr
obl
em
s. In
se
m
a
nt
i
c
ro
ut
i
n
g
,
n
o
d
es a
r
e cl
u
s
t
e
red
base
d
o
n
ce
rt
ai
n i
n
t
e
re
st
s. N
o
des i
n
c
l
ust
e
rs
fo
rm
a t
r
ee and t
h
e root
n
o
d
e keep
s t
h
e i
n
f
o
r
m
at
i
on of w
hol
e cl
ust
e
r and f
o
rm
an overl
ay
net
w
o
r
k f
o
r sh
ari
n
g
th
eir resou
r
ces. Rou
ting
co
nsists o
f
two
lev
e
ls: In
tr
a Cluster and
In
ter
Clu
s
ter [3
]. Pro
p
o
s
ed
so
lu
tion
is
p
e
rform
e
d
in
In
ter Cluster lev
e
l. Th
e
ro
o
t
of each
cluste
r i
n
an
In
ter Clu
s
ter ro
u
ting is presen
ted
b
y
th
e in
d
e
x
of w
h
ol
e cl
ust
e
r nam
e
d i
ndi
cat
or o
f
t
h
e cl
ust
e
r w
h
i
c
h f
o
rm
an ove
rl
ay
net
w
o
r
k
.
R
o
u
t
i
ng req
u
est
s
a
m
ong
clu
s
ters is essen
tial to
sh
are resou
r
ces. Thu
s
a ro
u
ting
algorith
m
cal
led
Resou
r
ce
Distance Vector, R
D
V, is
use
d
. B
y
fo
rw
ardi
ng a re
q
u
e
s
t
t
o
a node
,
nearest
no
de
wi
t
h
desi
r
e
d r
e
so
urce i
s
ch
o
s
en t
h
r
o
ug
h
di
st
ance
v
ector. Roo
t
no
d
e
s
m
a
in
tain
a ro
u
t
i
n
g
tab
l
e in
wh
ich
all en
tr
ies are set to
in
fin
ity (no
t
availab
l
e) at first. Each
no
de
kee
p
s t
h
e i
n
f
o
rm
at
i
on
of
l
o
cal
reso
u
r
ces an
d
nei
g
h
b
o
r
s i
n
t
h
e f
o
r
m
of vect
o
r
s
o
f
num
bers t
h
at
sh
o
w
nearest
distanc
e
to each res
o
urce
.
When
the inform
ation of
one
node is
se
nt to anothe
r node
, the ve
ctor is
increm
ented.
Local res
o
urce
s in RDVT
a
r
e set to 0. All
of vectors in
each node is merged a
nd se
nt to its
n
e
igh
bors an
d if th
ere are
m
u
l
tip
le
rou
t
es to
a
reso
urce, nod
es cho
o
se th
e sho
r
test
p
a
th fo
r m
e
rg
ing
.
By
changing the i
n
form
ation of
each node,
updated inform
ation m
u
st be sent
to all neighbors. By forwardi
nga
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:20
88-
870
8
IJEC
E
V
o
l
.
3,
No
. 1,
Fe
br
uar
y
20
13
:
64
–
7
2
66
request to a
node,
first the local resource
s a
r
e chec
ke
d
an
d t
h
e
n
t
h
e
ri
g
h
t
nei
g
h
b
o
r i
s
c
hos
en t
o
f
o
r
w
a
r
d t
h
e
req
u
est
i
f
n
o
n
ode
i
s
f
o
un
d.
F
i
gu
re1
sh
o
w
s t
h
i
s
pr
ocess
wi
t
h
a
n
e
x
am
pl
e. See [
2
]
f
o
r
m
o
re i
n
f
o
rm
at
i
on.
Fig.1. RDV rou
t
ing table
3.
1.
A
C
-
R
DV
T
Two
p
r
ob
lem
s
ex
ist in
RDV tab
l
es: 1
-
Stored
in
fo
rm
atio
n
in
th
ese tab
l
es d
i
rects th
e req
u
e
sts to
th
e
sam
e
resource
t
h
r
o
u
g
h
di
ffe
re
nt
pat
h
s.
2-T
h
e
r
e are
cycles in these ta
bles.
These
problem
s will be overc
o
m
e
by eli
m
in
ating ext
r
a
and deceptive i
n
form
at
ion in tabl
es. Figure
2 shows
t
h
e al
g
o
ri
t
h
m
o
f
t
h
e
p
r
o
p
o
se
d
m
e
t
hod.
The
fi
rst
pr
obl
em
ari
s
es by
t
h
e c
o
m
m
on n
e
i
g
h
b
o
r
s.
M
a
i
n
t
a
i
n
i
n
g a
not
h
e
r t
a
bl
e
nam
e
d
NO
N
, will
so
lv
e t
h
is proble
m
. Th
is tab
l
e in
clud
es th
e
in
fo
rm
ati
o
n
o
f
n
e
igh
bor
of
neig
hb
or
s.
I
f
ther
e ar
e an
y commo
n
Fig.1. RDV rou
t
ing table
GN: Number of
nodes in gr
aph
NRES: Number of resources
rdv: RDV routin
g tab
l
e (includes
the informati
on
of local resources and neighbors
of a nod
e)
Neighbor: Number of
neighbors
(
f
or node i)
for ea
ch nod
e
j i
n
the
graph
do
\*F
i
nding th
e m
i
n
im
um
of each
c
o
lum
n
in t
a
bl
e
for
k
=
1
to
N
R
ES
min ( k )
= big
n
u
mber
for
h=1
to
iNeighbor+1
i
f
(
r
d
v ( h
,
k
, j
)
<
mi
n
( k
) )
min ( k )
=
rdv(
h
,
k
,
j )
min ( k )
= min (
k )
+ 1
\* For each
neig
hbor of nod
e j,
minimum of columns in
RDV table
is calcu
l
ated
in
which
th
e info
rmation of
node j and
common nodes betw
een
j
and m doe
s
n
’t in
terfere
in f
i
nding minimum.
for each nod
e m
that is
neighbor
with node j do
for n
=
1
to
N
R
ES
min2 (n)
= big
number
for h
=
1
to
iN
eighbor+1
If (
rdv (
h,
n, m )
< min2
( n
) )
and
( h
≠
j )
and
(
h
≠
co
mmon neighbor’s number)
min2 ( n
)
= rdv
( h
,
n
,
m )
min2 (
n )
= min2 ( n
)
+ 1
\*
inserting
th
e
m
e
rged
inform
ation
of
each
pa
i
r
of n
e
ighbors in
ea
ch o
t
her
for
p=1
to
N
R
ES
rdv ( m, p
,
j )
=
min2 ( p )
rdv ( j, p
,
m )
=
min ( p )
Fig 2. Algor
ithm of AC-RDVT
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE I
S
SN
:
208
8-8
7
0
8
AC-RDVT: Ac
yclic Resource
Distance Vect
or Routing
T
a
bl
es f
o
r
Dy
na
mi
c
Gri
d
…
.
(
N
af
i
s
eh B
a
hr
ami
)
67
n
e
igh
bor
s
b
e
tw
een two
nodes, th
e
v
ector
o
f
t
h
at co
mm
o
n
n
o
d
e
d
o
e
s no
t in
terf
er
e i
n
mer
g
ing
pro
c
ess. Fo
r
exam
ple, in Fi
gure
3,
C
i
s
t
h
e
com
m
on nei
g
hb
o
r
bet
w
ee
n
A
an
d
B
.
Accord
ing
to
th
e tab
l
e,
A
accesses th
e r
e
so
ur
ce 2
thr
ough
tw
o
d
i
f
f
e
r
e
nt p
a
th
s:
AC
a
nd
ABC
. I
n
R
D
V
m
e
t
hod,
by
e
n
t
e
ri
n
g
C
to
th
e system
, it sh
ou
ld sen
d
its in
fo
rm
atio
n
of its tab
l
e to
B
and
B
mu
s
t
m
e
r
g
e
th
e
n
e
w informatio
n
b
y
its
vecto
r
and
send it to
A
. nod
e
B
do
esn’
t
k
now
th
at
C
is a neig
hb
or
of
A
an
d thu
s
the ext
r
a information of local
res
o
urce
of
C
that is accessible directly by
C
, is i
n
serted
t
o
th
e tab
l
e t
h
rou
g
h
B
and
B
se
nds (2, 1,
2) t
o
A
. B
u
t if
B
was aware of this, it does
n’t m
e
rge the vect
or
of
C
fo
r sen
d
in
g to
A
and
t
hus we
kee
p
NO
N
tab
l
e to
so
lv
e t
h
is p
r
oble
m
.
NON
m
a
intains
neighbors of each
node and t
h
eir nei
g
hbors
.
For e
x
am
pl
e,i
n
Fi
gure
4, i
n
A
’s
NO
N
tab
l
e,
th
e rows show th
e n
e
ig
hbo
r
o
f
A
(
B
,
C
), an
d
th
e co
lu
m
n
s sh
ow
t
h
e nei
g
h
b
o
rs
of
B
and
C
.
Whe
n
B
wan
t
s to
m
e
rg
e its i
n
fo
rm
atio
n
,
first it ch
eck
s its
co
mm
o
n
n
e
ig
hb
ors b
e
t
w
een
A
and itself.
If t
h
ere
i
s
a
n
y
com
m
on nei
g
h
b
o
r
,
t
h
ei
r
i
n
f
o
r
m
at
i
on d
o
es
n’t
m
e
rge. Si
nce
C
i
s
c
o
m
m
on nei
g
hb
o
r
of
A
and
B
,
B
doesn’t m
e
rge
vector
C
which
is sh
own
in Figu
re 5.
Fig 3. Problems of RDV method
Fig 4.
NON tables
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:20
88-
870
8
IJEC
E
V
o
l
.
3,
No
. 1,
Fe
br
uar
y
20
13
:
64
–
7
2
68
Cu
rren
t m
e
rg
in
g
i
n
RDVT cau
s
es so
m
e
cy
cles in
rou
ting
tab
l
es.
Wh
en
a n
o
d
e
send
s its in
fo
rm
atio
n
to
its n
e
i
g
hbo
rs, th
e n
e
i
g
hbo
rs shou
ldn
’
t
ret
u
rn
t
h
is
informatio
n
to
it again
.
Oth
e
rwise, add
ition
a
l d
e
cep
tiv
e
in
fo
rm
atio
n
in
tab
l
es will b
e
fo
und
th
at cau
s
e cycles.
So
b
y
ch
an
g
i
n
g
t
h
e state o
f
a
reso
urce to
offli
n
e mo
d
e
,
th
e alg
o
rith
m
may d
i
rect th
e requ
est to
th
at o
fflin
e
re
s
o
u
r
ce by
i
n
f
o
rm
ati
on
of t
a
bl
es
.
B
y
el
im
i
n
at
i
ng t
h
ese
cycles in the
tables, t
h
is
probl
em
will be s
o
l
v
ed.
In
the
ot
her
words, i
n
R
D
V m
e
thod, a
dditional inform
ation
are m
e
rged and sent to t
h
e ne
ighbors. Me
rgi
ng t
h
is in
form
ation will create
deceptive
i
n
form
at
ion in the
tables
whi
c
h l
ead t
o
cy
cl
es i
n
ro
ut
i
ng m
echani
s
m
.
I
n
t
h
e
pr
o
p
o
s
ed m
e
t
hod,
t
h
i
s
ext
r
a i
n
f
o
r
m
at
i
on d
o
esn'
t
m
e
rg
e
therefore cycles are pre
v
e
n
ted. Fo
r e
x
am
ple, in Figure
6, whe
n
A
sen
d
s its in
fo
rm
ati
o
n
to
B
, m
e
rg
i
ng b
y
RDV m
e
th
od
i
s
as fo
llowing
:
No
de
A
m
e
rges vectors
A
and
B
, lead
in
to
th
e v
ector A (~, 2
,
~, 1
,
2, 1
)
. Th
is v
ector is sen
t
to
n
ode
B
. Tabl
e o
f
n
ode
B
s
h
ows
that we can a
ccess the res
o
urce
(1,4
) by
0 h
o
p
an
d 2
h
ops t
h
r
o
ug
h i
t
s
l
o
cal
r
e
sour
ces
(
0
ho
p)
o
r
tro
ugh
i
t
s n
e
ighb
or
A
(
2
ho
ps)
.
A
c
cor
d
i
n
g to
Figu
r
e
6
,
nod
e
B
retu
rn
s t
o
itself t
h
rou
gh
no
de
A
. By t
h
e p
r
op
osed
m
e
th
od
,
wh
en
A
wants t
o
m
e
rge its vectors to send
B
, it sh
ou
ldn
’
t m
e
rg
e
vecto
r
B
.
So t
h
e m
e
rged
vector for
node
A is:
A
΄
(~, ~,
~, 1, ~,
1).
4.
E
X
PERI
MEN
T
AL RES
U
L
T
In t
h
i
s
sect
i
o
n
ex
peri
m
e
nt
al
resul
t
s
a
r
e
di
scusse
d t
o
sh
o
w
t
h
e
bet
t
e
r
p
e
rf
orm
a
nce o
f
t
h
e p
r
op
ose
d
m
e
t
hod.
A
n
ove
rl
ay
net
w
o
r
k i
s
c
o
nsi
d
e
r
ed t
o
be as
a gr
ap
h. C
o
nsi
d
e
r
i
n
g t
h
e
di
f
f
i
c
ul
t
y
of
act
ual
im
pl
em
ent
a
t
i
o
n, t
h
ree ex
peri
m
e
nt
s are sim
u
l
a
t
e
d by
a Pe
nt
i
u
m
i
n
C
#
envi
ro
nm
ent
.
We set
u
p ex
p
e
ri
m
e
nt
s
un
de
r f
o
l
l
o
wi
n
g
co
n
d
i
t
i
on f
o
r b
o
t
h
new m
e
t
h
o
d
an
d
per
v
i
o
us o
n
e.
Th
e avera
g
e n
u
m
ber of n
o
d
es
i
n
t
h
e
syste
m
is co
n
s
id
er
ed
to
b
e
480
and
th
e t
o
tal n
u
m
b
e
r
o
f
r
e
qu
ests is equ
a
l to
100
00
.
Th
e
n
u
m
b
e
r
o
f
n
e
ig
hbors
fo
r eac
h n
o
d
e i
s
u
n
i
f
orm
l
y
di
st
ri
but
e
d
i
n
{
1
,
2,
3,
4,
5
,
6}
.O
ffl
i
n
e a
n
d
onl
i
n
e rat
e
s
o
f
re
so
urces
f
o
l
l
o
w
P
o
i
sso
n
di
st
ri
b
u
t
i
o
n
wi
t
h
t
h
e
rat
e
of
0.
02
. T
h
e e
x
p
e
ri
m
e
nt
al
resul
t
s
sh
ow
t
h
at
t
h
e
pr
o
pose
d
m
e
t
hod
i
m
proves t
h
e
efficiency of the syste
m
by consid
e
r
i
n
g t
h
ree
cri
t
e
ri
a:
t
h
e num
ber of fai
l
e
d req
u
est
s
, r
o
ut
i
ng t
i
m
e and n
u
m
ber
of
h
o
p
s
.
Fi
g
u
r
e
7 s
h
ow
s t
h
e
resul
t
of
fi
rst
e
xpe
ri
m
e
nt
whi
c
h c
o
m
p
ares t
h
e
num
ber
of
f
a
i
l
e
d re
quest
s
i
n
bo
t
h
m
e
thods
. T
h
e
num
ber
of
failures for ea
ch 1000 re
quests
is calculated. Obtaine
d
results s
h
ow that by
Fig 5
.
showing
common neighbor between A
and
B b
y
NON table
Fig 6.
Solv
ing th
e c
y
c
l
es in RDV
T
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE I
S
SN
:
208
8-8
7
0
8
AC-RDVT: Ac
yclic Resource
Distance Vect
or Routing
T
a
bl
es f
o
r
Dy
na
mi
c
Gri
d
…
.
(
N
af
i
s
eh B
a
hr
ami
)
69
i
n
creasi
n
g t
h
e
num
ber o
f
re
q
u
est
s
, fai
l
u
re n
u
m
b
ers i
s
redu
ced i
n
im
pro
v
e
d
R
D
V
.
Pr
o
p
o
s
ed m
e
t
hod im
pr
o
v
es
t
h
e n
u
m
b
er o
f
fai
l
e
d re
q
u
est
s
1
6
.
87%
. Fi
g
u
re
8 i
n
di
cat
es
t
h
e res
u
l
t
o
f
seco
nd e
x
peri
m
e
nt
. The
n
u
m
ber of
hops
for each
1000
requests i
s
calculated in
bot
h m
e
t
hods
and the
res
u
lts
are c
o
m
p
ared.
This im
prove
m
ent is
16
.9
8%
.
Fi
g
u
r
e
9
sh
o
w
s
ro
ut
i
ng t
i
m
e i
n
R
D
V a
n
d
Im
pr
ove
d R
D
V
f
o
r
eac
h
10
0
0
req
u
est
s
. P
r
o
p
o
se
d m
e
t
h
o
d
i
m
p
r
ov
es
r
o
u
tin
g ti
m
e
3
6
%
.
Exp
e
r
i
m
e
n
t
al r
e
su
lts sh
ow
t
h
e ef
f
i
cien
cy of pr
opo
sed m
e
t
h
od
i
n
co
m
p
ar
iso
n
with
RDV m
e
th
od
th
at is th
e resu
lt o
f
elimin
atin
g
ex
tra in
form
at
io
n
in
m
e
rg
in
g
stag
e and
p
r
ev
entin
g
to
pr
o
duce
t
h
e
de
cept
i
v
e i
n
f
o
rm
at
i
on.
0
1000
2000
3000
4000
5000
6000
7000
8000
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000
Failure
Numbers
RDV
AC
‐
RDV
Requests
Numbers
0
2000
4000
6000
8000
10000
12000
14000
16000
18000
20000
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000
Hops
Numbers
RD
V
AC
‐
RD
V
Requests
Numbers
Fig 7
.
Av
erage n
u
mber of failed
r
e
quests per
each
1000 requests
Fig.8. Av
erage n
u
mber of hops p
e
r each
1000 r
e
q
u
ests
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:20
88-
870
8
IJEC
E
V
o
l
.
3,
No
. 1,
Fe
br
uar
y
20
13
:
64
–
7
2
70
5.
CO
NC
USI
O
N
In t
h
i
s
pa
per
,
an al
go
ri
t
h
m
is pr
op
ose
d
t
o
sol
v
e two
prob
lem
s
o
f
RDV ro
u
ting
tab
l
es in
On
to
su
m
m
e
t
hod,
whi
c
h
preve
n
t
s
di
rec
t
i
ng req
u
est
s
t
o
of
fl
i
n
e res
o
u
r
ces fre
q
u
ent
l
y
. The i
d
ea i
s
based o
n
t
h
e o
m
i
ssi
on
o
f
m
e
rg
in
g
the u
n
n
ecessary in
form
at
io
n
o
f
n
e
i
g
hbo
rs
i
n
fillin
g
pro
c
ess o
f
ro
u
t
i
n
g tab
l
es an
d
therefo
r
e
p
r
ev
en
tin
g th
e
creatio
n of
d
e
cep
tiv
e info
rm
a
tio
n
in tab
l
es
a
n
d so preventi
ng cycles
in
rou
tin
g m
ech
an
ism
.
Th
e
per
f
o
r
m
a
nce o
f
p
r
op
ose
d
m
e
t
h
o
d
i
s
e
v
al
uat
e
d
wi
t
h
si
m
u
l
a
t
i
on e
xpe
ri
m
e
nt
s whi
c
h c
o
nfi
r
m
t
h
e effi
ci
en
cy
of
al
go
ri
t
h
m
i
n
three as
pect
s:
t
h
e n
u
m
b
er o
f
fai
l
e
d re
que
st
s, ro
ut
i
n
g t
i
m
e
and
n
u
m
b
er of
ho
ps.
Ex
peri
m
e
nt
al
resul
t
s
s
h
o
w
t
h
at
p
r
o
p
o
sed
m
e
t
hod i
m
pro
v
es t
h
e
n
u
m
b
er o
f
fai
l
e
d
re
q
u
est
s
1
6
.
8
7%,
ro
ut
i
n
g t
i
m
e
36% a
n
d
n
u
m
b
e
r
o
f
hopes 16
.98
%
in co
m
p
ar
iso
n
w
i
t
h
RDV
m
e
th
od.
REFERE
NC
ES
[1]
R. Bu
yy
a, S. V
e
nugopal, A.
G
e
ntle Introdu
ctio
n to Grid Computing an
d
Techn
o
logies,
in:
Co
mputerSociety
o
f
India (CSI), vol.
29, no
. 1
,
pp
. 9-
19, 2005
.
[2]
Juan Li, Grid
resource discov
er
y based on
seman
tically
link
e
d vir
t
ual organization
s
,
Future Gener
a
tion
Computer
S
y
stems, pp. 36
1_373, 2010
.
[3]
Juan Li, Son Vuong, A Scalable Semantic Rou
ting Arch
itectur
e for Grid Resource Discover
y
, Conferen
ce on
Parallel
and Distributed
S
y
stems (ICPADS'
05) , 2
005.
[4]
I. Foster, C. Kesselman, Globus: A me
tacomputing infrastructur
e toolkit, In
t. J. High Perform. Comput.Appl. 2,
pp. 115–128
, 19
97.
[5]
M. Mutka, M. Livn
y
,
Schedulin
g remo
te proces
s
i
ng capac
it
y in a works
t
a
tion processing bank computing sy
stem,
in: Proc. of
ICDCS, September
1
987.
[6]
C.
Germain,
V.
Neri,
G.
Fedak,
F.
Cappello
, Xtrem
W
eb: Building an experim
e
ntal platfo
rm for g
l
obal computing
,
in: Proc
. of
IE
E
E
/ACM Grid, Decem
ber
2000.
[7]
A. Chien
,
B
.
C
a
lder,
S
.
Elbe
rt,
K. Bhat
ia
, En
tro
p
ia:
Archit
ec
tur
e
and
perform
an
ce of
an
ent
e
rpr
i
s
e
des
k
top
grid
s
y
stem, J. Parallel
Distr
i
b. Comput.,2003
.
[8]
F. Berman, et al., Adaptive computi
ng on
the grid
using AppLeS
,
TPDS, 2003.
[9]
M.O. Near
y
,
S.P. Br
y
don, P. Km
iec,
S. Rollins
,
P. Capello
, JavelinCC: Sc
alab
ilit
y
issues in global com
puting,
Future Gener
.
C
o
mput.S
y
s
t. J. p
p
. 659-674
, 199
9.
[10]
M. Cai, M. Frank, J. Ch
en, P
.
S
zekely
,
MAAN: A multi-attribute
addre
ssable network for
grid informatio
n
services, in
: Th
e 4th In
tern
ation
a
l Workshop on
Grid Computing
,
pp
. 184-191
, 2
003.
0
0.
005
0.
01
0.
015
0.
02
0.
025
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000
Time
(s)
RDV
AC
‐
RDV
Requests
Numbers
Fig 9. Rou
ting
time per
each 100
0 requests
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE I
S
SN
:
208
8-8
7
0
8
AC-RDVT: Ac
yclic Resource
Distance Vect
or Routing
T
a
bl
es f
o
r
Dy
na
mi
c
Gri
d
…
.
(
N
af
i
s
eh B
a
hr
ami
)
71
[11]
A. Iam
n
itchi, I
.
F
o
s
t
er, On full
y decentr
ali
zed re
s
ource di
s
c
over
y
in grid environm
ents
, in: P
r
oceeding of the 2nd
IEEE/ACM Internation
a
l Works
hop on Grid
Co
mputing, Denv
er
, pp
. 51-62
, 200
1.
[12]
K. Karaoglanog
lou, H. Kara
tza “Resource discover
y
in a d
y
namical Gr
id s
y
stem based on re-routing tab
l
es
”,
Journal of Simulation
Modelling
Practi
ce
and
Theor
y
, vol. 16
, pp
.
704-720, 2008
.
[13]
S. Tangpongpr
asit,
T. Katag
i
ri, H.
Honda,
T. Yuba, A time-to-liv
e based
r
e
servation
algor
ithm on fully
decen
tral
iz
ed r
e
source d
i
scover
y
in grid
com
putin
g, Para
ll
el Com
p
uting, pp. 529-5
43, 2005
.
[14]
R.-S. Chang
,
M.-S.Hu, A resource disc
ov
er
y
tr
ee using bitmap f
o
r grids,
Future
Gener.Comput.S
y
s
t., pp
. 29–37,
2010.
[15]
M. Bawa, G.S. Manku, P.
Rag
h
avan, SETS: Search
enhan
ced
b
y
top
i
c segmentation
,
in
: Proceedings of AC
M
SIGIR, pp. 306-
313, 2003
.
[16]
A. Iamnitchi,
M. Ripeanu, I.
T. Foster, Lo
catin
g data in
peer-to-peer sc
ien
tifi
c
coll
abora
tions,
in: Proc
eedings
of
International Wo
rkshop on Peer-
t
o-Peer
S
y
s
t
ems,
IPTPS, pp. 232-
241, 2002
.
[17]
W. Nejdl, M. Wolpers, W. Siber
s
ki,
C. Schmitz,
M.T. Sch
l
osser,
I. Brunkhor
st, A
.
Lser
, Super-p
eer-based routing
and clus
ter
i
ng s
t
rateg
i
es
for RDF
-
bas
e
d peer-to-
peer netw
orks
, i
n
: P
r
oceedings
of Internat
ional
W
o
rld W
i
de W
e
b
Conference, WWW,
pp.
536-543,
2003.
[18]
C.
H.
Ng,
K.
C.
Sia,
C.
H.
Chang,
Adva
nced peer cluster
i
ng and firework quer
y
m
odel in the p
eer-
t
o-peer n
e
twork
,
in: Proceedings
of Intern
ation
a
l
World Wide
Web Conferen
ce, W
WW, Poster ID
S130.
[19]
A. Crespo, H. G
a
rcia-Molina,
Semantic over
l
ay
networks for p2p s
y
stems,
Tech
nical report, Stanford University,
2002.
[20]
X. Tem
p
ich
,
S
.
S
t
aab,
A. W
r
ani
k
, RE
MINDIN'
: semantic quer
y
routing
in p
eerto- peer
network
s
based on social
metaphors International
World Wide Web Confer
ence (WWW),
New York,
USA,
pp.
640-649,
2004.
[21]
S. Castano
,
A.
Ferrara, Montan
elli
, D. Zu
cchelli, H
e
lios: A general fra
mewor
k
for ontolog
y
-
based knowledg
e
sharing and
evol
ution in P2P s
y
s
t
em
s, in: I
EEE
Pr
oc. of DEXA
W
E
BS 2003 Workshop, Prague, Czech
Republ
ic
,
1(5), pp
. 597-60
3, 2003
.
[22]
S.
Ca
sta
no,
A.
Fe
rra
ra,
S.
Monta
n
elli
, E. Pagani, G. Rossi, Ontolog
y
addres
s
a
ble con
t
ents in
P2P networks,
in:
Proceedings of
the WWW'
03 Workshop on Semantics in Pe
er-to
-
Peer and
Grid
Computing, pp
. 5
5
-68, 2003
.
[23]
[23]
H. Zhuge,
RuixiangJia,
Jie
Liu, Semantic link network builder and
intelligent semantic
bro
w
ser, Concurr
e
n
c
y
- Practice and
Experien
ce, pp
. 1
453_1476, 2004
.
[24]
H. Zhuge, Yunchuan Sun, RuixiangJia, Ji
e Liu,
Algebra model
and experiment
f
o
r
semantic link network,
IJHPCN,
pp. 227_238
, 20
05.
[25]
H. Zhuge, Co
m
m
unities and em
erging sem
a
ntics in sem
a
nt
ic l
i
nk network
:
Discover
y
an
d learn
i
ng, I
E
E
E
Transactions on
Knowledge and
Da
ta
Engineerin
g, pp
. 785-799
,
2009.
[26]
H. Zhuge, X. Li, Peer-
t
o-peer in metric space
and se
mantic sp
ace, IEEE Trans
acti
ons on Knowledge and D
a
ta
Engineering, pp.759-771, 2007
.
[27]
H. Zhuge, S
e
mantics, resource
and grid, Future
Generation Computer S
y
stems, p
p
. 1-5
,
2004
.
BIOGRAP
HI
ES
OF AUTH
ORS
NafisehBahrami
received h
e
r B.S. (2008) from Azad
university
of Tabr
iz, Iran. She is
currently
M.S student in Azad uni
versity
of Tab
r
iz, Iran
.
Her re
s
earch int
e
res
t
s
includ
e grid
computingand w
i
reless sensor network.
Ahmad Habibi
zad
Navin
He rece
ived th
e B.S
.
degree in app
l
i
e
d m
a
them
ati
c
s
from
Tabriz
University
,
Tabr
iz, Ir
an,
in 1999
. He receiv
ed
th
e M.S. degree in computer arch
itecture from
University
of Science and Research Branch
, Is
lamic Azad University
, Tehr
an, Ir
an, in 2003
and the
P
h
.D. i
n
com
puter ar
c
h
ite
cture
from
Univers
i
t
y
of S
c
ien
ce
and Res
earch
Branch
,
Islamic Azad U
n
iversity
, Tehran, Iran
,
in 2007
.H
is resear
ch in
terest
includ
es
data-or
i
ented
approach
, robo
tic, soft
computin
g and prob
ab
i
lit
y and
st
atist
i
c
.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:20
88-
870
8
IJEC
E
V
o
l
.
3,
No
. 1,
Fe
br
uar
y
20
13
:
64
–
7
2
72
Mina alavighi
r
e
ceiv
e
d her
B.S.
(2007) from Azad univ
e
rsity
of
Shabestar, Iran
and her
M.S
(2011) from Azad university
of Tabriz, Iran
.
Her
r
e
search
interests
includ
e grid
co
mputing and
wireless sensor
network.
Ali AsgharPourhajiKaz
e
m
rece
ived a B.S
c
. de
gree in com
pute
r
engine
eringfro
m
Univers
i
t
y
of Isfahn and
also a M.S. deg
r
ee in
computer
engineer
ing
fromShahidBeheshti University
in
Tehran
. He is currently
a Ph.D
. student of
co
mputerengineering in
S
c
ienc
e a
nd Res
earch
branch of Is
l
a
m
i
c Azad Univ
ers
i
t
y
in T
e
hran
.His
current
res
e
arch
inter
e
s
t
s
inc
l
ud
e dis
t
ribu
ted
s
y
stems, Grid
co
mputing and C
l
o
ud computing.
Evaluation Warning : The document was created with Spire.PDF for Python.