TY - GEN

T1 - Revisiting RFID Missing Tag Identification

AU - Liu, Kanghuai

AU - Chen, Lin

AU - Huang, Junyi

AU - Liu, Shiyuan

AU - Yu, Jihong

N1 - Publisher Copyright:
© 2022 IEEE.

PY - 2022

Y1 - 2022

N2 - 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 left( {N + frac{{{{(1 - alpha )}^2}{{(1 - delta )}^2}}}{{{varepsilon ^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 Theta left( {frac{N}{{log N}} + frac{{{{(1 - delta )}^2}{{(1 - alpha )}^2}}}{{{varepsilon ^2}log frac{{(1 - delta )(1 - alpha )}}{varepsilon }}}} 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 Theta left( {frac{{log log N}}{{log N}}N + frac{{{{(1 - alpha )}^2}{{(1 - delta )}^2}}}{{{varepsilon ^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.

AB - 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 left( {N + frac{{{{(1 - alpha )}^2}{{(1 - delta )}^2}}}{{{varepsilon ^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 Theta left( {frac{N}{{log N}} + frac{{{{(1 - delta )}^2}{{(1 - alpha )}^2}}}{{{varepsilon ^2}log frac{{(1 - delta )(1 - alpha )}}{varepsilon }}}} 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 Theta left( {frac{{log log N}}{{log N}}N + frac{{{{(1 - alpha )}^2}{{(1 - delta )}^2}}}{{{varepsilon ^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.

UR - http://www.scopus.com/inward/record.url?scp=85133303405&partnerID=8YFLogxK

U2 - 10.1109/INFOCOM48880.2022.9796971

DO - 10.1109/INFOCOM48880.2022.9796971

M3 - Conference contribution

AN - SCOPUS:85133303405

T3 - Proceedings - IEEE INFOCOM

SP - 710

EP - 719

BT - INFOCOM 2022 - IEEE Conference on Computer Communications

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 41st IEEE Conference on Computer Communications, INFOCOM 2022

Y2 - 2 May 2022 through 5 May 2022

ER -