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

【關(guān)鍵詞】射頻標簽 查詢樹 防碰撞 優(yōu)化

1 研究背景和概述

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

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

2 查詢樹（QT）算法及相關(guān)概念

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

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

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

3 查詢樹算法優(yōu)化方法綜述

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

3.1 分支推斷優(yōu)化

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

3.2 多叉樹搜索優(yōu)化

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

3.3 發(fā)送遞增前綴優(yōu)化

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

3.4 沖突位置檢測優(yōu)化

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

3.5 提前終止優(yōu)化

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

3.6 混合算法優(yōu)化

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

4 查詢樹算法優(yōu)化方向分析與研究

4.1 結(jié)合物理層協(xié)議進行研究

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

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

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

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

如果射頻標簽的地址長度是n個bits，QT算法假設(shè)射頻標簽的所有地址的總數(shù)量是2n，我們假設(shè)這2n個射頻標簽的地址集合是S2n，某一次射頻標簽列表操作需要讀取的射頻標簽地址集合為Sr?；镜腝T算法相當于是在集合S2n，中通過地址空間分割和遍歷識別Sr中的每一個射頻標簽。實際上，假設(shè)在一個超級市場、一個倉庫、或者一個區(qū)域內(nèi)進行射頻標簽識別操作，我們只關(guān)心已經(jīng)入庫的射頻標簽，該類射頻標簽的地址集合稱為系統(tǒng)可能標簽地址集合Sp。顯然，Sp∈S2n，我們可以設(shè)計射頻標簽識別算法在地址集合Sp內(nèi)搜索，而不是在S2n中搜索，從而獲得較高的射頻標記列表操作吞吐率?；镜乃悸肥茄芯坑枚鏄浔硎镜纳漕l標簽地址集合Sp，只在可能存在射頻標簽地址的二叉樹分支路徑上搜索，從而減少射頻標簽地址前綴的發(fā)送數(shù)量，優(yōu)化射頻標簽識別效率。

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

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

5 結(jié)論

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

參考文獻

[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]李競.生活必需品現(xiàn)場保障數(shù)據(jù)系統(tǒng)的設(shè)計與實現(xiàn)[J].中國安全生產(chǎn)科學技術(shù)，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-），男，河北省承德市人，碩士學位，現(xiàn)為高級工程師。主要研究方向：信息技術(shù)在應急指揮、應急救援與應急保障方向的應用。

作者單位

1.中國安全生產(chǎn)科學研究院 北京市 100012

2.重大危險源監(jiān)控與事故應急技術(shù)國家安全監(jiān)管總局安全生產(chǎn)重點實驗室 北京市 100012