Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

The anti-collision mechanism is a very important part in Radio-frequency Identification (RFID) systems. Among all the algorithms, the Framed Aloha based (FA) ones are most widely used due to simplicity and robustness. Previous works mainly focused on the tag population estimation, but determined the reading strategy based on the classical results of Random Access (RA) systems. We show that a new theory is needed for the optimization of the RFID systems as they have characteristics very different from the RA systems. In this paper, We propose a new approach to minimize the total expected reading time by choosing the most suitable frame size based on the tag population distribution. We show that the optimal strategy can be used in different applications. The mathematical analysis and computer simulation show our approach outperforms the previous optimization works in the literature.

REFERENCES

• 1: K. Finkenzeller. RFID handbook - Second Edition. JOHN WILEY&SONS, 2003.
• 2: EPCglobal. EPCglobal Class 1 Generation 2 UHF Air Interface Protocol Standard Version 1.0.9, 2005. http://www.epcglobalinc.org/.
• 3: International Organization for Standardization. Information technology - RFID for item management - Part 6: Parameters for air interface communications at 860 MHz to 960 MHz, 2004.
• 4: Philips Semiconductor. I-CODE1 Label ICs Protocol Air Interface Datasheet, January 2005.
• 5: Jihoon Myung , Wonjun Lee , Jaideep Srivastava , Timothy K. Shih, Tag-Splitting: Adaptive Collision Arbitration Protocols for RFID Tag Identification, IEEE Transactions on Parallel and Distributed Systems, v.18 n.6, p.763-775, June 2007 [doi>10.1109/TPDS.2007.1098]
• 6: K.W. Chiang, C.Q. Hua and T.S.P. Yum. Prefix-Randomized Query-Tree Protocol for RFID Systems. IEEE ICC, 2006
• 7: Petar Popovski , Frank H. P. Fitzek , Ramjee Prasad, Batch conflict resolution algorithm with progressively accurate multiplicity estimation, Proceedings of the 2004 joint workshop on Foundations of mobile computing, October 01-01, 2004, Philadelphia, PA, USA [doi>10.1145/1022630.1022636]
• 8: J.Park, M.Y. Chung and T.J. Lee. Identification of RFID Tags in Framed-Slotted ALOHA with Tag Estimation and Binary Splitting, Communications and Electronics, 2006
• 9: J. Mosely, P.A. Humblet. A Class of Efficient Contention Resolution Algorithms for Multiple Access Channels. IEEE Transactions of communications, Vol. Com-33, No., Feb. 1985.
• 10: F.C.Schoute. Dynamic Frame Length ALOHA. IEEE Transactions on Communications, COM-31(4):565--568, Apr 1983.
• 11: Harald Vogt, Efficient Object Identification with Passive RFID Tags, Proceedings of the First International Conference on Pervasive Computing, p.98-113, August 26-28, 2002
• 12: Christian Floerkemeier, Transmission control scheme for fast RFID object identification, Proceedings of the 4th annual IEEE international conference on Pervasive Computing and Communications Workshops, p.457, March 13-17, 2006 [doi>10.1109/PERCOMW.2006.136]
• 13: B. Zhen, M. Kobayashi, M. Shimizu. Framed Aloha for Multiple RFID objects Identification. IEICE Transactions of comminication. Vol.E88-B, No.3, March 2005
• 14: Michael Buettner , David Wetherall, An empirical study of UHF RFID performance, Proceedings of the 14th ACM international conference on Mobile computing and networking, September 14-19, 2008, San Francisco, California, USA [doi>10.1145/1409944.1409970]
• 15: C. Floerkemeier. Bayesian Transmission strategy for Framed ALOHA Based RFID Protocols. IEEE International Conference on RFID, Gaylord Texan Resort, Grapevine, TX, USA, March, 2007
• 16: Murali Kodialam , Thyaga Nandagopal, Fast and reliable estimation schemes in RFID systems, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161126]
• 17: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 18: W. Feller. An Introduction to Probability Theory and Its Applications, Second edtion, Vol I, John Wiley.
• 19: Sheldon M. Ross, Introduction to Probability Models, Ninth Edition, Academic Press, Inc., Orlando, FL, 2006

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
RFID, algorithm, framed aloha, optimization