RFID多標(biāo)簽防碰撞原理與解決方法

劉鵬 長(zhǎng)江大學(xué)計(jì)算機(jī)科學(xué)學(xué)院， 湖北 荊州 434023

RFID多標(biāo)簽防碰撞原理與解決方法

劉鵬 長(zhǎng)江大學(xué)計(jì)算機(jī)科學(xué)學(xué)院， 湖北 荊州 434023

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

RFID；防碰撞；二進(jìn)制算法

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

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

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

2. RFID多標(biāo)簽防碰撞算法分類

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

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

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

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

3. 防碰撞基本原理

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

閱讀器在識(shí)別的過(guò)程中使用了下面的指令：

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

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

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

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

采用這些命令，一個(gè)算法的識(shí)別過(guò)程如下：

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

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

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

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

(4) 重復(fù)執(zhí)行1～3，直到閱讀器沒(méi)有接受到任何ID號(hào)，這是所有的標(biāo)簽被識(shí)別。

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

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

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

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

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

[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]王雪, 錢志鴻, 胡正超等. 基于二叉樹(shù)的RFID防碰撞算法的研究[J]. 通信學(xué)報(bào),2010,31(6):49～57

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

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

10.3969/j.issn.1001-8972.2012.07.052