Revisiting RFID Missing Tag Identification: Theoretical Foundation and Algorithm Design

Kanghuai Liu

doi:10.1109/TNET.2024.3404471

2024-10-01

PRE

DOI：10.1109/TNET.2024.3404471

原文链接

原文求助

摘要

En 中文

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 Theta(N+(1-alpha)(2)(1-delta)(2)/epsilon(2)) , where delta and epsilon are parameters quantifying the required identification accuracy, N denotes the number of tags in the system, among which alpha N tags are missing. Secondly, we analytically establish the expected execution time lower-bound for any missing tag identification algorithm as Theta(N/logN+(1-delta)(2)(1-alpha)(2)/epsilon(2)log(1-delta)(1-alpha)epsilon), thus setting the theoretical performance limit. Thirdly, we develop two novel missing tag identification algorithms with the expected execution time of Theta(log logN/logN N+(1-alpha)2(1-delta)2 epsilon(2)) , reducing the time overhead by a factor of up to log N over the best algorithm in the literature. The key technicality in our first algorithm is a novel data structure termed as collision-partition tree (CPT), built on a subset of bits in tag pseudo-IDs, leading to a more balanced tree structure and reducing the time complexity in parsing the entire tree. To further improve time efficiency, our second algorithm integrates multiple CPTs to form a collision-partition forest (CPF), reducing both the number of slots and the quantity of information broadcasting.

Keyword:

Radiofrequency identification

Encoding

Standards

Decoding

Task analysis

Protocols

Physical layer

RFID

missing tag identification