基于动态Q值的RFID防碰撞算法

李建雄，冯 鑫，史伟光，宋战伟

（天津工业大学电子与信息工程学院，天津300387）

基于动态Q值的RFID防碰撞算法

李建雄，冯 鑫，史伟光，宋战伟

（天津工业大学电子与信息工程学院，天津300387）

在考虑冗余时间的情况下，利用DFSA数学模型的最大系统效率值，将标签分组与动态调整Q值相结合，对传统Q值算法进行优化，并提出了针对EPC-C1G2协议的DQA防碰撞算法.仿真结果显示：与传统防碰撞算法相比，所提出的算法保持系统效率在0.368，节约系统时隙，减少系统冗余时间.此外，该算法考虑了EPC-C1G2标准，移植性强.

RFID；动态帧时隙；最大系统效率；Q值算法；防碰撞算法

近几年，随着现代物流业技术与制造业信息化水平的提高，射频识别（RFID）技术凭借其非接触式识别方式以及大量存储信息的优势，已经被公认是条形码识别系统的最好替代技术，并广泛地应用于仓库物流[1]、室内定位[2]、图书管理[3]等诸多领域.然而，当2个或2个以上标签同时与阅读器通信时，由于无源RFID系统标签共用一个传输信道，标签之间的碰撞将导致标签不能与阅读器正常通信.

目前，动态帧时隙算法（DFSA）是最为常用的标签防碰撞方法[4-5].由于识别帧长和标签数量会直接影响到RFID系统效率，为了降低标签之间的碰撞率，系统使用某一帧长完成一轮标签识别过程之后，DFSA会根据该帧长内标签的碰撞情况，动态调整下一识别过程的识别帧长.然而，阅读器没有标签数目感知能力，需根据当前帧长度下标签的碰撞情况来调整下一识别过程的识别帧长.

EPC Class1 Generation2（EPC-C1G2）协议即ISO/ IEC 18000-6C国际标准[6]，采用了Q值防碰撞算法对标签进行识别.该算法通过统计识别帧内部空闲和碰撞时隙的数目，控制下一识别帧的长度，使得系统在不同标签数目范围内，均可以保持较好的识别性能.然而，学术界大多采用穷举法进行模拟，使得系统最优效率很难实现.

本文利用RFID最大系统效率值，在考虑冗余时间的情况下，提出一种基于动态Q值的标签防碰撞算法，该方法类似于Q值算法的帧长度改进方法，本文命名其为DQA算法.当识别环境有大量标签存在时，DQA算法将结合碰撞和空闲时隙的数目，使用最大系统效率对Q值算法进行简化，进而实时控制识别帧长.仿真结果表明，DQA算法与现有Q值算法比较，能够有效地降低系统总时隙数目的消耗，减少计算量.

1 EPC-C1 G2 协议和Q值算法

EPC-C1G2协议是第二代EPC超高频空中接口标准，该协议使用的防碰撞算法如图1和图2所示.

图2 EPC-C1G2协议下多标签查询-应答的链路时序图Fig.2 Link timing of multi-tags′query-response on EPC-C1G2

首先阅读器向标签发送包含参数Q信息的大小为22比特的Query指令，开启一个盘存周期，则阅读器对标签盘存的次数为2Q[7-8].

（1）标签产生一个16位的RN16作为其临时身份的ID，并将[0，2Q-1]范围内产生的一个随机数置于自身时隙计数器中；

（2）时隙计数器数值为0的标签向阅读器发送其RN16.若读写器收到有效的RN16，则发送包含该RN16参数的ACK指令到指定标签；若该标签收到有效的ACK，则发送其EPC到阅读器并进入到确认状态.时隙计数器数值不等于0的标签则转到仲裁状态；

（3）读写器发送QueryRep指令，处于仲裁状态标签的slot counter减1，跳转至步骤（2）；

（4）一帧识别结束后，判断Q值：若Q值改变，读写器发送QueryAdjust指令，改变Q值并开启一个新的盘存周期；若Q值不变，阅读器发送Query指令，开始一个新的盘存周期，跳转至步骤（1）.

在无源标签识别系统中，阅读器不能预知标签数目.如果帧长预估计结果太大，空闲时隙数目会随之增加，导致系统总时隙数目的增加；相反，如果帧长预估计太小，一帧识别结束后，标签之间严重的碰撞现象会导致系统识别率下降.因此，一个合理的帧长度预估计体系对DFSA防碰撞算法至关重要.Q值算法通过适时统计成功时隙、空闲时隙和碰撞时隙的个数来完成Q值大小的动态调整[9-11]，其算法流程如图3所示.

图3 Q值算法的流程Fig.3 Control flow of Q Algorithm

图3中：Qf为Q值的浮点表示；C为调整步长.令2Qi等于第i帧的长度Li，一个盘存周期内，标签随机选择时隙进行应答，若检测到无标签应答，则Qf=max（0，Qf-C）；若检测到标签成功应答，则Qf保持不变；若检测到多个标签同时应答，则Qf=min（15，Qf+C）.当Q值较大时，C选择较小值，而当Q值较小时，C选择较大值.因此，第i帧结束时，对Qf取整并调整Qi+1得：

式中：Nc和Ne分别代表第i帧中碰撞和空闲时隙的数目；round（φ）表示接近φ的最小整数.

Q值算法允许读写器在识别帧内选择任意一个时隙，通过灵活控制C值的大小，有效地提高系统的识别率.一般地，C值的大小介于0.1到0.5之间.当识别帧长较大时，限制C值大小会影响系统的识别率.当识别帧长较小时，如果C值的下限选择不当，将会导致帧长动态调整机制出现饥饿现象：即使当前识别系统出现严重的时隙碰撞或者空闲现象，帧长仍然不会改变.目前，针对最优C值选择的问题，虽然有诸多方案，但C值多数通过建模仿真获得.

2 基于EPC-C1 G2的防碰撞算法

在RFID系统中，标签识别率的高低决定系统性能的好坏.通常定义识别率S为只有一个标签选择的时隙数目与系统全部时隙数目的比值，如公式（2）所示.

使用第i个帧长对标签进行识别时，由于会出现只有一个标签选择的成功时隙Ns、没有标签选择的空闲时隙Ne以及因为多个标签选择的碰撞时隙Nc，因此，公式（2）可改写为：

假设阅读器识别区域内的标签数目为n，阅读器随机选择（0，Li）范围内的任意整数τ，并置于计数器中.各阅读器之间选择数值相互独立，由于标签选择时隙服从二项分布，且τ～B（n，1/Li）.因此，有x个标签同时响应一个时隙的概率为：

则只有一个标签响应一个时隙的概率为：

对上式求导可得最优长度为：

当n较大时，使用泰勒级数化简得：

分析表明，当标签数目n等于帧长度Li时，系统识别率达到最大.但是由于RFID识别技术硬件条件的限制，当环境中出现大量标签时，帧长不可以无限增加.本文对标签采取分组操作，通过限制响应的标签数量降低标签之间的碰撞率，进而提高系统识别率.假设最大识别帧长Lmax=256，定义分组数G为：

不同帧长度下对应的系统效率如图4所示，结合抛物线的对称性可知，2个相邻帧长中必然存在系统效率相同的点，即满足SLi=S2Li，代入公式（5）得两曲线的交点为：

图4 不同帧长度下对应的系统效率Fig.4 System efficiency vs frame size

因此，当未识别的标签数目大于nLi，2Li时，调整下一帧长为原帧长的2倍；当未识别的标签数目小于nLi，2Li时，调整下一帧长为原帧长的1/2.

当所需要的Li大于256时，系统采取分组操作.定义帧长度为256时，SG和SG+1分别为标签分组数为G和G+1组所对应的系统效率.不同分组下对应的系统效率如图5所示，2个相邻不同分组间同样存在具有相同系统效率的标签数目节点，即满足SG=SG+1，化简得：

图5 不同分组下对应的系统效率Fig.5 System efficiency vs grouping number

3 DQA算法

标签与阅读器进行通信过程中，传输的内容不仅包括标签的数据信息，同时还包括数据传输过程中必备的选择、请求、应答等指令所占据的数据信息，定义其为冗余信息.本文在考虑冗余信息的情况下重新定义系统理论识别率η：

式中：E[η]为系统有效传输时间，即标签与阅读器进行实际数据传输时所消耗的时间；T冗余为标签与阅读器数据传输过程中所消耗的冗余时间.

不同分组情况下考虑冗余时间的理论系统效率如图6所示.

通常，在数据传输过程中，每一个识别帧长所包含的冗余信息是固定的.由图6可见，当标签数目较少时，E[η]较小，根据公式（11）可知，与E[η]比较，T冗余占有较大比重，系统理论识别率η随着标签数目的变化波动较大；由于在该标签数目范围内，阅读器识别帧长大小可调，因此，阅读器动态调整帧长以适应变化的标签数目，不采取标签分组措施.当标签数目较大时，E[η]占有足够大的比重，此时，系统理论识别率η随着标签数目的变化波动较小；由于在较大标签数目范围内，帧长不能无限增加，当识别帧长增加到最大值256且标签数目继续增大时，本文采用标签分组识别方式.

图6 不同分组情况下考虑冗余时间的理论系统效率曲线Fig.6 Theoretical value of system efficiency considering redundant time under different groups

图7所示为不同分组情况下获得的系统最优识别效率图，该图截取了识别率为0.360～0.368的区间.

图7 考虑冗余时间下的系统最优识别效率曲线Fig.7 Optimal value of system efficiency considering redundant time

由图7可知，对于存在大量标签的标签识别环境，在考虑冗余时间的情况下，分组优化后的帧时隙算法，可以使系统识别率在较高标签数目范围内保持理论上的最大值，近似等于36.8%.标签数目较少时，对于系统理论识别效率较低的现象，可以采用树确定性算法做进一步的改进.

结合公式（9）和公式（10），本文总结了不同标签数目范围所对应的最优帧长和分组数，如表1所示，并定义其为动态调整标准.

表1 考虑冗余时间下的不同标签数目对应的帧长度和分组数Tab.1 Optimal assignment of frame size and grouping number considering redundant time

对Q值算法的改进通常包括2种：一种是为变量设置权值，通过仿真获得不同Q值条件下最优权值的取值，但该算法较高的复杂度和较长的仿真时间会加重阅读器的负担；另一种是提升标签数目估计能力，例如Vogt[12]标签估计法，其原理如公式（12）所示：

式中：ε为预测误差；ns、nc和ne分别代表实际环境中成功、碰撞和空闲状态的时隙数目.该算法通过采用缩小理论和实际之间误差精确地估计未识别标签的数目，但由于其操作的复杂性，实际中很难应用.

Schoute[13]基于泊松分布提出了一种针对动态帧时隙算法（DFSA）的标签评估体系，未识别标签数目n0可由公式（13）获得.

该方法的优点在于原理简单易懂，方便移植，硬件要求低，计算量小，能够提供准确的标签数目估计.

本文以经典Q值算法和Schoute预测标签数目方法为基础，提出了适用于ISO180006C协议的动态帧改进算法.同时，为了获得最优帧长，本文使用最大系统效率，如公式（14）所示：

化简得

因此，一帧识别之后，根据该帧中成功识别标签的时隙个数，可以获得最大系统效率下对应的Q值，该Q值可决定EPC-C1G2协议中帧长的大小.改进的Q值算法，在标签数目较多时，采取动态分组的策略，同时，在一帧结束时，对标签数目进行预测，并与建立的动态调整标准进行比较，若与其不同，阅读器将发送QueryAdjust或Query调整指令改变Q值，保证系统识别率保持在36.8%左右，算法流程图如图8所示.

图8 DQA算法流程图Fig.8 Flow chart of proposed DQA algorithm

4 仿真结果及分析

本文对单阅读器多标签环境进行仿真，假设标签与阅读器之间为理想信道，忽略阅读器在识别过程中由于传播延时、链路丢失以及噪声干扰所引起的识别误差.所有标签均等地接受阅读器发送的能量，且在盘存过程中没有其他标签进出识别系统.成功接受识别的标签将不会响应阅读器接下来的识别指令.系统标签数目最大为1200个，阅读器的起始识别帧长为16.

在MATLAB平台下，对DFSA、GFSA[14]、EDFSA[15]和推荐的DQA算法进行仿真，依据Gen2协议评估各算法的识别时间.发送指令的长度、动态ID（RN16）和Q值算法均符合Gen2规范（如图1和图2）.上下链路的数据传输速率均被设置为80 kps，因此，标签在一个时隙花费的时间为0.2 ms.

图9显示了当标签数目为0～1 200时，各算法所消耗的时隙数目.由图9可知，当标签数目较小时，由于GFSA不能很好地控制识别帧长到最优，标签之间碰撞现象严重，系统识别率降低，所以消耗较多的时隙；其他3种算法动态调整识别帧长，使得系统保持较高的标签识别率，因此消耗的时隙数目随标签数目的增加而线性平稳增长.当标签数目较大时，EDFSA、GFSA、DQA算法均采取分组操作，DFSA算法由于受到阅读器最大帧长的限制且未采取分组操作，导致随着标签数目的继续增长，碰撞现象加剧，消耗的总时隙数呈现指数增长.DQA动态帧时隙算法简化了Q值更新方式，降低了识别系统的盘存次数，因此消耗较少的时隙数.

图10比较了基于Gen2协议各算法的冗余时间.该时间记录的是除去传输有效信息（例如96比特或256比特EPC信息）所消耗的时间，其中，系统耗时等于传输有效信号耗时与冗余时间之和.

图10 不同算法的系统冗余Fig.10 Redundant time of different algorithms

由图10可知，当标签数目较多时，DFSA算法中碰撞时隙消耗时间占主导因素；由于阅读器与每个标签进行EPC通信所消耗的时间是固定且有限的，因此系统冗余时间随着标签数目增长的幅度小于时隙消耗时间的增长幅度，因此单一考虑冗余时间时，会出现冗余时间增长幅度较缓慢的现象.当标签数目较少时，GFSA算法由于选择帧长过大，导致空闲时隙占主导因素；但对于识别相同数量的标签而言，阅读器发送帧的数量相比较于其他算法而言受帧长变化影响差别不大，因此，各算法冗余时间相差较小.EDFSA动态调整帧长，系统消耗识别帧的数量稳定增长，因此，冗余时间呈线性增长.DQA算法采用了考虑冗余情况下的最大识别效率对系统进行优化，使得帧长得到更加精确的控制，系统的盘存次数得到有效的降低，因此与其他算法相比较，冗余时间有所降低.

图11所示为不同算法的系统效率图.

图11 不同算法的系统效率图Fig.11 System efficiency of different algorithms

由图11可知，EDFSA通过采取动态分组与变帧长，使得系统保持较高的识别率，但该算法未将最大系统效率值应用于接下来的动态帧长调整中，使得其系统识别率并非最优.DFSA通过动态调整帧长使其在标签数目较少的情况下保持较好的系统识别率，但随着标签数目的增加，帧长不能无限增加，系统需要的时隙数目呈现指数增长，时隙碰撞加剧，最终导致系统识别率急剧下降.GFSA算法采用固定帧长进行识别，当标签数目较少时，由于未采用与DFSA相似的动态变帧长方法，导致一个识别帧中，出现大量的空闲时隙，造成时隙的浪费，因此降低了系统识别率；而当标签数目逐渐增大时，标签被分为多组，使得最终系统效率保持在一定范围内.本文提出的DQA算法在考虑冗余时间的情况下，重新获得了Q值调整标准，并且将动态分组和动态Q变帧有效结合，使得系统在不同标签数目范围内仍可以稳定地保持识别率在36.8%左右，优越于其他3种算法.

5 结语

使用EPC-C1G2协议中的Q值算法来调节帧长，能够减轻阅读器的计算负荷，节约大量的存储空间.在考虑系统冗余的情况下，使用系统最大识别率36.8%对传统Q值算法进行了优化，并采用效率高、计算量小的Schoute算法对标签数目进行估计.同时，本文提出了适用于Gen2协议的DQA防碰撞算法，将标签分组与动态调整Q值相结合，保证系统拥有稳定的识别率.仿真结果表明，该算法在节省时隙、减少冗余、保持较高系统识别率方面具有一定的优越性.此外，由于该算法考虑了EPC-C1G2的标准，可以直接移植使用，应用价值较高.

[1]李小笠，刘桂芝，尤正建，等.基于RFID的自动化生产线配套仓库管理[J].机床与液压，2013，41（13）：120-123.

[2]段本亮，李建雄，陈明省，等.改进的RFID室内定位算法[J].天津工业大学学报，2013，32（4）：66-70.

[3]胡国仁，韩其睿.基于条码与RF技术的图书仓储管理系统设计[J].天津工业大学学报，2008，27（1）：81-83.

[4]FINKENZELLER K，WADDINGTON R.RFID Handbook：Radio-Frequency Identification Fundamentals and Applications[M].Chichester：John Wiley&Son，1999：159-163.

[5]EOM J B，LEE T J.Accurate tag estimation for dynamic framed-slotted ALOHA in RFID systems[J].Communications Letters，IEEE，2010，14（1）：60-62.

[6]EPCglobal，EPC.Radio-frequency identity protocols class-1 generation-2 UHF RFID protocol for communications at 860 MHz-960 MHz version1.0.9[S].2005：42-44.

[7]李萌，钱志鸿，张旭，等.基于时隙预测的RFID防碰撞ALOHA算法[J].通信学报，2011，32（12）：43-50.

[8]SCHANTIN A，RULAND C.Retransmission strategies for RFID systems using the EPC protocol[C]//RFID-Technologies and Applications（RFID-TA），2013 IEEE International Conference on.Johor Bahru.Malaysia：IEEE，2013：1-6.

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

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

[11]胡智宏，李凯.基于帧内调整的RFID防碰撞Q值算法的研究[J].制造业自动化，2015，37（4）：19-25.

[12]VOGT H.Efficient object identification with passive RFID tags [C]//Proceedings of the First International Conference on Pervasive Computing.Zurich.Suisse：S pringer-Verlag，Aug. 2002：98-113.

[13]SCHOUTE F C.Dynamic frame length ALOHA[J].Communications，IEEE Transactions on，1983，31（4）：565-568.

[14]CHUNHUI P，ZHENJIANG F，CHUNYAN Y，et al.Research on group-based polling anti-collision algorithm for RFID tag identification[C]//Information Technology and Applications（IFITA）.2010 International Forum on.Kunming：IEEE，2010：185-188.

[15]庞宇，彭琦，林金朝，等.基于分组动态帧时隙的射频识别防碰撞算法[J].物理学报，2013，62（14）：488-495.

RFID anti-collision algorithm based on dynamic Q method

LI Jian-xiong，FENG Xin，SHI Wei-guang，SONG Zhan-wei
（School of Electronics and Information Engineering，Tianjin Polytechnic University，Tianjin 300387，China）

By considering the redundant time and the theoretical maximum system efficiency value，the DQA algorithm is proposed after optimized by grouped and dynamic Q method.Simulation results show that the proposed algorithm，compared with the traditional anti-collision algorithms，obtains a high system efficiency which maintains at 0.368 and shows the superiority in the time slots saving and redundant time reducing.What is more，the algorithm takes EPC-C1G2 protocol into account which contributes to the arithmetic replant.

RFID；DFSA；maximum system efficiency；Q-algorithm；anti-collision algorithm

TP311；TP391.44

A

1671－024X（2015）06－0055－06

10.3969/j.issn.1671-024x.2015.06.012

2015-07-17

国家自然科学基金资助项目（61372011）；天津市应用基础与前沿技术研究计划项目（15JCYBJC16300）

李建雄（1969—），男，副教授，硕士生导师，主要研究方向为射频识别（RFZD系统）及计算电磁学.E-mail：lijianxiong@tjpu.edu.cn