防止標籤訊號碰撞的問題在無線射頻標籤辨識系統中一直是重要的研究議題。最近有許多研究學者採用改進的替代性ID(Alternative ID)技術，透過另一較短或是與其他標籤ID相似度較低的替代性ID來取代原本96位元長度的ID，進而減少標籤碰撞與碰撞所耗費的訊號傳輸量，進而加快標籤辨識的速度，然而這些方法在標籤數量較大時，過短的替代性ID長度會產生相同的替代性ID而造成某些標籤無法被辨識之問題，當標籤數量較小時，過長的替代性ID長度則會造成多餘的浪費，因此，本論文提出了以QT為基礎並結合改進的替代性ID技術的標籤防碰撞演算法：X-bit Random Number Aided Query Tree Algorithm(RNXQTA)，嘗試透過位元長度為x的替代性ID來取代原本96位元長度的ID，進而節省碰撞發生時所耗費的訊號傳輸量，首先根據目前尚未辨識的標籤數量計算出最佳的替代性ID長度x，接著在辨識過程中使用位元長度為x的替代性ID取代原本96位元長度的ID。本論文透過模擬的方式來評估RNXQTA的效能，並跟目前現有的演算法進行比較，其結果顯示RNXQTA在標籤數量較大時，辨識效能勝於其它現存的演算法，甚至當標籤數量大於32768時，RNXQTA辨識效能優於其它現存的演算法約14%。

An anti-collision problem is always an important research topic in Radio Frequency Identification(RFID). Recently, many research academic using improved alternative ID technology which replaced the 96 bits length of the tag ID with another short length or lower similar alternative ID then to reduce the tag collision and consuming number of bits when collision occurs and enhancing tag of identification efficiency. However, the method in lots of tags, the shorter length alternative ID will generate same alternative ID then cause some tags unidentified problems. When in a few of tags, the longer length alternative ID will cause redundant consuming. Thus, this paper proposed anti-collision algorithms which based on QT and combined improved alternative ID technology technology called X-bit Random Number Aided Query Tree Algorithm(RNXQTA).The algorithm try to replace original the 96 bits length of the tag ID with the x bits length of the alternative ID and then to reduce consuming number of bits when collision occurs. First of all, according to the currently number of unidentified tags to calculate the optimal length x of alternative ID. Then, replacing original the 96 bits length of the tag ID with the x bits length of the alternative ID in the identifying process. This paper through the way of simulation to estimate the efficiency of RNXQTA and compared with currently existing algorithms. The experimental results point out that RNXQTA identification efficiency is more than other existing algorithms while in lots of tags. Even the number of tags more than 32768, RNXQTA identification efficiency is more than other existing algorithms about 14%.

[1] “Information technology - radio frequency identification for item management - part 6: parameters for air interface communications at 860 MHz to 960 MHz, amendment 1: extension with type C and update of types A and B,” ISO/IEC 18000-6:2004/Amd. 1:(E), Jun. 2006.
[2] “EPCTM radio-frequency identity protocols class 1 generation-2 UHF RFID protocol for communications at 860-960MHz version 1.2.0,” EPCglobal IncTM, May 2008.
[3] M. Azambuja, C. A. M. Marcon, and F. P. Hessel, “Survey of standardized ISO 18000-6 RFID anti-collision protocols,” Second International Conference on Sensor Technologies and Applications, pp. 468-473, Aug. 2008.
[4] M. K. Yeh, J. R. Jiang, and S. T. Huang, “Parallel response query tree splitting for RFID tag anti-collision,” 40th International Conference on Parallel Processing Workshops, pp. 6-15, Sept. 2011.
[5] J. Myung, W. Lee, and T. K. Shih, “An adaptive memoryless protocol for RFID tag collision arbitration,” IEEE Transactions on Multimedia, vol. 8, no. 5, pp. 1096-1101, Oct. 2006.
[6] J. Myung, W. Lee, J. Srivastava, and T. K. Shih, “An adaptive collision arbitration protocols for RFID tag identification,” IEEE Transactions on Parallel and Distributed Systems, vol. 18, no. 6, pp. 763-775, Jun. 2007.
[7] Y. C. Lai and C. C. Lin, “Two blocking algorithms on adaptive binary splitting: single and pair resolutions for RFID tag identification,” IEEE/ACM Transactions on Networking, vol. 17, no. 3, pp. 962-975, Jun. 2009.
[8] Y. C. Lai and C. C. Lin, “Two couple-resolution blocking protocols on adaptive query splitting for RFID tag identification,” IEEE Transactions on Mobile Computing, DOI: 10.1109/TMC.2011.171.
[9] Y. C. Lai and L. Y. Hsiao, “General binary tree protocol for coping with the capture effect in RFID tag identification,” IEEE Communications Letters, vol. 14, no. 3, pp. 208-210, Mar. 2010.
[10] 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, Oct. 2012.
[11] X. Jia, Q. Feng, and C. Ma, “An efficient anti-collision protocol for RFID tag identification,” IEEE Communications Letters, vol. 14, no. 11, pp. 1014-1016, Nov. 2010.
[12] Y. H. Chen, S. J. Horng, R. S. Run, J. L. Lai, R. J. Chen, W. C. Chen, Y. Pan, and T. Takao, “A novel anti-collision algorithm in RFID systems for identifying passive tags,” IEEE Transactions on Industrial Informatics, vol. 6, no. 1, pp. 105-121, Feb. 2010.
[13] Y. F. Li, H. J. Wang, and H. Li “A RFID algorithm based on cyclic redundancy check,” Anti-counterfeiting, Security, and Identification in Communication, pp. 278-281, Aug. 2009.
[14] H. Vogt, “Efficient object identification with passive RFID tags,” Pervasive 2002, LNCS 2414, pp. 98–113, Jan. 2002.
[15] J. B. Eom, T. J. Lee, R. Rietman, and A. Yener, “An efficient framed-slotted aloha algorithm with pilot frame and binary selection for anti-collision of RFID tags,” IEEE Communications Letters, vol.12, no. 11, pp. 861-863, Nov. 2008.
[16] J. B. Eom, and T. J. Lee, “Accurate tag estimation for dynamic framed-slotted aloha in RFID systems,” IEEE Communications Letters, vol.14, no. 1, pp. 60-62, Jan. 2010.
[17] M. H. Nazir, and N. Sheriff, “Dynamic grouping frame-slotted aloha,” International Journal of Computer Applications , vol.37, no. 4, pp. 1-5, Jan. 2012.
[18] W. T. Chen, “An accurate tag estimate method for improving the performance of an RFID anti-collision algorithm based on dynamic frame length ALOHA,” IEEE Transactions on Automation Science and Engineering, vol. 6, no. 1, pp. 9-15, Jan. 2009.
[19] B. Li and J. Wang, “Efficient anti-collision algorithm utilizing the capture effect for ISO 18000-6C RFID protocol,” IEEE Communications Letters, vol. 15, no. 3, pp. 352-354, Mar. 2011.
[20] K. W. Chiang, C. Hua, and T. S. Peter Yum, “Prefix-randomized query-tree protocol for RFID systems,” International Conference on Communications, pp. 1653-1657, Jun. 2006.
[21] G. Binetti, G. Boggia, P. Camarda, and L.A. Grieco, “A hashing-based anti-collision algorithm for RFID tag identification,” 4th International Symposium on Wireless Communication Systems, pp.524-528, Oct. 2007.
[22] J. S. Cho, J. D. Shin and S. K. Kim, “RFID tag anti-collision protocol query tree with reversed IDs,” ICACT 2008. 10th International Conference on, pp. 225-230, Mar. 2008.
[23] 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.
[24] C. N. Yang, and J. Y. He, “A effective 16-bit random number aided query tree algorithm for RFID tag anti-collision,” IEEE Communications Letters, vol. 11, no. 1, pp.85-87, Jan. 2007.