基于成功时隙的自适应Q值防碰撞算法

徐春艳，陈科明，孙智勇，严迪科，洪 慧

（杭州电子科技大学电子信息学院，杭州310018）

基于成功时隙的自适应Q值防碰撞算法

徐春艳，陈科明，孙智勇，严迪科，洪 慧

（杭州电子科技大学电子信息学院，杭州310018）

为提高射频识别系统中动态帧时隙ALOHA算法的识别效率，提出一种快速收敛的自适应Q值防碰撞算法。基于上一帧成功识别标签的时隙数对Q值进行不同步长的调整，使其以自适应方式快速收敛到最优Q值的情况下进行工作，加快系统的标签识别速度，并使实际系统吞吐率快速逼近于理想值，保证系统的高吞吐率。仿真结果表明，在待识别标签数为5 000的情况下，该算法的系统吞吐率比泊松估计算法提高了8.19%，且随着标签数的增加，其系统吞吐率可稳定在33%以上。

射频识别；防碰撞；ALOHA算法；快速收敛；成功时隙

1 概述

射频识别［1］（Radio Frequency Identification，RFID）技术是一项非接触式的自动识别技术［2］，通过无线射频方式获取物体存储在标签内的相关数据，并对物体加以识别，也可修改相关数据，具有可读写、识别距离远、安全性好、实时性强等特点，广泛应用于工业自动化、商业自动化、物流、防伪等领域，成为当前物流网技术研究的热点之一。

超高频RFID系统由阅读器和标签组成［1］。当阅读器向标签发出一个请求信号时，它会提供能量给无源标签。但是由于标签响应区比阅读器的识别区要小很多，在处于多张标签响应的情况下，多张标签反射回的信号会产生碰撞导致阅读器不能正确接收到标签的响应信息，从而降低系统识别效率。标签防碰撞算法可以降低系统标签之间产生碰撞的概率，提高系统识别效率，为此RFID系统中防碰撞算法的优劣很大程度上决定了系统性能。

目前学术界中标签防碰撞算法的研究主要包括基于ALOHA协议的算法、基于树协议的算法和基于计数器协议的算法［3］。而基于ALOHA协议的算法因实现简单被大多RFID系统采用，例如目前全球广泛认可的EPC Gen2标准［4-5］就是采用该算法。然而学术界大多针对动态帧时隙ALOHA算法［6-7］的防碰撞问题的研究（包括最小值估计算法、泊松估计算法、空间点逼近估计算法等标签估计算法［8］）都是根据上一帧中产生的碰撞时隙数来估计未被识别的电子标签数［9-10］，然后据此选择最优的下一帧长度2Q（也即时隙的个数），提高系统吞吐率。但是在实际系统中，无法分辨出未成功识别的时隙是空闲时隙还是碰撞时隙，碰撞时隙数无法准确统计。为此，本文提出一种新的自适应Q值防碰撞算法，该算法只考虑上一帧中的成功时隙数，得到当前系统吞吐率。对实际系统吞吐率与理论系统吞吐率进行比较，将Q值分为是否达到理想值的2种情况，并对2种情况下Q值的调整方式进行分析。采用不同的步长ΔQ方式来调整Q值，使系统Q值以最快速度收敛到最优值，保证系统始终处于最优Q值的状态下工作，提高系统工作效率。

2 动态帧时隙ALOHA算法

超高频阅读器的EPC Gen2协议中采用动态帧时隙算法，其中，帧长L=2Q（Q∈［0，15］，且Q为整数）。算法通过调整Q值确定下一帧的帧长度，该算法实现流程如图1所示。

图1 动态帧时隙ALOHA算法流程

动态帧时隙ALOHA算法实现步骤如下［8］：

步骤1 在开始盘点存储标签时，确定Q初值，也即确定初始帧长度L（L=2Q），阅读器发送Query指令（包含Q参数）给标签群。标签接收到Query指令，所有未识别标签在（0，2Q-1）范围内随机选择一个时隙，并将其存入时隙计数器，进入步骤2。

步骤2 阅读器发送QueryRep指令，所有响应标签的时隙计数器减1。当标签时隙计数器为0时，产生一个16位的随机数RN16，并将RN16发送给阅读器。若在同一个时隙中只有一个标签响应，阅读器成功接收RN16，进入步骤3。若在同一个时隙中多种标签同时响应，则标签信息产生碰撞，阅读器无法识别到正确的RN16，识别不成功，进入步骤4。

步骤3 阅读器会发送ACK指令，标签将EPC传递给阅读器，标签识别成功。

步骤4 一帧结束，系统有标签产生碰撞。阅读器发送QueryAdjust指令给标签调整Q值，重新查询标签，重复上述工作，直到所有标签识别为止。

3 快速收敛的自适应Q值防碰撞算法

3.1 定义与推论

由于动态帧时隙算法是以包含多个时隙的帧为基础，而且本文算法思想是依据系统吞吐率函数进行Q值调整，需要分析一帧中成功发送数据的时隙数，以计算最大吞吐率值，因此给出如下定义和推论［9］。

定义1 令同一个时隙内识别的标签数R服从标签总数为n、概率为1/L（L为帧长度，L=2Q（Q∈［0，15］，且Q为整数））的二项分布，即R～（n，1/L），从而同一时隙中出现标签数的概率表达式为［11-13］：

推论 根据定义1，同一时隙成功识别标签（识别到一张标签）和未成功识别标签（包括未识别到标签和多张标签产生碰撞）的概率为：

定义2 超高频阅读器的系统吞吐率为一帧时长内成功识别到标签的时隙数与该帧的时隙数的比值，系统吞吐率可以用S表示，一帧中的成功时隙数可以用K表示，帧长用L表示。

根据定义1和推论可知，系统吞吐率表达式为：

根据式（5）可知，最大系统吞吐率Smax关于帧长度L的对应关系如图2所示。即同一时隙成功识别的效率S∈［1，0.367 9］，且Q≥3后系统吞吐率稳定在0.367 9左右。本文定义0.367 9为系统吞吐率的理想值。

图2 Q值与系统吞吐率的对应关系

根据上述定义和推论，系统可依据S值判断Q值是否设置合理。若S值大于0.367 9，说明系统设置的Q值合理，Q值不需要调整。但若是S值远离0.367 9，则说明帧长L偏离标签数n，需要调整Q值，使帧长L接近于待检标签数。在传统帧时隙算法中，每个QueryAd just命令只能对Q值进行加1或是减1，调整Q值则收敛速度过慢。但若将S进行分组处理，采用不同的步长ΔQ来调整Q值，就可加快Q值的收敛速度，使帧长L快速接近于待检标签数n，从而提高系统吞吐率S。

3.2 自适应Q值调整方法

由于提高系统吞吐率可以提升系统标签识别效率，因此本文算法基于成功时隙，根据当前实际系统吞吐率与理想系统吞吐率的比较，对Q值进行不同步长的调整，使实际系统吞吐率快速接近理想值，之后继续通过Q值的调整，保证系统的高吞吐率，加快系统的标签识别速度。本文算法主要分为2个部分：逼近理想系统吞吐率的快速Q值调整方法和维持高系统吞吐率的自适应Q调整方法。

3.2.1 逼近理想系统吞吐率的快速Q值调整方法

当Q值取不同固定值时，根据式（4）得到待识别标签数与系统吞吐率的关系曲线如图3所示。可以看出，标签数分别为8，16，32时，对应的Q值为3，4，5的曲线都达到最高系统吞吐率0.368。当标签数大于帧长（2Q）时，系统吞吐率函数为单调递减函数，因此当待识别标签数大于帧长（2Q）时，增大Q值可提高系统吞吐率。

图3 不同帧长（2Q）下待识别标签数对应的系统吞吐率

假设当前系统中的帧长L=2Q小于标签数n，根据定义2、式（4）和图3可得，在L＜n时系统吞吐率函数关于标签数是单调递减的函数，因此当标签数n∈［2Q，2Q+ΔQ］时，系统吞吐率S∈［S2，S1］（S1为标签数n=2Q时的系统吞吐率，S2为标签数n=2Q+ΔQ时的系统吞吐率），为此：

（1）当ΔQ=1、n∈［2Q，2Q+1］时，系统吞吐率S∈［S2，S1］，S1，S2为：

根据式（6），当帧长不同时，系统吞吐率S1，S2如图2、图4所示。从图2、图4中分别可得S∈［0.367 9，1］，S2∈［0，0.270 9］，且当Q≥3后系统吞率S1，S2分别稳定在极限值0.367 9和0.270 9左右，则当标签数n∈［2Q，2Q+1］时，系统吞吐率S∈［S2min，S1max］，即S∈［0，1］。为此，结合式（5）系统达到理想状况的条件下和ΔQ=1的情况，当标签n∈（2Q，2Q+1］时，系统吞吐率S∈［0，0.367 9］。

图4 ΔQ=1时的系统吞吐率S2

（2）当ΔQ=2、n∈［2Q，2Q+2］时，系统吞吐率S∈［S2，S1］，S1，S2为：

根据式（7），当帧长不同时，系统吞吐率S1，S2如图2、图5所示。从图2、图5中可得S∈［0.367 9，1］，S2∈［0，0.073 3］，且当Q≥3后系统吞率S1，S2分别稳定在极限值0.367 9和0.073 3左右，则当标签数n∈［2Q，2Q+2］时，系统吞吐率S∈［S2min，S1max］，即S∈［0，1］。为此，结合ΔQ=1、ΔQ=2的情况，当标签n∈（2Q+1，2Q+2］时，系统吞吐率S∈［0，0.270 9）。

图5 ΔQ=2时的系统吞吐率S2

（3）当ΔQ=3时，n∈［2Q，2Q+3］时，系统吞吐率S∈［S1，S2］，S1，S2为：

根据式（8），当帧长不同时，系统吞吐率S1，S2如图2、图6所示。

图6 ΔQ=3时的系统吞吐率S2

从图2、图6中分别可得S∈［0.367 9，1］，S2∈［0，0.002 7］。则当标签数n=［2Q，2Q+3］时，系统吞吐率S∈［S2min，S1max］，即S∈［0，1］。为此，结合ΔQ=2和ΔQ=3的情况，当标签n∈（2Q+2，2Q+3］时，系统吞吐率S∈［0，0.073 3）。

综上所述，同理当ΔQ≥4时，标签数n∈（2Q+3，2Q+ΔQ］时，系统吞吐率S∈［0，0.002 7），此时系统吞吐率很低近似为0，为此不做吞吐率分组考虑。因此，结合系统Q达到理想值情况下的系统吞吐率S∈［0.367 9，1］，将系统吞吐率分为S∈［0.367 9，1］、S∈［0.270 9，0.367 9）、S∈［0.073 3，0.270 9）、S∈［0，0.073 3）4组。为此，系统吞吐率临界参考值为0.367 9，0.270 9，0.073 3，以S0，S1，S2表示，系统吞吐率未达到理想值时，ΔQ可取值为1，2，3，系统吞吐率达到理想值时，结合3.2.2节ΔQ的调整值ΔQ0，Q值调整方式与系统吞吐率对应关系如表1所示。

表1 Q值调整方式与系统吞吐率的关系1

此时未考虑标签数在步长ΔQ为1范围内的标签其理想Q值也将处于Q～Q+1之间波动。为此考虑系统上述情况，结合标签数大于时隙数时系统吞吐率的单调递减特性，对系统效率的临界参考值S0，S1，S2重新处理，表达式为：

其中，i=0，1，2。由式（9）和表3可得，吞吐率分组临界值S0，S1，S2调整为0.319 4，0.172 1，0.036 7。为此，重新调整后快速收敛自适应Q算法的Q值调整方式与系统吞吐率的对应关系如表2所示。

表2 Q值调整方式与系统效率的关系2

3.2.2 保证高系统吞吐率的自适应Q值调整方法

当系统吞吐率达到理想临界值后，此时系统具有最优Q值，系统可以根据成功时隙数与系统吞吐率估算出未成功识别标签数，其未成功识别标签数n的表达式为：

为此，在吞吐率达到理想临界值后自适应Q值采用ΔQ0的方式调整步长ΔQ。

3.3 算法流程

结合上述系统吞吐率、ΔQ的调整原则，本文提出的自适应Q算法流程（见图7），具体步骤如下：

步骤1 设定Q的初值为0，发送Query命令，获取一帧中的成功时隙数，得到系统吞吐率S。

步骤2 将系统吞吐率S与S0进行比较。若系统吞吐率小于S0，则将S与S1，S2作比较，调整相应的Q值，重复步骤2。若系统吞吐率大于等于S0值，则跳到步骤3。

步骤3 若系统吞吐率大于等于S0值，说明系统处于最优Q值状态下工作，估算未识别的标签数n，由round（lb n）获取下一帧Q值。将当前的Q值与上一帧的Q值作比较得到步长ΔQ，调整Q值。若剩余标签数为0，则标签识别结束，否则重复步骤2、步骤3。为此，直到所有标签识别完，系统都处于最优Q值状态下识别标签。

由式（10）可确定系统下一步的调整步长，其步长获得的表达式为：

图7 本文自适应Q值防碰撞算法流程

4 仿真结果与分析

本文采用Matlab7.8.0对以下3种不同情况下的最小值估计算法、泊松估计算法和快速收敛Q算法性能进行对比分析。

（1）在5 000张待识别标签和Q初值为0的条件下，3种算法使Q值达到理想情况所需调整次数如图8所示。

图8 不同调整次数时3种算法的吞吐率比较

从图8可看出，最小值估计算法经过11次Q值调整使系统吞吐率达到21.25%后无法再次提高，系统性能明显比泊松估计算法和本文算法差。当系统到达理想Q值（Q=12）时，系统达到最大吞吐率36.02%，该过程本文算法只调整了6次Q值，而泊松估计算法调整了12次Q值，收敛速度远快于另外2种算法。

（2）在5 000张待识别标签和不同Q初值情况下，3种算法的系统吞吐率如表3（吞吐率提高百分比为本文算法吞吐率与泊松算法吞吐率之比）、图9所示。

表3 5 000张待识别标签情况下不同Q初值的吞吐率

图9 不同Q初值时3种算法的系统吞吐率比较

从表3、图9可以看出，当Q初值小于10时，快速收敛自适应Q算法系统吞吐率相比泊松估计算法提高了5.67%～15.62%。当时隙数小于待识别标签数时，快速收敛自适应Q算法系统吞吐率稳定在32.25%～36.51%之间，相比于泊松估计算法和最小值估计算法的30.28%～36.85%和27.90%～35.67%，系统稳定性具有明显的提高。

（3）在Q初值为0、最大标签数为5 000张的情况下，3种算法的系统吞吐率如表4、图10所示。

表4 Q初值为0情况下不同标签数的吞吐率提高比

图10 不同标签数时3种算法的系统吞吐率比较

从表4、图10可以看出，最小值估计算法系统吞吐率最低、性能最差。本文算法相比泊松估计算法的提高了8.19%以上，而且系统吞吐率稳定在33%左右，接近理论值36.79%，性能稳定，时隙利用率高。

5 结束语

本文为提高超高频阅读器系统的识别效率和实用性，提出基于成功时隙的快速收敛自适应Q值防碰撞算法。该算法通过采用合理的Q调整值使系统吞吐率快速逼近理想值，以提高系统吞吐率。该算法与传统Q算法相比，不仅提高了系统吞吐量，而且随着标签数的增加，系统吞吐率能够稳定在33%以上。但是现有算法的Q值更新是基于前一次成功的标签识别，因此可进一步优化算法，使得算法能够参考前多帧成功识别标签的经验值获得更加合理的Q值。

［1］ 黄玉兰.物联网射频识别（RFID）核心技术详解［M］.北京：人民邮电出版社，2010.

［2］ 张学军，王 娟，王锁萍.基于标签识别码分组的连续识别防碰撞算法研究［J］.电子与信息学报，2011，33（5）：1159-1165.

［3］ 张 彦，陈积明.RFID与传感器网络：架构、协议、安全与集成［M］.北京：机械工业出版社，2012.

［4］ EPC Global.ISO 18000-6C-2004 EPC Radio-Frequency Identity Protocols Class-1 Generation-2 UHF RFID Protocol for Communications at 860 MHz-960 MHz，Version：1.0.9［S］.2004.

［5］ Zhu Lei.The Optim al Reading Strategy for EPC Gen-2 RFID Anti-Collision System s［J］.IEEE Transactions on Communications，2010，58（9）：2725-2733.

［6］ 李青青，刘洪武，张小林.一种基于不等长时隙的射频识别防碰撞算法［J］.电子与信息学报，2011，33（11）：2628-2633.

［7］ Maguire Y，Pappu R.An Optimal Q-Algorithm for the ISO 18000-6C RFID Protocol［J］.IEEE Transactions on Automation Science and Engineering，2009，6（1）：16-24.

［8］ 江 建.RFID中多标签防碰撞技术的研究［D］.成都：电子科技大学，2009.

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

［10］ 轩秀巍.超高频射频识别系统的关键技术研究［D］.天津：天津大学，2012.

［11］ Peng Qi，Zhang Chun，Wang Zhihua.A Multi-tag Emulator for the UHF RFID System［J］.IEEE Transactions on Instrumentation and Measurement，2014，63（6）：1461-1495.

［12］ Xie Lei，Yin Yafen，Vasilakos A，et al.Managing RFID Data：Challenges，Opportunities and Solutions［J］.IEEE Communications Surveys&Tutorials，2014，16（3）：1294-1311.

［13］ Zhu Lei，Yum T S P.Optimal Framed Aloha Based Anticollision Algorithms for RFID Systems［J］.IEEE Transactions on Communications，2010，58（12）：3583-3592.

编辑 陆燕菲

AdaPtive Q Value Anti-collision Algorithm Based on Successful Tim e Slot

XU Chunyan，CHEN Kem ing，SUN Zhiyong，YAN Dike，HONG Hui
（Institute of Electronic Information，Hangzhou Dianzi University，Hangzhou 310018，China）

In order to im prove the recognition efficiency of dynamic framed slot ALOHA algorithm in Radio Frequency Identification（RFID）system，this paper proposes a fast convergence amd adaptive Q value anti-collision algorithm.To make the system throughput quickly close to theoretical value，the actual system throughput based on the singleton slots is com pared with the theoretical system throughput to adjust Q value by the empirical value.Then，Q value is adaptively adjusted to ensure high system throughput and speed up tags identification.Simulation results show that the throughput of proposed algorithm is increased by more than 8.19%com pared with Poisson estimation algorithm when the number of identification tag is 5 000，and it can stabilize the throughput above 33%With the increase of tag number.

Radio Frequency Identification（RFID）；anti-collision；ALOHA algorithm；fast convergence；successful time slot

徐春艳，陈科明，孙智勇，等.基于成功时隙的自适应Q值防碰撞算法［J］.计算机工程，2015，41（9）：7-12.

英文引用格式：Xu Chunyan，Chen Kem ing，Sun Zhiyong，et al.Adaptive Q Value Anti-collision Algorithm Based on Successful Time Slot［J］.Computer Engineering，2015，41（9）：7-12.

1000-3428（2015）09-0007-06

A

TN911

10.3969/j.issn.1000-3428.2015.09.002

国家自然科学基金资助项目（61107025）；浙江省自然科学基金资助项目（LY 13F040004）。

徐春艳（1989-），女，硕士研究生，主研方向：物联网技术，射频识别；陈科明，副教授；孙智勇、严迪科，硕士研究生；洪 慧，副教授。

2014-09-02

2014-10-15 E-m ail：xcy198903@163.com