一种改进的RFID防碰撞算法

冯东旭,夏哲雷,凌访华

(中国计量学院信息工程学院,浙江杭州310018)

0 引 言

射频识别(Radio Frequency Identification,RFID)技术是一种非接触的自动识别技术,其原理是利用射频信号的空间耦合或反射的传输特性,实现对被识别物体的自动识别[1]。防碰撞算法是RFID系统中的关键技术之一,当阅读器的作用范围内存在多个标签,并有两个或者两个以上的标签同时响应阅读器时将会产生碰撞。解决RFID系统中标签碰撞问题一般有空分多路、频分多路、码分多路和时分多路等方法[2]。但考虑到RFID系统中通信形式、功耗、系统的复杂性及成本等因素,目前广泛使用的防碰撞算法都是基于TDMA的,比较经典的两类是：基于ALOHA的防碰撞算法和基于二进制搜索的防碰撞算法。本文在二进制防碰撞算法的基础上,提出了一种改进的防碰撞算法。

1 RFID系统的构成

RFID系统一般由电子标签和读写器两部分构成。电子标签(又称应答器)是由耦合天线及芯片构成,每个标签具有唯一的电子产品代码(EPC),并附着在被标识的物体或对象上。读写器(又称阅读器)是读取或擦写标签信息的设备,用于发送和接收射频信号。读写器和标签之间采用非接触双向通信,已达到交换数据并识别的目的。RFID系统的结构组成如图1所示：

图1 RFID系统结构图

2 二进制防碰撞算法

二进制防碰撞算法的基本思想是将处于碰撞的标签分成左右两个子集0和1,先查询子集0,若没有碰撞,则正确识别标签,若有碰撞则再分裂,把子集0分成00和01两个子集。依次类推,直到识别出子集0中的所有标签,再按此步骤查询子集1[1]。

2.1 二进制搜索算法

二进制搜索算法采用曼彻斯特编码,能够准确检测出碰撞位的位置。为了实现这个算法,引入以下4种命令。

(1)REQUEST--请求命令：发送一序列号作为参数给区域内的标签。标签把自己的序列号与接收的相比较,若小于或者等于,则此标签回送其序列号给阅读器;

(2)SELECT--选择命令：用某个(事先确定的)序列号作为参数发送给标签。具有相同序列号的应答器将以此作为执行其他命令(读出和写入)的切入开关,即选择了标签;

(3)READ-DATA--读出数据：选中的标签将存储的数据发送给阅读器;

(4)UNSELECT--去选择：取消一个事先选中的标签,使其进入无声状态,这样标签对QEQUEST命令不再作应答。

假设阅读器范围内有 4个标签,即标签 1：10100111;标签 2：10110101;标签 3：10101111;标签4：10111101。二进制搜索算法的工作流程如下：

(1)阅读器发送REQUEST(11111111)命令,要求区域内所有标签应答。根据曼彻斯特编码,阅读器译码结果为101XX1X1,D1、D3、D4位发生碰撞,算法做如下处理：将碰撞最高位D4置“0”,高于D4位的数位不变,低于D4位的置“1”,可得到下一次REQUEST命令所需的参数,即10101111;

(2)阅读器发送REQUEST(10101111)命令,标签1和3应答。阅读器译码结果为1010X111,D3位发生碰撞,将D3位置“0”,低于D3位置“1”,得到下一次REQUEST命令所需参数,即10100111;

(3)阅读器发送REQUEST(10100111)命令,只有标签1应答。没有碰撞发生,阅读器对标签1进行读取操作后,执行UNSELECT命令使得标签1进入无声状态;

(4)算法从第一步重复上述过程直到所有的标签都被识别出来为止。

由二进制搜索算法的工作流程可知,标签的数量越多,防碰撞执行的时间将越长。此算法识别一个标签平均的搜索次数可用式N=logn2+1来计算,其中n为电子标签的个数[2]。

2.2 基于后退式索引的二级制搜索算法

此算法是在二进制搜索算法的基础上改进而来,与二进制算法不同的是该算法在阅读器识别出一个标签后不是从根节点开始重新查询,而是退到它的上一层节点,即父亲节点。

仍以4个标签为例,来说明此算法的实现过程。

(1)阅读器发送REQUEST(11111111)命令,标签1、2、3、4均应答。阅读器译码结果为101XX1X1,D1、D3、D4位发生碰撞,算法做如下处理：将碰撞最高位D4置“0”,高于D4位的数位不变,低于D4位的置“1”,可得到下一次REQUEST命令所需的参数,即10101111;

(2)阅读器发送REQUEST(10101111)命令,标签1和3应答。译码结果为1010X111,D3位发生碰撞,同上可得到下一次REQUEST命令所需的参数,即10100111;

(3)阅读器发送REQUEST(10100111)命令,只有标签1应答。没有碰撞发生,阅读器对标签1进行阅读操作后,执行UNSELECT命令使得标签1进入无声状态。算法采用后退策略,从该节点的父亲节点获得下一次REQEST命令的参数即10101111;

(4)阅读器发送REQUEST(10101111)命令,标签3应答,无碰撞。阅读器对标签3进行阅读操作后使其进入无声状态。算法再采用后退策略,得到下一次的寻呼命令REQUEST(11111111);

(5)阅读器发送REQUEST(11111111)命令,标签2和4应答,译码结果为1011X101,D3位发送碰撞,同样可得到下一次的寻呼命令参数REQUEST(10110111);

(6)阅读器发送REQUEST(10110111)命令,只有标签2应答,将标签2处理完毕后返回到父亲节点得到下次的寻呼命令参数REQUEST(11111111);

(7)阅读器发送REQUEST(11111111)命令,标签4应答,识别过程结束。

该算法的特点是：碰撞发生时,根据碰撞的最高位跳跃式向前搜索;无碰撞时,采取后退策略。这样能够有效地减少时间复杂度,更快速的识别所有标签[3]。

3 改进的防碰撞算法

3.1 算法的改进思路

与上述防碰撞算法相比,本文提出的算法主要有两点改进：(1)采用标识碰撞位的方法,把发生碰撞的比特位标识出来,只在被标识的比特位上进行防碰撞处理。因为如果阅读器译码有K个位置发生碰撞,说明只有这K个比特位对于阅读器来说是未知的,其他比特位对阅读器来说已经是已知的。因此在阅读器与电子标签的通信中可以不再传输这些已知的比特位,只在未知的比特位上作防碰撞处理,以减少传输时延和能耗;(2)采用曼彻斯特编码的电子标签的序列号每个比特位的取值不是1就是0,具有相互排斥的特性。所以如果阅读器检测到只有一个比特位发生碰撞时,则阅读器可以不需要发送请求命令而能够直接识别这两个标签。该算法在大量标签存在的情况下会大大缩短识别的时间、提高识别的效率。

本改进算法需要引入一条命令,即REQUEST(UID,0)。UID表示阅读器第一次寻呼之后,根据译码结果所得到的下一次的寻呼指令。UID的取值约定为：阅读器在判断出数据发生碰撞的准确比特位之后,将碰撞位置“1”,未发生碰撞的位置“0”,组成新的寻呼指令。阅读器发出这个寻呼指令之后,电子标签的响应为：标签接到这个命令之后将自己的序列号与之相比较,与UID中值为“1”所对应的比特位将被标识出来。在以后的防碰撞处理中,参与数据发送和比较的仅仅是这几个被标识的比特位。碰撞位被标识以后所有电子标签被标识的比特位中最高位为“0”的回送自己的ID给阅读器。下面以上述的4个标签和另外4个标签为例来说明这一过程,8个示范标签如表1所示：

表1 8个示范标签

3.2 算法的实现过程

(1)阅读器发送REQUEST(11111111)命令,区域内所有电子标签都应答。阅读器译码结果为：101XXXX1。可得到下一次的寻呼指令为REQUEST(00011110,0);

(2)阅读器发送REQUEST(00011110,0)命令,所有标签序列号的D4、D3、D2和D1位被标识,得到他们新的 ID：0011、1010、0111、1110、1111、0010、0101 和 1011,同时标签 1、3、6、7 回送自己新的 ID 给阅读器,阅读器译码为0XXX。得到下一次的寻呼指令REQUEST(0111,0);

(3)阅读器发送REQUEST(0111,0)命令,标签1、3、6、7应答其序列号的D2、D1、D0位被标识,得到他们新的ID：011、111、010、101,同时标签1和6回送自己新的ID号给阅读器。阅读器译码结果为01X,因为只有一个比特位发生碰撞,阅读器直接选择标签1和6。然后对这两个标签进行读写处理,最后读写器运行“去选择”命令使标签1和6进入“无声”状态。算法采用后退策略,从该节点的父亲节点获得下一次命令的参数REQUEST(111);

(4)阅读器发送REQUEST(111)命令,标签3和7应答,译码结果为1X1。因为只有一个比特位发生碰撞,阅读器直接选择标签3和7。然后对这两个标签进行读写处理,最后读写器运行“去选择”命令使标签3和7进入“无声”状态。算法再采用后退策略,从该节点的父亲节点获得下一次命令的参数REQUEST(1111);

(5)阅读器发送REQUEST(1111)命令,标签2、4、5、8应答,阅读器译码结果为1XXX。得到下一次的寻呼指令为REQUEST(1000,1);

(6)阅读器发送REQUEST(1000,1)命令,标签2、4、5、8应答其序列号的D2、D1、D0位被标识,得到他们新的ID：010、110、111、011,同时标签2和8回送自己新的ID号给阅读器。阅读器译码结果为01X,因为只有一个比特位发生碰撞,阅读器直接选择标签2和8,然后对这两个标签进行读写处理,最后读写器运行“去选择”命令使标签2和8进入“无声”状态。算法采用后退策略,从该节点的父亲节点获得下一次的命令参数REQUEST(111);

(7)阅读器发送REQUEST(111)命令,标签4和5应答,译码结果为11X。因为只有一个比特位发生碰撞,阅读器直接选择标签4和5。然后对这两个标签进行读写处理,最后读写器运行“去选择”命令使标签4和5进入“无声”状态。所有标签都被识别出来,识别过程结束。该实例防碰撞处理过程的树型结构图如图2示。

图2 算法实例的树型结构图

4 结束语

从图2可知改进算法识别8个标签的搜索次数为7次,而二进制搜索算法识别4个标签的搜索次数为12次,后退式索引搜索算法的搜索次数为7次。比较发现改进算法的搜索次数明显低于其他算法,可以通过数学归纳法证明,如果被标识的比特位中有n个参与以后的防碰撞处理,则识别2n个标签所用搜索的次数为2n-1-1次。另外,标签能耗的大小取决于阅读器寻呼次数以及标签接收和发送的比特长度。本改进算法采用标识碰撞位的方法仅让碰撞位参与防碰撞处理,使系统的传输数据量、搜索次数以及传输时间大大缩短,有效减少标签能耗,节省了传输信道提高识别效率。随着电子标签数目增加以及标签序列号比特位数变长,该改进算法的优势将会越来越明显。

[1]康东,石喜勤,李勇鹏,等.射频识别(RFID)核心技术与典型应用开发案例[M].北京：人民邮电出版社,2008：168-179.

[2]Klaus Finkenzellr.吴晓峰,陈大才,译.射频识别技术([第三版])[M].北京：电子工业出版社,2006：160-169.

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

[4]陈冲,徐志,何明华.一种新的 RFID防碰撞算法的研究[J].福州大学学报(自然科学版),2009,37(3)：367-371.

[5]Jia-linMa,XuWei.An Improved Anti-collision Algorithm In RFID System[J].Hybrid IntelligentSystems,2009,3(9)：138-141.