RFID 防碰撞算法研究

宋瑞玲，高仲合

SONG Ruiling,GAO Zhonghe

曲阜師范大學 計算機科學學院，山東 日照276826

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

1 引言

射頻識別（Radio Frequency IDentification，RFID）是一種利用射頻信號通過空間電磁耦合實現無接觸式的自動識別技術[1]。作為物聯網的最核心技術之一，在物聯網技術的引領下RFID 技術必將獲得越來越大的發展空間。目前，RFID 技術以其特有的設備屬性已被廣泛應用于軍事、交通、工業、醫學以及日常生活的各個方面。

RFID 系統是由電子標簽、閱讀器、數據處理子系統等三部分[2]組成。當多個電子標簽同時進入閱讀器的閱讀范圍內時就會產生信息碰撞問題，信息碰撞使系統不能正常工作，導致誤讀和漏讀等現象，限制了RFID 的實際應用。因此，需要一種防碰撞技術來解決碰撞問題，解決碰撞的算法稱為防碰撞算法。

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

2 RFID 防碰撞算法

2.1 基于aloha 的隨機型防碰撞算法

aloha 協議最早被用在分組無線網絡中實現隨機訪問機制。基于aloha算法主要有純aloha算法[4]、時隙aloha算法（SA）[5-6]、幀時隙aloha算法（FSA）、動態幀時隙aloha算法（Dynamic Frame Slotted Aloha，DFSA）[7]、自適應動態幀時隙，其中，DFSA 算法由于操作簡單和性能良好，很多研究都是在該算法的基礎上進行研究改進的。基于aloha 機制的算法操作簡單、易于實現，但是其性能不穩定，識別效率不高，并且標簽數量大時，部分標簽在相當長的時間內得不到識別，會出現“餓死”現象。

2.2 基于二進制樹的確定型防碰撞算法

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

3 改進算法

3.1 算法的幾點約定

（1）算法是基于二進制樹搜索算法提出的，要求閱讀器能夠準確地識別出數據的碰撞位置，這里采用曼徹斯特編碼，該編碼約定邏輯‘1’對應信號含下降沿跳變，邏輯‘0’對應信號含上升沿跳變，若無狀態跳變，視為錯誤被識別。當兩個或多個標簽同時返回的某一數位有不同的值，則接收到的上升沿和下降沿相互抵消，以致出現“沒有變化”或變化被明顯消弱的狀態，閱讀器由此可判斷該位出現了碰撞。

（2）標簽內部設置了一個計數器R 用于存儲標簽ID中所有比特位的按位異或結果，R 的取值可在標簽制造時固化寫入，R 取值為0 和1 分別代表標簽ID 中‘1’的個數是偶數和奇數。

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

①請求命令Request（nul，0），R=0組標簽響應；Request（nul，1），R=1 組標簽響應。這里還引入一個電子標簽自身的標簽選擇計數器Counter，初始值設為-1，標簽響應請求命令后變為0。

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

③選擇命令Select（ID）：選擇標簽。

④讀命令Read（ID）：讀取標簽信息。

⑤去選擇Unselect（ID）：使標簽進入休眠狀態。

3.2 算法思路

（1）閱讀器發出請求命令Request（nul，0），其作用范圍內的所有R=0 組標簽響應請求命令并將自身ID 發給閱讀器，該組標簽的標簽選擇計數器Counter=0。

（2）閱讀器對這些序列編碼解碼，如果碰撞位超過2則轉到第（3）步；若沒有碰撞或只有2 位碰撞時，閱讀器即可成功識別出標簽：

①如果不存在碰撞直接識別，轉到（4）。

②當存在兩個標簽碰撞位時，閱讀器通過奇偶校驗位即可準確地識別出兩個標簽的序列編碼，轉到（4）。

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

（4）讀寫器對識別的標簽相繼發出Select、Read 和Unselect 命令，完成對標簽的讀寫并使之進入休眠狀態。所有未進入休眠狀態R=0 組的標簽的Counter 減1。返回上一次碰撞節點，閱讀器發出Request(x，1)的命令，標簽選擇計數器Counter=0 的標簽序列編碼第x位為1 值則響應，將自身低于x位的序列編碼傳送個閱讀器；其余未進入休眠狀態的R=0 組的電子標簽將自身的Counter加1，轉入（2）。

（5）重復以上步驟，直到對R=0 組標簽全部識別，然后以同樣的方法識別R=1 組標簽。

3.3 算法舉例

假設閱讀器范圍內有6 個標簽，各標簽的編碼A：10100000 B：10000100 C：10010000 D：10001000 E：00000001 F：00001000

（1）閱讀器發出Request（nul，0）命令，其作用范圍內A、B、C、D 響應并將自身ID 發給閱讀器，Counter（A、B、C、D）=0。

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

（3）閱讀器對這些序列編碼解碼為???00，最高碰撞位4，閱讀器再次向作用范圍內的標簽發送Request（4，0），B、D 響應，將自身低于第4 位的序列編碼傳送個閱讀器，A、C 的Counter加1。

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

（5）閱讀器對B、D 標簽完成讀寫并使之進入休眠狀態。R=0 組內A、C 的Counter減1。

（6）閱讀器再次向作用范圍內的標簽發送Request（4，1），只有C 標簽響應，被識別。

（7）閱讀器對C 標簽完成讀寫并使之進入休眠狀態。R=0 組內A 的Counter 減1。閱讀器發出Request（5，1）命令，只有A 響應，直接識別。R=0 組標簽全部被識別。

（8）閱讀器發送Request（nul，1）命令，R=1 組內的E、F 響應，返回自身ID。

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

標簽的識別過程如圖1 所示。

圖1 改進算法的標簽識別過程

4 算法性能分析及仿真

對算法性能進行分析時主要考慮識別出所有標簽時命令發送的總次數，命令參數長度和標簽響應數據長度，等效分析識別出所有標簽時命令發送的總次數，閱讀器發送數據量和標簽發送數據量。

4.1 識別標簽所需搜索次數

（1）后退式二進制搜索算法

識別閱讀器范圍內的N個標簽所需要總的搜索次數[13]：

（2）分組策略

本算法基于動態調整算法，通過設置一位奇偶校驗寄存器實現分組，在識別過程中檢測到只有兩位碰撞位時即能直接識別標簽，減少了搜索次數。

假設在識別過程中檢測到M次只有2 個比特位發生碰撞時，采用本算法相當于在二叉樹上減少了M個葉子節點，即搜索次數減少了2M次。

算法的搜索次數為：

特別地，當用ID 數位中的n位來表示2n個標簽時，這時候搜索次數是2n-2。

這里取ID長度是64 bit借助Matlab工具對使用分組后不同數目標簽對應搜索次數進行統計，如表1 所示。

表1 不同數目標簽對應搜索次數

4.2 閱讀器和標簽之間的通信量

（1）標簽發送總的通信量

JDS算法識別過程中，標簽每次發送的數據平均長度[14]：

其中L是ID 號長度。

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

（2）閱讀器發送的數據量

本算法中發送請求命令的第一個參數是最高碰撞位信息，與編碼長度L 無關，與最高碰撞位P 有關，標簽發送的二進制編碼長度為[15]，得出本算法傳輸的二進制數據量：

標簽閱讀器之間總的數據通信量：

4.3 算法仿真

在Matlab 仿真平臺上對本算法、動態調整二進制搜索算法、跳躍式動態二進制搜（JDBS）和基于后退策略的二進制搜索算法進行仿真比較。仿真實驗中編碼位數n取64。

圖2是本文算法、動態調整二進制搜索算法、跳躍式動態二進制搜索（JDBS）和基于后退策略的二進制搜索算法閱讀器進行搜索次數的比較。由圖2 可以看出本算法相對其他算法搜索次數最少，當標簽數目越多時本算法的優勢越明顯，這是因為本算法通過分組可以減少碰撞概率，并且僅有兩位碰撞即可識別減少了搜索次數。

圖2 不同算法搜索次數比較

圖3～圖5 是本算法、動態調整二進制搜索算法、跳躍式動態二進制搜索（JDBS）和基于后退策略的二進制搜索算法標簽數據通信量、閱讀器數據通信量以及閱讀器和標簽之間傳輸總的數據量進行的仿真結果。

圖3 標簽數據通信量

圖4 閱讀器數據通信量

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

圖5 閱讀器和標簽之間傳輸總的數據量

5 結束語

本文是基于二進制搜索算法提出的一種具體的改進算法，該算法在動態調整算法基礎上通過設置奇偶計數器來實現分組，一次搜索過程中所有響應的標簽計數器R 值都相等，等效于每個響應標簽ID 的‘1’的個數有相同的奇偶性，所以一次搜索過程中只有兩次比特位發生沖突可以直接識別，分組進一步減少了閱讀器的搜索次數。引入堆棧存放數據使請求命令參數簡化得以實現，使閱讀器數據通信量減少。通過仿真實驗驗證該算法具有明顯的優越性。

[1] 張學軍，王緒海，蔡文琦.基于分組碼的改進型防碰撞算法研究[J].計算機應用研究，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] 朱軍，張元，盧小冬，等.基于分段搜索的多RFID 標簽抗沖突方法倡[J].計算機應用研究，2011，28（3）：1031-1033.

[4] Abramson N.THE ALOHA SYSTEM：another alternative for computer communications[C]//Proceedings of the November 17-19，1970，Fall 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] 謝振華，賴聲禮，陳鵬.標簽防沖撞算法設計[J].計算機工程，2008，34（6）：90-92.

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

[13] 王雪，錢志鴻，胡正超，等.基于二叉樹的RFID 防碰撞算法的研究[J].通信學報，2010，31（6）：49-57.

[14] 王亞奇，蔣國平.基于分組機制的跳躍式動態二進制防碰撞算法[J].自動化學報，2010，36（10）：1390-1400.

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