2013 Proceedings IEEE INFOCOM 300 [6]J.Cha and J.Kim,"Novel Anti-collision Algorithms for Fast Object nl0k Identification in RFID System,"Proc.IEEE ICPADS,2005. n=50k 250 n=100k [7]D.Klair,K.Chin,and R.Raad,"On the Energy Consumption of Pure 200 n=200k and Slotted Aloha based RFID Anti-Collision Protocols."Computer 0一440k==== Communications,2008. 150 n=500k [8]D.Hush and C.Wood,"Analysis of Tree Algorithm for RFID Arbitration,"Proc.of IEEE ISIT.1998. u I 100 [9]J.Myung and W.Lee,"An adaptive memoryless tag anti-collision 50 protocol for RFID networks,"Proc.IEEE ICC,2005. [10]H.Choi,J.Cha,and J.Kim,"Fast Wireless Anti-collision Algorithm 0 in Ubiquitous ID System,"Proc.IEEE VTC,Sep 2004. 0.1 0.20.30.40.50.6 [11]V.Namboodiri and L.Gao,"Energy-Aware Tag Anti-Collision h Protocols for RFID Systems,"Proc.of IEEE PerCom,2007. [12]M.Kodialam and T.Nandagopal,"Fast and Reliable Estimation Fig.4.Execution time with respect to the value of l/h when o =99%, Schemes in RFID Systems,"Proc.of ACM MOBICOM,Los Angeles. B=1% 2006. [13]M.Kodialam,T.Nandagopal,and W.Lau."Anonymous Tracking using RFID tags,”Poc.g寸IEEE INFOCOM,2007. has a larger slope than that of TBC. [14]C.Qian.H.Ngan,and Y.Liu,"Cardinality Estimation for Large-scale RFID Systems,"Proc.of IEEE PerCom,2008. D.Execution time required in terms of the total tag number [15]S.Chen T.Li and Y.Ling,"Identifying the Missing Tags in a Large RFID System."Proc.of ACM Mobihoc.2010. Finally,we evaluate the performance of TBC under [16]B.Sheng.Q.Li,and W.Mao,"Efficient Continuous Scanning in RFID different numbers of tags.The results are shown in Fig.4. Systems,"Proc.of IEEE INFOCOM,March 2010. [17]C.Tan,B.Sheng,and Q.Li,"How to Monitor for Missing RFID where a =99%,B=1%,I/h varies from 0.1 to 0.6,and n Tags."Proc.of IEEE ICDCS.June 2008. varies from 10k to 500k.Each value of n corresponds to a [18]S.Chen,M.Zhang.and B.Xiao."Efficient Information Collection Protocols for Sensor-augmented RFID Networks,"Proc.of IEEE curve in the figure.The execution time of TBC increases as n INFOCOM.April 2011. increases,which is expected.For all values of n,we observe [19]B.Bianchi,L.Fratta,and M.Oliveri,"Performance Evaluation and that the execution time of TBC increases as I/h increases, Enhancement of the CSMA/CA MAC Protocol for 802.11 Wireless confirming the results in Tables II-IV LANs,"Personal,Indoor and Mobile Radio Communications.IEEE International Symposium on.vol.2,pp.392-396.1996. [20]H.Han,B.Sheng.Chiu C.Tan,Q.Li,W.Mao,and S.Lu,"Counting VI.CONCLUSION RFID Tags Efficiently and Anonymously,"Proc.IEEE INFOCOM, March 2010. This paper proposes a new solution for multigroup [21]T.Li,S.Wu,S.Chen,and M.Yang,"Energy Efficient Algorithms for threshold-based classification in a large RFID system.While the RFID Estimation Problem."Proc.IEEE INFOCOM,March 2010. much of the prior work focuses on estimating the total [22]Philips Semiconductors, "I-CODE Smart Label RFID Tags," http://www.nxp.com/acrobat_download/other/identification/SL092030.pdf. number of tags in a system,it is inefficient to apply those Jan2004. solutions to sequentially estimate the size of each tag group and see if it is above a threshold.In this paper,we propose a new protocol based on logical bitmaps that allow the sizes of all groups to be estimated together for classification. Slot sharing is exploited to reduce the execution time.The new method is able to perform tag-group classification with any pre-set accuracy.Our protocol can be configured for tradeoff between time efficiency and accuracy.We evaluate the proposed solution and compare it with existing protocols through simulations,which demonstrate that the new protocol performs better in terms of execution time than the best existing work. VII.ACKNOWLEDGEMENT This work was supported in part by the National Science Foundation under grant CNS-1115548. REFERENCES [1]L.Ni,Y.Liu,and Y.C.Lau,"Landmarc:Indoor Location Sensing using Active RFID,"Proc.of IEEE PerCom,2003. [2]B.Sheng.Chiu C.Tan,Q.Li.and W.Mao. “Finding Popular Categories for RFID Tags,"Proc.ACM MOBIHOC,May 2008. [3]Q.Yao,Y.Qi,J.Han,J.Zhao,X.Li,and Y.Liu,"Randomizing RFID Private Authentication,"Proc.of IEEE PerCom,2009. [4]H.Vogt,"Efficient Object Identification with Passive RFID Tags," Proc.of IEEE PerCom.2002. [5]J.Zhai and G.N.Wang."An Anti-Collision Algorithm Using Two- functioned Estimation for RFID Tags,"Proc.of /CCSA,2005. 8980 50 100 150 200 250 300 0.1 0.2 0.3 0.4 0.5 0.6 Time in seconds l/h n=10k n=50k n=100k n=200k n=400k n=500k Fig. 4. Execution time with respect to the value of l/h when α = 99%, β = 1% has a larger slope than that of TBC. D. Execution time required in terms of the total tag number Finally, we evaluate the performance of TBC under different numbers of tags. The results are shown in Fig. 4, where α = 99%, β = 1%, l/h varies from 0.1 to 0.6, and n varies from 10k to 500k. Each value of n corresponds to a curve in the figure. The execution time of TBC increases as n increases, which is expected. For all values of n, we observe that the execution time of TBC increases as l/h increases, confirming the results in Tables II-IV. VI. CONCLUSION This paper proposes a new solution for multigroup threshold-based classification in a large RFID system. While much of the prior work focuses on estimating the total number of tags in a system, it is inefficient to apply those solutions to sequentially estimate the size of each tag group and see if it is above a threshold. In this paper, we propose a new protocol based on logical bitmaps that allow the sizes of all groups to be estimated together for classification. Slot sharing is exploited to reduce the execution time. The new method is able to perform tag-group classification with any pre-set accuracy. Our protocol can be configured for tradeoff between time efficiency and accuracy. We evaluate the proposed solution and compare it with existing protocols through simulations, which demonstrate that the new protocol performs better in terms of execution time than the best existing work. VII. ACKNOWLEDGEMENT This work was supported in part by the National Science Foundation under grant CNS-1115548. REFERENCES [1] L. Ni, Y. Liu, and Y. C. Lau, “Landmarc: Indoor Location Sensing using Active RFID,” Proc. of IEEE PerCom, 2003. [2] B. Sheng, Chiu C. Tan, Q. Li, and W. Mao, “Finding Popular Categories for RFID Tags,” Proc. ACM MOBIHOC, May 2008. [3] Q. Yao, Y. Qi, J. Han, J. Zhao, X. Li, and Y. Liu, “Randomizing RFID Private Authentication,” Proc. of IEEE PerCom, 2009. [4] H. Vogt, “Efficient Object Identification with Passive RFID Tags,” Proc. of IEEE PerCom, 2002. [5] J. Zhai and G. N. Wang, “An Anti-Collision Algorithm Using Two￾functioned Estimation for RFID Tags,” Proc. of ICCSA, 2005. [6] J. Cha and J. Kim, “Novel Anti-collision Algorithms for Fast Object Identification in RFID System,” Proc. IEEE ICPADS, 2005. [7] D. Klair, K. Chin, and R. Raad, “On the Energy Consumption of Pure and Slotted Aloha based RFID Anti-Collision Protocols,” Computer Communications, 2008. [8] D. Hush and C. Wood, “Analysis of Tree Algorithm for RFID Arbitration,” Proc. of IEEE ISIT, 1998. [9] J. Myung and W. Lee, “An adaptive memoryless tag anti-collision protocol for RFID networks,” Proc. IEEE ICC, 2005. [10] H. Choi, J. Cha, and J. Kim, “Fast Wireless Anti-collision Algorithm in Ubiquitous ID System,” Proc. IEEE VTC, Sep 2004. [11] V. Namboodiri and L. Gao, “Energy-Aware Tag Anti-Collision Protocols for RFID Systems,” Proc. of IEEE PerCom, 2007. [12] M. Kodialam and T. Nandagopal, “Fast and Reliable Estimation Schemes in RFID Systems,” Proc. of ACM MOBICOM, Los Angeles, 2006. [13] M. Kodialam, T. Nandagopal, and W. Lau, “Anonymous Tracking using RFID tags,” Proc. of IEEE INFOCOM, 2007. [14] C. Qian, H. Ngan, and Y. Liu, “Cardinality Estimation for Large-scale RFID Systems,” Proc. of IEEE PerCom, 2008. [15] S. Chen T. Li and Y. Ling, “Identifying the Missing Tags in a Large RFID System,” Proc. of ACM Mobihoc, 2010. [16] B. Sheng, Q. Li, and W. Mao, “Efficient Continuous Scanning in RFID Systems,” Proc. of IEEE INFOCOM, March 2010. [17] C. Tan, B. Sheng, and Q. Li, “How to Monitor for Missing RFID Tags,” Proc. of IEEE ICDCS, June 2008. [18] S. Chen, M. Zhang, and B. Xiao, “Efficient Information Collection Protocols for Sensor-augmented RFID Networks,” Proc. of IEEE INFOCOM, April 2011. [19] B. Bianchi, L. Fratta, and M. Oliveri, “Performance Evaluation and Enhancement of the CSMA/CA MAC Protocol for 802.11 Wireless LANs,” Personal, Indoor and Mobile Radio Communications, IEEE International Symposium on, vol. 2, pp. 392–396, 1996. [20] H. Han, B. Sheng, Chiu C. Tan, Q. Li, W. Mao, and S. Lu, “Counting RFID Tags Efficiently and Anonymously,” Proc. IEEE INFOCOM, March 2010. [21] T. Li, S. Wu, S. Chen, and M. Yang, “Energy Efficient Algorithms for the RFID Estimation Problem,” Proc. IEEE INFOCOM, March 2010. [22] Philips Semiconductors, “I-CODE Smart Label RFID Tags,” http://www.nxp.com/acrobat download/other/identification/SL092030.pdf, Jan 2004. 2013 Proceedings IEEE INFOCOM 898