基于查詢樹的射頻標簽防碰撞算法優化

摘 要射頻標簽 （RFID tag）又稱電子標簽，是二十世紀八九十年代興起的一種非接觸式的物品單元自動識別通信技術，在跟蹤、物流、定位等領域已得到廣泛應用。其中，用于解決射頻讀寫器作用范圍內多標簽識別情景下的射頻標簽識別防碰撞方法已成為該領域的重要研究點。相對于基于通訊信道競爭的ALOHA算法，經典的查詢樹（Query Tree，下文簡稱QT）射頻標簽防碰撞算法由于標簽側電路設計簡單，比較適用于利用射頻讀寫器反射能量的被動標簽。本文對近年來針對查詢樹（QT）射頻標簽防碰撞算法的各種優化技術進行總結分析，并提出下一步的研究方向。

【關鍵詞】射頻標簽 查詢樹 防碰撞 優化

1 研究背景和概述

射頻標簽 （RFID tag）又稱電子標簽，是二十世紀八九十年代興起的一種非接觸式的物品單元自動識別通信技術，可通過無線信號識別特定目標并讀寫相應數據。在跟蹤、物流、定位等領域已得到廣泛應用，例如：圖書館門禁系統，交通收費，倉儲管理、貨架管理以及食品安全溯源等。其中，用于解決讀寫器作用范圍內多標簽識別情景下的射頻標簽識別防碰撞方法已成為該領域的重要研究點。

射頻標簽的防碰撞方法主要是為了解決在射頻標簽識別設備的有效通信區域內，當多個射頻標簽同時與識別設備進行通信時產生的無線沖突問題。目前，常用的防碰撞方法主要有兩類，一類是基于時隙隨機分配的ALOHA方法，由于該類方法的時隙是隨機分配的，某一標簽在相當一段時間內可能無法識別，造成“饑餓”（Tag starvation）問題。另一類是采用二叉樹搜索的方法，又稱查詢樹算法，用射頻標簽識別設備發送的標簽地址前綴對射頻標簽的地址空間進行空間分區搜索，利用該方法，射頻標簽可以簡化設計、降低成本，是目前多射頻標簽識別防碰撞算法的研究熱點。

2 查詢樹（QT）算法及相關概念

QT算法利用了二進制前綴樹（Binary Trie）數據結構，該數據結構由節點（TNode）和節點間的邊組成，節點分布在樹的n個分層中。節點類型分為根節點，內部節點和葉子節點。每一個根節點或者內部節點可能有1個或者2個子節點，葉子節點都在樹的最低層。節點和它的子節點間有直接相連的邊，每條邊對應一個標簽：字符‘0或者字符‘1。一般每個節點與左子節點間的邊（若有）對應字符‘0，與右子節點間的邊（若有）對應字符‘1。從根節點到每一個葉子節點的無重復節點的依次連接的邊組成一條路徑。在基于QT的射頻標簽防碰撞算法中，把長度為n的射頻標簽的地址集合組織為深度為n+1的二進制前綴樹，每個射頻標簽地址和二進制前綴樹的路徑一一對應。例如，一個長度為3，地址個數為3的射頻標簽地址集合Seta為{“010”，“011”， “110”}，此射頻標簽地址集合對應的二進制前綴樹如圖1所示。

QT算法采用前綴匹配法對射頻標簽的地址空間進行分割。該算法工作時，首先給出一個1比特前綴，所有與該前綴匹配的射頻標簽進行響應。如果響應的射頻標簽數量大于1個，產生沖突，則算法給出一個2比特的前綴，依次不斷增加發出的地址前綴的長度，直到沒有沖突，讀取一個射頻標簽地址。算法按照類似二叉樹深度優先搜索的方式，對射頻標簽的地址空間進行遍歷，讀取所有射頻讀寫器通訊范圍以內的射頻標簽。

例如對于圖1表示的RFID地址集合，QT算法發出地址前綴“0”，地址為“010”和“011”的射頻標簽響應，出現沖突。然后QT算法發出地址前綴“00”，無標簽響應。然后QT算法發出地址前綴“01”，地址為“010”和“011”標簽響應，出現沖突。然后QT算法發出地址前綴“010”，地址為“010”的標簽響應，完成一個標簽讀取。然后QT算法發出地址前綴“011”，地址為“011”的標簽響應，完成一個標簽讀取。對于圖1所示Trie樹的左分支，QT算法發出5個地址前綴，讀取2個標簽地址，讀取全部3個地址，需要發出6個地址前綴。

3 查詢樹算法優化方法綜述

QT算法并不能保證每發出一個地址前綴就可以讀取一個射頻標簽地址。對于讀寫器發出的射頻標簽地址前綴，如果有多個標簽進行響應，就會出現沖突的問題；如果沒有標簽響應，就會出現空讀取的問題。研究人員提出了多種方案，避免上述兩個問題，提高射頻標簽的讀取效率。

3.1 分支推斷優化

如果射頻讀寫器發出一個地址前綴p，出現沖突；射頻讀寫器又發出一個地址前綴“p0”，響應的射頻標簽數量是0；那么射頻讀寫器可以推斷出，如果發出地址前綴“p1”，一定會出現多標簽沖突；因此射頻讀寫器不發送地址前綴“p1”，直接發送地址前綴“p10”，和“p11”，至少優化了一次地址前綴發送。

3.2 多叉樹搜索優化

在基本的QT算法中，如果射頻讀寫器發送地址前綴“p”匹配出現沖突，下一次發送地址前綴“p0”和“p1”。而如果采用基于多叉樹搜索的QT算法，如果地址前綴“p”匹配失敗，下一步射頻讀寫器直接發送“p00”，“p01”，“p10”和“p11”。研究表明，一般情況下，基于多叉樹搜索的QT算法性能并不優于基本的QT算法。

3.3 發送遞增前綴優化

在基本的QT算法中，如果射頻讀寫器發送地址前綴“p”匹配出現沖突，則下一次發送地址前綴“p0”和“p1”。而采用了遞增前綴的QT算法，下一次只發送“0”或者“1”。這種技術需要射頻標簽跟蹤射頻讀寫器的狀態，容易發生狀態不同步的問題。

3.4 沖突位置檢測優化

射頻標簽識別的通訊協議一般采用曼切斯特編碼。曼切斯特編碼的核心特征是在每一位數據的中心都有跳變，當發生沖突時，曼切斯特編碼中心的跳變消失。因此如果設計了相應的檢測電路，射頻讀寫器可以識別出發生沖突地址的第一個比特位置。下一次，射頻讀寫器可以從該位置開始發出查詢前綴，避免了中間地址前綴的發送過程。如圖2所示，射頻讀寫器發出地址前綴“q”后，地址為“q010”，“q011”，“q111”的三個射頻標簽響應，出現沖突。基本的QT算法，射頻讀寫器發出前綴“q0”，仍然出現沖突，然后射頻讀寫器繼續發出“q01”，仍然出現沖突，然后射頻讀寫器發出前綴“q010”，讀取一個射頻標簽。而具有沖突位置檢測能力的QT算法，在射頻讀寫器發出地址前綴“q0”時，能夠根據射頻標簽的響應確定沖突位于地址前綴“q01”，所以射頻讀寫器不發送地址前綴“q01”，直接發送地址前綴“q010”，減少了一次產生沖突的前綴匹配過程，優化了射頻標簽識別效率。

3.5 提前終止優化

在能夠進行沖突位置檢測的基礎上，射頻讀寫器可以在發現沖突后命令射頻標簽停止進行響應，不發送已發生沖突后無意義的后續射頻標簽地址。

3.6 混合算法優化

一些研究表明，綜合利用查詢樹和ALOHA的射頻標簽識別算法能夠獲得更高的射頻標簽識別吞吐率，但是這些算法相對都比較復雜，不易于在使用反射能量的被動射頻標簽上，在本文中不討論該類算法。

4 查詢樹算法優化方向分析與研究

4.1 結合物理層協議進行研究

在前文所述的遞增發送前綴、沖突位置檢測和提前終止等方法對射頻通訊環境進行了比較理想的假設，沒有充分考慮出現通訊錯誤導致射頻讀寫器和射頻標簽的狀態不同步、射頻標簽識別提前終止命令沒有被所有標簽接收、由于不同標簽射頻信號的動態范圍不同導致沖突位置檢測失敗等問題。如果結合射頻標簽使用的物理層協議對上述問題進行全面的理論分析與仿真，并提出解決方案，必將推動上述方法的實用化。

4.2 研究參考待識別標簽數量信息的自適應算法

上文提到，研究表明，一般情況下，多叉樹搜索的QT算法性能并不優于基本的QT算法。但是如果根據待讀取標簽的數量動態調整每次地址前綴擴展的長度，就可以即減少沖突，又避免沒有標簽響應的空查詢，提高射頻標簽識別效率。研究參考待識別標簽數量信息的自適應算法、以及研究對待讀取射頻標簽的數量進行估計的方法，都是目前學術界較活躍的研究方向。

4.3 研究已知射頻標簽地址范圍信息情況下的算法

如果射頻標簽的地址長度是n個bits，QT算法假設射頻標簽的所有地址的總數量是2n，我們假設這2n個射頻標簽的地址集合是S2n，某一次射頻標簽列表操作需要讀取的射頻標簽地址集合為Sr。基本的QT算法相當于是在集合S2n，中通過地址空間分割和遍歷識別Sr中的每一個射頻標簽。實際上，假設在一個超級市場、一個倉庫、或者一個區域內進行射頻標簽識別操作，我們只關心已經入庫的射頻標簽，該類射頻標簽的地址集合稱為系統可能標簽地址集合Sp。顯然，Sp∈S2n，我們可以設計射頻標簽識別算法在地址集合Sp內搜索，而不是在S2n中搜索，從而獲得較高的射頻標記列表操作吞吐率。基本的思路是研究用二叉樹表示的射頻標簽地址集合Sp，只在可能存在射頻標簽地址的二叉樹分支路徑上搜索，從而減少射頻標簽地址前綴的發送數量，優化射頻標簽識別效率。

4.4 研究射頻標簽地址編碼策略對算法的影響

EPC（Electronic Product Code）即電子產品編碼，是一種編碼系統。它建立在EAN.UCC（即全球統一標識系統）條型編碼的基礎之上，并對該條形編碼系統做了一些擴充，用以實現對單品進行標志。EPC編碼分為很多類型，例如EPC-96編碼由頭字段、EPC管理、對象類別和序列號四個字段組成。 EPC編碼是一種層次化的編碼策略。而“隨機編碼”策略，顧名思義，就是對每一個射頻標簽隨機生成和分配一個地址。通過計算機仿真，可以得出結論，對于同樣數量的待識別射頻標簽，如果采用“隨機編碼”策略，利用QT算法可以獲得比類似EPC編碼的層次化編碼策略明顯更高的射頻標簽識別吞吐率。而類似EPC編碼的層次化編碼策略也有一定的應用需求，如何優化QT算法，提高采用類似EPC編碼的層次化編碼策略時的射頻標簽識別吞吐率，也是具有較大實用價值的研究方向。

5 結論

射頻標簽又稱電子標簽，是一種得到廣泛應用的物品單元自動識別通信技術。解決射頻讀寫器作用范圍內多標簽識別情景下的射頻標簽識別防碰撞方法已成為該領域的重要研究點。經典的查詢樹（QUERY TREE）射頻標簽防碰撞算法由于標簽側電路設計簡單，比較適用于利用射頻讀寫器反射能量的被動標簽。本文對近年來基于查詢樹的射頻標簽防碰撞算法的各種優化技術進行總結分析，并提出了結合物理層協議進行防碰撞算法設計、研究參考待讀取標簽數量信息的自適應算法、研究已知射頻標簽地址范圍信息情況下的算法、研究射頻標簽地址編碼策略對算法的影響等多個具有較大實用價值和現實意義的研究方向。

參考文獻

[1]C.Law，K.Lee，and K.-Y.Siu，“Efficient memoryless protocol for tag identification，”in Proceedings of the 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications，（Toronto，CA），pp.75-84，Aug.2000.

[2]J.H.Choi，D.Lee，and H.Lee，“Query tree-based reservation for efficient RFID tag anti-collision，”IEEE Commun.Lett.，vol.11，no.1，pp.85-87，2007.

[3]李競.生活必需品現場保障數據系統的設計與實現[J].中國安全生產科學技術，2014（11）：94-100.

[4] 張予帥，蔣泰，蘇平，羅義學，肖煌.ISO 18000-6 Type B與Type C標準的分析與比較[J].廣西科學院學報，2009（04）：336-339.

[5]Ziling，Zhou Binbin Chen，Haifeng Yu，“Understanding RFID counting protocols”，IEEE/ACM Transactions on Networking （TON），vol.24，（01），pp312-327，2016.

作者簡介

李競（1979-），男，河北省承德市人，碩士學位，現為高級工程師。主要研究方向：信息技術在應急指揮、應急救援與應急保障方向的應用。

作者單位

1.中國安全生產科學研究院 北京市 100012

2.重大危險源監控與事故應急技術國家安全監管總局安全生產重點實驗室 北京市 100012