一种改进的动态二进制防碰撞算法

岳青青

摘要：针对RIFD标签识别过程中的碰撞问题，在动态二进制防碰撞算法基础上提出一种改进的防碰撞算法。该算法在动态二进制算法基础上结合了后退式二进制算法，使阅读器不用每次从头开始发送请求命令，而且改进算法中引入了计数器，以控制标签状态信息。分析表明，该算法可以降低阅读器发送请求的次数，同时可以减少标签识别所需的时间。

关键词：射频识别（RFID）；碰撞算法；动态二进制；后退式二进制

DOIDOI：10.11907/rjdk.172434

中图分类号：TP312

文献标识码：A文章编号文章编号：16727800（2018）003008103

英文摘要Abstract：In this paper，in view of the occurrence of collision when identifying labels simultaneously in the RFID system，we introduced an improved dynamic binary anticollision algorithm.This algorithm combines the idea of dynamic binary algorithm and regressive binary algorithm，which avoid the reader starting sending request commands every time.In addition，the algorithm proposes a tag counter that control the status of tag.The analysis shows that the algorithm can reduce the number of times that the reader can send the request，and also reduce the time required to identify the label.

英文關键词Key Words：Radio Frequency Identification （RFID）； collision algorithm； dynamic binary searching algorithm； regressive binary algorithm

0引言

RFID（Radio Frequency Identification）是一种通过射频信号通信实现非接触的自动识别技术。RFID具有存储容量大、信息读取速度快、范围广等优点，是一种便捷、快速的信息识别技术。因此，该技术广泛应用于生产制造、交通物流、医疗管理、自动化、校园管理等各个领域。当阅读器的阅读范围出现两个以上标签发送标签信息时，由于信息间的相互干扰，导致阅读器无法正确识别每一个标签发送的数据信息，即出现了标签信息碰撞问题。

随着RFID技术的普及，很多应用场合都出现了碰撞问题，也成为了RFID系统应用急需解决的关键问题[1]。防碰撞技术是解决碰撞问题、提高标签识别效率的关键技术，主要解决的是如何快速、准确地从多个标签中选出一个与阅读器进行数据交流，而其它标签也以同样方法与阅读器进行数据交流[23]。

1算法约定

RFID系统二进制搜索算法采用曼彻斯特编码方法，通过电平的改变表示数值位，用逻辑“0”表示上升沿跳变，逻辑“1”表示下降沿跳变。当某一位不发生状态跳变时，读写器即知道该位发生了碰撞，产生错误，从而进行下一次循环。为了方便描述，使用如下不同的命令机制[4]：

（1）Request（请求）：阅读器向识别区域内的所有标签发送请求命令序列号ID，标签对该请求作出响应。

（2）Select（选择）：阅读器发送特定的请求命令ID，经过多次循环比较，只有与序列号ID相同的标签才能被选中。

（3）ReadDate（读数据）：被选中的标签发送自身携带的信息，阅读器接收来自该标签的编码信息。

（4）Unselect（取消选择）：对已经读写完信息的标签取消选中状态，使该标签进入“休眠”状态，对阅读器之后发送的任何请求命令序列号，该标签不再作出响应。

2改进的防碰撞算法

防碰撞算法主要分为确定性的基于树的防碰撞算法和概率性的基于ALOHA的防碰撞算法。在传统二进制搜索算法[5]中，当标签的EPC小于阅读器发送的命令ID时，标签才会响应阅读器命令，阅读器每完成一个标签的识别，都会从头开始搜索，每次传输的数据是全部长度的序列号。因此，学者们提出了许多改进的二进制防碰撞算法[68]。为了减少阅读器每次发送的请求序列长度，N为标签EPC编码的长度，X为标签碰撞的最高位。将最高碰撞位X置0，阅读器只传输NX位作为下一次的请求序列号，即动态二进制防碰撞算法[9]。为了减少阅读器查询次数，阅读器每识别出一个标签，不是从根节点重新查询，而是返回它的上一层，即后退式二进制防碰撞算法[1011]。其特点是标签发生碰撞时，根据碰撞位中的最高位向前搜索，无碰撞时采用后退策略。

为了减少传输的数据长度，提高标签识别速度，将动态二进制防碰撞算法与后退式二进制防碰撞算法相结合，并加入计数器，用于控制标签状态。当标签不再发生碰撞或者被识别后，选择邻近节点，结合动态二进制算法，使用最高碰撞位判断，满足最高碰撞位X为0的标签参与对阅读器命令的响应，否则被屏蔽。同时引入计数器，用于对被屏蔽标签状态的管理。当标签计数器中的状态S<0时，说明该标签信息已经被获取，S=0时的标签才对阅读器命令响应，S>0时同样对阅读器发送的请求命令不响应，改进算法流程如图1所示。

3算法原理实例

在改进的动态二进制防碰撞算法基础上，通过实例分析算法的可行性。假设阅读器的阅读范围内有5个标签，标签EPC长度为8位。用X表示一个碰撞比特位。

tag1：00010011tag2：11111100tag3：10010101

tag4：01100100tag5：01110101

（1）阅读器发送R（11111111），所有标签的计数器初始化值为S1=S2=S3=S4=S5=0，即所有标签对阅读器发送的指令进行响应。标签在发送EPC编码时发生碰撞，此时阅读器的译码结果为XXXXXXXX。最高碰撞位为D7。

（2）阅读器发送R（7，0），即判断所有标签的D7位是否为0，标签D7位为0的标签响应阅读器发送的请求，其余标签被屏蔽并且计数器值加1。标签2与3被屏蔽，计数器值加1，即S2=S3=1。标签1、4、5发送信息时发生碰撞，译码结果为0XXX0XXX。最高碰撞位为D6。

（3）阅读器发送R（6，0），标签D6位为0，且计数器值为0的标签响应。只有标签1响应，标签4与5被屏蔽，S2=S3=2，S4=S5=1。因此标签1被识别，与阅读器进行数据读写操作，完成后进行Unselect操作，使标签1处于“休眠”状态，不再参与信息响应。同时所有标签计数器值减1，S2=S3=1，S4=S5=0。此时标签4、5处于等待状态。

（4）阅读器返回上一层发送R（6，1）命令。此時只有标签4、5对该请求命令进行响应，标签2、3被屏蔽，计数值加1，S2=S3=2。标签4、5发送信息给阅读器，阅读器译码结果为：011x010x，最高碰撞位为D4。

（5）阅读器发送R（4，0），只有标签4对此命令响应，5被屏蔽C5=1。标签与阅读器进行信息读写，标签4进入“休眠”状态。其余标签计数器减1，S2=S3=1，S5=0。

（6）阅读器发送R（4，1），只有标签5响应，标签5与阅读器进行信息读写，处于“休眠”状态。标签计数器减1，S2=S3=0。

（7）通过后项搜索，发现只有碰撞位D7没有进行1检测。阅读器发送R（D7，1），只有标签2、3对阅读器的命令响应。标签2、3发生碰撞，阅读器得到的译码结果为1XX1X10X，最高碰撞位为D6。

（8）阅读器发送R（6，0），只有标签3响应，标签2被屏蔽，S2=1。标签3与阅读器进行读写操作，并进入“休眠”状态。同时计数器S2为0。

（9）阅读器发送R（6，1），只有唯一的标签2响应，并进行数据的读写等操作，此时所有标签都已经识别完毕。

4算法比较与分析

只使用5个标签的EPC编码，将改进算法与动态二进制算法进行对比。使用的标签为tag1：00010001，tag2：11111100，tag3：10010101，tag4：01110100，tag5：01110101。

动态二进制搜索算法整个搜索过程如表1所示。改进的动态二进制算法实施过程如表2所示。

通过表1、表2的分析，两种算法无论是阅读器搜索次数、标签碰撞次数还是阅读器发送指令的长度，改进的二进制动态算法都较原有的动态二进制算法有一定提升。

阅读器发送的指令更加简洁，碰撞次数也随之减少，其中改进算法中采用的计数器控制标签状态，使每次参与阅读器指令响应的标签数量减少，缩短了标签响应时间。

5结语

本文在动态二进制防碰撞算法基础上提出改进的动态二进制防碰撞算法，该算法结合了原始动态二进制和后退式二进制两种算法，并且加入了标签计数器。利用计数器的3种状态排除在请求外的标签则不再响应，减少了内部干扰，从而减少了算法搜索次数。同时将标签发送的请求命令形式简化，缩短了阅读器发送指令的长度与时间。因此，改进的算法具有一定优势。

参考文献参考文献：

[1]赵斌，张红雨.RFID技术的应用与发展[J].电子设计工程，2012，18（10）：123126.

[2]谢振华，赖声礼，陈鹏.RFID技术和防冲撞算法[J].计算机工程与应用，2007，43（6）：223225.

[3]张友能.射频识别系统中的防冲突算法研究[J].国外电子元器件，2008（12）：7174.

[4]高金辉，郑晓彦.RFID系统中二进制搜索防碰撞改进算法[J].计算机测量与控制，2012，20（10）：27542756.

[5]鲁玉军，吴远.RFID系统二进制防碰撞算法的研究[J].工业控制计算机，2015，28（5）：6264.

[6]杨晓娇，闫斌，谢光斌.一种改进的二进制防碰撞算法[J].计算机应用与软件，2013，30（10）：312316.

[7]潘磊，谌贵辉，李柯.二进制防碰撞算法在RFID系统中的改进研究[J].自动化与仪器仪表，2015，35（7）：161163.

[8]张鸣.RFID系统中改进的二进制防碰撞算法[J].工业控制计算机，2016，29（5）：2932.

[9]苏俊，王忠，陈和恒.基于动态二进制改进算法的RFID防碰撞算法[J].测控技术，2015，34（2）：111114.

[10]樊文静，张珊珊，田智慧.基于后退式二进制搜索的RFID防碰撞算法的研究[J].计算机应用与软件，2012，29（5）：191194.

[11]丰硕，高飞，薛艳明，等.一种改进的RFID标签防碰撞算法[J].微计算机信息，2011，27（1）：4952.

责任编辑（责任编辑：黄健）