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

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

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

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

RFID；防碰撞；二進制算法

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

1. RFID系統(tǒng)的構成

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

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

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

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

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

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

3. 防碰撞基本原理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[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]馮娜，潘偉杰，李少波，楊觀賜. 基于新穎跳躍式動態(tài)搜索的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