宋瑞玲，高仲合

SONG Ruiling,GAO Zhonghe

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

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

1 引言

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

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

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

2 RFID 防碰撞算法

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

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

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

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

3 改進算法

3.1 算法的幾點約定

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

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

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

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

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

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

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

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

3.2 算法思路

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

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

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

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

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

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

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

3.3 算法舉例

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

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

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

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

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

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

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

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

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

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

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

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

4 算法性能分析及仿真

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

4.1 識別標簽所需搜索次數(shù)

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

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

（2）分組策略

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

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

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

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

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

表1 不同數(shù)目標簽對應搜索次數(shù)

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

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

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

其中L是ID 號長度。

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

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

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

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

4.3 算法仿真

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

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

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

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

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

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

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

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

5 結(jié)束語

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

[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，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] 謝振華，賴聲禮，陳鵬.標簽防沖撞算法設(shè)計[J].計算機工程，2008，34（6）：90-92.

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

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

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

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