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

《基于四叉树的改进型rfid防碰撞算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于四叉树的改进型RFID防碰撞算法　　摘要：射频识别（RFID）技术是一种无接触的自动识别电子标签的技术，是物联网感知层中的一种重要技术。随着该技术在诸多领域的广泛应用，解决多标签识别问题的防碰撞算法显得越来越重要。目前的RFID防碰撞算法主要分为两大类：基于ALOHA的算法和基于树的算法。针对传统基于树的防碰撞算法识别时间较长、效率不高的问题，提出了一种基于四叉树的改进型RFID防碰撞算法，通过对电子标签的原始ID码进行分组后重新进行编码，消除了识别过程中的空闲时隙。经数学分析和仿真实验表明，在同等数量的标签情况下，该算法的识别时间较其它传统基于树的算法平均降低40%左

2、右，识别性能得到了较大的提升。关键词：射频识别；防碰撞；四叉树；标签识别中图分类号：TP393文献标识码：A文章编号：2095-1302（2014）08-0024-040引言RFID（RadioFrequency9Identification）即射频识别技术的英文缩写，它利用射频信号通过空间耦合（交变磁场或电磁场）在阅读器和电子标签之间实现无接触的信息传递，并通过所传递的信息达到自动识别的目的[1]。作为物联网感知层中的一种主要技术，RFID目前已经在物流、仓储、交通等诸多领域广泛使用。但是，在一个阅读器的识别范围内如果有多个标签存在，当这些标签同时向阅读器传递信息时，阅读

3、器就会检测到冲突，这称之为“碰撞”，从而造成标签识别失败[2]。为了解决这个问题，各种防碰撞算法被提了出来。目前的RFID防碰撞算法主要分为两大类：基于ALOHA的算法[3]和基于树的算法[4]。基于ALOHA的算法运用了时分多址的思想，标签随机选择一个时隙发送信息，若发生碰撞则随机延迟一段时间再重发。这种算法由于对标签读取时间的不确定性，容易出现标签长时间不被阅读器读取的“饿死”现象[5]。基于树的算法采用轮询的思想，按照二进制组合规律，运用树的遍历算法对所有可能性进行搜索，直到识别出正确的数据。这种算法的标签读取时间是确定的，可以有效解决电子标签的“饿死”现象。但由于它

4、对每种可能性都进行遍历，会导致读取标签的时延较长，标签数量较多时，算法的效率会明显降低[6]。在基于树的防碰撞算法的基础上，本文提出了一种基于四叉树的改进型RFID防碰撞算法，通过改进四叉树的结构，降低标签识别时间，提高了识别效率。1基于树的防碰撞算法9树是一种重要的非线性数据结构，它主要由结点和分枝组成。结点即树中的每一个数据元素，除根结点和叶子结点外每个结点都有父结点和子结点；分枝即指向其子结点的分支[7]。基于树的防碰撞算法需要对标签的ID按照一定的长度进行分组，当分组长度为1时，即为二叉树算法；当分组长度为2时，即为四叉树算法；当分组长度为3时，即为八叉树算法……依

5、此类推。在RFID系统中应用最广泛的是二叉树算法，它的基本原理是：阅读器给标签发送一个比特的查询码Q（0或1，相当于形成两个子树，先查询0子树，再查询1子树），在阅读器响应范围内的每一个标签判断自己的ID是否以Q开头，若是则将自己的ID传送给阅读器。这时，有可能会出现三种情况：识别（仅有一个标签以Q开头）、碰撞（有两个或两个以上标签以Q开头）、空闲（无标签以Q开头）[8]。若发生碰撞，则在前一个查询码后分别加上0和1，形成两个新查询码（相当于分裂成左右两个子树）。先发送末尾加上0的新查询码给标签，查询左子树；再发送末尾加上1的新查询码给标签，查询右子树。在查询过程中如果再次

6、发生了碰撞，则重复上述操作，直到成功识别出全部标签为止[9]。假设有三个标签，其ID分别为：0101、0110、1010，若采用二叉树防碰撞算法，其识别过程如图1所示。9由以上识别过程可以看出，在基于树的防碰撞算法中，整个树的结点可分为四种：初始结点、识别结点、碰撞结点和空闲结点。初始结点有且仅有一个，识别结点的数量与标签数量相等，这两种结点的数量是确定的。因此，要提高识别效率，关键是想办法减少碰撞结点和空闲结点的数量。在基于树的RFID防碰撞算法中除了应用二叉树外，多叉树在很多场合也有实际应用，如四叉树。四叉树中标签分组长度为2，结点编码共有四种组合：00、01、10、1

7、1。同样是如前所述的三个标签：0101、0110、1010，采用四叉树算法的识别过程如图2所示。将四叉树和二叉树识别过程作对比可以发现，四叉树的碰撞结点较少，空闲结点较多。若能通过对四叉树的结构进行改进，减少甚至去除空闲结点，将大大提高识别效率。2基于四叉树的改进型防碰撞算法基于四叉树的改进型防碰撞算法主要通过引入分组重编码的机制，改进生成树的结构，去除空闲时隙，缩短识别时间，从而提高识别效率[10]。整个算法主要由两部分组成：分组重编码和标签识别。2.1分组重编码该算法首先要对标签的原始ID码进行分组，将原始ID