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

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

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

1 研究背景和概述

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

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

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

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

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

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

3 查詢(xún)樹(shù)算法優(yōu)化方法綜述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)論

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

[4] 張予帥，蔣泰，蘇平，羅義學(xué)，肖煌.ISO 18000-6 Type B與Type C標(biāo)準(zhǔn)的分析與比較[J].廣西科學(xué)院學(xué)報(bào)，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.

作者簡(jiǎn)介

李競(jìng)（1979-），男，河北省承德市人，碩士學(xué)位，現(xiàn)為高級(jí)工程師。主要研究方向：信息技術(shù)在應(yīng)急指揮、應(yīng)急救援與應(yīng)急保障方向的應(yīng)用。

作者單位

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

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