A Tree-Based Collision Resolution Algorithm for RFID using Bayesian Tag Estimation

Abstract

Radio Frequency IDentification (RFID) is a promising wireless object identifying technology which uses radio frequency waves to transmit data between an RFID reader and tags. The RFID systems have been effectively applied in different areas, like manufacturing, healthcare, supply chain, transportation and agriculture. Despite the vast deployment of the RFID technology in practice, the inherent RFID tag collision problem still persists as a serious concern and remains a challenge. The tag collision problem happens when some tags in reader’s vicinity try to transmit data to a reader simultaneously without priori coordination. The existing RFID Electronic Product Code (EPC) Class 1 Generation 2 (Gen 2) industrial standard family uses the Q algorithm as its anti-collision protocol to resolve the tag collision problem. As the Q algorithm relies on the concept of ALOHA protocols, the achievable maximum system efficiency is only around 34%.

In this thesis, we propose two novel anti-collision protocols, namely Bayesian Estimation based Modified Dynamic Tree (BE-MDT) and Binary Splitting Modified Dynamic Tree (BS-MDT), which outperform all existing anti-collision protocols. Both protocols use two phases of operations, i.e., estimate the amount of tags in the system and identify all of them. In the first phase of BE-MDT, we propose a slotted ALOHA based Bayesian tags estimation method which can accumulate the prior knowledge in each slot to estimate the amount of tags in the system and decide the initial frame size to use in the second phase. In the second phase of BE-MDT, we introduce Modified Dynamic Tree (MDT) algorithm which takes the estimated frame size in the first phase as the initial frame and follow by a definite collision skip binary tree algorithm to identify the tags. In our second algorithm, which is BS-MDT, we follow a binary splitting-based tag estimation method in the first phase and use the MDT algorithm in the second phase with a technique to estimate the initial frame size to maximize the system efficiency for any range of tags.

We also present the mathematical models for each algorithm to determine the system efficiency and time system efficiency. The mathematical models are validated through computer simulations. Numerical results confirm that the BE-MDT achieve the system efficiency of 45% and the time system efficiency is 78%, whereas the BS-MDT achieves the system efficiency of 46% and the time system efficiency of 80%.