RFID防碰撞算法的研究

秦連芃， 王 喆

（蘭州交通大學電子與信息工程學院 蘭州 730070）

0 引言

射頻識別技術（Radio Frequency Identification,RFID）是一種非接觸式的自動識別技術，它通過射頻信號自動識別目標對象并獲取相關數據，識別過程無須人工干預，可工作于各種惡劣的環境。RFID領域處于物聯網發展的最前端，也是實現物聯網的基礎技術之一[1]。

RFID系統主要包括標簽（Tag）和讀寫器（Reader）兩部分。標簽適用于對象身份識別，它的主要模塊集成在一個芯片中，芯片內存用來存儲ID或其他數據。讀寫器主要由一個RF模塊和控制單元組成，通常有內置天線，通過射頻信號與標簽通信，標簽將自身ID號發送給讀寫器，達到身份識別的目的。閱讀器作用范圍內存在多個標簽，同一時刻有兩個或以上的標簽向讀寫器返回信息時，將產生沖突，稱為標簽沖突。這個沖突被稱為碰撞（collision），其結果將會導致一次傳輸的失敗。為了解決上述問題而產生了防碰撞算法。

1 防碰撞算法

RFID防碰撞算法在廣義上可分為碼分多址（Code Domain Multiple Access，CDMA）、頻分多址（Frequency Domain Multiple Access，FDMA）、時分多址（Time Domain Multiple Access，TDMA），以及空分多址（Space Domain Multiple Access，SDMA）4大類。目前在RFID系統中應用最多、種類最廣的算法是基于TDMA的防碰撞算法。RFID防碰撞算法又可以分為確定性算法和非確定性算法2大類[2]。如圖1所示。

表1對非確定性防碰撞算法與確定性防碰撞算法進行了比較，列出各自的優缺點。

圖1 RFID防碰撞算法分類

表1 非確定性防碰撞算法與確定性防碰撞算法比較

2 非確定性防碰撞算法分析與仿真

非確定性防碰撞算法主要是在Aloha算法基礎上的研究與改進，其基本原理是不同標簽在不同的時隙發送識別編碼，達到防碰撞的目的。其中包括純ALOHA算法（Pure ALOHA，PA），時隙ALOHA算法（Slotted Aloha，SA），幀時隙ALOHA算法（Frame Slotted Aloha，FSA）及動態幀時隙ALOHA算法（Dynamic Frame Slotted Aloha，DFSA）。

PA算法是所有多路存取中最簡單的一種方法，在閱讀器作用范圍內的標簽隨機產生應答時間。

SA算法是在PA算法的基礎上，將信道分成若干時隙，標簽只在規定的同步時隙內傳輸數據包，因此沖突只在時隙邊界處才會發生。

FSA算法是在SA算法的基礎上，將多個時隙組成一幀，標簽在每一幀內隨機選擇一個時隙發送自己的數據信息。

DFSA算法通過估算閱讀器作用范圍內的標簽數目動態地調整幀的長度，以求在減少沖突標簽和避免空閑時隙之間尋找平衡點。

表2為非確定性防碰撞算法吞吐率計算公式及最大吞吐率的比較。

表2 非確定性防碰撞算法比較

表2中S為吞吐率，G為輸入負載即系統交換的數據包量，n為讀寫器識別范圍內的標簽數，N為時隙數。其中動態幀時隙ALOHA算法的N是根據讀寫器識別范圍內的標簽數n不同而變化的。圖2為非確定性防碰撞算法的仿真。

圖2 非確定性防碰撞算法仿真

從圖2中可以看出非確定性防碰撞算法對系統的利用率不高，理想狀態下也只能達到36.8%。

3 確定性防碰撞算法分析與仿真

由于非確定性防碰撞算法無法保證在規定時間內完成閱讀器作用范圍里所有的標簽的辯識，且信道利用率也較低，因此，對于希望識別率達到100%應用，尤其是在超高頻段環境下，往往采用確定性的防碰撞算法。確定性防碰撞算法主要是基于樹形的算法，包括樹形分裂（Tree splitting，TS）算法、詢問樹（Query Tree，QT）算法、二進制搜索（Binary search，BS）算法及按位仲裁（Bit wise arbitration，BTA）算法。

TS算法基本思想是當碰撞發生時，采用隨機方式將標簽分成若干子組，分組數目會不斷增加直到每組內僅包含一個標簽。TS算法中的每個標簽都要一個隨機數產生器和一個計數器以追蹤其在樹上的位置，這增加了標簽成本及計算復雜度。

QT算法則是將所有復雜運算交由閱讀器處理，標簽始終處于“無記憶”狀態，僅需包含一個前綴匹配電路。該協議無需時隙劃分，無須內存且能耗很小，但在標簽位數較長時搜索范圍很大，因此其應用受到一定限制。

在BS算法中，標簽的序列號必須采用曼徹斯特編碼。閱讀器根據已接收到的來自標簽的應答，找到碰撞位，并據此向它們發送不同的請求信號或命令，采用二叉樹查找的方法，從作用范圍內的標簽中篩選出唯一一個標簽進行通信。

BTA算法是按位對標簽編碼進行詢問，其關鍵是所有標簽同步發送位信息，當閱讀器發現某一位有多個標簽發生碰撞，則將從該位入手，對標簽編碼進行進一步分析。

表3為確定性防碰撞算法的比較。

表3 確定性防碰撞算法比較

表3中mi為第i組的標簽數，n為總標簽數，k為標簽長度。圖3為確定性防碰撞算法的仿真。

圖3 確定性防碰撞算法仿真

從圖3中可以看出確定性防碰撞算法隨著標簽數量的增加，閱讀器對標簽的搜索次數將急劇增加，這嚴重影響了讀取速度。

4 結束語

非確定性防碰撞算法識別速度快，缺點是識別率低；確定性防碰撞算法識別率高，但當標簽數量比較大時識別速度慢。在實際應用中，RFID系統必須在高誤碼率環境下，以最快的速度無漏讀地識別大量標簽。這就需要結合兩種算法的優點設計一種新的算法，提高RFID系統識別速度和標簽讀取率。

[1]周曉光,王曉華.射頻識別(RFID)技術原理與應用實例[M].北京:人民郵電出版社,2006.

[2]譚民,劉禹,曾雋芳,等.RFID技術系統工程及應用指南[M].北京:機械工業出版社,2007.

[3]于潔瀟.基于RFID的情境感知關鍵技術研究[D].天津:天津大學,2010.

[4]崔沂峰,陳平.RFID電子標簽防碰撞算法的研究[J].微計算機信息,2007(27):233-244.

[5]張剛建,鄒傳云.RFID系統防碰撞協議的研究[J].電子技術應用,2010(12).

[6]李寶山,羅春青.RFID防碰撞算法計算機仿真模型的研究[J].自動化與儀器儀表,2010(05).

[7]中華人民共和國科學技術部等十五部委.中國射頻識別(RFID)技術政策白皮書[R].北京:中華人民共和國科學技術部等十五部委,2006.

[8]EPC global.Electronic product code [OL].http://www.epcglobalinc.org/home/.

[9]ISO.RFID Standards [OL].http://www.iso.org/iso/search.htm?qt=RFID&published=on&active tab=standards.

[10]Dheeraj K.Klair, Kwan-Wu Chin, Raad.A Survey and Tutorial of RFID Anti-Collision Protocols[J].IEEE Communications Surveys&Tutorials,Third Quarter,2010,12(3):400-420.

[11]J.Myung, W.Lee, J.Srivastava.Adaptive binary splitting for efficient RFIDtag anti-collision[J].IEEE Personal Commun.Mag,2006,10(3):144-146.