20000 140000 MLEA 40000 MLEA 35000 120000 30000 15000 p 100000 2500 ZEB 80000 20000 MLEA 10000 60000 1500 40000 1000 UP 5000 20000 5000 ra四WIRATEONIEAMEE0 500010000 15000 20000 0 5000 10000 15000 20000 50001000015000 20000 the number of tags N the number of tags n the number of tags N Fig.5. a=95%,3=3%,6%and9%, MLEA is the estimation of the success probability g.It is known that asymptotically g follows a normal distribution: -UPE-M ZEB ~Norm( q(1-q q, (29) Because the MLE approach provides statistically consistent 2 estimate,when i is large,we can consider the contention probabilities in the later stage of the pooling process to be 0 0 5000 1000015000 20000 approximatly a constant.In addition,the number of polling the number of tags N results before stabilization of the contention probability is limited,and their impact will diminish as i becomes large Fig.6.Estimation times of the algorithms That is,they can be ignored when the asymptotic property of N;is considered.Hence,for the asymptotic property,we can let pj=pi,for1≤j≤i,and Eq.(8)becomes [3]M.Kodialam and T.Nandagopal,"Fast and Reliable Estimation Schemes in RFID Systems,"Proc.ACM MOBICOM,Los Angeles,2006. aln(L.） (1-p)N [4]M.Kodialam,T.Nandagopal,and W.Lau,"Anonymous Tracking using (30) RFID tags,"Proc.IEEE INFOCOM,2007 [5]C.Qian,H.Ngan,and Y.Liu,"Cardinality Estimation for Large-scale RFID Systems,"Proc.IEEE PerCom,2008. [6]V.Namboodiri and L.Gao,"Energy-Aware Tag Anti-Collision Protocols Therefore,the MLE N;that solves ain()0 satisfies for RFID Systems,"Proc.of IEEE PerCom,2007. [7]D.Klair,K.Chin,and R.Raad,"On the Energy Consumption of Pure and Slotted Aloha based RFID Anti-Collision Protocols,"Computer 1-p)=1-(∑Z)/i=1-g 31) Communications,2008. j=1 [8]K.Hwang.B.Vander-Zanden,and H.Taylor,"A Linear-time Probabilis- tic Counting Algorithm for Database Applications,"ACM Transactions Hence,from(29).(1-pi)Wasymptotically follows the fol- on Database Systems,vol.15,no.2.June 1990. lowing normal distribution [9]H.Vogt,"Efficient Object Identification with Passive RFID Tags,"Proc IEEE PerCom,2002. [10]J.Zhai and G.N.Wang,"An Anti-Collision Algorithm Using Two Norm (1-)N,L-1-p)1-)N (32) functioned Estimation for RFID Tags,"Proc./CCSA,2005. [11]J.Cha and J.Kim,"Novel Anti-collision Algorithms for Fast Object Identification in RFID System,"Proc.IEEE /CPADS.2005. According to the 6-method [17],if a random variable Xi [12]D.Hush and C.Wood,"Analysis of Tree Algorithm for RFID Arbitra- satisfies tion,"Proc.IEEE ISIT.1998. [13]J.Myung and W.Lee,"An adaptive memoryless tag anti-collision X:马Norm6,), (33) protocol for RFID networks,"Proc.IEEE ICC,2005 [14]H.Choi,J.Cha,and J.Kim,"Fast Wireless Anti-collision Algorithm in Ubiquitous ID System,"Proc.IEEE VTC.Sep 2004 whereand are finite constants andBmeans convergence [15]Chiu C.Tan,Bo Sheng.and Qun Li,"How to monitor for missing RFID in distribution,then we must have tags."Proc.IEEE ICDCS.June 2008. [16]Philips Semiconductors, "I-CODE Smart Label RFID Tags." htp://www.nxp.com/acrobat_download/other/identification/SL092030.pdf. g(Xi)B Norm g(0), o2Lg(0)]2 (34) Jan2004. [17]G.Casella and R.L.Berger,"Statistical Inference,"2nd edition,Duxbury for any function g such that g')exists and takes a non-zero Pres3,2002. [18]Lehmann and G.Casella,"Theory of Point Estimation,"Springer:2nd value.Based on (33)and (34),taking the logarithm of (32), edirion,1998. we have [19]"EPC Radio-Frequency Identity Protocols Class-1 Generation-2 UHF RFID Protocol for Communications at 860 MHz-960 MHz Version N:n(1-pi)~Norm NIn(1-p), 1-(1-p)) (35) 1.0.9"hmp://www.epcglobalinc.org/standards/uhfc1g2/uhfc1g2_1_0_9- (1-p) standard-20050126.pdf.EPCglobal,2005. That is, Ni~Norm (1-(1-)) (36) APPENDIX A:DISTRIBUTION AND VARIANCE OF Ni i(1-pi)Nn2(1-p) Let i be a large positive integer.Consider the sequence of Bernoulli random variables,Zj,1 <j<i,whose success Hence,we have Var(Ni) (1-(1-p)) probability is q=1-(1-p:)N.Let =(/i which i(1-p)Nn2(1-p)0 20000 40000 60000 80000 100000 120000 140000 0 5000 10000 15000 20000 number of bits transmitted the number of tags N MLEA ASEA EMLEA UPE-M ZEB 0 5000 10000 15000 20000 25000 30000 35000 40000 0 5000 10000 15000 20000 number of bits transmitted the number of tags N MLEA ASEA EMLEA UPE-M ZEB 0 5000 10000 15000 20000 0 5000 10000 15000 20000 number of bits transmitted the number of tags N MLEA ASEA EMLEA UPE-M ZEB Fig. 5. α = 95%, β = 3%, 6% and 9%. 0 2 4 6 8 10 12 0 5000 10000 15000 20000 estimation time in seconds the number of tags N MLEA ASEA EMLEA UPE-M ZEB Fig. 6. Estimation times of the algorithms [3] M. Kodialam and T. Nandagopal, “Fast and Reliable Estimation Schemes in RFID Systems,” Proc. ACM MOBICOM, Los Angeles, 2006. [4] M. Kodialam, T. Nandagopal, and W. Lau, “Anonymous Tracking using RFID tags,” Proc. IEEE INFOCOM, 2007. [5] C. Qian, H. Ngan, and Y. Liu, “Cardinality Estimation for Large-scale RFID Systems,” Proc. IEEE PerCom, 2008. [6] V. Namboodiri and L. Gao, “Energy-Aware Tag Anti-Collision Protocols for RFID Systems,” Proc. of IEEE PerCom, 2007. [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] K. Hwang, B. Vander-Zanden, and H. Taylor, “A Linear-time Probabilis￾tic Counting Algorithm for Database Applications,” ACM Transactions on Database Systems, vol. 15, no. 2, June 1990. [9] H. Vogt, “Efficient Object Identification with Passive RFID Tags,” Proc. IEEE PerCom, 2002. [10] J. Zhai and G. N. Wang, “An Anti-Collision Algorithm Using Two￾functioned Estimation for RFID Tags,” Proc. ICCSA, 2005. [11] J. Cha and J. Kim, “Novel Anti-collision Algorithms for Fast Object Identification in RFID System,” Proc. IEEE ICPADS, 2005. [12] D. Hush and C. Wood, “Analysis of Tree Algorithm for RFID Arbitra￾tion,” Proc. IEEE ISIT, 1998. [13] J. Myung and W. Lee, “An adaptive memoryless tag anti-collision protocol for RFID networks,” Proc. IEEE ICC, 2005. [14] H. Choi, J. Cha, and J. Kim, “Fast Wireless Anti-collision Algorithm in Ubiquitous ID System,” Proc. IEEE VTC, Sep 2004. [15] Chiu C. Tan, Bo Sheng, and Qun Li, “How to monitor for missing RFID tags,” Proc. IEEE ICDCS, June 2008. [16] Philips Semiconductors, “I-CODE Smart Label RFID Tags,” http://www.nxp.com/acrobat download/other/identification/SL092030.pdf, Jan 2004. [17] G. Casella and R. L. Berger, “Statistical Inference,” 2nd edition, Duxbury Press, 2002. [18] Lehmann and G. Casella, “Theory of Point Estimation,” Springer, 2nd edition, 1998. [19] “EPC Radio-Frequency Identity Protocols Class-1 Generation-2 UHF RFID Protocol for Communications at 860 MHz - 960 MHz Version 1.0.9,” http://www.epcglobalinc.org/standards/uhfc1g2/uhfc1g2 1 0 9- standard-20050126.pdf, EPCglobal, 2005. APPENDIX A: DISTRIBUTION AND VARIANCE OF Nˆ i Let i be a large positive integer. Consider the sequence of Bernoulli random variables, Zj , 1 ≤ j ≤ i, whose success probability is q = 1−(1−pi) N . Let qˆ = (Pi j=1 Zj )/i, which is the estimation of the success probability q. It is known that asymptotically qˆ follows a normal distribution: qˆ ∼ Normµ q, q(1 − q) i ¶ . (29) Because the MLE approach provides statistically consistent estimate, when i is large, we can consider the contention probabilities in the later stage of the pooling process to be approximatly a constant. In addition, the number of polling results before stabilization of the contention probability is limited, and their impact will diminish as i becomes large. That is, they can be ignored when the asymptotic property of Nˆ i is considered. Hence, for the asymptotic property, we can let pj = pi , for 1 ≤ j ≤ i, and Eq. (8) becomes ∂ ln(Li) ∂N = ln(1−pi) · (i− Xi j=1 Zj )− (1 − pi) N 1 − (1 − pi)N Xi j=1 Zj ¸ . (30) Therefore, the MLE Nˆ i that solves ∂ ln(Li) ∂N = 0 satisfies (1 − pi) Nˆi = 1 − ( X i j=1 Zj )/i = 1 − q. ˆ (31) Hence, from (29), (1 − pi) Nˆ asymptotically follows the fol￾lowing normal distribution Normµ (1 − pi) N , (1 − (1 − pi) N )(1 − pi) N i ¶ . (32) According to the δ-method [17], if a random variable Xi satisfies Xi D→ Norm(θ, σ 2 i ), (33) where θ and σ are finite constants and D→ means convergence in distribution, then we must have g(Xi) D→ Normµ g(θ), σ 2 [g 0 (θ)]2 i ¶ , (34) for any function g such that g 0 (θ) exists and takes a non-zero value. Based on (33) and (34), taking the logarithm of (32), we have Nˆi · ln(1 − pi) ∼ Normµ N ln(1 − pi), (1 − (1 − pi) N ) i(1 − pi)N ¶ . (35) That is, Nˆi ∼ Normµ N, (1 − (1 − pi) N ) i(1 − pi)N ln2 (1 − pi) ¶ . (36) Hence, we have V ar(Nˆ i) ≈ (1 − (1 − pi) N ) i(1 − pi)N ln2 (1 − pi)