8
Tag Identication Protocols in RFID Systems
silent until the end of the protocol; otherwise, in
case of collision or idle slot (i.e. slot not selected
by any tag) no ack is sent, so all non-acknowledged
tags know that the protocol is not ended yet. Read
cycles are repeated for unrecognized (namely,
whose transmission results in a collision) tags,
until all tags have been identified. So, in the last
read cycle there must be no collision.
Dynamic Framed Slotted
Aloha (DFSA)
The Dynamic Framed Slotted Aloha (DFSA) (Vogt
2002) protocol changes the frame size dynami-
cally. As BFSA, DFSA operates in multiple rounds,
with the difference that at the end of each round
the reader estimates the number of participating
tags, according to the Chebyshev’s estimation
function (see below) for deciding a proper size
of the next transmission frame.
The constraint of this protocol is that the frame
size cannot be increased indefinitely as the number
of tags increases, but it has an upper bound. This
implies a very high number of collisions when the
number of tags exceeds the maximum admitted
frame size. An Advanced Framed Slotted Aloha
(AFSA) protocol, analyzed in (Lee et al. 2005),
overcomes such a problem by dividing the unread
tags into a number of groups, and interrogating
each group separately. The performance of DFSA
protocol is improved by the Variant Enhanced
Dynamic Framed Slotted Aloha (EDFSA) protocol
(Peng et al. 2007), where a dynamic approach for
group dividing is adopted.
The frame size affects the performance of
Aloha based algorithms. A small frame size results
in many collisions, and so increases the required
total number of slots when the number of tags is
high. In contrast, a large frame size may result in
more idle time slots, when the number of tags is
small. Different methods estimating the number
of unread tags, so allowing the reader to choose
an optimal frame size for the next read cycle, are
presented in (Cha & Kim 2005; 2006).
Tree Slotted Aloha (TSA)
In (Bonuccelli et al. 2006), the Tree Slotted Aloha
protocol is proposed. It aims at reducing tag
transmission collisions by querying only those
tags colliding in the same slot of a previous frame
of transmissions. At the end of each frame, for
each slot in which a collision occurred, the reader
starts a new small frame, reserved to those tags
which collided in the same time slot. In this way,
a transmission frame can be viewed as a node in
a tree, where the root is the initial frame; leaves
represent frames where no collision occurred. The
behaviour of TSA protocol is illustrated in Figure
5. To establish the size of “child” frames, TSA
uses Chebyshev’s estimation function in a way
similar to (Vogt 2002). More precisely, consider
a level l in the tree, let n
i
be the estimated number
of transmitting tags in frame i. Then, if c
1
i
is the
number of identified tags and c
k
i
is the number of
collision slots in frame i, the expected number of
transmitting tags in each of the c
k
i
child frames at
level l + 1 is given by
n c
c
i i
k
i
−
1
Dynamic Tree Slotted Aloha (DTSA)
When the number of tags to be identified is very
high (of the order of thousands) and the initial
frame size is set too small with respect to the actual
number of tags, the estimation function used by
TSA may not define proper frame sizes. This is
because the n which minimizes the Chebyshev’s
inequality is searched in the range [c
1
+ 2c
k
, 2(c
1
+ 2c
k
)], and when c
1
= 0 the upper limit 4c
k
may
be insufficient to capture the real number of trans-
mitting tags. This problem has been approached
in (Maselli et al. 2008). The improvement to TSA
is in considering not only the outcomes of frames
at a given level, but exploiting also the knowledge