ABSTRACT

In this paper, we develop a novel mathematical model to estimate the probability distribution function of the number of tags discovered after a certain number of interrogation rounds. In addition, the pdfs of the number of rounds needed to discover all the tags are also calculated. The estimation of such pdfs will be helpful in estimating the number of interrogation rounds and the optimal parameter configuration of the RFID system which in turn will be helpful in estimating the time needed to discover all tags. Our results show that the proposed model accurately predicts the tags detection probability. We then use the proposed model to optimally configure the reader parameters (i.e. the frame size and the number of interrogation rounds).

1. Introduction

In RFID systems with one reader and many tags, tag-totag collisions occur when multiple tags transmit their signals simultaneously to the reader. This problem is called tag collision and many tag anti-collision protocols have been proposed in the literature [1]. Many efficient anti-collision protocol adopted by different body standards [2] and commercial products are based on the classical Framed-Slotted Aloha. In framed slotted aloha based anti-collision protocols, the reader begins each interrogation round by informing all tags about the current frame size in terms of time slots. Each tag then selects a random time slot and sends its identifier in that time slot. The probability of tag collision depends on the frame size and the number of tags. Since not all tags can be identified in the one round, the reader repeats the interrogation rounds until all tags are identified.

Many experimental [3] and mathematical performance analysis [4-6] of framed-slotted Aloha based anti-collision protocols have been published in the literature to measure and estimate the performance of RFID systems in terms of discovery delay and throughput. However in those previous models, an estimation of the number of rounds needed to discover all tags was not proposed yet. In this paper, we develop a novel mathematical model to estimate the probability distribution function of the number of tags discovered after a certain number of interrogation rounds. In addition, the pdfs of the number of rounds needed to discover all the tags are also calculated. The estimation of such pdfs will be helpful in estimating the number of interrogation rounds and the optimal parameter configuration of the RFID system which in turn will be helpful in estimating the time needed to discover all tags. The paper is organized as follows. Section 3 presents the system model used to develop the proposed mathematical model. The development of the two stages mathematical model is presented in Section 4. Parameter selection and optimization are presented in Section 5. Finally, the conclusion is presented in Section 6.

2. Related Work

Framed Slotted Aloha protocols has been carefully and extensively analyzed and modeled either as a communication system or as an RFID anti-collision protocol. The most classical paper that provides an exact analysis of the framed slotted aloha communication system was written by Wieselthier and others [4]. The authors provided a combinatorial analysis of different variations of the protocol including capture effects and dynamic frame slots allocation. By calculating all states of all users, the techniques provided in the paper could be used to calculate the throughput and other performance indicators.

Haralad Vogt [7] introduced a mathematical modeling for the Slotted Aloha protocol that is being used in RFID readers as an anti-collision protocol. Starting form a simple occupancy problem, Vogt has calculated the probability distribution function of the random variable that is equal to the number of slots in a frame that is being filled with exactly r tags. Kim et al. [8] have started with conditional probabilities and reached to the same recursive closed formula introduced by Vogt. The mathematical model introduced in [9] was based on simple probability calculations with approximated performance measurements.

Delgado et al. [10] utilized Vogt model [7] and modified it to reflect the case of tag muting in RFID system. The algorithm is modeled by a Markov Chain of size N + 1 where N is the number of tags. The transition probabilities of the Markov Chain are then calculated using the model introduced by Vogt.

3. System Model

We assume an RFID network with one reader and n tags. Note that in real applications, the number of tags is usually unknown. For this, we assume the availability of a population estimation algorithm such as [11-13]. The reader selects the frame size s in terms of time slots and announces it to the tags. Each tag then, selects a random time slot to send its identification code. The reader identifies the tags who selected unique time slots. Hence when at least two tags select the same time slot, a tag collision occurs. As a result, the involved tags will not be identified during that specific interrogation round. The reader continues the interrogation process for r rounds. In this work, once a tag is identified, it will be muted (i.e. the tag will not respond to the reader request) in the subsequent interrogation rounds. Also, we assume that frames have fixed sizes and no channel capture effect is assumed. We will relax these assumptions in our future work.

The allocation of tags to slots within a time frame is an example of a mathematical class of problems called the Occupancy Problems [14-17]. This class of problems studies the random allocation of a number of balls to a number of bins with different settings and objectives. Some examples of such problems include, estimating the number of empty bins, estimating the number of bins containing only one ball and estimating the number of bins containing more than one ball.

Reformulating the occupancy problem in terms of tags and slots, we are interested in finding the number of slots that contains one and only one tag. This means that the tags included in those slots were successfully identified by the RFID reader. Figure 1 shows an example of an interrogation process. In the first round, 8 tags were competing for 8 time slots. After selecting a random slot, three tags selected distinct time slots. The reader was able to recognize them. The other five tags selected one of two time slots and thus their messages collided. The reader needed 4 rounds to discover all the tags in this particular example.

4. Mathematical

The proposed mathematical model consists of two parts. First in 4.1, we calculate the probability mass function of the number of tags that can be identified in one round. Then in 4.3, we calculate the probability density function of the number of identified tags after r rounds. Additionally, the probability density function of the number of rounds needed to discover n tags can also be estimated. The notations used throughout the paper are summarized in Table 1.

4.1. Analytical Model for Slot Selection Mechanism

To identify a tag during an arbitrary slot time “a” out of s slots in a round, exactly one tag out of n tags should select that slot and transmit its identification code. Let us define slot “a” as a Discovery Slot. Then, the probability

p(n, s) that an arbitrary slot is a discovery slot (i.e. exactly one tag transmits during that slot) can be given as

, (1)

where, is the probability that a tag selects a random slot out of s slots. Let us also define m(n, s) as the maximum number of tags that can be identified during a single interrogation round given that there are n tags competing for s slots. Formally, m(n, s) can be defined as

(2)

Defining m(n, s) is very important in case an exact analysis of the slotted Aloha operation is needed. The first line explains the case where only one time slot is used in the time frame. In that case no tag will be identified because all of them will collide in that time slot. The second line explains the case where the number of tags is more than the number of slots. In this case, only (s − 1) tags could be identified while the remaining tags will collide in the remaining time slot. The last line represents the case where the number of tags is less than the number of time slots available in the frame. In that case, all tags could be identified. Figure 2 illustrates the different cases.

Now, we can define the probability q₁(n, s) of identifying exactly 1 tag out of n tags during an interrogation round that consists of s slots is given as

(3)

where l(n − 1, s − 1) is the probability that none of the remaining (s − 1) slots is a discovery slot. Alternatively,

l(n − 1, s − 1) can be defined also as the probability that none of the remaining (n −1) tags is identified during the remaining (s − 1) slots. The term p(n, s) is the probability of having an arbitrary discovery slot as defined in Equation (1) and is the number of ways this arbitrary slot can be selected. The probability q_i(n, s) of identifying i tags (1 ≤ i ≤ m (n, s)) in one interrogation round can be calculated as

(4)

which, can be used to calculate the probability mass function of the number of tags that can be identified in one interrogation round.

Finally, the probability l(n − i, s − i) is defined as the probability that none of the remaining (s − i) slots are discovery slots, or alternatively, it is the probability that no discovery slot exist among (s − i) slots and is calculated as

(5)

4.2. RFID System Efficiency

An interesting metrics to be measured for RFID systems is its efficiency which can be calculated as follows. The expected number of identified tags for each interrogation round can be calculated as follows

(6)

and the efficiency of the RFID system can then is calculated as

(7)

Figure 3 shows the efficiency of the RFID system with different frame sizes and number of tags. The figure clearly shows that efficiency maximizes when number of

slots is equal to number of tags.

4.3. Analytical Model for Multiple Interrogation Rounds

Recall that from Equation (2), the RFID reader can only identify up to m(n, s) tags in one interrogation round. To estimate the probability that k tags are identified when the whole interrogation process ends (i.e., after r rounds), we must keep track of different possibilities that lead to identifying the k tags in r rounds.

For example, assume that tag A discovered 4 tags after 3 rounds of interrogation frames. Then, A might have discovered 1 tag in the first round, 0 tag in the second and 3 tags in the third round. On the other hand, it might have discovered 2 tags in the first round, one tag in the second and one tag in the third round.

To account for such possibilities, subsequent interrogation rounds can be described as a two dimensional probability map with (n + 1) × r states as shown in Figure 4. Each state (x, y) represents the probability that y tags are identified up to and including the xth round. Any state (x, y) can only access states (x + 1, y), (x + 1, y + 1),∙∙∙ or (x + 1, min(y + m(y, s), n)). The transition probabilities from states (x, a) to (x + 1, b) are given by the probability mass of the number of identified tags in round x.

Note that the states’ probabilities are greatly dependent on the number of tags n and the number of slots s. In fact, the probability of the state (x, y) given that there are n tags and s slots per round can be given as

(8)

Therefore, the probability distribution function of the number of tags identified after r rounds is given by calculating the probabilities (), .

4.4. Model Validation

To validate the accuracy of our analytical models, we have implemented the slot selection mechanism in MATLAB and compared its result with the result obtained from the models presented earlier. Simulation results are averaged over 10,000 runs with different seeds. Figure 5 shows a comparison of the cumulative distribution function of the number of identified tags out of 10 tags using different number of slots. As shown in the Figure, the model matches perfectly with the simulation results. Figure 6 shows the cumulative distribution function of the number of identified tags using 4 slots in different number of rounds with similar accuracy.

5. Parameter Optimization

The aforementioned multiple interrogation rounds model can be used to optimize the parameters of the RFID sys-

tem. We are interested in finding the optimal system configuration that minimizes the discovery time such that probability that the reader misses at most one tag is less than a certain threshold ϵ. Each round r takes t_r + t_s*s seconds to finish where t_r is the time to send the Hello packet and t_s is the slot duration. Then, the discovery time can be calculated as

(9)

We can represent this optimization problem as the following linear program

(10)

where P_Miss is the probability of missing at least one tag and can be computed using Equation (8) as follows

(11)

To solve this optimization problem, we propose a heuristic approach to find the optimal number of slots and rounds needed to discover all the tags with certain miss threshold. The approach sequentially iterates through all slot values starting from 2 slots to maxSlots slots. Then, for each number of slots, the approach finds the minimum number of rounds that satisfy the condition P_Miss ≤ ϵ and minimizes the discovery time.

The algorithm Find Optimal Configuration (n, ϵ, maxSlots, t_r, t_s) describes such approach.

6. Conclusion and Future Work

In this paper, we presented a mathematical model to analysis the framed slotted aloha protocol used in RFID anti-collision standards. Through recursive computation in two stages, the model predicts the performance with high accuracy. The mathematical model is used to optimally configure the parameters of the interrogation process such as frame size and number of rounds. In our future work, we are planning to extend the model to different varieties of the slotted frame aloha (i.e. non-muting, variable frame size etc.).

Acknowledgements

This work is part of the REMONG project supported by the National Science, Technology and Innovation Plan, Saudi Arabia grants: NSTIP-10-ELE1238-10.

REFERENCES