登录
注册
基于RFID的二进制防碰撞算法的改进
作者：亢军贤 张瑞生 夏禹 李武社 曾俊国
来源：RFID世界网
日期：2011-04-08 17:29:17
摘要：本文从RFID (Radio Frequency Identification, 无线射频识别技术)的关键技术之一射频标签序号防碰撞入手，先介绍了常用的二进制防碰撞算法，针对其在终端射频卡数量越多，UID(Ubiquitous Identifications，身份识别标签)位数越多，传送时间越长的缺点；提出了二进制防碰撞算法的改进算法，改进算法与传统算法相比，在标签位数逐渐增多的情况下，其查询次数增加速度明显减慢；最后通过仿真给以证实。
1. 引言
无线射频识别技术(Radio Frequency Identific -ation RFID)是从二十世纪90 年代兴起的一项非接触式自动识别技术。它是利用电磁原理进行非接触式双向通信，以达到自动识别目标对象并获取相关数据的目的。RFID 己被广泛应用于工业自动化、商业自动化、交通运输控制管理等众多领域[１]。随着成本的下降和标准化的实施，RFID 技术的全面推广和普遍应用将是不可逆转的趋势．
但 RFID 技术也存在着很多关键问题需要解决，例如RFID 技术的操作距离问题，安全和隐私问题，数据存储问题，碰撞问题等[2]。本文是论述有关RFID 的防碰撞问题。在很多情况下，阅读器射频区可能会有多个标签存在，面对阅读器发出的指令，每个标签都会响应，所以标签的响应信息会产生叠混的现象，在RFID 技术中这种现象被称为标签碰撞问题[3]。RFID 系统会采用一定的策略或算法来避免标签碰撞现象的发生，控制标签的响应信息逐个通过射频信道被阅读器接收。防碰撞问题的研究主要解决如何快速和准确地从多个标签中选出一个与阅读器进行数据交流，而其他的标签同样可以从接下来的防碰撞循环中选出与阅读器通信。
2 传统二进制算法
2.1 传统二进制算法的基本原理
在二进制搜索算法中，要能够检测出多张卡的存在，卡片的返回数据必须具有唯一性，且卡片在传输其UID(Ubiquitous Identifications，身份识别标签)时必须准确、快速、同步，这是防碰撞检测的关键。
传统二进制算法流程是，当阅读器发出的序列号大于标签序列号时，则阅读器作出响应。根据这一特点，传统二进制算法[4]的工作流程是:
①标签进入阅读器的工作范围，阅读器发出一个最大序列号让所有标签响应;同一时刻开始传输它们的序列号到阅读器的接收模块。
②阅读器对比标签响应的序列号的相同位数上的数，如果出现不一致的现象，则可判断出该位有碰撞。
③确定有碰撞后，把有不一致位的数从最高位到最低位依次置0 再输出系列号，即依次排除序列号大的数，循环至阅读器对比标签响应的序列号的相同位数上的数完全一致时，说明无碰撞。这时就选出序列号最小的数。
④选出序列号最小的数后，对该卡进行数据交换，然后使该卡进入“无声”状态，则在阅读器范围也不再响应(重新移入该标签才可再次响应)。
⑤重复流程①，选出序列号倒数第二的标签进行数据交换。
⑥多次循环后可完成所有标签的读取。
2.2 传统二进制算法的传输时间
由传统二进制算法的工作流程可知，防碰撞处理是在确认有碰撞的情况下，根据高低位不断降值的序列号一次次进行筛选出某一射频卡，从而可知标签的数量越多，防碰撞执行时间就将越长。查询的次数N 可用下式来计算:N=Integ(logM/log2)+l 式中:M 是终端作用范围内射频卡片数目;Integ 表示数值取整。UID 的位数越多(如ICODE 达64 位[5])，每次传送的时间加长，数据传送的时间就会增大。如每次都传输完整的UID，时间为T，则用于传输UID 的通信时间为:t=T×N 即终端作用范围内射频卡片数越多，UID 位数越多，传送时间越长，总的防碰撞执行时间肯定也就越长。
3. 改进的二进制算法
针对采用传统二进制搜索算法时终端射频卡片数越多，UID 位数越长，传送时间越长的缺点，目前提出了很多改良防碰撞算法，如：ALOHA 算法[6]， EPC 动态二进制算法[7]，跳跃式二进制算法[8]等，归纳一下基本采用两种方法改良算法的性能，一是减少传输数据的字节数，二是减少查询次数，本算法，试图将此两种方法应用到同一种防碰撞算法中。
3.1 改进的二进制算法的基本原理
本算法首先是标签阅读器发出请求指令，等待阅读器接收范围内所有标签第一位回应，标签回应完毕，程序检查是否碰撞，如果没有碰撞则转到读取各标签下一位，如果有碰撞则记录碰撞位，并优先选取各标签同样位上数据是0 的标签，选取完毕后，再将所选标签继续读取判断，直到所读取标签只有一个的时候，不论后面还有多少位，都不再读取，选定，并将标签代码完整读取并识别，然后屏蔽；之后返回离选取该标签最近的碰撞位，改变原来选取的0 值，现改为读取这一位上标签值为1 的标签继续进行选取判断，直到解决所有碰撞位并读取完阅读器阅读范围内所有标签为止，程序结束。
3.2 改进的二进制算法实例解析
以上是我的改进的二进制算法的基本原理介绍，为了解释的更加清楚，我通过五个标签的实例作进一步解析如表1：
本算法首先阅读器每次只接收 lbit 的数据，因此可以避开阅读器必须能够确定碰撞的准确的bit 位置这一困难，或者说可以避开阅读器必须对所有标签准确地同步这一困难，因而编码方式更加自由，实现起来更加容易。另外，在标签的序列号较短的情况下，用此种方法的算法在时间复杂度方面也优于二进制搜索算法。
3.4 仿真
下面使用 Matlab 仿真来对上述算法作进一步说明：其中n 为标签位数，m 为查询次数，m 和n 均取正整数(下同)。仿真结果如图1 所示：
4 结束语
在 RFID 系统的应用中，有效地解决标签的碰撞问题和如何提高标签的识别速率对整个RFID 系统的应用是至关重要的。尤其是在物流领域、仓库管理中，标签数量多、标签ID相似度高的场合中。本文提出了一种改进的RFID 防碰撞算法，与其他常用的防碰撞算法相比，如目前应用比较广泛的传统二进制算法，在有大量的标签存在、标签ID 度相似极高的环境中，显示出了明显的优势。
本文作者创新点:本文主要通过阅读古今中外的有关基于射频识别技术的防碰撞算法，结合自己的实践探索，从理论上分析了防碰撞的根本原理，针对传统防碰撞算法中存在的终端射频卡数量越多，UID(Ubiquitous Identifications，身份识别标签)位数越多，传送时间越长的缺点，提出了从低层二进制入手，运用计算机中查找二查树原理和路径最优化原理，对标签的选择实行最优化最快速的读取算法，本文最后对改进算法和传统算法进行仿真，从仿真结果可以看到改进算法明显优于传统算法，这个改进可以有效解决防碰撞问题。
参考文献
[1] FinkenzellerK 著，陈大译，射频识别技术.清华大学出版社，2000
[2] 游战清.无线射频识别技术(RFID)理论与应用[M].北京:电子工业出版社, 2004
[3] 张晖，王东辉．PLC 技术应用200 例．微计算机信息，2007，4-2：253-254。
[4] 陈博．一种类二进制搜索的RFID 系统反碰撞算法及其实现.电子器件，2006 年3 月，29 卷第一期
[5] Draft protocol specification for a 900 MHz Class 0 Radio Frequency IdentificationTag[Z],Auto-ID Certer,2003.
[6]吴春华、陈军，动态ALoHA 法在解决RFID 反碰撞问题中的应用【J].电子器件，2003 年第2 期:173 一176.
无线射频识别技术(Radio Frequency Identific -ation RFID)是从二十世纪90 年代兴起的一项非接触式自动识别技术。它是利用电磁原理进行非接触式双向通信，以达到自动识别目标对象并获取相关数据的目的。RFID 己被广泛应用于工业自动化、商业自动化、交通运输控制管理等众多领域[１]。随着成本的下降和标准化的实施，RFID 技术的全面推广和普遍应用将是不可逆转的趋势．
但 RFID 技术也存在着很多关键问题需要解决，例如RFID 技术的操作距离问题，安全和隐私问题，数据存储问题，碰撞问题等[2]。本文是论述有关RFID 的防碰撞问题。在很多情况下，阅读器射频区可能会有多个标签存在，面对阅读器发出的指令，每个标签都会响应，所以标签的响应信息会产生叠混的现象，在RFID 技术中这种现象被称为标签碰撞问题[3]。RFID 系统会采用一定的策略或算法来避免标签碰撞现象的发生，控制标签的响应信息逐个通过射频信道被阅读器接收。防碰撞问题的研究主要解决如何快速和准确地从多个标签中选出一个与阅读器进行数据交流，而其他的标签同样可以从接下来的防碰撞循环中选出与阅读器通信。
2 传统二进制算法
2.1 传统二进制算法的基本原理
在二进制搜索算法中，要能够检测出多张卡的存在，卡片的返回数据必须具有唯一性，且卡片在传输其UID(Ubiquitous Identifications，身份识别标签)时必须准确、快速、同步，这是防碰撞检测的关键。
传统二进制算法流程是，当阅读器发出的序列号大于标签序列号时，则阅读器作出响应。根据这一特点，传统二进制算法[4]的工作流程是:
①标签进入阅读器的工作范围，阅读器发出一个最大序列号让所有标签响应;同一时刻开始传输它们的序列号到阅读器的接收模块。
②阅读器对比标签响应的序列号的相同位数上的数，如果出现不一致的现象，则可判断出该位有碰撞。
③确定有碰撞后，把有不一致位的数从最高位到最低位依次置0 再输出系列号，即依次排除序列号大的数，循环至阅读器对比标签响应的序列号的相同位数上的数完全一致时，说明无碰撞。这时就选出序列号最小的数。
④选出序列号最小的数后，对该卡进行数据交换，然后使该卡进入“无声”状态，则在阅读器范围也不再响应(重新移入该标签才可再次响应)。
⑤重复流程①，选出序列号倒数第二的标签进行数据交换。
⑥多次循环后可完成所有标签的读取。
2.2 传统二进制算法的传输时间
由传统二进制算法的工作流程可知，防碰撞处理是在确认有碰撞的情况下，根据高低位不断降值的序列号一次次进行筛选出某一射频卡，从而可知标签的数量越多，防碰撞执行时间就将越长。查询的次数N 可用下式来计算:N=Integ(logM/log2)+l 式中:M 是终端作用范围内射频卡片数目;Integ 表示数值取整。UID 的位数越多(如ICODE 达64 位[5])，每次传送的时间加长，数据传送的时间就会增大。如每次都传输完整的UID，时间为T，则用于传输UID 的通信时间为:t=T×N 即终端作用范围内射频卡片数越多，UID 位数越多，传送时间越长，总的防碰撞执行时间肯定也就越长。
3. 改进的二进制算法
针对采用传统二进制搜索算法时终端射频卡片数越多，UID 位数越长，传送时间越长的缺点，目前提出了很多改良防碰撞算法，如：ALOHA 算法[6]， EPC 动态二进制算法[7]，跳跃式二进制算法[8]等，归纳一下基本采用两种方法改良算法的性能，一是减少传输数据的字节数，二是减少查询次数，本算法，试图将此两种方法应用到同一种防碰撞算法中。
3.1 改进的二进制算法的基本原理
本算法首先是标签阅读器发出请求指令，等待阅读器接收范围内所有标签第一位回应，标签回应完毕，程序检查是否碰撞，如果没有碰撞则转到读取各标签下一位，如果有碰撞则记录碰撞位，并优先选取各标签同样位上数据是0 的标签，选取完毕后，再将所选标签继续读取判断，直到所读取标签只有一个的时候，不论后面还有多少位，都不再读取，选定，并将标签代码完整读取并识别，然后屏蔽；之后返回离选取该标签最近的碰撞位，改变原来选取的0 值，现改为读取这一位上标签值为1 的标签继续进行选取判断，直到解决所有碰撞位并读取完阅读器阅读范围内所有标签为止，程序结束。
3.2 改进的二进制算法实例解析
以上是我的改进的二进制算法的基本原理介绍，为了解释的更加清楚，我通过五个标签的实例作进一步解析如表1：
本算法首先阅读器每次只接收 lbit 的数据，因此可以避开阅读器必须能够确定碰撞的准确的bit 位置这一困难，或者说可以避开阅读器必须对所有标签准确地同步这一困难，因而编码方式更加自由，实现起来更加容易。另外，在标签的序列号较短的情况下，用此种方法的算法在时间复杂度方面也优于二进制搜索算法。
3.4 仿真
下面使用 Matlab 仿真来对上述算法作进一步说明：其中n 为标签位数，m 为查询次数，m 和n 均取正整数(下同)。仿真结果如图1 所示：
图1 两种算法查询次数比较
4 结束语
在 RFID 系统的应用中，有效地解决标签的碰撞问题和如何提高标签的识别速率对整个RFID 系统的应用是至关重要的。尤其是在物流领域、仓库管理中，标签数量多、标签ID相似度高的场合中。本文提出了一种改进的RFID 防碰撞算法，与其他常用的防碰撞算法相比，如目前应用比较广泛的传统二进制算法，在有大量的标签存在、标签ID 度相似极高的环境中，显示出了明显的优势。
本文作者创新点:本文主要通过阅读古今中外的有关基于射频识别技术的防碰撞算法，结合自己的实践探索，从理论上分析了防碰撞的根本原理，针对传统防碰撞算法中存在的终端射频卡数量越多，UID(Ubiquitous Identifications，身份识别标签)位数越多，传送时间越长的缺点，提出了从低层二进制入手，运用计算机中查找二查树原理和路径最优化原理，对标签的选择实行最优化最快速的读取算法，本文最后对改进算法和传统算法进行仿真，从仿真结果可以看到改进算法明显优于传统算法，这个改进可以有效解决防碰撞问题。
参考文献
[1] FinkenzellerK 著，陈大译，射频识别技术.清华大学出版社，2000
[2] 游战清.无线射频识别技术(RFID)理论与应用[M].北京:电子工业出版社, 2004
[3] 张晖，王东辉．PLC 技术应用200 例．微计算机信息，2007，4-2：253-254。
[4] 陈博．一种类二进制搜索的RFID 系统反碰撞算法及其实现.电子器件，2006 年3 月，29 卷第一期
[5] Draft protocol specification for a 900 MHz Class 0 Radio Frequency IdentificationTag[Z],Auto-ID Certer,2003.
[6]吴春华、陈军，动态ALoHA 法在解决RFID 反碰撞问题中的应用【J].电子器件，2003 年第2 期:173 一176.
