Tag Anti-Collision Algorithms in RFID Systems

Majid Al-otaibi (2010). Tag Anti-Collision Algorithms in RFID Systems PhD Thesis, School of Information Technology and Electrical Engineering, The University of Queensland.

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads
s40486981_PhD_Finalthesis.pdf Final Thesis application/pdf 4.36MB 0
Author Majid Al-otaibi
Thesis Title Tag Anti-Collision Algorithms in RFID Systems
School, Centre or Institute School of Information Technology and Electrical Engineering
Institution The University of Queensland
Publication date 2010-09
Thesis type PhD Thesis
Supervisor Adam Postula
Total pages 188
Total colour pages 85
Total black and white pages 103
Subjects 08 Information and Computing Sciences
Abstract/Summary Mobile and wireless technologies have enabled the first step of pervasive communication systems and applications with billions terminals in commercial operation in the world. Yet this is only the beginning as wireless technologies such as Radio Frequency Identification (RFID) are drawn with a potential use tens of billions of tags and a virtually unlimited range of applications considered. RFID is a contactless, without line-of-sight, low-power and low-cost wireless communication technology that provides automatic identification and data collection. Behind the technological aspects of RFID, it is expected to have a long lasting impact on our society. RFID technology is applied in many fields such as in logistics, supply chain, transportation, manufacturing, distribution, retail, healthcare, agriculture, construction, safety, security, law enforcement, intellectual property protection and many other areas. It is envisioned that RFID will tag billions of objects which can over wireless connections report their location, identity, and history hence becoming the “Internet of Things”[1]. RFID systems contain a number of tags with unique serial numbers, a reader to communicate and collect information from the tags, and an application processor. A RFID reader identifies a tag attached to an object through RF wireless communications. The tag sends its own ID and additional information to the reader for tag identification. The reader should be able to recognize tags as quickly as possible. However, the signals in both directions between the reader and the tag may collide because communication is performed over a shared wireless channel. As a consequence, either the reader may not identify all tags or the tag identification process may be delayed. Thus, anti-collision algorithms which provide quick and correct recognition regardless of the occurrence of collisions are required. There are three main groups of tag anti-collision algorithms: ALOHA based, Tree based and Hybrid algorithms. ALOHA based methods reduce the occurrence of collisions by providing tags the opportunity to select a random transmission time (a slot or frame). Tree based methods reduce collisions with the reader by splitting the tags based on their identification number (ID). Hybrid algorithms combine the characteristics of both ALOHA and Tree based algorithms. Estimating number of tags in the interrogation zone of the reader is essential in most of ALOHA based and hybrid algorithms as the throughput efficiency of the system can be maximized when the number of available slots is set equal to the number of remaining tags. Most existing methods estimate the number of tags in the interrogation zone based on the collision information of the previous round. xii Although ALOHA based tag anti-collision algorithms are simple to implement and fast, they have a problem that a specific tag may not be identified for a long time and this is called tag starvation. That means ALOHA based algorithms cannot completely avoid collisions. For more improvement, finding an accurate method to estimate the number of presented tags in the interrogation zone of the reader is the most important field of research. The algorithms can be further improved by restricting the number of responding tags, when there are a high number of tags present in the interrogation zone. The tree based RFID tag anti-collision algorithms achieve full read rate, however, the efficiency of the identification process can be affected by the length and distribution of tag IDs, and the tag population size. Thus, tree based algorithms suffers from the long identification delay. Hybrid algorithms combine the advantages of both ALOHA and tree based methods, thereby mitigating tag starvation and long delay. As such, these algorithms are most promising and substantial research has been reported on their development and applications last years. This thesis introduces the Signal Strength (SS) based estimation technique which shows better performance compared to other estimation methods. The new method uses the information of which bits collided in each slot as well as the total received signal strength of each collision. For different encoding schemes the information available in the signal strength of collisions can differ, and therefore a comprehensive analysis of signal strength based tag estimation for encoding methods used in RFID systems is presented in this thesis. Several encoding schemes, including commercially used FM0 and Manchester benefit from SS estimation. Among these, Manchester encoding has been found to provide best improvement in the performance. Two anti-collision algorithms are improved by applying SS estimation technique in this thesis. They are Dynamic Frame Slotted ALOHA with SS (DFSA-SS) and improved Query Tree ALOHA with SS estimation technique (iQTA-SSx) algorithms. The time efficiencies of DFSA-SS and iQTA-SSx are 67.5% and 82% respectively. These performances exceed best time efficiency of DFSA and QT-ALOHA algorithms, which are 66.5% and 62% respectively. For large number of tags, the optimum frame size for DFSA and DFSA-SS becomes too large for practical implementation and therefore iQTA-SSx becomes the appropriate choice. Both algorithms work with existing standards and can be implemented within the reader thus no modifications to tags are needed. Analysis of the implementation aspects is performed for these improved algorithms. One of the main implementation aspects involves using a reduced number of bits for capturing signal strength data. Fewer bits allow cheaper Analogue to Digital Converters (ADCs) to be used. The simulation results show that performance of DFSA-SS and iQTA-SSx algorithms is preserved even if 7 bit ADC resolution is used instead of floating point representation. The reading range is highly related xiii to the SNR level of each tag‟s signal at the reader. For a system with a reading range of 10 m radius, 7 bits ADC resolution and -70 dBm noise, the estimation performance drops to 64.3% and 76% for DFSA-SS and iQTA-SSx respectively. In the experiments the Universal Software Radio Peripheral (USRP) hardware using the open source GNU radio stack was used to analyse the message exchange between the reader and tags showing that SS based estimation technique works in practice.
Keyword RFID, estimation, signal strength, anti-collision algorithm
Additional Notes 25, 29, 32-34, 37, 41, 45-47, 49, 53, 59, 64, 67-69, 72-73, 76-77, 82-84, 86-91, 93-94, 96-99, 101-105, 107, 109-115, 117, 120-127, 135-136, 138-139, 141, 143-149, 153, 159-168, 171, 173-175

Citation counts: Google Scholar Search Google Scholar
Created: Mon, 21 Feb 2011, 13:35:06 EST by Mr Majid Al-otaibi on behalf of Library - Information Access Service