Advanced
On the Accuracy of RFID Tag Estimation Functions
On the Accuracy of RFID Tag Estimation Functions
Journal of information and communication convergence engineering. 2012. Mar, 10(1): 33-39
Copyright ©2012, The Korean Institute of Information and Commucation Engineering
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/3.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • Received : February 02, 2012
  • Accepted : February 27, 2012
  • Published : March 31, 2012
Download
PDF
e-PUB
PubReader
PPT
Export by style
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Young-Jae Park

Abstract
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.
Keywords
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 rated 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 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 anti-collision protocol. The design of anti-collision protocols becomes more challenging considering that the tags must be simple, cheap, and small enough [3] .
PPT Slide
Lager Image
An example of radio frequency identification systems.
Among various RFID anti-collision protocols, dynamic frame slotted Aloha (DFSA) based anti-collision 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 anti-collision 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 non-optimal frame sizes and incorrect values of Tα . Non-optimal 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 well-known 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.
PPT Slide
Lager Image
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 anti-collision 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.
Ht, St, Ct denote the number of empty slots, successful slots, and collision slots, respectively, after the tth read cycle. If we put O t = ( Ht, St, Ct ) and t = 1,2,... , then the vector ( O 1 , O 2 ,..., O t ) now represents the observation data collected until the tth 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 Lt , t = 1,2,..., the frame size used for the tth read cycle. The value of L1 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 tth read cycle, the identification delay τid is given by
PPT Slide
Lager Image
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 Nt = f ( O 1 , O 2 ,..., O t ), optimal frame size Lt+1 = g( Nt ) , and termination time Tα such that identification delay τid is minimized under the constraint that
PPT Slide
Lager Image
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 Nt .
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 = ( Ht,St,Ct ) in the tth read cycle. Denoting the lower bound by Elb , we have
PPT Slide
Lager Image
- A. Schoute's Estimate
Schoute's estimate [6] can be obtained based on the assumption that with Ct slots in collision, on average, the total number of tags existing in those slots is 2.39× Ct . Specifically, Schoute's estimate, denoted by Esc(Ht,St,Ct) , is given by
PPT Slide
Lager Image
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
PPT Slide
Lager Image
is given by
PPT Slide
Lager Image
Based on the observations until the tth cycle, { O 1 , O 2 ,..., O t }, Vogt's estimate Evd is computed as
PPT Slide
Lager Image
where for a function of N , i.e., f(N) , argmin N f(N) denotes the value of N maximizing f(N) and
PPT Slide
Lager Image
denotes the average number of slots with occupancy greater than or equal to 2. Thus it always holds that
PPT Slide
Lager Image
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 Nt is computed after the tth cycle for t = 1,2,... and the the frame size Lt+1 for the ( t +1) st read cycle is recomputed. As the tag reading process goes on, the frame size Lt 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
PPT Slide
Lager Image
and it holds that
PPT Slide
Lager Image
For the sake of brevity we denote the common frame size of all the read cycles in the mth round by Lm .
We can take sample averages after each read cycle in the mth round, i.e.,
PPT Slide
Lager Image
Kim and Park’s estimate
PPT Slide
Lager Image
for the th cycle in the mth round is given by
PPT Slide
Lager Image
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=k|X≥ 2] =P[X=k]/P[X≥ 2],k= 2,3,...
where
PPT Slide
Lager Image
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
PPT Slide
Lager Image
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
PPT Slide
Lager Image
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
PPT Slide
Lager Image
and thus for large N , we can approximately take
PPT Slide
Lager Image
Computed values of E[X | X ≥ 2]
PPT Slide
Lager Image
Computed values of E[X | X ≥ 2]
Schoute's estimate [6] can be obtained based on the assumption that with Ct slots in collision, on average, the total number of tags existing in those slots is 2.39× Ct , 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
PPT Slide
Lager Image
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
PPT Slide
Lager Image
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).
PPT Slide
Lager Image
Accuracy of Schoute's estimation function for λ = 1. MSE: mean squared error.
PPT Slide
Lager Image
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
PPT Slide
Lager Image
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.
PPT Slide
Lager Image
Comparisons of four estimation functions for λ = 0.5 in terms of mean squared error (MSE).
PPT Slide
Lager Image
Comparisons of four estimation functions for λ = 1 in terms of mean squared error (MSE).
PPT Slide
Lager Image
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.
PPT Slide
Lager Image
Comparison of three schemes in terms of identification delay.
PPT Slide
Lager Image
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.
References
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 anti-collision 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
Schoute F. C 1983 "Dynamic frame length ALOHA" IEEE Transactions on Communications 31 (4) 565 - 568    DOI : 10.1109/TCOM.1983.1095854
Cha J. R , Kim J. H 2005 "Novel anti-collision 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 anti-collision protocols" submitted for publication in IEICE-Transactions on Communications