一种改进的位竞争式RFID防碰撞算法*

2014-02-10蔡彬元宋依青王海龙

通信技术 2014年10期

关键词：堆栈阅读器时隙

蔡彬元,宋依青,王海龙,骆华

(1.曲阜师范大学,山东曲阜273165;2.常州工学院,江苏常州213002)

一种改进的位竞争式RFID防碰撞算法*

蔡彬元1,宋依青2,王海龙1,骆华1

(1.曲阜师范大学,山东曲阜273165;2.常州工学院,江苏常州213002)

为解决射频识别系统中的标签防碰撞问题,在基于位竞争算法的基础上提出一种改进的防碰撞算法(IBCA)。改进的算法首先加入锁位机制,使阅读器通过锁位的方法将标签的碰撞比特位提取出来,之后和标签仅通信这些碰撞位,再按位进行“或”运算。然后再通过设置堆栈,使得每次识别完一个标签后返回上一个碰撞位。算法考虑了碰撞时隙数和阅读器问询次数两个性能指标,仿真结果表明,IBCA算法较BCA算法性能有很大提高。

位竞争锁位堆栈

0 引言

在当前研究热门的物联网领域中,射频识别技术(RFID,Radio Frequency Identification)是底层关键技术之一,它是一种非接触式的自动识别技术,可以实现对目标信息的自动采集,能够在恶劣、无人的环境中工作[1]。RFID系统主要包括电子标签与阅读器,它们之间通过射频信号进行数据传递与交互。

标签碰撞问题是RFID系统需要解决的主要问题,它是指同一时刻在阅读器范围内有多个标签发送响应信号,此时阅读器在同一时刻收到的数据之间发生干扰,由于这种干扰而无法正确识别任何标签。标签碰撞问题极大恶化了RFID的系统效率,目前主要利用TDMA防碰撞算法[2]来改善这一问题,其中包含两种主要算法:ALOHA[3]算法和二叉树算法[4]。ALOHA算法是一种不确定性的算法,因此会出现某些标签不能被识别的可能,通常称为“饿死”现象。二叉树算法是一种确定性算法,它可以解决标签“饿死”现象,但是由此却产生了高延时和高功耗的问题。

1 位竞争式防碰撞算法

如果阅读器范围内标签的数量进一步增大,标签的碰撞问题就会变得更加严重,系统效率急剧降低,采用上述的防碰撞算法产生大量碰撞时隙和空闲时隙,不能很好解决这一情况。文献[5]提出了一种基于位竞争(Bit Competed Algorithm)的防碰撞算法来提高系统的性能。

算法如图1所示,4个标签A,B,C,D的UID (唯一识别码)分别为0010,0101,1100,1110,阅读器首先发送请求信号给所有标签,标签据此发送自己的UID给阅读器,这时发生碰撞,阅读器便从高位到低位利用“或”运算筛选识别标签。

图1 BCA算法Fig.1 BCA algorithm

图1中先从第3位开始进行“或”运算,如果结果为0,直接开始下一位的运算,此时结果为1,第3位为0的标签A,B退出竞争,剩下的C,D由于第3位都是1,无法确定优先级,阅读器开始对C,D的第2位进行“或”运算。第2位的运算结果仍然是1,此位上没有比特为0的标签,阅读器则继续对第1位做“或”运算。第1位运算结果为1且只有唯一一个标签此位上比特值为1,阅读器选中D而C退出竞争。识别出标签D后阅读器从头开始从第3位开始识别标签,重复运算和识别直到识别出所有响应标签。

BCA防碰撞算法,使用“或”运算竞争出优先识别的标签,是一种新的防碰撞算法,保证阅读器每次询问至少可识别一个标签,且它所产生的问询次数,碰撞次数,复杂程度与其他算法相比有很大的竞争力。但是BCA算法也有很多不足之处,如每次成功识别一个标签之后要从头开始询问标签UID,这使阅读器的询问次数和传输的数据量大幅增加,导致整体系统效率降低,因此,将对这些问题提出解决方法。

2 改进的位竞争式防碰撞算法

针对上述对BCA防碰撞算法存在的一些问题,提出一种改进的位竞争式防碰撞算法(Improved Bit Compete Anti-Collision Algorithm)。在IBCA算法中,首先将碰撞标签的碰撞位取出,在通信过程中只传输比较这些碰撞位,降低系统传输数据量。接着阅读器会记录下此次竞争失败的比特位置和标签数量,当成功识别一次的标签后,只要从堆栈中取得之前竞争失败的标签信息,从当时竞争失败的下个位比特位置继续竞争,不需要从第一位比特重新竞争,这样可以减少问询次数并有效减少与标签通信的信息量传输,进而提升系统效率。

2.1 曼彻斯特编码

系统通过曼彻斯特编码方式来标记具体碰撞位。标签首先通过曼彻斯特编码自己的UID,将其中的“1”表示为由高电平跳变的低电平,“0”表示由低电平跳变的高电平。标签将自己的UID同步发给阅读器,阅读器检测某段同步时间内的电平,如果没有发生变化则判断出此位发生了碰撞,如图2所示。

图2 曼彻斯特编码Fig.2 Manchester encoding

2.2 锁位

阅读器判断出发生碰撞的比特位后,通过译码将碰撞位置1,其他位置0,生成新的请求信号发送给标签。标签收到请求信号后与自身UID作对比,将未发生碰撞的位锁住,下一轮通信过程中只发送发生碰撞的位,这样就降低了系统传输的数据量,如图3所示。

图3 锁位过程Fig.3 Bit-locking process

2.3 设置堆栈后退

为了减少传输过程中的通信次数,通过设置堆栈使阅读器在成功识别完一个标签后不必从头开始识别下一标签。阅读器收到标签发送的碰撞位,使用位竞争算法筛选位,将每次竞争失败的标签信息放入堆栈中,标签信息包括竞争失败的比特位位置和这一步中竞争失败的标签数,在堆栈中存储形式为(失败比特位置,失败标签个数)。当成功识别完一个标签后阅读器获取堆栈信息,如果是空就结束,如果非空就取出栈顶元素信息,此时如果只有一个标签则直接识别,如果多于一个则继续往下判断。如图4所示。

图4 堆栈后退算法Fig.4 Stack back-off algorithm

2.4 IBCA算法步骤

图5为IBCA算法流程图,图中主要符号意义如下:

REQ:请求命令。阅读器发送请求信号给标签,标签收到命令后与自身UID作比较,若小于等于这个值则发送UID给阅读器。

REQ(UID,0):锁定指令。阅读器发送锁定信号给标签,标签收到信号后将未碰撞比特位锁住,以后只发送发生碰撞的位。

P:进行运算的比特位。

MSB:碰撞位的最高位。

N:栈顶标签竞争失败比特位的下一位。

图5 IBCA算法流程Fig.5 IBCA algorithm flow chart

算法的主要步骤如下:

1)阅读器发送REQ(111···111)命令,所有ID码值小于或者等于(111···111)的电子标签将自己的UID发送给阅读器。

2)阅读器检测接收到的信号并进行译码,判断是否发生碰撞,如果有,转到步骤3),如果没有,直接识别该标签。

3)阅读器判断发生碰撞的具体位,生成新的请求信号REQ(UID,0)并发送给标签,其中置碰撞位“1”,未碰撞位“0”。标签收到信号后与自身UID比较,将未碰撞位锁住,进行步骤4)。

4)标签发送最高碰撞位比特给阅读器,阅读器进行“或”运算,①如果运算结果是0,表示此次参与位比特竞争的标签优先权都是相同的,故无法区分需进行下一个位比特竞争;②如果“或”运算结果为1,存在唯一一个比特位为1的标签,那么该标签将取得所有参与竞争标签的最高优先权,此次运算位值是0的标签放弃此轮竞争,阅读器将失败标签的信息放入堆栈中,然后转到步骤5;③如果“或”运算结果是1但是比特位为1的标签不止一个,那么比特位为1的标签将进入下一比特位的竞争,此次比特位为0的标签放弃此轮竞争,阅读器将失败标签信息放入堆栈中,然后转到步骤6)。

5)阅读器成功识别标签。

6)成功识别完一个标签后,阅读器检查堆栈里有没有竞争失败标签的信息。若为空代表所有标签已经全部识别完,如果堆栈中还有待识别标签,那么取出堆栈中优先权最高标签的信息,如果取出的标签。

2.5 算法举例说明

设有如下5个标签待识别:A1010010100,B 1010110110,C1010110100,D1010111110,E1001111110,识别过程如下:

1)阅读器发送REQ(1111111111)信号给标签, 5个标签收到后全部返回发送自己的UID。

2)阅读器检测到标签发生碰撞,译码生成新请求信号REQ(0011101010)给标签。

3)标签收到锁位信号,将未发生碰撞位锁住,将碰撞位重新排序发送。这时为A 10000,B 10101, C 10100,D 10111,E 01111。

4)阅读器将第5位做“或”运算,结果为1,E退出竞争,第5位为0的标签有1个,将(5,1)推入堆栈。然后第4位做“或”运算,结果是0,对A,B,C, D的第三位进行操作。这时A退出竞争,第3位为0的标签有1个,将(3,1)推入堆栈。对剩下的标签第2位做“或”运算,结果为1且为1的标签只有一个D,直接识别。有两个第2位为0的标签,将(2, 2)推入堆栈。

5)从栈顶取出(2,2)对下一位也就是第1位做“或”运算,结果为1且只有一个为1的标签B,直接识别,同时将标签C也识别。再取出栈顶的(3,1),识别出A,同理识别出E。

3 仿真结果

采用MATLAB仿真平台对BCA,IBCA及同样基于比特位的二叉树算法BTA(Bit Tree Algorithm)[6]进行仿真对比,标签数量从0变化到1 000,仿真结果如图6和图7所示。

图6 标签数量与碰撞时隙数关系Fig.6 Relationship between tag number and collision-slot number

图6可以看出IBCA算法比BTA,BCA算法所产生的碰撞时隙要少的多,改进的算法有明显的优势。

图7 标签数量与通信次数关系Fig.7 Relationship between tag the number and communication number

图7仿真了标签数量与阅读器询问次数的关系,从中可见IBCA算法较前两种询问次数也大量减少,从而减少了系统的通信量,提高了系统的效率。

4 结语

文中介绍了RFID系统中的碰撞问题和对应的防碰撞算法,重点分析了基于位竞争的算法原理,当阅读器识别大量标签时,其虽然在系统性能上有了

很大改进,但还是不够理想。本文提出的改进算法通过引入锁位机制和设置堆栈后退的方法,与位竞争算法相结合,使得系统所需的碰撞时隙数和询问次数进一步降低,有效地提高了阅读器的识别效率,增强了系统的性能。经过对改进后的算法进行仿真实验分析,结果表明算法可以工作并改善了系统性能,证明了可行性。

[1] 高飞,薛艳明,王爱华.RFID原理与应用[M].北京:人民邮电出版社,2010.

GAO Fei,XUE Yan-ming,WANG Ai-hua.RFID Principles and Applications[M].BeiJing:People Post Press, 2010.

[2] NEMAI Chandra Karmakar.Handbook of Smart Antennas for RFID Systems[M].New York:Wiley and Sons, 2010.

[3] 宋瑞玲,高仲合.基于分组动态帧时隙ALOHA防碰撞算法研究[J].通信技术,2013,46(07):37-39.

SONG Rui-ling,GAO Zhong-he.Tag Anti-collision Algorithm based on Dynamic Frame Slotted ALOHA[J]. Communications Technology,2013,46(07):37-39.

[4] 侯胜宇,冯锋.一种改进的二叉树型RFID防碰撞算法[J].计算机工程与应用,2013,49(04):129-233.

HOU Sheng-yu,FENG Feng.Improved binary tree anticollision algorithm in RFID system[J].Computer Engineering and Applications,2013,49(4):129-133.

[5] TZAY-FARN Shih,and WEN-LI Hsu.An efficient Anti -Collision Algorithm for RFID System[C]//Proceedings of the 8th WSEAS International Conference on Applied Computer and Applied Computational Science(ACACOS'09).Athens:WSEAS Press,2009:488-494.

[6] 单承赣,孙明.基于后退策略的位传输二进制搜索算法[J].合肥工业大学学报:自然科学版,2010, 33(01):68-72.

SHAN Cheng-gan,SUN Ming.An algorithm based on bit -by-bit binary-tree ofbacktracking[J].Journal of Hefei University of Technology(Natural Science),2010,33 (01):68-72.

CAI Bin-yuan(1990-),male,graduate student,mainly engaged in wireless communication technology.

宋依青(1960—),男,教授,主要研究方向为电子信息与通信系统;

SONG Yi-qing(1960-),male,professor,mainly engaged in electronic information and communication system.

王海龙(1971—),男,教授,主要研究方向为光通信技术;

WANG Hai-long(1971-),male,professor,mainly engaged in optical communication technology.

骆华(1989—),男,硕士,主要研究方向为电路与系统。

LUO Hua(1989-),male,M.Sci.,mainly engaged in circuits and systems.

An Improved Bit-Competition RFID Anti-Collision Algorithm

CAI Bin-yuan1,SONG Yi-qing2,WANG Hai-long1,LUO Hua1
(1.Qufu Normal University,Qufu Shandong 273165,China;2.Changzhou Institute of Technology,Changzhou Jiangsu 213003,China)

The improved bit-competition algorithm(IBCA)based on BCA algorithm is proposed to solve the problem of tag collision in RFID system.Firstly,bit-locking mechanism is introduced into the improved algorithm,thus the readers could extract collision bits among tags via bit-locking method.Then only the collision bits are communicated and OR operations done by bit.The improved algorithm makes the tag get back to the pervious collision bit via setting a stack after identifying a tag.This algorithm takes number of collision slot and times of the request into account.Simulation results indicate that this IBCA algorithm is highly improved in performance as compared with BCA algorithm.

bit competition;bit-locking;stack

TP301.6

1002-0802(2014)10-1227-05

10.3969/j.issn.1002-0802.2014.10.024