一種雙向混合查詢樹防碰撞算法

鄧紅衛，孫艷平，許 航，廖瑾蕓

（衡陽師范學院 計算機科學與技術學院，湖南 衡陽 421002）

RFID技術是物聯網應用系統中的核心技術，RFID標簽識別是制約RFID技術發展的一項關鍵技術，標簽碰撞大大降低了閱讀器對標簽的識別速度和識別率。因此，對防碰撞算法的研究是至關重要的［1］。

防碰撞算法主要分為不確定性算法和確定性算法兩種類型［2］。不確定性算法隨機性大，信道利用率低，會出現“餓死”現象；確定性算法簽識別率高，但識別延遲率高。目前，有研究者結合兩種算法的特點，探索出一些混合性防碰撞算法［3］。

本文在雙向查詢樹算法基礎上，正向根據最高和次高碰撞位的具體信息，動態生成查詢前綴，逆向引入碰撞模板，減少標簽識別的查詢次數和通信量。

1 算法相關理論基礎

1.1 查詢樹算法［4］

查詢樹算法簡稱為QT算法。閱讀器從查詢隊列中選擇一個查詢前綴發送給標簽，具有相同前綴的標簽響應閱讀器，如果只有一個標簽響應，則正確識別該標簽；如果有多于一個標簽響應，則發生了碰撞，閱讀器在查詢前綴后加0和1，生成新的查詢前綴，添加到查詢隊列中。通過不斷地增加查詢前綴的長度，直至所有標簽都被正確識別。如有4個等待識別的標簽ID號：0010、0110、1001和1010，其識別過程如圖1所示。

圖1 QT算法

1.2 混合查詢樹算法［5］

混合查詢樹算法簡稱為HQT算法，算法原理與QT算法類似，只是在發生碰撞時，閱讀器在查詢前綴后增加2位二進制數位：00、01、10和11，生成新的查詢前綴，添加到查詢隊列中，通過不斷地增加查詢前綴的長度，直至所有標簽都被正確識別。如有4個等待識別的標簽ID號：0010、0110、1001和1010，其識別過程如圖2所示。

圖2 HQT算法

2 雙向混合查詢樹防碰撞算法

2.1 算法指令約定

為了充分利用已得到的碰撞位信息，減少查詢次數和通信量，本算法對原有的算法指令進行了如下改進：

（1）碰撞距離（d）：發生碰撞的數據位到標簽中心位置的相對距離。dH和dL分別定義為高、低位碰撞距離之和，當閱讀器收到發生碰撞的數據后，首先對碰撞位進行判別，即比較dH和dL的大小，然后再確定搜索方式。若dH＞dL，從高位到低位進行搜索，直到將所有標簽識別完畢；反之，即從低位到高位進行搜索。例如，閱讀器接收到的數據為1x01x1x0，則各碰撞位所對應的碰撞距離分別為d1＝3、d3＝1、d6＝3，計算出dH＝3和dL＝4，即dH＞dL，采用逆向搜索方式。

（2）查詢指令REQUEST。REQUEST指令中的參數設有單參數、雙參數和三參數3種形式，分別有 REQUEST（＃）、REQUEST（Ht，Hr）和 REQUEST（p，Ht，Hr）3 個 REQUEST 指 令。RE－QUEST（＃）為最初查詢指令，要求閱讀器范圍內的所有標簽都得響應；REQUEST（Ht，Hr）中的 Ht和Hr是標簽響應REQUEST（＃）發生碰撞所得到最高碰撞位和次高碰撞位，REQUEST（Ht，Hr）要求標簽計算組合HtHr的十進制值并存入自己的累加器C中；REQUEST（p，Ht，Hr）中的p為已知的前綴，Ht和Hr是以p為前綴的標簽，p位置之后碰撞位中的最高碰撞位和次高碰撞位。

（3）選擇指令SELECT。SELECT（ID）選擇編號為ID標簽，為讀出或寫入數據作準備。

（4）讀取指令 READ。READ（ID）讀出編號為ID標簽中的數據。

（5）屏蔽指令 UNSELECT。UNSELECT（ID）讓編號為ID標簽處于非激活狀態，對收到的REQUEST指令不作應答。

（6）碰撞模板CID。與標簽ID位數相同，對應碰撞位均置0，其他位置不變。

2.2 算法描述

本算法根據雙向混合查詢樹算法，先計算比較Dh和Dl的大小。若Dh＜Dl根據最高碰撞位Ht和次高碰撞位Hr的組合XtXr值，決定標簽推遲C個時隙響應閱讀器，閱讀器端設有兩個查詢隊列Q0和Q1，Q0存放由最高碰撞位Ht和次高碰撞位Hr之間的Xt…Xr值構成新的查詢前綴p，Q1存放新的最高碰撞位和次高碰撞位的組合（Ht，Hr），初始值都為空；一個統計Request指令發送次數的累加器k，初始值都為1，直到標簽識別結束。若Dh＞Dl根據逆向二進制算法碰撞位置0，其余位不變，request根據碰撞模板依次增加1，直到標簽識別結束。算法流程如圖3所示。

圖3 算法流程圖

假設閱讀器識別范圍內有N個等待識別的標簽，閱讀器首先發送Request（＃），N個標簽都響應，根據曼徹斯特編碼原理解碼生成相應的比特流。計算比較Dh和Dl的大小。

1）Dh＜Dl

（1）從中取得最高碰撞位Ht，次高碰撞位Hr，構成一個新查詢組合參數（Ht，Hr），插入到Q1隊列的尾部。閱讀器從Q1隊列取出（Ht，Hr）生成查詢命令Request（Ht，Hr），發送給標簽。標簽分別計算其第Ht、Hr碰撞位的組合XtXr對應的十進制值，存放在自身的累加器C中，然后根據自己的C值在對應的時隙中進行響應。

（2）某一個時隙中如果只有一個標簽響應，則直接識別該標簽，使用READ指令讀出該標簽中的數據，并使用UNSELECT指令屏蔽該標簽。否則，進入第（3）步。

（3）某一個時隙中如果存在多個標簽響應，可以推知最高碰撞位Ht和次高碰撞位Hr之間的Xt…Xr值，將它作為一個新的查詢前綴p，按時隙順序依次插入到Q0隊列的尾部。同時，同一個時隙內響應的多個標簽也會發生碰撞，碰撞位處在原來Hr位之后，從中取得最高碰撞位Ht，次高碰撞位Hr，構成一個新查詢組合參數（Ht，Hr），按時隙順序依次插入到Q1隊列的尾部。

（4）閱讀器分別從隊列Q0和Q1的首部取出查詢前綴p和組合參數（Ht，Hr），生成新的查詢命令Request（p，Ht，Hr），發送給標簽，要求前綴為p的標簽響應。前綴為p的標簽計算第Ht、Hr碰撞位組合XtXr對應的十進制值，并存入自身的累加器C中，然后根據C值在對應的時隙中進行響應。

（5）當隊列Q0和Q1的值為空時，表明N個標簽全部識別，算法結束。否則，返回到第（2）步。

2）Dh＞Dl

（1）閱讀器初始化指令序列號CID為全0。

（2）閱讀器接收標簽的反饋信息，要么沒有碰撞，要么只有一位碰撞，這時，可直接識別。被識別出的標簽，閱讀器將繼續依次發送選擇指令、讀取指令和去屏蔽指令。

（3）閱讀器發送request請求指令之后，指令序列號CID自動累加1，并將作為下次發送request指令的序列號。

（4）當CID重新為全0時，識別結束；否則返回到（2）繼續執行。

2.3 算法舉例

假設閱讀器識別范圍內有8個等待識別的標簽，標簽的ID號為8位，如表1所示。

表1 曼徹斯特編碼

算法的實現過程如下：

（1）閱讀器初始化查詢隊列Q0和Q1，初值為空；初始化k＝1。

（2）閱讀器發送Request（＃），閱讀器識別范圍內的所有標簽都響應，根據曼徹斯特編碼原理得到的解碼信息為XX0XXX1X，如表2所示。根據碰撞距離計算Dh、Dl，Dh＞Dl即逆向搜索標簽。根據CID得到Request（00000010），標簽7被識別。碰撞不變，Rwquest（00000011），標簽2被識別。碰撞不變Request（00000110），標簽1被識別。碰撞不變Request（00000111），標簽8被識別。

表2 碰撞位信息

（3）碰撞發生改變，剩余標簽3、4、5、6碰撞為X10XXX0X，如表3所示。根據碰撞距離計算Dh、Dl，Dh＜Dl即正向搜索標簽。最高碰撞位為Ht＝8，次高碰撞位為 Hr＝5，將（Ht，Hr）＝（8，5）存入Q1尾部，統計Request指令次數累加器k值為1，閱讀器從Q1取出（8，5），生成新的詢問命令Request（8，5），發送給標簽。同時，k值加1。標簽分別計算其最高和次高碰撞位（第8、5位）的組合XtXr對應的十進制值，存放在自身的累加器C中，然后根據C值在對應的時隙中響應閱讀器。Tag3、Tag6的XtXr＝10對應C＝2，Tag4、Tag5的XtXr＝01對應C＝1，分別在時隙slot2、slot1中響應，都發生碰撞，如表4、5所示。

表3 碰撞位信息

表4 標簽響應時隙

（4）表4表明Tag4、Tag5在時隙slot1中響應，Tag3、Tag6在時隙slot2中響應。Tag4、Tag5在時隙slot1中響應第3位置發生碰撞，碰撞位信息如表5所示。閱讀器生成新的詢問命令Request（01010，3），并發送給標簽，標簽4、5分別被識別。Tag3和Tag6在時隙slot2中響應，在第4和3位置發生碰撞，碰撞位信息如表5所示。

表5 標簽碰撞信息

表6 標簽碰撞位信息

（5）最高碰撞位為Ht＝4，次高碰撞位為Hr＝3，閱讀器生成新的詢問命令 Request（1100，4，3），并發送給標簽，要求前四位（第8、7、6、5位）為1100的標簽響應。Tag3和Tag6分別計算第4、3碰撞位組合XtXr對應的十進制值存放在自身的累加器C中，標簽根據C值在對應的時隙中進行響應。Tag3的XtXr＝00對應C＝0，Tag6的XtXr＝01對應C＝1，分別在時隙slot0和slot1中響應并被識別，識別過程如表7所示。

表7 標簽響應時隙

上述8個標簽的識別過程與QT算法、HQT算法相比，減少了查詢次數和系統通信量，算法效率明顯提高。

3 算法仿真驗證

本文使用Matlab仿真工具對該算法進行仿真驗證。仿真結果在相同實驗條件下，在識別次數和傳輸數據量等方面，將此算法與QT算法、HQT算法相比，在識別次數和傳輸數據量等性能有明顯改善。如圖4所示。

圖4 BHQT、QT和HQT算法比較

4 結束語

本文在混合查詢樹防碰撞算法的基礎上，提出了一種改進的算法，該算法比較碰撞距離之和的大小，正向根據最高和次高碰撞位的具體信息，動態生成查詢前綴，充分利用已知位的信息，基本采用四叉樹，逆向搜索方式利用基本二進制算法減少交互次數，標簽識別的查詢次數和通信量明顯減少。仿真結果表明，該算法與基本二進制算法、動態二進制數算法、基本查詢樹算法、混合查詢樹算法相比，性能方面明顯提高。

［1］楊曉嬌，閆斌，謝光斌.一種改進的二進制防碰撞算法［J］.計算機應用與軟件，2013，30（10）：312－316.

［2］米志強.射頻識別（RFID）技術與應用［M］.北京：電子工業出版社，2011.

［3］王春華，許靜，彭關超，等.改進的RFID標簽識別防沖突算法［J］.計算機工程與應用，2011，47（31）：104－107.

［4］Choi J H，Lee D，Lee H.Bi－Slotted tree based anti－collision protocols for fast tag identification inRFID systems［C］.IEEE Communications Letters，2006：861－863.AND Feng Bo，Li Jintao，Guo Junbo，etal.ID－Binary tree stack anti－collision algorithm for RFID［C］.Proceedings of the 11th IEEE Symposium on Computers and Communications（2006ISCC’06），2006：207－212.

［5］李秉璋，景征駿，羅燁.基于后退式二進制的RFID防碰撞搜索算法［J］.計算機應用與軟件，2009，26（12）：96－98.

［6］Myung J，Lee W.An adaptive memory less tag anti－collision protocol for RFID networks［C］.IEEEICC，2005：32－26.

［7］Hsu C H，Chia－Hao Yu，Yi Pin Huang，etal.An enhanced query tree（EQT）protocol for memorylesstag anti－collision in RFID systems ［J］.Second International Conference on Future Generation Communication and Networking FGCN ’08，2008：427－432.

［8］Ryu J，Lee Hojin，Seok Y，et al.A Hybrid Query Tree Protocol for Tag Collision Arbitration in RFID System［C］／／Proceedings of the IEEE international conference on communications.Glasgow：IEEE，2007：5981－5986.