RFID系統跨層詢問反碰撞演算法之設計

The Design of a Stride Query Tree Anti-Collision Algorithm for RFID Systems

鄧嘉豪(Chia-hao Teng)

指導教授 ： 施再繁

朝陽科技大學/資訊學院/資訊工程系/碩士(2011年)

摘要

無線射頻辨識系統(Radio Frequency IDentification，RFID)在運作時，最困擾的就是訊號碰撞(Collision)問題，此問題將會造成整體系統效能降低。如何減少碰撞的問題，以提高其辨識效率是目前RFID系統極熱門的研究議題。本論文將針對RFID系統在運作時之碰撞問題提出兩種有效的解決方法。我們提出的兩種方法分別為SQT演算法(Stride Query Tree Algorithm)及MQSQT演算法(Minimal Query Set QT Algorithm)都是以Query Tree Algorithm(QT)為基礎並加以改良。其中SQT演算法將原來QT詢問標籤的方式改為跨層詢問的方式，結果顯示SQT可大幅降低詢問過程中所產生的碰撞次數，為了減少在跨層過程中帶來閒置(idle)次數過多的問題，我們也進一步修改了SQT詢問資訊的產生方式，以邏輯運算的方式找出下一個詢問節點，使整個系統能同時減少碰撞及閒置問題，此新方法稱為MQSQT，模擬結果顯示我們所提出的演算法在碰撞及閒置兩種問題上均獲得明顯的改善。

關鍵字

詢問樹演算法 ； 碰撞 ； 讀取器 ； 無線射頻辨識系統 ； 反碰撞演算法

並列摘要

During the operation of Radio frequency Identification systems (RFID), the most difficult aspect is the problem of signal collision. The collision of RFID systems results in lower efficiency. How to decrease the problem of collision so as to enhance its identification rate is the hot issue of RFID systems. In this dissertation, we propose two efficient solutions, called Stride Query Tree (SQT) and Minimal Query Set QT (MQSQT), to solve the collision problem of RFID systems respectively. All of the SQT and MQSQT are Query Tree -Based algorithms which are based on QT algorithm to improve their performance. The SQT algorithm changes the original layer-by-layer query of tags into the method of striding-layer tag query. It shows that the SQT therefore substantially decreased the collision times during querying. In order to decrease the times of idle during tag query in SQT, we proposed the MQSQT algorithm that further modified the production method of the next query string by XOR logic operation. This enables the whole system to decrease collision and idle problems in a tag identification process. The simulation results show that both problems of collision and idle were improved significantly.

並列關鍵字

Collision ； Query tree algorithm ； Reader ； RFID ； Anti-collision algorithm

參考文獻

[1] C. P. Wong and Q. Feng, “Grouping based Bit-Slot ALOHA Protocol for Tag Anti-Collision in RFID Systems,” IEEE Communications Letter, Dec. 2007, vol. 11, pp. 946-948.

[3] H. Vogt, “Efficient object identification with passive RFID tags,” Proc. of the 1st Int’l Conf., on Pervasive Computing, 2002, pp. 98-113.

[4] J. Cha and J. Kim, “Novel Anti-Collision Algorithms for Fast Object Identification in RFID System,” in Proc. of Parallel and Distributed System, Jul. 2005, vol. 2, pp. 63-67.

[5] J. H. Chio, D. Lee and H. Lee, “Bi-Slotted Tree based Anti-Collision Protocols for Fast Tag Identification in RFID Systems,” IEEE Communications Letter, Dec. 2006, vol. 10, pp. 861-863.

[6] J. Kim, W. Lee, J. Yu, J. Myung, E. Kim and C. Lee, “Effect of Localized Optimal Clustering for Reader Anti-Collision in RFID Networks: Fairness Aspects to the Readers,” Proceedings 14th International Conference on Computer Communications and Networks, Oct. 2005, vol.1, pp. 497-502.