TIGP (SNHCC) --A Comprehensive Anti-Collision Protocol and Efficiency Enhancement Strategies for Minimizing Tag Collision and Identification Delays in RFID System
- LecturerProf. Zelalem Legese Hailemariam (Department of Computer Science and Information Engineering National Taiwan University of Science and Technology)
Host: TIGP (SNHCC) - Time2024-02-26 (Mon.) 09:00 ~ 11:00
- LocationWebex
Live Stream
https://asmeet.webex.com/asmeet/j.php?MTID=m3e6b308765f53598d2bd2805175cac64
Abstract
Radio Frequency Identification (RFID) has allowed the realization of ubiquitous tracking and monitoring of physical objects wirelessly with minimum human interactions. It is crucial in many applications, including asset tracking, contactless payment, access control, transportation, and logistics. In Radio Frequency Identification (RFID) systems, the reader identifies tags through communications over a shared wireless channel. However, when multiple tags transmit their IDs
simultaneously, their signals collide, prolonging the identification delay. Numerous anti-collision protocols have been proposed to address these challenges, including the tree-based and ALOHA-based approaches. The former mainly include Query Tree (QT) and the Binary Tree (BT) algorithms.
In some scenarios, the reader knows the IDs of the possible tags that might appear; this is called “knowledge” here. In this dissertation, we consider the knowledge query tree, which is a query tree by using known knowledge. We present three anti-collision protocols: A novel Knowledge-based Query Tree with Shortcutting and Couple Resolution (QTSC), A Bit-tracking Knowledge-based Query Tree (BKQT), and A Distinguished-bit Searching Knowledge-based Query Tree (DKQT) protocol respectively. The main concept of these protocols is that QTSC utilizes knowledge. In contrast, BKQT and DKQT utilize the knowledge and adopt the bit-tracking
technique, allowing the reader to perceive the locations of collided bits in a collision slot. On the other hand, the difference between BKQT and DKQT is the latter reduces the time complexity of the former in constructing the query tree.
First, in QTSC, a knowledge-based query tree (k-tree) is constructed to store the queries required to identify all possible tags in the database. Then, traversing this k-tree with a shortcut to identify the appearing tags. Couple-resolution techniques, which can transmit two ID prefixes simultaneously within the same slot, are employed to skip redundant queries in the k-tree. Next, we propose BKQT, which combines the two techniques: knowledge, which stores all tag IDs that possibly occur, and bit-tracking, which allows the reader to detect the locations of collided bits in a collision slot. BKQT also constructs a k-tree using knowledge while it constructs bit-collision cases and the corresponding actions for each node in this k-tree using bit-tracking. In the identification process, BKQT traverses this constructed k-tree and thus identifies the colliding tags faster by taking actions according to the happening bit-collision cases. Finally, the proposed DKQT protocol constructs a distinguished-bit knowledge tree. In each tree’s node, the algorithm searches for a tag that has a distinguished bit from all possible tags and stores the tag in the
database. Thus, the distinguished-bit k-tree is an n-ary rather than a binary tree. The DKQT algorithm traverses this constructed distinguished-bit k-tree during the tag identification process. If a tag has a distinguished bit from all appearing tags, the reader directly identifies the tag in the corresponding query.
The simulation results show that compared to the existing knowledge-based protocols, Knowledge Query Tree (KQT) and Heuristic Query Tree (H-QT) protocols, QTSC improves the identification time by 60.5% and 39.0%, respectively. BKQT improves the identification time by 44.3%, 46.4%, and 25.1%, compared with KQT, H-QT, and QTSC. DKQT improves the identification time by 41.1% and 21.1% compared to QTSC and BKQT.
Keywords: RFID; query tree; bit-tracking; distinguished-bit; anti-collision protocol
simultaneously, their signals collide, prolonging the identification delay. Numerous anti-collision protocols have been proposed to address these challenges, including the tree-based and ALOHA-based approaches. The former mainly include Query Tree (QT) and the Binary Tree (BT) algorithms.
In some scenarios, the reader knows the IDs of the possible tags that might appear; this is called “knowledge” here. In this dissertation, we consider the knowledge query tree, which is a query tree by using known knowledge. We present three anti-collision protocols: A novel Knowledge-based Query Tree with Shortcutting and Couple Resolution (QTSC), A Bit-tracking Knowledge-based Query Tree (BKQT), and A Distinguished-bit Searching Knowledge-based Query Tree (DKQT) protocol respectively. The main concept of these protocols is that QTSC utilizes knowledge. In contrast, BKQT and DKQT utilize the knowledge and adopt the bit-tracking
technique, allowing the reader to perceive the locations of collided bits in a collision slot. On the other hand, the difference between BKQT and DKQT is the latter reduces the time complexity of the former in constructing the query tree.
First, in QTSC, a knowledge-based query tree (k-tree) is constructed to store the queries required to identify all possible tags in the database. Then, traversing this k-tree with a shortcut to identify the appearing tags. Couple-resolution techniques, which can transmit two ID prefixes simultaneously within the same slot, are employed to skip redundant queries in the k-tree. Next, we propose BKQT, which combines the two techniques: knowledge, which stores all tag IDs that possibly occur, and bit-tracking, which allows the reader to detect the locations of collided bits in a collision slot. BKQT also constructs a k-tree using knowledge while it constructs bit-collision cases and the corresponding actions for each node in this k-tree using bit-tracking. In the identification process, BKQT traverses this constructed k-tree and thus identifies the colliding tags faster by taking actions according to the happening bit-collision cases. Finally, the proposed DKQT protocol constructs a distinguished-bit knowledge tree. In each tree’s node, the algorithm searches for a tag that has a distinguished bit from all possible tags and stores the tag in the
database. Thus, the distinguished-bit k-tree is an n-ary rather than a binary tree. The DKQT algorithm traverses this constructed distinguished-bit k-tree during the tag identification process. If a tag has a distinguished bit from all appearing tags, the reader directly identifies the tag in the corresponding query.
The simulation results show that compared to the existing knowledge-based protocols, Knowledge Query Tree (KQT) and Heuristic Query Tree (H-QT) protocols, QTSC improves the identification time by 60.5% and 39.0%, respectively. BKQT improves the identification time by 44.3%, 46.4%, and 25.1%, compared with KQT, H-QT, and QTSC. DKQT improves the identification time by 41.1% and 21.1% compared to QTSC and BKQT.
Keywords: RFID; query tree; bit-tracking; distinguished-bit; anti-collision protocol
BIO
Prof. Zelalem Legese Hailemariam currently holds the position of Assistant Professor in the esteemed Department of Computer Science and Information Engineering at the National Taiwan University of Science and Technology. He assumed this role in August 2022 and has since been actively engaged in advancing research, education, and the academic community in computer science and information technology.
Prof. Zelalem Legese Hailemariam earned his B.S. in Information Technology from Aksum University, Ethiopia, in 2015. Building upon his educational background, he pursued and completed his doctoral studies, earning a Ph.D. in Information Management from the National Taiwan University of Science and Technology, Taiwan, in 2022.
His research interests include:
-
Wireless Networks and Performance Evaluation
-
Network Protocols
-
RFID
-
Device-to-Device Communications
-
Network Configuration and Highspeed-Related Issues
-
AIoT (AI+IoT)
-
Machine Learning