基于四叉树的改进型RFID防碰撞算法

0引言

RFID（RadioFrequencyIdentification）即射频识别技术的英文缩写，它利用射频信号通过空间耦合（交变磁场或电磁场）在阅读器和电子标签之间实现无接触的信息传递，并通过所传递的信息达到自动识别的目的。作为物联网感知层中的一种主要技术，RFID目前已经在物流、仓储、交通等诸多领域广泛使用。但是，在一个阅读器的识别范围内如果有多个标签存在，当这些标签同时向阅读器传递信息时，阅读器就会检测到冲突，这称之为“碰撞”，从而造成标签识别失败。为了解决这个问题，各种防碰撞算法被提了出来。

目前的RFID防碰撞算法主要分为两大类:基于ALOHA的算法和基于树的算法。基于ALOHA的算法运用了时分多址的思想，标签随机选择一个时隙发送信息，若发生碰撞则随机延迟一段时间再重发。这种算法由于对标签读取时间的不确定性，容易出现标签长时间不被阅读器读取的“饿死”现象。基于树的算法采用轮询的思想，按照二进制组合规律,运用树的遍历算法对所有可能性进行捜索，直到识别出正确的数据。这种算法的标签读取时间是确定的，可以有效解决电子标签的“饿死”现象。但由于它对每种可能性都进行遍历,会导致读取标签的时延较长，标签数量较多时，算法的效率会明显降低。

在基于树的防碰撞算法的基础上，本文提出了一种基于四叉树的改进型RFID防碰撞算法，通过改进四叉树的结构，降低标签识别时间，提高了识别效率。

1基于树的防碰撞算法

树是一种重要的非线性数据结构，它主要由结点和分枝组成。结点即树中的每一个数据元素，除根结点和叶子结点外每个结点都有父结点和子结点；分枝即指向其子结点的分支。基于树的防碰撞算法需要对标签的ID按照一定的长度进行分组，当分组长度为1时，即为二叉树算法；当分组长度为2时,即为四叉树算法;当分组长度为3时，即为八叉树算法……依此类推。在RFID系统中应用最广泛的是二叉树算法，它的基本原理是：阅读器给标签发送一个比特的查询码Q（0或1，相当于形成两个子树，先查询0子树，再查询1子树），在阅读器响应范围内的每一个标签判断自己的ID是否以Q开头,若是则将自己的ID传送给阅读器。这时，有可能会出现三种情况：识别（仅有一个标签以Q开头）、碰撞（有两个或两个以上标签以Q开头）、空闲（无标签以Q开头）。若发生碰撞，则在前一个查询码后分别加上0和1,形成两个新查询码（相当于分裂成左右两个子树）。先发送末尾加上0的新查询码给标签，查询左子树;再发送末尾加上1的新查询码给标签,查询右子树。在查询过程中如果再次发生了碰撞，则重复上述操作，直到成功识别出全部标签为止。假设有三个标签,其ID分别为：0101、0110、1010,若采用二叉树防碰撞算法,其识别过程如图1所示。

由以上识别过程可以看出，在基于树的防碰撞算法中,整个树的结点可分为四种：初始结点、识别结点、碰撞结点和空闲结点。初始结点有且仅有一个，识别结点的数量与标签数量相等，这两种结点的数量是确定的。因此，要提高识别效率,关键是想办法减少碰撞结点和空闲结点的数量。

在基于树的RFID防碰撞算法中除了应用二叉树外，多叉树在很多场合也有实际应用，如四叉树。四叉树中标签分组长度为2,结点编码共有四种组合：00、01、10、11。同样是如前所述的三个标签：0101、0110、1010,采用四叉树算法的识别过程如图2所示。

将四叉树和二叉树识别过程作对比可以发现，四叉树的碰撞结点较少，空闲结点较多。若能通过对四叉树的结构进行改进，减少甚至去除空闲结点，将大大提高识别效率。

2基于四叉树的改进型防碰撞算法

基于四叉树的改进型防碰撞算法主要通过引入分组重编码的机制，改进生成树的结构，去除空闲时隙，缩短识别时间,从而提高识别效率。整个算法主要由两部分组成：分组重编码和标签识别。

2.1分组重编码

该算法首先要对标签的原始ID码进行分组，将原始ID码从最高位到最低位每两位分成一组，最后一组不足两位则补0。这样，每一组的两位ID就有四种组合：00、01、10、11，对应于四叉树的四个分支。

下来再对这四种组合的两位分组ID码重新进行编码，用新的编码来替换两位分组ID码，重编码的规则如表1所列。

从表1可以看出，用来替换两位分组ID码的新编码最大长度4位，最小长度1位，平均长度2.5位，比原分组ID码的2位略有增加。新编码有一个显著的特点：最高位为1,低位全部为0。之所以采用这种编码规则，目的是使阅读器在识别过程中有更好的区分度，利用碰撞发生的位置就可以直接判断出参与碰撞的标签的替换编码。

以上的分组重编码操作均由标签完成，因此要求标签要具有存储和生成替换编码的能力。

2.2标签识别

在识别过程中，电子标签可能处于以下三种状态:

激活状态

当阅读器对响应范围内的标签发送初始化命令时，所有标签进入激活状态；另外，当标签的编码与阅读器发送的请求编码一致时，该标签也将处于激活状态。

安静状态

当标签的编码与阅读器当前发出的请求编码不同时，该标签将暂时退出通信连接，进入到安静状态，等待下一次被激活。

休眠状态

当一个标签已经被识别出来，它将进入到休眠状态，之后的通信过程不再进行任何响应，一直到整个识别过程全部结束。

具体识别过程如下：

阅读器向进入自己响应范围内的所有标签发送初始化命令，并令分组序号”=0。

处于激活状态的标签进行响应。若阅读器检测到未发生碰撞，则成功识别，转(4)；若发生碰撞，则标签令分组序号n=n+1,并发送其第n组替换编码。

阅读器接收到标签发来的替换编码，通过识别替换编码中碰撞发生的位置和数量，判断出响应范围内标签的替换编码的具体值，并将其和n值一起压入堆栈s中。

阅读器判断堆栈s是否为空，不为空则转(5),为空则转(6)。

堆栈s顶部编码和n值出栈，阅读器发送栈顶编码来请求标签，转(2)。

所有标签识别完毕。

识别过程中指定四种替换编码的压栈顺序为：1000、100、10、1。

2.3算法举例

假设在阅读器响应范围内有6个待识别的电子标签，其原始ID分别为:标签a:01101101、标签b:11000110、标签c:10011100、标签d:11001011、标签e：01001011、标签f:10101101,则各标签的原始ID经过分组重编码后对应的替换编码如表2所列。

由上表可知，识别上述6个标签阅读器共需进行11次查询，若直接采用传统的四叉树算法则需要进行20次查询，可见改进型算法对于标签识别效率的提高非常显著。

3性能分析与仿真

阅读器完成响应范围内所有电子标签的识别工作所花费的时间一般用时隙数作为单位，它是衡量防碰撞算法性能的重要标准之一，时隙数越少的算法性能越优越。因此，接下来用数学分析的方法推导出基于四叉树的改进型防碰撞算法的总时隙数值，并与二叉树、四叉树算法一起进行比较和仿真。

3.1数学分析

四叉树算法的碰撞时隙数、空闲时隙数、识别时隙数和总时隙数(均为期望值)分别为：

基于四叉树的改进型算法，由识别过程可知，其碰撞时隙数与传统四叉树算法相同，并且通过对标签的原始ID编码分组(两位一组)后重新编码，实现了在识别标签的过程中将空闲时隙数降为0的目的。其捜索树的结构优化为一种无空闲结点的四叉树，相比传统的四叉树算法，贝崎:

3.2算法仿真

接下来对上述的数学分析用Matlab进行模拟仿真。

图3显示了二叉树算法、传统四叉树算法和改进型四叉树算法等三种算法的碰撞时隙对比。可以看出，在同等数量的标签情况下，改进型四叉树算法和传统四叉树算法的碰撞时隙数相等，且它们都比二叉树算法的碰撞时隙数少得多。

图3三种算法的碰撞时隙数对比仿真图

图4所示是三种算法的空间时隙数对比仿真图。通过图4可以看出，传统四叉树算法的空闲时隙数比二叉树算法的空闲时隙数要多，但改进型四叉树算法通过引入分组重编码机制，改进了四叉树的结构，从而彻底消除了空闲时隙。

图5所示是三种算法的总时隙数仿真对比图，通过仿真

结果可知，改进型四叉树算法的总时隙数比二叉树和传统四叉树算法的总时隙数要少，约为二叉树和传统四叉树算法的60%左右。并且，标签数量越大，这种差距就越明显。

图4三种算法的空闲时隙数对比仿真图

图5三种算法的总时隙数对比仿真图

通过以上的数学分析和仿真说明基于四叉树的改进型RFID防碰撞算法的标签识别性能要明显优于其它两种算法,其识别效率更高。

4结语

基于四叉树的改进型RFID防碰撞算法通过对标签的原始ID码采取分组重编码的手段，优化了生成树的结构，消除了空闲时隙，大大提高了标签的识别效率。通过数学分析和算法仿真，进一步证明了在同等数目的标签情况下，该算法的识别时间要明显低于传统的二叉树和四叉树算法，并且随着标签数目的增多，这种优势就更加明显。因此，该算法对于解决标签密集环境下的RFID防碰撞问题具有一定的实际意义。

20211221_61c1aa86f10c2__基于四叉树的改进型RFID防碰撞算法