基于标签预测的分组映射防碰撞查询树算法

摘  要：多标签防碰撞系统为了提高识别效率也会使通信复杂度更高，不利于提升系统信息传递的效率。针对防碰撞系统中识别效率与通信复杂度之间的矛盾关系，提出一种基于标签预测的分组映射查询树防碰撞算法。首先使用标签预测算法对阅读范围内的标签数量进行预测，根据预测结果使用不同的查询前缀，标签据此返回不同的信息；在此基础上根据标签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技术、物联网应用。