Eror probablity 1% Condderce interval E=5% FNEB PET- Z0E-4 0 10 10% 20% % 10 Error rate 5% 10 15% 20 1% 5% 10% 15 Fig.12.Accuracy comparisons under varying error rates Confidence interval E Error probabilityδ (a) (b) REFERENCES Fig.11.Memory overhead in storing the random numbers:(a)with different [1]"Alien Technology".http://www.alientechnology.com confidence interval e,and the same error probability 6 1%;(b)with [2]"EPCglobal CIG2".http://www.epcglobalinc.org/standards/uhfc1g2 different error probability 6,and the same confidence interval e=5%. [3 "Gen 2 RFID Tools",https://www.cgran.org/wiki/Gen2 [4 "Ettus Research",http://www.ettus.com [5]"WISP Platform".http://wisp.wikispaces.com interval [47500,52500]in ZOE,the existing approaches can [6]M.Buettner and D.Wetherall,"An Empirical Study of UHF RFID only guarantee less than 80%results within such an interval. Performance".in ACM MobiCom,2008. We compare the computation and memory overhead at [7]J.I.Capetanakis,"Tree algorithms for packet broadcast channels",IEEE Trans.on Information Theory,vol.25,issue 5,pp.505-515,1979. RFID tags.We examine the memory overhead and compare [8]S.Chen,M.Zhang.and B.Xiao,"Efficient Information Collection ZOE with recent protocols in Figure 11.We fix the error Protocols for Sensor-augmented RFID Networks",in IEEE INFOCOM. probability 6=1%and vary the confidence interval from 5% 2011. [9]K.Finkenzeller,"RFID Handbook:Radio-Frequency Identification Fun to 20%in Figure 11(a).We vary the error probability 6 from damentals and Applications",John Wiley Sons,2000. 1%to 15%with fixed confidence interval s=5%in Figure [10]G.R.Grimmett.D.R.Stirzaker,"Probability and Random Processes. 11(b).According to the statistics,we observe that ZOE and 3nd edition",Oxford Universiry Press,2001. [11]H.Han,B.Sheng,C.C.Tan,Q.Li,W.Mao.and S.Lu."Counting PET consume constant small storage,and outperforms FNEB RFID Tags Efficiently and Anonymously",in IEEE INFOCOM,2010. and LoF which require much larger memory cost. [12]M.Kodialam and T.Nandagopal,"Fast and reliable estimation schemes in RFID systems",in ACM MobiCom.2006. Till now we focus on the performance comparison over ideal [13]M.Kodialam,T.Nandagopal,and W.C.Lau,"Anonymous Tracking channels.In Figure 12,we examine the estimation accuracy using RFID tags",in IEEE INFOCOM,2007. of ZOE compared with recent approaches with different error [14]T.Li,S.Chen,and Y.Ling,"Identifying the Missing Tags in a Large rates.We vary the error rate from 5%to 30%,and the actual RFID System",in ACM MobiHoc,2010. [15]L.M.Ni,Y.Liu,Y.C.Lau,and A.Patil,"LANDMARC:Indoo tag cardinality is 50000.According to Figure 12,we find that Location Sensing Using Active RFID",ACM Wireless Nerworks,vol. the estimation accuracies of LoF and PET are significantly 10,issue6,pp.701-710,2004. biased from the actual value.Though FNEB is more robust [16]C.Qian,H.Ngan,and Y.Liu,"Cardinality Estimation for Large-scale RFID Systems".in /EEE PerCom.2008. than LoF and PET,it still fails to provide an unbiased and [17]C.Qian,Y.Liu,H.-L.Ngan,and L.M.Ni,"ASAP:Scalable Identifi- accurate estimation.On the other hand.ZOE with EEA resists cation and Counting for Contactless RFID Systems".in /EEE /CDCS. 2010. the various error rates and provides accurate estimation results [18]Y.Qiao,S.Chen,T.Li,and S.Chen,"Energy-efficient Polling Protocols even when the error rate reaches 30%. in RFID Systems",in ACM MobiHoc,2011. [19]T.F.La Porta,G.Maselli,and C.Petrioli,"Anticollision Protocols for VII.CONCLUSION Single-Reader RFID Systems:Temporal Analysis and Optimization" IEEE Trans.on Mobile Computing,vol.10.issue pp.267-279.2011. (20]L.G.Roberts,"Aloha Packet System with and without Slots and In this paper,we propose a cardinality estimation protocol Capture".ACM SIGCOMM Computer Communication Review.vol.5. based on Zero-One Estimator (ZOE)which improves the issue2,Pp.28-42,1975. estimation time efficiency in meeting arbitrary accuracy re- [21]J.R.Smith,A.P.Sample,P.S.Powledge.S.Roy,and A.Mamishev. "A wirelessly-powered platform for sensing and computation",in ACM quirement.ZOE only requires one-bit response from the RFID Ubicomp,2006. tags per estimation round while prior works require several [22]C.C.Tan,B.Sheng,and Q.Li."How to Monitor for Missing RFID time slots.We also enhance the robustness of cardinality Tags",in IEEE ICDCS.2008. estimation over noisy channels.We implement a prototype [23]R.Want,"An Introduction to RFID Technology",IEEE Pervasive Computing,vol.5,issue 1,pp.25-33,2005. system based on the GNURadio/USRP platform in concert [24]L.Yang.J.Han,Y.Qi,C.Wang.T.Gu,and Y.Liu,"Season:Shelving with the WISP RFID tags.ZOE only requires slight updates Interference and Joint Identification in Large-scale RFID Systems",in IEEE INFOCOM.2011. to the EPCglobal C1G2 standard.We also conduct extensive (25]R.Zhang.Y.Liu.Y.Zhang,and J.Sun,"Fast Identification of the simulations to evaluate the performance of ZOE in large- Missing Tags in a Large RFID System".in IEEE SECON,2011. scale settings.The experiment results demonstrate that ZOE [26]Y.Zhang.L.T.Yang,and J.Chen "RFID and Sensor Networks:Archi- tectures,Protocols,Security and Integrations".Auerbach Publications, outperforms the most recent cardinality estimation protocols. 2010. [27]Y.Zheng.M.Li,and C.Qian,"PET:Probabilistic Estimating Tree for ACKNOWLEDGMENT Large-Scale RFID Estimation",in IEEE ICDCS,2011. [28]Y.Zheng and M.Li,"Fast Tag Searching Protocol for Large-Scale RFID Systems",in IEEE /CNP,2011. We acknowledge the support from NTU Nanyang As- (29]F.Zhou,C.Chen,D.Jin,C.Huang,and H.Min,"Evaluating and sistant Professorship (NAP)grant M4080738.020,Microsoft optimizing power consumption of anti-collision protocols for applications research grant FY12-RES-THEME-001,and NSFC grant No. in rfid systems",in /SLPED.2004. 61272456.100 101 102 103 104 Total numbers (in log 5% 10% 15% 20% scale) Confidence interval ε Error probability δ=1% FNEB LoF PET ZOE (a) 100 101 102 103 104 Total numbers (in log 1% 5% 10% 15% scale) Error probability δ Confidence interval ε=5% FNEB LoF PET ZOE (b) Fig. 11. Memory overhead in storing the random numbers: (a) with different confidence interval ε, and the same error probability δ = 1%; (b) with different error probability δ, and the same confidence interval ε = 5%. interval [47500, 52500] in ZOE, the existing approaches can only guarantee less than 80% results within such an interval. We compare the computation and memory overhead at RFID tags. We examine the memory overhead and compare ZOE with recent protocols in Figure 11. We fix the error probability δ = 1% and vary the confidence interval ε from 5% to 20% in Figure 11(a). We vary the error probability δ from 1% to 15% with fixed confidence interval ε = 5% in Figure 11(b). According to the statistics, we observe that ZOE and PET consume constant small storage, and outperforms FNEB and LoF which require much larger memory cost. Till now we focus on the performance comparison over ideal channels. In Figure 12, we examine the estimation accuracy of ZOE compared with recent approaches with different error rates. We vary the error rate from 5% to 30%, and the actual tag cardinality is 50000. According to Figure 12, we find that the estimation accuracies of LoF and PET are significantly biased from the actual value. Though FNEB is more robust than LoF and PET, it still fails to provide an unbiased and accurate estimation. On the other hand, ZOE with EEA resists the various error rates and provides accurate estimation results even when the error rate reaches 30%. VII. CONCLUSION In this paper, we propose a cardinality estimation protocol based on Zero-One Estimator (ZOE) which improves the estimation time efficiency in meeting arbitrary accuracy re￾quirement. ZOE only requires one-bit response from the RFID tags per estimation round while prior works require several time slots. We also enhance the robustness of cardinality estimation over noisy channels. We implement a prototype system based on the GNURadio/USRP platform in concert with the WISP RFID tags. ZOE only requires slight updates to the EPCglobal C1G2 standard. We also conduct extensive simulations to evaluate the performance of ZOE in large￾scale settings. The experiment results demonstrate that ZOE outperforms the most recent cardinality estimation protocols. ACKNOWLEDGMENT We acknowledge the support from NTU Nanyang As￾sistant Professorship (NAP) grant M4080738.020, Microsoft research grant FY12-RES-THEME-001, and NSFC grant No. 61272456. 0 0.5 1 5% 10% 20% 30% Accuracy Error rate FNEB LoF PET ZOE Fig. 12. Accuracy comparisons under varying error rates. REFERENCES [1] “Alien Technology”, http://www.alientechnology.com [2] “EPCglobal ClG2”, http://www.epcglobalinc.org/standards/uhfc1g2 [3] “Gen 2 RFID Tools”, https://www.cgran.org/wiki/Gen2 [4] “Ettus Research”, http://www.ettus.com [5] “WISP Platform”, http://wisp.wikispaces.com [6] M. Buettner and D. Wetherall, “An Empirical Study of UHF RFID Performance”, in ACM MobiCom, 2008. [7] J. I. Capetanakis, “Tree algorithms for packet broadcast channels”, IEEE Trans. on Information Theory, vol. 25, issue 5, pp. 505-515, 1979. [8] S. Chen, M. Zhang, and B. Xiao, “Efficient Information Collection Protocols for Sensor-augmented RFID Networks”, in IEEE INFOCOM, 2011. [9] K. Finkenzeller, “RFID Handbook: Radio-Frequency Identification Fun￾damentals and Applications”, John Wiley & Sons, 2000. [10] G. R. Grimmett, D. R. Stirzaker, “Probability and Random Processes, 3nd edition”, Oxford University Press, 2001. [11] H. Han, B. Sheng, C. C. Tan, Q. Li, W. Mao, and S. Lu, “Counting RFID Tags Efficiently and Anonymously”, in IEEE INFOCOM, 2010. [12] M. Kodialam and T. Nandagopal, “Fast and reliable estimation schemes in RFID systems”, in ACM MobiCom, 2006. [13] M. Kodialam, T. Nandagopal, and W. C. Lau, “Anonymous Tracking using RFID tags”, in IEEE INFOCOM, 2007. [14] T. Li, S. Chen, and Y. Ling, “Identifying the Missing Tags in a Large RFID System”, in ACM MobiHoc, 2010. [15] L. M. Ni, Y. Liu, Y. C. Lau, and A. Patil, “LANDMARC: Indoor Location Sensing Using Active RFID”, ACM Wireless Networks, vol. 10, issue 6, pp. 701-710, 2004. [16] C. Qian, H. Ngan, and Y. Liu, “Cardinality Estimation for Large-scale RFID Systems”, in IEEE PerCom, 2008. [17] C. Qian, Y. Liu, H.-L. Ngan, and L. M. Ni, “ASAP: Scalable Identifi- cation and Counting for Contactless RFID Systems”, in IEEE ICDCS, 2010. [18] Y. Qiao, S. Chen, T. Li, and S. Chen, “Energy-efficient Polling Protocols in RFID Systems”, in ACM MobiHoc, 2011. [19] T. F. La Porta, G. Maselli, and C. Petrioli, “Anticollision Protocols for Single-Reader RFID Systems: Temporal Analysis and Optimization”, IEEE Trans. on Mobile Computing, vol. 10, issue 2, pp. 267-279, 2011. [20] L. G. Roberts, “Aloha Packet System with and without Slots and Capture”, ACM SIGCOMM Computer Communication Review, vol. 5, issue 2, pp. 28-42, 1975. [21] J. R. Smith, A. P. Sample, P. S. Powledge, S. Roy, and A. Mamishev, “A wirelessly-powered platform for sensing and computation”, in ACM Ubicomp, 2006. [22] C. C. Tan, B. Sheng, and Q. Li, “How to Monitor for Missing RFID Tags”, in IEEE ICDCS, 2008. [23] R. Want, “An Introduction to RFID Technology”, IEEE Pervasive Computing, vol. 5, issue 1, pp. 25- 33, 2005. [24] L. Yang, J. Han, Y. Qi, C. Wang, T. Gu, and Y. Liu, “Season: Shelving Interference and Joint Identification in Large-scale RFID Systems”, in IEEE INFOCOM, 2011. [25] R. Zhang, Y. Liu, Y. Zhang, and J. Sun, “Fast Identification of the Missing Tags in a Large RFID System”, in IEEE SECON, 2011. [26] Y. Zhang, L. T. Yang, and J. Chen “RFID and Sensor Networks: Archi￾tectures, Protocols, Security and Integrations”, Auerbach Publications, 2010. [27] Y. Zheng, M. Li, and C. Qian, “PET: Probabilistic Estimating Tree for Large-Scale RFID Estimation”, in IEEE ICDCS, 2011. [28] Y. Zheng and M. Li, “Fast Tag Searching Protocol for Large-Scale RFID Systems”, in IEEE ICNP, 2011. [29] 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