Murali Kodialam
ABSTRACT
RFID tags are being used in many diverse applications in increasingly large numbers. These capabilities of these tags span from very dumb passive tags to smart active tags, with the cost of these tags correspondingly ranging from a few pennies to many dollars. One of the common problems that arise in any RFID deployment is the problem of quick estimation of the number of tags in the field up to a desired level of accuracy. Prior work in this area has focused on the identification of tags, which needs more time, and is unsuitable for many situations, especially where the tag set is dense. We take a different, more practical approach, and provide very fast and reliable estimation mechanisms. In particular, we analyze our estimation schemes and show that the time needed to estimate the number of tags in the system for a given accuracy is much better than schemes presented in related work. We show that one can estimate the cardinality of tag-sets of any size in near-constant time, for a given accuracy of estimation.
- "RFID:Wikipedia entry", http://en.wikipedia.org/wiki/RFID 2006.Google Scholar
- K. Finkenzeller, "RFID handbook: Radio frequency identification fundamentals and applications", John Wiley & Sons 2000.Google Scholar
- EPCglobal, "EPC Radio-Frequency Identity Protocols Class-1 Generation-2 UHF RFID Protocol for Communications at 860 MHz .960 MHz Version 1.0.9 ", 2005.Google Scholar
- ISO/IEC 15963, "Information technology. Radio frequency identification for item management. Unique identification for RF tags", 2004.Google Scholar
- L. Burdet, "RFID multiple access methods", Technical Report ETH Zurich, 2004.Google Scholar
- R. Want, "An introduction to RFID technology", IEEE Pervasive Computing Jan. 2006. Google ScholarDigital Library
- T. Hassan and S. Chatterjee, "A taxonomy for RFID", Hawaii International Conference on System Sciences Kauai, HI, Jan 2006. Google ScholarDigital Library
- RFID Journal, http://www.rfidjournal.com 2006.Google Scholar
- Philips Semiconductors, "I-CODE Smart Label RFID Tags", http://www.semiconductors.philips.com/acrobat download/other/identification/SL092030.pdfGoogle Scholar
- Feller, W., "An Introduction to Probability Theory and Its Applications", Vol 1 John Wiley, 1968.Google Scholar
- K. Whang, B. Vander-Zanden, and H. Taylor, "A Linear Time Probabilistic Counting Algorithm for Database Applications", ACM Transactions on Database Systems June, 1990. Google ScholarDigital Library
- Rao, C. R., "Linear Statistical Inference and its Applications",Google Scholar
- M. Kodialam and T. Nandagopal, "Fast Estimation Schemes in RFID Systems", Bell Labs Technical Report March 2006. Available at http://www.bell-labs.com/user/thyaga.Google Scholar
- K. S. Leong, M. L. Ng and P. H. Cole, "Synchronization of RFID readers for dense RFID reader environments", International Symposium on Applications and Internet Workshops Phoenix, AZ. Jan 2006. Google ScholarDigital Library
- S. Chen and V. Thomas, "Optimization of inductive RFID technology", IEEE International Symposium on Electronics and Environment 2001.Google ScholarCross Ref
- D. Engels and S. Sarma, "The reader collision problem", IEEE Systems, Man and Cybernetics 2002.Google Scholar
- J. Waldrop, D. Engels and S. Sarma, "Colorwave: An anticollision algorithm for the reader collision problem", IEEE ICC 2002.Google Scholar
- H. Vogt, "Efficient Object Identification with Passive RFID Tags", Lecture Notes in Computer Science Springer-Verlag, vol. 2414, 2002. Google ScholarDigital Library
- P. Hernandez, J. D. Sandoval, F. Puente and F. Perez, "Mathematical Model for a Multi-read Anti-collision Protocol", IEEE Pacific Rim Conference on Communications, Computers and Signal Processing 2001.Google Scholar
- B. Zhen, M. Kobayashi and M. Shimizu, "To read transmitter-only RFID tags with confidence", IEEE PIMRC '04 Barcelona, Spain. Sept 2004.Google Scholar
- H. Choi, J. R. Cha and J. H. Kim, "Fastwireless anti-collision algorithm in ubiquitous ID system", IEEE VTC '04 Los Angeles, CA. Sep 2004.Google Scholar
- J. R. Cha and J. H. Kim, "Novel anti-collision algorithms for fast object identification in RFID system", IEEE International Conference on Parallel and Distributed Systems 2005. Google ScholarDigital Library
- C. Floerkemeier and M. Wille, "Comparison of Transmission Schemes for Framed ALOHA based RFID Protocols", Workshop on RFID and Extended Network Deployment of Technologies and Applications Phoenix, AZ. Jan 2006.Google ScholarDigital Library
- C. Floerkemeier, "Transmission control scheme for fast RFID object identification", IEEE PerCom Workshop on Pervasive Wireless Networking Mar 2006.Google ScholarDigital Library
- F. C. Schoute, "Dynamic framed length ALOHA", IEEE Transactions on Communications vol.31(4), Apr 1983.Google ScholarCross Ref
- A. Micic, A. Nayak, D. Simplot-Ryl and I. Stojmenovic, "A hybrid randomized protocol for RFID tag identification", IEEE International Workshop on Next Generation Wireless Networks Goa, India. 2005.Google Scholar
- I. Cidon and M. Sidi, "Conflict multiplicity estimation and batch resolution algorithms", IEEE Transactions on Information Theory vol. 34(1), Jan 1988. Google ScholarDigital Library
- B. Zhen, M. Kobayashi and M. Shimizu, "Framed ALOHA for multiple RFID objects identification", IEICE Transactions on Communications vol. E88-B(3), Mar 2005.Google Scholar
- P. F. Greenberg and R. E. Ladner, "Estimating the multiplicities of conflict to speed their resolution in multiple access channels", J. ACM vol. 34(2), Apr. 1987. Google ScholarDigital Library
- P. Popovski, F. H. P. Fitzek, and R. Prasad, "Batch Conflict Resolution Algorithm with Progressively Accurate Multiplicity Estimation", ACM DIALM-POMC Workshop Philadephia, PA. Oct. 2004. Google ScholarDigital Library
- K. Cho, H. Shin and J. Lee, "Performance analysis of HIPERLAN channel access control protocol", IEICE Transactions on Communications vol. E85-B(10), Oct 2002.Google Scholar
- Y. C. Tay, K. Jamieson and H. Balakrishnan, "Collision-minimizing CSMA and its applications to wireless sensor networks", IEEE Journal on Selected Areas in Communications vol.22(6), Aug 2004. Google ScholarDigital Library
- J. Wieselthier, A. Ephremides and L. Michaels, "An exact analysis and performance evaluation of framed ALOHA with capture", IEEE Transactions on Communications vol.(37(2), Feb 1989.Google ScholarCross Ref
- S. Lee, S. Joo and C. Lee, "An enhanced dynamic framed slotted ALOHA algorithm for RFID tag identification", IEEE MobiQuitous 2005. Google ScholarDigital Library
- F. Cali, M. Conti and E. Gregori, "Dynamic tuning of the IEEE 802.11 protocol to achieve a theoretical throughput limit", IEEE/ACM Transactions on Networking vol. 8(6), Dec 2000. Google ScholarDigital Library
- K. Jamieson, H. Balakrishnan, and Y. C. Tay, "Sift: a MAC Protocol for Event-Driven Wireless Sensor Networks", Proceedings of the Third European Workshop on Wireless Sensor Networks, Feb 2006. Google ScholarDigital Library
- M. Nanjundaiah and V. Chaudhary, "Improvement to the anticollision protocol specification for 900 MHz class 0 RFID tag", International Conference on Advanced Information Networking and Applications 2005. Google ScholarDigital Library
- 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", ACM ISLPED '04 Aug 2004. Google ScholarDigital Library
- D. Hush and C. Wood, "Analysis of tree algorithms for RFID arbitration", IEEE Symposium on Information Theory Cambridge, MA. Aug 1998.Google ScholarCross Ref
- L. Bolotnyy and G. Robins, "Randomized pseudo-random function tree walking algorithm for secure radio-frequency identification", IEEE Workshop on Automatic Identification Advanced Technologies Oct 2005. Google ScholarDigital Library
- J. Kim, W. Lee, J. Yu, E. KimandC. Lee, "Effect of localized optimal clustering for reader anti-collision in RFID networks: fairness aspects to the readers", IEEE ICCCN 2005.Google Scholar
- I. Chlamtac, C. Petrioli and J. Redi, "Energy conserving access protocols for identification networks", IEEE/ACM Transaction on Networking vol. 7(1), Feb 1999. Google ScholarDigital Library
- C. Law, K. Lee, and K. Siu, "Efficient Memoryless Protocol for Tag Identification", ACM DIAL-M Workshop Aug 2000. Google ScholarDigital Library
- J. Myung and W. Lee, "An Adaptive Memoryless Tag Anti-Collision Protocol for RFID Networks", IEEE ICC 2005.Google Scholar
- A. Krohn, M. Beigl and S. Wendhack, "SDJS: Efficient Statistics in Wireless Networks", IEEE ICNP Berlin, Germany, Oct 2004. Google ScholarDigital Library
Index Terms
- Fast and reliable estimation schemes in RFID systems
Recommendations
Every bit counts: fast and scalable RFID estimation
Mobicom '12: Proceedings of the 18th annual international conference on Mobile computing and networkingRadio Frequency Identification (RFID) systems have been widely deployed for various applications such as object tracking, 3D positioning, supply chain management, inventory control, and access control. This paper concerns the fundamental problem of ...
A fast zero estimation scheme for RFID systems
Tag estimation is one of the key technologies in radio frequency identification (RFID) systems. Quick and accurate tag estimation is very important to improve tag identification efficiency. In this paper, we propose a scalable and reliable zero ...
Fast and accurate estimation of RFID tags
Radio frequency identification (RFID) systems have been widely deployed for various applications such as object tracking, 3-D positioning, supply chain management, inventory control, and access control. This paper concerns the fundamental problem of ...
Comments