Revisiting RFID Missing Tag Identification

Kanghuai Liu 1 , Lin Chen 1 2 , , Jihong Yu 3 , , Junyi Huang 1 , and Shiyuan Liu 1 · 2025

Read Revisiting RFID Missing Tag Identification by Kanghuai Liu 1 , Lin Chen 1 2 , , Jihong Yu 3 , , Junyi Huang 1 , and Shiyuan Liu 1 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-18285.txt.

Introduction

Kanghuai Liu, with Lin Chen and three co-authors, revisits missing tag finding in RFID networks in 2025. RFID, meaning radio-frequency identification, lets readers scan many small tags at once without contact. Finding which tags are missing from a known set must be fast and accurate.

The authors first benchmark a decade of earlier methods on equal footing. They then prove a lower bound, meaning no method can beat a certain time, for any such algorithm. Their new method uses a collision-partition tree, a branching structure built from bits of tag codes. It runs faster than the best prior method by a wide factor.

Catalog record

CREATORKanghuai Liu 1 , Lin Chen 1 2 , , Jihong Yu 3 , , Junyi Huang 1 , and Shiyuan Liu 1
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE53 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-18285

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Revisiting RFID Missing Tag Identification Kanghuai Liu 1 , Lin Chen 1 2 , , Jihong Yu 3 , , Junyi Huang 1 , and Shiyuan Liu 1 Abstract We revisit the problem of missing tag identification in RFID networks by making three contributions. Firstly, we quantitatively compare and gauge the existing propositions spanning over a decade on missing tag identification. We show that the expected execution time of the best solution in the literature is Θ ⁡ ( N + ( 1 − α ) 2 ​ ( 1 − δ ) 2 ϵ 2 ) \Theta\left(N+\frac{(1-\alpha)^{2}(1-\delta)^{2}}{\epsilon^{2}}\right) , where δ \delta and ϵ \epsilon are parameters quantifying the required identification accuracy, N N denotes the number of tags in the system, among which α ​ N \alpha N tags are missing. Secondly, we analytically establish the expected execution time lower-bound for any missing tag identification algorithm as Θ ⁡ ( N log ⁡ N + ( 1 − δ ) 2 ​ ( 1 − α ) 2 ϵ 2 ​ log ⁡ ( 1 − δ ) ​ ( 1 − α ) ϵ ) \Theta\left(\frac{N}{\log N}+\frac{(1-\delta)^{2}(1-\alpha)^{2}}{\epsilon^{2}\log\frac{(1-\delta)(1-\alpha)}{\epsilon}}\right) , thus giving the theoretical performance limit. Thirdly, we develop a novel missing tag identification algorithm by leveraging a tree structure with the expected execution time of Θ ⁡ ( log ⁡ log ⁡ N log ⁡ N ​ N + ( 1 − α ) 2 ​ ( 1 − δ ) 2 ϵ 2 ) \Theta\left(\frac{\log\log N}{\log N}N+\frac{(1-\alpha)^{2}(1-\delta)^{2}}{\epsilon^{2}}\right) , reducing the time overhead by a factor of up to log ⁡ N \log N over the best algorithm in the literature. The key technicality in our design is a novel data structure termed as collision-partition tree (CPT), built on a subset of bits in tag pseudo-IDs, leading to more balanced tree structure and reducing the time complexity in parsing the entire tree. I Introduction Characterized by backscatter communication, fast and accurate identification, and non-line-of-sight tracking capability, radio frequency identification (RFID) has become an enabling technology in emerging IoT applications and has been widely applied in a large number of applications ranging from warehouse management, supply-chain control, indoor localization, to object tracking [ 1 , 2 , 3 ] . An RFID system in its standard form is composed of a reader, usually connected to a back-end server, and a number of tags that can harvest energy from the reader via RF waves to communicate with it over the wireless medium [ 4 ] . In typical large-scale RFID applications such as inventory control and factory surveillance, one of the most important and fundamental tasks is missing tag identification. This task is particularly challenging, because it needs to be performed in a time-efficient fashion while satisfying the identification accuracy requirement, two objectives that are often at odd with each other [ 5 , 6 ] . Given its paramount practical importance, missing tag identification has been extensively investigated, with the first proposition dating back to as early as 2010 [ 7 ] . Since then, a variety of techniques involving adaptive sampling [ 8 ] , probabilistic framed ALOHA [ 3 ] , multi-seed hashing [ 9 ] , physical layer coding [ 10 ] etc., have been delicately mobilized to design dozens of missing tag identification algorithms, some focusing on particular application scenarios, some searching for appropriate performance trade-offs among detection accuracy, time and energy cost, others advancing the state of the art by refining the related algorithm and protocol design so as to reduce the communication and computing overhead. Given the large body of research spanning over a decade [ 7 , 8 , 10 , 3 , 9 , 11 , 12 ] resulting in a large palette of proposed solutions, two natural questions arise: 1. How do they compare with each other? Can we quantify their performance? 2. Is there a theoretical limit for any missing tag identification algorithm? If yes, is it achievable? Driven by the above research questions, and standing on the shoulder of the existing works, in this paper we revisit the problem of missing tag identification both retrospectively and prospectively. Retrospectively, we quantitatively compare and gauge the existing propositions spanning over a decade on missing tag identification (cf. Tab. II ). Specifically, we show that the expected execution time of the best solution in the literature is \Theta\left(N+\frac{(1-\alpha)^{2}(1-\delta)^{2}}{\epsilon^{2}}\right) , where \delta and \epsilon are parameters quantifying the required detection accuracy, N denotes the number of tags in the system, among which \alpha N of them are missing. For comparison, we analytically establish the expected execution time lower-bound for any missing tag identification algorithm in Theorem 1 as \Theta\left(\frac{N}{\log N}+\frac{(1-\delta)^{2}(1-\alpha)^{2}}{\epsilon^{2}\log\frac{(1-\delta)(1-\alpha)}{\epsilon}}\right) . 1 1 1 Throughout this paper, logarithm is taken on base 2 . We note that, despite the large body of research works, the theoretical performance limit of missing tag identification has not been formally characterized. Our result derived in this paper fills this important gap, and can serve as a design guideline for future research in this field. Prospectively, armed with the theoretical results we derive, we further develop a novel missing tag identification algorithm by leveraging a tree-based structure to optimize the time efficiency, the central performance metric in missing tag identification. With the expected execution time of \Theta\left(\frac{\log\log N}{\log N}N+\frac{(1-\alpha)^{2}(1-\delta)^{2}}{\epsilon^{2}}\right) as proved in Theorem 3 , our algorithm reduces the time overhead by a factor of up to \log N over the best algorithm in the literature, advancing the state of the art on missing tag identification. Compared to the theoretical performance limit we derive, there is still room for improvement over our algorithm. We hope that our work will stimulate further algorithmic study that can narrow or even fill the performance gap. Roadmap . The rest of the paper is articulated as follows. Section II introduces the system model and formulates the problem. Theoretical performance limit is derived in Section III . Section IV quantifies major existing RFID missing tag identification algorithms. We present our proposition, termed as collision-partition tree-based (CPT) algorithm, in Section V . Extensive experiments are conducted in Section VI . Section VII summarizes related work and analyzes their limitations. Section VIII concludes the paper. II System Model and Problem Formulation Consider a time-synchronized RFID system composed of a reader and a set \cal N of N tags, each characterized by a unique M -bit ID ( M=96 in the current standard). The reader communicates with tags via the standard Framed Slotted Aloha (FSA) protocol. The time slots are divided into empty , singleton and collision slots: in empty slots, no tag responds; in singleton slots, only one tag responds; a slot is called a k -collision slot if k tags responds in this slot; collision slots and singleton slots are collectively referred to as busy slots. Slots differ in their length depending on the number of bits transmitted within the slots. Typically, we distinguish three slot lengths: t_{s} denotes the length of a short slot containing a single bit, t_{t} denotes the length of a tag slot containing a tag ID (i.e. M bits), t_{l} denotes the length of a long slot containing more information transmitted between the reader and tags. TABLE I: Main

Read the complete text