RFID多標簽防碰撞原理與解決方法

劉鵬 長江大學計算機科學學院， 湖北 荊州 434023

RFID多標簽防碰撞原理與解決方法

劉鵬 長江大學計算機科學學院， 湖北 荊州 434023

在射頻識別系統中, 存在閱讀器與多個標簽同時通信的碰撞問題, 多標簽識別的防碰撞算法是解決數據沖突的關鍵。本文分析了RFID多標簽防碰撞原理，在此基礎上提出了一些提高RFID多標簽防碰撞效率的解決方法。

RFID；防碰撞；二進制算法

射頻識別技術(RFID, radio frequency identification)是一種非接觸式自動識別技術，通過空間射頻信號自動獲取信息，實現無線雙向數據通信。與傳統條形碼、IC 卡等自動識別技術相比，RFID具有識別距離遠、使用壽命長、安全性高、整個識別過程無需人工干預等優點，能廣泛地應用于工業自動化、商業自動化、交通運輸控制管理、防偽、軍事等領域。

1. RFID系統的構成

RFID系統由閱讀器(interrogator)、標簽(tag)和后臺網絡3部分組成：標簽分為有源標簽和無源標簽兩大類，大多數RFID系統都采用無源標簽；閱讀器在后臺網絡系統控制下發送出一定頻率的射頻信號，當具有唯一ID號的標簽進入閱讀器磁場時會產生感應電流，從而獲得能量，標簽利用這些能量將反饋信息調制后發送回閱讀器，該信息被閱讀器解碼后送至后臺網絡系統進行處理。

2. RFID多標簽防碰撞算法分類

標簽碰撞問題是指當讀寫器向工作場區內的一組電子標簽發出查詢指令時，由于2個或2個以上的電子標簽同時響應讀寫器的查詢，返回信息產生相互干擾，從而導致讀寫器不能正確識別其中任何一個電子標簽的信息。隨著電子標簽數量的增加，發生多標簽碰撞的概率也會增加，讀寫器的識別效率將進一步下降。

目前在RFID系統當中標簽防碰撞算法主要由時分、頻分、碼分以及空分四種方法，分別利用時間，頻率碼元以及空間來達到防止RFID標簽發生碰撞的目的。其中利用最多的時分方法。它主要分為基于概率的ALOHA算法和確定的二進制算法。

ALOHA算法是基于概率的，即每個電子標簽隨即發送數據，如果有兩個以上電子標簽在同一時間發送就會產生碰撞，電子標簽等待一段時候后再發送，直到所有的電子標簽被讀取為止。該方法不受標簽ID位數的影響。ALOHA算法非常簡單，效率也不是很高，讀取電子標簽需要大量的時間。

二進制算法與基于概率的ALOHA算法不相同，它是一種確定的算法，它是現在使用最為廣泛的標簽防碰撞算法。每個電子標簽都有自己的ID號，閱讀器通過二進制算法來確定讀取電子標簽的順序。二進制算法采用遞歸的工作方式，當遇到碰撞時，分支成2個子集，這些分支越來越小，直到最后當分支下面只有一個信息包時，完成識別過程；對于給定的標簽群，二進制樹算法能預測標簽的識別順序以及過程，因此被稱為確定型算法。二進制樹算法分為有記憶型和無記憶型2種。在有記憶型算法中，標簽的反饋是由接收的指令以及標簽的當前狀態決定的，而無記憶型算法中，標簽的反饋僅由接收的指令決定，以適應低成本和低功耗的要求。

3. 防碰撞基本原理

下面以二進制防碰撞算法為例來說明RFID多標簽的防碰撞原理。閱讀器發出請求命名，將接受電子標簽發過來的標簽號，如果沒有接到ID，則沒有標簽發送，如果只有一個則不會出現標簽的碰撞，直接選擇此標簽，如果兩個以上ID號，將碰撞的最高位置為0，所有小于碰撞最高位值為1，將這個數據發送給電子標簽，電子標簽判斷是否需要應答，所有要應答的標簽發送自己的ID號給閱讀器，直到沒有碰撞，閱讀器選定要發送數據的電子標簽并且接收來自該ID號標簽的數據，電子標簽與閱讀器的通訊結束之后，閱讀器發送命令使此標簽不再對查詢名利應答，一直執行此操作直到所有標簽發送完畢。

閱讀器在識別的過程中使用了下面的指令：

(1) REQUEST指令，閱讀器發送一段ID1，標簽得到此ID1，然后與自己的lD號比較，從而判斷時候要發送自己的ID號(當ID<= ID1時)。

(2) SELECT指令，閱讀器發送ID1，當電子標簽自己的ID=ID1時候，此標簽被選中，選中的標簽與閱讀器之間進行數據的通訊。

(3)READATA指令，閱讀器得到被選中標簽的數據。

(4)UNSELECT指令，使已經發送完數據的標簽睡眠，被睡眠的標簽不再對指令做出反應。

采用這些命令，一個算法的識別過程如下：

現在假設有4個電子標簽，且他們的標簽號分別為A(11010111)，B(11100101)，C(11101111)，D(11010101)，則算法的流程為:

(1) 首先閱讀器發送REQUEST(111111l1)，4個標簽都接到此指令并發送自己的ID號，閱讀器接收ID號，可以知道在5，4，3，1為發生碰撞，其他位可以識別，得到的結果11000101，因此可以得到下一次閱讀器發送的查詢ID號應為11011111。

(2) 發送REQUEST(11011111)，標簽A，D發送11010111以及11010101，發生碰撞位可以知道是第一位，這樣下一次的查詢指令應該為11010101。

(3) 發送上一次得到的查詢指令，后只有一個標簽D滿足發送條件，這樣閱讀器就可以正確識別標簽的ID號，發送SELECT指令選中標簽D，標簽傳完數據之后，執行指令使標簽D睡眠，D不再對指令做出任何發應。

(4) 重復執行1～3，直到閱讀器沒有接受到任何ID號，這是所有的標簽被識別。

4.提高RFID防碰撞效率的方法

從上面的過程首先可以看到在過程(2)中發送的位數較多，能不能采用合適的編碼，使之包含較少的位數，又能知道碰撞發送的位置。其次，在過程(4)中，每次識別下一個標簽都從第一個過程開始查詢，能否從中間某個過程開始查詢，也能達到同樣的效果，這樣如何減少查詢次數。

算法的實現前提是標簽到閱讀器的數據傳輸選擇一種合適的編碼方法，以能夠識別出沖突的準確位置。曼徹斯特編碼滿足這樣的條件。曼徹斯特編碼是用在一個位窗內的電平的改變(上升/下降沿)來表示某一位的。當多個標簽同時發送的數據位有不同的值，則接收的上升沿和下降沿相互抵消，以致在某一個位窗之內“沒有變化”。因此通過這種方式可以識別沖突的準確位置。

標簽識別所花費的時間很大程度上取決于發生碰撞的時間(為處理發生碰撞的所有節點而花費的時間之和)。因此，通過減少發生碰撞節點的數量能夠達到提高系統識別速度的目的。

減少REQUEST的命令的位數也是一個重要的解決思路。如果在碰撞位后面所有為都被設置為1，只要知道碰撞位，并不需要傳輸碰撞位后面的數字位，如只傳送最高碰撞位以及最高碰撞位以前的數字，從而減少了傳送的數據量，相應的增加了傳送的效率，減少傳送的時間。

[1]Myung J, Lee W, Srivastava J. Adaptive binary splitting for efficient RFID tag anticollision[J]. IEEE Communications Letters,2006,10(3):144～146

[2]王雪, 錢志鴻, 胡正超等. 基于二叉樹的RFID防碰撞算法的研究[J]. 通信學報,2010,31(6):49～57

[3]馮娜，潘偉杰，李少波，楊觀賜. 基于新穎跳躍式動態搜索的RFID防碰撞算法[J].計算機應用,2012,32(1) :288～291

[4]李萌，錢志鴻，張旭，王義君. 基于時隙預測的RFID防碰撞 ALOHA 算法[J]. 通信學報,2011,32(12):43～50

10.3969/j.issn.1001-8972.2012.07.052