增强型混合树RFID防碰撞算法研究

周伟辉

摘 要 为了解决现阶段RFID技术中存在的多标签碰撞问题。针对二叉树算法识别时间长，四叉树算法产生大量空闲时隙而降低识别效率的不足，提出了一种增强型混合树防碰撞（EHT）算法。该算法根据待识别标签数目来动态选择基于树的算法，从而缩短识别时间，提高识别效率和减少所耗总时隙数。仿真结果表明，当待识别标签总数超过1 000时，EHT算法的识别效率仍能维持在65%以上，所耗总时隙数为1 500个左右。因此EHT算法可以很好地解决多标签碰撞问题，并在大规模标签识别场合中具有良好的应用前景。

关键词 RFID；二叉树；四叉树；混合树；防碰撞算法

中图分类号 TP3 文献标识码 A 文章编号 1674-6708（2018）216-0148-02

1 EHT算法分析与实现步骤

1.1 EHT算法设计思想

文章针对基于树的算法识别时间长，识别过程中会产生大量空闲时隙而降低识别效率的不足，提出了一种增强型混合树防碰撞（Enhanced hybrid tree， EHT）算法。在识别过程中根据响应的标签数动态选择二叉树、三叉树和四叉树，共有7个待识别标签数，第一轮识别中采用四叉树算法识别一个标签，产生两个碰撞时隙，第二轮识别成功识别三个标签，第三轮识别成功识别一个标签，产生一个碰撞标签，最后一轮成功识别全部标签，总共搜索查询了4次，只产生一个空闲时隙，可以得出混合树算法能够减少搜索查询次数从而缩短识别时间，同时能减少空闲时隙从而太高识别效率。

EHT算法是基于树的算法的改进，通过标签的碰撞位来进行碰撞标签的分组，当有且仅有一个最高碰撞位时，采用二叉树算法，将最高碰撞位为“0”的标签分组到左子树，将最高碰撞位为“1”的标签分组到右子树；当有最高碰撞位和次高碰撞位连续时，采用四叉树算法，从左到右依次存放的是碰撞位为“00”“01”“10”“11”的标签；若最高碰撞位和次高碰撞位連续但碰撞位“00”“01”“10”“11”不全部存在时，动态选择二叉树或三叉树进行识别，这样可以避免空闲时隙的产生，可以保证无空闲时隙。

1.2 EHT算法流程

在EHT算法中，用堆栈来保存每次碰撞标签的碰撞位信息，并不断重复更新碰撞位信息，直到堆栈为空，算法结束。

EHT算法流程如下：

1）阅读器发送Request（？）命令给所有待识别的标签，？一开始为全“1”，这样可以保证一开始所有标签都能响应。

2）阅读检测碰撞位，并将碰撞位信息存入堆栈中，即执行POP（q）命令，并发送该命令，相应的标签会响应。

3）阅读器根据响应的标签数判断子树的时隙状态，会发生以下3种情况之一：

（1）如果子树上有且仅有一个标签响应，则该子树的时隙为成功时隙，即该标签识别成功，将其转换为休眠状态，跳转至（5）。

（2）如果无标签响应在该子树的时隙上，说明该子树的时隙为空闲时隙，跳转至（5）。

（3）若有两个及两个以上的标签响应，则该子树的时隙为碰撞时隙，跳转至（4）。

4）阅读器检测碰撞标签的碰撞位信息，此时会发生以下两种情况之一：

（1）若阅读器检测出有且仅有一个最高碰撞位时，选择二叉树算法，并将碰撞信息存放在堆栈中，即执行PUSH（0q，1q ）命令，跳转至（2）。

（2）若阅读器检测到最高碰撞位和次高碰撞位连续时，选择四叉树算法，并将碰撞位存放在堆栈中，即执行PUSH（××q）命令，跳转至（2）。

5）判断堆栈是否为空，如果不为空，则跳转至（2）；如果为空，则算法结束。

EHT算法流程图如图1所示。

2 实验仿真与分析

在MATLAB平台下编程进行实验仿真，本文算法标签数的最大取值为1000个，标签编码长度为64位，仿真实验100次取其最后平均值，在理想的实验环境下，误差率小于等于5%。将本文EHT算法与CT算法、AHT算法、ISE-BS算法作比较，分别进行了三组仿真实验对比：总时隙数对比、碰撞时隙数对比、算法识别效率对比，仿真结果如图2、3、4所示。

仿真实验一：总时隙数对比

从图2可以看出本文EHT算法在识别标签过程中所耗总时隙数较其他三种算法要少很多，当识别标签数达到1000个左右时，EHT算法所耗总时隙数为1200个左右，而CT算法超过了2000个，这也能说明EHT算法的优越性。而分析其原因是因为EHT算法在识别标签过程中不会产生空闲时隙，而CT算法和AHT算法会产生空闲时隙，这样就增加了总时隙数。

仿真实验二：碰撞时隙数对比

图3为各算法的碰撞时隙数比较，可以看出EHT算法在碰撞时隙数上与ISE-BS算法和AHT算法基本相近，但比CT算法减少了很多，这是因为CT算法利用的纯二叉树算法来进行识别标签，当代识别标签数增大是，碰撞产生的概率大大增加，从而产生了大量的碰撞时隙数。

仿真实验三：识别效率对比

识别效率作为衡量算法的好与坏的一个重要指标，识别效率高的算法更优。图4为各算法识别效率对比，可以得到，EHT算法识别效率是最高的，即使标签数目达到1 000时，仍可以稳定的保持在65%左右，从而可以得出本文提出的EHT算法性能比其他三种算法更高，能够高效解决大量标签碰撞问题。

3 结论

本文针对基于树的算法识别时间长，识别过程中会产生大量空闲时隙而降低识别效率的不足，提出了一种增强型混合树防碰撞（EHT）算法。在识别过程中根据响应的标签数动态选择二叉树、三叉树和四叉树，完全可以避免空闲时隙的产生。仿真结果表明，EHT算法可以减少在识别过程所耗总时隙数和碰撞时隙数，并且在提高算法识别效率的同时将其稳定地维持在0.65左右，因此EHT算法适合在需要快速读取大量标签的场合，能够实现快速准确的识别所有标签。