可并行识别的超高频RFID系统防碰撞性能研究.doc

第6期王必胜等：可并行识别的超高频RFID系统防碰撞性能研究113可并行识别的超高频RFID系统防碰撞性能研究王必胜1,2，张其善1(1. 北京航空航天大学 电子信息工程学院，北京 100083；2. 山东科技大学 信电学院，山东 青岛 266510 )摘 要：对超高频射频识别（RFID）系统的防碰撞问题进行了分析。提出了基于动态帧时隙ALOHA（DFSA）协议与正交可变扩频因子码（OVSF）作为扩频码的码分多址技术相结合的超高频RFID系统，实现了在单一时隙内最多可并行识别m个RFID应答器，m为OVSF扩频码长度。对提出的RFID系统期望的系统吞吐量进行了理论分析，仿真结果表明其防碰撞性能显著超过了现有的基于动态帧时隙ALOHA（DFSA）协议的超高频RFID系统的防碰撞性能。关键词：射频识别；可并行识别；OVSF码；动态帧时隙ALOHA（DFSA）中图分类号：TN929.532 文献标识码：B 文章编号：1000-436X(2009)06-0108-06Study of anti-collision performance in parallelizable identification UHF RFID systemWANG Bi-sheng1,2 , ZHANG Qi-shan1(1. College of Electronic and Information Engineering, Beijing University of Aeronautics and Astronautics, Beijing 100083, China; 2. College of Information and Electrical Engineering, Shandong University of Science and Technology, Qingdao 266510,China)Abstract: The anti-collision problem of ultra high frequency (UHF) RFID system was analyzed. A novel UHF RFID system, which based on combination of dynamic framed-slotted ALOHA and CDMA technology with orthogonal variable spread factor (OVSF) code, was presented. The RFID system had an ability to identify at most m tags simultaneously in one time slot, where m was the length of OVSF spread code. The expected system throughput of the presented RFID system was theoretically analyzed. The simulation results show that the anti-collision performance of the presented RFID system outperforms significantly that of current dynamic-framed-slotted-ALOHA (DFSA) UHF RFID system.Key words: radio frequency identification; parallelizable identification; OVSF code; DFSA1 引言在当前普适计算中，射频识别（RFID）技术是一种重要的无线自动识别技术。RFID系统具有快速、安全及高效等优点，越来越对工厂自动化产品线、仓储管理、超市及供应链管理等应用领域产生很大的影响。RFID系统可在较恶劣的环境下工作，并以很高的精确度1识别被标识物件。收稿日期：2007-12-04；修回日期：2009-04-10基金项目：广东省重大科技专项计划项目（2008A090300001）Foundation Item: The Key Item in the GuangDong Province Science & Technology Special Program(2008A090300001)一般情况下，RFID系统包含阅读器和应答器。阅读器通过发送射频波查询其识读范围内的应答器，所有应答器收集信号功率并回送各自的标识（ID）信息给阅读器。当同时有2个或多个应答器在同一时隙内回送ID信息时，会发生“应答器碰撞”问题，此时阅读器不能识别其中任何一个应答器的信息。阅读器使用防碰撞算法14来解决“应答器碰撞”。现有2种防碰撞方法：帧时隙ALOHA (FSA)协议5,6及二进制搜索算法79。在FSA及其各变种协议中，如动态帧时隙ALOHA (DFSA)10,11，阅读器发送包含帧长参数的“查询”命令启动识别应答器，应答器从帧长为n个时隙中随机选择一个时隙，如果选择的时隙符合协议的发送要求，应答器就在该时隙内回送自己的ID信息给阅读器，阅读器完成识别或解决碰撞。在二进制搜索算法中，每一次发生碰撞的所有应答器不断地被细分为2组，直到每一组中只包含一个应答器为止。无论是FSA协议还是二进制搜索算法，阅读器在一个时隙内只能成功识别一个应答器，这样RFID系统期望的系统吞吐量（平均每个时隙成功识别应答器的数量）非常低。对DFSA协议而言，最大期望的系统吞吐量约为0.42611，对二进制搜索算法约为0.4307。对于超高频RFID系统而言，具有快速且高效的防碰撞识别技术是非常必要的，特别是需要在短时间内识别大量的应答器情况下尤其重要。本文提出了一种新的超高频（UHF）RFID系统（以下简称DFSA-OC），将动态帧时隙ALOHA协议与使用正交可变扩频因子码（OVSF）作为扩频码的码分多址技术相结合，可在同一个时隙内最多可并行识别m个应答器，m为OVSF扩频码长度。提出的DFSA-OC系统期望的系统吞吐量显著高于现有基于DFSA协议（包括FSA协议）或二进制搜索算法UHF RFID系统的吞吐量。2 DFSA-OC RFID系统现有UHF RFID系统在阅读器识别应答器过程中，所有应答器在与阅读器通讯时共享一个无线射频信道。这样当有2个或以上应答器在一个时隙内同时响应时，所有应答器信号因碰撞叠加在一起，阅读器没有办法分离出任一应答器信号。在DFSA协议中，阅读器发送“查询”命令启动一轮应答器识别过程，其中“查询”命令中包含帧长参数k。每个应答器接收到阅读器“查询”命令后，提取参数k作为当前ALOHA帧长，并随机生成一个0，k1内的时隙号。其中生成的时隙号为0的应答器立即发送包含自身ID信息的信号给阅读器。若在一个时隙内没有发生“应答器碰撞”，如图1识别状态中浅灰色所示，阅读器可以识别这个应答器。若在一个时隙内发生了“应答器碰撞”，如识别状态中黑色表示，阅读器不能识别该时隙内的任一个应答器并且忽略该时隙内所有发生碰撞的应答器。阅读器继续下一时隙的识别过程，直到完成当前ALOHA帧中所有时隙的识别。所有剩余的应答器阅读器启动下一帧完成识别，这一过程不断重复直到所有应答器全部识别完结束。在DFSA协议的ALOHA帧中，识别过程使用了TDMA方式，应答器只能通过不同的时隙号才能被识别出来。如果ALOHA帧长远远小于阅读器识读范围内的应答器数量，将会有更多的应答器产生出相同的时隙号，这样形成更多的应答器发生碰撞，从而导致较低的期望的系统吞吐量。对于利用二进制搜索算法实现防碰撞识别的RFID系统，其识别过程也是属于TDMA方式，需要不断地分解碰撞的应答器以便在一个时隙内只有一个应答器参与识别，识别时间较长，影响了系统的吞吐量。图1 帧时隙ALOHA射频识别工作原理2.1 DFSA-OC RFID系统防碰撞工作原理CDMA技术广泛使用在各种无线通信应用中，可供多个用户在同一时间段内同时存取信息。为了降低RFID系统在同一时隙内“应答器碰撞”的概率，提高期望的系统吞吐量和识别效率，本文提出以OVSF码12作为扩频码，将CDMA技术嵌入到DFSA控制协议中以解决UHF RFID系统的防碰撞问题。提出的DFSA-OC超高频RFID系统的防碰撞工作原理如图2所示。在DFSA-OC超高频RFID系统中，阅读器首先发送“查询”命令启动应答器识别过程。该命令中包含帧长参数k和OVSF扩频码长度参数m（如图2，第一帧中k=8及m=4）。应答器接收到阅读器“查询”命令后提取参数k和m。参数k作为ALOHA协议的当前帧长，参数m作为OVSF扩频码的码长。在应答过程中，每一个应答器先生成2个随机整数。一个是时隙号，其值在0，k1中，用于在当前ALOHA帧中随机选择一个响应时隙。例如图2 图2 DFSA-OC超高频RFID系统的防碰撞工作原理及其实例第1帧中，应答器1的时隙号值为0，应答器2、3、4的值为1以及应答器5、6的值为6。另一个是码索引号，其值在0，m1中，用于随机生成一个OVSF扩频码。对长度为m的OVSF扩频码而言，其OVSF扩频码的总数量也为m，并且每一个OVSF扩频码都有唯一索引值，范围在0，m1中。例如图2第1帧中，应答器1生成的码索引号对应的OVSF扩频码为 1 1 1 1，应答器2、3、4、5对应的扩频码为1 1 1 1以及应答器6对应的扩频码为 1 1 1 1。每一个应答器使用各自生成的OVSF扩频码对包含ID信息的数据信号进行扩频调制然后应答阅读器。阅读器与应答器的通信过程处在DFSA协议控制之下。接收到应答器的回送信号以后，阅读器首先生成m个OVSF扩频码（码长为m），并使用这些扩频码对接收到的扩频信号进行解扩。利用OVSF码分多址技术，阅读器可以在一个时隙内最多识别m个应答器。识别过程中出现4种情况。1) 一个时隙内只有一个应答器响应。如图2第1帧，在第0个时隙只有应答器1响应阅读器，其OVSF扩频码为1 1 1 1，阅读器可以成功识别应答器1。2) 一个时隙内有2个或以上（m）应答器同时响应，但每一个应答器都有一个不同的OVSF扩频码。如图2第1帧中应答器5和6均在第6个时隙内同时响应，但是应答器5的扩频码为1 1 1 1，应答器6的扩频码为 1 1 1 1，利用码分多址技术，阅读器可以识别该时隙内的所有应答器。3) 一个时隙内有2个或以上（m）应答器同时响应，所有应答器都有一个相同的OVSF扩频码。如图2第1帧中应答器2，3，4均在第1个时隙内响应，并且都具有相同的扩频码1 1 1 1。这种情况称之为“码碰撞”。阅读器不能识别该时隙内的所有应答器，只能在下一帧中查询这些应答器。4) 一个时隙内有3个或以上应答器响应，其中有2个或以上应答器具有一个相同的OVSF扩频码，也就是说发生了“码碰撞”，如图2第2帧中的应答器3、4，此时阅读器不能在第2帧中识别出应答器3、4；另外有一个或以上应答器生成不相同的OVSF扩频码，如图2第2帧中的应答器2。在这种情况下，虽然应答器2与应答器3、4有相同的时隙号，但是应答器2中的扩频码1 1 1 1与应答器3、4中的扩频码1 1 1 1不相同。按照码分多址技术，阅读器可以识别出该时隙内的应答器2。由上述分析可知，在DFSA-OC RFID系统中，在同一时隙内只有发生了“码碰撞”的应答器才不能被识别，而其它没有发生“码碰撞”的应答器仍然可以被识别出来。而在DFSA协议或二进制树搜索算法RFID系统中，同一个时隙内只要有两个或以上应答器就会发生“应答器碰撞”，阅读器将不能识别该时隙内任一个应答器。因此本文提出的RFID系统其吞吐量要高于基于现有协议的RFID系统的吞吐量。在DFSA-OC RFID系统中，若一个时隙内没有发生“码碰撞”，阅读器最多可以识别出m个应答器。2.2 OVSF扩频码生成在DFSA-OC RFID系统中，应答器使用OVSF扩频码对包含ID信息的数据信号进行扩频调制，阅读器使用所有的m个OVSF扩频码对接收到的扩频信号进行解扩运算。在应答器中，可根据OVSF码快速生成算法12设计一个OVSF硬件生成模块。应答器将接收到的码长参数m及随机生成的码索引号输入到OVSF生成模块即可得到一个所需要的OVSF扩频码。由于OVSF生成模块一次只能得到一个OVSF扩频码，阅读器在解扩时需要所有码长为m的扩频码。考虑到阅读器硬件资源丰富，可将所有需要的OVSF扩频码预先存储在OVSF码表中，在解扩时，阅读器根据码长参数m通过查找OVSF码表来获取所有码长为m的OVSF扩频码。在DFSA-OC系统中，当应答器数量及帧长一定的情况下，随着码长m值增大，应答器在一个时隙内发生“码碰撞”的概率随之减小，系统期望的吞吐量随之增大，防碰撞性能提高。另一方面码长m值增大意味着DFSA-OC系统占用的频率资源在增加，另外系统的硬件复杂度有所增加。根据本文后面的仿真结果，码长m的最大值取27能够满足实际应用的需要。超高频RFID系统实际应用情形各不相同，应答器数量从较少到非常多都可能出现。为了灵活适应各种情况，DFSA-OC系统在识别过程中帧长参数k及OVSF码长参数m都是动态可变的，这在识别协议中很容易实现，不需要太多的硬件资源。在应答器数量非常多时，可以使用较大的码长m，以提高系统的吞吐量，加快应答器的识别速度，降低总的识别时间。在应答器数量较少时，可使用较小的码长m，在满足系统对期望吞吐量要求下可减小系统对频率资源的占用。3 防碰撞性能分析在UHF RFID系统中，期望的系统吞吐量表示为平均每个时隙内成功识别的应答器数量，是反映RFID系统对应答器防碰撞识别性能的一个最为重要的指标。在基于DFSA 协议的RFID系统中，对于有N个应答器及帧长为L时，其期望的系统吞吐量E(SDFSA)如式(1)所示。(1)而DFSA-OC系统期望的系统吞吐量E(SDSFA-OC)的计算要比较复杂一些。首先，可计算出一个时隙内有k个应答器且OVSF码长为m时对应的期望的吞吐量Eslot(SDSFA-OC)为(2)其次，按照DFSA协议，对于有N个应答器及L个时隙时在一个时隙内出现k个应答器的概率为 (k=1,2,N)(3)现在，对于给定OVSF码长m，则DFSA-OC系统的期望的系统吞吐量E(SDSFA-OC)可由式(4)计算：(4)式(4)也可修改成式(5)： (5)式(5)由2部分组成：第一部分等同于式(1)，第二部分是一个不小于0的数，记为Ed(SDSFA-OC)。随着码长m增大，Ed(SDSFA-OC)值也增大，期望的系统吞吐量E(SDSFA-OC)也越大，DFSA-OC系统的防碰撞性能就越好。为了更详细地分析DFSA-OC系统的防碰撞性能，按照式(4)或式(5)分别在不同的时隙数及OVSF扩频码长条件下计算出DFSA-OC系统的最大期望的系统吞吐量，并与基于DFSA协议的系统作了比较，结果如图3所示。在数值计算中，对于DFSA-OC系统，时隙L依次取2q, (q=2,3, 10)中的值，OVSF扩频码长m依次取2p, (p=0,1,7)中的值，应答器数N从1到1024变化。图3中反映了时隙L和码长m对最大期望系统吞吐量Emax(SDSFA-OC)的影响。同样，对于基于DFSA协议的RFID系统，令时隙L也依次取2q, (q=2,3, 10)中的值，应答器数N从1到1024变化，按照式(1)，得到了对应的期望的系统吞吐量的最大值Emax(SDFSA),如图3中最下方箭头所指示。图3 最大期望吞吐量与OVSF扩频码长m及时隙数L的关系（1应答器数N1024）图3中Emax(SDSFA-OC)值随码长m增大而增大，其值要大于Emax(SDFSA)。例如在L=4的情况下，当m=128时Emax(SDSFA-OC)达到47.1346而Emax(SDFSA)却只有0.421 9；在L=1024的情况下，当m=128时Emax(SDSFA-OC)为0.992 2，而Emax(SDFSA)却只有0.368 1。上述最大期望吞吐量是在应答器数限制在1到1024范围内得到的。由DFSA协议可知，只有当帧长与应答器数相接近时系统具有最大的吞吐量，此时防碰撞性能最佳，而当帧长与应答器相差较大时系统的吞吐量将减小，随之防碰撞性能也降低。同样的，当m=128时，L=1024时的最大吞吐量相比L=4时的要小很多。这是因为应答器数在1到1024范围内，帧长越长，平均分配在每个时隙内的应答器数就越少，扩频码长优势没有显现出来，系统的防碰撞性能优势没有发挥出来。所以实际工作中应根据具体的应答器数量，动态地调整帧长及码长大小，使系统能工作在具有最佳期望的吞吐量状态。由理论分析知，DFSA-OC RFID系统随码长m值增大其期望的系统吞吐量也随之增大，防碰撞性能显著超过了基于DFSA协议的RFID系统的性能。4 仿真结果利用仿真软件，分别建立了DFSA-OC UHF RFID系统及基于DFSA协议的UHF RFID的防碰撞仿真模型。每个模型中都包括一个阅读器和多个应答器，应答器数量在1到1000个内间隔50改变。仿真时ALOHA帧长限定在2q, (q=2,3, 10)，初始帧长为32，以后每一帧的帧长按照相应的应答器估计算法的结果来确定。在基于DFSA协议的仿真模型中，采用Schoute算法11即B=2.39C来估计剩余应答器数，其中C为当前帧中发生碰撞的时隙数。在DFSA-OC系统的仿真模型中，无法直接利用Schoute算法来估计剩余应答器数，但是可借鉴Schoute算法原理，先估计每一个时隙内发生碰撞的应答器数Bslot=2.39Nc，Nc为当前时隙内发生了“码碰撞”的OVSF扩频码的个数，然后再将当前ALOHA帧中所有时隙估计的Bslot相加，得到当前帧中未识别的剩余应答器数B。仿真时OVSF扩频码长m依次取2p, (p=0,1,7)中的值。仿真结果的输出用识别总时隙数表示，用以反映完成所有应答器识别时的识别总时间的大小。系统的识别总时间越小表示系统吞吐量越大，防碰撞性能越高，反之则系统吞吐量越小，防碰撞性能越低。仿真结果如图4所示。图4中当m=1时，OVSF扩频因子为1，也即没有发生实质性的扩频，DFSA-OC系统退变为DFSA系统，此时DFSA-OC系统的防碰撞性能与基于DFSA协议的系统性能一样，图中2曲线相重合。随着m的值从2增大到128，DFSA-OC系统扩频因子越来越大，在相同的应答器数量下需要的识别总时隙数越来越小。例如应答器数量为1 000时，OVSF码长m=1时需要的识别总时隙数为3 140，码长m=2时需要的识别总时隙数为1 627，减少了1 513个时隙，与m=1相比总的识别时间减少了48.18%。码长m=128时需要的识别总时隙数为290，减少了 2 850个时隙，与m=1相比总的识别时间减少了90.76%，识别效率显著提高。系统的仿真结果与理论分析的相一致。图4 OVSF扩频码长对识别总时隙数的影响5 结束语利用OVSF扩频码，将CDMA技术与DFSA协议相结合，对于提高超高频RFID系统的防碰撞性能是一种简便而又高效的识别方案。在DFSA-OC UHF RFID系统中，“码碰撞”代替了传统的“应答器碰撞”，降低了“应答器碰撞”的概率，提高了系统吞吐量。在应答器中嵌入OVSF硬件生成模块，对应答器的硬件成本及功耗有所增加。但随着IC技术及工艺的快速发展，应答器总体成本不断下降，功耗也逐渐降低。另外考虑到基于DFSA协议的EPC C1G2 RFID系统现处于强势地位，可对DFSA-OC系统适当改进实现与DFSA RFID系统的相互兼容识别。由前述分析知当m=1时，DFSA-OC系统退变为DFSA系统。因此当DFSA系统的阅读器发出“查询”识别命令时，DFSA-OC系统的应答器将其默认为是DFSA-OC系统的阅读器发出的m=1时的“查询”识别命令，从而可实现DFSA系统的阅读器对DFSA-OC系统的应答器的兼容识别。由于DFSA-OC系统的阅读器硬件资源丰富，可容易实现对基于DFSA协议的应答器的兼容识别，这样有利于DFSA-OC系统的推广。理论分析及仿真验证结果表明，本文提出的DFSA-OC UHF RFID系统具有实现简单，有很高的期望的系统吞吐量和防碰撞识别性能，可广泛用于各种各样的应用场景中，也为我国制定自己的超高频RFID系统标准提供了一定的理论参考依据。参考文献：1VOGT H. Efficient object identification with passive RFID tagsA. First International Conference PERVASIVE 2002C. 2000,981132WIESELTHIER J E, EPHREMIDES A, MICHAELS L A. An exact analysis and performance evaluation of framed ALOHA with captureJ. IEEE Transactions on Communications, 1989,37:125-137.3ISO/IEC FDIS 18000-6:2003(E), Information Technology Automatic Identification and Data Capture Techniques-Radio Frequency Identification for Item management Air Interface-Part 6: Parameters for Air Interface Commnications at 860-960 MHzS.4EPCGLOBAL, EPC Radio-Frequency Identity Protocols Class-1 Generation-2 UHF RFID Protocol for Communications at 860 MHz- 960 MHz Version 1.0.9S.5ABRAMSON N. The ALOHA system-another alternative for computer communicationsA. 1970 Fall Joint Computer ConfC. 1970.281-285.6FLOERKEMEIER C, WILLE M. Comparison of transmission schemes for framed ALOHA based RFID protocolsA. Proceedings of International Symposium on Applications and the Internet WorkshopsC.