Revisiting RFID Missing Tag Identification
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914105120522240 |
|---|---|
| author | Liu, Kanghuai Chen, Lin Yu, Jihong Huang, Junyi Liu, Shiyuan |
| author_facet | Liu, Kanghuai Chen, Lin Yu, Jihong Huang, Junyi Liu, Shiyuan |
| contents | 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 $Θ\left(N+\frac{(1-α)^2(1-δ)^2}{ ε^2}\right)$, where $δ$ and $ε$ are parameters quantifying the required identification accuracy, $N$ denotes the number of tags in the system, among which $αN$ tags are missing. Secondly, we analytically establish the expected execution time lower-bound for any missing tag identification algorithm as $Θ\left(\frac{N}{\log N}+\frac{(1-δ)^2(1-α)^2}{ε^2 \log \frac{(1-δ)(1-α)}ε}\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 $Θ\left(\frac{\log\log N}{\log N}N+\frac{(1-α)^2(1-δ)^2}{ ε^2}\right)$, reducing the time overhead by a factor of up to $\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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_18285 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Revisiting RFID Missing Tag Identification Liu, Kanghuai Chen, Lin Yu, Jihong Huang, Junyi Liu, Shiyuan Networking and Internet Architecture Data Structures and Algorithms 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 $Θ\left(N+\frac{(1-α)^2(1-δ)^2}{ ε^2}\right)$, where $δ$ and $ε$ are parameters quantifying the required identification accuracy, $N$ denotes the number of tags in the system, among which $αN$ tags are missing. Secondly, we analytically establish the expected execution time lower-bound for any missing tag identification algorithm as $Θ\left(\frac{N}{\log N}+\frac{(1-δ)^2(1-α)^2}{ε^2 \log \frac{(1-δ)(1-α)}ε}\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 $Θ\left(\frac{\log\log N}{\log N}N+\frac{(1-α)^2(1-δ)^2}{ ε^2}\right)$, reducing the time overhead by a factor of up to $\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. |
| title | Revisiting RFID Missing Tag Identification |
| topic | Networking and Internet Architecture Data Structures and Algorithms |
| url | https://arxiv.org/abs/2510.18285 |