可回溯位元競爭式之無線射頻辨識系統反碰撞演算法

An Retentive Backtracking Bit Competed Anti-Collision Algorithm for RFID Systems

莊堡凱(Pao-Kai Chuang)

指導教授 ： 施再繁

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

摘要

在無線射頻辨識(Radio Frequency Identification, RFID)系統中，讀取器(Reader)與標籤(Tag)相互溝通的過程，若讀取器同時接收到多個標籤之回覆訊息將發生碰撞。由於碰撞次數的增加，會使得讀取器詢問次數和傳輸資料量劇增，進而導致系統整體效能降低，本論文主要著重在標籤碰撞的議題上，我們所提出反碰撞演算法(Retentive Backtracking Bit Competed Anti-Collision Algorithm, RBBCA)可有效減少標籤回應讀取器時發生之碰撞次數。在RBBCA演算法中，讀取器會將競爭過程失敗標籤的競爭資訊記錄於堆疊中，若有多個標籤同時競爭，在每次成功辨識一個標籤後，僅需從堆疊抓取競爭資訊(即前次競爭失敗標籤的UID和下一個競爭位元的位置)從前次競爭停駐點繼續進行辨識，不但不需重頭詢問標籤UID(Unique Identification)可減少資料傳輸量，同時也減少參與競爭的標籤數，因此可大幅減少碰撞發生率和詢問次數。將我們的反碰撞演算法和其它演算法以電腦模擬進行效能評估，結果顯示無論在碰撞次數、詢問次數、標籤辨識率、讀取器計算量、請求及回應總位元數的額外負擔(overhead)等均可獲得有效改善。

關鍵字

讀取器 ； 碰撞 ； 唯一識別碼 ； 反碰撞演算法 ； 無線射頻辨識系統

並列摘要

In the process of communication between reader and tag in Radio Frequency Identification systems (RFID), collisions occur when the reader simultaneously receives reply messages from multiple tags. Reader request frequency and transmitted overhead both increase sharply as the number of collisions increases, thus, the overall efficiency of the system decreases. In this study, we proposed an retentive backtracking bit competed anti-collision algorithm (RBBCA) to effectively reduce the number of collisions when a tag responds to the reader. In the RBBCA algorithm, the reader identifies the competitive information of the process, which it will be pushed in the stack. If there are multiple competing tags, once a tag is successfully identified, the competitive information (i.e. UID of the previous competition failure tag and the position of next competitive bit) can be pop from the stack, and identification proceeds from the previous competition stop point, thus, there is no need to re-inquire tag Unique Identification (UID). Data transmission volume can be thus reduced. The efficiency of the proposed anti-collision algorithm and other algorithms were evaluated through computer simulation. The results showed that the collision number, request number, identification rate, reader calculation amount, and request-response number (overhead) were effectively improved.

並列關鍵字

Anti-Collision algorithm ； UID ； RFID ； Reader ； Collision

參考文獻

[5] 張晴翔、王偉驎，RFID無線射頻辨識系統，滄海書局，2007。

[1] 許文力，無線射頻辨識系統預防碰撞演算法之設計，碩士論文，朝陽科技 大學資訊工程系，台中，2009。

[2] 鄧嘉豪，RFID跨層詢問反碰撞演算法之設計，碩士論文，朝陽科技大學資訊工程系，台中，2010。

[7] D. Shih, P. L. Sun, D. C. Yen, and S. M. Huang, “Taxonomy and survey of RFID anti-collision protocols,” Computer and Communications, Jul 2006, vol.29, pp. 2150–2166.

[8] D. K. Klair, K. W. Chin, and R. Raad, “A Survey and Tutorial of RFID Anti-Collision Protocol,” Communications Surveys & Tutorials, Apr 2010, vol.12, pp. 400–421.