基于標簽預測的分組映射防碰撞查詢樹算法

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

關鍵詞：射頻識別；標簽預測；查詢樹；分組映射

中圖分類號：TP391 ? ? 文獻標識碼：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 ?引 ?言

物聯網是指使用射頻識別（RFID）等信息傳感儀器，遵循既定規定，將任意物品與因特網之間建立起聯系以實現信息的傳輸，從而完成對所聯系物品的識別定位等操作的網絡。當代物聯網技術的飛速發展使得射頻識別技術逐漸成為現在的研究熱點[1]。

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

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

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

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

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

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

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

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

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

2 ?LGQT算法

2.1 ?算法思想

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

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

1）首先閱讀器向識別區域內的所有標簽發送Q，Q的初始值設為8。

2）標簽在接收到Q值后，利用隨機數生成器，在1～2Q中隨機選擇一個數，進行相應的短暫延時，然后向閱讀器發送一個非常短的長度為2 bit的預約幀。

3）閱讀器在相應時隙內接收完標簽反饋所有預約幀后，計算成功接收數S和碰撞數C。若C = 2Q，表示標簽數遠大于2Q，令Q = Q + 1，轉到步驟1；若C＜2Q/3，則轉到步驟4。

4）根據n′ = S + 2.39×C，計算出識別范圍內標簽的大概數量。

根據預測的標簽數量分配不同的查詢前綴，選擇最佳的查詢類型。根據DGMQT算法的特性推導，當標簽數量大于4時，后續查詢采用DGMQT算法，當標簽數量小于4時采用CT算法，當標簽數量小于2時，直接識別。

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

2.2 ?算法命令

REQ（*）：閱讀器查詢命令，所有標簽返回組標簽信息，閱讀器進行標簽數量預測

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

REQ（0/1）：閱讀器查詢命令，查詢前綴為0或1的標簽進行響應

DEcode（G0/1）：閱讀器解碼命令，對組標簽為G0或者G1的標簽返回的信號進行翻譯，轉化為對應的原始信息

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

2.3 ?LGQT算法流程

LGQT具體算法流程為：

1）閱讀器將查詢堆棧初始化為空，發出命令REQ（*）對查詢范圍內的標簽數量進行預測，若預測結果小于或等于4個，則發送REQ（0/1）信號進行識別，若預測結果多余4個，則轉到第二步。

2）閱讀器發出REQ（G）信號，根據組標簽對閱讀器范圍內的標簽進行識別并判斷碰撞情況，如果未發生碰撞，則發送READ命令進行標簽數據讀取操作，然后轉到第四步；如果發生碰撞，則執行第三步。

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

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

LGQT算法流程如圖1所示。

3 ?算法性能分析

LGQT算法總的空閑時隙數：

總的非空閑時隙數：

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

系統識別效率為：

通信復雜度定義位標簽成功被閱讀器讀取所傳輸的總比特數：

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

4 ?算法仿真及分析

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

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

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

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

5 ?結 ?論

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

參考文獻：

[1] 寧煥生，徐群玉.全球物聯網發展及中國物聯網建設若干思考 [J].電子學報，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] 李萌，錢志鴻，張旭，等.基于時隙預測的RFID 防碰撞 ALOHA算法 [J].通信學報，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，FENG 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] 嚴利輝，史長瓊，陳蓉，等.基于奇偶分組的多周期RFID標簽防碰撞算法 [J].計算機工程，2016，42（2）：312-315.

[13] 李川，蘇健，劉克雄，等.基于查詢樹的防碰撞算法性能分析與研究 [J].電子學報，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，FENG 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].通信學報，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標準的RFID防碰撞算法 [J].電子學報，2014，42（12）：2515-2519.

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

[22] 董軒江，李世寶，蔡麗萍，等.基于分組映射的防碰撞查詢樹算法 [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]．計算機工程，2020，46（4）：177-182．

作者簡介：董軒江（1994—），男，漢族，山東青島人，講師，碩士研究生，主要研究方向：RFID技術、物聯網應用。