摘 要：射频识别（RFID）技术是一种无接触的自动识别电子标签的技术，是物联网感知层中的一种重要技术。随着该技术在诸多领域的广泛应用，解决多标签识别问题的防碰撞算法显得越来越重要。目前的RFID防碰撞算法主要分为两大类：基于ALOHA的算法和基于树的算法。针对传统基于树的防碰撞算法识别时间较长、效率不高的问题，提出了一种基于四叉树的改进型RFID防碰撞算法，通过对电子标签的原始ID码进行分组后重新进行编码，消除了识别过程中的空闲时隙。经数学分析和仿真实验表明，在同等数量的标签情况下，该算法的识别时间较其它传统基于树的算法平均降低40%左右，识别性能得到了较大的提升。
关键词：射频识别；防碰撞；四叉树；标签识别
中图分类号：TP393 文献标识码：A 文章编号：2095-1302（2014）08-0024-04
0 引 言
RFID（Radio Frequency Identification）即射频识别技术的英文缩写，它利用射频信号通过空间耦合（交变磁场或电磁场）在阅读器和电子标签之间实现无接触的信息传递，并通过所传递的信息达到自动识别的目的[1]。作为物联网感知层中的一种主要技术，RFID目前已经在物流、仓储、交通等诸多领域广泛使用。但是，在一个阅读器的识别范围内如果有多个标签存在，当这些标签同时向阅读器传递信息时，阅读器就会检测到冲突，这称之为“碰撞”，从而造成标签识别失败[2]。为了解决这个问题，各种防碰撞算法被提了出来。
目前的RFID防碰撞算法主要分为两大类：基于ALOHA的算法[3]和基于树的算法[4]。基于ALOHA的算法运用了时分多址的思想，标签随机选择一个时隙发送信息，若发生碰撞则随机延迟一段时间再重发。这种算法由于对标签读取时间的不确定性，容易出现标签长时间不被阅读器读取的“饿死”现象[5]。基于树的算法采用轮询的思想，按照二进制组合规律，运用树的遍历算法对所有可能性进行搜索，直到识别出正确的数据。这种算法的标签读取时间是确定的，可以有效解决电子标签的“饿死”现象。但由于它对每种可能性都进行遍历，会导致读取标签的时延较长，标签数量较多时，算法的效率会明显降低[6]。
在基于树的防碰撞算法的基础上，本文提出了一种基于四叉树的改进型RFID防碰撞算法，通过改进四叉树的结构，降低标签识别时间，提高了识别效率。
1 基于树的防碰撞算法
树是一种重要的非线性数据结构，它主要由结点和分枝组成。结点即树中的每一个数据元素，除根结点和叶子结点外每个结点都有父结点和子结点；分枝即指向其子结点的分支[7]。基于树的防碰撞算法需要对标签的ID按照一定的长度进行分组，当分组长度为1时，即为二叉树算法；当分组长度为2时，即为四叉树算法；当分组长度为3时，即为八叉树算法……依此类推。在RFID系统中应用最广泛的是二叉树算法，它的基本原理是：阅读器给标签发送一个比特的查询码Q（0或1，相当于形成两个子树，先查询0子树，再查询1子树），在阅读器响应范围内的每一个标签判断自己的ID是否以Q开头，若是则将自己的ID传送给阅读器。这时，有可能会出现三种情况：识别（仅有一个标签以Q开头）、碰撞（有两个或两个以上标签以Q开头）、空闲（无标签以Q开头）[8]。若发生碰撞，则在前一个查询码后分别加上0和1，形成两个新查询码（相当于分裂成左右两个子树）。先发送末尾加上0的新查询码给标签，查询左子树；再发送末尾加上1的新查询码给标签，查询右子树。在查询过程中如果再次发生了碰撞，则重复上述操作，直到成功识别出全部标签为止[9]。假设有三个标签，其ID分别为：0101、0110、1010，若采用二叉树防碰撞算法，其识别过程如图1所示。
由以上识别过程可以看出，在基于树的防碰撞算法中，整个树的结点可分为四种：初始结点、识别结点、碰撞结点和空闲结点。初始结点有且仅有一个，识别结点的数量与标签数量相等，这两种结点的数量是确定的。因此，要提高识别效率，关键是想办法减少碰撞结点和空闲结点的数量。
在基于树的RFID防碰撞算法中除了应用二叉树外，多叉树在很多场合也有实际应用，如四叉树。四叉树中标签分组长度为2，结点编码共有四种组合：00、01、10、11。同样是如前所述的三个标签：0101、0110、1010，采用四叉树算法的识别过程如图2所示。
将四叉树和二叉树识别过程作对比可以发现，四叉树的碰撞结点较少，空闲结点较多。若能通过对四叉树的结构进行改进，减少甚至去除空闲结点，将大大提高识别效率。
2 基于四叉树的改进型防碰撞算法
基于四叉树的改进型防碰撞算法主要通过引入分组重编码的机制，改进生成树的结构，去除空闲时隙，缩短识别时间，从而提高识别效率[10]。整个算法主要由两部分组成：分组重编码和标签识别。
2.1 分组重编码
该算法首先要对标签的原始ID码进行分组，将原始ID码从最高位到最低位每两位分成一组，最后一组不足两位则补0。这样，每一组的两位ID就有四种组合：00、01、10、11，对应于四叉树的四个分支。
下来再对这四种组合的两位分组ID码重新进行编码，用新的编码来替换两位分组ID码[11]，重编码的规则如表1所列。
从表1可以看出，用来替换两位分组ID码的新编码最大长度4位，最小长度1位，平均长度2.5位，比原分组ID码的2位略有增加。新编码有一个显著的特点：最高位为1，低位全部为0。之所以采用这种编码规则，目的是使阅读器在识别过程中有更好的区分度，利用碰撞发生的位置就可以直接判断出参与碰撞的标签的替换编码。
以上的分组重编码操作均由标签完成，因此要求标签要具有存储和生成替换编码的能力。
2.2 标签识别
在识别过程中，电子标签可能处于以下三种状态[12]：
（1） 激活状态
当阅读器对响应范围内的标签发送初始化命令时，所有标签进入激活状态；另外，当标签的编码与阅读器发送的请求编码一致时，该标签也将处于激活状态。
（2） 安静状态
当标签的编码与阅读器当前发出的请求编码不同时，该标签将暂时退出通信连接，进入到安静状态，等待下一次被激活。
（3） 休眠状态
当一个标签已经被识别出来，它将进入到休眠状态，之后的通信过程不再进行任何响应，一直到整个识别过程全部结束。
具体识别过程如下：
（1） 阅读器向进入自己响应范围内的所有标签发送初始化命令，并令分组序号n=0。
（2） 处于激活状态的标签进行响应。若阅读器检测到未发生碰撞，则成功识别，转（4）；若发生碰撞，则标签令分组序号n=n+1，并发送其第n组替换编码。
（3） 阅读器接收到标签发来的替换编码，通过识别替换编码中碰撞发生的位置和数量，判断出响应范围内标签的替换编码的具体值，并将其和n值一起压入堆栈s中。
（4） 阅读器判断堆栈s是否为空，不为空则转（5），为空则转（6）。
（5） 堆栈s顶部编码和n值出栈，阅读器发送栈顶编码来请求标签，转（2）。
（6） 所有标签识别完毕。
识别过程中指定四种替换编码的压栈顺序为：1 000、100、10、1。
2.3 算法举例
假设在阅读器响应范围内有6个待识别的电子标签，其原始ID分别为：标签a：01101101、标签b：11000110、标签c：10011100、标签d：11001011、标签e：01001011、标签f：10101101，则各标签的原始ID经过分组重编码后对应的替换编码如表2所列。
3 性能分析与仿真
阅读器完成响应范围内所有电子标签的识别工作所花费的时间一般用时隙数作为单位，它是衡量防碰撞算法性能的重要标准之一，时隙数越少的算法性能越优越。因此，接下来用数学分析的方法推导出基于四叉树的改进型防碰撞算法的总时隙数值，并与二叉树、四叉树算法一起进行比较和仿真。
3.1 数学分析
设m为待识别的标签数，为总时隙数期望值，为碰撞时隙数期望值，为空闲时隙数期望值，为识别时隙数期望值。在基于B叉树的防碰撞算法中，
3.2 算法仿真
接下来对上述的数学分析用Matlab进行模拟仿真。
4 结 语
基于四叉树的改进型RFID防碰撞算法通过对标签的原始ID码采取分组重编码的手段，优化了生成树的结构，消除了空闲时隙，大大提高了标签的识别效率。通过数学分析和算法仿真，进一步证明了在同等数目的标签情况下，该算法的识别时间要明显低于传统的二叉树和四叉树算法，并且随着标签数目的增多，这种优势就更加明显。因此，该算法对于解决标签密集环境下的RFID防碰撞问题具有一定的实际意义。
参 考 文 献
[1]刘云浩. 物联网导论[M]. 北京：科学出版社， 2011，3：23-24.
[2] K.Dheeraj， K.W.Chin， and R.Raad. A survey and tutorial of RFID anti-collision protocols[C]. IEEE Transactions on Wireless Communication， 2010（12）：105-117.
[3] Finkenzeller K. RFID handbook， fundamentals and applications in contactless smart cards and identification[M]. New York： Wiley， 2003.
[4] Myung J.， Lee W.，Srivastava J. Adaptive binary splitting for efficient RFID tag anti-collision[C]. IEEE Communications Letters， 2006，10（3）：144-146.
[5] Jihoon Myung， Wonjun Lee. Adaptive binary splitting： a RFID tag collision arbitration protocol for tag identification[J]. Mobile Networks and Applications， 2006，11（2）：711-722
[6]苏晖. 射频识别防碰撞算法研究[D]. 重庆：重庆大学， 2012.
[7]严蔚敏，吴伟民. 数据结构[M]. 北京：清华大学出版社， 2011.
[8] Jae-Dong Shin，Sang-Soo Yeo，etc. Hybrid tag anti-collision algorithms in RFID systems[C]. ICCS 2007 Part IV， 2007：693-700.
[9]吴博，周铜，王栋. RFID防碰撞算法分析与研究[J]. 微电子学与计算机， 2009，26（8）：237-239.
[10]张学军，王绪海，蔡文琦. 基于分组码的改进型防碰撞算法研究[J]. 计算机应用研究， 2012，29（11）：4266-4267.
[11] Kuo-Hui Yeh， N.W.Lo. An efficient tree-based tag identification protocol for RFID systems[C]. 22nd International Conference on Advanced Information Networking and Applications， WAINA， 2008，220：966-970.
[12]田芸，陈恭亮，李建华. Bi-slotted binary tree algorithm with stack for radio frequency identification tag anti-collision[J]. Journal of Shanghai Jiaotong University（Science）， 2013，18（2）：173-179.
[13] Hush D R and Wood C. Analysis of tree algorithms for RFID arbitration[C]. Proceedings of IEEE Symposium on Information Theory， Cambridge， MA， USA. 1998：107-116.
