基于后退式搜索的自适应多叉树防碰撞算法

收稿日期:2011-01-24;修回日期:2011-03-07。

作者简介:孙文胜（1966-），男，安徽巢湖人，副教授，硕士，主要研究方向：嵌入式系统、无线通信与网络； 胡玲敏（1985-），女，湖北黄石人，硕士研究生，主要研究方向：射频识别、网络通信协议。

文章编号:1001-9081（2011）08-02052-04doi:10.3724/SP.J.1087.2011.02052

（杭州电子科技大学 通信工程学院，杭州310018）

（）

摘 要:针对无线射频识别（RFID）系统中常见的标签防碰撞问题，在后退式搜索算法的基础上提出了一种改进的多叉树防碰撞算法。根据标签碰撞的特点，采用休眠计数的方法，以及遇到连续碰撞位时进行四叉树分裂的策略，使得在搜索过程中能够动态选择分叉数量，缩短了标签识别时间，有效地提高了算法的搜索效率。性能分析表明，该算法的系统识别效率达76.5%，且随着标签数目的增多，优越性更加明显。

关键词:无线射频识别；标签碰撞；后退式搜索；标签识别

中图分类号: TP391.45文献标志码:A

Anti-collision algorithm for adaptive multi-branch tree based on

regressive-style search

SUN Wen-sheng, HU Ling-min

（College of Telecommunication Engineering, Hangzhou Dianzi University, Hangzhou Zhejiang 310018, China）

Abstract: Concerning the common problem of tag collision in Radio Frequency Identification （RFID） system, an improved anti-collision algorithm for multi-branch tree was proposed based on the regressive-style search algorithm. According to the characteristics of the tags collision, the presented algorithm adopted the dormancy count, and took quad tree structure when continuous collision appeared, which had the ability to choose the number of forks dynamically during the searching process, reduced the search range and improved the identification efficiency. The performance analysis results show that the system efficiency of the proposed algorithm is about 76.5%; moreover, with the number of tags increased, the superiority of the performance is more obvious.

Key words: Radio Frequency Identification （RFID）; tag collision; regressive-style search; tag identification

0 引言

无线射频识别（Radio Frequency Identification, RFID）技术是一种利用射频通信实现的非接触式自动识别技术，其应用开始于20世纪60年代。它以简单RFID系统为基础，结合已有的网络技术、数据库技术、中间件技术等，构筑出一个由大量联网的阅读器和无数移动的标签组成的，比因特网更为庞大的物联网，被广泛应用于生产制造、物流管理、门禁系统、零售业和仓储管理等领域。

随着RFID的普及和应用需要，多标签识别问题亟待解决。一般来说，在同一个射频识别系统中所有电子标签都工作在同一频段，如果在同一时刻多个标签同时发送信息至读写器，就会出现信息之间的相互干扰，使得读写器不能正常识别每个标签的信息，为了解决这个问题，必须采用合适的防碰撞算法。

1 RFID系统防碰撞算法分析

RFID系统的碰撞问题分为阅读器碰撞和标签碰撞两大类。本文主要研究标签的碰撞问题。传统的标签反碰撞算法包括以下4种［1］：空分多址（Space Division Multiple Access, SDMA）算法、频分多址（Frequency Division Multiple Access, FDMA）算法、码分多址（Code Division Multiple Access, CDMA）算法和时分多址（Time Division Multiple Access, TDMA）算法。

TDMA算法是把整个可供使用的信道容量按时间分配给多个用户，在RFID系统防碰撞问题上得到广泛的应用。目前研究的热点在于TDMA中的基于帧时隙随机分配多址（random assignment multiple access, ALOHA）算法和二进制树型算法。ALOHA算法被称为概率性反碰撞算法，它采用随机多址，标签利用随机时间响应阅读器的命令。其特点是：算法简单，便于实现，适用于低成本的RFID系统;但由于该类算法的时隙是随机分配的，这种可能性导致某一标签可能在相当长的一段时间内无法识别，而且在应用中，随着标签数量的扩大,性能将会急剧恶化，出现吞吐量偏低、饿死（starvation）、识别速度缓慢、能量消耗大等缺点。二进制树型算法被称为确定性算法，阅读器根据标签的唯一性来选择标签进行通信。该类算法比较复杂，识别时间较长，适合于待识别标签数量较多的场合;但该算法存在安全问题严重、实现复杂度高、能量消耗大等不足。在实际的RFID系统中，根据工作频率的特点，在高频（High Frequency, HF）频段，防碰撞算法一般采用传统的ALOHA算法。在超高频（Ultra High Frequency, UHF）频段，主要采用二进制搜索算法来避免碰撞。

本文针对这些缺点和不足，在相关算法和协议的基础上，对后退式搜索［2］算法进行分析和研究，提出一种改进的标签防碰撞算法。

2 基于后退式搜索的自适应多叉树防碰撞算法

2.1 算法原理及流程

本文算法采用曼彻斯特编码来判别位碰撞，保持后退式算法［2］的后退机理：碰撞发生时，根据碰撞的最高位，跳跃式向前搜索；无碰撞时，采取后退策略，实现标签的有序读取，并在此基础上进行如下改进。

1）引入了休眠计数［3］的方法。其设定标签有三种状态：待命态、休眠态和去活态。标签中设有一个休眠计数器。计数器的值为0时该标签处于待命态，大于0为休眠态，小于0为去活态。

2）碰撞前缀中出现连续碰撞位时采取四叉树分裂的策略。

3）只有一位碰撞位时直接识别。例如射频场内有01001101和01101101两个标签，阅读器探测到的返回数据为01X01101，由于只有一位冲突位，故阅读器可直接识别出2个标签电子编码（IDentity, ID）数据。

2.2 算法约定

后退式算法中引入休眠计数［3］，则正确识别一个标签后,阅读器发送激活命令Active（激活）命令,使各休眠标签将其各自的休眠程度寄存器减1。此时，休眠程度寄存器归0的标签转为待命态。算法再采用回跳策略开始执行。本文算法修改算法约定，将不需要阅读器发送激活命令，从而节省一半的命令数。

1）Request（X，m）请求命令。其中X{x1…xn}为阅读器发送请求命令的序列号参数（为n比特位的二进制数），m为检测到的冲突最高位。阅读器发送该命令给射频场内所有标签，区域内所有待命态的标签应答，这里对X有如下规定。

若X是全0，则处于待命态的标签若其ID号的第m到m-n+1位与X是否相同。如相同则应答,并返回冲突位及相关信息；若不同，则休眠程度加1。其他所有标签其休眠程度皆加1。

若X是全1，则所有标签的休眠计数值皆减1，这时处于待命态的标签，如果其第m到m-n+1位与X相同，则返回冲突位及相关信息。各标签休眠度不变。

否则，所有标签的休眠程度皆减1，对于待命标签判断自己的序列号第m到m-n+1位与X是否相同。若相同，返回冲突位及相关信息；若不同，则休眠程度加1。其他所有标签其休眠程度皆加1。

2）Read-Write读写指令。阅读器读写已识别的标签。

3）Unselect去活命令。取消事先选中的标签，使其进入“无声”状态。此状态下的标签不对阅读器任何指令作出反应，当标签离开阅读器作用范围（等于没有供应能量）后复位。

2.3 算法步骤

步骤1 初始化查询堆栈S为空，读写器发出搜索请求命令Request（NULL，N），阅读器作用范围内的所有待命标签应答。

步骤2 读写器根据标签响应，确定时隙状态，并根据时隙状态，自适应地选择搜索叉数和查询码。算法根据标签的响应,将时隙分为3种状态［1］。

1）碰撞时隙。区域内两个或两个以上的标签响应读写器的查询命令,由于发生碰撞,读写器无法对任意一个标签进行识别。

如果当碰撞前缀中出现连续碰撞位时，则选择动态四叉树搜索，并根据碰撞比特前两位的信息，确定四条新的Request查询参数，将其写入查询堆栈S。若只有一个碰撞位时，直接识别两个标签，否则选择动态二叉树搜索，并根据碰撞比特的首位信息，确定两条新的Request查询参数，将其写入查询堆栈S。

2）空闲时隙。说明区域内没有标签响应读写器的查询命令，在该分叉内无需继续搜索。

3）可读时隙。说明区域内有且只有一个标签响应读写器的查询命令，读写器可完成标签的识别和进行相应的读写操作。

步骤3 判断堆栈的内容是否为空，若不是，则读写器读取查询堆栈内的第一条Request命令参数按照约定规则继续搜索，并返回到步骤2；若是，则算法结束。

本文算法流程如图1所示。

图1 算法流程

2.4 算法举例

假设标签的编码为8位，阅读器作用范围内有6个标签:标签A为10011110，标签B为10011011，标签C为10001001，标签D为10100010，标签E为10100110，标签F为10110010。

1）读写器初始化清空查询堆栈，所有标签休眠度均置为0。读写器发送搜索命令Request（NULL，8），阅读器作用范围内的所有待命标签应答。根据Manchester编码原理，解码得到的UID数据为10XXXXXX，碰撞位为D6、D5、D4、D3、D2、D1，m取6。由于是连续碰撞位，故选择动态四叉树搜索，确定4条新的查询码Request（00，6）、Request（01，6）、Request（10，6）、Request（11，6）将其入栈。

2）阅读器从堆栈中获取栈顶查询指令Request（00，6），并发送该命令。所有待命的第6、5位为00的标签响应，这里是标签C，由于没有碰撞发生，正确识别。阅读器可以对其进行相应的操作（如Read-Write、Unselect等），使之处于“无声”状态。按规则，标签ABDEF转为休眠态，并将各自的休眠程度计数器置“1”。

3）正确识别一个标签后，算法再采用回跳策略开始执行，取出栈顶查询指令Request（01，6）。

4）阅读器发送Request（01，6）命令。标签ABDEF休眠度均减1，转为待命态，第6、5位为01的标签（即AB）应答，DEF休眠度均加1。解码得到的新的编码数据为1X1X，阅读器检测到新的最高冲突位为D3，故m取3。由于碰撞位不连续且不为1位，故选择动态二叉树搜索，得到下次Request命令所需参数Request（0，3）、Request（1，3）并且将其入栈。

5）阅读器发送Request（0，3）命令，标签B应答，处理完后执行Unselect命令，标签A转为休眠态，并将其休眠程度计数器置“1”，标签DEF休眠程度加1。

6）阅读器发送Request（1，3）命令。按照规则，所有的标签休眠程度减1，标签A应答，处理完后执行Unselect命令。

7）采用回跳策略，阅读器发送Request（10，6）命令。DEF休眠度减1，转为待命态，标签DE应答，标签F休眠程度加1。解码得到的新的编码数据为0X10，由于只有一位碰撞位，阅读器可成功识别出DE，再对其进行相应的操作后执行Unselect命令屏蔽掉它们。阅读器取出栈顶查询指令Request（11，6）。

8）阅读器发送Request（11，6）命令。标签F休眠程度减1，转为待命态并应答，到此所有标签全部被识别出来。

2.5 算法性能分析

2.5.1 自适应分叉的说明

本文算法中，若只有一个碰撞位时，直接识别两个标签；若碰撞前缀中碰撞位不连续时，选择进行二叉树分裂搜索；当碰撞前缀中出现连续碰撞位时，则要求进行四叉树分裂搜索，这是因为若想空闲时隙随着叉树的增长而减小，则系统分配的叉树不大于四叉，分析如下。

假设系统内有N个待识别标签，系统分配的叉树为L。当搜索深度为1时，标签的识别概率为P（1）（1-1/L）N-1。在搜索深度为k时，则所需搜索深度的均值E（k）为：

E（k）∑∞k1kP（k）P（1）∑∞k1k［1-P（1）］k-1（1）

因为1-P（1）

T（L）LE（k）L/（1-1/L）N-1（2）

由式（2）可见，若希望随着L的增加所需的平均时隙数T（L）减小，可由T（L+1）

1/（1-）N-1>1/（1-）N-1（3）

由树的性质可知，叉树L2m，m是不为0的任意整数。那么，结合式（3）整理可得：

L

设函数Y（x）1+，则当0

设x，考虑实际情况在N≥2时碰撞才有可能发生，可知当N2时x取得最大值。代入式（4）计算得到，只有当L

由式（2）可知，对于二叉树搜索，所需的平均时隙数为T22/（1-1/2）N-1。对于四叉树搜索，所需的平均时隙数为T44/（1-1/4）N-1。比较两式，可得当N≥3时，采用四叉树分裂搜索所需平均时隙少于二叉树搜索，亦即：在标签数量较多时，采用此算法可缩短搜索时间。

2.5.2 算法的识别效率

查询次数是决定系统效率的关键因素。假设系统内有N个待识别标签，所需查询次数为S（N），则系统效率e通常定义为如下形式［4］:

eN/S（N）（5）

1）后退式算法中，阅读器识别N个标签的查询次数S（N）［2］为：

S（N）2N-1（6）

系统效率即吞吐率e为：

e（7）

当N较大时，后退式的效率接近50%。

2）基于后退式搜索的自适应多叉树防碰撞算法中，采用动态分叉搜索，减少了搜索次数。

假设系统的标签分布是均匀的，根据算法描述，N个标签搜索方法被分为二叉树搜索和四叉树搜索，搜索次数分别为S（N）2-array，S（N）4-array，故总识别时隙S（N）即为二者时隙之和：

S（N）S（N）2-array+S（N）4-array（8）

设在整个识别过程中探测M次只有1个碰撞位，则在进行二叉树搜索时，本文算法比后退式算法减少了二进制搜索树的M个叶子节点，此时只需查询指令发送次数为：

S（N）2（N-M）-1; 0≤M≤N/2（9）

假设在深度k时，子节点标签数量平均为3。由算法特性可知，必然存在一个深度k，使得当搜索深度大于或等于k，搜索方法采用动态二叉树搜索；当搜索深度小于k，搜索方法采用动态四叉树搜索，即kTlog4,T表示向下去整。

S（N）4-array≈∑ki04i∑Tlog4i04i（10）

结合式（6）和式（9）可知，本文算法中的二叉树搜索次数为：

S（N）2-array≈（2×3-1）-2M≈-2M（11）

由于0≤M≤N/2，故N≤S（N）2-array≤5N/3。由式（8）可得：

S（N）S（N）2-array+S（N）4-array≈-2M+∑Tlog4i04i（12）

分析可知，M值越大，算法效率越高，接下来分析M的取值。将标签的产品电子代码（Electronic Product Code, EPC）认为是二进制树的叶子，如果有N个标签，M的最小取值为0，最大取值为TN/2，所以M的范围为0～TN/2。为了使其具有可比性，这样定义M［5］，即：当TN/2为偶数时，M的最大值为「N/4S；当TN/2为奇数时，M的最大值为「N/4S-1。

根据吞吐量的定义，由式（7）可得:

e（2（3-M）-1）+∑Tlog4i04i（13）

由于0

当发生大规模标签碰撞时，标签ID号连续性比较大，故探测到1位碰撞几率较大。例如当2L个标签第1次发送Request识别指令只探测出L个碰撞位时，可知识别过程中将出现连续的1位碰撞，此时，M2L/22L-1，S（2L）2L-1。可见，随着M的增大，在进行二叉树搜索时，本文算法的搜索次数比后退式算法以倍数级递减，系统效率得到明显提高。

2.6 算法仿真

下面使用Matlab仿真工具对本文提出的算法进行仿真实验。假设系统的标签分布是均匀的，仿真结果在相同实验条件下，取20次实验的平均值。

利用式（2）可分别得到二叉树搜索与四叉树搜索所需的时隙数，如图2所示。当标签数目大于3时，四叉树优于二叉树搜索；反之，二叉树优于四叉树。动态二进制算法对发送指令长度进行了研究，但未对多个标签的连续有序性读取进行分析。尽管后退式算法采取后退策略，能够实现标签的有序读取，但其发送指令长度比较固定［6］，仍需进一步改善。本文提出自适应多叉树搜索算法，在保持标签读取的有序性的同时，采用动态分叉搜索，对指令长度进行了动态调整，可以有效地减小发送指令长度，从而高效地利用信道。

图2 二叉树搜索与四叉树搜索所需时隙数的比较

图3中，针对标签数目从0到500的情况，根据式（6）及式（12），比较了后退式算法与本文的自适应多叉树防碰撞算法中查询次数的理论值。仿真结果表明：当标签数量较少时，探测到一位碰撞几率不大，本文算法比后退式算法只具稍微优势；当标签数量明显增多时，标签ID值比较接近，探测到一位碰撞的几率较大，即M较大，同时动态分叉的结合，使得搜索次数比后退式算法明显减少。由于传输信息的长度与搜索次数成正比，因此传输信息的长度得到降低，意味着系统的识别时间得到了提高。取20次实验的平均值，本文算法的系统识别效率为76.5%左右，而后退式算法的效率仅为50%左右。

3 结语

本文基于后退式算法，提出的一种自适应多叉树防碰撞算法。该算法结合休眠计数，去掉了原有的激活命令机制，节省了一半的后退搜索时间，并且可以灵活地根据碰撞时隙的连续性选择合适的分叉数量，由于对指令长度进行了动态调整，可以有效地减小发送信息量提高发送速率。仿真表明，与后退式算法相比，新算法的系统识别效率平均可达76.5%，且性能优势会随着识别范围内标签数目和产品EPC长度的增加越发明显。

图3 两种防碰撞算法的查询次数比较

参考文献:

[1] 丁治国.RFID关键技术研究与实现［D］.合肥：中国科学技术大学,2009:80-83.

［2］ 余松森,詹宜巨,彭卫东,等.基于后退式索引的二进制树形搜索反碰撞算法及其实现［J］.计算机工程与应用,2004,40（16）:26-28.

［3］ 姜丽芬,卢桂章,辛运帏.射频识别系统中的防碰撞算法研究［J］.计算机工程与应用,2007,43（15）:30-32.

［4］ 崔英花,赵玉萍.基于标签估计的动态最优多分支搜索防碰撞算法［J］.高技术通讯,2010,20（8）:772-774.

［5］ CHEN XIAOYUN, LIU GUOHUA, YAO YUKAI, et al. IRBST: An improved RFID anti-collision algorithm based on regressive-style binary search tree ［C］// 2010 International Forum on Information Technology and Applications. Washington, DC: IEEE Computer Society, 2010: 403-406.

［6］ VOGT H. Efficient object identification with passive RFID tags ［C］// Pervasive'02: Proceedings of the First International Conference on Pervasive Computing, LNCS 2414. Berlin: Springer-Verlag, 2002: 98-113.