12 1216202428 0099 d (bit) 8 26 4 1500200025003000350040004500500 n scannng area Fig.3.Optimal values of a and d. Fig.4.Execution time under different length of Fig.5.Execution time under different number of category ID Ci. tags in scanning area. 500 10 0 100 250 300 Number of rles Fig.6.Execution time under different number of Fig.7.Number of verified category IDs under Fig.8.Accuracy under different number of rules. rules. different number of rules. the length of the Bloom filter and the number of hash functions [5]M.Zhang.T.Li,S.Chen,and B.Li,"Using analog network coding used in the Bloom filter to meet the requirement. to improve the RFID reading throughput."in IEEE ICDCS.2010.pp. 547C556. IX.CONCLUSION (6]H.Ning,Y.CongZ.-Q.Xu,T.Hong,J.-C.Zhao,and Y.Zhang,"Perfor- In this paper,we investigate the rule checking problem mance Evaluation of RFID Anti-Collision Algorithm with FPGA Imple- mentation."in 21st International Conference on Advanced Information in RFID systems.We present two efficient protocols,one Networking and Applications Workshops,May 2007. is CRCP,it improves the time efficiency by resolving the [7]M.Alotaibi,KS.Bialkowski,and A.Postula,"A Signal Strength Based collision slots.The other one is ECRCP,it combines the Tag Estimation Technique for RFID Systems,"in 2010 IEEE Internation- al Conference on RFID-Technology and Applications (RFID-TA),June collision detection and the rules'logical features to achieve the 2010. time efficiency.Based on the performance evaluation,CRCP [8]T.Lim,T.Li,and S.Yeo,"A cross-layer framework for privacy enhance- and ECRCP have better performance.Besides,the simulation ment in RFID systems,"Pervasive and Mobile Computing,Vol.4,no.6, pp.889-905,December 2008. results show that ECRCP outperforms all the other solutions. [9]L.Liu,Z.Xie,J.Xi,and S.Lai,"An Improved Anti-collision Algorithm ACKNOWLEDGEMENT in RFID System,"in Proc.of 2nd Interational Conference on Mobile Technology,Applications and Systems,pp.15-17,2005. This work is partially supported by the National Ba- [10]SS.Kim,YH.Kim,SJ.Lee,and KS.Ahn,"An Improved Anti Collision sic Research Program of China (973)under Grant No. Algorithm using Parity Bit in RFID System,"in Proc.of 7th IEEE Internation Symposium,pp.224-227.2008. 2009CB320705:the National Natural Science Foundation [11]Y.Zheng,and M.Li,"Fast Tag Searching Protocol for Large-Scale RFID of China under Grant No.61100196.61073028.61021062: Systems,"in 19th IEEE International Conference on Network Protocols (/CNP).October 2011. the JiangSu Natural Science Foundation under Grant No. [12]H.Yue,C.Zhang.M.Pan,Y.Fang,and S.Chen,"A Time-efficient BK2011559 Information Collection Protocol for Large-scale RFID Systems,"in Pro- REFERENCES ceedings IEEE INFOCOM,2012. [13]EPC Radio Frequency Identify Protocols Class-1 Generation-2 UHF [1]J.Myung.W.Lee,and S.Jaideep,"Adaptive binary splitting for efficient RFID Protocol for Communications at 860 MHz-916 MHz Version rfid tag anti-collision,"IEEE Communications Letters,vol.10.no.3.pp. 1.2.0 144-146.2006. [14]"Information Technology Automatic Identification And Data Capture [2]L.Pan and H.Wu,"Smart Trend-Traversal:A Low Delay and Energy Tag Techniques-Radio Frequency Identification For Item Management Air Arbitration Protocol for Large RFID Systems,"in Proc.of INFOCOM. Interface.Part 6.Parameters for Air interface communications at 860- mini-conference,2009. 960 MHZ,"ed:Standard ISO 18000-6.2003. [3]B.Sheng,C.C.Tan,Q.Li,and W.Mao,"Finding popular categoried [15]J.Wang,H.Hassanieh,D.Katabi,and P.Indyk,"Efficient and Reliable for RFID tags,"in Proc.of ACM Mobihoc,2008. Low-Power Backscatter Networks,"ACM S/GCOMM Computer Commu- [4]L.Xie,B.Sheng.C.C.Tan,H.Han,Q.Li and D.Chen,"Efficient tag nicarion Review,Vol.42.no.4,pp.61-72.October 2012. identification in mobile RFID systems,"in Proc.of INFOCOM,2010.0 4 8 12 16 20 24 28 32 0 4 8 12 16 20 24 28 32 0 10 20 30 40 ,7 d (bit) Execution time (sec) (,7=4 , d=7) Fig. 3. Optimal values of α¯ and d. 16 24 32 40 48 56 64 0 2 4 6 8 10 12 14 16 18 20 Length of category ID (bits) Execution Time (sec) ARCP PRCP BRCP CRCP ECRCP Fig. 4. Execution time under different length of category ID Cj . 500 1000 1500 2000 2500 3000 3500 4000 4500 5000 0 5 10 15 20 25 30 Number of tags in scanning area Execution Time (sec) ARCP PRCP BRCP CRCP ECRCP Fig. 5. Execution time under different number of tags in scanning area. 50 100 150 200 250 300 350 400 450 500 0 5 10 15 20 25 30 Number of rules Execution Time (sec) ARCP PRCP BRCP CRCP ECRCP Fig. 6. Execution time under different number of rules. 50 100 150 200 250 300 0 500 1000 1500 2000 2500 Number of rules Number of category IDs verified in the protocol ARCP PRCP BRCP CRCP ECRCP Fig. 7. Number of verified category IDs under different number of rules. 50 100 150 200 250 300 0 10 20 30 40 50 60 70 80 90 100 Number of rules Accuracy of checking the rules (%) ARCP PRCP BRCP CRCP ECRCP Fig. 8. Accuracy under different number of rules. the length of the Bloom filter and the number of hash functions used in the Bloom filter to meet the requirement. IX. CONCLUSION In this paper, we investigate the rule checking problem in RFID systems. We present two efficient protocols, one is CRCP, it improves the time efficiency by resolving the collision slots. The other one is ECRCP, it combines the collision detection and the rules’ logical features to achieve the time efficiency. Based on the performance evaluation, CRCP and ECRCP have better performance. Besides, the simulation results show that ECRCP outperforms all the other solutions. ACKNOWLEDGEMENT This work is partially supported by the National Ba￾sic Research Program of China (973) under Grant No. 2009CB320705; the National Natural Science Foundation of China under Grant No. 61100196, 61073028, 61021062; the JiangSu Natural Science Foundation under Grant No. BK2011559. REFERENCES [1] J. Myung, W. Lee, and S. Jaideep, “Adaptive binary splitting for efficient rfid tag anti-collision,” IEEE Communications Letters, vol. 10, no. 3, pp. 144-146, 2006. [2] L. Pan and H. Wu, “Smart Trend-Traversal: A Low Delay and Energy Tag Arbitration Protocol for Large RFID Systems,” in Proc. of INFOCOM, mini-conference, 2009. [3] B. Sheng, C. C. Tan, Q. Li, and W. Mao, “Finding popular categoried for RFID tags,” in Proc. of ACM Mobihoc, 2008. [4] L. Xie, B. Sheng, C. C. Tan, H. Han, Q. Li and D. Chen, “Efficient tag identification in mobile RFID systems,” in Proc. of INFOCOM, 2010. [5] M. Zhang, T. Li, S. Chen, and B. Li, “Using analog network coding to improve the RFID reading throughput,” in IEEE ICDCS, 2010, pp. 547C556. [6] H. Ning, Y. CongZ.-Q. Xu, T. Hong, J.-C. Zhao, and Y. Zhang, “Perfor￾mance Evaluation of RFID Anti-Collision Algorithm with FPGA Imple￾mentation,“ in 21st International Conference on Advanced Information Networking and Applications Workshops, May 2007. [7] M. Alotaibi, KS. Bialkowski, and A. Postula, “A Signal Strength Based Tag Estimation Technique for RFID Systems,“ in 2010 IEEE Internation￾al Conference on RFID-Technology and Applications (RFID-TA), June 2010. [8] T. Lim, T. Li, and S. Yeo, “A cross-layer framework for privacy enhance￾ment in RFID systems,“ Pervasive and Mobile Computing, Vol. 4, no. 6, pp. 889-905, December 2008. [9] L. Liu, Z. Xie, J. Xi, and S. Lai, “An Improved Anti-collision Algorithm in RFID System,” in Proc. of 2nd International Conference on Mobile Technology, Applications and Systems, pp. 15-17, 2005. [10] SS. Kim, YH. Kim, SJ. Lee, and KS. Ahn, “An Improved Anti Collision Algorithm using Parity Bit in RFID System,” in Proc. of 7th IEEE Internation Symposium, pp.224-227, 2008. [11] Y. Zheng, and M. Li, “Fast Tag Searching Protocol for Large-Scale RFID Systems,” in 19th IEEE International Conference on Network Protocols (ICNP), October 2011. [12] H. Yue, C. Zhang, M. Pan, Y. Fang, and S. Chen, “A Time-efficient Information Collection Protocol for Large-scale RFID Systems,” in Pro￾ceedings IEEE INFOCOM, 2012. [13] EPC Radio Frequency Identify Protocols Class-1 Generation-2 UHF RFID Protocol for Communications at 860 MHz - 916 MHz Version 1.2.0. [14] “Information Technology Automatic Identification And Data Capture Techniques-Radio Frequency Identification For Item Management Air Interface. Part 6. Parameters for Air interface communications at 860- 960 MHZ,” ed: Standard ISO 18000-6, 2003. [15] J. Wang, H. Hassanieh, D. Katabi, and P. Indyk, “Efficient and Reliable Low-Power Backscatter Networks,” ACM SIGCOMM Computer Commu￾nication Review, Vol. 42, no. 4, pp.61-72, October 2012