A Novel Time-aware Frame Adjustment Strategy for RFID Anti-collision

Haipeng Chen, Kexiong Liu, Chunyang Ma, Yu Han and Jian Su

Abstract: Recently, object identification with radio frequency identification (RFID)technology is becoming increasingly popular. Identification time is a key performance metric to evaluate the RFID system. The present paper analyzes the deficiencies of the state-of-the-arts algorithms and proposes a novel sub-frame-based algorithm with adaptive frame breaking policy to lower the tag identification time for EPC global C1 Gen2 UHF RFID standard. Through the observation of slot statistics in a sub-frame, the reader estimates the tag quantity and efficiently calculates an optimal frame size to fit the unread tags. Only when the expected average identification time in the calculated frame size is less than that in the previous frame size, the reader starts the new frame. Moreover,the estimation of the proposed algorithm is implemented by the look-up tables, which allows dramatically reduction in the computational complexity. Simulation results show noticeable throughput and time efficiency improvements of the proposed solution over the existing approaches.

Keywords: Radio frequency identification, anti-collision, alpha, time efficiency.

1 Introduction

The growing demands in object identification make radio frequency identification (RFID)technology increasingly attractive. RFID enables fast non-line-of-sight, mobile, multiobject recognition, position and tracking [Wu, Zhou, Zuo et al. (2013)]. It has been widely used in intelligent management and monitoring of people, object and asset in various fields penetrating into our daily lives because of its long identification distance,fast speed, and the tag’s large memory capacity and reusability, etc. In various RFID application systems, a reader usually need to quickly and accurately identify a large number of tags within its coverage range. Since the reader communicates with the tags via a shared wireless channel, the information collision occurs when multiple tags respond to the reader simultaneously [Klair, Chin and Raad (2010)]. Such phenomenon is termed as multi-tag collision, which leads to reduced identification efficiency, increased omission ratio and identification latency, and eventually limits the RFID applications.Therefore, RFID systems need to employ an efficient anti-collision algorithm to tackle such multi-tag collisions and minimize their impact. The mainstream anti-collision protocols can be divided into Aloha-based and Tree-based protocols.

Tree-based protocols essentially split collided tags into subsets, and further split the subsets repeatedly up to all tags are identified by the reader. Aloha-based protocols divide the time into several frames contain multiple time intervals (called slot), so that tags randomly choose one slot per frame to respond to the reader. As a most widespread standard in RFID systems, EPC global C1 Gen2 [EPC global (2015)] adopts a dynamic frame slotted Aloha (DFSA) protocol to manage the identification process of tags.Recently, most RFID manufacturers follow the EPC global C1 Gen2, attracting more attention for relevant research of DFSA protocols [Chen (2009); Impinj Inc. (2015)].

Specifically, DFSA protocol is characterized by the strategy it employs to adjust the frame size along the identification process. The performance of DFSA depends on both the cardinality (the number of unread tags) estimation and the setting of frame size. In order to ensure the accuracy of estimation, most previous solutions require a vast computation costs, but most RFID readers in practice are built with a single-chip microprocessor, whose computational ability and memory are limited. Recently, many state-of-the-arts works have presented energy-efficient DFSA algorithms for the purpose of reducing computation overhead. The literature [Chen (2016)] presented an anticollision protocol which resorts to only one examination of current frame size at a specific time slot during each identification round. Solic et al. [Solic, Radic and Rozic(2014)] introduced an Improved Linearized Combinatorial Model (ILCM) to estimate the cardinality at the cost of modest calculation. Since the ILCM adopts a frame-by-frame estimation based on the number of idle, success, and collision slots observed in the previous full frame, the performance of ILCM is limited to the accuracy of a single estimation. Therefore, its performance fluctuates sharply accompanied by the tag number varies by a big margin. To achieve the robust performance, the slot-by-slot version of ILCM has been presented [Solic, Radic and Rozic (2016)]. In another paper, the authors presented a FuzzyQ method which integrates fuzzy logic with a DFSA algorithm [Arjona,Landaluce, Perallos et al. (2016)]. A fuzzy rule based system is defined to model the current frame size and the idle or collision response rate as fuzzy sets to adaptively calculate frame size. However, the performance of FuzzyQ is needed to further improve.Sub-frame based algorithms [Su, Sheng, Hong et al. (2016); Chen, Su and Yi (2017)] are proposed very recently. In Su et al. [Su, Sheng, Hong et al. (2016)], the tag quantity is predict based on the observation of ratio relations between idle and collision statistics in the current sub-frame. However, the estimation is not accurate enough because it is based on empirical correlation rather than theoretical calculation. In Chen et al. [Chen, Su, Yi(2017)], the MAP estimation function is used to estimate the tag quantity by the observation of current sub-frame. The DS-MAP picks up an estimation result from the look-up tables instead of calculating a real-time result of the tag number during the identification process. Although the DS-MAP can reduce the total number of slots during the identification process, it does not consider the duration discrepancy of different slot type. Therefore, the DS-MAP algorithm is inefficient in terms of time efficiency or identification time.

To reduce the computational complexity and reduce the identification time during the identification process, we propose an anti-collision solution named time-aware frame adjustment strategy (TAFAS) based algorithm. The proposed algorithm integrates the low-cost estimation method, adaptive frame size calculation strategy and efficient frame size adjustment policy. Specifically, the proposed algorithm determines the optimal frame size based on both estimated tag quantity and the time duration of a slot. Moreover, the proposed frame size adjustment policy can avoid the improper frame adjustment. Extensive simulation results indicate that the proposed algorithm can achieve better performance than the reference methods.

2 Algorithm description

2.1 Estimation strategy

In most RFID application scenarios, the number of tags is unknown to the reader in advance, hence the reader need to estimate the tag number accurately to maximize the performance of the proposed algorithm. Here we also refer to the maximum a posteriori probability (MAP) method to calculate the cardinality of tag population based on the feedback from a sub-frame. Although MAP can achieve an accurate estimation, its high computational overhead hinders its application in low-cost RFID platforms. In the proposed estimation method, we design look-up tables to pre-store the estimation results.Restricted by the sub-frame size and the item quantity in the tables, the proposedestimation strategy is space-efficient and implementable. Considering tags allocated inslots, the probability that idle slot occurstimes, success slot occurs times, and collision slots occurs times in a sub-frame can be expressed as

Where Pi, Ps, and PCare the probabilities of idle, success and collision slots in the full frame. The tag quantity involved in a sub-frame is determined when the value ofis maximized. So, the estimation result in a sub-frame is. Then, the estimated tag quantity involved in the full frame can be calculated as

To reduce computational complexity, the estimated results of the tag cardinalityduring the sub-frame can be stored in the preset tables. The recommendation setting of can be referred to Su et al. [Su, Sheng, Hong et al. (2016); Chen, Su and Yi (2017)] and can be listed in Tab. 1.

Table 1: The recommendation setting of Fsub

2.2 Adaptive frame size calculation

The most existing DFSA algorithms set the frame size as the nearest value to the estimated tag number. Unlike the conventional DFSA algorithms, the proposed algorithm calculates the frame size by minimizing the average identification time to identify one tag Tavg, which can be defined as (11)

Where E, S, and C are the number of idle slots, success slots and collision slots,respectively. TE, TS, and TCare the time intervals of above three slot types, and have

Where Tcmdis the time interval of reader’s command which can be Query, QueryAdj, or QueryRep [Su, Sheng and Hong et al. (2016)]. Considering the number of tags isandthe initial frame size is F , the fill level of tags allocated in a slot is described by a binomial distribution with 1/Foccupied probability:

Accordingly,Pr=0, Pr=1, and Pr＞1are the corresponding probabilities that a slot is idle,successful and collided, respectively. If F is assumed large enough, the distribution oftags can be approximated as Poisson distribution with mean . Then, the parameters E,S , and C in Eq. (3) can be approximated as

Substitute Eqs. (8)-(10) into Eq. (3), the Tavgcan be approximated as

We take the first derivative of Tavgwith respect to λ. Let the derivative equals to zero,we then have

Transforming the Eq. (12), we can have

By solving the Eq. (12), the value of λto minimize the Tavgcan be calculated as

Where W(*) denotes as the Lambert W-function. Consequently, the optimal frame size in the proposed algorithm can be set as

2.3 Frame size adjustment strategy

The mainstream frame size adjustment strategy can be divided into three categories. First is Frame-by-Frame (FbF) in which the reader calculates the new frame size at the end of the current frame. The FbF strategy is not efficient when the frame size is far away from the number of tags. Second is Slot-by-Slot (SbS) in which the reader calculates the new frame size at every slot of the current frame. The SbS strategy suffers from a rather high complexity. Finally, the sub-frame solution provides the flexibility of ending the current frame in advance to maintain the performance stability with a reduced computational complexity. In our proposed algorithm, we adopt a hybrid strategy combining sub-frame observation and SbS. At every slot, the reader keeps track of the relation between E and C. And then the reader will reset the sub-frame size if the difference value between E and C is above the threshold value. After the reading of Fsubslots, the reader estimates the tag quantity according to Eq. (2). And then the new frame size for the next identification round can be given by Eq. (15). Then the reader computes the Tavg1and Tavg2with the current frame size and the new frame size, respectively. The policy is to end the current frame and to adopt the new frame size if Tavg2＜Tavg1. Otherwise, the reader will go to the next slot of the current frame. The identification process ends until no collision occurs.According to the hybrid frame size adjustment strategy, the algorithm can achieve a better and stable performance.

2.3 The proposed tag identification algorithm

Combining the tag quantity estimation, frame size calculation, and frame size adjustment strategy, we propose the anti-collision algorithm TAFAS as follows.

Algorithm TAFAS Reader Operation

1: Initialize Fcurr=Fini, Fsub, E, S, and C 2: while (unidentified tags 0)3: The reader identifies tags among Fcurr slots and counts E, S, and C slot by slot.4: if E-3.2 ? C/λ>threshold 5: Fsub=i;6: else if E-0.6?C/λ<- threshold 7: Fsub=i;8: end if 9: if i==Fsub 10: Estimate the tag quantity and calculate the new frame size by using Eqs. (2) and (15).11: if Tavg2

3 Simulation results

The identification performance of the proposed algorithm and the reference methods including FuzzyQ, SUBF-DFSA, ILCM, and Impinj R2000 was compared by carrying out extensive Monte Carlo simulations. Various metrics including system throughput,time efficiency, average identification time to identify one tag are taken into account to evaluate the performance of TAFAS. The primary time parameters are the same as Su et al. [Su, Sheng, Hong et al. (2016); Chen, Su and Yi (2017)].

Fig. 1 compares the system throughput of various algorithms under different initial frame size. As can be found from Fig. 1, the performance of ILCM is most sensitive to the initial frame size than other algorithms. When the number of tags is much larger than the size of frame, the ILCM is unable to adjust to a proper frame size to fit the unread tags,and cause performance degradation. That is to say, the stability and scalability of ILCM is difficult to get used to a widely varying of the tag population. Since the other algorithms adopt the in-frame-like frame adjustment mechanism that allows the frame to be end in advance, so they can guarantee more stable performance. Also can be seen from Fig. 1, the average system throughput of five algorithms from the highest to the lowest is TAFAS, SUBF-DFSA, ILCM, FuzzyQ, and Impinj R2000. Although the Impinj R2000 and FuzzyQ can improve the performance stability and reduce the computational complexity, their system throughput is below that of ILCM. Specifically, the average system throughput of TAFAS is 0.3533, achieves a 6.9% improvement over ILCM.In order to illustrate the advantage of the TAFAS, we show the time efficiency of various algorithms in Fig. 2. The metric time efficiency is dependent on the timing parameters ofEPC global C1 Gen2, particularly on the intervals of the slots, , , and ,respectively. Forthis purpose, the reference methods are evaluated for different ratio between and . All algorithms present an increasing time efficiency with the increasing betweenand. As can be seen various algorithms show the discrepant time efficiency under the different conditions. For example, the time efficiency of Impinj R2000 is the lowest when s the increase in the Impinj R2000 achieves a significant performanceimprovement. Since the frame size can be adaptively adjusted to adapt to the different he TAFAS can always hold the best time efficiency compared to other algorithms.

Figure 1: Comparison of system throughput for various algorithms

Figure 2: Comparison of time efficiency for various algorithms

Fig. 3 presents the simulation result of the average identification time for identifying one tag with an initial frame size of 16. Note that the average identification time for identifying one tag includes the coordination time used to transmitting command and guard time beside the necessary time used for message (such as ID or EPC) transmission.The average time is calculated by Eqs. (3)-(6). As can be observed from Fig. 3, the TAFSA consumes the least average time to identify one tag. It spends about 2.1045 ms,i.e. an identification speed is of 475 tags/s. That is to say ATFAS can identify more tags per unit time. Also, since our proposed solution is based on the same hardware platform of EPC global C1 Gen2 standard, it will not bring in extra requirements compared to other algorithms.

Figure 3: Comparison of average identification time for various algorithms

4 Conclusions

In this paper, we proposed a time-aware anti-collision protocol to identify multiple RFID tags within one reader’s filed. The proposed scheme determines the optimality of the current frame size based on the combination of sub-frame observation and slot-by-slot.According to the adaptive adjustment mechanism, the ATFAS can restrain the performance degradation in time efficiency due to the duration discrepancy. Moreover,the tag quantity estimation is implemented by the look-up tables, which allows dramatically reduction in the computational complexity. Simulation results show that the proposed ATFSA outperforms other algorithm in various metrics.

Acknowledgement:This research is supported by Doctoral Scientific Research Fund of Northeast Electrical Power University (BSJXM-2016203).