research-article

PHY-Tree: Physical Layer Tree-Based RFID Identification

Authors:

Yuanqing Zheng,

Yuanqing ZhengAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 26, Issue 2

Pages 711 - 723

https://doi.org/10.1109/TNET.2018.2791938

Published: 01 April 2018 Publication History

Abstract

Tree-based RFID identification adopts a binary-tree structure to collect IDs of an unknown set. Tag IDs locate at the leaf nodes and the reader queries through intermediate tree nodes and converges to these IDs using feedback from tag responses. Existing works cannot function well under the scenario of non-uniform ID distribution as they ignore those ID distribution information hidden in the physical-layer signal of colliding tags. Different from them, we introduce PHY-Tree, a novel tree-based scheme that collects two types of information regarding ID distribution from every encountered colliding signal. First, we can detect if all colliding tags send the same bit content at each bit index by looking into inherent temporal features of the tag modulation schemes. If such resonant states are detected, either left or right branch of a certain sub-tree can be trimmed horizontally. Second, we estimate the number of colliding tags in a slot by computing a related metric defined over the signal’s constellation map, based on which nodes in the same layers of a certain sub-tree can be skipped vertically. We thus call the two types of information as horizontal and vertical info. Evaluations from both experiments and simulations demonstrate that PHY-Tree outperforms the state-of-the-art schemes by at least $1.79\times $ .

References

[1]

(Jul. 2014). EPCglobal C1G2 UHF RFID Protocol at 860 MHz-960 MHz. [Online]. Available: http://www.epcglobalinc.org/standards/uhfc1g2

[2]

C. Angerer, R. Langwieser, and M. Rupp, "RFID reader receivers for physical layer collision recovery," IEEE Trans. Commun., vol. 58, no. 12, pp. 3526-3537, Dec. 2010.

Digital Library

[3]

J. Capetanakis, "Tree algorithms for packet broadcast channels," IEEE Trans. Inf. Theory, vol. IT-25, no. 5, pp. 505-515, Sep. 1979.

Digital Library

[4]

B. Chen, Z. Zhou, and H. Yu, "Understanding RFID counting protocols," IEEE/ACM Trans. Netw., vol. 24, no. 1, pp. 312-327, Feb. 2016.

Digital Library

[5]

N. Cho, S.-J. Song, S. Kim, S. Kim, and H.-J. Yoo, "A 5.1-μw UHF RFID tag chip integrated with sensors for wireless environmental monitoring," in Proc. IEEE ESSCIRC, Sep. 2005, pp. 279-282.

[6]

J. Gan and Y. Tao, "DBSCAN revisited: Mis-claim, un-fixability, and approximation," in Proc. ACM SIGMOD, 2015, pp. 519-530.

Digital Library

[7]

R. E. Greeff, F. W. Smith, and D. K. Ovard, "RFID device time synchronization," U.S. Patent 7 889 083, Feb. 15, 2011.

[8]

H. Hassanieh, J. Wang, D. Katabi, and T. Kohno, "Securing RFIDs by randomizing the modulation and channel," in Proc. USENIX NSDI, 2015, pp. 235-249.

[9]

Y. Hou, J. Ou, Y. Zheng, and M. Li, "PLACE: Physical layer cardinality estimation for large-scale RFID systems," in Proc. IEEE INFOCOM, May 2015, pp. 1957-1965.

[10]

Y. Hou and Y. Zheng, "PHY assisted tree-based RFID identification," in Proc. IEEE INFOCOM, May 2017, pp. 1-9.

[11]

P. Hu, P. Zhang, and D. Ganesan, "Laissez-faire: Fully asymmetric backscatter communication," in Proc. ACM SIGCOMM, 2015, pp. 255-267.

Digital Library

[12]

R. S. Khasgiwale, R. U. Adyanthaya, and D. W. Engels, "Extracting information from tag collisions," in Proc. IEEE RFID, Apr. 2009, pp. 131-138.

[13]

C. Law, K. Lee, and K.-Y. Siu, "Efficient memoryless protocol for tag identification," in Proc. ACM DIALM Workshop, 2000, pp. 75-84.

Digital Library

[14]

V. Namboodiri and L. Gao, "Energy-aware tag anti-collision protocols for RFID systems," in Proc. IEEE PerCom, Mar. 2007, pp. 23-26.

Digital Library

[15]

J. Ou, M. Li, and Y. Zheng, "Come and be served: Parallel decoding for COTS RFID tags," in Proc. ACM MobiCom, 2015, pp. 500-511.

Digital Library

[16]

L. Pan and H. Wu, "Smart trend-traversal: A low delay and energy tag arbitration protocol for large RFID systems," in Proc. IEEE INFOCOM, Apr. 2009, pp. 2571-2575.

[17]

J. Posamentier, "RFID tag clock synchronization," U.S. Patent 20 070 205 871, Sep. 6, 2007.

[18]

C. Qian, Y. Liu, H. Ngan, and L. M. Ni, "ASAP: Scalable identification and counting for contactless RFID systems," in Proc. IEEE ICDCS, Jun. 2010, pp. 52-61.

Digital Library

[19]

C. Qian, H. Ngan, and Y. Liu, "Cardinality estimation for large-scale RFID systems," in Proc. IEEE PerCom, Mar. 2008, pp. 30-39.

Digital Library

[20]

J. Ryu, H. Lee, Y. Seok, T. Kwon, and Y. Choi, "A hybrid query tree protocol for tag collision arbitration in RFID systems," in Proc. IEEE ICC, Jun. 2007, pp. 5981-5986.

[21]

M. Shahzad and A. X. Liu, "Every bit counts: Fast and scalable RFID estimation," in Proc. ACM MobiCom, 2012, pp. 365-376.

Digital Library

[22]

M. Shahzad and A. Liu, "Probabilistic optimal tree hopping for RFID identification," in Proc. ACM SIGMETRICS, 2013, pp. 293-304.

Digital Library

[23]

D. Shen, G. Woo, D. P. Reed, A. B. Lippman, and A. Lippman, "Separation of multiple passive RFID signals using software defined radio," in Proc. IEEE RFID, Apr. 2009, pp. 139-146.

[24]

J. Wang, F. Adib, R. Knepper, D. Katabi, and D. Rus, "RF-compass: Robot object manipulation using RFIDs," in Proc. ACM MobiCom, 2013, pp. 3-14.

Digital Library

[25]

J. Wang, H. Hassanieh, D. Katabi, and P. Indyk, "Efficient and reliable low-power backscatter networks," in Proc. ACM SIGCOMM, 2012, pp. 61-72.

Digital Library

[26]

J. Wang and D. Katabi, "Dude, where's my card?: RFID positioning that works with multipath and non-line of sight," in Proc. ACM SIGCOMM, 2013, pp. 51-62.

Digital Library

[27]

J. Wang, D. Vasisht, and D. Katabi, "RF-IDraw: Virtual touch screen in the air using RF signals," in Proc. ACM SIGCOMM, 2014, pp. 235-246.

Digital Library

[28]

R. Want, "An introduction to RFID technology," IEEE Pervas. Comput., vol. 5, no. 1, pp. 25-33, Jan. 2006.

Digital Library

[29]

L. Yang et al., "Tagoram: Real-time tracking of mobile RFID tags to high precision using COTS devices," in Proc. ACM MobiCom, 2014, pp. 237-248.

Digital Library

[30]

R. Zhang, Y. Liu, Y. Zhang, and J. Sun, "Fast identification of the missing tags in a large RFID system," in Proc. IEEE SECON, Jun. 2011, pp. 278-286.

[31]

B. Zhen, M. Kobayashi, and M. Shimizu, "Framed ALOHA for multiple RFID objects identification," IEICE Trans. Commun., vol. 88, no. 3, pp. 991-999, 2005.

[32]

Y. Zheng and M. Li, "P-MTI: Physical-layer missing tag identification via compressive sensing," in Proc. IEEE INFOCOM, Apr. 2013, pp. 917-925.

[33]

F. Zhu, B. Xiao, J. Liu, and L. Chen, "Efficient physical-layer unknown tag identification in large-scale RFID systems," IEEE Trans. Commun., vol. 65, no. 1, pp. 283-295, Jan. 2017.

[34]

A. Molisch, Wireless Communications, vol. 34. Hoboken, NJ, USA: Wiley, 2012.

Digital Library

Cited By

Zeng YDing H(2023)A Dictionary-Matrix Separation and Viterbi Decoding for Miller Code in RFID Tag CollisionWireless Personal Communications: An International Journal10.1007/s11277-023-10403-6130:4(2801-2819)Online publication date: 24-Apr-2023
https://dl.acm.org/doi/10.1007/s11277-023-10403-6
Bocanegra CKhojastepour MArslan MChai ERangarajan SChowdhury K(2020)RFGoProceedings of the 26th Annual International Conference on Mobile Computing and Networking10.1145/3372224.3419211(1-14)Online publication date: 16-Apr-2020
https://dl.acm.org/doi/10.1145/3372224.3419211
Liu XHuang YXi ZLuo JZhang S(undefined)An Efficient RFID Tag Search Protocol Based on Historical Information Reasoning for Intelligent Farm ManagementACM Transactions on Sensor Networks10.1145/3607475
https://dl.acm.org/doi/10.1145/3607475

Recommendations

Approximating the selected-internal Steiner tree

In this paper, we consider a variant of the well-known Steiner tree problem. Given a complete graph G=(V,E) with a cost function c:E->R^+ and two subsets R and R^' satisfying R^'@?R@?V, a selected-internal Steiner tree is a Steiner tree which contains (...
Constrained tree inclusion
CPM'03: Proceedings of the 14th annual conference on Combinatorial pattern matching

The tree matching problem is considered of given labeled trees P and T, determining if the pattern tree P can be obtained from the text tree T by deleting degree-one and degree-two nodes and, in the case of unordered trees, by also permuting siblings. ...
On the hardness of full Steiner tree problems

Given a weighted graph G = ( V , E ) and a subset R of V, a Steiner tree in G is a tree which spans all vertices in R. The vertices in V R are called Steiner vertices. A full Steiner tree is a Steiner tree in which each vertex of R is a leaf. The full ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 26, Issue 2

April 2018

377 pages

ISSN:1063-6692

Issue’s Table of Contents

Copyright © 2018.

Publisher

IEEE Press

Publication History

Published: 01 April 2018

Published in TON Volume 26, Issue 2

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
67
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zeng YDing H(2023)A Dictionary-Matrix Separation and Viterbi Decoding for Miller Code in RFID Tag CollisionWireless Personal Communications: An International Journal10.1007/s11277-023-10403-6130:4(2801-2819)Online publication date: 24-Apr-2023
https://dl.acm.org/doi/10.1007/s11277-023-10403-6
Bocanegra CKhojastepour MArslan MChai ERangarajan SChowdhury K(2020)RFGoProceedings of the 26th Annual International Conference on Mobile Computing and Networking10.1145/3372224.3419211(1-14)Online publication date: 16-Apr-2020
https://dl.acm.org/doi/10.1145/3372224.3419211
Liu XHuang YXi ZLuo JZhang S(undefined)An Efficient RFID Tag Search Protocol Based on Historical Information Reasoning for Intelligent Farm ManagementACM Transactions on Sensor Networks10.1145/3607475
https://dl.acm.org/doi/10.1145/3607475

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents