一种基于随机生成树的多维Q选择算法

靳晓芳，黄祥林，朱允

(中国传媒大学 信息工程学院，北京 100024)

1 引言

随着射频识别技术的发展以及应用规模的扩大，读写器需要在短时间内识别多个标签。当识别区域有多个标签到达时，标签信号的混叠造成碰撞。为了避免此情况发生，提高系统识别效率，需要高效的防碰撞技术来解决系统中的标签竞争问题[1]。超高频(Ultra High Frequency，UHF)射频产品适合远距离识别，并且对环境影响较小，成为了目前国际上RFID产品发展的热点[2]。

在UHF段，ISO/IEC 18000-6 Type A和Type B是世界标准组织早先提出的两种技术标准。2005年，全球产品电子代码中心(EPC global)的Class-1 Gen-2[3](Q算法)标准被修改为了ISO/IEC 18000-6 Type C标准[4]。其中，Type A与Type C是基于随机性算法的协议标准；Type B是基于确定性算法的协议标准[5]。

本文提出了一种基于随机生成树的多维Q选择算法，是一种确定性算法与随机性算法的混合算法。本文第二部分针对ISO/IEC 18000-6 Type C(以下简称ISO 18000-6C)标准所应用的Q算法进行了介绍；在第三部分对该创新算法进行介绍；第四部分 对该算法进行了性能仿真；第五部分给出了相关结论。

2 EPC Global Class-1 Gen-2和ISO 18000-6C标准下的防碰撞算法

EPC Global Class-1Gen-2即Q算法，它本质上接近动态帧时隙ALOHA算法，系统内标签的状况如图1所示：

图1 基于Q参数的随机性算法碰撞情况示意图

在Q算法中，参数Q是[0，15]之间的整数。由图1中第一帧可见，各标签通过在[0，2Q-1]内选择不同随机数使自身落在了对应的时隙中，这样的随机选择产生了有限规模的若干空时隙、成功时隙和碰撞时隙。后续帧的情况与之类似。在动态帧时隙ALOHA算法中，系统根据标签规模决定帧长；而在如上的Q算法中，系统根据实时碰撞情况决定帧长和时隙的分配，并可以随时结束当前帧。值得注意的是，Q算法只关注选择0的标签，而落在其他时隙内的标签，无论该时隙内有无碰撞，读写器并不和它们建立通信。

Q值将系统实时碰撞情况反馈到算法前端，通过不断的自我刷新决定当前帧的时隙数分配和退出，从而改变系统的碰撞情况。Q值的参与既是对碰撞的检测，也是对标签规模的一种估计，更是对碰撞约束和控制的过程。

在参数Q的计算中，偶尔一次的碰撞或无标签并不代表Q值过小或过大。且系统每一次调整Q都会造成一定的系统延时与设备损耗[6]。为了避免这种不稳定，降低算法成本，ISO 18000-6C标准提出了一种带有参数C的Q算法流程。C是一个在[0.1，0.5]之间动态调整的小数[7-8]。

另外，标签碰撞情况的改变并不随即反映在Q值上，而是依靠参数C将这个变化缩小保留其趋势，累计在内部数据Qfp上，Qfp是Q值得浮点数表现形式。当Qfp的变化积累到一定程度，其值再向Q弹出。但是，这使得Q值对系统的碰撞情况变得不敏感，时隙数的调整不能很好地适应碰撞情况，系统效率会降低。

带参数C的Q算法流程图如图2：

图2 带参数C的Q算法伪程序流程图

3 基于随机生成树的多维Q选择算法

3.1 算法原理

为了减少Q的调整次数，进一步提高系统效率，本文提出一种改进算法：基于随机生成树的多维Q选择算法(Multiple Dimensional Q-Selection with Random Tree，MDQRT)。该算法引入一个新的参数 ：入口容量(IC：Ingress Capacity)，定义为Q算法的选择维数，可以取任意正整数。。当系统中选择0的标签数大于IC时，系统调整Q值使其有增大的趋势；当系统中选择0的标签数小于等于IC且不为0时，这些标签将离开Q选择周期，被接入后续基于随机生成树的二进制树算法[9]。在该算法中，这些标签重新选择0和1，每次选择0的标签继续选择0和1直至无碰撞识别，而每次选择1的标签挂起等待；当系统中选择0的标签数等于0时，系统调整Q值使其有减小的趋势。显然，Q算法中的IC=1。

MDQRT算法流程图如图3所示：

图3 MDQRT算法流程图

在MDQRT算法中，读写器与标签之间的通信过程如下：

Step1：读写器向若干标签发送一个包含参数Q的Query命令。Q为时隙数参数，每帧共2Q个时隙；

Step2：电子标签在[0，2Q-1]之间选择一个随机数进入对应时隙，标签同时产生一个16位的随机数RN16。当标签所选随机数不为0时，不对读写器响应；仅当标签选择0时，标签才允许对读写器进行响应。

标签响应可能出现以下三种情况：

(1)小于等于IC个标签选择0：读写器将响应的标签接入随机生成二进制树算法，通过不断生成子树遍历各个标签建立通信并读取。对于每个可通信的标签，其RN16到达读写器，读写器返回ACK命令，请求标签的EPC。若成功读取，读写器将标签灭活。Q值不变，进入下一Q选择周期；

(2)无标签选择0：即无标签响应读写器，Q值将通过参数C的调整进行适当缩小，读写器发送Query Adjust命令，开始下一Q选择周期；

(3)大于IC个标签选择0：多于IC个标签选择同一时隙时，超过了入口容量的值，因此会发生碰撞，Q值将通过参数C的调整适当加大，读写器发送Query Adjust命令，开始下一Q选择周期。

3.2 MDQRT算法实例

设在一RFID系统中，系统某一时刻参数状态如下：

1.标签数=200；

2.Q=8；

3.IC=6。

算法识别过程如下：

a.这批标签收到带有参数Q的Query命令，则每一个标签产生一位[0，28-1]内的随机数响应该命令；

b.在这一个随机过程中没有标签选择随机数0，即没有标签能够应答读写器，如图4(a)中所示；

c.系统重新向标签发送Query命令，每一个标签重新产生一位随机数响应Query命令；

d.此次系统中有7个标签以0响应读写器，如图4(b)中所示；

e.由于IC<7，系统再次向标签发送Query命令，则每一个标签再次产生一位随机数响应Query命令；

f.此次系统中有5个标签以0响应读写器，如图4(c)中所示；

(a) (b) (c) 图4 Q标签选择随机数过程

g.由于IC>5，这5个标签被接入二进制树流程；

h.基于随机生成树的二进制树流程中，标签随机选择0或1。其中2个选1的标签被挂起，3个选0的标签进入下一分支；

i.这3个标签继续选择0与1。其中1个选1的标签挂起，2个选0的标签进入下一分支；

j.这2个标签继续选择0与1。其中1个选1的标签挂起，1个选0的标签被读取；上述过程如图5所示：

图5 随机树的生成与标签的读取

k.被挂起的标签重复类似f，g的步骤，直至剩余所有标签均被读取。

由算法实例可以看出，在Q选择过程中，若选择0的标签数量小于等于IC，系统将以随机生成树的形式快速将其识别，避免了参数Q的过多调整，同时也提高了系统效率。

4 MDQRT算法仿真与性能分析

参数C的提出，使得Q算法在Q参数的调整频率上大大降低，降低了设备的损耗。而在算法的效率上，却并未显出优势。本文将在MATLAB环境下对Q算法、带有参数C的改进算法及MDQRT算法进行仿真，对其性能进行比较和分析。

4.1 Q参数的改变情况

在RFID系统中，Q值每调整一次，标签的动态功耗量便会增加约0.8μw。因而在标签较多的情况下，减少Q参数改变的频率，是优化系统性能的重要目标之一。图6是在一次识别过程中，Q算法、带有参数C的Q算法及MDQRT算法中Q值改变情况的仿真结果：

图6 三种算法Q值改变情况仿真

由图6可看出，MDQRT算法在参数Q的波动上均明显优于其他两种算法。经过100次的独立重复的识别过程，统计结果如图7所示：

(a) (b)图7 通信周期与Q改变次数积累图

由图7(a)可以看出，三种算法中的参数Q改变的累积过程各聚拢为一簇直线；(b)图是(a)图的平均效果。首先可以看出，Q算法与带有参数C的Q算法相比，前者效率较高但Q值改变过于频繁；后者Q值改变次数减少但是其效率降低。其次，MDQRT相较于另外两种算法，参数Q的改变次数非常少，而所消耗通信周期也非常短。同时，由各直线簇的离散程度可看出各算法的稳定性差异，MDQRT的直线簇相比其他两种算法的更加集中，反映出其更加优越的稳定性。

4.2 系统效率情况

MDQRT算法的效率如图8所示：

(a) (b)图8 三种算法系统效率图

图8(a)为三种算法的实时系统效率图。对其进行平滑后，得出如图8(b)所示的平滑效率曲线。显然，MDQRT在系统效率上远远领先与带有参数C的Q算法和EPC C1G2标准下基于Q选择的防碰撞算法。本文通过仿真计算得出参数为IC=6时的MDQRT算法系统效率值：

(1)

从图中还可知，EPC global C1G2协议下的Q算法效率约为0.41，ISO 18000-6C协议下带有参数C的Q算法效率约为0.35。

4.3 IC取值分析

IC的取值影响标签的识别效率，对此本文进行了仿真，如图9所示：

图9 入口容量IC取值与系统效率关系图

图中系统效率是不同规模标签下效率的平均值。随着标签数量的改变，IC的取值并不呈现单调递增或递减的情况，而是在IC=10的时候，系统效率取得极值：

ηMDQRT≈0.5195

(2)

5 结论

防碰撞技术已成为RFID系统大规模应用的关键技术之一，本文在ISO18000-6C标准防碰撞算法的基础上，结合二进制树确定性算法，提出了一种带有入口容量的多维Q选择算法。仿真结果显示，该算法相比现有的Q算法及其改进算法，有效减少了设备的损耗，提高了系统效率，性能上更具稳定性。今后，在Q选择与确定性算法的对接上，将实现更深入的讨论和研究。

[1]童乔玲.RFID阅读器芯片设计及通讯算法研究[D].华中科技大学，2013.

[2]马倩，石良平，周立宏.ISO18000_6C标准的防碰撞算法研究[J].计算机应用，2008，28(12)：341-343.

[3]EPC global Inc.EPCTM radio-frequency identity protocols class-1 gen-2 UHF RFID protocol for communications at 860MHz-960 MHz Version 1.2.0[S].Lawrenceville：EPC global Inc，2008.

[4]Huiyang Wang，Xiangdong You，Yinghua Cui.A Stack-Like Optimal Q-Algorithm For The ISO 18000-6C in RFID Systems[C].Proceedings of IC-NIDC，2012：164-168.

[5]Wong C P，Quanyuan Feng.Grouping Based Bit-Slot ALOHA Protocol for Tag Anti-Collision in RFID Systems[J].IEEE Communications Letters，2007，111(12).

[6]韩振伟，宋克非.射频识别防碰撞Q算法的分析与改进[J].计算机工程与设计，2011，32(7)：2314-2318.

[7]王晓东，戎蒙恬.基于Q-选择的RFID防碰撞算法的研究[J].计算机仿真，2008，26(5)：124-126.

[8]Muhammad Umer Farooq，Muddassar Asif，Syed Waqar Nabi，M Adnan Qureshi.Optimal Adjustment Parameters for EPC Global RFID Anti-Collision Q-Algorithm in Different Traffic Scenarios[C].10th International Conference on Frontiers of Information Technology，2012.

[9]李瑾.无线射频识别(RFID)防碰撞算法的研究和仿真[D].北京交通大学，2007：30-53.