TELKOM
NIKA
, Vol. 11, No. 12, Decem
ber 20
13, pp.
7476
~74
8
3
e-ISSN: 2087
-278X
7476
Re
cei
v
ed
Jun
e
26, 2013; Revi
sed Aug
u
st
5, 2013; Accepted Augu
st
29, 2013
Anti-collision Algorithm for RFID based on Continuous
Collision Detection
Liu Zhen-p
e
ng*
1
, Guan Z
h
en
y
a
ng
1
, S
h
ang Kai-
y
u
2
, Cai Wen-lei
2
1
Col
l
eg
e of Ele
c
tronic an
d Informatio
n
Engi
n
eer
i
ng, Heb
e
i
Univers
i
t
y
, Ba
o
d
in
g, 071
002,
Chin
a
2
Net
w
o
r
k Ce
ntre, HeBei U
n
ive
r
sit
y
, Bao
d
in
g, 071
00
2, Chin
a
*Corres
p
o
ndi
n
g
author, e-ma
i
l
: lzp@h
bu.ed
u
.
cn
A
b
st
r
a
ct
Tag esti
mation
can
i
m
pr
ove
the thro
ug
hput
of
the
UHF
passiv
e
RFID
systems. It p
l
ays a
n
importa
nt role i
n
anti-co
llisi
on
alg
o
rith
m. In order to
reduc
e the co
mp
lexity of the estimati
o
n
alg
o
rith
m an
d
the hardw
ar
e supp
ort, a ne
w
algorith
m
b
a
sed o
n
the contin
uo
us
de
tect
i
o
n
m
e
chan
i
s
m
h
a
s
be
en
prop
osed. Acc
o
rdi
ng to the d
i
fferent
pro
bab
i
lity of the col
l
i
s
ion a
nd i
d
l
e
, the nu
mber of
the contin
uo
u
s
detected sl
ots must be set in
dep
en
dently. This sch
e
m
e ca
n simplify the
system an
d re
duce the extra
consu
m
ption
b
y
less d
e
tectin
g timesl
ot. Simulati
on re
s
u
lts i
ndic
a
te the
pro
pose
d
sch
e
m
e
can i
m
prove t
h
e
efficiency without complic
ate system
.
Ke
y
w
ords
:
RFID, Q-algorith
m
, tag estimati
on
, conti
nuo
us de
tection, prob
ab
ility of collis
io
n
Copy
right
©
2013 Un
ive
r
sita
s Ah
mad
Dah
l
an
. All rig
h
t
s r
ese
rved
.
1. Introduc
tion
Radi
o fre
que
ncy id
entificat
ion (RFI
D) te
chn
o
logy h
a
s bee
n
widely
use
d
a
s
one
of th
e
key technolo
g
y of the Internet of Thi
n
gs [1,
2]. Ultra hig
h
freq
u
ency (UHF)
(860
~96
0
MHZ
)
identificatio
n
with hi
ghe
r e
fficiency
and
furthe
r read
ran
ge
ha
s b
een
deem
ed
to have
bri
g
ht
future compa
r
ing
with the l
o
we
r on
e. In the RFI
D
sy
stem, if there a
r
e multiple ta
gs in the
ran
g
e
of the anten
na, tags
will
re
spo
nd th
e re
ade
r si
multaneo
usly
. Tag collisi
on will
hap
p
e
n
inevitably. As a result, the
collisio
n pro
b
lem ha
s be
come the im
portant facto
r
that influences
the efficien
cy and a
c
cura
cy
of RFID syst
em.
The m
o
st
po
pular inte
rnat
ional
sol
u
tion
of anti
-
collision i
s
the
time divisi
on
multiple
acce
ss
(T
DM
A) tech
nolog
y. Because the tag st
ru
cture i
s
sim
p
le
and the T
D
MA scheme
is
conve
n
ient. In the low fre
quen
cy ban
d
,
main
ly approache
s incl
u
de pu
re ALO
H
A algo
rithm
,
timeslot ALO
H
A algo
rithm
,
frame timeslot ALOHA al
gorithm, dyn
a
mic frame ti
meslot AL
OHA
algorith
m
, etc. In the high
freque
ncy
ba
nd, the
soluti
on is the EP
Cglo
bal
UHF
Cla
s
s1 Ge
n
2
algorith
m
[3]
(sta
nda
rd
Q-alg
o
rithm
)
whi
c
h
ha
s bee
n p
r
om
ulgated
by t
he Internatio
nal
Orga
nization
for Standa
rdi
z
ation in 2
0
0
5
.Due to
the
stand
ard
Q al
gorithm h
a
s t
he problem t
hat
it adapt the
Q value
slo
w
ly espe
cially
there
ar
e
ma
ssive ta
gs [4]
,
tag estimati
on me
cha
n
ism
has be
en introdu
ced into the algo
rithm. Although,
the
s
e algo
rithm
s
will incre
a
se the compl
e
xity
of the system
unexpe
ctedl
y. In
order to solve tho
s
e p
r
oble
m
s, a ne
w improved a
l
gorithm
calle
d
an
anti-collisi
on
al
gorithm for RFID based
on
continuous detect
ion has
been propo
sed in this
pape
r. Thi
s
a
ppro
a
ch
can
determi
ne th
e num
ber
of
contin
uou
s d
e
tection
slot
s indep
end
entl
y
according to the difference
of t
he idle and colli
sion probabilities.
2. Rese
arch
Metho
d
The sta
nda
rd
Q-alg
o
rithm
prom
ulgated
by
the EPC Gen2 i
s
ge
neral
simila
r
as th
e
dynamic fram
e timeslot AL
OHA anti-coll
ision al
gor
ith
m
(DFSA)
actually. Unlike
the tradition
al
DFSA, the G
en-2
alg
o
rith
m allo
ws ea
rl
y adjustm
ent
of frame l
engt
h within
ea
ch
slot fra
m
e. Th
e
frame
size ca
n be d
e
cid
e
d
by (1). Thi
s
early
adj
ustm
ent ca
n imp
r
ove rea
d
pe
rf
orma
nce whe
n
frame len
g
th is extremely a
ppro
p
ri
ate.
2
Q
Fr
am
e
=
(1)
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
e-ISSN:
2087
-278X
Anti-colli
sion
Algorithm
for RFID b
a
se
d on Co
nt
inuo
u
s
Colli
sio
n
De
tection (Li
u
Z
hen-pen
g)
7477
Duri
ng the process of identifi
cation there will be three states
: Idle state (idle),
no tag
respon
se; su
ccessful stat
e
(su
c
cee
d
), o
n
ly one tag re
spo
n
se; colli
sion state
(colli
sion
), multipl
e
tags re
sp
on
se.
()
Q
r
oun
d
Q
fp
=
(2)
Figure 1. Q Value Adju
stm
ent Flow Cha
r
t
Studies have
sho
w
n that
when the n
u
mbe
r
of slo
t
s that each
identification
fram
e
contai
ns is g
eneral e
qual
to the
numb
e
r of
tag
s
,
the system can achieve
maxim
u
m
recognitio
n
efficien
cy (3
6
.
8%) [5]. In order to
adj
ust t
he le
ngt
h of i
dentificatio
n f
r
ame, flo
a
ting
point
numb
e
r
f
p
Q
and a
c
cumul
a
ting pa
ram
e
ter
c
(
[0
.
1
,
0
.
5
]
c
Î
) are u
s
ed to adj
ust
Q. Q value i
s
calculated
by
roun
d
f
p
Q
(2) .Whe
n the int
e
rrogato
r
ob
serves
colli
sio
n
state, the
f
p
Q
value increa
ses by
c
.
Whe
n
the
interrogato
r
observe
s idl
e
state, th
e
f
p
Q
value
de
cre
a
ses by
c
.When the
interrogato
r
observe
s
su
cceed state,
the
f
p
Q
value
remai
n
s
un
chang
ed. The
method fo
r
cho
o
si
ng the
slot-cou
nt parameter i
s
sh
o
w
n in Figu
re
1.
Main co
mma
nd of inventory round: Que
r
y, QueryRep,
QueryAdju
s
t [6].
Query: Initialize identifi
c
ation pro
g
ra
m. Set
the initial Q of each tag. Each tag counte
r
will sel
e
ct a
number in the range
[0
,
2
1
]
Q
ran
domly. Tags
with the ran
d
o
m numb
e
r zero will
reply the re
ad
er in this time
slot immedi
ately.
Query
R
ep
A
u
to de
cre
a
se
d com
m
an
d. If tags re
ceiv
e this
comm
and, their
co
unters
will be decreased by 1. Tags with the
number
zero wil
l
reply the reader.
QueryAdj
ust:
Adjust the value of Q. When
the valu
e of Q has b
een chan
ged
by (2),
read
er
will se
nd this comm
and. Tag
s
ch
oose anoth
e
r numbe
r bet
wee
n
[0
,
2
1
]
Q
-
, then a new
roun
d of ident
ification will
start.
Query
R
ep
co
mmand
will b
e
se
nt after t
he idle
and
succee
d state.
If the rou
nd
value of
f
p
Q
is different from the curre
n
t Q value, t
he interrogat
or will send the Que
r
yAdj
ust com
m
an
d
to adju
s
t the
Q value fo
r id
entifying un
re
ad tag
s
. Call
these
co
mma
nds in a
c
cord
ance with
the
provisi
o
n
s
of the orde
r. Th
e read
er
will identify
the tags con
s
tantly until all tags a
r
e identified.
3. An An
ti-collision Algorithm
based
on Con
t
inuo
us Detection
Although th
e
EPCglo
bal
Gen-2 p
r
ovid
es
early
adju
s
tment
of fra
m
e len
g
th fo
r anti
-
colli
sion alg
o
rithm, the parameter Q ca
n’t obtains
ap
prop
riate initi
a
l value quickly espe
cially
in
the exce
ssiv
e
tags situati
on. So estimation
numb
e
r of tags sho
u
ld be execu
t
ed before th
e
identificatio
n started. The value
of
Q will
be
se
le
cte
d
by the e
s
ti
mation result. Studies h
a
ve
provide
d
the
relation
shi
p
b
e
twee
n time
sl
ot numb
e
r
an
d tag
numb
e
r. Whe
n
the
timeslot
num
b
e
r
is e
qual t
o
th
e un
rea
d
tag
s
, the
syste
m
will
rea
c
h
th
e maximum
e
fficiency [7].
These m
e
tho
d
s
whi
c
h
provid
ed by
previou
s
studie
s
mai
n
ly incl
ude
th
e lo
we
r limit
value al
gorith
m
(L
ow Bou
n
d
,
LB) [8], Schoute estimatio
n
algorithm [
9
], chebysh
e
v
inequality estimation alg
o
rithm [10], etc.
Evaluation Warning : The document was created with Spire.PDF for Python.
e-ISSN: 2
087-278X
TELKOM
NIKA
Vol. 11, No
. 12, Dece
mb
er 201
3: 747
6 – 7483
7478
But these ta
g estimatio
n
algorithm
s
need a
stro
n
g
hardware
sup
port a
nd
will bri
ng hu
ge
addition
al po
wer
con
s
u
m
p
t
ion in reality. Relative
to the simpl
e
structure of rea
der, it will bri
ng
lots of operation co
st.
In ord
e
r to
solve this
pro
b
lem, a m
o
re sim
p
le tag
estimatio
n
method
call
e
d
anti-
colli
sion alg
o
rithm base
d
o
n
contin
uou
s
detecti
o
n
is p
r
opo
se
d. Basi
c idea: Set the first
m
slot
s
as
estimatin
g
timesl
ots
and m
onitor them. Get
the commu
nication
state
(free,
su
cce
ss,
colli
sion
) of the first
m
slot
s. If the continu
ous idle
slots
or colli
sion slots have bee
n detecte
d,
the value of Q will minu
s
or plu
s
1 im
mediately.
In this way, the interrogato
r
can adj
ust the
frame l
ength
only after three o
r
fo
ur tim
e
sl
ots.
So
id
entification
proce
s
s
will b
e
more
effectiv
e.
Unli
ke previo
us alg
o
rithm,
this app
roa
c
h
determin
e
the numbe
r of continu
o
u
s
detectio
n
slo
t
s
indep
ende
ntly.
Next three
parts, the principle of the
c
ontinuous detection
me
chanism
will be given.
Then a
c
cordi
ng to the prin
ciple the n
u
m
ber of monito
ring time
slots can be
cal
c
ul
ated.
3.1. Diffe
ren
ce of the Mo
nitoring Slots
Suppo
se th
ere are
n
tags to be read. A
c
cordi
ng to
the Bernoulli
experim
ent, if there
are
x
tags choose a
same
slot, the probability will be calcul
ated by:
11
()
(
1
)
x
xn
x
en
PC
Nn
-
=-
(3)
The probability of the idle slot is cal
c
ulated by:
00
le
11
()
(
1
)
n
id
n
PC
Nn
=-
(4)
The probability of the succes
s slot is
cal
c
ulated by:
11
1
11
()
(
1
)
n
su
c
n
PC
Nn
-
=-
(5)
The probability of the collisi
on slot is
cal
c
ulated by:
le
1
co
l
i
d
s
u
c
PP
P
=-
-
(6)
Cal
c
ulate the
derivative of
s
uc
P
and set it equal to 0.
If
s
uc
P
want to ap
proa
ch the m
a
ximum, there must be
Nn
=
and
(m
ax)
0
.
3
6
8
suc
P
=
.
Whe
n
Nn
=
,
e
1
(1
)
n
id
l
P
n
=-
and
1
1
(1
)
n
su
c
P
n
-
=-
.
If
n
is big eno
u
gh,
e
s
uc
i
d
l
PP
»
,then
le
1
1
0.
36
8
0
.
3
68
0
.
26
4
co
l
i
d
suc
PP
P
=
--=
-
-
=
Obviou
sly, in
the conditio
n
of high
effici
e
n
cy
the
p
r
ob
a
b
ility of collisi
on time
sl
ot i
s
le
ss
than the
prob
ability of idle t
i
me sl
ot,
e
col
i
dl
PP
<
. So the dete
c
ted
numbe
r
of co
ntinuou
s idl
e
slots (
i
m
) sho
u
ld big
g
e
r than the
co
llision o
nes(
c
m
).
ic
mm
>
(7)
3.2. Analy
s
is
of the Conti
nuous Idle Slots
Suppo
se
'
n
is the estimated n
u
mbe
r
of tags. Then define
the estimate
error a
s
:
'
('
)
nn
de
v
n
n
-
=
(8)
('
)
de
v
n
is use
d
to measure the d
e
v
iation of tag estimation.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
e-ISSN:
2087
-278X
Anti-colli
sion
Algorithm
for RFID b
a
se
d on Co
nt
inuo
u
s
Colli
sio
n
De
tection (Li
u
Z
hen-pen
g)
7479
Identifying tags i
s
a Poisson
process.
Due to the
concept
of the
timeslot, the
pro
c
e
ss
has b
een
si
mplified. The
numbe
r of the estimate
d
value is
'
n
.Each fram
e ha
s
N
slot
s.
I
f
t
he
system
dete
c
ts idle time
slot, it will
ca
ll the Q
ueryRep
comm
a
nd auto
m
atically. Then ta
g
counters
will
be decreased by 1. For
moni
toring timeslot, the probability for first
i
m
contin
uou
s
idle slot
s is:
i
*
1
(1
)
(
1
)
(
)
i
i
i
mn
N
mn
mN
n
ii
N
m
mm
P
NN
e
=-
=-
»
(9)
Set
/0
nN
（）
ll
=>
,then
i
(1
/
)
i
m
m
Pe
l
=
(
m
is p
o
sitive i
n
teger), In
(0
,
+
)
¥
area,
i
m
P
is
monoton
e de
cre
a
si
ng fun
c
tion.
Then the
criti
c
al value of
('
)
de
v
n
will be calculated as:
()
(
/
2
)
d
e
vN
d
e
vN
=
Then,
1
()
1
nN
Nn
de
v
N
nn
l
-
-
==
=
-
2
()
2
N
n
N
de
v
n
-
=
As
2
N
nN
££
,then
1
2
()
1
22
N
n
N
de
v
nl
-
==
-
. Set
()
(
)
2
N
de
v
N
d
e
v
=
,s
o
0.
75
l
=
.
As a re
sult, when
0.
7
5
l
<
,
()
(
)
2
N
de
v
N
de
v
³
.
Set
0.
7
5
l
=
, then:
i
0.
75
(1
/
)
i
m
m
Pe
=
In the proba
bility theory,
if the probabi
lity is
very close to zero (whi
ch mea
n
s event
appe
ars with
very low fre
q
uen
cy in a large num
ber
of repe
ated te
sts), this eve
n
t will be
calle
d
as the small probability event. Range
(0
.
0
1
,
0
.
0
5
)
is commo
nly used a
s
the st
anda
rd rang
e
.
3
i
m
=
,
i
0.
10
54
m
P
»
;
4
i
m
=
,
i
0.0498
m
P
»
Whe
n
4
i
m
=
,
i
m
P
achi
eves the requi
rement and
choo
se
4 a
s
the contin
uou
s
idle slot
s
finally. So
i
m
is set
to 4,
whi
c
h me
an
s that
wh
en
4
co
ntinuou
s i
d
le
sl
ots a
r
e
dete
c
ted
0.
75
l
>
woul
d be th
e
small p
r
o
babi
lity event. Then
0.
7
5
l
£
can b
e
in
ferre
d. The
sl
ots nu
mbe
r
o
f
each
frame will be
/2
N
and that will p
e
rform
better
than
N
.Q will minus 1,
/2
Fr
a
m
e
N
=
.
3.3. Analy
s
is
of the Conti
nuous Collision Slots
Whe
n
collisio
n happ
en, th
ere m
u
st be
multip
le tag
counters valu
e
are
zero. Th
en the
system will
start the collision algo
rithm
.
Proc
e
ssi
ng method: Ch
a
nge colli
sio
n
tags counte
r
s
value
from 0 to
0XFFFF. These collisi
on
tags
will
stay in epicy
cl
ic inv
entory and wait for the
system a
d
ju
sting Q and
di
spe
r
si
ng the
colli
sion
tag
s
.
This p
r
o
c
e
s
s continue
s
until the wh
ol
e
inventory cycl
e is end.
Bec
a
us
e
ic
mm
>
, the range of
c
m
can
be inferred. The value ran
ge sh
ould b
e
{2
,
3
}
.
The probability for first
c
m
con
t
inuou
s colli
si
on slot
s is:
Evaluation Warning : The document was created with Spire.PDF for Python.
e-ISSN: 2
087-278X
TELKOM
NIKA
Vol. 11, No
. 12, Dece
mb
er 201
3: 747
6 – 7483
7480
c
mm
1
1
**
1
11
[1
(
1
)
(
1
)
]
11
[1
(1
)
(
1
)
]
11
[
1
()
()
]
c
c
c
c
nn
mc
nn
NN
m
NN
nn
m
NN
N
n
PP
NN
N
n
NN
N
n
eN
e
-
-
-
==
-
-
-
-
=-
-
-
-
=-
-
(10
)
As
0
n
N
（）
ll
=>
, then:
c
1
m
11
[1
(
)
(
)
]
c
N
m
P
ee
l
l
l
-
=-
-
In
(0
,
+
)
¥
area,
c
m
P
is monotone in
crea
sing fun
c
tion.
As
2
N
nN
££
,
22
(2
)
1
Nn
de
v
N
nl
-
==
-
1
()
1
nN
nN
de
v
N
nn
l
-
-
==
=
-
Set
()
(
2
)
de
v
N
d
e
v
N
=
,then
1.5
l
=
Whe
n
1.
5
l
>
,
()
(
2
)
dev
N
d
e
v
N
³
.
Set
1.
5
l
=
,then
c
m
P
value ca
n be
calculate, Whe
n
N
is big enoug
h, there i
s
1/
N
ll
-»
.
2
c
m
=
,
c
0.
19
57
m
P
»
;
3
c
m
=
,
c
0.0866
m
P
»
Whe
n
3
c
m
,
c
m
P
is ve
ry nea
r to
the
rang
e
(
0
.
0
1
,
0.
05
)
an
d it ha
s
achieved th
e
requi
rem
ents of the range
of
c
m
(
{2
,
3
}
). Choo
se 3 as the co
ntinuou
s colli
sion
slots fin
a
lly. So
c
m
is set to 3,
which m
ean
s t
hat whe
n
3 continuo
us coll
isi
on slots are
dete
c
ted.
1.
5
l
<
will be
the small
pro
bability event
. Then
1.
5
l
³
can
be inferred. The slot
s num
ber of each frame will
be
2
N
and that will perfo
rm b
e
tter than
N
. Q
will plus 1,
2
F
ra
m
e
N
=
.
3.4. An Anti-collision Algorithm
based on Continuous Detecti
on
In co
ncl
u
si
on
, the p
r
o
c
e
s
s of th
e n
e
w algo
rithm
ca
n be
de
scrib
ed a
s
foll
ow:
In th
e
begin
n
ing
of each invento
r
y cycle,
the
reade
r will
mo
nitor the first
f
our slots.
If
there are
fo
u
r
continuous idle slot
s or
three continuous colli
sion
slots be detected,
the reader
will order
Q
minus o
r
plu
s
1. Then the read
er
sen
d
the
Que
r
y Co
mmand a
gain
and sta
r
t a new invento
r
y
roun
d. This
continuo
us det
ection me
ch
a
n
ism is
sho
w
n in Figure 2.
Acco
rdin
g to this method,
the interrogat
or can a
dapt
the frame le
ngth only
after 4
slots
wh
ich i
s
more q
u
ickly than th
e
norm
a
lized ru
le.
4. Simulation Resul
t
and
Performanc
e Comparis
o
n
We u
s
e Ma
tLab to sim
u
late the im
proved
algo
rithm and co
mpare it with the
conve
n
tional Q-alg
o
rithm.
G
(the ave
r
ag
e
packet ex
cha
nge
cap
a
city) is offe
red tra
ffic and it indi
cate the l
oad
of
the interrogat
or. Define the
system effici
ency(
S
) as
follows
:
/_
Sp
l
e
n
S
n
o
w
tim
e
Sr
at
e
=
(11
)
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
e-ISSN:
2087
-278X
Anti-colli
sion
Algorithm
for RFID b
a
se
d on Co
nt
inuo
u
s
Colli
sio
n
De
tection (Li
u
Z
hen-pen
g)
7481
Figure 2. The
Propo
sed
Co
ntinuou
s Detection Me
ch
a
n
ism
Splen is th
e
sum
of pa
cke
t
length. Srat
e is
the
symb
ol rate. n
o
w_t
i
me is th
e time that
identify all of tags. So
S
can
also b
e
de
scribed a
s
:
P
a
c
k
e
t
t
r
ans
m
i
s
s
i
on
t
i
m
e
S
T
a
g
id
e
n
tifi
c
a
tio
n
tim
e
=
(12
)
Whe
n
simulat
i
ng this prog
ram, the
scop
e of
G
is
[
0
.5
,2
.0
]
. 100
times te
sts
h
a
ve bee
n
done for e
a
ch tag. The bit rate is 512kbps an
d t
he symbol rat
e
is 256
kpb
s
, p
a
cket length i
s
128, normali
zed tra
n
smission d
e
lay is 0.01s. Then
simulate the
standa
rd Q
-
algorith
m
in the
same exp
e
ri
ment enviro
n
m
ent.
From Fi
gu
re
3 we
ca
n g
e
t con
c
lu
sio
n
s
as follo
ws: (1
) When th
e o
ffered traffic
G
is
same, the i
m
prove
d
alg
o
rithm id
entification
efficie
n
cy
S
is high
e
r
than
stand
ard
Q valu
e
algorith
m
. It i
s
clo
s
e
r
to
th
e theo
reti
cal
optimum. T
h
e imp
r
oved
q
uantity is ab
o
u
t
3%
; (2)
With
G
(num
ber
of tags) in
cre
a
si
ng, throu
ghp
ut will
incre
a
s
e firstly but then de
crea
se
. The de
cline
of the improv
ed algo
rithm i
s
less than
standa
rd Q
-
alg
o
rithm.
0.
5
1
1.
5
2
0.
2
9
0.
3
0.
3
1
0.
3
2
0.
3
3
0.
3
4
Th
r
o
u
g
h
p
u
t
of
t
h
e sy
st
em
O
ffe
r
e
d
t
r
a
ffi
c
(
G
)
T
h
rou
ghput
(S
)
S
t
anda
rd Q-
al
go
ri
t
h
m
I
m
pr
ov
ed al
gor
i
t
hm
Figure 3. Through
put of System
Evaluation Warning : The document was created with Spire.PDF for Python.
e-ISSN: 2
087-278X
TELKOM
NIKA
Vol. 11, No
. 12, Dece
mb
er 201
3: 747
6 – 7483
7482
The influ
e
n
c
e
of increa
sin
g
num
ber of
tags
i
s
small
e
r
tha
n
the st
anda
rd Q-al
g
o
rithm.
System has
better
stabilit
y compari
n
g to t
he
pure ALOHA, ti
meslot A
L
OHA (SA),
frame
timeslot ALO
H
A (FSA) al
gorithm. The
s
e algo
rithm
s
will make the identifica
t
ion efficiency
decli
ne serio
u
sly wh
en tag
s
increa
se
ra
pidly [11]. The improve
d
al
gorithm h
a
s a
d
vantage
s.
Average
Dela
y time is defined as:
*
*
T
p
le
n
S
r
a
te
AD
T
Sr
at
e
s
p
e
n
d
p
l
e
n
=
(13
)
Tplen i
s
the
sum of all th
e identify dat
e l
ength,
spe
nd is th
e nu
mber
of pa
cket. Then
ADT is norm
alized.
From
Figu
re
4 we
can
get
con
c
lu
sio
n
s a
s
follo
ws: (1)
Contin
uou
s
d
e
tection
me
chani
sm
has d
e
crea
se
d averag
e time delay
of the system
si
gnifica
ntly, wh
ich al
so me
ans that it won't
bring
mu
ch
extra
con
s
u
m
ption a
nd t
he
system
b
e
com
e
m
o
re
efficient.
(2) With
G
(ta
g
s
numbe
r) in
creasi
ng, the
average
d
e
lay of t
he system wo
uld de
cre
a
se grad
ually. So
advantag
es
of the ne
w a
l
gorithm
will
become
m
o
re and m
o
re
obviou
s
ly especi
a
lly for the
massive tags.
0.
5
1
1.
5
2
20
25
30
35
40
45
O
f
fe
r
e
d
t
r
a
ffi
c
(
G
)
A
v
er
ag
e D
e
l
a
y
t
i
m
e
S
t
andar
d Q
-
al
gor
i
t
hm
I
m
pr
ov
ed al
gor
i
t
hm
Figure 4. Average
Delay Ti
me of System
We
can
draw the co
ncl
u
si
on thro
ugh th
e exper
i
m
ent
al re
sults: T
h
e ne
w alg
o
rit
h
m not
only improves the
system
efficien
cy but also enhances the abilit
y to confront
the problem
of
tags in
cre
a
si
ng qui
ckly.
5. Conclusio
n
Tag estim
a
tion algorithm
plays an im
portant
role in the anti-collision algorit
h
ms of
RFID UHF sy
stem
s. In order to redu
ce t
he co
m
p
lexity of the tag estimation and the dema
nd o
f
high-l
e
vel hardwa
r
e supp
ort, the continu
ous d
e
te
ctio
n
mecha
n
ism has b
een introdu
ced into t
he
tag colli
sion
algorith
m
. Th
e differen
c
e
betwe
en the
colli
sion p
r
o
b
ability and idl
e
pro
bability has
been
prove
d
by the mat
h
analy
s
is.
Then the
nu
mber
of the
contin
uou
s
frame mu
st
be
con
s
id
ere
d
in
depe
ndently
(3 an
d 4). Si
mulation
resu
lts prove th
at the new
alg
o
rithm
spe
e
d
s
up the frame
length adju
s
t
m
ent and im
prove
s
the re
cog
n
ition efficien
cy witho
u
t
increa
sin
g
a
n
y
compl
e
xity of the
system. I
t
can al
so
reduce
the
average delay time and
enhance the ability for
dealin
g with the su
rgin
g tags.
Referen
ces
[1]
W
e
i W
e
i, Kevi
n Curra
n. Indo
or Rob
o
t Loca
l
isatio
n
w
i
th Ac
tive RF
ID.
IAES Internatio
nal
Journa
l of
Robotics and Automation (IJRA)
. 2012; 1(3): 137-
144.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
e-ISSN:
2087
-278X
Anti-colli
sion
Algorithm
for RFID b
a
se
d on Co
nt
inuo
u
s
Colli
sio
n
De
tection (Li
u
Z
hen-pen
g)
7483
[2]
Jian
xi
n D
eng.
Architecture
D
e
sig
n
of t
he V
ehicl
e T
r
ackin
g
S
y
stem B
a
s
ed o
n
RF
ID.
TEL
K
OMNIKA
Indon
esi
an Jou
r
nal of Electric
al Eng
i
ne
eri
n
g
.
2013; 1
1
(6): 2
997-
300
4.
[3]
EPC Glo
bal. IS
O1800
0-6c.EP
C
®
radi
o-frequ
enc
y
pr
otoco
l
s class-1 ge
nera
t
ion-2 UHF
RF
I
D
protoc
o
l
for commun
i
ca
tions at 8
60 M
H
z–9
60 MHz
versio
n.
Intern
ation
a
l Orga
ni
zation for Sta
n
dard
i
zatio
n
.
Sing
apor
e. 200
6.
[4] Che
n
W
en-T
z
u.
A new
RF
ID
Anti-coll
i
si
on
al
gorith
m
s
for th
e EPC
glo
b
a
l
U
H
F
Class-
1 Ge
nerati
o
n
-
2
standar
d
. Ub
iq
uitous
Intell
ig
e
n
ce &
Com
put
ing
an
d
9th
In
ternatio
nal
Co
nferenc
e o
n
A
u
tonom
ic &
T
r
usted Computing (UIC/A
T
C
). 2012; 9: 811
–81
5.
[5]
Yael M
agu
ire,
Ravika
nth Pa
p
pu. An Optima
l
Q-Algorithm fo
r the ISO 1800
0-6C RF
ID pr
o
t
ocol.
IEEE
T
r
ansactio
n
s o
n
Auto
matio
n
Scienc
e an
d Engi
neer
in
g
. 20
09: 6(1): 19-2
0
.
[6]
HAN Zhe
n
-
w
e
i
, SONG Ke-fei. Improve
d
anti-co
llisi
on
Q-algorit
hm fo
r RFID s
y
ste
m
.
Computer
Engi
neer
in
g an
d Desi
gn
. 20
11
; 32(7): 231
4-2
318.
[7]
Bo Li, J
u
n
y
u
W
ang. Efficie
n
t
Anti-Col
lisi
o
n
Algor
ithm Uti
l
i
z
ing th
e C
aptu
r
e Effect for ISO 180
00-6
C
RFlD Protoco
l
.
IEEE Communication Letters
. 201
1; 15(3): 35
2-35
4.
[8]
Jae-R
y
o
ng C
h
a, Jae-H
y
u
n
Ki
m.
Dynamic frame
d
slotted AL
OHA algor
ith
m
s using fast tag
estimati
on
m
e
thod for RF
ID system
s
. Proceedings of
the IEEE Internat
ional
Conf
erence on Communic
a
tion
T
e
chnolog
y. 2
006: 1-4.
[9]
In
w
h
e
e
Jo
e, J
uno
Le
e. A
novel anti-collisi
o
n al
gor
ithm
w
i
th optimal fr
ame si
z
e
f
o
r RFI
D
system
. 5th
ACIS Internati
ona
l Confer
en
ce on Soft
w
a
r
e
Engi
neer
in
g
Researc
h
, Mana
geme
n
t &Appl
icatio
ns.
200
7: 424-
428.
[10] Li
Qi
ng-q
i
n
g
,
L
i
u Hon
g
-
w
u,
Z
han
g Xiao-
lin.
An
a
n
ti-col
lisi
o
n a
l
gor
ithm
ba
sed
on
un
eq
ua
l timesl
ots i
n
radi
o frequ
enc
y id
ent
ific
ation s
y
stem.
Electr
onic a
nd Infor
m
ati
on R
eport
.
2011; 3
1
(11):
262
8-26
33.
[11] W
ang Ji
n, Yi L
i
ng-z
h
i, W
ang
Gen-pi
ng. R
e
s
earch
on
an
e
nha
nce
d
anti
Coll
isio
n a
l
g
o
ri
thm for RF
ID.
Comp
uter Engi
neer
ing a
nd Sc
i
enc
e. 201
1; 33(6): 182-
18
5.
Evaluation Warning : The document was created with Spire.PDF for Python.