RFID系统中二叉树防碰撞算法性能的提升*

伍继雄,江 岸,黄生叶†,何怡刚

(1.中国电子科技集团公司第七研究所,广东广州 510310,2.湖南大学计算机与通信学院,湖南长沙 410082)

RFID系统中二叉树防碰撞算法性能的提升*

伍继雄1,江 岸2,黄生叶2†,何怡刚2

(1.中国电子科技集团公司第七研究所,广东广州 510310,2.湖南大学计算机与通信学院,湖南长沙 410082)

针对RFID系统中的标签碰撞问题,提出了一种改进的二叉搜索树防碰撞算法.通过划分标签子集、动态调整冲突检测过程,以减少标签冲突和系统开销,提高识别效率.仿真结果表明,相比于目前的二叉树搜索算法,本文方法在待识别标签数量较大的情况下提高了识别效率,减少了搜索次数及阅读器与标签之间的通信量.

防碰撞;RFID;子集划分;动态调整

在RFID技术的发展过程中,防碰撞技术是信号识别与处理的关键技术之一.当在读写器的作用区域中有多个标签同时发送信号而产生信道争用问题时,信号互相干扰,即发生了碰撞.因此,如何使用防碰撞技术识别多个目标以及如何在保证识别精度的同时提高效率具有重要意义.

当前广泛使用的防碰撞算法有两类:基于树分叉的算法和基于A loha的算法[1-2].A loha算法实现相对简单,效率也较低[3].树分叉算法采用了确定性搜索的防碰撞策略,其核心思想是读写器根据冲突的信号,按照二叉树深度优先搜索的思想,逐步缩小搜索范围,直到找到符合指定条件的标签.这类算法主要有跳跃式动态树形防碰撞算法(Jumping Dynam ic Search JDS)[4],查询树算法(Query T ree QT)[5]、ABS 算法(Adap tive Binary Sp litting)以及文献[6]中的改进动态二分搜索算法IDBS(imp roved dynamic binary search)等[1].树分叉算法有更好的识别精度和信道利用率.但目前的树分叉算法仍有较长的识别延时和较大的通信复杂度,需进一步改进.

本文提出的标签防碰撞算法在文献[6]中算法的基础上,通过划分标签子集、动态调整冲突检测过程,旨在大幅度地减少标签冲突和读写器与标签之间的通信量.并通过仿真检验算法的性能.

1 算法的几点约定

1)本算法基于树分叉搜索算法,要求阅读器能够准确地识别出数据碰撞位的位置,采用了曼彻斯特编码[7].该编码约定逻辑“1”对应信号含下降沿跳变,而逻辑“0”对应信号含上升沿跳变.若无状态跳变,视为错误被识别.当两个或多个标签同时返回的某一数位有不同的值,则接收到的上升沿和下降沿相互抵消,以致出现“没有变化”或变化被明显削弱的状态,阅读器由此可判断该位出现了碰撞.假设标签1和标签2的ID分别是01010011和00110011,利用曼彻斯特编码能按位识别出碰撞位的示意图如图1所示.由于标签1和2是同时传送其数据,利用曼彻斯特编码阅读器解码为0XX 1X0X1,于是阅读器检测出第1,2,4和6比特出现碰撞.

图1 用曼彻斯特编码的碰撞情况Fig.1 Co llision cases with M anchester codes

2)标签内部设置了一个计数器R用于存储标签ID中所有比特位的按位异或的结果,例如标签ID:01001001,则标签中计数器R的值为1,这个计数器的值可以在标签制造时由工厂固化写入.因为该计数器值可以是0或者1,分别代表标签ID中‘1'的个数是偶数和奇数的情况,所以增加该计数器R是为了将标签划分为更小的两个子集.

为了动态传输标签ID数据,标签中计数器flag是表示标签是否被屏蔽的标志位,为0表示没有被屏蔽,可以响应阅读器的命令,传送从计数器count指向的对应位开始的ID数据,该标志非零表示标签被屏蔽,不响应阅读器的命令.

3)为了便于描述算法,引入以下有关指令:

a)Request(m,n)请求命令:m为上一次搜索过程中标签第1次碰撞的位置,n为划分标签子集的标识位.标签收到这个请求命令后,只有其计数器R的值与子集标识位n相匹配的标签响应请求命令.若匹配,当m+1的值大于计数器count值时,令count=m+1.检查此m指定的自己ID对应的比特位,若为0,则从计数器count指向的比特位开始传送自己的ID数据,若为1,则将计数器flag值加一,即将标签屏蔽.阅读器第1次搜索时发送Request(L-1,n),L为标签ID的长度,要求区域内所有匹配子集标识位n的标签应答.

b)Select(ID)选择命令:把某个事先确定的ID作为参数发送给标签.具有指定ID的标签将以此作为执行后续命令(例如读写和写入数据)的切入开关,即选择这个标签.具有其它ID的标签将自己的计数器flag值减一.

c)Read-Data读出数据:选中的标签将存储的数据发送给阅读器.

d)Unselect去选择:取消一个事先选中的标签,标签进入“无声状态”.

2 算法要点和实现

2.1 算法要点

1)阅读器每次发送的Request指令指出了上1次搜索过程中标签第1次碰撞的位置,减少了指令长度.

2)由于一次搜索过程中所有响应的标签的计数器值R都相等,则说明每个标签ID的按位异或结果相等,等效于每个响应标签ID中‘1'的个数有相同的奇偶性.因此一次搜索过程中不可能出现只有一次冲突的情况.

3)一次搜索过程中只有两次比特位发生冲突时,可以直接识别出两个标签.例如对计数器值R为1的标签识别过程如下.

ID1:01001001 ID2:11000001

阅读器端接收到解码为:×100×001,发现有两个冲突位.对阅读器正确接收部分×100×001进行按位异或结果为0,表示正确接收部分ID中‘1'的个数为偶数,而这两个标签的计数器值R都为1,说明这两个标签ID中‘1'的个数为奇数,可以判断两个冲突标签在这两个冲突位中有且仅有一个比特位值为1,因此可以快速的识别出标签 01001001和11000001.

4)阅读器检测到有3次比特位发生冲突时,即停止接受标签传送的后续数据,进入下一次搜索过程,这样有效地减少了标签的识别延时和阅读器与标签之间的通信量.需要强调的是,目前的信号处理技术和半导体工艺水平已能为这种处理提供支持.例如,主流的数字信号处理器(DSP)的指令速度已达到400 MIPs以上,UHF频段的 RFID标准中规定的信息速率为640 kbps,在传送一bit信息的时间内,DSP可以执行约700条指令,因此一旦比特冲突(碰撞)发生,读写器内处理器在标签传输一个比特的时间后发起新一轮标签搜索过程是容易实现的.

2.2 算法实现:

本算法的实施依赖于阅读器与标签,因此下面分两部分描述算法的详细流程.阅读器中初始状态栈stack和string均为空,标签的ID为L位,每个标签的计数器flag和count均为0.算法中符号ID (i,j)表示标签传送从第i～第j比特的ID数据位.‘+'表示连接操作,例如‘0010'+‘1000'=‘00101000'.表达式XOR(ID识别)表示对已经识别的部分ID进行按位异或.标签的算法描述如下:

假设ID代码为8位,阅读器作用范围内有5个标签,它们在文中的代号及ID码见表1,阅读器如何利用该算法来识别它们,如表2所示.由于简化了阅读器命令,当阅读器检测到3次比特位发生冲突时即停止接受标签传送的数据,因为此后标签发送的比特数据是没有意义的,这样可节省数据传输时间.除此之外,该算法根据计数器R将标签分成两个子集分类进行识别,若一次搜索完毕只检测出二次比特位发生冲突可以直接识别两个标签,提高了标签识别的效率.从表2可知,识别5个标签只用了4次搜索过程,标签与阅读器的直接通信量为41.

表1 几个8位ID码标签举例Tab.1 An examp le of several tagswith 8-bit identifying codes

表2 标签识读过程例Tab.2 An examp le of identifying tags

3 算法的分析与比较

采用本算法,识别完阅读器作用范围内的 N个标签所需的搜索次数记为S(N),N个标签中有N 1个标签的计数器R值为1,N2个标签的计数器R值为0,参照跳跃式动态树形防碰撞算法的有关方法进行对比分析[4],可推出本文算法的时间复杂度为:

本算法相对于已有的二叉树搜索算法有如下一些优势:

1)由于将标签划分为两个子集分类识别,减小了冲突的概率.当标签ID号相对集中时,探测到只有两次比特位发生冲突的机率比较大,能减少搜索的次数.

2)简化了阅读器发送的指令,同时当检测到有3次比特位发生冲突时即停止接受标签传送的数据,立刻对标签作出冲突处理,有效地减少了标签的识别延时和阅读器与标签之间的通信量.

3)阅读器利用栈stack和字符串string来保存已经被阅读器接收到的标签ID数据,因此每次搜索中标签只需传送部分数据,在文献[6]IDBS算法的基础上减少了传输时间.

阅读器的搜索次数和阅读器与标签之间的通信量直接影响到标签的识别速度.若阅读器需要M次搜索才能识别N个标签,每次搜索时间t是由阅读器命令传输时间treader,标签ID数据传输时间ttag,标签对阅读器命令的响应时间DE tag,阅读器的冲突检测时间 DE reader组成.阅读器的数据发送速率为DR reader,标签的数据发送速率为DR tag.RL i为第i次搜索中阅读器的指令长度,TLi为第i次搜索中标签发送的数据比特长度,ti为第 i次搜索时间, t delay为一次搜索中的响应延迟.识别N个标签需要的总时间为:

从式(5)可知阅读器识别完N个标签的时间T主要由通信量NUM,和搜索次数M决定.

由于本文算法是基于标签ID码的奇偶性进行预分集的动态二分搜索算法,因此简记为PDBS(parity -based dynamic binary search).设标签ID长度是64位,

标签ID随机分配,DR reader和DR tag均为40 kbps,t delay为20μs,一个空闲时隙为40μs,通过编程并运行本算法与文献[6]的IDBS算法、跳跃式动态树形防碰撞算法JDS、查询树算法QT、ABS算法进行仿真.搜索次数的比较见表3.

表3 各算法搜索次数比较Tab.3 Comparison of the searching times of different algorithms

可以看出,随着标签的增多,本文算法中阅读器搜索次数相对于其它算法最少,这是因为多标签时,发生两次比特位冲突的概率增大,导致本算法优势更明显.本算法采取了简化阅读器指令、动态传输ID数据策略,使得阅读器与标签之间的通信量明显少于JDS和QT算法.

表4为各算法识别同样数量标签条件下不同算法读写器所发出的信息量的比较.由于本算法减少了阅读器的搜索次数并通过硬件配合减少了阅读器与标签之间一些不必要的通信量,根据式(5)可知标签的识别延时也将随之减少,这与我们的仿真结果一致.识别延时的比较如表5所示.在待识别标签数较大时,本算法识别标签的耗时小于所有其它算法,有更高的识别速率.表3～5所列的每项数据,都是10次运行结果的平均,每次所用标签的ID编号是随机产生的.

表4 各算法读写器发送信息量比较Tab.4 Comparison of the traffic transferred by the reader of different algorithms bit

表5 各算法耗时比较Tab.5 Execution time comparison of different algorithms ms

4 结 语

标签防碰撞算法对RFID系统识别效率至关重要,本文提出的防碰撞算法相对于目前的二叉树搜索算法,能够在保证识别精度的前提下,明显提高RFID系统的识别速率.所提出的算法涉及了对读写器的指令进行改进,并需要硬件系统的支持.设计并实现支持本算法的读写器以将本文算法付诸实践是作者下一步要开展的主要工作之一.

[1] M YUNG J,LEEW,SRIVASTA VA J,eta l.Tag-splitting:adaptive collision arbitration p rotocols for RFID tag identification[J].IEEE Transactions on Parallel and Distribu ted System s,2007,18(6):763-775.

[2] VOGT H.E fficient ob ject identification with passive RFID tags[C]//Proceedings of International Conference on Pervasive Com puting.Berlin:Springer,2002.98-113.

[3] A IBERTO LG,INDRA W.Comm unication netw ork s fundamental concep ts and key architectures[M].New York:M c-Graw-H ill,1999:354-365.

[4] 余松森,詹宜巨,王志平,等.跳跃式动态树形反碰撞算法及其分析[J].计算机工程,2005,31(9):19-26.

YU Song-sen,ZHAN Yi-ju,WANG Zhi-ping,et a l.A nti-collision algorithm based on jumping and dynamic searching and its analy sis[J].Compu ter Engineering,2005,31(9):19-26.(In Chinese)

[5] LAW C,LEE K,SIU K Y.Efficient mem ory less protocol for tag Identification[C]//Proceedings of the 4th International W orkshop on Discrete A lgorithm s and Methods for Mobile Compu ting and Comm unications.Boston:ACM,2000:75-84.

[6] 江岸,伍继雄,黄生叶,等.一种改进的RFID二进制搜索防碰撞算法[J].计算机工程与应用,2009,35(5):229-235.

JIANG Aan,WU Ji-xiong,HUANG Sheng-yie,et al.Improved RFID binary search anti-collision algorithm[J].Computer Engineering,2009,35(5):229-235.(In Chinese)

[7] FINKENZELLERK.RFID handbook:radio-frequency identification fundamen tals and applications[M].John Wiley and Sons,2003:187-193.

[8] The International Standard Organization.ISO/IEC FDIS 18000-6-2003 Information technology automatic identification and data capture techniques-radio frequency identification for item management air interface-part 6[S].Parameters for Air Interface Communications at 860-960MHz,USA:ISOPress,2003.

Imp rovement of the Binary-searching-based Anti-collision A lgorithm of RFID System s

WU Ji-xiong1,JIANG An2,HUANG Sheng-ye2†,HE Yi-gang2

(1.NO.7th Research Institute,China Electronics Techno logy G roup Corporation,Guangzhou,Guangdong 510310,China; 2.College of Computer and Communication,Hunan Univ,Changsha,H unan 410082,China)

To address the tag collision problem in Radio Frequency Identification(RFID)system,an improved binary-tree anti-collision algorithm was p roposed.By dividing the tags into different subsets and ad justing dynamically the process of collision detection,the collision probabilities and power consum ption were reduced.The simulation resultshave show n that,com pared w ith other binary-tree anti-collision algorithm s,the p roposed algorithm enhances the identifying efficiency,and both the num ber of searching times and the bits transferred between the reader and the tags are relatively low when the number of tags is large.

collision avoidance;radio frequency identification;subset-division;dynamic ad justm ent

TN914.3

A

1674-2974(2010)12-0082-05 *

2009-11-16

国家863计划先进制造技术领域重大资助项目(2006AA 04A 104)

伍继雄(1970-),男,广东台山人,湖南大学博士,中国电子科技集团公司高级工程师

†通讯联系人,E-mail:sheryl_huang@163.com