基于查詢樹的射頻標(biāo)簽防碰撞算法優(yōu)化

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

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

1 研究背景和概述

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

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

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é)點間有直接相連的邊，每條邊對應(yīng)一個標(biāo)簽：字符‘0或者字符‘1。一般每個節(jié)點與左子節(jié)點間的邊（若有）對應(yīng)字符‘0，與右子節(jié)點間的邊（若有）對應(yīng)字符‘1。從根節(jié)點到每一個葉子節(jié)點的無重復(fù)節(jié)點的依次連接的邊組成一條路徑。在基于QT的射頻標(biāo)簽防碰撞算法中，把長度為n的射頻標(biāo)簽的地址集合組織為深度為n+1的二進制前綴樹，每個射頻標(biāo)簽地址和二進制前綴樹的路徑一一對應(yīng)。例如，一個長度為3，地址個數(shù)為3的射頻標(biāo)簽地址集合Seta為{“010”，“011”， “110”}，此射頻標(biāo)簽地址集合對應(yīng)的二進制前綴樹如圖1所示。

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

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

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

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

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

如果射頻讀寫器發(fā)出一個地址前綴p，出現(xiàn)沖突；射頻讀寫器又發(fā)出一個地址前綴“p0”，響應(yīng)的射頻標(biāo)簽數(shù)量是0；那么射頻讀寫器可以推斷出，如果發(fā)出地址前綴“p1”，一定會出現(xiàn)多標(biāo)簽沖突；因此射頻讀寫器不發(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ù)需要射頻標(biāo)簽跟蹤射頻讀寫器的狀態(tài)，容易發(fā)生狀態(tài)不同步的問題。

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

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

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

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

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

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

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

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

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

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

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

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

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

4.4 研究射頻標(biāo)簽地址編碼策略對算法的影響

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

5 結(jié)論

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

[4] 張予帥，蔣泰，蘇平，羅義學(xué)，肖煌.ISO 18000-6 Type B與Type C標(biāo)準(zhǔn)的分析與比較[J].廣西科學(xué)院學(xué)報，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-），男，河北省承德市人，碩士學(xué)位，現(xiàn)為高級工程師。主要研究方向：信息技術(shù)在應(yīng)急指揮、應(yīng)急救援與應(yīng)急保障方向的應(yīng)用。

作者單位

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

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