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].

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 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 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×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.

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.

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₁, O₂,..., 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₁ 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₁, O₂,..., 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.

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

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].

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₁, O₂,..., 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.

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

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

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

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 N , 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.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 of N . This result implies that for the most commoly used setting of L, 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. 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.

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.

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.