射频识别防碰撞Q算法的分析及改进

韩振伟， 宋克非

(中国科学院长春光学精密机械与物理研究所，吉林长春130033)

0 引 言

射频识别(RFID)系统中，当读写器的天线辐射区域中有多个标签同时存在时，多个标签将几乎同时响应读写器的指令，读写器不能正确接收标签返回信号，这样就产生了碰撞问题。RFID系统若能够准确识别多个标签，必需采取相应的防碰撞技术[1]。由于RFID系统的特殊性，标签无源并且不具有载波监听能力，防碰撞技术主要考虑如何提高系统效率和降低系统功耗。防碰撞技术设计的优劣很大程度上决定了RFID系统性能的优劣。高识别效率的RFID系统可以适应标签数量巨大的场合；低功耗的RFID标签不仅可以扩展标签的使用距离，还可以延长标签的使用寿命，进而降低整个RFID系统的成本。

由于时分多址方式(TDMA)应用简单，并且容易实现大量标签的读写，目前一般的防碰撞技术主要以TDMA方式实现。常用的方法有ALOHA法、时隙ALOHA法、帧时隙ALOHA(FSA)法和动态帧时隙ALOHA(DFSA)法。EPCglobal Class-1 Gen-2(以下简称EPC Gen2)标准采用的防碰撞Q算法是基于动态帧时隙ALOHA(DFSA)法。

1 EPC Gen2标准的防碰撞技术分析

EPC Gen2标准[2]中读写器采用3个基本操作命令来管理标签。选择操作用于读写器选择特定的标签群，以便于盘存操作和访问操作。盘存操作用于读写器识别标签。读写器发送Query命令，开始一个盘存周期，一个或一个以上的标签可以响应。读写器检测某个标签响应，请求该标签发出PC、EPC和CRC-16。访问操作用于读写器对每个标签读取或写入。

如果读写器的天线辐射区域中有多个标签，当读写器发起盘存操作时，会产生碰撞问题。EPC Gen2标准防碰撞算法采用了基于动态帧时隙ALOHA法。在读写器开始对标签群进行盘存时，读写器发出Query命令，Query命令含有一个参数Q，Q的取值范围为1至15，该参数控制标签往各自的时隙计数器内载入一个随机数。当标签接收到读写器QueryRep命令时，时隙计数器值减1。仅当标签内时隙计数器值为0时，标签才对读写器进行响应；当时隙计数器值不为0时，标签不对读写器进行响应，而是根据读写器的不同命令，执行时隙计数器值继续减1操作，或者根据新的Q参数值再次载入新的随机数。已经阅读成功的标签，退出这轮标签盘存。当有两个或多个标签的时隙计数器值同时为0时，这些标签会同时对读写器进行响应，从而造成碰撞。读写器检测到碰撞发生后，发出相关命令，让碰撞标签的时隙计数器值从 0变到0xFFFF，继续留在这轮盘存周期内，以后读写器再设置新的Q参数值来分散发生碰撞的标签。这个识别过程一直继续下去，直到完成这轮盘存周期。

Query命令可能会出现以下3个结果：

(1)无标签响应：读写器可以另外再发一个Query命令，或者也可以发出QueryAdjust或QueryRep命令。

(2)一个标签响应：标签转换到应答状态，反向散射一个RN16，读写器发送ACK予以确认。若标签收到的ACK包含的RN16正确，则反向散射其PC、EPC和CRC-16，并转换到确认状态。若标签收到的ACK所包含的RN16错误，则转换到仲裁状态。假设是RN16正确的ACK，则读写器可以访问所确认的标签。

(3)多个标签响应：读写器观察到由多个RN16组成的反向散射的波形，发送QueryAdjust或QueryRep命令，直至识别出每个标签。图1为多个标签对读写器响应的时序图。

2 Q算法性能分析

2.1 系统效率

在RFID系统工作过程中，读写器天线辐射区域中的标签数量通常是未知的。大多数基于ALOHA的防碰撞算法先根据前一帧的反馈值(碰撞时隙数量ck、空闲时隙数量c0和成功时隙数量c1)，使用某一种标签估算方法来估算出待识别的标签数量n值，然后根据此数量值选择一个最佳的帧长度做动态调整[3]。

假设读写器使用帧长度大小为L，天线辐射区域中的标签数量为n，那么在一个给定的时隙内存在r个标签的概率符合二项分布

因此，在一个盘存周期内期望识别的标签数量为

式中：1,——在帧长度为L，待识别标签数量为n的情况下，时隙中存在1个标签的时隙数量。那么，系统效率可以计算得出

为了得出最大系统效率时标签数量，对式(2)求导

对式(4)求解，得出当帧长度为L时，最佳标签数量

图1 多个标签响应时序

由此，当标签数量为n时，最佳帧长度

当n很大时，利用Taylor级数近似得出

由以上可得出，当帧长度L与标签数量n值近似相等时，系统效率达到最大[4]，接近于时隙ALOHA算法的最大系统效率36.8%，如图2所示。

图2 各种帧长度下的系统效率

从图2中可以看出，帧长度取不同值时，对于帧时隙ALOHA算法，系统效率在标签数量等于帧长度时达到最大。读写器天线辐射区域中的标签数量是动态变化的，若要使系统效率始终保持在35%以上，则必须使帧长度最大限度地适应现场标签的数量n，即若能始终保持标签数量n值在合适的帧长度范围内，则可达到最优系统效率。

2.2 帧长度调整

若能准确估算出读写器天线辐射区域中标签数量 n值，就可以实时地对帧长度值最优化。通常可以通过以下几种预测算法来估算标签数量n值：

(1)LowerBound算法[5]：碰撞时隙数量为ck，碰撞时隙至少有2个以上的标签存在，则可以预测发生碰撞的标签数量至少为2*ck。

(2)Schoute算法[6]：在同一帧中，若每个标签选择的时隙符合 =1的泊松分布，则该帧中各碰撞时隙平均响应的标签个数约为2.39，这样可以预测未识别的标签数量为2.39*ck。

(3)Vogt算法[7]：通过比较前一帧成功、空闲、碰撞时隙数量与理论的成功、空闲、碰撞时隙数量得出误差最小的结果来预测未知标签数量，即

其中，c1、ck、c0为实际测得的成功、空闲、碰撞时隙数值。在标签数量N取值范围[c1+2*ck，……，2*(c1+2*ck)]内找到最小的 值，所对应的N值就是预测的标签数量。

图3给出了采用Lowbound、Schout、Vogt这3种不同的标签预测算法的系统效率仿真结果，它们均先预测确定现场可能的标签数量后，然后动态调整最优帧长度。与帧时隙ALOHA算法(帧长度固定为256)相比，可以看出基于标签数量预测的系统的效率有明显改善，最高系统效率达到了36%。

图3 系统效率比较

但从图4看出，当现场标签数量比较大(特别是标签数量大于500)时，采用由预测标签数量算法来设置最优帧长度的方案是不合适的，系统效率急剧下降，从32%下降至18%左右。

图4 大量标签情况下标签预测方案比较

所以，为了使现场存在标签数量大于500时系统效率得到提高，EPC Gen2标准中采用了Q算法的实时自适应帧时隙设置方案。当一个帧中出现过多的碰撞时隙时，读写器提前结束该帧然后发送一个新的更长的帧；当一个帧中出现过多的空闲时隙时，此帧也不是最优长度的帧，读写器提前结束该帧然后发送一个新的更短的帧。Q算法如图5所示。

图5中参数Q为正整数，取值范围为0到15。帧长度为L=(2^Q)-1，Q值是动态变化的，初值取round(Qfp)。一个时隙之后，若该时隙是碰撞时隙，则将Qfp加上参数c；若是空闲时隙，则将Qfp减去参数c；若是成功时隙，则Qfp保持不变。读写器根据新的Q=round(Qfp)来决定是继续发送下一个时隙还是重新开启一个新的帧。

图5 Q算法

图6给出Vogt算法和Q算法两种方案的系统效率仿真结果[8]。与Vogt算法相比，在读写器范围内存在大量标签时，Q算法系统效率明显提高，接近于帧时隙ALOHA算法的最大系统效率38.6%。

图6 Vogt算法和Q算法性能比较

3 Q算法改进

Q算法能够在标签数量变化很大的范围内实现高系统效率主要取决于参数c的取值情况。c太大会造成帧长度调整过于频繁，太小又不能快速的实现最优帧的选择。在Q算法中，帧长度调整过于频繁，即Q值变化过于频繁，导致标签频繁地重新选择时隙，这将带来很大功耗负担；同时，若帧长度不能实时调整到最优帧长度，则识别标签速率迅速下降，系统效率也大大降低。因此，系统效率和功耗问题是相互矛盾的。仅仅依靠参数c的取值调整，并不能使帧长度最优地适应标签数量，不能完全解决Q算法这一矛盾。

Q算法在参数c的辅助下对帧长度进行动态调整，从图7中可看出在读取500个标签过程中动态调整帧长度的过程[9]。识别500个标签需要读写器与标签通信交互次数约1500多次。Q值在通信100次左右之后可以迅速调整到最佳帧长范围内，但从200到1400之间，Q值不断的做出调整，在7、8和9之间波动，即帧长度在128、256和512之间调整。在总的识别过程中，Q值跳动次数为280次。这样非常密集的调整Q值，直接导致标签内部频繁地启动随机数发生器，从而选择新的时隙。而标签动态功耗量主要来自于标签内部模拟电路和数字电路电平变化和翻转，Q值调整次数每增加一次，意味着标签动态功耗量增加一个固定值0.8uw(芯片电路设计和工艺不同，功耗略有差别)，从而如何减少Q值调整次数成为重点。

图7 Q算法帧长度调整过程

本文对此提出一种新的解决方案，简述如下：

当前Q值记为Q，产生碰撞累积得新Q值记为newQ，上一Q值记为oldQ；

当产生新Q值newQ时，立即清除Qfp，恢复成newQ；

若产生的新Q值newQ与oldQ相同，则保持当前Q值不变，oldQ更新；

若产生的新Q值newQ与oldQ不同，则Q值和oldQ同步更新。

这样，使帧长度稳定在最优值范围内，相邻通信次数间减小Q值调整频率。改进后的Q算法读取500个标签过程中动态调整帧长度的过程如图8所示。

图8 改进后Q算法帧长度调整过程

从图8中可以看出，识别500个标签需要读写器与标签通信交互次数约1400多次。Q值在通信100次左右之后依然可以迅速调整到最佳帧长范围内，但从200到1400之间，与改进之前的Q算法相比Q值调整次数明显减少，即帧长度调整频率变小，帧长度在128、256和512之间调整。在总的识别过程中，Q值跳动次数为51次。因此，标签内部防碰撞模块门电路翻转频率变小，随机数发生器启动次数也减少。

以识别500个标签为例，Q算法防碰撞过程中，Q值调整280次，总动态功耗动态为224uw；改进Q算法后防碰撞过程中，Q值调整51次，总动态功耗为40.8uw，总动态功耗下降了81.8%。

从图7中看出识别过程接近结束时，Q值不能够迅速减小至盘存结束。并且Q值小于4，对识别标签提高效率意义不大，故可进一步改进Q算法，使Q取值最小只能为4，帧时隙数最少为16。仿真结果如图9所示。

图9 改进后Q算法帧长度最小为16的调整过程

这样，与原Q算法相比，改进后的Q算法调整帧长度频率降低，并且盘存开始后，可以迅速进入最佳帧长范围；盘存接近结束时帧长度保持固定长度，可以降低标签动态功耗。同时，给出改进后的系统效率，如图10所示。系统效率与原Q算法相比并未降低，依然维持在30%以上。

图10 改进后的Q算法识别效率

4 结束语

对EPCGen2防碰撞Q算法进行了深入分析，研究了RFID系统标签数量的3种不同估算方法，与Q算法比较了系统效率的优劣，并对Q算法提出改进方案。通过比较相邻或相近的帧长度，使Q算法到达最优帧长度范围内之后，帧长度调整频率明显减小，从而降低了标签防碰撞过程中总动态功耗81.8%。同时，系统效率并没有降低，依然保持在30%以上，标签消耗的硬件资源没有任何增加，可应用于低功耗远距离RFID系统。

[1]刘亮,邢焕革,郭金卫.奇偶区域搜索反碰撞算法及其仿真分析[J].计算机工程与设计,2010,31(12):2740-2743.

[2]EPCglobal Inc.EPCTM radio-frequency identity protocols class-1 gen-2 UHF RFID protocol for communications at 860 MHz-960 MHz version 1.2.0[S].Lawrenceville:EPCglobal Inc,2008.

[3]Su-Ryun Lee,Sung-Don Joo,Chae-Woo Lee.An enhanced dynamic framed slotted ALOHA algorithm for RFID tag identification[C].Proceedings of the Second Annual International Conference on Mobile and Ubiquitous Systems,2005:166-172.

[4]Wang Jianwei,Wang Dong,Zhao Yuping.A novel anti-collision algorithm with dynamic tag number estimation for RFID systems[C].Proceedings of the IEEE International Conference on Communication Technology,2006:1-4.

[5]Jae-RyongCha,Jae-Hyun Kim.Dynamicframed slotted ALOHA algorithmsusingfast tag estimationmethodfor RFIDsystem[C].Proceedings of the IEEE International Conference on Consumer Communications,2006:768-772.

[6]Inwhee Joe,Juno Lee.A novel anti-collision algorithm with optimal frame size for RFID system[C].5th ACIS International Conference on Software Engineering Research,Management&Applications,2007:424-428.

[7]Tae-Wook Hwang,Byong-Gyo Lee.Improved anti-collision scheme for high speed identification in RFID system[C].First International Conference on Innovative Computing,Information and Control,2006:449-452.

[8]Cheng Jin,Sung Ho Cho.Performance evaluation of RFID EPC Gen2 anti-collision algorithm in AWGN environment[C].Proceeding of the IEEE International Conference on Mechatronics and Automation,2007:2066-2070.

[9]Tao Cheng,Li Jin.Analysis and simulation of RFID anti-collision algorithms[C].Proceedings of the 9th International Conference on Advanced Communication Technology,2007:697-701.