IJCNS  Vol.2 No.1 , February 2009
Synchronous Dynamic Adjusting: An Anti-Collision Algorithm for an RF-UCard System
Abstract: An RF-UCard system is a contactless smartcard system with multiple chip operating systems and multiple applications. A multi-card collision occurs when more than one card within the reader’s read field and thus lowers the efficiency of the system. This paper presents a novel and enhanced algorithm to solve the multi-card collision problems in an RF-UCard system. The algorithm was originally inspired from framed ALOHA-based anti-collision algorithms applied in RFID systems. To maximize the system efficiency, a synchronous dynamic adjusting (SDA) scheme that adjusts both the frame size in the reader and the response probability in cards is developed and evaluated. Based on some mathematical results derived from the Poisson process and the occupancy problem, the algorithm takes the estimated card quantity and the new arriving cards in the current read cycle into consideration to adjust the frame size for the next read cycle. Also it changes the card response probability according to the request commands sent from the reader. Simulation results show that SDA outperforms other ALOHA-based anti-collision algorithms applied in RFID systems.
Cite this paper: nullJ. CAO, L. SHU and Z. LU, "Synchronous Dynamic Adjusting: An Anti-Collision Algorithm for an RF-UCard System," International Journal of Communications, Network and System Sciences, Vol. 2 No. 1, 2009, pp. 8-20. doi: 10.4236/ijcns.2009.21002.

[1]   K. Finkenzeller, “RFID handbook,” 2nd edition, John Wiley and Sons, 2003.

[2]   W. Rankl and W. Effing, “Smart card handbook,” 3rd edition, John Willey and Sons, 2004.

[3]   L. Shu, J. C. Cao, and Z. D. Lu, “CIM: Hardware support for Multi-COS isolation of RF-UCard,” in Proceedings 2008 International Conference on Embedded Software and Systems, pp. 595-602, July 2008.

[4]   D. R. Hush and C. Wood, “Analysis of tree algorithm for RFID arbitration,” in Proceedings IEEE International Symposium on Information Theory, pp. 107, 1998.

[5]   ISO/IEC 18000-6: Information technology-Radio frequency identification for item management, Part 6, Parameters for air interface communications at 860 MHz to 960 MHz, 2004/Amd 1: 2006.

[6]   J. Myung and W. Lee, “Adaptive binary splitting: A RFID tag collision arbitration protocol for tag identification,” Mobile Networks and Applications, Vol. 11, No. 5, pp. 711-722, May 2006.

[7]   C. Law, K. Lee, and K. S. Siu, “Efficient memoryless protocol for tag identification,” in Proceedings 4th ACM International workshop on discrete algorithms and methods for mobile computing and communications, pp.75-84, August 2000.

[8]   J. Myung and W. Lee, “Adaptive splitting protocols for RFID tag collision arbitration,” in Proceedings 7th ACM international symposium on Mobile ad hoc networking and computing, pp. 202-213, 2006.

[9]   N. Abramson, “Development of the ALOHANET,” IEEE Transactions on Information Theory, Vol. IT-31, pp. 119-123, March 1985.

[10]   L. G. Roberts, “ALOHA packet system with and without slots and capture,” ARPA Network Information Center, Stanford Institute, Menlo Park California, ASS Note 8 (NIC 11290), June 1972.

[11]   F. C. Schoute, “Control of ALOHA signalling in a mobile radio trunking system,” in Proceedings International Conference on Radio Spectrum Conservation Techniques, pp. 38-42, 1980.

[12]   F. C. Schoute, “Dynamic frame length ALOHA,” IEEE Transactions on Communications, Vol. 31, No. 4, pp. 565-568, April 1983.

[13]   H. Vogt, “Efficient object identification with passive RFID tags,” in Proceedings International Conference on Pervasive Computing, Springer-Verlag, Vol. 2414, pp. 98-113, 2002.

[14]   W. T. Chen and G. H. Lin, “An efficient anti-collision method for tag identification in a RFID system,” IEICE Transaction on Communications, Vol. E89-B, No.12, pp. 3386-3392, December 2006.

[15]   J. Zhai and G. N. Wang, “An anti-collision algorithm using two-functioned estimation for RFID tags,” in Proceedings International Conference Computational Science and its Applications, Vol. 3843, pp. 702-711, May 2005.

[16]   S. R. Lee, S. D. Joo, and C. W. Lee, “An enhanced dynamic framed slotted ALOHA algorithm for RFID tag identification,” in Proceedings 2nd Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services, pp. 166-172, July 2005.

[17]   B. Zhen, M. Kobayashi, and M. Shimizu, “Framed ALOHA for multiple RFID objects identification,” IEICE Transaction on Communications, Vol. E88-B, No. 3, pp. 991-999, March 2005.

[18]   S. S. Yu, Y. Zhan, and Y. H. Wang, “RFID anti-collision algorithm based on bi-directional binary exponential index,” in Proceedings the IEEE International Conference on Automation and Logistics, Jinan, China, pp. 2917–2921, August 2007.

[19]   S. A. Tanenbaum, “Computer Networks,” 4th edition, Prentice Hall PTR, 2002.

[20]   R. Motwani and P. Raghavan, “Randomized algorithms,” Cambridge University Press, 1995.