【学术论文】基于EPC Gen2防碰撞算法的研究与优化
摘要：
防碰撞算法是射频识别(RFID)关键技术之一。基于EPC Gen2标准的Q值防碰撞算法，提出了InnerQ算法，利用对碰撞时隙再次处理的方法，解决原有算法Q值反复跳变的问题，并提高了系统吞吐率，突破了ALOHA类算法吞吐率最高为36.8%的瓶颈，提高了RFID系统性能。
0 引言
射频识别(Radio Frequency Identification，RFID)是一种可以通过无线电信号识别特定目标并读写相关数据的无线通信技术[1]。RFID系统的射频通信部分包括阅读器和标签，当阅读器的电磁能量覆盖范围内同时有多个标签向该阅读器返回信息时，阅读器便无法正确识别任何一个标签的信息，这种现象称之为标签碰撞。
目前，国际通用标准EPC Gen2中采用的防碰撞算法可用于解决标签碰撞问题。EPC Gen2算法基于ALOHA类算法，有很好的自适应性，实现简单，有较低的识别时延，但是缺点是吞吐率较低。前人的一些文章中对EPC Gen2防碰撞算法进行了优化，吞吐率有所提高，但都难于实现，并且很多文章也没能突破在标签数比较多的情况下，吞吐率仅为36.8%的瓶颈[2-4]。
本文提出的优化方案在分析了EPC Gen2算法和动态帧时隙ALOHA算法(Dynamic Frame Slotted ALOHA，DFSA)[5]的特点和性能的基础上，提出了InnerQ算法，仍然保持了ALOHA类算法的易于实现的优点，减少了标签碰撞时隙数，同时提高了系统吞吐率，突破了36.8%的瓶颈。
1 研究现状
1.1 DFSA算法介绍
DFSA算法是一种可以动态调整帧长，使帧长接近待识别标签数目，让系统吞吐率尽可能保持在最大值的一种算法。当帧长等于待识别标签数目时，系统吞吐率达到最大值，并且当标签数远大于1时，吞吐率的峰值保持在36.8%。证明过程参见文献[6]。
1.2 EPC Gen2算法介绍
EPC Gen2标准中的防碰撞算法也是一种特殊的DFSA算法。该算法由读写器定义一段时间长度（包含若干个时隙），当标签接收到对应命令后，随机选择一个时隙进行接入。读写器通过Query、QueryRep、QueryAdjust等指令的组合对标签中时隙计数器数值进行调整，当标签的计数器值为0时进行响应。在一个盘存（Inventory）周期中包含多个帧。EPC Gen2防碰撞算法可以在盘存过程中的任意时刻动态调整帧长，使未识别标签进入下一帧的响应周期中[7]。
1.2.1 EPC Gen2防碰撞算法的实现步骤
该算法流程如图1所示，具体实现步骤如下：
(1)Q初始值设为4。读写器发出Query(Q)指令，开始一个盘存周期。
(2)标签会在[0，2Q-1]范围内生成一个随机数载入到标签时隙计数器。同时在阅读器端将2Q载入到阅读器时隙计数器，以此记录当前帧长剩余时隙数。
(3)标签时隙计数器的值为0时进行响应，若当前时隙只有一个标签进行响应，则为成功时隙。若有两个或两个以上标签进行响应，则为碰撞时隙，Qfp的值加上C值；若没有标签响应，则为空闲时隙，Qfp的值减去C值。
(4)当前时隙处理完成，阅读器的时隙计数器减去1。若阅读器的时隙计数器减为0，则再次发送Querry命令，开启新的一帧，回到步骤(2)；若阅读器的时隙计数不为零，并且Q值发生了变化，则发送QueryAdjust命令，调整Q值，开启新的一帧，回到步骤(2)；若阅读器的时隙计数器不为零，并且Q值未发生改变，则发送QuerryRep命令，标签时隙计数器的值减1，回到步骤(3)。如此循环往复。
1.2.2 EPC Gen2防碰撞算法的性能分析
在识别过程中，参数Q决定了标签产生的随机数的范围，参数C决定了是否改变帧长以适应标签数目的变化，从而直接影响系统的性能。该算法并不消耗大量的运算去估算待识别标签的数量，只是去统计碰撞时隙、空闲时隙的次数。当接入信道连续的发生1/C次碰撞或空闲时，Q值进行加1或减1操作。该算法实现简单，但也有如下两个缺点：
(1)Q值反复跳变。
标准规定Q的初始值等于4，当标签数量比较多时，Q值会依次增加到某一个值，并在该值左右反复跳变。Q值每改变一次，标签就得重新生成一次随机数，即使当Q值改变到合理范围（2Q接近标签个数），仍会反复跳变，导致标签做大量的无用动作，增加识别时延。举例说明：在标签数量为200、600和1 000的情况下，待识别标签数目的变化和Q值的关系如图2所示。
(2)帧长并不能做到和标签数相等，导致吞吐率较低。
由于Q值控制的帧长始终是2的幂，而标签数量不可能总是2的幂，因此该算法的吞吐率一定无法达到36.8%的理论值。由于C值对吞吐率有直接的影响，而标准中又没有给出具体的取值，因此不同的文章选取不同的C值，分析得到的吞吐率也不同。为了便于研究，本文借鉴文献[8]，采用基于经验值的C=0.8/Q调整Qfp的值，使得系统吞吐率能够保持在32%左右。
2 优化算法的提出
本文提出的优化算法InnerQ，针对上文提到的两个问题进行优化。InnerQ算法由两部分组成，一是稳定Q值算法，二是碰撞时隙再处理算法。
2.1 稳定Q值算法
由上文分析可知，当标签数量比较多时，Q值会从初始值增加到某一个值，然后在这一个值左右反复跳变。可以设计稳定Q值算法，记录Q值的变化过程，一旦检测到Q值不是依次递增或递减，而是反复跳变，则固定下Q值，让读写器不再反复发送QuerryAdjust，导致所有待识别标签都反复生成随机数。将Q值固定后的状态定义为Q值稳定状态。具体算法流程如图3所示。
达到Q值稳定状态后，标签时隙的分布相对比较分散，不会出现大量标签都选择同一个时隙，也不会出现大量的空闲时隙，造成时隙浪费的情况。在某一个时隙内标签接入成功、发生碰撞及空闲的概率[9]如式(1)所示：
由式(2)可以仿真得到总的标签数量n与达到稳定状态后的Q值，以及达到稳定状态后，碰撞时隙中平均包含的标签数量Nc的对应关系，结果如表1所示。
由表1可以得出结论，当Q值稳定后，标签的分布比较分散，每一个碰撞时隙的标签数量是少量的，在2~6的范围内。
2.2 碰撞时隙再处理算法
达到Q值稳定状态后，只是标签选择接入的时隙比较分散，但是仍有碰撞标签的存在。这些标签需要再次处理，才能全部识别。本文提出的方案出于兼容性的考虑，借鉴了原先的EPC Gen2防碰撞算法的处理逻辑，并且它是一种特殊的DFSA算法，而DFSA算法在标签个数比较少时，吞吐率是比较高的。
证明过程如下：
设帧长为L，标签数为n。某个时隙仅被一个标签选择的概率为Ps，则：
该函数图像如图4所示。可以观察到，当标签数量小于40时，吞吐率明显高于36.8%，并且随着标签的减少，吞吐率有大幅度的提高。而这个特点被很多研究EPC Gen2防碰撞算法优化的学者忽视，并没有充分利用，导致提出的优化方案总是想办法让吞吐率接近36.8%，而始终无法超过这个理论瓶颈。
本文首先利用上文提到的Q值稳定算法，使得每一碰撞时隙标签的个数平均在2~6之间，对这些碰撞标签再处理并不影响到其他时隙的标签，同时又利用了DFSA算法在标签个数少时吞吐率高的特性，大幅度提高了系统的吞吐率。算法流程图如图5所示。
需要注意的是，本文在碰撞时隙再处理时借鉴了原有标准中Q值的处理流程，但是也有一些变动，其中有个明显的变动是Q值的初始值要从4改成2。因为由表1的数据可知：碰撞时隙内的标签数量在2~6个之间。Q值等于2时是更接近实际标签的数量，虽然做不到理论上的严格相等，但是在数学规律上符合DFSA算法在标签数量比较少时吞吐率较高的规律。图6展示了不同的Q的初始值对应吞吐率的变化情况。
3 仿真结果与分析
为了从实验角度证实InnerQ算法的有效性，利用仿真软件MATLAB分别对EPC Gen2算法、DFSA算法、InnerQ算法进行仿真。标签数量1 000个。由于这3种算法都是基于ALOHA算法改进的随机性算法，仿真的结果是取500次实验的平均值。以系统吞吐率、碰撞时隙个数、总时隙个数这3个指标作为评价标准，仿真得到的结果如图7～图9所示。
图7截取了标签数量从100～1 000个的数据来展示，结果表明DFSA算法的吞吐率始终保持在36.8%，与本文的的理论分析和前人的研究结果相吻合。本文提出的InnerQ算法结合了DFSA算法在少量标签的情况下吞吐率比较高的特点，利用碰撞时隙再处理的思想，使系统吞吐率稳定在42%左右。
图8的结果表明，InnerQ算法的碰撞时隙个数明显小于优化之前的算法。因为优化算法使得碰撞时隙内的标签数目比较少，这样再次处理时，发生碰撞的机率就比较小，碰撞时隙数自然就会减少。
图9的结果显示，DFSA算法、EPC Gen2算法和InnerQ算法在识别标签总时隙的差别上不算太大，虽然利用碰撞时隙再处理的方法其实是相当于引进了更多的时隙，但是碰撞时隙内的标签较少，并且稳定Q值算法，使得Q值不再反复跳变，相当于减少了不必要的时隙浪费。所以优化算法在整体上并没有增加过多额外的时隙。
4 结论
本文研究了DFSA算法和EPC Gen2算法的特性，指出了其中被很多人忽略的地方，从理论和仿真数据上证明，本文提出的优化算法可以突破原来的ALOHA类算法在多标签识别的情况下，吞吐率最高只能达到36.8%的瓶颈。优化算法的吞吐率提高到了42%左右，碰撞时隙数也有了大幅减少，同时确保了与当前标准的兼容性，可以快速投入到实际的生产中，具有很好的应用前景。
参考文献
[1] 杜云明，周杨.无线射频识别技术与应用研究[J].自动化技术与应用，2010，29(5)：52-55.
[2] 任守纲，杨帆，王浩云，等.基于判决门限的RFID防碰撞Q值算法[J].计算机科学，2014，41(8)：154-157.
[3] 吴淼，刘德盟，张钊锋.基于EPC Gen2防碰撞机制的研究与优化[J].微电子学与计算机，2013，30(5)：100-103.
[4] LEE D，BANG O，IM S，et al.Efficient dual bias Q-Algo-rithm and optimum weights for EPC Class 1 Generation 2 protocol[C].Wireless Conference，2008. Ew 2008. European.IEEE，2008：1-5.
[5] CHA J R，KIM J H.Dynamic frame slotted ALOHA algo-rithms using fast tag estimation method for RFID system[C].Proceeding of the IEEE International Conference on Consumer Communications，2006：768-772.
[6] LEE S R，JOO S D，LEE C W.An enhanced dynamic framed slotted ALOHA algorithm for RFID tag identification[C].IEEE Computer Society，2005：166-174.
[7] EPC Global.Radio-frequency identity protocols Class-1 Generation-2 UHF RFID protocol for communications at 860 MHz-960 MHz version 1.2.0[S/OL].(2008-05-11)[2017-08-08].URL：http：//www.gs1.org/sites/default/files/docs/epc/uhfc1g2_1_2_0-standard-20080511.pdf.
[8] FLOERKEMEIER C，WILLE M.Comparison of transmission schemes for framed ALOHA based RFID protocols[C].International Symposium Applications and the Internet Workshops.Phoenix，2006：94-97.
[9] CHA J R，KIM J H.Novel anti-collision algorithms for fastobject identification in RFID system[C].International Conference on Parallel and Distributed Systems. Fukuoka，2005：63-67.
作者信息:
孙 磊1，2，庄健敏1，张钊锋1
(1.中国科学院上海高等研究院，上海201210；2.中国科学院大学，北京100190）