一種新型的混合查詢樹防碰撞算法

鄧紅衛，梁小滿，許 航，廖瑾蕓

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

0 引 言

RFID技術是RFID系統架構中感知層的關鍵技術之一。RFID系統主要由閱讀器、電子標簽、RFID中間件和應用系統軟件四個部分組成，閱讀器和電子標簽通過一條共用的通信通道進行無線通信完成數據傳輸。如果兩個及以上處于同一閱讀器可讀范圍內的標簽同時與閱讀器通信時，就會出現數據碰撞問題，造成閱讀器無法識別標簽。RFID標簽防碰撞算法是RFID系統中的一個核心問題，標簽碰撞問題的解決對RFID系統性能的提高至關重要。

目前標簽防碰撞算法有兩種：基于ALOHA的非確定性算法和基于二進制樹型結構的確定性算法［1］。非確定性算法包括：ALOHA 算法、時隙ALOHA算法、幀時隙ALOHA算法和動態時隙ALOHA算法，算法隨機性大，信道利用率低（理想狀態為36.8%），而且會出現個別標簽無法識別（即“餓死”現象）；確定性算法包括：二進制搜索算法、動態二進制搜索算法、后退式二進制算法和查詢樹算法，算法標簽識別率高，但識別延遲率高。

本文欲在混合查詢樹算法基礎上，根據最高和次高碰撞位的具體信息，動態生成查詢前綴，減少標簽識別的查詢次數和通信量。

1 算法相關理論基礎

1.1 曼徹斯特編碼

曼徹斯特編碼［2］是RFID系統中的一種編碼方式。該編碼約定“0”表示上升沿，“1”表示下降沿。當多個標簽同時向閱讀器發送不同數據時，則對應曼徹斯特編碼的上升沿和下降沿相互抵消，出現“沒有變化”的狀態，閱讀器由此可以確定碰撞的準確位置。假設有兩個標簽：10010110和10100011同時響應閱讀器的請求，閱讀器獲得的信息為10XX0X1X，X表示為碰撞。工作原理如圖1所示。

圖1 曼徹斯特編碼

1.2 查詢樹算法［3］

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

圖2 QT樹結構

1.3 混合查詢樹算法［4］

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

圖3 HQT樹結構

2 新型的混合查詢樹算法

2.1 算法指令約定

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

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

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

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

美國在《Mobility 2000》中對交通管理系統的定義強調，監視、控制和管理交通。“監視”交通的關鍵是采集、存儲和傳輸交通信息。隨著科學技術的發展，采集、存儲、傳輸交通信息的方法越來越智能化，智能交通管理系統應運而生。智能交通管理系統是利用先進的信號檢測手段和相關交通控制模型，通過檢測到的交通信息，制定有效的交通控制方案，并將成熟的方案通過多種方式傳遞給交通參與者和管理者，目標是提高交通管理和運輸效率。

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

2.2 算法描述

本算法根據最高碰撞位Ht和次高碰撞位Hr的組合XtXr值，決定標簽推遲C個時隙響應閱讀器，閱讀器端設有兩個查詢隊列Q0和Q1，Q0存放由最高碰撞位Ht和次高碰撞位Hr之間的Xt…Xr值構成新的查詢前綴p，Q1存放新的最高碰撞位和次高碰撞位的組合（Ht，Hr），初始值都為空；一個統計Request指令發送次數的累加器k，初始值都為1。算法流程如圖4所示。

圖4 算法流程

（1）假設閱讀器識別范圍內有N個等待識別的標簽，閱讀器首先發送Request（＃），N個標簽都響應，根據曼徹斯特編碼原理解碼生成相應的比特流，從中取得最高碰撞位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.3 算法舉例

表1 曼徹斯特編碼

算法的實現過程如下：

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

（2）閱讀器發送Request（＃），閱讀器識別范圍內的所有標簽都響應，根據曼徹斯特編碼原理得到的解碼信息為X0XXXXXX，如表2所示。最高碰撞位為 Ht＝8，次高碰撞位為 Hr＝6，將（Ht，Hr）＝（8，6）存入Q1尾部，統計Request指令次數累加器k值為1，閱讀器從Q1取出（8，6），生成新的詢問命令Request（8，6），發送給標簽。同時，k值加1。標簽分別計算其最高和次高碰撞位（第8、6位）的組合XtXr對應的十進制值，存放在自身的累加器C中，然后根據C值在對應的時隙中響應閱讀器。Tag4的XtXr＝00對應C＝0，Tag2的XtXr＝01對應C＝1，分別在時隙slot0、slot1中響應并被識別；Tag5、Tag6和Tag7的XtXr＝10對應C＝2，在時隙slot2中響應，Tag1、Tag3和Tag8的XtXr＝11對應C＝3，在時隙slot3中響應，都發生碰撞，如表3所示。

表2 碰撞位信息

表3 標簽響應時隙

（3）表3表明Tag5、Tag6和Tag7在時隙slot2中響應，其Xt0Xr組合值為100，在第5至1位置發生碰撞，碰撞位信息如表4所示。最高碰撞位為Ht＝5，次高碰撞位為Hr＝3，閱讀器生成新的詢問命令Request（100，5，3），并發送給標簽，要求前三位（第8、7、6位）為100的標簽響應。Tag5、Tag6和Tag7分別計算第5、3碰撞位組合XtXr對應的十進制值存放在自身的累加器C中，然后根據C值在對應的時隙中進行響應。Tag6的XtXr＝01對應C＝1，Tag5的XtXr＝10對應C＝2，Tag7的XtXr＝11對應C＝3，它們分別在時隙slot1、slot2和slot3中響應并被識別，識別過程如表5所示。

表4 碰撞位信息

表5 標簽響應時隙

（4）表3表明Tag1、Tag3和Tag8在時隙slot3中響應，其Xt0Xr組合值為101，在第5至1位置發生碰撞，碰撞位信息如表6所示。最高碰撞位為Ht＝5，次高碰撞位為Hr＝4，閱讀器生成新的詢問命令Request（101，5，4），并發送給標簽，要求前三位（第8、7、6位）為101的標簽響應。Tag1、Tag3和Tag8分別計算第5、4碰撞位組合XtXr對應的十進制值存放在自身的累加器C中，標簽根據C值在對應的時隙中進行響應。Tag1的XtXr＝01對應C＝1，Tag3的XtXr＝10對應C＝2，Tag8的XtXr＝11對應C＝3，它們分別在時隙slot1、slot2和slot3中響應并被識別，識別過程如表7所示。

表6 碰撞位信息

表7 標簽響應時隙

（5）上述8個標簽的識別過程對應的樹型結構如圖5所示。根據最高碰撞位和次高碰撞位構建成一棵四叉樹，樹高為2層，碰撞時隙為3個，空閑時隙為2個，與QT、HQT算法相比，減少了查詢次數和系統通信量，算法效率明顯提高。

圖5 NHQT樹結構

3 算法仿真驗證

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

圖6 三種算法識別延遲對比

4 結束語

本文提出的算法在混合查詢樹算法基礎上，算法根據最高和次高碰撞位的具體信息，動態生成查詢前綴，充分利用已知位的信息，基本采用四叉樹，加大判斷的收斂性，標簽識別的查詢次數和通信量明顯減少。仿真結果表明，該算法與QT、HQT兩種算法相比，識別延時性能方面明顯提高。

［1］SCHOUTEFS.DynamicframelengthALOHA ［J］.IEEETransactionsonCommunicationsLetters，1983，31（4）：565－568.

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

［3］程文青，趙夢欣，徐晶，等.改進的RFID動態幀時隙ALOHA算法［J］.華中科技大學學報：自然科學版，2007，35（6）：14－16.

［4］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.