RFID 防碰撞算法研究

宋瑞玲，高仲合

SONG Ruiling,GAO Zhonghe

曲阜師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，山東 日照276826

College of Computer Science,Qufu Normal University,Rizhao,Shandong 276826,China

1 引言

射頻識(shí)別（Radio Frequency IDentification，RFID）是一種利用射頻信號(hào)通過(guò)空間電磁耦合實(shí)現(xiàn)無(wú)接觸式的自動(dòng)識(shí)別技術(shù)[1]。作為物聯(lián)網(wǎng)的最核心技術(shù)之一，在物聯(lián)網(wǎng)技術(shù)的引領(lǐng)下RFID 技術(shù)必將獲得越來(lái)越大的發(fā)展空間。目前，RFID 技術(shù)以其特有的設(shè)備屬性已被廣泛應(yīng)用于軍事、交通、工業(yè)、醫(yī)學(xué)以及日常生活的各個(gè)方面。

RFID 系統(tǒng)是由電子標(biāo)簽、閱讀器、數(shù)據(jù)處理子系統(tǒng)等三部分[2]組成。當(dāng)多個(gè)電子標(biāo)簽同時(shí)進(jìn)入閱讀器的閱讀范圍內(nèi)時(shí)就會(huì)產(chǎn)生信息碰撞問(wèn)題，信息碰撞使系統(tǒng)不能正常工作，導(dǎo)致誤讀和漏讀等現(xiàn)象，限制了RFID 的實(shí)際應(yīng)用。因此，需要一種防碰撞技術(shù)來(lái)解決碰撞問(wèn)題，解決碰撞的算法稱(chēng)為防碰撞算法。

RFID 防碰撞算法采用的是多路存取的防碰撞方式，主要有時(shí)分多址、頻分多址、碼分多址、空分多址[3]。在RFID 系統(tǒng)中應(yīng)用最多的是時(shí)分多址方式。而目前基于時(shí)分多址的防碰撞算法是基于aloha 的隨機(jī)型防碰撞算法和基于二進(jìn)制樹(shù)的確定型防碰撞算法。

2 RFID 防碰撞算法

2.1 基于aloha 的隨機(jī)型防碰撞算法

aloha 協(xié)議最早被用在分組無(wú)線網(wǎng)絡(luò)中實(shí)現(xiàn)隨機(jī)訪問(wèn)機(jī)制?；赼loha算法主要有純aloha算法[4]、時(shí)隙aloha算法（SA）[5-6]、幀時(shí)隙aloha算法（FSA）、動(dòng)態(tài)幀時(shí)隙aloha算法（Dynamic Frame Slotted Aloha，DFSA）[7]、自適應(yīng)動(dòng)態(tài)幀時(shí)隙，其中，DFSA 算法由于操作簡(jiǎn)單和性能良好，很多研究都是在該算法的基礎(chǔ)上進(jìn)行研究改進(jìn)的。基于aloha 機(jī)制的算法操作簡(jiǎn)單、易于實(shí)現(xiàn)，但是其性能不穩(wěn)定，識(shí)別效率不高，并且標(biāo)簽數(shù)量大時(shí)，部分標(biāo)簽在相當(dāng)長(zhǎng)的時(shí)間內(nèi)得不到識(shí)別，會(huì)出現(xiàn)“餓死”現(xiàn)象。

2.2 基于二進(jìn)制樹(shù)的確定型防碰撞算法

基于二進(jìn)制樹(shù)的算法識(shí)別效率高，避免標(biāo)簽“餓死”現(xiàn)象，但通信量大，且有相當(dāng)長(zhǎng)的時(shí)延。基于二進(jìn)制樹(shù)[8-9]的改進(jìn)算法有二進(jìn)制搜索（BS）算法、動(dòng)態(tài)二進(jìn)制搜索（DBS）算法、后退式二進(jìn)制（BBS）算法[10]、跳躍式動(dòng)態(tài)二進(jìn)制搜索（JDBS）算法。DBS 是在BS 算法基礎(chǔ)上改進(jìn)的，它避免了標(biāo)簽和閱讀器之間的冗余傳輸，但搜索次數(shù)依然很多。BBS 相對(duì)于BS 算法搜索次數(shù)有所減少，但閱讀器和標(biāo)簽之間存在大量的冗余傳輸。JDBS是由BBS 和DBS 改進(jìn)的，不但搜索次數(shù)減少，而且避免了標(biāo)簽和閱讀器之間的冗余傳輸，但是當(dāng)大量標(biāo)簽被識(shí)別時(shí)，系統(tǒng)數(shù)據(jù)傳輸量很大，性能仍需進(jìn)一步改進(jìn)。動(dòng)態(tài)調(diào)整二進(jìn)制樹(shù)形搜素算法基于一位沖突直接識(shí)別，當(dāng)只探測(cè)到一位碰撞時(shí)，可直接識(shí)別出兩個(gè)標(biāo)簽[11]。相比JDBS 進(jìn)一步減少了搜索次數(shù)，但是當(dāng)標(biāo)簽數(shù)量大，且標(biāo)簽ID 號(hào)較長(zhǎng)時(shí)，出現(xiàn)一位碰撞概率相對(duì)較低，搜索次數(shù)減少不明顯。文獻(xiàn)[12]提出的一種算法是在動(dòng)態(tài)調(diào)整算法基礎(chǔ)上改進(jìn)的，該算法通過(guò)引入分組策略，當(dāng)只有兩位碰撞位時(shí)即可直接識(shí)別，當(dāng)標(biāo)簽較多時(shí)，搜索次數(shù)減少比較明顯。本文結(jié)合以上各種算法的優(yōu)點(diǎn)提出一種具體的改進(jìn)算法。

3 改進(jìn)算法

3.1 算法的幾點(diǎn)約定

（1）算法是基于二進(jìn)制樹(shù)搜索算法提出的，要求閱讀器能夠準(zhǔn)確地識(shí)別出數(shù)據(jù)的碰撞位置，這里采用曼徹斯特編碼，該編碼約定邏輯‘1’對(duì)應(yīng)信號(hào)含下降沿跳變，邏輯‘0’對(duì)應(yīng)信號(hào)含上升沿跳變，若無(wú)狀態(tài)跳變，視為錯(cuò)誤被識(shí)別。當(dāng)兩個(gè)或多個(gè)標(biāo)簽同時(shí)返回的某一數(shù)位有不同的值，則接收到的上升沿和下降沿相互抵消，以致出現(xiàn)“沒(méi)有變化”或變化被明顯消弱的狀態(tài)，閱讀器由此可判斷該位出現(xiàn)了碰撞。

（2）標(biāo)簽內(nèi)部設(shè)置了一個(gè)計(jì)數(shù)器R 用于存儲(chǔ)標(biāo)簽ID中所有比特位的按位異或結(jié)果，R 的取值可在標(biāo)簽制造時(shí)固化寫(xiě)入，R 取值為0 和1 分別代表標(biāo)簽ID 中‘1’的個(gè)數(shù)是偶數(shù)和奇數(shù)。

（3）引入以下5 種命令描述算法：

①請(qǐng)求命令Request（nul，0），R=0組標(biāo)簽響應(yīng)；Request（nul，1），R=1 組標(biāo)簽響應(yīng)。這里還引入一個(gè)電子標(biāo)簽自身的標(biāo)簽選擇計(jì)數(shù)器Counter，初始值設(shè)為-1，標(biāo)簽響應(yīng)請(qǐng)求命令后變?yōu)?。

②請(qǐng)求命令Request(x，y)：x為檢測(cè)到的最高碰撞位；y為0/1 比特位。閱讀器向作用范圍內(nèi)的電子標(biāo)簽發(fā)送此命令，Counter=0 標(biāo)簽序列編碼第x位為y值的標(biāo)簽則響應(yīng)，將自身低于x位的序列編碼傳送各閱讀器；其余未進(jìn)入休眠狀態(tài)的電子標(biāo)簽將自身的Counter加1。

③選擇命令Select（ID）：選擇標(biāo)簽。

④讀命令Read（ID）：讀取標(biāo)簽信息。

⑤去選擇Unselect（ID）：使標(biāo)簽進(jìn)入休眠狀態(tài)。

3.2 算法思路

（1）閱讀器發(fā)出請(qǐng)求命令Request（nul，0），其作用范圍內(nèi)的所有R=0 組標(biāo)簽響應(yīng)請(qǐng)求命令并將自身ID 發(fā)給閱讀器，該組標(biāo)簽的標(biāo)簽選擇計(jì)數(shù)器Counter=0。

（2）閱讀器對(duì)這些序列編碼解碼，如果碰撞位超過(guò)2則轉(zhuǎn)到第（3）步；若沒(méi)有碰撞或只有2 位碰撞時(shí)，閱讀器即可成功識(shí)別出標(biāo)簽：

①如果不存在碰撞直接識(shí)別，轉(zhuǎn)到（4）。

②當(dāng)存在兩個(gè)標(biāo)簽碰撞位時(shí)，閱讀器通過(guò)奇偶校驗(yàn)位即可準(zhǔn)確地識(shí)別出兩個(gè)標(biāo)簽的序列編碼，轉(zhuǎn)到（4）。

（3）記錄最高碰撞位x，最高碰撞位之前的序列壓入堆棧記錄。閱讀器向其作用范圍內(nèi)的標(biāo)簽發(fā)送Request(x，0)命令，標(biāo)簽選擇計(jì)數(shù)器Counter=0 的標(biāo)簽序列編碼第x位為0 值響應(yīng)，并將自身低于x位的序列編碼傳送給閱讀器；其余未進(jìn)入休眠狀態(tài)的R=0 組的電子標(biāo)簽將自身的Counter加1，轉(zhuǎn)到（2）。

（4）讀寫(xiě)器對(duì)識(shí)別的標(biāo)簽相繼發(fā)出Select、Read 和Unselect 命令，完成對(duì)標(biāo)簽的讀寫(xiě)并使之進(jìn)入休眠狀態(tài)。所有未進(jìn)入休眠狀態(tài)R=0 組的標(biāo)簽的Counter 減1。返回上一次碰撞節(jié)點(diǎn)，閱讀器發(fā)出Request(x，1)的命令，標(biāo)簽選擇計(jì)數(shù)器Counter=0 的標(biāo)簽序列編碼第x位為1 值則響應(yīng)，將自身低于x位的序列編碼傳送個(gè)閱讀器；其余未進(jìn)入休眠狀態(tài)的R=0 組的電子標(biāo)簽將自身的Counter加1，轉(zhuǎn)入（2）。

（5）重復(fù)以上步驟，直到對(duì)R=0 組標(biāo)簽全部識(shí)別，然后以同樣的方法識(shí)別R=1 組標(biāo)簽。

3.3 算法舉例

假設(shè)閱讀器范圍內(nèi)有6 個(gè)標(biāo)簽，各標(biāo)簽的編碼A：10100000 B：10000100 C：10010000 D：10001000 E：00000001 F：00001000

（1）閱讀器發(fā)出Request（nul，0）命令，其作用范圍內(nèi)A、B、C、D 響應(yīng)并將自身ID 發(fā)給閱讀器，Counter（A、B、C、D）=0。

（2）閱讀器對(duì)這些序列編碼解碼為10????00，最高碰撞位5，最高碰撞位之前的‘10’序列壓入堆棧。閱讀器向作用范圍內(nèi)的標(biāo)簽發(fā)送Request（5，0），這時(shí)R=0 組內(nèi)的B、C、D 響應(yīng)，并把低于第5 位的序列編碼傳送給閱讀器；而R=0 組內(nèi)A 的Counter值加1。

（3）閱讀器對(duì)這些序列編碼解碼為???00，最高碰撞位4，閱讀器再次向作用范圍內(nèi)的標(biāo)簽發(fā)送Request（4，0），B、D 響應(yīng)，將自身低于第4 位的序列編碼傳送個(gè)閱讀器，A、C 的Counter加1。

（4）閱讀器對(duì)這些序列編碼解碼為??00，所以B、D直接被識(shí)別。

（5）閱讀器對(duì)B、D 標(biāo)簽完成讀寫(xiě)并使之進(jìn)入休眠狀態(tài)。R=0 組內(nèi)A、C 的Counter減1。

（6）閱讀器再次向作用范圍內(nèi)的標(biāo)簽發(fā)送Request（4，1），只有C 標(biāo)簽響應(yīng)，被識(shí)別。

（7）閱讀器對(duì)C 標(biāo)簽完成讀寫(xiě)并使之進(jìn)入休眠狀態(tài)。R=0 組內(nèi)A 的Counter 減1。閱讀器發(fā)出Request（5，1）命令，只有A 響應(yīng)，直接識(shí)別。R=0 組標(biāo)簽全部被識(shí)別。

（8）閱讀器發(fā)送Request（nul，1）命令，R=1 組內(nèi)的E、F 響應(yīng)，返回自身ID。

（9）閱讀器對(duì)這些序列編碼解碼為0000?00?，只有兩位碰撞所以直接被識(shí)別。

標(biāo)簽的識(shí)別過(guò)程如圖1 所示。

圖1 改進(jìn)算法的標(biāo)簽識(shí)別過(guò)程

4 算法性能分析及仿真

對(duì)算法性能進(jìn)行分析時(shí)主要考慮識(shí)別出所有標(biāo)簽時(shí)命令發(fā)送的總次數(shù)，命令參數(shù)長(zhǎng)度和標(biāo)簽響應(yīng)數(shù)據(jù)長(zhǎng)度，等效分析識(shí)別出所有標(biāo)簽時(shí)命令發(fā)送的總次數(shù)，閱讀器發(fā)送數(shù)據(jù)量和標(biāo)簽發(fā)送數(shù)據(jù)量。

4.1 識(shí)別標(biāo)簽所需搜索次數(shù)

（1）后退式二進(jìn)制搜索算法

識(shí)別閱讀器范圍內(nèi)的N個(gè)標(biāo)簽所需要總的搜索次數(shù)[13]：

（2）分組策略

本算法基于動(dòng)態(tài)調(diào)整算法，通過(guò)設(shè)置一位奇偶校驗(yàn)寄存器實(shí)現(xiàn)分組，在識(shí)別過(guò)程中檢測(cè)到只有兩位碰撞位時(shí)即能直接識(shí)別標(biāo)簽，減少了搜索次數(shù)。

假設(shè)在識(shí)別過(guò)程中檢測(cè)到M次只有2 個(gè)比特位發(fā)生碰撞時(shí)，采用本算法相當(dāng)于在二叉樹(shù)上減少了M個(gè)葉子節(jié)點(diǎn)，即搜索次數(shù)減少了2M次。

算法的搜索次數(shù)為：

特別地，當(dāng)用ID 數(shù)位中的n位來(lái)表示2n個(gè)標(biāo)簽時(shí)，這時(shí)候搜索次數(shù)是2n-2。

這里取ID長(zhǎng)度是64 bit借助Matlab工具對(duì)使用分組后不同數(shù)目標(biāo)簽對(duì)應(yīng)搜索次數(shù)進(jìn)行統(tǒng)計(jì)，如表1 所示。

表1 不同數(shù)目標(biāo)簽對(duì)應(yīng)搜索次數(shù)

4.2 閱讀器和標(biāo)簽之間的通信量

（1）標(biāo)簽發(fā)送總的通信量

JDS算法識(shí)別過(guò)程中，標(biāo)簽每次發(fā)送的數(shù)據(jù)平均長(zhǎng)度[14]：

其中L是ID 號(hào)長(zhǎng)度。

本文算法是基于JDS算法提出的，所以標(biāo)簽的通信量：

（2）閱讀器發(fā)送的數(shù)據(jù)量

本算法中發(fā)送請(qǐng)求命令的第一個(gè)參數(shù)是最高碰撞位信息，與編碼長(zhǎng)度L 無(wú)關(guān)，與最高碰撞位P 有關(guān)，標(biāo)簽發(fā)送的二進(jìn)制編碼長(zhǎng)度為[15]，得出本算法傳輸?shù)亩M(jìn)制數(shù)據(jù)量：

標(biāo)簽閱讀器之間總的數(shù)據(jù)通信量：

4.3 算法仿真

在Matlab 仿真平臺(tái)上對(duì)本算法、動(dòng)態(tài)調(diào)整二進(jìn)制搜索算法、跳躍式動(dòng)態(tài)二進(jìn)制搜（JDBS）和基于后退策略的二進(jìn)制搜索算法進(jìn)行仿真比較。仿真實(shí)驗(yàn)中編碼位數(shù)n取64。

圖2是本文算法、動(dòng)態(tài)調(diào)整二進(jìn)制搜索算法、跳躍式動(dòng)態(tài)二進(jìn)制搜索（JDBS）和基于后退策略的二進(jìn)制搜索算法閱讀器進(jìn)行搜索次數(shù)的比較。由圖2 可以看出本算法相對(duì)其他算法搜索次數(shù)最少，當(dāng)標(biāo)簽數(shù)目越多時(shí)本算法的優(yōu)勢(shì)越明顯，這是因?yàn)楸舅惴ㄍㄟ^(guò)分組可以減少碰撞概率，并且僅有兩位碰撞即可識(shí)別減少了搜索次數(shù)。

圖2 不同算法搜索次數(shù)比較

圖3～圖5 是本算法、動(dòng)態(tài)調(diào)整二進(jìn)制搜索算法、跳躍式動(dòng)態(tài)二進(jìn)制搜索（JDBS）和基于后退策略的二進(jìn)制搜索算法標(biāo)簽數(shù)據(jù)通信量、閱讀器數(shù)據(jù)通信量以及閱讀器和標(biāo)簽之間傳輸總的數(shù)據(jù)量進(jìn)行的仿真結(jié)果。

圖3 標(biāo)簽數(shù)據(jù)通信量

圖4 閱讀器數(shù)據(jù)通信量

圖3 表明算法標(biāo)簽數(shù)據(jù)通信量最少的直接原因是搜索次數(shù)減少。圖4 表明算法閱讀器數(shù)據(jù)通信量最少的原因不但是搜索次數(shù)少，還有就是算法中發(fā)送請(qǐng)求命令的第一個(gè)參數(shù)是僅最高碰撞位信息也使數(shù)據(jù)通信量大大減少。圖5 閱讀器數(shù)據(jù)通信量和標(biāo)簽閱讀器之間總的數(shù)據(jù)通信量取決于閱讀器數(shù)據(jù)通信量和標(biāo)簽數(shù)據(jù)通信量，閱讀器數(shù)據(jù)通信量和標(biāo)簽數(shù)據(jù)通信量的減少必然會(huì)使閱讀器數(shù)據(jù)通信量和標(biāo)簽閱讀器之間總的數(shù)據(jù)通信量減少，由圖5 可以看出算法閱讀器和標(biāo)簽之間傳輸總的數(shù)據(jù)量相比JDBS 減少量約50%，并且隨著標(biāo)簽數(shù)目的增多減少量更明顯，遠(yuǎn)多于50%。

圖5 閱讀器和標(biāo)簽之間傳輸總的數(shù)據(jù)量

5 結(jié)束語(yǔ)

本文是基于二進(jìn)制搜索算法提出的一種具體的改進(jìn)算法，該算法在動(dòng)態(tài)調(diào)整算法基礎(chǔ)上通過(guò)設(shè)置奇偶計(jì)數(shù)器來(lái)實(shí)現(xiàn)分組，一次搜索過(guò)程中所有響應(yīng)的標(biāo)簽計(jì)數(shù)器R 值都相等，等效于每個(gè)響應(yīng)標(biāo)簽ID 的‘1’的個(gè)數(shù)有相同的奇偶性，所以一次搜索過(guò)程中只有兩次比特位發(fā)生沖突可以直接識(shí)別，分組進(jìn)一步減少了閱讀器的搜索次數(shù)。引入堆棧存放數(shù)據(jù)使請(qǐng)求命令參數(shù)簡(jiǎn)化得以實(shí)現(xiàn)，使閱讀器數(shù)據(jù)通信量減少。通過(guò)仿真實(shí)驗(yàn)驗(yàn)證該算法具有明顯的優(yōu)越性。

[1] 張學(xué)軍，王緒海，蔡文琦.基于分組碼的改進(jìn)型防碰撞算法研究[J].計(jì)算機(jī)應(yīng)用研究，2012，29（11）：4265-4268.

[2] Ali K，Hassanein H，Tana A E M.RFID anti-collision protocol for dense passive tag environments[C]//Proceedings of the 32nd IEEE Conference on Local Compute Networks.Washington DC：IEEE Computer Society，2007：819-824.

[3] 朱軍，張?jiān)?，盧小冬，等.基于分段搜索的多RFID 標(biāo)簽抗沖突方法倡[J].計(jì)算機(jī)應(yīng)用研究，2011，28（3）：1031-1033.

[4] Abramson N.THE ALOHA SYSTEM：another alternative for computer communications[C]//Proceedings of the November 17-19，1970，F(xiàn)all Joint Computer Conference.ACM，1970：281-285.

[5] Maguire Y，Pappu R.An optimal Q-algorithm for the ISO 18000-6C RFID protocol[J].IEEE Transactions on Automation Science and Engineering，2009，6（1）：16-24.

[6] Finkenzeller K.RFID handbook fundamentals and applications in contactless smart cards and identification[M].2nd ed.West Sussex：John Wiley & Sons Ltd，2003.

[7] Vogt H.Efficient object identification with passive RFID tags[C]//Proceedings of IEEE International Conference on System，Man and Cybernetics，2002：651-656.

[8] Chen Z，Liao M.An enhanced dynamic binary anti-collision algorithm[C]//2010 5th International Conference on Computer Science and Education（ICCSE），IEEE，2010：961-964.

[9] Chen Y H，Horng S J，Run R S，et al.A novel anti-collision algorithm in RFID systems for identifying passive tags[J].IEEE Transaction on Industrial Information，2010，6（1）：105-121.

[10] Ryu J，Lee H，Seok Y，et al.A hybrid query tree protocol for tag collision arbitration in RFID systems[C]//IEEE International Conference on Communications，2007：5981-5986.

[11] 謝振華，賴(lài)聲禮，陳鵬.標(biāo)簽防沖撞算法設(shè)計(jì)[J].計(jì)算機(jī)工程，2008，34（6）：90-92.

[12] 伍繼雄，江岸，黃生葉，等.RFID 系統(tǒng)中二叉樹(shù)防碰撞算法性能的提升[J].湖南大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，37（12）：82-86.

[13] 王雪，錢(qián)志鴻，胡正超，等.基于二叉樹(shù)的RFID 防碰撞算法的研究[J].通信學(xué)報(bào)，2010，31（6）：49-57.

[14] 王亞奇，蔣國(guó)平.基于分組機(jī)制的跳躍式動(dòng)態(tài)二進(jìn)制防碰撞算法[J].自動(dòng)化學(xué)報(bào)，2010，36（10）：1390-1400.

[15] 吳躍前，辜大光，范振粵，等.RFID 系統(tǒng)防碰撞算法比較分析及其改進(jìn)算法[J].計(jì)算機(jī)工程與應(yīng)用，2009，45（3）：210-213.