《基于时隙ALOHA 的RFID 防冲突算法及其系统实现方案的分析研究.docx》由会员分享，可在线阅读，更多相关《基于时隙ALOHA 的RFID 防冲突算法及其系统实现方案的分析研究.docx（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、基于时隙ALOHA的RFID防冲突算法及其系统实现方案的分析研究1引言无线射频识别(RFID，RadioFrequencyIdentification)技术是近年来应用发展迅速的一种利用射频通讯方式实现的无线非接触式身份识别技术。RFID技术应用系统1主要是由RFID标签、标签阅读器及相应的计算机系统组成的，当系统要阅读现场贴有RFID标签的对象时，系统由标签阅读器向RFID标签发送特定频率的电磁波，RFID标签经电磁波的触发将內部存储的身份识别码信息送出，这样系统通过标签阅读器识别货物并进行相应的信息处理。但是，如果有多个RFID标签接收到电磁波并同时发送信息，则标签阅读器接收到的信号就会互
2、相干扰，不可避免地出现标签阅读冲突问题1。目前解决RFID标签阅读冲突问题主要是基于两种防冲突算法即1、2：基于时隙ALOHA的防冲突算法和基于树结构的防冲突算法。其中，前者是采用随机选择发送时间的方式，系统识别的可靠性相对差一些，但易于设计兑现；后者则采用二叉树的搜索算法，系统识别的可靠性较高，但系统兑现时需要与RFID标签的识别码信息相联系，硬件设计较为复杂。因此，低成本的RFID标签一般是采用基于时隙ALOHA的防冲突算法来设计的，如何提高该算法系统识别的可靠性是目前低成本RFID标签应用系统研究重点。本文将首先介绍基于时隙ALOHA的RFID防冲突算法的基本实现原理，分析说明该算法的关
3、键模型参数，指出设计该算法系统兑现的关键在于现场RFID标签数预测和时隙帧长确定问题，然后具体介绍几种不同的标签预测实现方案，并进行系统识别的性能仿真与分析，最后总结出各种情况下相对比较可行的系统实现方案。2基于时隙ALOHA的RFID防冲突算法时隙ALOHA算法（FramedSlottedALOHA）简称FSA是一种随机时分多址方式3的用户信息通讯收发算法，它将信道用信息帧表示，把信息帧分成许多时隙(slot)，每个标签随机选一个时隙来发送自己的识别码信息。在整个信息帧的时间内每个RFID只响应一次，如图1所示。620)this.style.width=620;border=0图1中每个圆圈
4、代表一个RFID标签发出的识别码信息，这样阅读器在整个信息帧接收过程中遇到的标签回复有3种情况，即：成功、空闲、冲突，它们可能分别代表在某个时隙内是一个标签、没有标签或两个以上标签的应答。实际情况中，由于各标签距阅读器距离不同，近距离标签发送的信息可能覆盖了远距离标签发出的信息，即使是时隙冲突，阅读器也可能正确识别近距离标签的信息。同样，由于其他环境噪声的影响，即使在一个时隙内只有一个RFID标签应答，阅读器也可能无法阅读成功。在不考虑这两种不理想条件即捕获效应和环境噪声的影响4，若整个信息帧的时隙数设定为F，则阅读N个RFID标签时每个信息帧内成功、空闲和冲突的时隙数分别为：620)this
5、.style.width=620;border=0因此，RFID系统的阅读吞吐率也称识别效率即阅读器在一个信息帧长的时间内能成功识别标签数所占的比例可以表示为：620)this.style.width=620;border=0图2中给出利用Matlab仿真的RFID系统阅读100次积累的识别结果，其中系统仿真设定的信息帧长即时隙数设定按2的幂次方递增，即F取值从16到256变化，横坐标为标签数N从1到1000变化，纵坐标为阅读吞吐率。可以看出当标签个数接近信息帧长时，系统的吞吐率比较高，这与式（2）的结果是一致的，即最大阅读吞吐率可通过式（2）对F进行微分即（dS/dF）F=N=0得到。620
6、)this.style.width=620;border=03RFID标签数预测与信息帧设定实现方案在RFID系统应用时，系统阅读器读取的RFID标签数往往是未知的。根据上面RFID多标签阅读的防冲突算法分析结果上看，要实现具有解决RFID防冲突算法功能的系统方案，系统需要先进行现场的RFID标签数预测5。通常可以通过以下几种预测方法来实现：1）最小预测（lowbound）6、14：即系统阅读有冲突出现的话，至少有2个以上的标签存在，可以预测发生冲突的标签个数至少为2*ak。2）Schout预测4、6、12、13：若在每个信息帧中每个标签选择时隙符合=1的泊松分布，则信息帧中各冲突时隙平均响应
7、的标签个数约为2.39，这样可以预测未识别的标签数为2.39*ak。3)Vogt预测2、11：它是通过比较实际的成功、空闲、冲突时隙数与理论的成功、空闲、冲突时隙数得出误差最小的结果来预测未知标签数，即：620)this.style.width=620;border=0其中，c1、ck、c0为实际测得的成功、空闲、冲突时隙数值。在标签数N取值范围C1+2*CK，2*（C1+2*CK）内找到最小的值，所对应的N值就是预测的标签数。图3分别给出采用Lowbound、Schout、Vogt三种不同的标签数预测实现方案的系统仿真结果，它们均先预测确定现场可能的标签数后再来设定最佳信息帧长度，并重复阅读
8、100次。与FSA（即信息帧长度固定为256）相比，可以看出基于标签数预测的系统，系统阅读吞吐率有明显改善。620)this.style.width=620;border=0但是总的来说，对于现场有大数量标签（特别是标签数大于500）时，采用式（2）由预测标签数来设置最佳信息帧长度的实现方案显然是不合适的。因此，有人提出了采用分组应答响应的方法7来实现，即当标签数超过354个时，将标签进行分组，选择1组的先应答，识别完1组之后再识别2组，分组数和标签数目的关系如表一。620)this.style.width=620;border=0图4是对现场有大数量标签（大于500）时采用分组算法和Lowb
9、ound、Schout、Vogt的预测方案比较仿真结果。可以看出采用分组算法的系统吞吐率在标签数大于500的时候可以达到很高，而其它几种则降得很快。因此如果用在大规模的标签识别时使用分组算法可以有效的提高系统的识别效率。620)this.style.width=620;border=04自适应信息帧时隙设置从前面分析与仿真结果上看，要获得最高的吞吐率或最佳识别效率，先得预测获得可能的标签数，并设置最佳的信息帧长度5。但是，任何RFID系统在不同场合要识别的标签数的变化范围很大，要直接预测标签数并设置好最佳信息帧长度在实际电路实现系统设计是比较复杂，且带来额外功耗8。事实上，RFID系统中常用2
10、的n次幂作为信息帧长度，其中n取1到8（即最大的帧长为256，最小为2，但更多最小取16)，如Vogt预测11提出的帧长和标签数的关系如表二，当标签个数在19之间时，帧长采用16。620)this.style.width=620;border=0为了简化实际电路的兑现设计，通常采用基于标签数预测的幂指数信息帧长度设置方法，如在最新的EPCGen2标准15中采用了Q-Algorithm的自适应信息帧时隙设置方案，当一个帧中出现过多的冲突时隙时，阅读器提前结束该帧发送一个新的更大的帧；当一个帧中出现过多的空闲时隙时，此帧也不是最佳的帧，阅读器提前结束该帧发送一个新的小的帧。具体实现方案如图5所示：
11、620)this.style.width=620;border=0图5中参数Q、Qfp和c均为正整数，信息帧长度为F=2Q-1，Q是动态变化的，初值取round(Qfp)。一个时隙之后，若该时隙是冲突时隙，则将Qfp加上参数c；若是空闲时隙，则将Qfp减去参数c；若是成功时隙，则Qfp保持不变。阅读器根据新的Q=round(Qfp)来决定是继续发送下一个时隙还是重新开启一个新的帧。EPCGen2采用Q-Algorithm在标签数变化很大的范围内要实现高吞吐率主要取决于参数c的取值。c太大会造成帧长变化过于频繁，太小又不能迅速的实现最佳帧的选择。在EPC标准中c的取值并未规定，因此必须找到合适的
12、c取值。文献8中帧长小于64的全部取c最大值0.5，帧长64到512之间c值取线性减小变化，帧长大于1024的全部取c最小值0.1。该取值方法比较简单且符合实际，实现结果也较理想，如图6。图6中x轴是标签从1到1000变化，y轴左边图形显示识别一个标签所需的平均时隙数为3，右边图形显示在标签数大范围的变化内都保持较高的吞吐率。文献9中提出了另外一种方案，时隙冲突和空闲时所取的c值不等，但成一定比例，这种方案相对复杂。620)this.style.width=620;border=0采用EPCGen2标准中的算法优势一是系统的总体识别时间较少，系统吞吐率高；二是阅读器中初始帧长值（即Q值）的设置
13、不受限制，如图7。图7中横轴1和2分别代表标签数200个和400个，Q初值分别取1-8的变化，发现最终的识别时间几乎无差别，这主要就是算法自适应调整的优势。采用EPCGen2标准中的算法劣势是系统由于调整帧长过于频繁而造成功耗的增加10。620)this.style.width=620;border=05总结防冲突算法是射频识别系统实现标签快速识别的关键。本文通过对现有几种代表性的防冲突算法的比较研究，对防冲突算法有更加深刻的理解。Vogt提出的预测识别范围内所有标签的机制，预测准确度高；分组算法采用幂次变化帧长且系统的识别时间短，吞吐率高，非常适合实际的应用；EPCGen2标准提出的Q-Al
14、gorithm算法使系统能自适应的调整，识别效率高，在超高频射频识别系统中得到广泛的应用。参考文献1KlausFinkenzeller著.射频识别技术M.第三版.BeiJing:电子工业出版社,2006.2MaurizioA.Bonuccelli,FrancescaLonetti,FrancescaMartelli.InstantcollisionresolutionfortagidentificationinRFIDnetworksA.AdHocNetworks,Elsevier,Volume5,Issue8,November20073L.Burdet.RFIDmultipleaccessm
15、ethodsA.TechnicalReportETHZurich,2004.4FRITSC.SCHOUTE.DvnamicFrameLengthALOHAA.IEEETransactiononCommunications,19835Jae-RyongCha,Jae-HyunKim.NovelAnti-collisionAlgorithmsforFastObjectIdentificationinRFIDSystemA.inProc.InternationalConferenceonParallelandDistributedSystems,20056ChristianFloerkemeier.
16、TransmissioncontrolschemeforfastRFIDobjectidentificationA.IEEEPerComWorkshoponPervasiveWirelessNetworking,Italy,March20067Su-RyunLee,Sung-DonJoo,Chae-WooLee.AnEnhancedDynamicFramedSlottedALOHAAlgorithmforRFIDTagIdentificationA.ProceedingsoftheSecondAnnualInternationalConferenceonMobileandUbiquitousS
17、ystems:NetworkingandServices,SanDiego,CA,USA,July20058InwheeJoe,JunoLee.ANovelAnti-CollisionAlgorithmwithOptimalFrameSizeforRFIDSystemA.2007.SERA2007.5thACISInternationalConference,20079DonghwanLee,KyungkyuKim,WonjunLee.Q-Algorithm:AnEnhancedRFIDTagCollisionArbitrationAlgorithmJ.ComputerScience,2007
18、,Volume4611:23-3210JianweiWang,DongWang,YupingZhao.ANovelAnti-CollisionAlgorithmwithDynamicTagNumberEstimationforRFIDSystemsA.CommunicationTechnology,2006.ICCT06,Nov.200611HaraldVogt.EfficientObjectIdentificationwithPassiveRFIDTagsA.inProceedingsoftheIEEEInternationalConferenceonSystems,ManandCybern
19、etics(SMC02),Hammamet,Tunisia,October200212QiaolingTong,XuechengZou,DongshengLiu,etal.ModelingtheAnti-collisionProcessofRFIDSystembyMarkovChainA.WirelessCommunications,NetworkingandMobileComputing,2007.WiCom200713ChristianFloerkemeier,MatthiasWille.ComparisonofTransmissionSchemesforFramedALOHAbasedR
20、FIDA.ApplicationsandtheInternetWorkshops,2006.SAINTWorkshops200614Tae-WookHwang,Byong-GyoLee,YoungSooKim,etal.ImprovedAnti-collisionSchemeforHighSpeedIdentificationinRFIDSystemA.InnovativeComputing,InformationandControl,2006.ICICIC0615EPCTMRadio-FrequencyIdentityProtocolsClass-1Generation-2UHFRFIDProtocolforommunicationsat860MHz960MHzVersion1.1.0Draft1,EPCglobalInc,2005作者简介：吴伟贞（1983-），女，福建莆田人，硕士生，研究方向为无线射频识别；郭东辉（联系人），男，教授，博士生导师. 1