RFID位屏蔽二进制搜索防碰撞算法研究

莫 磊

(四川托普信息技术职业学院通信系,四川成都 611743)

RFID位屏蔽二进制搜索防碰撞算法研究

莫 磊

(四川托普信息技术职业学院通信系,四川成都 611743)

在对基本二进制搜索树算法及其改进算法进行比较、分析的基础上,首次提出了位屏蔽搜索防碰撞算法,该算法利用“后退策略”以减少搜索的总次数;同时,利用已知信息,不发送和反馈重复信息,以减少阅读器和标签之间数据交换的比特数。该算法有效减少了命令发送的总次数和每次命令的参数长度,提高了搜索标签的效率和速度。

防碰撞;位屏蔽;射频识别

RFID(radio frequency identification)是一种非接触数据采集无线射频自动识别技术。RFID系统主要由2部分组成:阅读器和电子标签。每个标签都具有唯一的标识代码(ID)。当标签进入阅读器无线电磁场作用范围内,阅读器和标签之间通过无线射频进行双向通信,完成阅读器对标签的数据采集。阅读器和所有标签共用一个信道,当有多个标签同时向读写器发送数据,读写器就不能正确识别标签发送的数据,即发生了碰撞。为了保证阅读器对标签的准确识别,并读取标签的数据,需要一定的防碰撞算法来解决这些问题。

在现有的RFID防碰撞算法中,主要有ALOHA时隙防碰撞算法[1]和搜索树防碰撞算法[2]2种,ALOHA算法是概率性算法,比较简单,但随机性大,存在错判、漏判问题,其性能随着标签数量的增大而急剧恶化。搜索树算法是确定行算法,识别率较高,不存在错判、漏判问题,适合于标签数量较大的情况,但搜索树算法有较长的识别延时和较大的通信复杂度。笔者主要讨论搜索树防碰撞算法。

防碰撞算法的主要指标有:阅读标签的速度、读写信号的输出带宽、标签返回信号的带宽、准确率、稳定性、安全性和成本等。对于搜索树防碰撞算法,最重要的是要提高阅读标签的速度,减少读写信号的输出带宽以及标签返回信号的带宽。在不提高标签成本的情况下,如何快速高效地完成标签的识别,是当前RFID防碰撞技术的一个亟待解决的难题。笔者在现有的搜索树算法的基础上,首次提出了解决该难题的一个全新的方法:位屏蔽搜索树算法,该算法大大减少了阅读器和标签之间的数据通信量,提高了阅读标签的速度。

1 RFID二进制搜索树算法

在搜索树算法中,必须采用合适的编码,以便阅读器能够准确识别冲突位的准确比特位置。同时要保证所有标签能够同时传送数据,即能准确同步。曼彻斯特编码(Manchester)可在多个标签同时传送数据时按位识别出冲突位,现有的搜索树算法大多采用曼彻斯特编码。

1.1 二进制搜索树算法[3]

其基本思想是阅读器首先查询所有标签,看标签ID是否有冲突,若没有冲突,则正确识别标签,若有冲突,则标签分裂成2个子集:0和1。先查询子集0,若无冲突,则正确识别,若有冲突,再把子集0分裂成2个子集00和01。依次类推,直到识别出子集0的所有标签,接着再依此方法查询子集1。

设阅读器作用范围内标签数目为K,则基本二进制搜索树算法搜索到第1个标签的命令次数为完成所有标签识别的搜索命令次数为

阅读器发送单次命令的参数长度为N,标签返回单次命令的长度也为N。

1.2 返回式二进制搜索树算法[4]

在基本二进制算法中,当通过搜索识别出一个标签后,又从头开始新的搜索和识别。

返回式二进制搜索树算法中,当识别出一个标签后,并没有从头开始识别,这种算法利用了上次搜索获得的信息,利用“后退原则”,缩小了标签的搜索范围,减小了搜索次数。

返回式二进制搜索树算法完成所有标签识别的搜索命令次数为

和基本二进制搜索树算法相比,搜索次数大大减小。

阅读器发送命令的参数长度和标签返回数据的长度同基本二进制搜索树算法。

1.3 返回式动态二进制搜索树算法[4]

返回式二进制搜索树算法减小了搜索次数,但并没有减小阅读器发送命令和标签返回数据的参数长度。

前两种算法有一个缺点:阅读器发送命令和标签返回数据都有大量的重复信息。阅读器发出的请求命令中,最高冲突位后的所有比特位都被置1,对标签的识别不能提供任何的信息,对于标签来说,属于多余的重复信息;标签返回的数据中,最高冲突位以及最高冲突位以前的比特位对于阅读器来说,也是知道的,属于多余的重复信息。

返回式动态二进制搜索树算法对此作了改进,减小了这些重复信息的发送。

阅读器只发送最高冲突位以前的数据位,标签只返回最高冲突位以后的数据位。这样,阅读器发送命令的参数长度和标签返回数据的长度减少了一半。

返回式动态二进制搜索树算法完成所有标签识别的搜索命令次数和返回式二进制搜索树算法一样:

2 位屏蔽二进制搜索树算法

可以看出,以上所有算法中,动态二进制搜索树算法减少了重复发送的多余数据,识别速度最快,效率最高。但是,该算法仍有很多重复发送的数据,比如:阅读器每次只发送前Q个比特数据,减少了后面的(NQ)个比特数据的发送,但是,前Q个比特数据仍存在部分比特重复发送的问题。

有人对动态二进制搜索树算法提出了改进,提出了多状态二进制搜索树算法[5-11],主要思想:只发送首位碰撞位的位置信息,在该算法中,阅读器发送命令基本做到了无多余发送的重复信息,但标签返回数据中,仍有部分重复发送的无用信息,这必定会降低通信效率,减少识别标签的速度。

位屏蔽二进制搜索树算法的指导思想是:利用已知信息,不发送和反馈无用的重复信息,以提高标签识别速率。该算法借鉴了返回式二进制搜索树算法和动态二进制搜索树算法的基本思想,同时,充分利用了阅读器检测到的冲突位信息和已识别比特位信息,最大限度地减少了阅读器发送数据量和标签返回数据量。

2.1 算法实现

在位屏蔽二进制搜索树算法中,标签增加了一个位屏蔽寄存器R,以屏蔽多余的重复发送的信息,仅发送有用的碰撞位信息。屏蔽寄存器R的长度等于标签ID的长度N。

由于笔者首先提出了位屏蔽的概念,所以,先对位屏蔽作一个定义。

位屏蔽:指标签ID中和R的‘0’对应的比特位,反之,标签ID中和R的‘1’对应的比特位为非屏蔽位(或冲突位)。

屏蔽寄存器R的初始值全为‘1’。

假设标签ID号的长度为N,按位表示为1,2,…,N。

为了清楚地描述位屏蔽二进制搜索树算法,先对阅读器请求控制命令进行说明。

1)REQ0(SNR)

①SNR=0 请求所有标签返回标签ID数据。

②SNR≠0

a)R中‘1’的个数和SNR长度相等的标签更新屏蔽寄存器R,更新方法为SNR各位取代R的对应‘1’位。

b)按上述要求完成R更新的标签中,ID非屏蔽位首位为‘0’的标签,再次进行R更新,更新方法为R的最高‘1’位改为‘0’。该标签发送返回数据给阅读器,返回数据由标签ID非屏蔽位组成。

2)REQ1(SER)

标签收到命令后,则R中最高位‘1’为第SNR位的标签更新屏蔽寄存器R,更新方法为R中最高位‘1’改为‘0’。R完成更新后,该标签非屏蔽位组成返回数据,发送给阅读器。未更新R的标签不返回数据。

位屏蔽二进制搜索树算法的具体算法处理流程如下。

1)阅读器发送REQ0(0)。

2)标签收到命令后,所有标签同时返回ID数据给阅读器。

3)阅读器检测接收数据是否有冲突位,若没有冲突位,跳至5);若有冲突位,则可得到下次请求命令的SNR,构成如下:接收数据的所有冲突位为‘1’,其余位为‘0’,阅读器发送REQ 0(SNR)。

4)标签收到命令后,更新R,并发返回数据给阅读器。

5)阅读器检测接收数据,若有冲突位,跳至3);若没有冲突位,则识别出1个标签,阅读器读取该标签数据,对该标签进行去活化处理,该标签不再响应任何命令(要激活标签,必须暂时离开阅读器的作用范围)。

6)阅读器堆栈区弹出SER值,阅读器发送REQ1(SER)。

7)标签收到命令后,更新R,并发返回数据给阅读器。

8)跳至3),依次循环,直到识别出所有标签。

阅读器处理能力强,处理速度快,存储数据量大,可以处理比较复杂的算法。下面讨论步骤5)中阅读器识别标签的算法和步骤6)中阅读器计算出SER的算法。

阅读器中设置一个ID存储区域来存放收到的数据,由于位屏蔽二进制搜索树算法总的搜索次数为(2N-1)次,所以存储区大小可设置为(2N-1)。另外,阅读器还要设置一个堆栈区来存放SER值,SER值按后进先出的原则存取数据。算法如下。

1)若阅读器请求命令为REQ0(0),则直接存储收到的ID数据。

2)若阅读器请求命令为REQ0(SNR)(SNR≠0),则作如下处理:返回数据首位补0,组成一个新数据,该数据逐位取代前一个存储值的对应冲突位(前一个存储值还继续保留),得到一个新的存储值。

3)若阅读器请求命令为REQ1(SER),则返回数据首位补1,组成一个新数据;在ID存储区中,搜索最新存储的第SER位为首位冲突位的ID存储值,用该新数据逐位取代该ID存储值的对应冲突位(原存储值还继续保留),得到一个新的存储值。

4)若阅读器收到的ID数据有冲突位,最高冲突位为第Y位,则Y存于堆栈区。

5)若阅读器收到的ID数据无冲突位,则可识别出一个标签ID。

假设标签的编码为8位,阅读器作用范围内有4个标签,分别为

标签A:01101010;

标签B:01001011;

标签C:00101010;

标签D:10101001。

位屏蔽二进制搜索树算法过程如表1所示。

表1 位屏蔽二进制搜索树算法过程Tab.1 Process of binary searching algo rithm based on bit-shield

2.2 算法仿真

位屏蔽二进制搜索树算法和返回式动态二进制搜索树算法相比,其搜索方法都是基于后退策略的二进制搜索树算法,搜索次数是一样的,都是(2N-1)次。但是,位屏蔽二进制搜索树算法由于只传送标签ID位的冲突位信息,所以传送的比特数更少,标签识别速率得到了提高。

另外,由于采用了堆栈技术,使用后退策略搜索时,阅读器只发送ID的首位冲突位的位置信息,发送命令参数长度进一步减小。

为评价位屏蔽二进制搜索树算法的性能,对位屏蔽二进制搜索树算法和动态二进制搜索树算法进行了仿真,由于识别每个标签所需的平均比特数反映了防碰撞算法的平均最小时延,是衡量防碰撞算法的一个重要指标,所以,以识别每个标签所需的平均比特数作为指标进行仿真,假定略去控制命令本身及前、后缀等所需的比特数,则

其中,L(AVE)是识别每个标签平均比特数,L(TX)是阅读器发送命令参数总长度,L(RX)是标签响应命令参数总长度。仿真环境标签ID长度为96 bit,考虑到大多数在同一区域的ID有部分ID位相同的实际情况,假定其中16 bit是相同的,其余80 bit随机生成;标签数量为10～300。仿真结果如图1所示。

通过仿真结果可以看出,位屏蔽二进制搜索树算法明显优于动态二进制搜索树算法,这是由于位屏蔽二进制搜索树算法减少了多余的重复传送的比特数,效率更高,速度更快。

3 结 语

对二进制搜索树算法及其改进算法进行了分析,这些算法都存在重复发送已知信息的问题。为了减少阅读器和标签之间数据交换的信息量,提高标签识别速率,提出了一种新的搜索树防碰撞算法,全面利用已知信息,不发送和反馈无用的重复信息,标签识别速率得到较大提高。

笔者创新点:首次提出了位屏蔽的概念以及基于位屏蔽的二进制搜索树防碰撞算法,在标签内设置一个位屏蔽寄存器,凡是阅读器已知的数据位予以屏蔽,标签只发送阅读器不知道的冲突位信息。另外,还采用了堆栈技术,在使用后退策略搜索时,阅读器只发送最高非屏蔽的位置信息,发送命令参数长度进一步减小,最大限度地避免了重复发送信息,减少了数据发送比特数,能够快速、有效地识别多个标签。该算法对研究RFID防碰撞问题提出了一个全新的思路和方法,对RFID技术的推广和应用具有重要的意义。

图1 不同标签数量情况下识别每个标签平均比特数Fig.1 Average bit number of each tags identification in the case of different quantity of tags

[1] 万 红,杨延昭.RFID防碰撞算法研究与改进[J].微计算机信息(Microcomputer Information),2009,25(3-2):230-232.

[2] 林挺钊,刘建成.RFID二进制搜索算法的研究与改进[J].福建工程学院学报(Journal of Fujian University of Technology),2008,6(6): 732-736.

[3] 姜丽芬,卢桂章,辛运帷.射频识别系统中的防碰撞算法研究[J].计算机工程与应用(Computer Engineering and Applications),2007,43 (15):29-32.

[4] 王忠勇,高向川.基于回溯的RFID防碰撞算法[J].微计算机信息(Microcomputer Information),2009,25(2-2):187-188,217.

[5] 吴跃前,辜大光,范振粤.RFID系统防碰撞算法比较分析及其改进算法[J].计算机工程与应用(Computer Engineering and Applications),2009,45(3):210-213.

[6] 刘 丹,魏 鹏,谭 杰,等.一种RFID多标签碰撞检测方法[J].小型微型计算机系统(Journal of Chinese Computer Systems),2009,30 (9):1 890-1 894.

[7] 廉国斌.射频识别系统中的防碰撞算法研究[J].计算机技术与发展(Computer Technology and Development),2009,19(1):36-38.

[8] CHEN W T,L IN G H.An efficient anti-collisionmethod for tag identification in a RFID system[J].IEICE Transactionson Communications,2006(12):3 386-3 392.

[9] CHOIJ,LEED,YOUN Y.Scanning-based p re-p rocessing for enhanced RFID tag anti-collision p rotocols[A].International Symposium on Communications and Information Technologies(ISCIT’06)[C].[S.l.]:[s.n.],2006.

[10] 袁万锦,张 革.基于RC500的智能门禁控制系统研究[J].河北工业科技(Hebei Journal of Industrial Science and Technology),2006, 23(5):284-286.

[11] 刘东辉,张新岭,邱金蕙,等.基于无线传输的智能小区门禁系统设计[J].河北科技大学学报(Journal of Hebei University of Science and Technology),2007,28(1):37-40.

Research in binary tree anti-collision algo rithm based on bit-shield in RFID system

MO Lei
(Department of Communication,Sichuan TOP Vocational Institute of Info rmation Technology,Chengdu Sichuan 611743,China)

The elementary binary searching algorithm and some imp roved algorithm s are compared and analyzed,and an anticollision searching algorithm based on bit-shield isp roposed for the first time.The algorithm adop ts themethod of"back mechanism"to decrease the total timesof search,and by using know n information and not sending and responding redup licated information decreases the bits between the reader and the tags.The total timesof command and the length of parameter of every command are decreased effectively,and the efficiency and speed of tags identification is imp roved.

anti-collision;bit-shield;radio frequency identification

TP301

A

1008-1542(2010)05-0458-05

2010-04-01;责任编辑:陈书欣

莫 磊(1969-),男,四川遂宁人,讲师,硕士,主要从事RFID技术、自动控制技术方面的研究。