In this paper, we compare the accuracy of most representative radio frequency identification (RFID) tag estimation functions in the context of minimizing RFID tag identification delay. Before the comparisons, we first evaluate the accuracy of Schoute's estimation function, which has been widely adopted in many RFID tag identification processes, and show that its accuracy actually depends on the number of tags to be identified and frame size
L
used for dynamic frame slotted Aloha cycles. Through computer simulations, we show how the accuracy of estimation functions is related to the actual tag read performance in terms of identification delay.
I. INTRODUCTION
Due to the ability to identify objects wirelessly without lineofsight, radio frequency identification (RFID) systems are becoming noticeably prevalent. RFID systems are rated to be particularly attractive for applications such as retail, inventory management, and supplychain management
[1
,
2]
.
RFID systems consist of a reader and multiple tags. While the reader is powerful in terms of memory and computational resources, there are many types of tags that differ in their computational capabilities. Among various tag types, passive ones are becoming more and more popular for large scale deployments due to their low cost
[2]
.
Collision due to simultaneous tag responses is one of the key issues in RFID systems. It results in wastage of bandwidth and energy, and increases identification delays. To minimize collisions, RFID readers must use an anticollision protocol. The design of anticollision protocols becomes more challenging considering that the tags must be simple, cheap, and small enough
[3]
.
An example of radio frequency identification systems.
Among various RFID anticollision protocols, dynamic frame slotted Aloha (DFSA) based anticollision protocols are most commonly used for passive RFID tag identification processes, and hence our focus is mainly directed toward DFSA. Such protocols have the ability to adjust their frame size in accordance with varying tag populations using a tag estimation function.
Consider an RFID system adopting DFSA as an anticollision protocol and suppose there exist
N
passive tags in the reader's interrogation zone (See
Figs. 1
and
2
for conceptual diagrams). Under this circumstance, the primary task of the reader is to identify all the
N
tags in the shortest time. However, the number of tags
N
is unknown from the reader's perspective and therefore it becomes a tough problem to estimate
N
accurately and determine the frame size
L
suitable for DFSA. Furthermore, in the case of identifying passive tags without muting functionality, the reader cannot decide when to stop the reading process because it cannot tell whether all the tags have been read or not. Nonetheless, based on the estimated values of
N
and
L
, the reader has to determine when to stop the reading process, namely the
termination time T_{α}
. Here,
T_{α}
denotes the minimum number of frames required to identify all
N
tags in the interrogation zone with a probability no smaller than a certain value α, also referred to as the
assurance level
.
The overall tag reading procedures with DFSA
[3

5]
can be outlined as follows: Initially, the reader starts the read process with a preset frame size. During DFSA frames, each tag chooses a slot randomly to transmit its identification. The reader then monitors the status of each slot and counts the number of slots filled with zero, one, or multiple tag responses. This observation is then translated to a tag estimate
Ñ
via a tag estimation function. Once an estimate is computed, the reader adjusts its frame size accordingly in such a way that the reading process can be terminated as soon as possible.
It is noteworthy that an inaccurate tag estimate can result in nonoptimal frame sizes and incorrect values of
T_{α}
. Nonoptimal frame sizes imply a longer identification delay while improper values of
T_{α}
could make the read process terminate either too early or too late rather than in a timely manner.
The most wellknown tag estimation functions proposed so far are Schoute's estimation function
[6]
and Vogt's estimation function
[4
,
5]
. Several authors, such as Zhen et al.
[3]
and Cha and Kim
[7]
, have adopted Schoute's estimation function for their RFID tag identification schemes. More specifically,
[3]
also proposed to set the optimal frame size according to 1.4×
Ñ
. Vogt's estimation function
[4
,
5]
is based on Chebychev's inequality. Kim and Park
[8]
also proposed a new estimation function utilizing multiple past observations via sample averages, based on Vogt's estimation function.
In this paper, we compare the accuracy of several representative estimation functions in the context of minimizing the RFID tag identification delay. Before the comparisons, we evaluate the accuracy of Schoute's estimation function
[6]
, which has been widely adopted in many cases, and show that its accuracy depends on the number of tags to be identified and frame size used for DFSA cycles. To date, this work is new. Finally, through computer simulations, we show how the accuracy of estimation functions is related to the actual tag read performance in terms of identification delay.
The remainder of this paper is organized as follows: In the next section, we describe the optimal design problem for RFID systems. In section III, we introduce most representative estimation functions. Section IV first discuss on the accuracy of Schoute's estimation function
[6]
and then compares the accuracy of the estimation functions described in Section III. section VI concludes the paper.
A sample outcome of dynamic frame slotted Aloha read cycles.
II. OPTIMAL DESIGN PROBLEM FOR RFID SYSTEMS
We consider RFID systems adopting passive tags and DFSA with no muting as the anticollision protocol
[2]
. By DFSA with no muting, it is meant that no tags are informed of the outcome of each reading cycle from the reader. Similar to basic frame slotted Aloha (BFSA), DFSA operates in multiple cycles but with the key difference that in each read cycle, the reader uses a tag estimation function to vary its frame size. A tag estimation function calculates the number of tags based on the information collected through each reading frame, consisting of the number of idle slots (
H
), number of successful slots (
S
), and number of collision slots (
C
). This information is then used by the function to estimate the number of tags, and from this estimate an optimal frame size
L
is computed for the next DFSA cycle. Here, the optimal frame size is one which promises the minimum identification delay and maximum system efficiency. Throughout this paper we assume the situation of
static
tag sets where the tags in the interrogation zone do not depart and no new tags arrive until the ongoing reading process is terminated by the reader.
H_{t}, S_{t}, C_{t}
denote the number of empty slots, successful slots, and collision slots, respectively, after the
t^{th}
read cycle. If we put
O
_{t}
= (
H_{t}, S_{t}, C_{t}
) and
t
= 1,2,... , then the vector (
O
_{1}
,
O
_{2}
,...,
O
_{t}
) now represents the observation data collected until the
t^{th}
read cycle. For instance, in the case of
Fig. 2
where
N
=
L
= 4, we have
O
_{t}
= (1,2,1).
With the DFSA protocol in operation, the frame size
L
is updated every read cycle. We denote by
L_{t}
,
t
= 1,2,..., the frame size used for the
t^{th}
read cycle. The value of
L_{1}
is set to an appropriate value as a reading process starts (e.g., 16
[4]
). Also, note that if a tag read process is terminated upon completion of the
t^{th}
read cycle, the identification delay
τ_{id}
is given by
The optimal design problem for the tag reading process can be established as follows: Given an assurance level α, for
t
= 1,2,..., devise tag estimate
N_{t} = f
(
O
_{1}
,
O
_{2}
,...,
O
_{t}
), optimal frame size
L_{t+1} = g( N_{t} )
, and termination time
T_{α}
such that identification delay
τ_{id}
is minimized under the constraint that
Suppose there are
N
tags in the interrogation zone (actually the number of tags
N
is unknown to the reader). In the optimal design problem described above, we observe that playing the key roles are the tag estimation function
f
(·) and the function
g
(·) for computing the optimal frame size from tag estimate
N_{t}
.
III. TAG ESTIMATION FUNCTIONS
In this section, we first survey some past representative works on devising proper tag estimation functions and optimal frame sizes and discuss some problems associated with these studies. As a preliminary step, we are interested in the lower bound of the number of tags in the interrogation zone upon observing
O
_{t}
= (
H_{t},S_{t},C_{t}
) in the
t^{th}
read cycle. Denoting the lower bound by
E_{lb}
, we have
 A. Schoute's Estimate
Schoute's estimate
[6]
can be obtained based on the assumption that with
C_{t}
slots in collision, on average, the total number of tags existing in those slots is 2.39×
C_{t}
. Specifically, Schoute's estimate, denoted by
E_{sc}(H_{t},S_{t},C_{t})
, is given by
Schoute's estimate has been adopted in many schemes, including
[3
,
7]
.
 B. Vogt's Estimate[4,5]
With
N
tags in the interrogation zone and frame size
L
, the average number of slots with occupancy
r
(
r
= 0,1,...
N
), denoted by
is given by
Based on the observations until the
t^{th}
cycle, {
O
_{1}
,
O
_{2}
,...,
O
_{t}
}, Vogt's estimate
E_{vd}
is computed as
where for a function of
N
, i.e.,
f(N)
, argmin
_{N}
f(N)
denotes the value of
N
maximizing
f(N)
and
denotes the average number of slots with occupancy greater than or equal to 2. Thus it always holds that
It is noteworthy that Vogt's estimate utilizes only the last observation
O
_{t}
.
 B. Kim and Park's Estimate[8]
In DFSA, the tag estimate
N_{t}
is computed after the
t^{th}
cycle for
t
= 1,2,... and the the frame size
L_{t+1}
for the (
t
+1)
^{st}
read cycle is recomputed. As the tag reading process goes on, the frame size
L_{t}
may or may not change. In this respect, we can decompose the sequence of observations into multiple groups. Each group consists of consecutive observations with the same frame size. We term a group of consecutive read cycles with the same frame size as a
round
. In this context, we have
and it holds that
For the sake of brevity we denote the common frame size of all the read cycles in the
m^{th}
round by
L_{m}
.
We can take sample averages after each read cycle in the
m^{th}
round, i.e.,
Kim and Park’s estimate
for the
ℓ^{th}
cycle in the
m^{th}
round is given by
IV. ACCURACY COMPARISONS
With
N
tags in the interrogation zone and frame size
L
, consider the problem of estimating the actual number of tags in a slot after a read cycle, provided the slot is in collision. Let a random variable
X
stand for the number of tags in the slot. With the observation that the slot is in collision, the conditional probability that the slot actually contains
k
tags, denoted by
P
[
X
=
k

X
≥ 2], is given by

P[X=kX≥ 2] =P[X=k]/P[X≥ 2],k= 2,3,...
where
Therefore, the average number of tags in the slot on the condition that the slot is in collision, denoted by
E
[
X

X
≥ 2], can be computed as
If we always adjust the frame size
L
in proportion to
N
, then we can set
L = λN
for some positive real number
λ
(
λ
takes values in
[1
,
2]
) and (5) can be rewritten as
Table 1
shows the values of
E
[
X

X
≥ 2] computed for various values of
λ
and
N
. When the number of tags
N
grows unboundedly large, we get
and thus for large
N
, we can approximately take
Computed values of E[X  X ≥ 2]
Computed values of E[X  X ≥ 2]
Schoute's estimate
[6]
can be obtained based on the assumption that with
C_{t}
slots in collision, on average, the total number of tags existing in those slots is 2.39×
C_{t}
, where the value 2.39 is determined by putting
λ
=1 in (7), i.e., assuming that the frame size
L
is always set equal to
N
. However,
Table 1
explicitly indicates that Schoute's estimate should become incorrect when
L ≠ N
and/or
N
is not very large. Through computer simulations, we evaluated the impact of
N
and
L
on the correctness of Schoute's estimate (2).
Figs. 3
and
4
show the results where the optimal estimate uses
where
μ_{N,L}
is determined according to Eq. (6) and denoting by
Ñ
, the estimated value of
N
, the normalized mean squared error (MSE) is defined by
For each tag set size
N
, we carried out 100 DFSA tag reading frames. The results in
Figs. 3
and
4
are obtained for
λ
=1 and
λ
=1.4 i.e.,
L
=
N
and
L
= 1.4
N
, respectively. Note that the difference between Schoute's estimate
[6]
and the optimal estimate is negligible for λ=1 but this is not the case for λ=1.4, where the gap never diminishes irrespective of
N
. This result implies that for the most commoly used setting of
L
, i.e.,
L
= 1.4
N
, Schoute's estimation function will not work properly and should be corrected according to Eq. (6).
Accuracy of Schoute's estimation function for λ = 1. MSE: mean squared error.
Accuracy of Schoute's estimation function for λ = 1.4 . MSE: mean squared error.
On the other hand,
Figs. 5

7
compare the performance of the four estimation functions described in section III, namely the lower bound, those of Schoute
[6]
, Vogt
[4
,
5]
, and Kim and Park
[8]
, in terms of the MSE, which is defined by
Figs. 5

7
are the comparison results for
λ
= 0.5,
λ
= 1, and
λ
= 1.5 , respectively. Throughout in the figures, the ‘proposed’ values represent results from the estimation function of Kim and Park. As was done before, we executed 100 DFSA tag reading frames for each tag set size
N
. For the case of Kim and Park
[8]
, we used 10 samples and took sample averages (i.e., ℓ=10 in Eq. (4)). We can observe that the estimation error increases as
L
becomes smaller than
N
, i.e.,
λ
gets smaller. With respect to the estimation accuracy, the four estimation functions can be arranged in order from smaller to larger MSE from Kim and Park
[8]
, to Vogt
[4
,
5]
, Shoute
[6]
, and finally the lower bound. However, the order is reversed for
λ
= 0.5 in the case of Vogt’s and Shoute’s estimation functions, showing the tendency for Vogt’s estimation function not to work well for
λ
< 1. In all the cases, the estimation function of Kim and Park yields the smallest MSE.
Comparisons of four estimation functions for λ = 0.5 in terms of mean squared error (MSE).
Comparisons of four estimation functions for λ = 1 in terms of mean squared error (MSE).
Comparisons of four estimation functions for λ = 1.5 in terms of mean squared error (MSE).
In order to further evaluate how the accuracy of estimation functions is related to the actual tag read performance in terms of identification delay, we applied those to actual passive tag identification processes and performed computer simulations (the lower bound has been excluded on purpose). The assurance level aspired to, α , was set to 0.99 , that is, the requirement was that on average, the number of cases failing to identify all tags should not exceed 1% of all identification processes. The tag set size
N
for the simulation ranges from 10 to 100 and for each tag set size we carried out 1,000 runs of the reading procedure. In evaluating Vogt's estimation function, we used the procedure proposed in
[8]
due to the instability problem.
Fig. 8
shows that the estimation functions are arranged in order from in order from better to worst performance from those of Kim and Park
[8]
to Zhen
[3]
and Vogt
[4
,
5]
while
Fig. 9
shows the assurance level is met in all cases.
Comparison of three schemes in terms of identification delay.
Comparison of three schemes in terms of accuracy.
V. CONCLUSIONS
In this paper, we compared the accuracy of several representative estimation functions in the context of minimizing the RFID tag identification delay. Before the comparisons, we first evaluated the accuracy of Schoute's estimation function
[6]
which has been widely adopted in many cases and showed that its accuracy indeed depends on the number of tags to be identified and frame size used for DFSA cycles. Through computer simulations, we also showed how the accuracy of estimation functions is related to the actual tag read performance in terms of identification delay.
Klair D. K
,
Chin K. W
,
Raad R
2007
"On the accuracy of RFID tag estimation functions"
6th IEEE International Symposium on Communications and Information Technologies
Sydney
1401 
1406
Klair D. K
,
Chin K. W
,
Raad R
2010
"A survey and tutorial of RFID anticollision protocols"
IEEE Communications Surveys & Tutorials
12
(3)
400 
421
DOI : 10.1109/SURV.2010.031810.00037
Zhen B
,
Kobayashi M
,
Shimizui M
2005
"Framed Aloha for multiple RFID objects identification"
IEICE Transactions on Communications
88B
(3)
991 
999
Vogt H
2002
"Efficient object identification with passive RFID tags"
Proceedings of the First International Conference on Pervasive Computing
Seattle
98 
113
Vogt H
2002
"Multiple object identification with passive RFID tags"
IEEE International Conference on Systems, Man and Cybernetics
3
Cha J. R
,
Kim J. H
2005
"Novel anticollision algorithms for fast object identification in RFID system"
Proceedings of the 11th International Conference on Parallel and Distributed Systems
Fukuoka
63 
67
Kim Y. B
,
Park Y. J
2012
"On the performance enhancement of RFID anticollision protocols"
submitted for publication in IEICETransactions on Communications