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.
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
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.
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
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
Based on the observations stated above, we propose a new method for determining
. In the proposed scheme, Young et al.'s estimate is used instead of Vogt's estimate [3] for more secure estimation of
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
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 (
Denote by
The optimal design problem for the tag reading process can be formulated as follows.
Given an assurance level
is minimized under the constraint that
Suppose there are
With
is given by
Based on the observations until the
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
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 O_{t} instead of O_{1} , O_{2} , ..., O_{t} .
In DFSA, the tag estimate
The sample averages after each read cycle in the
are given by
The estimate
for
Fig. 3 shows that the estimate
yields more stable results compared to
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.
Denoting by
Upon applying the constraint (1), i.e.,
where the operator ？
The optimal frame size
By putting
Fig. 5 shows the tendency for the optimal frame size to grow
L*N =λ* × N with λ* ∈[1.3,1.6].
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
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
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
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
The tag set size
In setting suitable frame sizes associated with DFSA used in RFID tag identification processes, the constraint