Dynamic tag estimation for optimizing tree slotted aloha in RFID networks

ABSTRACT

The emergent commercial use of techniques for Radio Frequency-based IDentification of different items (RFID) requires the investigation and testing of collision resolution mechanisms for the efficient and correct communication between the system reader and the tags labeling the items that need to be identified. Several MAC protocols have been proposed to resolve collisions in RFID networks. A recent solution, named Tree Slotted Aloha (TSA), has been shown to outperform previous ones with respect to the time it takes for identifying all tags, and the total number of bits transmitted to complete the identification process. However, almost half of the time needed by TSA for identifying tags is spent in collisions. This depends on TSA operation and in particular on the way TSA estimates the number of colliding tags. We have observed that in the case of realistically large networks, TSA highly underestimates this number, with non-negligible impact on the protocol performance. In this paper, we propose a Dynamic Tree Slotted Aloha (Dy TSA) protocol that exploits the knowledge acquired during ongoing readings to refine the estimation of the number of colliding tags. In so doing, Dy TSA adapts the length of the following reading cycles to the actual number of tags still requiring identification. Through ns2-based simulations we show that the proposed method is effective for tag identification and results in significantly improved performance over TSA. Specifically, the length of the identification process is up to 20% lower than that of TSA. Furthermore, the amount of transmitted bits needed for identifying all tags decreases up to 30%.

REFERENCES

• 1: The Network Simulator - ns-2. http://www.isi.edu/nsnam/ns/.
• 2: EPCTM Radio-Frequency Identification Protocols Class-1 Generation-2 UHF RFID Protocol for Communications at 860MHz-960MHz, EPCglobal. http://www.epcglobalinc.org/standards/uhfc1g2, Dec. 2004.
• 3: Maurizio A. Bonuccelli , Francesca Lonetti , Francesca Martelli, Instant collision resolution for tag identification in RFID networks, Ad Hoc Networks, v.5 n.8, p.1220-1232, November, 2007 [doi>10.1016/j.adhoc.2007.02.016]
• 4: J. Capetanakis. Tree algorithms for packet broadcast channels. IEEE Transactions on Information Theory, 25(5):505 -- 515, 1979.
• 5: Ching Law , Kayi Lee , Kai-Yeung Siu, Efficient memoryless protocol for tag identification (extended abstract), Proceedings of the 4th international workshop on Discrete algorithms and methods for mobile computing and communications, p.75-84, August 11-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345848.345865]
• 6: Su-Ryun Lee , Sung-Don Joo , Chae-Woo Lee, An Enhanced Dynamic Framed Slotted ALOHA Algorithm for RFID Tag Identification, Proceedings of the The Second Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services, p.166-174, July 17-21, 2005 [doi>10.1109/MOBIQUITOUS.2005.13]
• 7: J. Massey. Collision resolution algorithms and random-access communication. Multi-Users Communication Networks, CISM Courses and Lectures, (256):73--137, 1981.
• 8: Jihoon Myung , Wonjun Lee, Adaptive binary splitting: a RFID tag collision arbitration protocol for tag identification, Mobile Networks and Applications, v.11 n.5, p.711-722, October 2006 [doi>10.1145/1160115.1160121]
• 9: Lawrence G. Roberts, ALOHA packet system with and without slots and capture, ACM SIGCOMM Computer Communication Review, v.5 n.2, p.28-42, April 1975 [doi>10.1145/1024916.1024920]
• 10: 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

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks

General Terms:
Algorithms, Performance

Keywords:
Radio Frequency IDentification, anti-collision protocol, passive tags