[10]B.Zhen,M.Kobayashi,and M.Shimizu,"Framed ALOHA for Multiple random variable.Hence,we have RFID Object Identification,"IEICE Transactions on Communications March 2005. V(Z)=E(Z)-(E(Z1)2 [11]L.G.Roberts,"ALOHA Packet System with and without Slots and Capture,"ACM SIGCOMM Computer Communication Review,vol.5, =(1+NP)e-N(1-(1+Np)e-NP).(I8) n0.2,pp.2842,Apri1975. [12]J.Myung and W.Lee."Adaptive Splitting Protocols for RFID Tag Therefore, Collision Arbitration."In Proc.of ACM MobiHoc.May 2006. [13]N.Bhandari,A.Sahoo,and S.Iyer, ."Intelligent Query Tree (IQT) V(ne)=f(1+Np)e-Np(1-(1+Np)e-Np).(19) Protocol to Improve RFID Tag Read Efficiency,"IEEE International Conference on Information Technology (ICIT),December 2006. According to the central limit theorem,if f is large,ne [14]F.Zhou.C.Chen,D.Jin,C.Huang,and H.Min,"Evaluating and Opti- is approximately normally distributed.When foo,ne mizing Power Consumption of Anti-collision Protocols for Applications in RFID Systems,"In Proc.of ACM Interational Symposium on Low converges to the normal distribution, Power Electronics and Design (ISLPED),August 2004. [15]"Information technology automatic identification and data capture tech- ne B Norm(0,82) niques C radio frequency identification for item management air inter- face-part 6:parameters for air interface communications at 860-960 where 6 is E(ne)as given in (10).62 is V(ne)as given in MHz."Final Draft International Standard ISO 18000-6.November 2003. (19),andB means convergence in distribution. [16]S.A.Weis,S.E.Sarma.R.L.Rivest,and D.W.Engels, "Security and Privacy Aspects of Low-cost Radio Frequency Identification Sys- According to the 6-method [291,we have tems,"In Proc.of International Conference on Security in Pervasive Computing (SPC).March 2003. h(ne)B Norm(h(0),62 [h'(0)2) (20) [17]S.Zhang.S.Liew,and P.P.Lam,"Physical Layer Network Coding." In Proc.of ACM MobiCom.September 2006. for any function h(.)such that h'()exists and takes a non- [18]D.Shih,P.L.Sun,D.C.Yen,and S.M.Huang."Taxonomy and Survey zero value. of RFID Anti-collision Protocols,"Computer and Communications,vol. In Section V-C,the estimation formula is designed based 29no.11,pp.2150-2166.2006 [19]M.C.Azambuja,C.A.M.Marcon,and F.P.Hessel,"Survey on (10).which is copied below. of Standardized ISO 18000-6 RFID Anti-collision Protocols,"In Proc.of IEEE International Conference on Sensor Technologies and E(ne)=f(1-(1-p)Ns-Np(1-p)Na-1). Applications (SENSORCOMM),August 2008. 20]S.Pasupathy."Minimum Shift Keying:A Spectrally Efficient Modula- Let g(.)be the mapping function from N;to ne.The above tion."IEEE Communications Magazine,1979. equation can be rewritten as E(ne)=g(Ni).Fig.4 shows [21]J.Hamkins, "An Analytic Technique to Separate Cochannel FM Signals,"IEEE Transactions on Communications,vol.48,no.4,pp. that g(.)is a monotonic function,and hence it has a unique 543-546.Apri12000. inverse function,denoted as h(.). [22]E.Casini,R.D.Gaudenzi.and O.R.Herrero,"Contention Resolution According to Section V-C,Ni is computed from (10)by Diversity Slotted ALOHA (CRDSA):An Enhanced Random Access Schemefor Satellite Access Packet Networks,"IEEE Transactions on substituting E(ne)with the instance value of ne (obtained Wireless Communications.vol.6.no.4.pp.1408-1419.April 2007. after the ith frame). [23]S.Gollakota and D.Katabi (MIT),"ZigZag Decoding:Combating Hidden Temminals in Wireless Networks,"In Proc.of ACM SIGCOMM ne=f1-(1-ps)-Np(1-p)N-1) August 2008. [24]M.Kodialam and T.Nandagopal, "Fast and Rellable Estimation ≈f(1-e-N:p-Npe-Np). (21) Schemes in RFID Systems:"In Proc.of ACM MobiCom.September 2006. Clearly,ne =g(Ni)and Ni h(ne).Applying Ni= [25]Philips Semiconductors. "I-CODE Smart Label RFID Tags," h(nc)to (20),we have http://www.nxp.com/acrobat_download/other/identification/SL092030.pdf January 2004. :马Norm(h(0),d2(ej2). (22) [26]K.Finkenzeller,"RFID Handbook:Fundamentals and Applications in Contactless Smart Cards and Identification,"John Wiley Sons,2003 We know that h(g(N:))=N:.Differentiating both sides, [27]J.I.Capetenakis,"Tree Algorithms for Packet Broadcast Channels," IEEE Transactions on Information Theory,vol.25,no.5,pp.505-515 we have h'(g(Ni))g'(Ni)=1.Hence. 1979. 1 [28]C.Law,K.Lee,and K.Y.Siu,"Efficient Memoryless Protocol for Tag Identification,"In Prof.of International Workshop on Discrete kO)=N(Ene》=hgN》=g (23) Algaorithms and Methods for Mobile Computing and Communications Pp.75-84,August2000. Therefore,from(22),the variance of Ni is [29]G.Casella and R.L.Berger,"Statistical Inference,"2nd edition. Duxbury Press.2002. V(N)=62[h'(0)12= V(ne) g'(Na)2 APPENDIX.ESTIMATION VARIANCE,V() =+Npe-1+2Np+N32 (24) Consider an arbitrary frame with index i.Let Z;be the fN2P indicator random variable for the event that the jth slot in the frame is a collision slot.Since no slot is special,Zj,Vj E V(N (1+Np)ep-(1+2Np:+Np) (25) [1..f],follows the same distribution.They are independent fNap random variables.Because ne=we have Below we perform approximate computation to give a rough idea on how big this variance is.In SCAT or FCAT,Nip;=w, V(ne)=>v(Zj)=fV(Z1). where w is 1.414,1.817 or 2.213 for A 2,3 or 4. (17) respectively.Our simulations show that Ni reliably converges j=1 to Ni when i is large.Hence,we substitute Nip;with w in E(Zi)=1-(1-P)N-NP,(1-p)-1≈1-e-Np- (25),and the variance V()is 0.0342,0.0287 or 0.0265 Nipie-NP.E(Z)=E(Z1)because Z1 is an indicator respectively for different w values. 556[10] B. Zhen, M. Kobayashi, and M. Shimizu, “Framed ALOHA for Multiple RFID Object Identification,” IEICE Transactions on Communications, March 2005. [11] L. G. Roberts, “ALOHA Packet System with and without Slots and Capture,” ACM SIGCOMM Computer Communication Review, vol. 5, no. 2, pp. 28–42, April 1975. [12] J. Myung and W. Lee, “Adaptive Splitting Protocols for RFID Tag Collision Arbitration,” In Proc. of ACM MobiHoc, May 2006. [13] N. Bhandari, A. Sahoo, and S. Iyer, “Intelligent Query Tree (IQT) Protocol to Improve RFID Tag Read Efficiency,” IEEE International Conference on Information Technology (ICIT), December 2006. [14] F. Zhou, C. Chen, D. Jin, C. Huang, and H. Min, “Evaluating and Opti￾mizing Power Consumption of Anti-collision Protocols for Applications in RFID Systems,” In Proc. of ACM International Symposium on Low Power Electronics and Design (ISLPED), August 2004. [15] “Information technology automatic identification and data capture tech￾niques C radio frequency identification for item management air inter￾face - part 6: parameters for air interface communications at 860-960 MHz,” Final Draft International Standard ISO 18000-6, November 2003. [16] S. A. Weis, S. E. Sarma, R. L. Rivest, and D. W. Engels, “Security and Privacy Aspects of Low-cost Radio Frequency Identification Sys￾tems,” In Proc. of International Conference on Security in Pervasive Computing (SPC), March 2003. [17] S. Zhang, S. Liew, and P. P. Lam, “Physical Layer Network Coding,” In Proc. of ACM MobiCom, September 2006. [18] D. Shih, P. L. Sun, D. C. Yen, and S. M. Huang, “Taxonomy and Survey of RFID Anti-collision Protocols,” Computer and Communications, vol. 29, no. 11, pp. 2150–2166, 2006. [19] M. C. Azambuja, C. A. M. Marcon, and F. P. Hessel, “Survey of Standardized ISO 18000-6 RFID Anti-collision Protocols,” In Proc. of IEEE International Conference on Sensor Technologies and Applications (SENSORCOMM), August 2008. [20] S. Pasupathy, “Minimum Shift Keying: A Spectrally Efficient Modula￾tion,” IEEE Communications Magazine, 1979. [21] J. Hamkins, “An Analytic Technique to Separate Cochannel FM Signals,” IEEE Transactions on Communications, vol. 48, no. 4, pp. 543–546, April 2000. [22] E. Casini, R. D. Gaudenzi, and O. R. Herrero, “Contention Resolution Diversity Slotted ALOHA (CRDSA): An Enhanced Random Access Schemefor Satellite Access Packet Networks,” IEEE Transactions on Wireless Communications, vol. 6, no. 4, pp. 1408–1419, April 2007. [23] S. Gollakota and D. Katabi (MIT), “ZigZag Decoding: Combating Hidden Terminals in Wireless Networks,” In Proc. of ACM SIGCOMM, August 2008. [24] M. Kodialam and T. Nandagopal, “Fast and Reliable Estimation Schemes in RFID Systems,” In Proc. of ACM MobiCom, September 2006. [25] Philips Semiconductors, “I-CODE Smart Label RFID Tags,” http://www.nxp.com/acrobat download/other/identification/SL092030.pdf, January 2004. [26] K. Finkenzeller, “RFID Handbook: Fundamentals and Applications in Contactless Smart Cards and Identification,” John Wiley & Sons, 2003. [27] J. I. Capetenakis, “Tree Algorithms for Packet Broadcast Channels,” IEEE Transactions on Information Theory, vol. 25, no. 5, pp. 505–515, 1979. [28] C. Law, K. Lee, and K. Y. Siu, “Efficient Memoryless Protocol for Tag Identification,” In Prof. of International Workshop on Discrete Algaorithms and Methods for Mobile Computing and Communications, pp. 75–84, August 2000. [29] G. Casella and R. L. Berger, “Statistical Inference,” 2nd edition, Duxbury Press, 2002. APPENDIX. ESTIMATION VARIANCE, V ( Nˆi Ni ) Consider an arbitrary frame with index i. Let Zj be the indicator random variable for the event that the jth slot in the frame is a collision slot. Since no slot is special, Zj , ∀j ∈ [1..f], follows the same distribution. They are independent random variables. Because nc = f j=1 Zj, we have V (nc) = f j=1 V (Zj ) = fV (Z1). (17) E(Z1)=1 − (1 − pi)Ni − Nipi(1 − pi)Ni−1 ≈ 1 − e−Nipi − Nipi · e−Nipi . E(Z2 1 ) = E(Z1) because Z1 is an indicator random variable. Hence, we have V (Z1) = E(Z2 1 ) − (E(Z1))2 = (1 + Nipi)e−Nipi (1 − (1 + Nipi)e−Nipi ). (18) Therefore, V (nc) = f(1 + Nipi)e−Nipi (1 − (1 + Nipi)e−Nipi ). (19) According to the central limit theorem, if f is large, nc is approximately normally distributed. When f → ∞, nc converges to the normal distribution, nc D → Norm(θ, δ2) where θ is E(nc) as given in (10), δ2 is V (nc) as given in (19), and D → means convergence in distribution. According to the δ-method [29], we have h(nc) D → Norm(h(θ), δ2 [h (θ)]2 ) (20) for any function h(.) such that h (θ) exists and takes a non￾zero value. In Section V-C, the estimation formula is designed based on (10), which is copied below. E(nc) = f(1 − (1 − pi) Ni − Nipi(1 − pi) Ni−1). Let g(.) be the mapping function from Ni to nc. The above equation can be rewritten as E(nc) = g(Ni). Fig. 4 shows that g(.) is a monotonic function, and hence it has a unique inverse function, denoted as h(.). According to Section V-C, Nˆi is computed from (10) by substituting E(nc) with the instance value of nc (obtained after the ith frame). nc = f(1 − (1 − pi) Nˆi − Nˆipi(1 − pi) Nˆi−1) ≈ f(1 − e−Nˆipi − Nˆipie−Nˆipi ). (21) Clearly, nc = g(Nˆi) and Nˆi = h(nc). Applying Nˆi = h(nc) to (20), we have Nˆi D → Norm(h(θ), δ2 [h (θ)]2 ). (22) We know that h(g(Ni)) = Ni. Differentiating both sides, we have h (g(Ni))g (Ni)=1. Hence, h (θ) = h (E(nc)) = h (g(Ni)) = 1 g (Ni) . (23) Therefore, from (22), the variance of Nˆi is V (Nˆi) = δ2 [h (θ)]2 = V (nc) [g (Ni)]2 = (1 + Nipi)eNipi − (1 + 2Nipi + N2 i p2 i ) fN2 i p4 i , (24) V ( Nˆi Ni ) = (1 + Nipi)eNipi − (1 + 2Nipi + N2 i p2 i ) fN4 i p4 i . (25) Below we perform approximate computation to give a rough idea on how big this variance is. In SCAT or FCAT, Nˆipi = ω, where ω is 1.414, 1.817 or 2.213 for λ = 2, 3 or 4, respectively. Our simulations show that Nˆi reliably converges to Ni when i is large. Hence, we substitute Nipi with ω in (25), and the variance V ( Nˆi Ni ) is 0.0342, 0.0287 or 0.0265 respectively for different ω values. 556