摘 ?要：多標(biāo)簽防碰撞系統(tǒng)為了提高識別效率也會使通信復(fù)雜度更高，不利于提升系統(tǒng)信息傳遞的效率。針對防碰撞系統(tǒng)中識別效率與通信復(fù)雜度之間的矛盾關(guān)系，提出一種基于標(biāo)簽預(yù)測的分組映射查詢樹防碰撞算法。首先使用標(biāo)簽預(yù)測算法對閱讀范圍內(nèi)的標(biāo)簽數(shù)量進(jìn)行預(yù)測，根據(jù)預(yù)測結(jié)果使用不同的查詢前綴，標(biāo)簽據(jù)此返回不同的信息；在此基礎(chǔ)上根據(jù)標(biāo)簽ID特性對其進(jìn)行分組并設(shè)計了映射碼機(jī)制，閱讀器根據(jù)映射規(guī)律反推出碰撞信息得到查詢碼進(jìn)行查詢識別。仿真結(jié)果表明，與QT算法、A4PQT、GBAQT以及DGMQT算法相比，所提算法能夠有效減少識別總時隙數(shù)，在提高系統(tǒng)效率的同時大大降低了通信復(fù)雜度。

關(guān)鍵詞：射頻識別；標(biāo)簽預(yù)測；查詢樹；分組映射

中圖分類號：TP391 ? ? 文獻(xiàn)標(biāo)識碼：A ? 文章編號：2096-4706（2023）14-0066-05

Group Mapping Anti-Collision Query Tree Algorithm Based on Label Prediction

DONG Xuanjiang

（College of Big Data， Qingdao Huanghai University， Qingdao ?266427， China）

Abstract： In order to improve the identification efficiency， the multi-tag anti-collision system will also make the communication more complex， which is not conducive to improving the efficiency of system information transmission. Aiming at the contradiction relationship between recognition efficiency and communication complexity in anti-collision system， a group mapping query tree anti-collision algorithm based on label prediction is proposed. Firstly， this paper uses the tag prediction algorithm to predict the number of tags in the reading range. According to the prediction results， different query prefixes are used， and the labels return different information accordingly. On this basis， the tag ID is grouped according to its characteristics and a mapping code mechanism is designed. The reader reversely deduces the collision information according to the mapping law to obtain the query code for query and identification. The simulation results show that compared with QT algorithm， A4PQT， GBAQT and DGMQT algorithm， the proposed algorithm can effectively reduce the total numbers of identification time slots， improve the system efficiency and greatly reduce the communication complexity.

Keywords： RFID; label prediction; query tree; group mapping

0 ?引 ?言

物聯(lián)網(wǎng)是指使用射頻識別（RFID）等信息傳感儀器，遵循既定規(guī)定，將任意物品與因特網(wǎng)之間建立起聯(lián)系以實(shí)現(xiàn)信息的傳輸，從而完成對所聯(lián)系物品的識別定位等操作的網(wǎng)絡(luò)。當(dāng)代物聯(lián)網(wǎng)技術(shù)的飛速發(fā)展使得射頻識別技術(shù)逐漸成為現(xiàn)在的研究熱點(diǎn)[1]。

傳統(tǒng)的射頻識別系統(tǒng)主要分為閱讀器、識別標(biāo)簽以及處理器三大部分[2]。如果有多個標(biāo)簽同時處于同一閱讀器的識別范圍，在這個閱讀器發(fā)送識別請求時，有概率會出現(xiàn)多個標(biāo)簽同時響應(yīng)這一個閱讀器的現(xiàn)象出現(xiàn)，這種現(xiàn)象被叫作標(biāo)簽碰撞[3]。

標(biāo)簽防碰撞算法可以處理標(biāo)簽碰撞問題，現(xiàn)階段的防碰撞算法有兩種：一類是基于ALOHA的不確定性算法[4-6]；另一類是基于樹的確定性算法[7，8]。前者包括ALOHA[9]、時隙ALOHA和其他一些基于此的算法等。后者包括了二進(jìn)制搜索樹算法、查詢樹（Query Tree， QT）算法[10]、碰撞樹算法[11]等多種基于樹的查詢算法?；贏LOHA算法無法解決某些標(biāo)簽可能一直無法被讀取的“標(biāo)簽饑餓”現(xiàn)象，特別是在標(biāo)簽數(shù)量增加時系統(tǒng)識別效率表現(xiàn)較差[12]，而基于樹的防碰撞算法由于是確定性的算法，不存在“標(biāo)簽饑餓”問題。

查詢樹算法屬是基于樹的確定性算法的重要分支，現(xiàn)有的各種查詢樹算法在提升識別效率的同時會往往會帶來通信復(fù)雜度的大幅提升，不利于提升系統(tǒng)信息傳遞的效率[13]。本文在查詢樹算法的思想上，提出一種基于標(biāo)簽預(yù)測的分組映射查詢樹防碰撞算法（Group Mapping Anti-collision Query Tree Algorithm Based on Label Prediction， LGQT）。根據(jù)標(biāo)簽ID分組來設(shè)計映射機(jī)制以降低查詢過程中的空閑時隙的產(chǎn)生，使用了標(biāo)簽預(yù)測技術(shù)動態(tài)分配查詢過程中的查詢前綴，在提升系統(tǒng)識別效率的同時減少了通信復(fù)雜度。

1 ?基于查詢樹的防碰撞算法

查詢樹算法（Query Tree， QT）的主要思想是[14]：閱讀器對標(biāo)簽進(jìn)行輪詢，ID與查詢信號相同的標(biāo)簽進(jìn)行反饋，閱讀器同時接受所有反饋標(biāo)簽的每一位ID信息并且進(jìn)行記錄。當(dāng)有兩個以上的標(biāo)簽同時響應(yīng)時發(fā)生碰撞，則在此輪查詢信號后增加一位0以及1構(gòu)成新的查詢信號再次查詢，如此繼續(xù)下去直到只有一個標(biāo)簽響應(yīng)。但是QT算法無法保證每一輪查詢都有一個以上的標(biāo)簽進(jìn)行相應(yīng)，即空閑時隙的產(chǎn)生無可避免，如此一來便增加了查詢時間，降低了系統(tǒng)效率[15]。

CT（Collision Tree， CT）算法[16]對QT算法的改進(jìn)在于其標(biāo)簽反饋信息時，只反饋有效的碰撞位信息，即規(guī)定將碰撞最高位置“0”及“1”并且入棧用作查詢碼，直接定位到碰撞位，從而消除了空閑時隙，減少了時隙內(nèi)的數(shù)據(jù)傳輸量。

A4PQT算法[17]在查詢的過程中根據(jù)碰撞位置的特點(diǎn)改進(jìn)了四叉樹，減少了空閑時隙的產(chǎn)生。閱讀器向讀取范圍內(nèi)的標(biāo)簽發(fā)送查詢前綴，匹配前綴的標(biāo)簽將除前綴外余下的ID發(fā)送給閱讀器，但是仍有一定的概率產(chǎn)生空閑時隙[18]。以及在此基礎(chǔ)上改進(jìn)的GBAQT算法[19]，雖然采用了分組的思想，但是也沒有完全杜絕空閑時隙的產(chǎn)生，算法的效率沒有較大的提升。

CCMA算法[20]是多進(jìn)制樹算法的一種，采用了映射數(shù)據(jù)的思想，將兩位ID映射為4位，消除了空閑時隙的產(chǎn)生。BQBMT算法[21]設(shè)計了比特查詢多進(jìn)制樹，引入映射序列并根據(jù)收到ID中含0的比率切換查詢機(jī)制，提高了算法的查詢效率。DGMQT算法[22]在此基礎(chǔ)上設(shè)計了基于雙重分組的對位映射查詢樹，根據(jù)對位映射規(guī)則，設(shè)計出同組標(biāo)簽之間互不相同，且不同組別之間可以共用的映射數(shù)據(jù)并將映射位ID提升到了3位，進(jìn)一步提升了系統(tǒng)查詢效率，但是就映射機(jī)制而言，2-4映射以及3-8映射為系統(tǒng)帶來的通信負(fù)載是巨大的，在提升傳輸效率的同時如何降低通信復(fù)雜度是一個必須解決的問題。

針對上述問題，本文基于預(yù)測思想以及映射樹查詢機(jī)制，提出一種基于標(biāo)簽預(yù)測的分組映射查詢樹防碰撞算法（LGQT），在LGQT算法中采用標(biāo)簽預(yù)測技術(shù)對本輪產(chǎn)生應(yīng)答的標(biāo)簽數(shù)量進(jìn)行預(yù)測，根據(jù)預(yù)測結(jié)果分情況給出查詢前綴，分組標(biāo)簽收到查詢前綴立即返回映射后的數(shù)據(jù)，閱讀器根據(jù)映射機(jī)制反解碼出碰撞數(shù)據(jù)，算法在消除了空閑時隙的前提下進(jìn)一步降低了通信復(fù)雜度。仿真結(jié)果表明與另外幾種經(jīng)典算法相比，LGQT算法具有較低通信復(fù)雜度、較高的系統(tǒng)效率以及時隙利用率。

2 ?LGQT算法

2.1 ?算法思想

LGQT算法的核心思想有兩點(diǎn)：一是根據(jù)預(yù)測標(biāo)簽的數(shù)量動態(tài)分配查詢前綴，選擇不同的查詢算法，減少查詢過程中標(biāo)簽返回的信息量；二是標(biāo)簽分組提高識別效率，ID映射機(jī)制消除碰撞時隙。

首先采用基于泊松分布的標(biāo)簽數(shù)量預(yù)測方法[23]對標(biāo)簽數(shù)量進(jìn)行預(yù)測，n′ = S + 2.39×C，假設(shè)未識別標(biāo)簽數(shù)量應(yīng)用成功數(shù)S與碰撞數(shù)C的2.39倍之和來預(yù)測。標(biāo)簽預(yù)測的具體步驟[24]如下：

1）首先閱讀器向識別區(qū)域內(nèi)的所有標(biāo)簽發(fā)送Q，Q的初始值設(shè)為8。

2）標(biāo)簽在接收到Q值后，利用隨機(jī)數(shù)生成器，在1～2Q中隨機(jī)選擇一個數(shù)，進(jìn)行相應(yīng)的短暫延時，然后向閱讀器發(fā)送一個非常短的長度為2 bit的預(yù)約幀。

3）閱讀器在相應(yīng)時隙內(nèi)接收完標(biāo)簽反饋所有預(yù)約幀后，計算成功接收數(shù)S和碰撞數(shù)C。若C = 2Q，表示標(biāo)簽數(shù)遠(yuǎn)大于2Q，令Q = Q + 1，轉(zhuǎn)到步驟1；若C＜2Q/3，則轉(zhuǎn)到步驟4。

4）根據(jù)n′ = S + 2.39×C，計算出識別范圍內(nèi)標(biāo)簽的大概數(shù)量。

根據(jù)預(yù)測的標(biāo)簽數(shù)量分配不同的查詢前綴，選擇最佳的查詢類型。根據(jù)DGMQT算法的特性推導(dǎo)，當(dāng)標(biāo)簽數(shù)量大于4時，后續(xù)查詢采用DGMQT算法，當(dāng)標(biāo)簽數(shù)量小于4時采用CT算法，當(dāng)標(biāo)簽數(shù)量小于2時，直接識別。

在標(biāo)簽端設(shè)計使用標(biāo)簽分組和映射機(jī)制，對標(biāo)簽進(jìn)行三位分組并進(jìn)行ID映射，消除空閑時隙。根據(jù)三位ID能否進(jìn)行異或運(yùn)算賦組標(biāo)簽G為0或者1。再根據(jù)分組情況對標(biāo)簽ID做映射，映射規(guī)則為對位映射，三位ID表示為XXX，對位映射為GXXX或者為GTTT（其中G表示組標(biāo)簽號，TTT表示為XXX按位取反）。具體的分組以及映射關(guān)系參照表1。經(jīng)過對位映射之后，3位ID對應(yīng)4位映射數(shù)據(jù)，在同一組內(nèi)可以做到準(zhǔn)確識別碰撞信息，不同組別之間則可以利用組標(biāo)簽號進(jìn)行區(qū)分從而完全消除空閑時隙。在向閱讀器進(jìn)行數(shù)據(jù)傳輸時，最終的傳輸數(shù)據(jù)為1位組標(biāo)簽號G加上4位映射數(shù)據(jù)。

2.2 ?算法命令

REQ（*）：閱讀器查詢命令，所有標(biāo)簽返回組標(biāo)簽信息，閱讀器進(jìn)行標(biāo)簽數(shù)量預(yù)測

REQ（G）：閱讀器查詢命令，組標(biāo)簽為G的標(biāo)簽識別并返回對位映射碼

REQ（0/1）：閱讀器查詢命令，查詢前綴為0或1的標(biāo)簽進(jìn)行響應(yīng)

DEcode（G0/1）：閱讀器解碼命令，對組標(biāo)簽為G0或者G1的標(biāo)簽返回的信號進(jìn)行翻譯，轉(zhuǎn)化為對應(yīng)的原始信息

Q0/1 POP：閱讀器彈棧命令，將Q0/1查詢前綴棧頂元素彈出

2.3 ?LGQT算法流程

LGQT具體算法流程為：

1）閱讀器將查詢堆棧初始化為空，發(fā)出命令REQ（*）對查詢范圍內(nèi)的標(biāo)簽數(shù)量進(jìn)行預(yù)測，若預(yù)測結(jié)果小于或等于4個，則發(fā)送REQ（0/1）信號進(jìn)行識別，若預(yù)測結(jié)果多余4個，則轉(zhuǎn)到第二步。

2）閱讀器發(fā)出REQ（G）信號，根據(jù)組標(biāo)簽對閱讀器范圍內(nèi)的標(biāo)簽進(jìn)行識別并判斷碰撞情況，如果未發(fā)生碰撞，則發(fā)送READ命令進(jìn)行標(biāo)簽數(shù)據(jù)讀取操作，然后轉(zhuǎn)到第四步；如果發(fā)生碰撞，則執(zhí)行第三步。

3）閱讀器對組標(biāo)簽為0的對位映射碼進(jìn)行Decode操作，將映射碼碰撞碼進(jìn)行解碼，之后對解碼后得到的查詢碼進(jìn)行PUSH（pre）操作入G0棧；之后閱讀器對組標(biāo)簽為1的映射碼執(zhí)行相同操作，入G1棧。

4）判斷查詢堆棧G0是否為空，若不為空，執(zhí)行Q0 POP操作，彈出棧頂查詢前綴，轉(zhuǎn)到第一步；若堆棧G0為空則對堆棧G1進(jìn)行上述操作；若堆棧G1也為空，則識別完成，該次識別過程終止。

LGQT算法流程如圖1所示。

3 ?算法性能分析

LGQT算法總的空閑時隙數(shù)：

總的非空閑時隙數(shù)：

最差情況下LGQT算法識別時隙數(shù)Tn≈Nnc，故使用Nnc作為LGQT算法的識別時隙來進(jìn)行性能分析。

系統(tǒng)識別效率為：

通信復(fù)雜度定義位標(biāo)簽成功被閱讀器讀取所傳輸?shù)目偙忍財?shù)：

其中：Fn表示算法成功識別n個標(biāo)簽所需要的通信復(fù)雜度，Li表示后續(xù)識別過程中每次查詢的傳輸位數(shù)，L表示第一次查詢的傳輸位數(shù)。

4 ?算法仿真及分析

以Matlab_2018b為平臺，使用蒙特卡洛仿真方法進(jìn)行仿真實(shí)驗，標(biāo)簽數(shù)目取最大1 000個，標(biāo)簽ID取96b，將DGMQT與QT算法A4PQT算法和GBAQT算法進(jìn)行仿真，分別從總時隙數(shù)、系統(tǒng)效率以及通信復(fù)雜度三個方面進(jìn)行性能分析對比。

圖2為LGQT算法與QT算法、A4PQT算法、GBAQT算法和DGMQT算法識別總時隙數(shù)比較，從圖中可以較為明顯地看出LGQT算法對比QT算法以及A4PQT算法的識別總時隙數(shù)有著明顯的減少：在標(biāo)簽數(shù)量達(dá)到1 000時，LGQT算法所用時隙數(shù)平均為1 249，相比QT算法以及A4PQT算法分別節(jié)省了55.3%以及45.7%的總時隙數(shù)；對比GBAQT和DGMQT也具有一定的識別時隙優(yōu)勢，隨著標(biāo)簽數(shù)目n增加，這種優(yōu)勢更加明顯。這主要是由于標(biāo)簽預(yù)測之后，算法將小范圍的標(biāo)簽識別過程簡化，不需要經(jīng)過重復(fù)時隙來判斷識別碼；同時分組和映射提高了信息的處理效率，消除了空閑時隙。

圖3為這五種算法的系統(tǒng)效率比較，從圖中可以較為明顯地看出，LGQT算法的系統(tǒng)效率保持在0.75以上，優(yōu)于0.72左右的DGMQT，大大優(yōu)于GBAQT以及另外兩種算法。

圖4為這幾種算法通信復(fù)雜度的比較。從中能夠觀察到，QT算法的通信復(fù)雜度較高；A4PQT算法采用了修剪分支的理論方法使得通信復(fù)雜度有所下降；而GBAQT以及DGMQT算法設(shè)計了分組，都擁有較優(yōu)的通信復(fù)雜度性能；但是LGQT算法使用了標(biāo)簽預(yù)測分組的思想，將細(xì)粒度的標(biāo)簽劃分到極致，進(jìn)一步降低了通信復(fù)雜度。

5 ?結(jié) ?論

本文基于查詢樹防碰撞思想，在DGMQT算法的思想上引入了標(biāo)簽預(yù)測分組的機(jī)制，同時結(jié)合分組映射機(jī)制，根據(jù)反饋標(biāo)簽的數(shù)量動態(tài)分配查詢前綴并選擇最佳查詢算法，提出了基于標(biāo)簽預(yù)測的分組映射查詢樹防碰撞算法。理論和仿真分析結(jié)果表明：LGQT算法可以有效減少識別總時隙數(shù)，在提高系統(tǒng)效率的同時大大降低了通信復(fù)雜度，在多標(biāo)簽的情況下該算法的各項性能顯著優(yōu)于其他算法。在實(shí)際應(yīng)用過程中可以利用算法準(zhǔn)確預(yù)測出閱讀器識別范圍內(nèi)的標(biāo)簽數(shù)量，因此本文算法具有一定的應(yīng)用價值。

參考文獻(xiàn)：

[1] 寧煥生，徐群玉.全球物聯(lián)網(wǎng)發(fā)展及中國物聯(lián)網(wǎng)建設(shè)若干思考 [J].電子學(xué)報，2010，38（11）：2590-2599．

[2] HSU C H，CHAO H C，Park J H.Threshold jumping and wrap-around scan techniques toward efficient tag identification in high density RFID systems [J].Information Systems Frontiers，2011，13（4）：471-480.

[3] Mbacke A A，MITTON N，RIVANO H. RFID Anticollision in Dense Mobile Environments [C]//2017 IEEE Wireless Communications and Networking Conference （WCNC）.San Francisco：IEEE，2017：1-6.

[4] 李萌，錢志鴻，張旭，等.基于時隙預(yù)測的RFID 防碰撞 ALOHA算法 [J].通信學(xué)報，2011，32（12）：43-50.

[5] ANDREA Z. Adaptive Batch Resolution Algorithm with Deferred Feedback for practical CSMA Wireless Networks [J].IEEE Transactionson Wireless Communications，2012，11（10）：3528-3539.

[6] ZHU L，YUM T S P. Optimal Framed Aloha Based Anti-Collision Algorithms for RFID Systems [J].IEEE Transactions on Communications，2011，58（12）：3583-3592.

[7] JIANG Y，ZHANG R N. An Adaptive Combination Query Tree Protocol for Tag Identification in RFID Systems [J].IEEECommunicationsLetters，2012，16（8）：1192-1195.

[8] YANG C N，HU L J，LAI J B. Query Tree Algorithm for RFID Tag with Binary-Coded Decimal EPC [J].IEEE Communications Letters，2010，16（10）：1616-1619.

[9] LAW C，LEE K，SIU K Y. Efficient memoryless protocol for tag identification（extended abstract）[J].ACM，2000：75-84.

[10] HUSH D R. Analysis of tree algorithm for RFID arbitration [C]//Proc IEEE International Symposium on Information Theory.Cambridge：IEEE，1998：107.

[11] JIA X，F(xiàn)ENG Q，YU L. Stability Analysis of an Efficient Anti-Collision Protocol for RFID Tag Identification [J].IEEE Transactions on Communications，2012，60（8）：2285-2294.

[12] 嚴(yán)利輝，史長瓊，陳蓉，等.基于奇偶分組的多周期RFID標(biāo)簽防碰撞算法 [J].計算機(jī)工程，2016，42（2）：312-315.

[13] 李川，蘇健，劉克雄，等.基于查詢樹的防碰撞算法性能分析與研究 [J].電子學(xué)報，2018，46（11）：2671-2678.

[14] HUSH D R，WOOD C. Analysis of tree algorithms for RFID arbitration [C]//Proceedings. 1998 IEEE International Symposium on Information Theory （Cat. No.98CH36252）. Cambridge：IEEE，1998：107.

[15] LAW C，LEE K，SIU K Y.Efficient memoryless protocol for tag identification：US09870074 [P].2023-06-29.

[16] JIA X L，F(xiàn)ENG Q Y，YU L S，et al. Stablity analysis of an efficiet anti-collision protocol for RFID tag identification [J]. IEEE Transactions on Communications，2012，60（8）：2285-2294.

[17] ZHANG W，GUO Y J，TANG X M，et al.An efficient adaptive anti-collision algorithm based on 4-ary pruning query tree [J].International Journal of Distributed Sensor Networks，2013，14（2）：135-143.

[18] 付鈺，錢志鴻，程超，等.基于分組機(jī)制的位仲裁查詢樹防碰撞算法 [J].通信學(xué)報，2016，37（1）：123-129.

[19] LANDALUCE H，PERALLOS A，ONIEVA E，et al. An Energy and Identification Time Decreasing Procedure for Memoryless RFID Tag Anticollision Protocols [J].IEEE Transactions on Wireless Communications，2016，15（6）：4234-4247.

[20] 蘇健，文光俊，韓佳利.一種基于ISO18000-6B標(biāo)準(zhǔn)的RFID防碰撞算法 [J].電子學(xué)報，2014，42（12）：2515-2519.

[21] 蘇建，許若鈺，姚永雷，等.基于比特查詢的多進(jìn)制樹標(biāo)簽防碰撞識別協(xié)議 [J].電子學(xué)報，2019，47（2）：422-427.

[22] 董軒江，李世寶，蔡麗萍，等.基于分組映射的防碰撞查詢樹算法 [J].計算機(jī)工程，2020，46（8）：184-189+196.

[23] CHEN W T. A Fast anticollision algorithm for the EPCglobal UHF class-1 generation-2 RFID standard [J]. IEEE Communications Letters，2014，18（9）：1519-1522.

[24] 王帥，楊恒新，楊華.基于偽ID碼的樹型防碰撞算法 [J]．計算機(jī)工程，2020，46（4）：177-182．

作者簡介：董軒江（1994—），男，漢族，山東青島人，講師，碩士研究生，主要研究方向：RFID技術(shù)、物聯(lián)網(wǎng)應(yīng)用。