RFID 防碰撞算法研究

宋瑞玲，高仲合

SONG Ruiling,GAO Zhonghe

曲阜师范大学 计算机科学学院，山东 日照276826

College of Computer Science,Qufu Normal University,Rizhao,Shandong 276826,China

1 引言

射频识别（Radio Frequency IDentification，RFID）是一种利用射频信号通过空间电磁耦合实现无接触式的自动识别技术[1]。作为物联网的最核心技术之一，在物联网技术的引领下RFID 技术必将获得越来越大的发展空间。目前，RFID 技术以其特有的设备属性已被广泛应用于军事、交通、工业、医学以及日常生活的各个方面。

RFID 系统是由电子标签、阅读器、数据处理子系统等三部分[2]组成。当多个电子标签同时进入阅读器的阅读范围内时就会产生信息碰撞问题，信息碰撞使系统不能正常工作，导致误读和漏读等现象，限制了RFID 的实际应用。因此，需要一种防碰撞技术来解决碰撞问题，解决碰撞的算法称为防碰撞算法。

RFID 防碰撞算法采用的是多路存取的防碰撞方式，主要有时分多址、频分多址、码分多址、空分多址[3]。在RFID 系统中应用最多的是时分多址方式。而目前基于时分多址的防碰撞算法是基于aloha 的随机型防碰撞算法和基于二进制树的确定型防碰撞算法。

2 RFID 防碰撞算法

2.1 基于aloha 的随机型防碰撞算法

aloha 协议最早被用在分组无线网络中实现随机访问机制。基于aloha算法主要有纯aloha算法[4]、时隙aloha算法（SA）[5-6]、帧时隙aloha算法（FSA）、动态帧时隙aloha算法（Dynamic Frame Slotted Aloha，DFSA）[7]、自适应动态帧时隙，其中，DFSA 算法由于操作简单和性能良好，很多研究都是在该算法的基础上进行研究改进的。基于aloha 机制的算法操作简单、易于实现，但是其性能不稳定，识别效率不高，并且标签数量大时，部分标签在相当长的时间内得不到识别，会出现“饿死”现象。

2.2 基于二进制树的确定型防碰撞算法

基于二进制树的算法识别效率高，避免标签“饿死”现象，但通信量大，且有相当长的时延。基于二进制树[8-9]的改进算法有二进制搜索（BS）算法、动态二进制搜索（DBS）算法、后退式二进制（BBS）算法[10]、跳跃式动态二进制搜索（JDBS）算法。DBS 是在BS 算法基础上改进的，它避免了标签和阅读器之间的冗余传输，但搜索次数依然很多。BBS 相对于BS 算法搜索次数有所减少，但阅读器和标签之间存在大量的冗余传输。JDBS是由BBS 和DBS 改进的，不但搜索次数减少，而且避免了标签和阅读器之间的冗余传输，但是当大量标签被识别时，系统数据传输量很大，性能仍需进一步改进。动态调整二进制树形搜素算法基于一位冲突直接识别，当只探测到一位碰撞时，可直接识别出两个标签[11]。相比JDBS 进一步减少了搜索次数，但是当标签数量大，且标签ID 号较长时，出现一位碰撞概率相对较低，搜索次数减少不明显。文献[12]提出的一种算法是在动态调整算法基础上改进的，该算法通过引入分组策略，当只有两位碰撞位时即可直接识别，当标签较多时，搜索次数减少比较明显。本文结合以上各种算法的优点提出一种具体的改进算法。

3 改进算法

3.1 算法的几点约定

（1）算法是基于二进制树搜索算法提出的，要求阅读器能够准确地识别出数据的碰撞位置，这里采用曼彻斯特编码，该编码约定逻辑‘1’对应信号含下降沿跳变，逻辑‘0’对应信号含上升沿跳变，若无状态跳变，视为错误被识别。当两个或多个标签同时返回的某一数位有不同的值，则接收到的上升沿和下降沿相互抵消，以致出现“没有变化”或变化被明显消弱的状态，阅读器由此可判断该位出现了碰撞。

（2）标签内部设置了一个计数器R 用于存储标签ID中所有比特位的按位异或结果，R 的取值可在标签制造时固化写入，R 取值为0 和1 分别代表标签ID 中‘1’的个数是偶数和奇数。

（3）引入以下5 种命令描述算法：

①请求命令Request（nul，0），R=0组标签响应；Request（nul，1），R=1 组标签响应。这里还引入一个电子标签自身的标签选择计数器Counter，初始值设为-1，标签响应请求命令后变为0。

②请求命令Request(x，y)：x为检测到的最高碰撞位；y为0/1 比特位。阅读器向作用范围内的电子标签发送此命令，Counter=0 标签序列编码第x位为y值的标签则响应，将自身低于x位的序列编码传送各阅读器；其余未进入休眠状态的电子标签将自身的Counter加1。

③选择命令Select（ID）：选择标签。

④读命令Read（ID）：读取标签信息。

⑤去选择Unselect（ID）：使标签进入休眠状态。

3.2 算法思路

（1）阅读器发出请求命令Request（nul，0），其作用范围内的所有R=0 组标签响应请求命令并将自身ID 发给阅读器，该组标签的标签选择计数器Counter=0。

（2）阅读器对这些序列编码解码，如果碰撞位超过2则转到第（3）步；若没有碰撞或只有2 位碰撞时，阅读器即可成功识别出标签：

①如果不存在碰撞直接识别，转到（4）。

②当存在两个标签碰撞位时，阅读器通过奇偶校验位即可准确地识别出两个标签的序列编码，转到（4）。

（3）记录最高碰撞位x，最高碰撞位之前的序列压入堆栈记录。阅读器向其作用范围内的标签发送Request(x，0)命令，标签选择计数器Counter=0 的标签序列编码第x位为0 值响应，并将自身低于x位的序列编码传送给阅读器；其余未进入休眠状态的R=0 组的电子标签将自身的Counter加1，转到（2）。

（4）读写器对识别的标签相继发出Select、Read 和Unselect 命令，完成对标签的读写并使之进入休眠状态。所有未进入休眠状态R=0 组的标签的Counter 减1。返回上一次碰撞节点，阅读器发出Request(x，1)的命令，标签选择计数器Counter=0 的标签序列编码第x位为1 值则响应，将自身低于x位的序列编码传送个阅读器；其余未进入休眠状态的R=0 组的电子标签将自身的Counter加1，转入（2）。

（5）重复以上步骤，直到对R=0 组标签全部识别，然后以同样的方法识别R=1 组标签。

3.3 算法举例

假设阅读器范围内有6 个标签，各标签的编码A：10100000 B：10000100 C：10010000 D：10001000 E：00000001 F：00001000

（1）阅读器发出Request（nul，0）命令，其作用范围内A、B、C、D 响应并将自身ID 发给阅读器，Counter（A、B、C、D）=0。

（2）阅读器对这些序列编码解码为10????00，最高碰撞位5，最高碰撞位之前的‘10’序列压入堆栈。阅读器向作用范围内的标签发送Request（5，0），这时R=0 组内的B、C、D 响应，并把低于第5 位的序列编码传送给阅读器；而R=0 组内A 的Counter值加1。

（3）阅读器对这些序列编码解码为???00，最高碰撞位4，阅读器再次向作用范围内的标签发送Request（4，0），B、D 响应，将自身低于第4 位的序列编码传送个阅读器，A、C 的Counter加1。

（4）阅读器对这些序列编码解码为??00，所以B、D直接被识别。

（5）阅读器对B、D 标签完成读写并使之进入休眠状态。R=0 组内A、C 的Counter减1。

（6）阅读器再次向作用范围内的标签发送Request（4，1），只有C 标签响应，被识别。

（7）阅读器对C 标签完成读写并使之进入休眠状态。R=0 组内A 的Counter 减1。阅读器发出Request（5，1）命令，只有A 响应，直接识别。R=0 组标签全部被识别。

（8）阅读器发送Request（nul，1）命令，R=1 组内的E、F 响应，返回自身ID。

（9）阅读器对这些序列编码解码为0000?00?，只有两位碰撞所以直接被识别。

标签的识别过程如图1 所示。

图1 改进算法的标签识别过程

4 算法性能分析及仿真

对算法性能进行分析时主要考虑识别出所有标签时命令发送的总次数，命令参数长度和标签响应数据长度，等效分析识别出所有标签时命令发送的总次数，阅读器发送数据量和标签发送数据量。

4.1 识别标签所需搜索次数

（1）后退式二进制搜索算法

识别阅读器范围内的N个标签所需要总的搜索次数[13]：

（2）分组策略

本算法基于动态调整算法，通过设置一位奇偶校验寄存器实现分组，在识别过程中检测到只有两位碰撞位时即能直接识别标签，减少了搜索次数。

假设在识别过程中检测到M次只有2 个比特位发生碰撞时，采用本算法相当于在二叉树上减少了M个叶子节点，即搜索次数减少了2M次。

算法的搜索次数为：

特别地，当用ID 数位中的n位来表示2n个标签时，这时候搜索次数是2n-2。

这里取ID长度是64 bit借助Matlab工具对使用分组后不同数目标签对应搜索次数进行统计，如表1 所示。

表1 不同数目标签对应搜索次数

4.2 阅读器和标签之间的通信量

（1）标签发送总的通信量

JDS算法识别过程中，标签每次发送的数据平均长度[14]：

其中L是ID 号长度。

本文算法是基于JDS算法提出的，所以标签的通信量：

（2）阅读器发送的数据量

本算法中发送请求命令的第一个参数是最高碰撞位信息，与编码长度L 无关，与最高碰撞位P 有关，标签发送的二进制编码长度为[15]，得出本算法传输的二进制数据量：

标签阅读器之间总的数据通信量：

4.3 算法仿真

在Matlab 仿真平台上对本算法、动态调整二进制搜索算法、跳跃式动态二进制搜（JDBS）和基于后退策略的二进制搜索算法进行仿真比较。仿真实验中编码位数n取64。

图2是本文算法、动态调整二进制搜索算法、跳跃式动态二进制搜索（JDBS）和基于后退策略的二进制搜索算法阅读器进行搜索次数的比较。由图2 可以看出本算法相对其他算法搜索次数最少，当标签数目越多时本算法的优势越明显，这是因为本算法通过分组可以减少碰撞概率，并且仅有两位碰撞即可识别减少了搜索次数。

图2 不同算法搜索次数比较

图3～图5 是本算法、动态调整二进制搜索算法、跳跃式动态二进制搜索（JDBS）和基于后退策略的二进制搜索算法标签数据通信量、阅读器数据通信量以及阅读器和标签之间传输总的数据量进行的仿真结果。

图3 标签数据通信量

图4 阅读器数据通信量

图3 表明算法标签数据通信量最少的直接原因是搜索次数减少。图4 表明算法阅读器数据通信量最少的原因不但是搜索次数少，还有就是算法中发送请求命令的第一个参数是仅最高碰撞位信息也使数据通信量大大减少。图5 阅读器数据通信量和标签阅读器之间总的数据通信量取决于阅读器数据通信量和标签数据通信量，阅读器数据通信量和标签数据通信量的减少必然会使阅读器数据通信量和标签阅读器之间总的数据通信量减少，由图5 可以看出算法阅读器和标签之间传输总的数据量相比JDBS 减少量约50%，并且随着标签数目的增多减少量更明显，远多于50%。

图5 阅读器和标签之间传输总的数据量

5 结束语

本文是基于二进制搜索算法提出的一种具体的改进算法，该算法在动态调整算法基础上通过设置奇偶计数器来实现分组，一次搜索过程中所有响应的标签计数器R 值都相等，等效于每个响应标签ID 的‘1’的个数有相同的奇偶性，所以一次搜索过程中只有两次比特位发生冲突可以直接识别，分组进一步减少了阅读器的搜索次数。引入堆栈存放数据使请求命令参数简化得以实现，使阅读器数据通信量减少。通过仿真实验验证该算法具有明显的优越性。

[1] 张学军，王绪海，蔡文琦.基于分组码的改进型防碰撞算法研究[J].计算机应用研究，2012，29（11）：4265-4268.

[2] Ali K，Hassanein H，Tana A E M.RFID anti-collision protocol for dense passive tag environments[C]//Proceedings of the 32nd IEEE Conference on Local Compute Networks.Washington DC：IEEE Computer Society，2007：819-824.

[3] 朱军，张元，卢小冬，等.基于分段搜索的多RFID 标签抗冲突方法倡[J].计算机应用研究，2011，28（3）：1031-1033.

[4] Abramson N.THE ALOHA SYSTEM：another alternative for computer communications[C]//Proceedings of the November 17-19，1970，Fall Joint Computer Conference.ACM，1970：281-285.

[5] Maguire Y，Pappu R.An optimal Q-algorithm for the ISO 18000-6C RFID protocol[J].IEEE Transactions on Automation Science and Engineering，2009，6（1）：16-24.

[6] Finkenzeller K.RFID handbook fundamentals and applications in contactless smart cards and identification[M].2nd ed.West Sussex：John Wiley & Sons Ltd，2003.

[7] Vogt H.Efficient object identification with passive RFID tags[C]//Proceedings of IEEE International Conference on System，Man and Cybernetics，2002：651-656.

[8] Chen Z，Liao M.An enhanced dynamic binary anti-collision algorithm[C]//2010 5th International Conference on Computer Science and Education（ICCSE），IEEE，2010：961-964.

[9] Chen Y H，Horng S J，Run R S，et al.A novel anti-collision algorithm in RFID systems for identifying passive tags[J].IEEE Transaction on Industrial Information，2010，6（1）：105-121.

[10] Ryu J，Lee H，Seok Y，et al.A hybrid query tree protocol for tag collision arbitration in RFID systems[C]//IEEE International Conference on Communications，2007：5981-5986.

[11] 谢振华，赖声礼，陈鹏.标签防冲撞算法设计[J].计算机工程，2008，34（6）：90-92.

[12] 伍继雄，江岸，黄生叶，等.RFID 系统中二叉树防碰撞算法性能的提升[J].湖南大学学报：自然科学版，2010，37（12）：82-86.

[13] 王雪，钱志鸿，胡正超，等.基于二叉树的RFID 防碰撞算法的研究[J].通信学报，2010，31（6）：49-57.

[14] 王亚奇，蒋国平.基于分组机制的跳跃式动态二进制防碰撞算法[J].自动化学报，2010，36（10）：1390-1400.

[15] 吴跃前，辜大光，范振粤，等.RFID 系统防碰撞算法比较分析及其改进算法[J].计算机工程与应用，2009，45（3）：210-213.