RFI D 技术中防碰撞算法研究与改进曹新宇 杨虹蓁 赵云峰(北华航天工业学院电子工程系,河北廊坊065000)摘　要:本文研究了射频识别技术中的防碰撞算法,介绍了几种标准搜索算法,提出了标签分区的改进算法,并且利用软件进行了仿真,仿真结果表明此改进算法能明显提高效率和稳定性。

关键词:射频识别;防碰撞算法;A LOH A中图分类号:T N911.23 文献标识码:A 文章编号:1673-7938(2010)01-0006-03收稿日期:2009-09-07作者简介:曹新宇(1977-),男,讲师,硕士,吉林省吉林市人,从事无线通信,微波技术研究。

0　引　言无线射频识别(RFI D ,Radio Frequency Identifica 2tion )技术是近年来应用发展迅速的一种利用射频通讯方式实现的无线非接触式身份识别技术。

在无线电技术中,多路存取的问题是众所周知的。

如果有多个RFI D 标签接收到电磁波并同时发送信息,则标签阅读器接收到的信号就会互相干扰,不可避免地出现标签阅读冲突问题。

识别过程中这种不可避免的多数据传输产生的冲突即碰撞问题严重影响了系统的性能。

因此,如何解决碰撞问题成为RFI D 系统的关键技术之一。

目前解决RFI D 标签阅读冲突问题主要是基于两种防冲突算法:基于时隙A LO 2H A 的防冲突算法和基于树结构的防冲突算法。

其中,前者是采用随机选择发送时间的方式,系统识别的可靠性相对差一些,但易于设计兑现。

后者则采用二叉树的搜索算法,系统识别的可靠性较高,但系统兑现时硬件设计较为复杂。

因此,低成本的RFI D 标签一般是采用基于时隙A LOH A 的防冲突算法来设计的,如何提高该算法系统识别的效率和吞吐量是应用系统研究重点。

1　算法原理1.1　帧时隙A LOH A 标签防碰撞算法帧时隙Aloha (Framed Slotted Aloha ,FS A )算法的基本思想是在时间域上进一步离散,将时间划分为不同的离散帧,每帧由若干可用时隙组成。

标签在每个帧内随机选择一个时隙发送数据。

读写器判断标签是否被识别,发生碰撞的标签进入下一识别周期,直到所有标签被识别。

这种算法适于传输信息量较大的场合,与时隙A LOH A 算法相同,该算法也需要一个同步开销。

FS A 算法存在一个缺点,当标签数量远大于时隙个数时,读取标签的时间将会大大增加,而在标签个数远小于时隙个数时,会造成时隙的浪费。

1.2　动态帧时隙A LOH A 算法动态帧时隙A LOH A (DFS A )算法是每帧时隙数都会根据标签数的不同而变化。

根据每帧中的空闲和碰撞情况动态调整帧长以提高识别效率。

读写器首先给标签提供较小的帧长,如果碰撞较多,就在下个识别周期增大帧长,直到至少识别一个标签为止。

为获得系统最大吞吐率,DFS A 算法需要在识别过程中估算标签数,用以确定匹配时隙数。

标签估算的方法有很多种,例如:1.2.1　估算出参与识别的标签总数设时隙数为L ,标签数为n ,则一个帧中碰撞时隙率C ratio =1-1-1Ln 1+n L -1。

在读写器识别过程中,已知当前帧时隙数为L ,并且可以统计出该帧时隙碰撞率C ratio ,采用逼近算法,可以估算出n 。

1.2.2　直接估算出未识别的标签数当系统达到最大吞吐率时,一个时隙的碰撞率C slot =0.4180,因此一个时隙碰撞的标签数C tags =1C slot=2.3922。

读写器在识别过程中,统计前一个帧的时隙碰撞数N coll ,则未识别标签数N est =2.3922×N coll 。

　第20卷第1期2010年2月 北华航天工业学院学报Journal of N orth China Institute of Aerospace Engineering V ol 120N o 11　Feb 12010在确定未识别标签估计数N est 后,从理论上讲最优的时隙数L 应该等于N est ,但在实际应用中,读写器能够设定的时隙数是定值,通常为1,8,16,32,64,128,256。

因此,读写器需要根据N est 从以上几个数中选择一个数作为下一帧的时隙数。

对250个以内不同数目的标签,选择不同时隙数,计算一个帧的吞吐率。

对不同标签数选择吞吐率最大所对应的时隙数如图1所示,这样就可以在估算出未识别标签数之后,在下一帧中选择匹配的时隙数,从而提高系统吞吐率。

图1　标签数目与最佳时隙数2　动态帧时隙Aloha 改进方法在基于Aloha 的算法中,影响系统性能最重要的参数是每一识别周期的帧长和响应标签数。

选择合适的帧长将大大改善算法的性能。

本改进算法首先动态选择帧长,通过分析得出,为达到最好的系统性能,只需在每个识别周期内取和标签数最接近的帧长大小即可。

n 个标签在帧长为N 时识别效率(即成功识别的标签数除以总的识别时隙数)为:P N=a N ,n1N=n1N1-1Nn -1由此可得图2不同帧长系统性能的变化曲线图,如图所示,确定相邻帧长性能曲线交点处的标签数,该标签数即为调整帧长或分组数的临界点,一旦待识别标签数达到该临界点时就调整相应帧长大小。

图中,两相邻帧性能曲线交点P N =P 2N 处的标签数为:n N ,2N=ln (2)ln2N -12N -2因此,当待识别标签数大于n N ,2N 时将帧长增加一倍,当标签数小于n 0.5N ,N 时帧长减半。

图2　识别效率性能比较图其次,当读写器鉴别出标签数远远大于每帧时隙数,而系统又无法通过增大时隙数来提高吞吐率时,可以采用标签分组的方式来处理。

在每帧时隙数为256,标签数多于354时,将全部标签分成两组或者更多组,读写器分别对每组标签进行识别,从而可以提高系统的吞吐率。

而此时各分组中标签的通信仍然是完全随机的。

那么在分组标签数目较多时,很可能出现帧的前部时隙过分拥塞,碰撞现象频繁。

于是,在动态选择帧长和分组的基础上再将时隙数动态分成若干小区,标签依据序列号分入各小区。

具体的说就是将标签芯片中增加一个运算器,用来将总时隙数与本序列号进行除法运算,所得结果再与分区数相乘取整,得出的数值作为该标签选择时隙的随机数基值,这样就实现了将时隙再动态分成若干小区的想法。

此方法将标签发送的随机时隙做了相应的调整,以此进一步减少碰撞的可能性。

当动态选择帧长为256时,进行选择分组,n 个标签在帧长为256时的分组为m 。

当帧长为N 时,小区选择时隙数为b ,分区k 为:k =N Πb ,识别效率为:P N =n256m1-k256n km-1其仿真图如图3,图4所示。

3　仿真分析采用matlab 仿真软件对算法进行函数建模与编程实现,最后对算法识别过程进行仿真。

仿真结果如图3、4所示。

从图3中可以看出随着标签数量的不断增多,改进算法的识别效率与基本算法相比效率有较大提高,而且改进算法可使系统更加稳定,在估计出待识别标签数目后只需将标签和时隙相应的第1期曹新宇等:RFI D 技术中防碰撞算法研究与改进2010年2月分组分区,即可进行信息的识别,省去了常用方案中反复查询数据的操作,计算复杂度和操作成本更小。

正如图4所示,在时隙数的分区中,对分区选择了不同的时隙数b ,并对它们的性能做了比较,发现效率随时隙的细化有所提高。

图3　算法性能比对图图4　不同分区长度性能比对图4　结　语本文对射频识别技术中的防碰撞算法进行了研究,在对帧时隙A LOH A 防碰撞算法的性能进行分析的基础上,提出了动态帧时隙的改进方法,并利用matlab 仿真软件对改进算法和基本算法的识别过程进行仿真与分析,结果表明改进后的算法进一步提高了算法的性能和标签识别效率。

参考文献:[1]LEE S 2R ,JOO S 2D Joo ,LEE C 2W.An enhanced dynamicframed slotted A LOH A alg orithm for RFI D tag identification [C].Proceedings of the The Second Annual International C on 2ference on M obile and Ubiquitous Systems Netw orking and Ser 2vices Washington ,DC :IEEE C om puter S ociety ,2005:166-174.[2]CH A J -R ,KI M J -H.N ovel anti -collision alg orithms forfast object identification in RFI D system [C ].Proceedings of the 11th International C on ference on Parallel and Distributed Systems W orkshops (ICPADS ’05).Washington ,DC :IEEE C om puter S ociety ,2005:63-67.[3]陈大才.Finkenzeller K.射频识别(RFI D )技术—无线电感应的应答器和非接触IC 卡的原理与应用[M].北京:电子工业出版社,2001:148-149.[4]慈新新,王苏滨,王硕.无线射频识别系统技术与应用[M].北京:人民邮电出版社,2007.[5]肖珊,郎为民,胡东华.(射频识别(RFI D )安全解决方案研究[J ].微计算机信息,2008,5-2:210-211.[6]沈宇超,沈树群,王海波.射频识别系统中的防碰撞算法设计[J ].电子科学学刊,1999,21(9):702-705.R esearch and Improvement of Anti 2Collision Algorithms of RFIDC AO X in 2yu Y ANG H ong 2zhen ZH AO Y un 2feng(E lectronics Engineering Department ,N orth China Institute of Aerospace Engineering ,Lang fang 065000,China )Abstract :This paper deals with the anti 2collision alg orithm of radio frequency identification technology.Firstly ,several standard search alg o 2rithms are introduced.Based on them ,the im provement alg orithm of smaller tag division is proposed.At the end of the paper ,the com puter simulation is given.The simulation results indicate this im proved alg orithm can im prove efficiency and stability.K ey w ords :RFI D ;anti 2collision ;A LOH A2010年2月北华航天工业学院学报 第20卷。