基于多叉树搜索算法改进的RFID防碰撞算法*

林 伟，李景霞，叶林锋

（广东工业大学 计算机学院，广东 广州 510006）

射频识别技术（RFID）是一种非接触、低功耗、无线通信技术，可通过无线电信号识别特定目标并读写相关数据。典型的RFID系统由电子标签 (Tags)和读写器(Reader)组成，电子标签与读写器之间是通过耦合(天线)实现射频信号的空间(无接触）耦合。在耦合通道内，根据时序关系，实现能量的传递、数据的交换。其工作原理如图1所示。

图1 RFID工作原理

随着RFID技术的广泛应用，存在的问题也越来越凸显出来。目前RFID技术存在的主要问题有：安全问题、传输距离问题、碰撞问题等,其中碰撞问题严重制约着RFID的发展。目前,虽然已经有很多种防碰撞的算法，但是在算法执行效率和精确度方面各有缺陷。本文在研究大量防碰撞算法的基础上,经过比较分析提出了一种新的基于树搜索的防碰撞算法，该算法根据碰撞位的情况动态地选择合适的搜索树算法,大幅度提高了RFID的性能。

1 防碰撞算法简介

如果在RFID读写器可读取范围内有多个标签,或是一个标签同时接收到几个读写器发出的信号就会发生冲突，即所谓的碰撞。一旦发生碰撞就会导致读写器不能读取电子标签信息或是无法读到正确的标签信息，所以防碰撞算法就显得尤为重要。根据碰撞的产生原理可以将RFID的碰撞分为[1]：标签碰撞、频率干扰、标签干扰。其中频率干扰和标签干扰统称为读写器碰撞。

由于读写器碰撞的发生概率较小且容易避免，所以本文主要研究对象是标签碰撞。解决碰撞的算法就称为防碰撞算法。防碰撞算法最常使用的方法[2]有空分多址(SDMA)、频分多址(FDMA)、码分多址(CDMA)和时分多址(TDMA)。目前较为流行的RFID的两种防碰撞算法，基于ALOHA和基于树的算法都是基于时分多址的。

2 基于多叉树的RFID防碰撞算法

二进制树算法(BS)[3]的基本思想是将处于碰撞状态的标签分为0和1两个子集,先查询子集0,若没有冲突，则正确识别；若仍有冲突,则再分裂，把子集 0分为00和01两个子集，依次类推，直到子集0中的所有标签全部识别，再按照此步骤查询子集1。使用BS算法的标签要经过多次比较,并通过循环操作以达到识别所有标签,搜索过程中会出现路径的重复,搜索效率比较低[4]。为满足RFID系统能耗低、速度快等要求，其防碰撞算法有如下特点[5]：(1)识别过程中查询时间要短，查询次数也要尽量少。(2)对于无源标签来说必须是低能耗，要达到低能耗就要求算法中标签与读写器之间传输的比特数要少。(3)标签能够被完全、正确地识别，要求读写器对其可读取范围内的所有标签都要正确、完整地识别，不能出现错误识别和遗漏识别。本文提出的基于多叉树搜索的防碰撞算法在满足RFID防碰撞算法的基础上,尽量解决上述防碰撞算法中的问题。

2.1 算法的基本思想

读写器在发出Request命令后，读写器可读取范围内的所有标签都要做出应答，如果读写器译码后得到n个位发生碰撞，即只有标签这n个比特是读写器无法识别的。读写器根据这n个碰撞位所在的位置,分成三种情况进行处理：(1)若碰撞位连续两位,则采用动态四叉树分裂查询；(2)若碰撞位非连续,则采用动态二叉树分裂查询；(3)若碰撞位只有一位,则采用二叉树查询。

在发送查询指令时，不需发送碰撞标签完整的ID号，只要用二进制代码表示碰撞位即可，这样可以在很大程度上减少发送的数据量，继而降低功耗、提高识别效率。

2.2 算法的工作流程

算法的步骤如下：

(1)算法先发送一个Request(11111111)命令，所有电子标签对此做出应答，然后将自己的ID码发送出去。

(2)读写器检测接收到的信号，若未能检测到信号，则说明在读写器可读取的范围内没有电子标签，返回步骤(1)；若检测到信号，则转到步骤(3)。

(3)判断是否有碰撞发生，若无则对标签进行读写操作；若有,则转到步骤(4)。

(4)将查询码压入堆栈,并发送栈顶的查询码,满足该查询码的标签应答。判断碰撞情况：若没有标签应答,则读写器本次识别过程结束，并检堆栈是否为空；若只有一个标签应答，读写器发出RW-DATA指令,对该标签进行读写操作之后，读写器发出Sleep指令,标签进入休眠状态，不参与后续的识别过程;若有多个标签做出应答，即发生碰撞，则转到步骤(5)。

(5)根据碰撞位的不同情况,选择不同的搜索方法，重复步骤(4),直到堆栈为空。

(6)堆栈为空说明所有标签都被成功识别，整个标签识别过程结束。

2.3 算法举例

假如电子标签的ID码均是8位,在读写器可读取范围内有4个处于准备状态的电子标签 A、B、C、D,它们的ID 号为：TagA：10000110、TagB：11010010、TagC:01000010、TagD:01001010。本例的搜索过程中堆栈变化情况如图2所示，算法实现步骤如下：

(1)当读写器发出Request(11111111)指令后，得到译码后的碰撞位为：XX0XXX10。

(2)读写器将连续碰撞位XX用四叉树进行查询,发生碰撞的最高位为第7位，用二进制表示为111。将Request(00,111)、Request(01,111)、 Request(10,111)、Request(11,111)依次入栈，然后发送栈顶指令Request(00，111)，没有符合查询码的标签响应,该分支的识别过程结束；发送指令 Request(01,111)，有标签 C、D响应，即发生了碰撞，将C、D重新译码后得到新的译码数据为0100X010，此时读写器检测到只有一个碰撞位。参考文献[6]中设定只有一个碰撞位时,读写器能直接识别出两个标签，但是由于标签本身无法识别，所以只有一个碰撞位时，读写器也还是要经过一次比较，才能识别出两个标签最高碰撞位为第 3位,将 Request(0,11)、Request(1,11)压入堆栈。

图2 搜索过程中堆栈变化情况

(3)读写器发送 Request(0，11)命令，只有标签 D应答，经读写器读写操作后进入休眠态。

(4)读写器发送 Request(1,11)命令，只有标签 C应答，执行读写操作后转入休眠态。

(5)读写器发送 Request(10,111)命令，只有标签 A应答，执行读写操作后转入休眠态。

(6)读写器发送 Request(11,111)命令，只有标签 B应答，执行读写操作后转入休眠态。

(7)堆栈内的命令全部读取并发送，堆栈为空，说明待识别的标签全部识别完，标签识别过程结束。

3 新算法的性能分析

3.1 发送数据量分析

当标签的ID较长时,读写器每次发送的查询指令的位数就会很多，这样会严重影响传输速率和系统识别效率[6]。如果直接用二进制表示碰撞位的信息，则可以大大减少发送的数据量。假设标签的ID号有N位，则只要n位序列就能表示出所有的碰撞位，其中：

用q表示采用新算法前后发送数据量的比值，表示形式为：

由式(2)可知，随着N的增大，q值在减小，这表明在ID长度较大时，采用新算法在发送数据量上有更加明显的优势。

3.2 系统效率分析

系统效率是衡量一个算法优劣的很重要的标准。假设所研究的RFID系统内有N个待识别的标签，全部识别所需总的查询次数为T，则系统效率e通常定义为如下形式[7]：

本文根据碰撞位的情况选择动态二叉树或是用动态四叉树进行分裂搜索，所以本文算法总的查询次数是动态二叉树查询数和动态四叉树查询数之和：

假设在整个识别过程中查询M次只有1个碰撞位，则整个识别过程中有M个叶子节点，那么动态二叉树查询次数为：

所以本文中提出的二叉树查询次数为：

其中

由算法的特性可得，一定存在一个搜索深度l，使得搜索深度大于或等于l时，采用动态二叉树搜索；当深度小于l时，采用动态四叉树搜索，即l=log4，其中」为向下取整。

由式(2)、式(4)、式(5)得到新算法所需查询总次数为：

根据式(1)、式(6)，得到系统的效率，即吞吐率为：

4 实验仿真与分析

利用软件Matlab对上述算法的传输数据量、查询次数和吞吐率进行试验仿真，结果如图3所示。

图3 性能分析比较

由图3(a)可以看出,随着标签ID的增长，新算法的传输数据量增加很少，与未经过改进的算法的指令长度相比，新算法能很大程度地减少传输指令长度，从而能减少系统的能耗，增加系统的识别效率。

由图3(b)可以看出，在同样数目的待识别标签的情况下，动态二叉树和动态四叉树所需的查询总数，与本文的算法所需查询总数的比较中，本文新算法所需的总查询数较少，即识别时间较短。

由图3(c)可得新算法的吞吐率高于动态二叉树和动态四叉树搜索算法的吞吐率，即新算法的识别率更高。

本文在研究大量防碰撞算法的基础上经过比较分析，提出了一种新的基于树搜索的防碰撞算法，该算法根据碰撞位的情况，动态地选择合适的搜索树算法，而且本文还引用了堆栈来存储查询命令，这样可以避免重复、多余的搜索，减少了搜索树的分支数。由数学分析和算法的仿真结果可得，该算法查询时间短、系统效率高、性能优良，特别是在待识别标签数量庞大时，该算法表现出更加明显的优势。

[1]Jia Xiaolin,Feng Quanyuan,Fan Taihua,et al.Analysis of anti-collision protocols for RFID tag identification[C].IEEE 2012 2nd International Conference on Digital Object Identifier,2012.

[2]胡兆吉.基于嵌入式的射频识别系统[D].西安：西安电子科技大学，2011.

[3]丁治国.RFID关键技术研究与实现[D].合肥：中国科学技术大学,2009.

[4]李兴鹤，胡咏梅，王华莲，等.基于动态二进制的二叉树搜索结构 RFID反碰撞算法[J].山东科学，2006,19(2)：51-55.

[5]江岸，伍继雄，黄生叶，等.改进的 RFID二进制搜索防碰撞算法[J].计算机工程与应用，2009,45(5)：229-235.

[6]江城，黄立波.基于二进制搜索的RFID标签防碰撞算法研究[J].计算机与数字工程，2011(4):29-33.

[7]孙文胜，胡玲敏.基于后退式搜索的自适应多叉树防碰撞算法[J].计算机应用,2011,31(08)：2052-2055.

[8]丁俊.射频识别 RFID标签防碰撞算法[D].合肥：中国科技大学 2010.