在RFID系統中，讀取器是透過共用的無線傳輸通道來辨識標籤。當有多個標籤同時回應ID時，他們彼此的訊號就會互相碰撞而延遲辨識。詢問樹協定(Query Tree Protocol, QT)為一個重要的標籤辨識協定，在一般的RFID應用當中，RFID系統可擁有一個存有所有可能會出現的標籤ID資料庫，因此，我們基於RFID系統擁有這樣的標籤知識庫，提出一個結合捷徑和配對解決技術的詢問樹協定 (Query Tree Protocol with Shortcutting and Couple-resolution techniques, QTSC)。QTSC能根據此知識庫建立一棵可用來辨識知識庫中所有標籤的知識詢問樹。接著，QTSC不僅可利用捷徑技術搜尋此樹避免許多多餘的標籤詢問指令；同時也能利用配對解決技術，藉由傳送一對ID字首使讀取器能一次詢問兩個標籤，減少辨識延遲時間。我們模擬的結果顯示QTSC比QT和知識詢問協定(Knowledge-based Query Tree protocol, KQT)有較優異的效能表現。

In Radio Frequency Identification (RFID) systems, the reader identifies tags through communication over a shared wireless channel. When multiple tags transmit their IDs simultaneously, their signals collide, increasing the identification delay. One important approach of the RFID tag identification protocol is Query Tree protocol (QT). In general RFID applications, a RFID system has a database, which owns all tag IDs that possibly occur. Thus, we consider the case that the RFID system has this knowledge and propose a Query Tree protocol with Shortcutting and Couple-resolution techniques (QTSC). From the database of RFID system, QTSC constructs a knowledge-based query tree, which stores each query that can identifies each tag stored in the database. Then, QTSC not only uses the shortcutting technique, which searches this knowledge-based query tree to skip many redundant queries, but also adopts the couple-resolution technique to couple two tags by simultaneously transmitting two ID prefixes from the reader for reducing the identification delay time. Our simulation results show that QTSC obviously outperforms QT and the previous method, namely, Knowledge-based Query Tree protocol (KQT).

[1] N. Abramson, “The Aloha system – another alternative for computer
communications,” in Proc. Fall Joint Computer Conf., AFIPS Conf. vol. 37, Nov.
1970, pp. 281-285.
[2] Information technology automatic identification and data capture techniques – radio
frequency identification for item management air interface – part 6: parameters for air
interface communications at 860-960 mhz, amendment 1: extension with type C and
update of types A and B.
[3] V. Anantharam, “The stability region of the finite-user slotted Aloha protocol,” IEEE
Transactions on Information Theory, vol. 37, no.3, pp. 535-540, May 1991.
[4] I. Teletar and R. Gallager, “Combining queuing theory and information theory for
multi-access,” IEEE J. Selected Areas in Comm., vol. 13, no. 6, Aug. 1995, pp.
963-969.
[5] F. Schoute, “Dynamic frame length Aloha,” IEEE Transactions on Communications,
vol. 31, no. 4, pp. 565-568, Apr. 1983.
[6] T. W. Hwang, B. G. Lee, Y. S. Kim, D. Y. Suh, and J. S. Kim “Improved anti-collision
scheme for high speed identification in RFID system,” First International Conference
on Innovative Computing, Information and Control, Aug. 2006, pp. 449-452.
[7] 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, pp. 452-454, May 2007.
[8] Q. Peng, M. Zhang, and W. Wu, “Variant enhanced dynamic frame slotted aloha
algorithm for fast object identification in RFID system,” in Proc. IEEE Int. Workshop
on Anti-Counterfeiting, Security, Identification, Apr. 2007, pp. 88-91.
[9] EPCTM Radio-Frequency Identity Protocols Class-1 Generation-2 UHF RFID
Protocol for Communications at 860–960 MHz Version 1.2.0, EPC Global Inc., Oct.
2008.
[10] “Draft protocol specification for a 900 MHz class 0 radio frequency identification
tag,” Auto-ID Center, Feb. 2003.
[11] J. I. Capetanakis, “Tree algorithms for packet broadcast channels,” IEEE Transactions
on Information Theory, vol. 25, pp. 505-515, Sept. 1979.
[12] D. R. Hush and C. Wood, “Analysis of tree algorithm for RFID arbitration,” in
Proceedings of IEEE Int’l Symp. on Inform. Theory, Aug. 1998, p.107.
[13] W. C. Chen, S. J. Horng, and P. Fan, “An enhanced anti-collision algorithm in RFID
based on counter and stack,” Second International Conference on Systems and
Networks Communications, Aug. 2007, pp. 21-24.
[14] “Information technology automatic identification and data capture techniques – radio
frequency identification for item management air interface – part 6: parameters for air
interface communications at 860-960 MHz,” Final Draft International Standard ISO
18000-6, Nov. 2003.
[15] D. R. Hush and C. Wood, “Analysis of tree algorithm for RFID arbitration,” in
Proceedings of IEEE Int’l Symp. on Inform. Theory, Aug. 1998, p.107.
[16] C. Law, K. Lee, and K. Y. Siu, “Efficient memoryless protocol for tag identification,”
in Proc. of Int’l Workshop on Disc. Alg. and Meth. for Mobile Comp. and Comm., Aug.
2000, pp. 75-84.
[17] “860MHz-930MHz class 1 radio frequency identification tag radio frequency &
logical communication interface specification candidate recommendation version
1.0.1,” Auto-ID Center, Nov. 2002.
[18] F. Zhou, C. Chen, D. Jin, and H. Min, “Evaluating and optimization power
consumption of anti-collision protocols for applications in RFID systems,” in Proc.
ACM ISLPED’04, pp. 357-362.
[19] K. W. Chiang, C. Hua, and T. S. Peter Yum, “Prefix-randomized query-tree protocol
for RFID systems,” International Conference on Communications, Jun. 2006, pp.
1653-1657.
[20] J. H . Choi, D. Lee, and H. Lee, “Query tree-based reservation for efficient RFID tag
anti-collision,” IEEE Communications Letters, vol. 11, no. 1, pp. 85-87, Jan. 2007.
[21] M. A. Bonuccelli, F. Lonetti, and F. Martelli, “Exploiting ID knowledge for tag
identification in RFID networks,” in Proc. 4th ACM Workshop on PE-WASUN’07, Oct.
2007, pp. 70-77.
[22] 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, Apr.
2006.
[23] X. Q. Yan, Z. P. Yin, and Y. L. Xiong, “A Comparative Study on the Splitting Tree
Based Protocols for RFID Tag Identification,” 11th IEEE Singapore International
Conference on Communication Systems, Nov. 2008, pp. 332-336.