Accelerating RFID Tag Identification Processes with Frame Size Constraint Relaxation

Journal of information and communication convergence engineering.
2012.
Sep,
10(3):
242-247

This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/li-censes/bync/ 3.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.

- Received : May 11, 2012
- Accepted : June 07, 2012
- Published : September 30, 2012

Download

PDF

e-PUB

PubReader

PPT

Export by style

Article

Metrics

Cited by

TagCloud

In the determination of suitable frame sizes associated with dynamic framed slotted Aloha used in radio frequency identification tag identification processes, the widely imposed constraint
L
= 2
^{Q}
often yields inappropriate values deviating far from the optimal values, while a straightforward use of the estimated optimal frame sizes causes frequent restarts of read procedures, both resulting in long identification delays. Taking a trade-off, in this paper, we propose a new method for determining effective frame sizes where the effective frame size changes in a multiple of a predetermined step size, namely Δ . Through computer simulations, we show that the proposed scheme works fairly well in terms of identification delay.
N
tags in its interrogation zone. Initially, the reader starts the collision resolution process with an arbitrary frame size. Tags then choose a slot randomly to transmit their identification. The reader 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.
An example of radio frequency identification systems.
In this vein, an inaccurate tag estimate can result in non- optimal frame sizes, which can again increase identification delay and energy wastage. Another factor that should be considered carefully in designing the reading process is to determine when to stop the reading process, namely the termination time
T_{α}
. Here,
T_{α}
denotes the minimum number of read cycles required to identify all
N
tags in the interrogation zone with probability
α
, also referred to as the
assurance level
.
H. Vogt
[3
,
4]
proposed a tag estimation function and a framework for choosing optimal frame sizes for computed tag estimates, including a procedure for adaptively reading a static set of tags. It is generally accepted that Vogt's tag estimation function based on Chebyshev's inequality is the most accurate among several estimation functions
[1]
. However, as is performed in
[5]
, the constraint that the frame size should be of the form 2
^{Q}
for some integer
Q
is imposed. As a result, the actual frame sizes used in identification processes often deviate far from the optimal (or sub-optimal) frame sizes, thereby significantly prolonging the identification delay. On the other hand, a direct use of optimal frame sizes as estimated can lead to frequent restarts of identification processes, also resulting in longer identification delays.
Based on the observations stated above, we propose a new method for determining
effective
frame sizes which change linearly proportional to a fixed step size Δ according to tag estimaties
. In the proposed scheme, Young et al.'s estimate is used instead of Vogt's estimate
[3]
for more secure estimation of
N
and the simplified parameter estimation method proposed in
[6]
for the initial estimation of optimal frame sizes and termination time. Through computer simulations, we show that the proposed scheme works fairly well in terms of identification delay.
The remainder of this paper is organized as follows. First, as a preliminary step for presenting our scheme, we give a formulation of passive tag reading processes as an optimal design problem, and then introduce Vogt's
[3]
and Young et al.'s schemes in the next section. In Section III, we summarize the simplified parameter estimation method proposed by Young et al. for computing optimal frame sizes and termination time and propose a new method for determining
effective
frame sizes. This is followed by a review of simulation results and discussion in Section IV. Section V concludes the paper.
A sample outcome of dynamic frame slotted Aloha read cycles.
H
), number of successful slots (
S
), and number of collision slots (
C
). This information is then used by the funsction to obtain a tag estimate, and hence the optimal frame size
L
for a given cycle. Here, the optimal frame size is one which promises the minimum identification delay and maximum system efficiency including the lowest battery power consumption. 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}
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. With the DFSA protocol in operation, the frame size
L
is updated every read cycle. We denote by
L_{t}
, where
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 the reading process starts (e.g., 16
[3]
).
A sample trajectory of tag estimates when N = 48.
The optimal design problem for the tag reading process can be formulated as follows.
Given an assurance level
α
, for
t
= 1,2,..., devise the 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 the identification delay
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) and we continue the read cycle with the same frame size
L
. The question now is when to stop the reading process such that the identification delay is minimized and with confidence level
α
all tags are read.
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
A Comparison of Vogt’s and the proposed methods forcomputing optimal frame sizes.
Based on the observations until the
t^{th}
cycle, {
O
_{1}
,
O
_{2}
,...,
O
_{t}
} , Vogt's estimate
E_{vd}
is computed as,
where
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}
. Upon obtaining
N_{t} = E_{vd}
(
O
_{t}
) , the optimal frame size for the (
t
+1)
^{st}
cycle
L
_{t+1}
is determined appropriately according to a table proposed in
[3]
.
O
_{t}
instead of
O
_{1}
,
O
_{2}
, ...,
O
_{t}
.
In DFSA, the tag estimate
N_{t}
is computed after the
t^{th}
cycle for
t
= 1,2,... and the frame size
L_{t+1}
for the (
t
+1)
^{st}
read cycle is adjusted appropriately. As the tag reading process goes on, the frame size
L_{t}
may or may not change. We can decompose the sequence of observations into multiple groups. Each group consists of consecutive observations with the same frame size. Each group of consecutive read cycles with same frame size is termed a
round
. In this vein, a read process can be organized as
The sample averages after each read cycle in the
m^{th}
round
are given by
The estimate
for
ℓ^{th}
cycle in
m^{th}
round of Young et al. is given by
Fig. 3
shows that the estimate
yields more stable results compared to
E_{vd}
.
The optimal frame sizes vs. number of tags.
E_{t}
the event that all tags are identified until the end of the
t^{th}
read cycle, under an independence assumption among tags we have
Upon applying the constraint (1), i.e.,
P
[
E_{t}
] ≥α , the termination time
T_{α}
can be computed as
where the operator ⎡
x
⎤ stands for the smallest integer greater than or equal to
x
. The exact value of
T_{α}
can be computed following the Markov chain approach described in
[3]
. However, the computation is extremely burdensome especially for large values of
N
. Though the independence assumption is not generally true,
Fig. 4
shows that the values computed in both ways coincide exactly, except only one case. Throughout we use the formula (2) for the estimation of
T_{α}
.
The optimal frame size
L^{*}_{N}
for a given
N
, minimizing the identification delay τ
_{id}
, is given by
By putting
L =λN
as was done before, τ
_{id}
can be expressed as a function of λ , i.e.,
Fig. 5
shows the tendency for the optimal frame size to grow
linearly
in
N
with the slope in the interval [1.3,1.6] . Thus, we can roughly compute the optimal frame size according to
L
needs to be updated. As briefly discussed in Section I, if frame sizes are updated frequently, the identification delay increases while sticking to the constraint
L
= 2
^{Q}
yields inaccurate frame sizes much different from the optimal frame sizes. In this respect, we propose to set the actual frame sizes used in the reading process, namely the effective frame sizes linearly proportional to a fixed step size Δ , i.e.,
with
The value of Δ can be set to any positive integer, e.g., 4,8,16,32,.... In order to prevent frequent updates of the effective frame sizes, we impose the following update rule. Denoting by
, the new effective frame size,
On the other hand, Vogt's procedure for reading tags
[3]
often generates overestimated values of
N
and
L
, which lead to unnecessarily large values of
T_{α}
, thereby resulting in greater identification delays. In order to circumvent this problem, as shown in
Fig. 6
, considering the cases of the initial value of
L
being too small compared to
N
, the initial estimation for the number of tags is performed twice. In the first estimation, the value of
L
is set to 16 while in the second estimation, the value of
L
obtained in the first estimation is used for reliable tag estimates.
The tag read procedure used in the proposed scheme.
and the read procedure described in
Fig. 6
. Via the estimation of optimal frame sizes according to (3), effective frame sizes were determined by (5). In (5), the value of Δ was set to 16, which appears to be most appropriate in our simulation. The termination time
T_{α}
was computed from the effective frame size by the formula (2).
Performance of two schemes in terms of identification delay.
The identification accuracies of the two schemes.
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.
Figs. 7
and
8
show that the proposed scheme works fairly well for the entire range of
N
with the desired accuracy level (i.e., 0.99) being satisfied all the time. For example, the identification delay for
N
= 80 in the proposed scheme is shorter than that in Vogt's scheme by about 1,200 slots. We can also observe that the proposed scheme is more useful for large values of
N
. On the other hand,
Fig. 8
shows that the actual accuracy of Vogt's scheme turns out to be unnecessarily far above the desired accuracy level.
L
= 2
^{Q}
yields inappropriate values deviating far from the optimal values while a straightforward use of the estimated optimal frame sizes causes frequent restarts of read procedures, both resulting in long identification delays. Taking a trade-off, in this paper, we proposed a new method for determining effective frame sizes where the effective frame sizes change in a multiple of a predetermined step size, namely Δ . Through computer simulations we show that the proposed scheme works fairly well in terms of identification delay.

I. INTRODUCTION

Due to the ability to identify objects wirelessly without line-of-sight, radio frequency identification (RFID) systems are becoming noticeably prevalent. RFID systems are thought to be particularly attractive for applications such as retail, inventory management, and supply-chain 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 with varying computational capabilities. Among the 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 anti-collision protocols becomes more challenging considering that the tags must be simple, cheap, and small enough.
The anti-collision algorithm of RFID can be either deterministic or statistical. In this paper, we analyze anticollision protocols based on framed slotted Aloha (FSA). Such protocols have the ability to adjust their frame size in accordance with varying tag populations using a tag estimation function.
Consider a reader with
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

II. BACKGROUND

We consider FRID systems adopting passive tags and dynamic frame slotted Aloha (DFSA) with no muting as the anti-collision protocol. DFSA can be defined as FSA protocols with variable frame sizes
[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 empty solts (
- A. Problem Formulation

Denote by
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

- B. Vogt's Estimate[3]

With
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

- C. The Estimate of Young et al.

A problem with Vogt's scheme is that the tag estimate does not converge to the actual value and continuously fluctuates as the reading process proceeds, due to the fact that Vogt's estimate utilizes only the most recent observation
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

III. PROPOSED SCHEME

In this section, we first summarize the simple parameter estimation method proposed in
[6]
and then present the proposed scheme for determining effective frame sizes.
- A. Simple Parameter Estimation Approach[6]

Denoting by
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

- L*N=λ*× N with λ*∈[1.3,1.6].

- B. Determination of Effective Frame Sizes

Fig. 6
shows the tag identification procedure used in the proposed scheme. In the main procedure, we see that a new reading round starts whenever the value of frame size
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

IV. SIMULATION RESULTS AND DISCUSSION

We performed computer simulations to evaluate the proposed scheme. The desired assurance level α was set to 0.99, meaning the requirement that on the average the number of cases failing to identify all tags should not exceed 1% of all identification processes. In the simulations, we used the tagestimate
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

V. CONCLUSIONS

In setting suitable frame sizes associated with DFSA used in RFID tag identification processes, the constraint
Klair D. K
,
Chin K. W
,
Raad R
2007
“ On the accuracy of RFID tag estimation functions,”
Proceedings of International Symposium on Communications and Information Technologies
Sidney, Australia
1401 -
1406

Klair D. K
,
Chin K. W
,
Raad R
2010
“ A survey and tutorial of RFID anti-collision protocols,”
IEEE Communications Surveys and Tutorials
12
(3)
400 -
421

Vogt H
2002
“ Efficient object identification with passive RFID tags,”
Proceedings of the 1st International Conference on Pervasive Computing
Zurich, Switzerland
98 -
113

Vogt H
2002
“ Multiple object identification with passive RFID tags,”
Proceedings of IEEE International Conference on Systems, Man and Cybernetics
Hammanet, Tunisia

Class 1 generation 2 UHF air interface protocol standard version 1.0.9 (Gen 2) [Internet]
EPCglobal
Available:http://www.epcglobalus.org/Standards/EPCglobalStandards/Class1Generation2UHFAirInterfaceProtocol/tabid/322/Default.aspx

Park Y. J
,
Kim Y. B
2012
“ On facilitating RFID tag read processes via a simple parameter estimation,”
Journal of the Korean Institute of Communication Sciences
37
(1)
38 -
44

Citing 'Accelerating RFID Tag Identification Processes with Frame Size Constraint Relaxation
'

@article{ E1ICAW_2012_v10n3_242}
,title={Accelerating RFID Tag Identification Processes with Frame Size Constraint Relaxation}
,volume={3}
, url={http://dx.doi.org/10.6109/jicce.2012.10.3.242}, DOI={10.6109/jicce.2012.10.3.242}
, number= {3}
, journal={Journal of information and communication convergence engineering}
, publisher={The Korean Institute of Information and Commucation Engineering}
, author={Park, Young-Jae
and
Kim, Young Beom}
, year={2012}
, month={Sep}