無線射頻辨識（Radio Frequency Identification, RFID）能以無線方式與最低限度的互動實現無所不在的追蹤與監控物件，其在許多應用中扮演了重要的角色，像是資產追蹤、無接觸支付、存取控制、運輸和物流以及其他工業應用。在RFID系統中，讀取器透過共享無線通道上的通訊來識別標籤。然而，當多個標籤同時傳輸其 ID 時訊號會發生碰撞，進而導致識別延遲（Identification Delay）之增加。許多抗碰撞（Anti-collision）的協定已經提出來應對這些挑戰，包括基於樹（Tree-based）和基於 ALOHA （ALOHA-based）的方法，前者主要包括詢問樹（Query Tree, QT）和二元樹（Binary Tree, BT）演算法。
在某些情況下，讀取器知道可能出現的標籤ID，此在本文中稱為「知識」。在本論文中，我們透過已知的知識建造一個詢問樹。我們提出了三種抗碰撞協定：一種基於知識且具有捷徑與配對解決的新型詢問樹（Query Tree with Shortcutting and Couple Resolution, QTSC）、基於知識的位元追蹤詢問樹 （Bit-tracking Knowledge-based Query Tree, BKQT）和基於知識的區分位元詢問樹（Distinguished-bit Searching Knowledge-based Query Tree, DKQT）協定。這些協定的主要概念是QTSC利用知識，而BKQT和DKQT不僅利用知識，還採用位元追蹤技術，允許讀取器感知碰撞槽中碰撞位元的位置。另一方面，BKQT 和 DKQT 的差異在於後者降低了前者建造詢問樹的時間複雜度。
首先，在QTSC中，建造一個基於知識的詢問樹（k-tree）來儲存識別資料庫中所有可能的標籤所需的查詢。然後使用捷徑來遊歷k-tree以識別出現的標籤，同時使用能在同一時槽內同時傳輸兩個ID前綴的配對解決技術來略過k-tree中的重複查詢。接下來，我們提出BKQT，它結合了兩種技術：儲存所有可能出現的標籤 ID之知識； 及允許讀取器檢測碰撞槽中發生碰撞位元位置之位元追蹤，BKQT亦會使用知識建造一個k-tree，同時它使用位元追蹤去建造位元碰撞案例和該k-tree中每個節點的對應操作。在識別過程中，BKQT遊歷此k-tree，因此能夠根據發生位元碰撞案例後採取行動以更快地識別碰撞標籤。最後，提出的DKQT協定建造一棵區分位元知識樹。在每個樹的節點中，該演算法可以從所有可能的標籤中尋找具有區分位元的標籤，並將該標籤儲存在資料庫中。因此，區分位元知識樹是一個n元樹，而不是二元樹。在識別標籤的過程中，DKQT演算法遊歷這個區分位元知識樹，如果一個標籤在所有出現的標籤中有一個區分位元，則讀取器便能直接在對應的查詢中識別該標籤。
模擬結果顯示，與現有的基於知識的協定：知識詢問樹（Knowledge Query Tree, KQT）和啟發式詢問樹（Heuristic Query Tree, H-QT）協定相比，QTSC分別將識別時間改進了60.5%和39.0%。與 KQT、H-QT 和 QTSC 相比，BKQT 分別將識別時間改進了 44.3%、46.4% 和 25.1%。而與QTSC和BKQT相比，DKQT 將識別時間改進了 41.1% 和 21.1%。

Radio Frequency Identification (RFID) has allowed the realization of ubiquitous tracking and monitoring of physical objects wirelessly with minimum human interactions. It plays a crucial role in many applications, including asset tracking, contactless payment, access control, transportation, and logistics. In Radio Frequency Identification (RFID) systems, the reader identifies tags through communications over a shared wireless channel. However, when multiple tags transmit their IDs simultaneously, their signals collide, prolonging the identification delay. Numerous anti-collision protocols have been proposed to address these challenges, including the tree-based and ALOHA-based approaches. The former mainly include Query tree (QT) and the Binary Tree (BT) algorithms.
In some scenarios, the reader knows the IDs of the possible tags which might appear; called “knowledge” here. In this dissertation, we consider the knowledge query tree, which is a query tree by using known knowledge. We present three anti-collision protocols; A novel Knowledge-based Query Tree with Shortcutting and Couple Resolution (QTSC), A Bit-tracking Knowledge-based Query Tree (BKQT), and A Distinguished-bit Searching Knowledge-based Query Tree (DKQT) protocol respectively. The main concepts of these protocols are that QTSC utilizes knowledge while BKQT and DKQT not only utilize knowledge but also adopt the bit-tracking technique, which allows the reader to perceive the locations of collided bits in a collision slot. On the other hand, the difference between BKQT and DKQT is the latter reduces the time complexity of the former in constructing the query tree.
First, in QTSC, a knowledge-based query tree (k-tree) is constructed to store the queries required to identify all of the possible tags in the database. Then, traversing this k-tree with a shortcut to identify the appearing tags. Couple-resolution techniques, which can transmit two ID prefixes simultaneously within the same slot, are employed to skip redundant queries in the k-tree. Next, we propose BKQT, which combines the two techniques: knowledge, which stores all tag IDs that possibly occur, and bit-tracking, which allows the reader to detect the locations of collided bits in a collision slot. BKQT also constructs a k-tree using knowledge while it constructs bit-collision cases and the corresponding actions for each node in this k-tree using bit-tracking. In the identification process, BKQT traverses this constructed k-tree and thus identifies the colliding tags faster by taking the actions according to the happening bit-collision cases. Finally, the proposed DKQT protocol constructs a distinguished-bit knowledge tree. In each tree’s node, the algorithm searches for a tag that has a distinguished-bit from all possible tags and stores the tag in the database. Thus, the distinguished-bit k-tree is an n-ary tree, rather than a binary tree. During the tag identification process, the DKQT algorithm traverses this constructed distinguished-bit k-tree. If a tag has a distinguished-bit from all appearing tags, the reader directly identifies the tag in the corresponding query.
The simulation results show that compared to the existing knowledge-based protocols, Knowledge Query Tree (KQT) and Heuristic Query Tree (H-QT) protocols, QTSC improves the identification time by 60.5% and 39.0%, respectively. BKQT improves the identification time by 44.3%, 46.4%, and 25.1%, compared with KQT, H-QT, and QTSC. DKQT improves the identification time by 41.1% and 21.1% compared to QTSC and BKQT.

References
[1] Z. Asif, "Integrating the supply chain with RFID: A technical and business analysis," Communications of the Association for Information Systems, vol. 15, no. 1, p. 24, 2005, doi: 10.17705/1CAIS.01524.
[2] M. Attaran, "RFID: an enabler of supply chain operations," Supply Chain Management: An International Journal, 2007, doi: 10.1108/13598540710759763.
[3] J. Wang and D. Yang, "Design of a multi-protocol rfid tag simulation platform based on supply chain," in 2009 International Conference on Management and Service Science, 2009: IEEE, pp. 1-4, doi: 10.1109/ICMSS.2009.5305208.
[4] K. Pal, "Algorithmic solutions for RFID tag anti-collision problem in supply chain management," Procedia Computer Science, vol. 151, pp. 929-934, 2019, doi: 10.1016/j.procs.2019.04.129.
[5] K. Finkenzeller, RFID handbook: fundamentals and applications in contactless smart cards, radio frequency identification and near-field communication. John wiley & sons, 2010, doi: 10.1002/9780470665121.fmatter.
[6] J. Aliasgari, M. Forouzandeh, and N. Karmakar, "Chipless RFID readers for frequency-coded tags: Time-domain or frequency-domain?," IEEE Journal of Radio Frequency Identification, vol. 4, no. 2, pp. 146-158, 2020.
[7] J. Myung, W. Lee, and J. Srivastava, "Adaptive binary splitting for efficient RFID tag anti-collision," IEEE communications letters, vol. 10, no. 3, pp. 144-146, 2006, doi: 10.1109/LCOMM.2006.1603365.
[8] T.-P. Wang, "Enhanced binary search with cut-through operation for anti-collision in RFID systems," IEEE communications letters, vol. 10, no. 4, pp. 236-238, 2006, doi: 10.1109/LCOMM.2006.1613732.
[9] F. Z. F. Zhou, D. J. D. Jin, C. H. C. Huang, and M. H. M. Hao, "Optimize the power consumption of passive electronic tags for anti-collision schemes," in ASIC, 2003. Proceedings. 5th International Conference on, 2003, vol. 2: IEEE, pp. 1213-1217, doi: 10.1109/ICASIC.2003.1277432.
[10] E.-f. EPCGlobal and K. Chiew, "Radio-frequency identity protocols class-1 generation-2 uhf rfid protocol for communications at 860 mhz–960 mhz version 1.0. 9," K. Chiew et al./On False Authenticationsfor C1G2 Passive RFID Tags, vol. 65, 2004, doi: 10.1109/ICCT.2008.4716249.
[11] J. Capetanakis, "Tree algorithms for packet broadcast channels," IEEE transactions on information theory, vol. 25, no. 5, pp. 505-515, 1979, doi: 10.1109/TIT.1979.1056093.
[12] J. Song, S. He, and H. Yao, "TMIA: A Tree-Based Multi-Reader Interactive Anti-Collision Algorithm for RFID Tag Identification," IEEE Access, vol. 8, pp. 81594-81605, 2020, doi: 10.1109/ACCESS.2020.2991027.
[13] C.-G. Liu, Y.-M. Huo, I.-H. Liu, H.-H. Liu, C.-F. Li, and J.-S. Li, "A Novel and Efficient Blocking Scheme for Multiple Tag Identifications in a Large Scale RFID System," Adhoc & Sensor Wireless Networks, vol. 46, 2020, doi: 10.1109/WiMOB.2016.7763249.
[14] A. Fahim, T. Elbatt, A. Mohamed, and A. Al-Ali, "Towards Extended Bit Tracking for Scalable and Robust RFID Tag Identification Systems," IEEE Access, vol. 6, pp. 27190-27204, 2018, doi: 10.1109/ACCESS.2018.2832119.
[15] J. Myung, W. Lee, J. Srivastava, and T. K. Shih, "Tag-Splitting: Adaptive Collision Arbitration Protocols for RFID Tag Identification," IEEE Transactions on Parallel and Distributed Systems, vol. 18, no. 6, pp. 763-775, 2007, doi: 10.1109/TPDS.2007.1098.
[16] Y.-C. Lai and L.-Y. Hsiao, "Adaptive frame on binary splitting for radio frequency identification anticollision," International Journal of Communication Systems, vol. 27, no. 10, pp. 1672-1685, 2014, doi: 10.1002/dac.2427.
[17] Y.-C. Lai, L.-Y. Hsiao, and B.-S. Lin, "Optimal slot assignment for binary tracking tree protocol in RFID tag identification," IEEE/ACM Trans. Netw., vol. 23, no. 1, pp. 255-268, 2015, doi: 10.1109/tnet.2013.2295839.
[18] C.-G. Liu, I. H. Liu, C.-D. Lin, and J.-S. Li, "A novel tag searching protocol with time efficiency and searching accuracy in RFID systems," Computer Networks, vol. 150, pp. 201-216, 2019, doi: 10.1016/j.comnet.2019.01.011.
[19] J. Su, Z. Sheng, A. X. Liu, Y. Han, and Y. Chen, "A group-based binary splitting algorithm for UHF RFID anti-collision systems," IEEE Transactions on Communications, vol. 68, no. 2, pp. 998-1012, 2019, doi: 10.1109/TCOMM.2019.2952126.
[20] Y. C. Lai, L. Y. Hsiao, H. J. Chen, C. N. Lai, and J. W. Lin, "A Novel Query Tree Protocol with Bit Tracking in RFID Tag Identification," IEEE Transactions on Mobile Computing, vol. 12, no. 10, pp. 2063-2075, 2013, doi: 10.1109/TMC.2012.176.
[21] C. N. Yang, L. J. Hu, and J. B. Lai, "Query Tree Algorithm for RFID Tag with Binary-Coded Decimal EPC," IEEE Communications Letters, vol. 16, no. 10, pp. 1616-1619, 2012, doi: 10.1109/LCOMM.2012.090312.121213.
[22] Y. Qing, L. Jian-Cheng, S. Zhen-Jiang, and W. Hong-Yi, "A Collected Blocking Collision Tree Algorithm with Bit Tracking for RFID Tag Identification," in 2015 Fifth International Conference on Instrumentation and Measurement, Computer, Communication and Control (IMCCC), 2015: IEEE, pp. 433-438, doi: 10.1109/IMCCC.2015.98.
[23] P. Šolić, J. Radić, and N. Rožić, "Energy efficient tag estimation method for ALOHA-based RFID systems," IEEE Sensors Journal, vol. 14, no. 10, pp. 3637-3647, 2014, doi: 10.1109/JSEN.2014.2330418.
[24] J. Park, M. Y. Chung, and T.-J. Lee, "Identification of RFID tags in framed-slotted ALOHA with robust estimation and binary selection," IEEE Communications Letters, vol. 11, no. 5, pp. 452-454, 2007, doi: 10.1109/LCOMM.2007.061581.
[25] W.-T. Chen, "Optimal frame length analysis and an efficient anti-collision algorithm with early adjustment of frame length for RFID systems," IEEE Transactions on Vehicular Technology, vol. 65, no. 5, pp. 3342-3348, 2015, doi: 10.1109/TVT.2015.2441052.
[26] J. Su, Z. Sheng, L. Xie, G. Li, and A. X. Liu, "Fast Splitting-Based Tag Identification Algorithm For Anti-Collision in UHF RFID System," IEEE Transactions on Communications, vol. 67, no. 3, pp. 2527-2538, 2019, doi: 10.1109/tcomm.2018.2884001.
[27] L. Arjona, H. Landaluce Simon, and A. Perallos Ruiz, "Energy-Aware RFID Anti-Collision Protocol," Sensors, vol. 18, no. 6, p. 1904, 2018, doi: 10.3390/s18061904.
[28] J. V. Sobral et al., "A framework for enhancing the performance of Internet of Things applications based on RFID and WSNs," Journal of Network and Computer Applications, vol. 107, pp. 56-68, 2018, doi: 10.1016/j.jnca.2018.01.015.
[29] M. A. Bonuccelli, F. Lonetti, and F. Martelli, "Exploiting id knowledge for tag identification in rfid networks," presented at the Proceedings of the 4th ACM workshop on Performance evaluation of wireless ad hoc, sensor,and ubiquitous networks, Chania, Crete Island, Greece, May., 2007, doi: 10.1145/1298197.1298210.
[30] H. Chen, Z. Wang, F. Xia, Y. Li, and L. Shi, "Efficiently and Completely Identifying Missing Key Tags for Anonymous RFID Systems," IEEE Internet of Things Journal, vol. 5, no. 4, pp. 2915-2926, 2018, doi: 10.1109/jiot.2017.2752239.
[31] X. Liu et al., "Fast Tracking the Population of Key Tags in Large-Scale Anonymous RFID Systems," IEEE/ACM Transactions on Networking, pp. 1-14, 2016, doi: 10.1109/tnet.2016.2576904.
[32] B. Baruah and S. Dhal, "An IoT Based Secure Object Tracking System," Wireless Personal Communications, vol. 106, no. 3, pp. 1209-1242, 2019, doi: 10.1007/s11277-019-06210-7.
[33] D. Zhang, Z. He, Y. Qian, J. Wan, D. Li, and S. Zhao, "Revisiting unknown RFID tag identification in large-scale internet of things," IEEE Wireless Communications, vol. 23, no. 5, pp. 24-29, 2016, doi: 10.1109/MWC.2016.7721738.
[34] J. Sung, D. Kim, T. Kim, and J. Choi, "Heuristic Query Tree Protocol: Use of Known Tags for RFID Tag Anti-Collision," IEICE Transactions on Communications, vol. E95.B, no. 2, pp. 603-606, 2012, doi: 10.1587/transcom.E95.B.603.
[35] Y.-C. Lai, R. Jayadi, S.-C. Huang, and Y.-H. Chen, "Query Tree with Knowledge-based Splitting for RFID Tag Identification," presented at the Proceedings of the 2018 International Conference on Sensors, Signal and Image Processing - SSIP 2018, 2018, doi.org/10.1145/3290589.3290592.
[36] T. F. La Porta, G. Maselli, and C. Petrioli, "Anticollision protocols for single-reader RFID systems: Temporal analysis and optimization," IEEE Transactions on Mobile Computing, vol. 10, no. 2, pp. 267-279, 2010, doi: 10.1109/TMC.2010.58.
[37] W. Zhu, M. Li, J. Cao, Z. He, and R. Xie, "Multiple resolution bit tracking protocol for continuous RFID tag identification," in 2019 IEEE 16th International Conference on Mobile Ad Hoc and Sensor Systems (MASS), 2019: IEEE, pp. 100-108, doi: 10.1109/MASS.2019.00021.
[38] X. Jia, Q. Feng, and L. Yu, "Stability analysis of an efficient anti-collision protocol for RFID tag identification," IEEE Transactions on Communications, vol. 60, no. 8, pp. 2285-2294, 2012, doi: 10.1109/TCOMM.2012.051512.110448.
[39] Y. Wang, Y. Liu, H. Leung, R. Chen, and A. Li, "A multi-bit identification protocol for RFID tag reading," IEEE Sensors Journal, vol. 13, no. 10, pp. 3527-3536, 2013, doi: 10.1109/JSEN.2013.2272460.
[40] J. Shin, B. Jeon, and D. Yang, "Multiple RFID tags identification with M-ary query tree scheme," IEEE Communications Letters, vol. 17, no. 3, pp. 604-607, 2013, doi: 10.1109/LCOMM.2013.012313.122094.
[41] L. Zhang, W. Xiang, X. Tang, Q. Li, and Q. Yan, "A time-and energy-aware collision tree protocol for efficient large-scale RFID tag identification," IEEE Transactions on Industrial Informatics, vol. 14, no. 6, pp. 2406-2417, 2017, doi: 10.1109/TII.2017.2771772.
[42] J.-S. Li and Y.-M. Huo, "An efficient time-bound collision prevention scheme for RFID re-entering tags," IEEE Transactions on Mobile Computing, vol. 12, no. 6, pp. 1054-1064, 2012, doi: 0.1109/TMC.2012.68.
[43] H. Guo, C. He, N. Wang, and M. Bolic, "PSR: A novel high-efficiency and easy-to-implement parallel algorithm for anticollision in RFID systems," IEEE Transactions on Industrial Informatics, vol. 12, no. 3, pp. 1134-1145, 2016, doi: 10.1109/TII.2016.2554465.
[44] M. Shahzad and A. X. Liu, "Probabilistic optimal tree hopping for RFID identification," IEEE/ACM Transactions on Networking, vol. 23, no. 3, pp. 796-809, 2014, doi: doi.org/10.1145/2494232.2465549.
[45] F. Schoute, "Dynamic frame length ALOHA," IEEE Transactions on communications, vol. 31, no. 4, pp. 565-568, 1983, doi: 10.1109/TCOM.1983.1095854.
[46] X. L. Jia, M. Bolic, Y. H. Feng, and Y. J. Gu, "An Efficient Dynamic Anti-Collision Protocol for Mobile RFID Tags Identification," (in English), Ieee Communications Letters, vol. 23, no. 4, pp. 620-623, Apr 2019, doi: 10.1109/Lcomm.2019.2895819.
[47] Z. L. Hailemariam, Y.-C. Lai, R. Jayadi, Y.-H. Chen, and S.-C. Huang, "A knowledge-based Query Tree with Shortcutting and Couple-Resolution for RFID tag identification," Comput Commun, 2020, doi: 10.1016/j.comcom.2020.06.025.
[48] H. Chen, G. Xue, and Z. Wang, "Efficient and Reliable Missing Tag Identification for Large-Scale RFID Systems With Unknown Tags," IEEE Internet of Things Journal, vol. 4, no. 3, pp. 736-748, 2017, doi: 10.1109/jiot.2017.2664810.
[49] J. Yu, L. Chen, R. Zhang, and K. Wang, "On Missing Tag Detection in Multiple-Group Multiple-Region RFID Systems," IEEE Transactions on Mobile Computing, vol. 16, no. 5, pp. 1371-1381, 2017, doi: 10.1109/tmc.2016.2592902.
[50] Z. Huang et al., "A Novel Cross Layer Anti-Collision Algorithm for Slotted ALOHA-Based UHF RFID Systems," IEEE Access, vol. 7, pp. 36207-36217, 2019, doi: 10.1109/access.2019.2900739.
[51] M. Q. Memon, J. He, M. A. Yasir, and A. Memon, "Improving Efficiency of Passive RFID Tag Anti-Collision Protocol Using Dynamic Frame Adjustment and Optimal Splitting," Sensors (Basel), vol. 18, no. 4, Apr 12 2018, doi: 10.3390/s18041185.
[52] J. Yu, W. Gong, J. Liu, L. Chen, and K. Wang, "On Efficient Tree-Based Tag Search in Large-Scale RFID Systems," IEEE/ACM Transactions on Networking, vol. 27, no. 1, pp. 42-55, 2019, doi: 10.1109/tnet.2018.2879979.
[53] Y. C. Lai and C. C. Lin, "Two Couple-Resolution Blocking Protocols on Adaptive Query Splitting for RFID Tag Identification," (in English), Ieee Transactions on Mobile Computing, vol. 11, no. 10, pp. 1450-1463, Oct 2012, doi: 10.1109/Tmc.2011.171.
[54] H. Landaluce, A. Perallos, and I. Angulo, "Managing the number of tag bits transmitted in a bit-tracking RFID collision resolution protocol," Sensors, vol. 14, no. 1, pp. 1010-1027, 2014, doi: 10.3390/s140101010.
[55] "<TNET-2022-00098_Proof_hi.pdf>."
[56] H. Landaluce, A. Perallos, E. Onieva, L. Arjona, and L. Bengtsson, "An Energy and Identification Time Decreasing Procedure for Memoryless RFID Tag Anticollision Protocols," IEEE Transactions on Wireless Communications, vol. 15, no. 6, pp. 4234-4247, 2016, doi: 10.1109/twc.2016.2537800.
[57] J. Su, Z. Sheng, G. Wen, and V. C. Leung, "A time efficient tag identification algorithm using dual prefix probe scheme (DPPS)," IEEE Signal Processing Letters, vol. 23, no. 3, pp. 386-389, 2016, doi: 10.1109/LSP.2016.2516768.
[58] J. Su, Y. Chen, Z. Sheng, Z. Huang, and A. X. Liu, "From M-Ary Query to Bit Query: A New Strategy for Efficient Large-Scale RFID Identification," IEEE Transactions on Communications, vol. 68, no. 4, pp. 2381-2393, 2020, doi: 10.1109/tcomm.2020.2968438.
[59] Y.-C. Lai, S.-Y. Chen, Z. L. Hailemariam, and C.-C. Lin, "A Bit-Tracking Knowledge-Based Query Tree for RFID Tag Identification in IoT Systems," Sensors, vol. 22, no. 9, p. 3323, 2022, doi: 10.3390/s22093323.
[60] Y. G. Kim and A. H. Vinck, "Anticollision algorithms for FM0 code and miller subcarrier sequence in RFID applications," IEEE Transactions on Vehicular Technology, vol. 67, no. 6, pp. 5168-5173, 2018, doi: 10.1109/TVT.2018.2817587.
[61] J. Su, Z. Sheng, A. X. Liu, Z. Fu, and C. Huang, "An efficient missing tag identification approach in RFID collisions," IEEE Transactions on Mobile Computing, 2021, doi: 10.1109/TMC.2021.3085820.
[62] Y. C. Lai and C. C. Lin, "A Pair-Resolution Blocking Algorithm on Adaptive Binary Splitting for RFID Tag Identification," IEEE Communications Letters, vol. 12, no. 6, pp. 432-434, 2008, doi: 10.1109/LCOMM.2008.080056.