無線射頻標籤辨識技術(RFID)被廣泛應用在自動化辨識系統中，因其與傳統條碼系統相比具有快速、便利及辨識無需接觸物體等特性。為了提高標籤辨識的速度，許多防止RFID標籤訊號碰撞的演算法被提出來解決標籤碰撞造成的問題。但傳統的防碰撞演算法並沒有考慮快速變化的通道品質，然而在通道品質不佳的環境下會造成讀取器高估碰撞時槽的數量與為解決碰撞時槽而產生的閒置時槽。因此，為了解決通道品質造成的問題，本論文提出了通道感知查詢樹演算法(CAQT)以改善在易出錯的通道下的辨識性能。CAQT具有三個新的特點：(1) 讀取器透過估計整個標籤解決程序的通道錯誤機率(PER)來提高在變化快速的通道環境下的標籤估計的準確性；(2) 為減少閒置時槽，其透過統計方式決定要採用重傳或是切割時槽進行辨識，以選擇最有效率的方式來解決碰撞時槽；(3) 為了加速辨識過程，當碰撞發生且選擇切割時槽時，會透過估計的碰撞標籤個數來分成數群進行辨識。根據模擬結果表示在易出錯的通道環境下，CAQT與其他演算法相比可以最小化降低閒置時槽數量，並減少全部辨識過程的時槽總數達31%。

The Radio Frequency Identification (RFID) technique is broadly applied as the automated identification system because its feasibility, convenience, fast and contactless objects identification compared with the conventional bar-code system. In order to accelerate the speed of tag identification process, many RFID anti-collision algorithms were proposed. These conventional algorithms did not consider the rapid changed channel quality, leading that the reader would overestimate the number of collided tags and lots of idle slots thus increased. In order to cope with this problem, this thesis proposes the Channel Aware Query Tree algorithm (CAQT) to improve the identification performance under error-prone channel. The CAQT has three novel features: (1) it estimates PER during the whole tag resolution procedure in order to improve the accuracy of the tag estimation in the rapidly changing channel quality environment; (2) it statistically adopts the most efficient strategy, which is to ask the tag to retransmit it or to split the collide tags, in order to reduce the idle slots; (3) the number of the group which it splits is based on the estimated number of tags collide in current slot in order to accelerate the tag identification process. The simulation results show that CAQT can reduce at most 31% slots used by the conventional algorithm through minimizing the idle slots during tag identification in the channel error-prone environment.

[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]J. R. Cha and J. H. Kim, “Dynamic framed slotted ALOHA algorithms using fast tag estimation method for RFID system,” IEEE Consumer Communications and Networking Conference, pp. 768-772, Jan. 2006.
[5]N. Vinod and G. Lixin, “Energy-aware tag anti-collision protocols for RFID systems,” IEEE International Conference on Pervasive Computing and Communications, pp. 33-36, May 2007.
[6]J. Park and T. J. Lee, “Error Resilient Estimation and Adaptive Binary Selection for Fast and Reliable Identification of RFID Tags in Error-prone Channel,” IEEE Transactions on Mobile Computing, vol. 11, no. 6, pp. 959-969, June 2012.
[7]L. Zhang, F. Gandino, R. Ferrero and M. Rebaudengo, “Evaluation of the Additive Interference Model for RFID Reader Collision Problem.” 2012 Fourth International EURASIP Workshop on RFID Technology, DOI: 10.1109/RFID.2012.13, Sept. 2012.
[8]L. Zhang, R. Ferrero, F. Gandino and M. Rebaudengo, “Evaluation of single and additive interference models for RFID collisions,” Mathematical and Computer Modelling(2013), DOI: 10.1016/j.mcm.2013. 01.011, Feb. 2013.
[9]H. Vogt, “Efficient object identification with passive RFID tags,” Pervasive 2002, LNCS 2414, pp. 98–113, Jan. 2002.
[10]Z. Lei and T. S. P. Yum, “The optimal reading strategy for EPC Gen-2 RFID anti-collision systems,” IEEE Transactions on Communications, vol. 58, no. 9, pp. 2725-2733, Sept. 2010.
[11]Y. Maguire and R. Pappu, “An optimal Q-Algorithm for the ISO 18000-6C RFID protocol,” IEEE Transactions on Automation Science and Engineering, pp. 16-24, Jan. 2009.
[12]Z. Lei and T. S. P. Yum, “Optimal framed aloha based anti-collision algorithms for RFID systems,” IEEE Transactions on Communications, vol. 58, no. 12, pp. 3583-3592, Dec. 2010.
[13]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.
[14]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.
[15]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.
[16]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, May 2007.
[17]C. F. Lin and F. Y. S. Lin, “Efficient estimation and collision-group-based anti-collision algorithms for dynamic frame-slotted aloha in RFID networks,” IEEE Transactions on Automation Science and Engineering, vol. 7, no. 4, pp. 840-848, Oct. 2010.
[18]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.
[19]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.
[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]H. Gou, H. C. Jeong, and Y. Yoo, “A bit collision detection based query tree protocol for anti-collision in RFID system,” IEEE 6th International Conference on Wireless and Mobile Computing, Networking and Communications, pp. 421-428, Oct. 2010.
[22]W. Zein-Elabdeen and E. Shaaban, “An enhanced binary tree anti-collision technique for dynamically added tags in RFID systems,” 2nd International Conference on Computer Engineering and Technology, pp. 349-353, Apr. 2010.
[23]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.
[24]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.
[25]V. Namboodiri and L. Gao, “Energy-aware tag anticollision protocols for RFID systems,” IEEE Transactions on Mobile Computing, vol. 9, no. 1, pp. 44-59, Jan. 2010.
[26]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.
[27]C. N. Yang and J. Y. He, “An effective 16-bit random number aided query tree algorithm for RFID tag anti-collision,” IEEE Communications Letters, vol. 15, no. 5, pp.539-541, May 2011.
[28]D. H. Shiha, P. L. Suna, D. C. Yenb, S. M. Huangc, “Taxonomy and survey of RFID anti-collision protocols”, Computer Communications, vol. 29, no. 11, pp. 2150-2166, July 2006.
[29]M. K. Yeh and J. R. Jiang, “Adaptive k-way Splitting and Pre-Signaling for RFID Tag Anti-Collision,” Industrial Electronics Society, 2007. IECON 2007. 33rd Annual Conference of the IEEE, pp. 40-45, DOI: 10.1109/ IECON.2007.4460228, Nov. 2007.
[30]M. K. Yeh, J. R. Jiang and S. T. Huang, “Adaptive splitting and pre-signaling for RFID tag anti-collision,” Computer Communications, vol. 32, no. 17, pp. 862-1870, Nov. 2009.