This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2010 proceedings This paper was presented as part of the main Technical Program at IEEE INFOCOM 2010. 400 350 -Controlled conditio -Noisy condition 350 300 300 250 250 200 200 0.7 150 150 一DP -AD 100 0.6 050 1 2 3 00 20 304050 60 70 Distance The number of tags (a)Noisy conditions.(b)Controlled conditions. (a)pi(r)and pt(r) (b)Required number of slots for various strategies (c)Required number of slots for different propaga- to select frame sizes tion situations 90 250 80叶 Actual number of tags 025 70 -Estimated number of tags 02 60 0.15 50 150 40 30 % C=30 20 0.05 50 -C=50 10 0 10203040,50 607080 5 10 15 20 1.5 253 3.5 The number of tags Read rounds (d)Normalized throughput for various initial frame (e)Simulation results for tag size estimation. (f)Maximum number of tags which can be identi- sizes fied for various conveyor speeds. Fig.4.Simulation results exceeds nmaz(v),then conventionally the reader cannot finish [6]S.Lee,S.Joo,and C.Lee,"An enhanced dynamic framed slotted aloha identifying all the tags in time. algorithm for rfid tag identification,"in Proc.of MobiOuitous,2005. [7]J.Myung.W.Lee,and S.Jaideep."Adaptive binary splitting for efficient VIII.CONCLUSION rfid tag anti-collision,"IEEE Communications Letters,vol.10,no.3,pp 144-146.2006. In this paper we consider how to efficiently identify tags on [8]L.Pan and H.Wu,"Smart Trend-Traversal:A Low Delay and Energy the moving conveyor.Considering conditions like the path loss Tag Arbitration Protocol for Large RFID Systems,"in Proc.of INFO- and multi-path effect in realistic settings,we first propose a COM.mini-conference,2009. [9]F.Schoute,"Dynamic frame length aloha,"IEEE Transactions on probabilistic model for RFID tag identification.Based on this Communications,vol.31,no.4,pp.565-568,1983. model,we propose efficient solutions to identify moving RFID [10]C.Floerkemeier,"Bayesian transmission strategy for framed aloha based rfid protocols,"in Proc.of RFID,2007. tags,according to the fixed-path mobility on the conveyor. [11]H.Vogt."Efficient object identification with passive rfid tags,"in Proc. of Pervasive,2002. ACKNOWLEDGMENTS [12]M.Kodialam and T.Nandagopal,"Fast and reliable estimation schemes This project was supported in part by US National Science in rfid systems."in Proc.of MobiCom.2006. Foundation grants CNS-0721443,CNS-0831904,CAREER [13]C.Qian,H.-L.Ngan,and Y.Liu,"Cardinality estimation for large-scale rfid systems,"in Proc.of PerCom,2008. Award CNS-0747108,the China 973 project(2009CB320705. [14]B.Sheng.C.C.Tan,Q.Li,and W.Mao."Finding popular categoried 2006CB303000),the China NSF grant(60673154,60873026, for RFID tags,"in Proc.of ACM Mobihoc,2008. 90718031.60721002.60573106.60573132.60825205) [15]C.C.Tan,B.Sheng,and Q.Li,"How to monitor for missing RFID tags."in Proc.of IEEE ICDCS.2008. [16]Y.Kawakita and J.Mitsugi,"Anti-collision performance of gen2 air REFERENCES protocol in random error communication link,"in Proc.of SAINT-W. [1]Y.Maguire and R.Pappu,"An optimal g-algorithm for the iso 18000-6c 2006. rfid protocol,"IEEE Transactions on Automation Science and Engineer- [17]Z.Ren,C.C.Tan,D.Wang,and Q.Li,"Experimental study on mobile img,ol.6,n0.1,pp.16-24,2009. RFID performance,"in Proc.of WASA,2009. [2]B.Zhen,M.Kobayashi,and M.Shimuzu,"Framed aloha for multiple [18]S.R.Jeffery,M.Garofalakis,and M.J.Franklin."Adaptive cleaning rfid objects identification,"IEICE Transactions on Communications,vol. for rfid data streams,"in Proc.of VLDB,2006. E80-B,no.3,Pp.991-999,2005. [19]"Epcglobal.epc radio-frequency identity protocols class-1 generation-2 [3]M.Buettner and D.Wetherall,"An empirical study of uhf rfid perfor- uhf rfid protocol for communications at 860 mhz-960mhz version 1.2.0," mance,"in Proc.of MobiCom,2008. Tech.Rep.,2008. [4]K.M.Ramakrishnan and D.D.Deavours,"Performance benchmarks for [20]H.Lehpamer,RFID Design Principles.Artech House,Incorporate, passive uhf rfid tags,"in Proc.of the 13th Gl/ITG Conference on Mea- 2008. surement,Modeling,and Evaluation of Computer and Communication [21]W.Chen,"An accurate tag estimate method for improving the perfor- Sy3s1es,2006. mance of an rfid anticollision algorithm based on dynamic frame length [5]S.R.Aroor and D.D.Deavours,"Evaluation of the state of passive uhf aloha,"IEEE Transactions on Automation Science and Engineering, rfid:An experimental approach,"IEEE Systems Journal,vol.1,no.2. vol.6,no.1,Pp.9-15.2009. Pp.168-176,2007. Authorized licensed use limited to:Nanjing University.Downloaded on July 11,2010 at 07:37:18 UTC from IEEE Xplore.Restrictions apply.0 1 2 3 4 5 6 0.5 0.6 0.7 0.8 0.9 1 Distance Propagation probability Controlled condition Noisy condition (a) pi(r) and pt(r) 10 20 30 40 50 60 70 0 50 100 150 200 250 300 350 400 The number of tags Required number of slots DP AD f=n f=32 (b) Required number of slots for various strategies to select frame sizes 1 2 0 50 100 150 200 250 300 350 (a)Noisy conditions.(b)Controlled conditions. Required number of slots (c) Required number of slots for different propaga￾tion situations 10 20 30 40 50 60 70 80 0 0.05 0.1 0.15 0.2 0.25 The number of tags Throughput C=10 C=30 C=50 (d) Normalized throughput for various initial frame sizes 5 10 15 20 0 10 20 30 40 50 60 70 80 90 Read rounds Number of tags Actual number of tags Estimated number of tags (e) Simulation results for tag size estimation. 1 1.5 2 2.5 3 3.5 4 0 50 100 150 200 250 Speed of the conveyor: v Maximum number of tags to be read (f) Maximum number of tags which can be identi- fied for various conveyor speeds. Fig. 4. Simulation results exceeds nmax(v), then conventionally the reader cannot finish identifying all the tags in time. VIII. CONCLUSION In this paper we consider how to efficiently identify tags on the moving conveyor. Considering conditions like the path loss and multi-path effect in realistic settings, we first propose a probabilistic model for RFID tag identification. Based on this model, we propose efficient solutions to identify moving RFID tags, according to the fixed-path mobility on the conveyor. ACKNOWLEDGMENTS This project was supported in part by US National Science Foundation grants CNS-0721443, CNS-0831904, CAREER Award CNS-0747108, the China 973 project (2009CB320705, 2006CB303000), the China NSF grant (60673154, 60873026, 90718031, 60721002, 60573106, 60573132, 60825205). REFERENCES [1] Y. Maguire and R. Pappu, “An optimal q-algorithm for the iso 18000-6c rfid protocol,” IEEE Transactions on Automation Science and Engineer￾ing, vol. 6, no. 1, pp. 16–24, 2009. [2] B. Zhen, M. Kobayashi, and M. Shimuzu, “Framed aloha for multiple rfid objects identification,” IEICE Transactions on Communications, vol. E80-B, no. 3, pp. 991–999, 2005. [3] M. Buettner and D. Wetherall, “An empirical study of uhf rfid perfor￾mance,” in Proc. of MobiCom, 2008. [4] K. M. Ramakrishnan and D. D. Deavours, “Performance benchmarks for passive uhf rfid tags,” in Proc. of the 13th GI/ITG Conference on Mea￾surement, Modeling, and Evaluation of Computer and Communication Systems, 2006. [5] S. R. Aroor and D. D. Deavours, “Evaluation of the state of passive uhf rfid: An experimental approach,” IEEE Systems Journal, vol. 1, no. 2, pp. 168–176, 2007. [6] S. Lee, S. Joo, and C. Lee, “An enhanced dynamic framed slotted aloha algorithm for rfid tag identification,” in Proc. of MobiQuitous, 2005. [7] 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. [8] L. Pan and H. Wu, “Smart Trend-Traversal: A Low Delay and Energy Tag Arbitration Protocol for Large RFID Systems,” in Proc. of INFO￾COM, mini-conference, 2009. [9] F. Schoute, “Dynamic frame length aloha,” IEEE Transactions on Communications, vol. 31, no. 4, pp. 565–568, 1983. [10] C. Floerkemeier, “Bayesian transmission strategy for framed aloha based rfid protocols,” in Proc. of RFID, 2007. [11] H. Vogt, “Efficient object identification with passive rfid tags,” in Proc. of Pervasive, 2002. [12] M. Kodialam and T. Nandagopal, “Fast and reliable estimation schemes in rfid systems,” in Proc. of MobiCom, 2006. [13] C. Qian, H.-L. Ngan, and Y. Liu, “Cardinality estimation for large-scale rfid systems,” in Proc. of PerCom, 2008. [14] B. Sheng, C. C. Tan, Q. Li, and W. Mao, “Finding popular categoried for RFID tags,” in Proc. of ACM Mobihoc, 2008. [15] C. C. Tan, B. Sheng, and Q. Li, “How to monitor for missing RFID tags,” in Proc. of IEEE ICDCS, 2008. [16] Y. Kawakita and J. Mitsugi, “Anti-collision performance of gen2 air protocol in random error communication link,” in Proc. of SAINT-W, 2006. [17] Z. Ren, C. C. Tan, D. Wang, and Q. Li, “Experimental study on mobile RFID performance,” in Proc. of WASA, 2009. [18] S. R. Jeffery, M. Garofalakis, and M. J. Franklin, “Adaptive cleaning for rfid data streams,” in Proc. of VLDB, 2006. [19] “Epcglobal. epc radio-frequency identity protocols class-1 generation-2 uhf rfid protocol for communications at 860 mhz-960mhz version 1.2.0,” Tech. Rep., 2008. [20] H. Lehpamer, RFID Design Principles. Artech House, Incorporate, 2008. [21] W. Chen, “An accurate tag estimate method for improving the perfor￾mance of an rfid anticollision algorithm based on dynamic frame length aloha,” IEEE Transactions on Automation Science and Engineering, vol. 6, no. 1, pp. 9–15, 2009. This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2010 proceedings This paper was presented as part of the main Technical Program at IEEE INFOCOM 2010. Authorized licensed use limited to: Nanjing University. Downloaded on July 11,2010 at 07:37:18 UTC from IEEE Xplore. Restrictions apply