RFID多标签防碰撞原理与解决方法

刘鹏 长江大学计算机科学学院， 湖北 荆州 434023

RFID多标签防碰撞原理与解决方法

刘鹏 长江大学计算机科学学院， 湖北 荆州 434023

在射频识别系统中, 存在阅读器与多个标签同时通信的碰撞问题, 多标签识别的防碰撞算法是解决数据冲突的关键。本文分析了RFID多标签防碰撞原理，在此基础上提出了一些提高RFID多标签防碰撞效率的解决方法。

RFID；防碰撞；二进制算法

射频识别技术(RFID, radio frequency identification)是一种非接触式自动识别技术，通过空间射频信号自动获取信息，实现无线双向数据通信。与传统条形码、IC 卡等自动识别技术相比，RFID具有识别距离远、使用寿命长、安全性高、整个识别过程无需人工干预等优点，能广泛地应用于工业自动化、商业自动化、交通运输控制管理、防伪、军事等领域。

1. RFID系统的构成

RFID系统由阅读器(interrogator)、标签(tag)和后台网络3部分组成：标签分为有源标签和无源标签两大类，大多数RFID系统都采用无源标签；阅读器在后台网络系统控制下发送出一定频率的射频信号，当具有唯一ID号的标签进入阅读器磁场时会产生感应电流，从而获得能量，标签利用这些能量将反馈信息调制后发送回阅读器，该信息被阅读器解码后送至后台网络系统进行处理。

2. RFID多标签防碰撞算法分类

标签碰撞问题是指当读写器向工作场区内的一组电子标签发出查询指令时，由于2个或2个以上的电子标签同时响应读写器的查询，返回信息产生相互干扰，从而导致读写器不能正确识别其中任何一个电子标签的信息。随着电子标签数量的增加，发生多标签碰撞的概率也会增加，读写器的识别效率将进一步下降。

目前在RFID系统当中标签防碰撞算法主要由时分、频分、码分以及空分四种方法，分别利用时间，频率码元以及空间来达到防止RFID标签发生碰撞的目的。其中利用最多的时分方法。它主要分为基于概率的ALOHA算法和确定的二进制算法。

ALOHA算法是基于概率的，即每个电子标签随即发送数据，如果有两个以上电子标签在同一时间发送就会产生碰撞，电子标签等待一段时候后再发送，直到所有的电子标签被读取为止。该方法不受标签ID位数的影响。ALOHA算法非常简单，效率也不是很高，读取电子标签需要大量的时间。

二进制算法与基于概率的ALOHA算法不相同，它是一种确定的算法，它是现在使用最为广泛的标签防碰撞算法。每个电子标签都有自己的ID号，阅读器通过二进制算法来确定读取电子标签的顺序。二进制算法采用递归的工作方式，当遇到碰撞时，分支成2个子集，这些分支越来越小，直到最后当分支下面只有一个信息包时，完成识别过程；对于给定的标签群，二进制树算法能预测标签的识别顺序以及过程，因此被称为确定型算法。二进制树算法分为有记忆型和无记忆型2种。在有记忆型算法中，标签的反馈是由接收的指令以及标签的当前状态决定的，而无记忆型算法中，标签的反馈仅由接收的指令决定，以适应低成本和低功耗的要求。

3. 防碰撞基本原理

下面以二进制防碰撞算法为例来说明RFID多标签的防碰撞原理。阅读器发出请求命名，将接受电子标签发过来的标签号，如果没有接到ID，则没有标签发送，如果只有一个则不会出现标签的碰撞，直接选择此标签，如果两个以上ID号，将碰撞的最高位置为0，所有小于碰撞最高位值为1，将这个数据发送给电子标签，电子标签判断是否需要应答，所有要应答的标签发送自己的ID号给阅读器，直到没有碰撞，阅读器选定要发送数据的电子标签并且接收来自该ID号标签的数据，电子标签与阅读器的通讯结束之后，阅读器发送命令使此标签不再对查询名利应答，一直执行此操作直到所有标签发送完毕。

阅读器在识别的过程中使用了下面的指令：

(1) REQUEST指令，阅读器发送一段ID1，标签得到此ID1，然后与自己的lD号比较，从而判断时候要发送自己的ID号(当ID<= ID1时)。

(2) SELECT指令，阅读器发送ID1，当电子标签自己的ID=ID1时候，此标签被选中，选中的标签与阅读器之间进行数据的通讯。

(3)READATA指令，阅读器得到被选中标签的数据。

(4)UNSELECT指令，使已经发送完数据的标签睡眠，被睡眠的标签不再对指令做出反应。

采用这些命令，一个算法的识别过程如下：

现在假设有4个电子标签，且他们的标签号分别为A(11010111)，B(11100101)，C(11101111)，D(11010101)，则算法的流程为:

(1) 首先阅读器发送REQUEST(111111l1)，4个标签都接到此指令并发送自己的ID号，阅读器接收ID号，可以知道在5，4，3，1为发生碰撞，其他位可以识别，得到的结果11000101，因此可以得到下一次阅读器发送的查询ID号应为11011111。

(2) 发送REQUEST(11011111)，标签A，D发送11010111以及11010101，发生碰撞位可以知道是第一位，这样下一次的查询指令应该为11010101。

(3) 发送上一次得到的查询指令，后只有一个标签D满足发送条件，这样阅读器就可以正确识别标签的ID号，发送SELECT指令选中标签D，标签传完数据之后，执行指令使标签D睡眠，D不再对指令做出任何发应。

(4) 重复执行1～3，直到阅读器没有接受到任何ID号，这是所有的标签被识别。

4.提高RFID防碰撞效率的方法

从上面的过程首先可以看到在过程(2)中发送的位数较多，能不能采用合适的编码，使之包含较少的位数，又能知道碰撞发送的位置。其次，在过程(4)中，每次识别下一个标签都从第一个过程开始查询，能否从中间某个过程开始查询，也能达到同样的效果，这样如何减少查询次数。

算法的实现前提是标签到阅读器的数据传输选择一种合适的编码方法，以能够识别出冲突的准确位置。曼彻斯特编码满足这样的条件。曼彻斯特编码是用在一个位窗内的电平的改变(上升/下降沿)来表示某一位的。当多个标签同时发送的数据位有不同的值，则接收的上升沿和下降沿相互抵消，以致在某一个位窗之内“没有变化”。因此通过这种方式可以识别冲突的准确位置。

标签识别所花费的时间很大程度上取决于发生碰撞的时间(为处理发生碰撞的所有节点而花费的时间之和)。因此，通过减少发生碰撞节点的数量能够达到提高系统识别速度的目的。

减少REQUEST的命令的位数也是一个重要的解决思路。如果在碰撞位后面所有为都被设置为1，只要知道碰撞位，并不需要传输碰撞位后面的数字位，如只传送最高碰撞位以及最高碰撞位以前的数字，从而减少了传送的数据量，相应的增加了传送的效率，减少传送的时间。

[1]Myung J, Lee W, Srivastava J. Adaptive binary splitting for efficient RFID tag anticollision[J]. IEEE Communications Letters,2006,10(3):144～146

[2]王雪, 钱志鸿, 胡正超等. 基于二叉树的RFID防碰撞算法的研究[J]. 通信学报,2010,31(6):49～57

[3]冯娜，潘伟杰，李少波，杨观赐. 基于新颖跳跃式动态搜索的RFID防碰撞算法[J].计算机应用,2012,32(1) :288～291

[4]李萌，钱志鸿，张旭，王义君. 基于时隙预测的RFID防碰撞 ALOHA 算法[J]. 通信学报,2011,32(12):43～50

10.3969/j.issn.1001-8972.2012.07.052