On the Accuracy of RFID Tag Estimation Functions
 Author: Park YoungJae, Kim Young Beom
 Organization: Park YoungJae; Kim Young Beom
 Publish: Journal of information and communication convergence engineering Volume 10, Issue1, p33~39, 31 March 2012

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.

KEYWORD
Anticollision protocol , Dynamic frame slotted Aloha , Passive tags , Radio frequency identification

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].
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 theN tags in the shortest time. However, the number of tagsN is unknown from the reader's perspective and therefore it becomes a tough problem to estimateN accurately and determine the frame sizeL 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 ofN andL , the reader has to determine when to stop the reading process, namely thetermination time T_{α} . Here,T_{α} denotes the minimum number of frames required to identify allN tags in the interrogation zone with a probability no smaller than a certain value α, also referred to as theassurance level .The overall tag reading procedures with DFSA [35] 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
N 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 ofT_{α} 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×
N . 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.
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 sizeL 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 ofstatic 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 thet^{th} read cycle. If we putO _{t} = (H_{t}, S_{t}, C_{t} ) andt = 1,2,... , then the vector (O _{1},O _{2},...,O _{t}) now represents the observation data collected until thet^{th} read cycle. For instance, in the case of Fig. 2 whereN =L = 4, we haveO _{t} = (1,2,1).With the DFSA protocol in operation, the frame size
L is updated every read cycle. We denote byL_{t} ,t = 1,2,..., the frame size used for thet^{th} read cycle. The value ofL_{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 thet^{th} read cycle, the identification delayτ_{id} is given byThe optimal design problem for the tag reading process can be established as follows: Given an assurance level α, for
t = 1,2,..., devise tag estimateN_{t} = f (O _{1},O _{2},...,O _{t}), optimal frame sizeL_{t+1} = g( N_{t} ) , and termination timeT_{α} such that identification delayτ_{id} is minimized under the constraint thatSuppose there are
N tags in the interrogation zone (actually the number of tagsN is unknown to the reader). In the optimal design problem described above, we observe that playing the key roles are the tag estimation functionf (·) and the functiong (·) for computing the optimal frame size from tag estimateN_{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 thet^{th} read cycle. Denoting the lower bound byE_{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 byE_{sc}(H_{t},S_{t},C_{t}) , is given bySchoute'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 sizeL , the average number of slots with occupancyr (r = 0,1,...N ), denoted byis given by
Based on the observations until the
t^{th} cycle, {O _{1},O _{2},...,O _{t}}, Vogt's estimateE_{vd} is computed aswhere for a function of
N , i.e.,f(N) , argmin_{N} f(N) denotes the value ofN maximizingf(N) anddenotes 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 thet^{th} cycle fort = 1,2,... and the the frame sizeL_{t+1} for the (t +1)^{st} read cycle is recomputed. As the tag reading process goes on, the frame sizeL_{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 around . In this context, we haveand it holds that
For the sake of brevity we denote the common frame size of all the read cycles in the
m^{th} round byL_{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 them^{th} round is given byIV. ACCURACY COMPARISONS
With
N tags in the interrogation zone and frame sizeL , 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 variableX 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 containsk tags, denoted byP [X =k X ≥ 2], is given byP[X = k  X ≥ 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 asIf we always adjust the frame size
L in proportion toN , then we can setL = λN for some positive real numberλ (λ takes values in [1,2] ) and (5) can be rewritten asTable 1 shows the values of
E [X X ≥ 2] computed for various values ofλ andN . When the number of tagsN grows unboundedly large, we getand thus for large
N , we can approximately takeSchoute'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 sizeL is always set equal toN . However, Table 1 explicitly indicates that Schoute's estimate should become incorrect whenL ≠ N and/orN is not very large. Through computer simulations, we evaluated the impact ofN andL on the correctness of Schoute's estimate (2). Figs. 3 and 4 show the results where the optimal estimate useswhere
μ_{N,L} is determined according to Eq. (6) and denoting byN , the estimated value ofN , the normalized mean squared error (MSE) is defined byFor 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 andL = 1.4N , 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 ofN . This result implies that for the most commoly used setting ofL , i.e.,L = 1.4N , Schoute's estimation function will not work properly and should be corrected according to Eq. (6).On the other hand, Figs. 57 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. 57 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 sizeN . 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 asL becomes smaller thanN , 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.[Fig. 5.] Comparisons of four estimation functions for λ = 0.5 in terms of mean squared error (MSE).
[Fig. 7.] 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.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.

[Fig. 1.] An example of radio frequency identification systems.

[Fig. 2.] A sample outcome of dynamic frame slotted Aloha read cycles.

[Table 1.] Computed values of E[X  X ≥ 2]

[Fig. 3.] Accuracy of Schoute's estimation function for λ = 1. MSE: mean squared error.

[Fig. 4.] Accuracy of Schoute's estimation function for λ = 1.4 . MSE: mean squared error.

[Fig. 5.] Comparisons of four estimation functions for λ = 0.5 in terms of mean squared error (MSE).

[Fig. 6.] Comparisons of four estimation functions for λ = 1 in terms of mean squared error (MSE).

[Fig. 7.] Comparisons of four estimation functions for λ = 1.5 in terms of mean squared error (MSE).

[Fig. 8.] Comparison of three schemes in terms of identification delay.

[Fig. 9.] Comparison of three schemes in terms of accuracy.