 Proceedings of Engineering and Technology Innovation , vol. 3, 2016, pp. 16 - 18 16 A Fast Anticollision Algorithm with Early Adjustment of Frame Length for the EPCglobal UHF Class-1 Generation-2 RFID Standard Wen-Tzu Chen * Department of Transportation and Communication Management, National Cheng Kung University, Tainan, Taiwan. Received 27 January 2016; received in revised form 16 February 2016; accept ed 11 March 2016 Abstract This paper deve lops a fast algorith m to identify a large nu mbe r of tags in a short period of t ime durat ion in RFID systems. The ma in goal of the proposed algorith m is to meet the require ment in supply chain manage ment. In this paper, we de rive mathe mat ica l mode l to analy ze the tag identify process. Based on the analysis, we can dec ide the optima l fra me length and when the current read round is early ended. We find that the optimal fra me length should be set to 1.72 times of the nu mbe r o f tags when the rat io bet ween co llision -slot duration and e mpty-slot durat ion is 4. Through the use of early ad justment o f fra me length , the RFID interrogator e xa mines the fitness of fra me le mgth only at three t ime slots in each read round. The primary advantage of ou r algorith m is the ab ility to ach ieve a good comp ro mise between th roughput performance and computation complexity. Keywor ds : RFID, tag identification, logistic management, read efficiency, An- ti-collision algorithm 1. Introduction Fo r mana g ing a la rge a mount o f ob jects and ident ify ing the ir IDs, th e rad io frequen cy ide nt ificat ion (RFID) te chno logy ope rat ing on u lt ra -h igh frequen cy (UHF) b and is in - cre as ing ly be ing used espec ia lly in log ist ic mana ge ment . To meet th e requ ire me nt o f rea d ing a dense popu lat ion o f ob jects, th e EPCg loba l dev e loped an a ir inte rfa ce , na me d UHF Class -1 Gene rat ion -2 o r ISO 18000-6 Type C [1]. The a lgorith ms for identify ing mu lt iple tags in RFID systems have been wide ly studied in the lite rature [2-6]. The EPCgloba l UHF Class -1 Generat ion-2 specifies an algo rith m based on dynamic fra me slotted ALOHA (DFSA ) to solve the RFID antico llis ion pro b - le m. The author in [ 4] indicated that the read performance of DFSA depends ma in ly on the accuracy o f backlog estimate and fra me length setting. Fo r the DFSA a lgorith m, a ma ximu m throughput of 36.8% can be achieved only if the fra me length is set to the nu mbe r of tags . One o f the most interesting p rocedures is how to dy- namica lly ad jus t fra me length to ach ieve ma ximu m throughput when a b ig d iffe rence exists between frame length and tag quantity . 2. Proposed Algorithm This paper proposes a simple and efficient anticollision algorith m for the EPCg lobal Cass -1 Generation-2 protocol and describes clear ru les for early adjustment mechanism of fra me length. This mechanism allows the interrogator to early end the current read round at any time slot and enter into a new round with a new fra me length. Hence, the interrogator will e xa mine whether the current fra me length requires adjustment or not and how to adjust it if necessary. To achieve a good compro mise between computation comple xity and throughput performance, the proposed algorithm e xa mines the fitness of fra me length at only the three quart iles in each read round, i.e. at the L/4 th , L/2 th , and (3/4)L th slots. The procedures of the proposed method is shown in Fig. 1. A key performce of anticollision a lgorith m is normalized throughput, *Corresponding aut hor. Email: wt chen@mail.ncku.edu.tw Proceedings of Engineering and Technology Innovation , vol. 3, 2016, pp. 16 - 18 17 Copyright © TAETI ( )/ S S C E U S T S T C T E T       (1) S, C, and E are the numbers of successful, collision, and e mpty slots. The t ime intervals of the successful, collision, and e mpty slots are TS, TC, and TE, respectively. Query(Q) QueryRep yes Q=Qopt Update Q with Qopt no Count (S, C, E) At the three quartiles slot Estimate n=(S+2.39C)L/i Qopt=round(log2(a·n)) Fig. 1 Proposed anti-collision procedures At the three time slots, the interrogator counts the number of singly occupied slots Si, the number of co llision slots Ci, and the number of empty slots Ei. Note that i is equal to L/4, L/2, or (3/ 4) L here . The tag quantity to be read at the beginning of the round can be estimated by [6]. iLCSn ii /)39.2(ˆ  (2) Given tag quantity n, we atte mpt to deter- mine an optima l fra me length Lopt to ma ximize the throughput in (1). Ta king the derivative of U with respect to L and setting the derivative to zero lead to an optimal frame length. naL  opt (3) In Eq. (3), a is a coeffic ient. Table 1 lists the coefficients for different values of TC/TE. Table 1 Coefficients between Lopt and n TC/TE a (Lopt=a×n) 1 1 2 1.30 3 1.53 4 1.72 5 1.89 6 2.05 7 2.19 8 2.32 9 2.44 After co mputing the optima l fra me length, the interrogator should check whether the cu r- rent fra me length is appropriate or not. The fra me length must be a power of 2 due to the UHF Class -1 Generation-2 standard. Hence, the optimal Q value can be obtained by: Qopt=round(log2Lopt) (4) 3. Simulation Results The read performance of the proposed algo- rith m and the refe rence schemes was exa mined by carrying out computer simu lations based on the Monte Carlo technique. Fig. 2 Co mparison of throughput performance for anticollision algorithms Fig. 3 Time-saving efficiency The throughput performance of the proposed algorith m is presented in Fig. 2. As mentioned before, our method uses early adjustment mechanis m for fra me length and performs at most three e xa minations in each read round for the fitness of fra me length. It can be found that our method has better throughput performance as compared with the other schemes. Particu- larly, for a large numbe r of tags, i.e. 1000, the proposed algorithm can achieve up to 10% throughput imp rovement as compared with the Proceedings of Engineering and Technology Innovation , vol. 3, 2016, pp. 16 - 18 18 Copyright © TAETI typical DFSA. Another advantage of the pro- posed method is the stability. When the nu mber of tags is increased, the proposed method can keep the throughput stable. Fig. 3 presents the time -saving effic iency for different algo rith ms. It can be observed fro m Fig . 3 that our a lgorith m can obta in 5 -10 % time -saving e ffic iency as the tag quantity is greater than 200. 4. Conclusions This paper proposes an efficient RFID an- ticollision algorithm to improve the read per- formance for the EPCglobal UHF Class -1 Gen- eration-2 standard. The results show that the proposed algorithm can ach ieve up to 400 tags/s read speed. For a large number o f tags, i.e. 1000, the proposed algorith m can achieve up to 10% throughput imp rovement as compared with the typical DFSA. We believe that this advantage comes fro m the early adjustment mechanis m for fra me length. Another advantage of the pro- posed method is the stability. When the nu mber of tags is increased, the proposed method can keep the throughput stable. Acknowledgement The support of Taiwan’s Ministry of Science and Techno logy, unde r Grant M OST 104-222 1-E-006-200 is gratefully acknowledged. References [1] EPCg lobal, EPC radio-frequency identity protocols class -1 generation-2 UHF RFID protocol for communicat ions at 860 MHz-960 MHz, version 1.2.0, Oct. 2008. [2] H. Vogt, “ Efficient object identification with passive RFID tags,” International Conference on Pe rvasive Co mputing , London, UK, pp. 98-113, 2002. [3] D. Lee, O. Bang, S. Im, and H. Lee, “ Effi- cient dual bias Q-algorithm and optimu m weights for EPC c lass 1 generation 2 pro- tocol,” 14 th European Wire less Conference, pp. 1-5, June 2008. [4] W. T. Chen, “An accurate tag estimate method for imp roving the performance of an RFID anticollision a lgorithm based on dynamic fra me length ALOHA,” IEEE Trans. Autom. Sci. Eng, vol. 6, no. 1, pp. 9-15, Jan. 2009. [5] B. Knerr, M. Holze r, C. Angerer, and M. Rupp, “Slot-wise ma ximu m likelihood es- timation of the tag population size in FSA protocols,” IEEE Trans. Co mmun ications, vol. 58, no. 2, pp. 578-585, Feb. 2010. [6] W. T. Chen, “A feasible and easy-to- imple ment anti-collision algorith m for the EPCg lobal UHF class -1 generation-2 RFID protocol,” IEEE T rans. Autom. Sci. Eng. , vol. 11, no. 2, pp. 485-491, Apr. 2014.