基于帧内调整的RFID防碰撞Q值算法的研究

胡智宏，李 凯

（郑州轻工业学院 电气信息工程学院，郑州 450002）

0 引言

RFID（Radio Frequency Identif i cation）技术是20世纪80年代兴起的一种非接触式的自动识别技术[1]。阅读器通过无线射频方式与电子标签进行双向数据通信，识别电子标签并对其进行读/写操作[2]。RFID技术具有很多突出的优点，如识别距离远、多目标自动识别、能够工作在恶劣的环境下、电子标签存储的信息量大以及具有很高的保密性等[3]。因此在工业自动化、交通运输管理、物流仓储自动化和图书档案管理等领域得到了广泛的应用[4]。但其在使用中存在很多技术难点，比如当多个标签进入同一个读写器的射频覆盖区时，它们之间会产生碰撞的问题，该问题也是影响RFID技术应用的一个问题。ISO 18000-6C标准提出了一种解决多标签碰撞问题的建议算法，即Q值防碰撞算法[3]。但该算法中没有明确给出参数C调整时的取值，且其仅在一帧结束时调整Q值的大小，使其在识别多个标签时时隙利用率不高，系统吞吐率低。

基于以上原因，首先给出了不同标签数量下使系统吞吐率达到最大的Q值，其次提出了在帧内动态调整Q值的方法，在一帧的中间时隙和结尾处分别对Q值进行调整。算法的改进对提高系统的吞吐率和标签的识别速度具有重要意义。

1 经典Q值防碰撞算法

1.1 算法总体描述

对于超高频频段的标签识别来说，6C是一种常见的应用标准。其识别过程简述如下：读写器首先向标签发送包含参数Q的Query命令，并开启一个盘存周期，即读写器对标签盘存2Q次[5～8]。

1）标签根据参数Q产生一个16位的RN16作为代表其身份的临时ID，并从中抽取Q位的子集将其置入时隙计数器（slot counter）中[5～8]；

2）时隙计数器数值为0的标签立即响应，反射其RN16。若读写器接收到有效的RN16，则发送包含该RN16参数的ACK指令，若标签收到有效的ACK指令则将其EPC反射给阅读器并转换到确认状态[5～8]。时隙计数器数值不为0的标签进入仲裁状态[5～8]；

3）读写器发送QueryRep指令，处于仲裁状态标签的slot counter的数值减1，执行步骤2的操作；

4）在一帧识别结束后判断Q值，若Q的值改变，读写器发送QueryAdjust指令，改变Q值并开启一个新的盘存周期，若Q的值不变则发送Query指令开启一个新的盘存周期，转到步骤1执行。

在一个时隙中，若没有标签应答则为空闲时隙；若有单个标签应答为成功时隙；若有多个标签应答则为碰撞时隙。Q值防碰撞算法就是读写器通过检测到的空闲时隙、成功时隙和碰撞时隙的个数来动态调整Q值的大小[9～11]，其算法流程如图1所示。其中Qfp为参数Q的浮点表示，C为Q值的调整步长。在一个盘存周期中，若读写器检测到空闲时隙，则Qfp=max(0,Qfp-C)；若检测到成功时隙，则Qfp保持不变；若检测到碰撞时隙，则Qfp=min(15,Qfp+C)[9～11]。当Q值较大时，C取较小值，而当Q值较小时，C取较大值。在一帧结束时对Qfp取整并调整Q的值[9～11]。

图1 Q值防碰撞算法流程图

1.2 最佳帧长

在一个盘存周期中，当标签的数量远大于时隙数时，会出现大量的碰撞时隙，导致时隙的浪费；而当标签的数量远小于时隙数时，会出现很多空时隙，也会造成时隙的浪费。可以证明，当时隙数约等于标签数时，读写器在一帧中识别出的成功时隙的数目达到最大值，能识别出最多的标签数。证明过程如下：

假设待识别的标签数为N，如果标签随机选择（0,L）中的随机数ξ载入槽计数器，并且各个Tag选择的数值是相互独立的，则ξ服从二项分布，ξ～ B（N,1/L）。因此，一个时隙为空，成功和碰撞时隙的概率为[12]：

系统的吞吐率为：

由式(2)可得成功时隙的数学期望为：

通过对式(4)中的L求导，并令其等于0，可得：

即每帧时隙的个数与待识别的Tag数近似相等时，系统的吞吐率能取得最大值。该时隙数即为Q值算法的最佳帧长。

由于Q值算法没有具体给出C值的大小，只是建议C的值在0.1～0.5之间，当Q取较大值时C取较小值，Q取较小值时C取较大值[13]。因此，我们首先需要确定不同标签数下的最佳帧长，以此来得到不同标签数下的最佳Q值。

图2 不同帧长的系统吞吐率与标签数关系图

图2描述了不同的标签数量在不同的帧长下系统的吞吐率。从图中可以看出，当帧长与标签的数量近似相等时，系统的吞吐率达到理论上的最大值，近似为0.368。通过式(4)和图2，我们可以得到不同标签数下的最佳Q值，如表1所示。

表1 不同标签数下的最佳Q值

2 改进的Q值防碰撞算法

以往对防碰撞算法的改进，主要包括两个方面：一是提高未识别标签数目预测的准确度。但复杂的标签预测算法会加重计算能力有限的读写器的负担；二是与其他防碰撞算法相结合，例如与二叉树防碰撞算法的结合。但二叉树防碰撞算法的实现要求读写器的编码方式为曼彻斯特编码，而6C标准规定的读写器的编码方式为PIE编码[14]。这些改进在一定程度上都可以提高系统的吞吐率，但不利于在实际中的应用。

本文在先前研究和经典Q值算法的基础上，提出了在6C标准下易于实现的改进算法。该算法采用Lowbou-nd算法[15]来预测标签的数量，以减轻计算能力有限的读写器的负担。经典Q值算法是在一帧识别结束时调整Q的值，而当帧长较大时，不合适的Q值会造成大量碰撞时隙或空闲时隙的出现，导致系统的吞吐率下降。改进算法采用了在帧内动态调整Q值的策略，在一帧的中间时隙和结束时分别对标签的数量进行预测，并与表1中得到的最佳帧长进行比较，若与其不同则发送QueryAdjust或Query指令调整Q的值，使帧长调整到最佳值；具体的算法流程如图3所示。

图3 改进的Q值防碰撞算法流图

3 系统仿真与性能分析

在MATLAB平台下分别对固定帧时隙算法、基于Schoute预测的DFSA（Dynamic Framed Slotted Aloha）算法[15]和改进算法的系统吞吐率和识别时间进行了仿真。标签范围选择在0～500之间，结果是通过测试1000次求其平均值得到的。

由图4可以看出，256固定帧时隙算法在标签数和时隙数相等时，系统吞吐率达到最大值0.368，基于Schoute预测的DFSA算法系统吞吐率维持在0.37左右；改进算法的吞吐率维持在0.42左右。在标签数量大于50个时，改进算法的性能优势明显。

图4 不同算法下的系统吞吐率

图5 不同算法下的识别时间

由图5可知，基于Schoute预测的DFSA算法和本文所提出的改进算法识别标签所需的时间要少于时隙数为256的固定帧时隙算法。改进算法在标签数较小时所用的识别时间多于DFSA算法。但当标签数大于50时，改进算法所用的识别时间增长缓慢并少于DFSA算法，说明该改进算法在标签数较多时性能较好。如图5所示, 该改进算法识别500个标签大概需要1450ms，识别速度约为345个/秒。物流管理的应用中要求读写器的识别速度要大于300个/秒，故该改进算法能满足物流管理的应用要求。

4 结束语

本文通过理论推导和仿真，给出了不同标签数量下的最佳Q值，并在Q值算法的基础上提出了一种改进算法。该改进算法采取了在一帧的中间时隙和结束时分别动态调整Q值的策略。通过与其他算法的比较，证明了该改进算法在性能上的优越性。同时该算法也考虑了

ISO 18000-6C标准和实际的硬件条件，能在计算能力有限的读写器上实现，具有实用价值。

[1] 管小卫,傅伟,蒋道霞.一种改进的分组帧时隙ALOHA算法[J].制造业自动化,2014,36(7):1-4.

[2] 陆冰清,牛国柱,赵英臣.一种新型RFID动态多叉树查询防碰撞算法[J].制造业自动化,2012,34(15):12-15.

[3] 王维,宣兆龙,程泽,等.基于RFID技术的弹药储运方舱自动识别系统研究[J].包装工程,2014,35(11):91-95.

[4] 张学军,蔡文琦,王锁萍.改进型自适应多叉树防碰撞算法研究[J].电子学报,2012,40(1):193-198.

[5] 李萌,钱志鸿,张旭,等.基于时隙预测的RFID防碰撞ALOHA算法[J].通信学报,2011,32(12):43-50.

[6] Muhammad F,Muddassar A, Syed N, etal. Optimal Adjustment Parameters for EPC Global RFID Anti-Colli -sion Q Algorithm in Different Traffic Scenarios[A].Proc of 10th International Conference on Frontiers of In -formation Technology, Islamabad,Pakistan[C],CA,2012:302-305.

[7] Andreas S,Christoph R. Retransmission Strategies for RFID systems Using the EPC Protocol[A].Proc of the 2013 IEEE International Conference on RFID Technologies and Applications,Johor Bahru, Malaysia,CA[C].2013:1-6.

[8] Eom J, Lee T.Accurate tag estimation for dynamic framed-slotted ALOHA in RFID systems[J].IEEE Com-munications Letters,2010,14(1):60-62.

[9] 陈颖,张福洪,廖彬彬.一种新的RFID传感系统的防碰撞算法的研究[J].传感技术学报,2009,22(6):865-868.

[10] 王进,易灵芝,王根平.新型Q值防碰撞算法在RFID系统中的研究[J].计算机工程与科学,2011,33(6):182-185.

[11] 任守纲,杨帆,徐焕良.一种双权重参数的RFID防碰撞Q值算法研究[J].计算机科学,2014,41(4):256-259.

[12] 吴海锋,曾玉.RFID动态帧时隙ALOHA防冲突中的标签估计和帧长确定[J].自动化学报,2010,36(4):620-624.

[13] Chen Y H, Horng S J,and Tun R S. A novel anti-collision algorithm in RFID systems for identifying pa-ssive tags[J].IEEE Transactions on Industrial Informatics, 2010,6(1):105-121.

[14] Eom J, Lee T.Rietman R. An efficient framed-slotted ALOHA algorithm with pilot frame and binary sele-ction for anti-collision of RFID tags[J].IEEE Communications Letters,2008,12(10):861-863.

[15] 李青青,刘洪武,张小林.一种基于不等长时隙的射频识别防碰撞算法[J].电子与信息学报,2011,33(11):2628-2633.