正在加载图片...
TABLE IV TOTAL TIME(IN NUMBER OF SLOTS)FOR FIVE SINGLE SET ESTIMATORS.SINCE CSE AND UPE NEED TO IDENTIFY THE TYPE OF A SLOT,WE LIST THE DETAIL:EMPTY SLOTS,SINGLETON SLOTS,AND COLLISION SLOTS.FOR OTHERS,WE SIMPLY SHOW THE SUM. Number Total time (in number of slots) of tags CSE UPE EZB FNEB Enhanced FNEB empty singleton collision sum empty singleton collision sum sum sum sum 10 2220 530 305 3055 1135 384 71 1590 21.052 98.132 5526 50 2264 534 345 3143 53 269 416 840 21.052 91.808 5738 100 2277 642 328 3247 91 239 1050 1380 21,052 84.559 5732 500 1974 972 450 3396 151 380 1509 2040 21.052 46.525 5758 1000 1926 1373 704 4005 150 388 1592 2130 21,052 26,010 5683 5000 971 1822 4358 7151 147 406 1697 2250 21,052 6510 5661 quality is poor,the reader may not be able to detect [8]A.Juels,D.Molnar,and D.Wagner,"Security and privacy issues in the signal sent by RFID tags,resulting in the reader e-passports,"in SECURECOMM,2005. [9]RFID driver's licenses debated. [Onlinel. Available: possibly observing more empty slots.We can compensate http://www.wired.com/politics/security/news/2004/10/65243 by averaging the results over multiple rounds.In addition, [10]A.Juels,"RFID security and privacy:A research survey,"Manuscript, a learning phase can be adopted to characterize the link RSA Laboratories,September 2005. quality before estimation. [11]C.C.Tan,B.Sheng,and Q.Li,"Secure and serverless RFID authenti- cation and search protocols,"IEEE Transactions on Wireless Communi- 4)Active attacks:If an attacker can intentionally generate cations,2008. a reply in an arbitrary slot,there is no feasible solution [12]M.Kodialam and T.Nandagopal,"Fast and reliable estimation schemes to solve this problem till now,since all replies from in RFID systems,"in MOB/COM,2006,pp.322-333. [13]M.Kodialam,T.Nandagopal,and W.C.Lau,"Anonymous Tracking the legitimate tags may be corrupted by the attacker. using RFID tags,"in INFOCOM,2007. Therefore,active attacks are excluded in this paper. [14]Z.Bar-Yossef,T.S.Jayram,R.Kumar,D.Sivakumar,and L.Trevisan, "Counting distinct elements in a data stream,"in RANDOM,2002. VII.CONCLUSIONS [15]J.Zhai and G.-N.Wang,"An anti-collision algorithm using two- functioned estimation for RFID tags"in /CCS4(4)2005,pp.702-711. In this paper,we consider the problem of estimating the num- [16]J.Myung and W.Lee,"Adaptive splitting protocols for rfid tag collision ber of distinct tags without identifying each tag in a large scale arbitration,"in MOB/HOC,2006,pp.202-213. RFID system.We present a new scheme and its variations based [17]H.Vogt,"Efficient object identification with passive RFID tags,"in PERVASIVE,2002,Pp.98-113. on the probability of the position of the first reply from a group [18]C.Law,K.Lee,and K.-Y.Siu,"Efficient memoryless protocol for tag of tags.These schemes can be used to estimate tag population in identification,"in D/AL-M,2000,pp.75-84 both static and dynamic environments.Theoretical analysis and [19]D.Hush and C.Wood,"Analysis of tree algorithms for rfid arbitration," in1ST,1998. extensive simulation show our approach drastically improves [20]F.Zhou,C.Chen,D.Jin,C.Huang,and H.Min,"Evaluating and the time efficiency over prior schemes. optimizing power consumption of anti-collision protocols for applications in rfid systems,"in ISLPED,2004. ACKNOWLEDGMENTS [21]N.Abramson,"The Aloha system -another alterative for computer communications,"in AFIPS Conference,1970 We would like to thank all the reviewers for their helpful [22]J.-R.Cha and J.-H.Kim,"Novel anti-collision algorithms for fast object comments.This project was supported in part by US Na- identification in RFID system,"in /CPADS (2),2005,pp.63-67. tional Science Foundation grants CNS-0721443,CNS-0831904, [23]B.Zhen,M.Kobayashi,and M.Shimizu,"Framed ALOHA for multiple rfid objects identification,"IEICE Transactions 2005 CAREER Award CNS-0747108.the National High-Tech Re- [24]S.-R.Lee,S.-D.Joo,and C.-W.Lee,"An enhanced dynamic framed slot- search and Development Program of China(863)under Grant ted ALOHA algorithm for RFID tag identification,"in MOB/OUITOUS No.2006AA01Z199,the National Natural Science Foundation 2005,pp.166-174. [25]C.Qian,H.Ngan,and Y.Liu,"Cardinality estimation for large-scale of China under Grant No.90718031.No.60721002.No. RFID systems,"in PERCOM 08. 60573106 and the National Basic Research Program of China 26]H.Tijims,Understanding Probability:Chance Rules in Everyday Life. Cambridge University Press,2007. (973)under Grant No.2009CB320705. 27]M.Abramowitz and I.A.Stegun,Handbook of mathematical fimctions REFERENCES with Formulas,Graphs,and Mathematical Tables.Dover Publications, 1972. [1]L.Ni,Y.Liu,Y.C.Lau,and A.Patil,"Landmarc:indoor location sensing [28]"EPC radio-frequency identity protocols class-1 generation-2 UHF RFID using active RFID,"Percom '03. protocol for communications at 860 mhz -960 mhz version 1.1.0," [2]C.Wang.H.Wu,and N.-F.Tzeng,"RFID-based 3-d positioning EPCglobal,Tech.Rep.,2005. schemes,.”FOCOM'07. [3]C.-H.Lee and C.-W.Chung."Efficient storage scheme and query pro- cessing for supply chain management using RFID,"in S/GMOD 08. [4]A.Nemmaluri,M.D.Corner,and P.Shenoy,"Sherlock:automatically locating objects for humans,"in MobiSys 08. [5]L.Ravindranath,V.N.Padmanabhan,and P.Agrawal,"Sixthsense:RFID- based enterprise intelligence,"in MobiSys '08. [6]C.C.Tan,B.Sheng,and Q.Li,"How to monitor for missing RFID tags," in IEEE ICDCS,2008. [7]B.Sheng,C.C.Tan,Q.Li,and W.Mao,"Finding popular categoried for RFID tags,"in ACM Mobihoc,2008.TABLE IV TOTAL TIME (IN NUMBER OF SLOTS) FOR FIVE SINGLE SET ESTIMATORS. SINCE CSE AND UPE NEED TO IDENTIFY THE TYPE OF A SLOT, WE LIST THE DETAIL: EMPTY SLOTS, SINGLETON SLOTS, AND COLLISION SLOTS. FOR OTHERS, WE SIMPLY SHOW THE SUM. Number Total time (in number of slots) of tags CSE UPE EZB FNEB Enhanced FNEB empty singleton collision sum empty singleton collision sum sum sum sum 10 2220 530 305 3055 1135 384 71 1590 21,052 98,132 5526 50 2264 534 345 3143 155 269 416 840 21,052 91,808 5738 100 2277 642 328 3247 91 239 1050 1380 21,052 84,559 5732 500 1974 972 450 3396 151 380 1509 2040 21,052 46,525 5758 1000 1926 1375 704 4005 150 388 1592 2130 21,052 26,010 5683 5000 971 1822 4358 7151 147 406 1697 2250 21,052 6510 5661 quality is poor, the reader may not be able to detect the signal sent by RFID tags, resulting in the reader possibly observing more empty slots. We can compensate by averaging the results over multiple rounds. In addition, a learning phase can be adopted to characterize the link quality before estimation. 4) Active attacks: If an attacker can intentionally generate a reply in an arbitrary slot, there is no feasible solution to solve this problem till now, since all replies from the legitimate tags may be corrupted by the attacker. Therefore, active attacks are excluded in this paper. VII. CONCLUSIONS In this paper, we consider the problem of estimating the number of distinct tags without identifying each tag in a large scale RFID system. We present a new scheme and its variations based on the probability of the position of the first reply from a group of tags. These schemes can be used to estimate tag population in both static and dynamic environments. Theoretical analysis and extensive simulation show our approach drastically improves the time efficiency over prior schemes. ACKNOWLEDGMENTS We would like to thank all the reviewers for their helpful comments. This project was supported in part by US National Science Foundation grants CNS-0721443, CNS-0831904, CAREER Award CNS-0747108, the National High-Tech Research and Development Program of China (863) under Grant No. 2006AA01Z199, the National Natural Science Foundation of China under Grant No. 90718031, No. 60721002, No. 60573106 and the National Basic Research Program of China (973) under Grant No. 2009CB320705. REFERENCES [1] L. Ni, Y. Liu, Y. C. Lau, and A. Patil, “Landmarc: indoor location sensing using active RFID,” Percom ’03. [2] C. Wang, H. Wu, and N.-F. Tzeng, “RFID-based 3-d positioning schemes,” INFOCOM ’07. [3] C.-H. Lee and C.-W. Chung, “Efficient storage scheme and query processing for supply chain management using RFID,” in SIGMOD ’08. [4] A. Nemmaluri, M. D. Corner, and P. Shenoy, “Sherlock: automatically locating objects for humans,” in MobiSys ’08. [5] L. Ravindranath, V. N. Padmanabhan, and P. Agrawal, “Sixthsense: RFIDbased enterprise intelligence,” in MobiSys ’08. [6] C. C. Tan, B. Sheng, and Q. Li, “How to monitor for missing RFID tags,” in IEEE ICDCS , 2008. [7] B. Sheng, C. C. Tan, Q. Li, and W. Mao, “Finding popular categoried for RFID tags,” in ACM Mobihoc, 2008. [8] A. Juels, D. Molnar, and D. Wagner, “Security and privacy issues in e-passports,” in SECURECOMM, 2005. [9] RFID driver’s licenses debated. [Online]. Available: http://www.wired.com/politics/security/news/2004/10/65243 [10] A. Juels, “RFID security and privacy: A research survey,” Manuscript, RSA Laboratories, September 2005. [11] C. C. Tan, B. Sheng, and Q. Li, “Secure and serverless RFID authentication and search protocols,” IEEE Transactions on Wireless Communications, 2008. [12] M. Kodialam and T. Nandagopal, “Fast and reliable estimation schemes in RFID systems,” in MOBICOM, 2006, pp. 322–333. [13] M. Kodialam, T. Nandagopal, and W. C. Lau, “Anonymous Tracking using RFID tags,” in INFOCOM, 2007. [14] Z. Bar-Yossef, T. S. Jayram, R. Kumar, D. Sivakumar, and L. Trevisan, “Counting distinct elements in a data stream,” in RANDOM, 2002. [15] J. Zhai and G.-N. Wang, “An anti-collision algorithm using twofunctioned estimation for RFID tags,” in ICCSA (4), 2005, pp. 702–711. [16] J. Myung and W. Lee, “Adaptive splitting protocols for rfid tag collision arbitration,” in MOBIHOC, 2006, pp. 202–213. [17] H. Vogt, “Efficient object identification with passive RFID tags,” in PERVASIVE, 2002, pp. 98–113. [18] C. Law, K. Lee, and K.-Y. Siu, “Efficient memoryless protocol for tag identification,” in DIAL-M, 2000, pp. 75–84. [19] D. Hush and C. Wood, “Analysis of tree algorithms for rfid arbitration,” in ISIT, 1998. [20] F. Zhou, C. Chen, D. Jin, C. Huang, and H. Min, “Evaluating and optimizing power consumption of anti-collision protocols for applications in rfid systems,” in ISLPED, 2004. [21] N. Abramson, “The Aloha system - another alternative for computer communications,” in AFIPS Conference, 1970. [22] J.-R. Cha and J.-H. Kim, “Novel anti-collision algorithms for fast object identification in RFID system,” in ICPADS (2), 2005, pp. 63–67. [23] B. Zhen, M. Kobayashi, and M. Shimizu, “Framed ALOHA for multiple rfid objects identification,” IEICE Transactions 2005. [24] S.-R. Lee, S.-D. Joo, and C.-W. Lee, “An enhanced dynamic framed slotted ALOHA algorithm for RFID tag identification,” in MOBIQUITOUS, 2005, pp. 166–174. [25] C. Qian, H. Ngan, and Y. Liu, “Cardinality estimation for large-scale RFID systems,” in PERCOM ’08. [26] H. Tijims, Understanding Probability: Chance Rules in Everyday Life. Cambridge University Press, 2007. [27] M. Abramowitz and I. A. Stegun, Handbook of mathematical functions with Formulas, Graphs, and Mathematical Tables. Dover Publications, 1972. [28] “EPC radio-frequency identity protocols class-1 generation-2 UHF RFID protocol for communications at 860 mhz - 960 mhz version 1.1.0,” EPCglobal, Tech. Rep., 2005