基于EPC-G2协议的分组访问控制Q算法

Q-Algorithm Utilizing Access Control by Group Based on EPC-G2 Protocol

摘要: 根据EPC-Gen2协议中的标准Q算法以及现有的改进Q算法，提出一种采用分组访问控制方法来提高RFID系统俘获效应的Q_gac算法。为了提高系统的俘获效应，该算法在执行Q算法之前根据标签接收到的信号强度将所有标签分组，然后根据信号强度差异选定一对最有可能产生俘获效应的分组进行识别。在Matlab平台上的仿真结果表明，Q_gac算法能有效地提高RFID系统的俘获效应，减少识别冲突的概率，从而进一步提高了RFID系统的识别性能。

Abstract: This paper presents a novel anti-collision algorithm called Q_gac-Algorithm that drastically enhances the capture-effect in RFID system by utilizing access control by group, according to the standard and improved Q-Algorithm based on EPC-Gen2 Protocol. In order to enhance the capture-effect, Q_gac-Algorithm divides all tags into multiple groups depending on received signal strength at the beginning of executing. Then, according to the difference of signal intensity, a pair of groups most likely to produce capture effect is selected for recognition. Numerical simulation results with Matlab platform represent that Q_gac-Algorithm can effectively improve the capture-effect in RFID system, and greatly reduce collision probability, outperforming the other existing schemes significantly.

1. 引言

物联网中射频识别(Radio Frequency Identification, RFID)是一种非接触识别技术，它通过无线信道获取物体的相关数据从而自动识别该物体 [1] 。该识别过程无需人参与，所以RFID能够被广泛运用在如物流系统、生产管理与控制、防伪与安全控制等众多领域当中。然而，RFID系统在并发识别多个电子标签时所产生的冲突问题始终是影响系统性能的关键问题之一。

为了解决这一问题，各种防冲突方案纷纷出现。目前解决阅读器识别多个标签时的冲突问题的算法大致分为两类：ALOHA时隙算法和二叉树算法 [2] [3] 。其中，ALOHA时隙算法由于简单、容易实施而成为目前的主流算法。ALOHA时隙算法中目前用得较多的是EPC-Gen2协议 [4] 中提出的Q算法，提高了系统的识别效率，但是由于进行数据传输所需的时隙数是固定的，不能随意进行动态调整，当标签数量多时，时隙数不够用，导致时隙内标签的碰撞率急剧上升，也急剧的降低了系统的识别效率和信道利用率；当标签数量少时，如有的时隙内没有标签在传输数据，则会产生许多空时隙，造成时隙的浪费。

文献 [5] 中的Q_ext算法对这些问题进行了很好的研究，但只是从理论上分析了俘获概率α对识别性能的影响，并没有提出如何增大RFID系统俘获效应的俘获概率的有效方案。而本文的Q_gac算法提出了一种采用分组访问控制的方法解决此问题，有效地引进并增强了RFID系统的俘获效应，进一步提高了RFID系统的识别性能。

2. EPC-Gen2标准Q算法简介

在每个识别周期，读写器首先通过Query指令开启新的盘存(inventory)周期，指令中含槽计数器参数Q，用于控制标签在该盘存周期发出响应的概率。参与识别的标签应在(0, 2Q 一1) (标准附录推荐的Q初始值为4)范围内产生一个随机数，并将其载入槽计数器(Slot Counter)中，每过一个时隙，随机数即减1，当标签随机数为零时进入应答状态并立即响应。

在识别过程中，参数Q决定标签产生随机数的范围，以及读写器是否改变识别时隙大小以适应标签数的变化，因此直接影响了系统的识别性能。在标准附录推荐的算法中，Q值由一个参数C来决定。其中，Q_fp为Q的浮点表示，读写器对Q四舍五入取整后作为Query命令中的Q值，C的典型值为0.1 < C < 0.5 [4] ，Q值越大C值越小。然后，该算法会根据不同类型的标签响应——成功、冲突、空闲，逐一处理每个时隙。若没有标签响应，则为空闲时隙，此时Q_fp的值减去C值；若有两个或两个以上标签同时进行响应，即发生冲突时，Q_fp的值加上C值；而当其只有一个标签响应时，Q_fp保持不变。然后，通过对Q_fp取整得到Q的值。最后，根据当前的Q值更新帧尺寸的大小。其流程如图1所示。

Figure 1. Flow chart of Q algorithm for EPC-Gen2 protocol

图1. EPC-Gen2协议Q算法流程图

该算法相对于传统的纯ALOHA、帧时隙ALOHA (FSA, DFSA)算法而言，在识别过程中，参数Q决定了标签产生的随机数的范围，参数C决定了是否改变帧长以适应标签数目的变化，从而直接影响系统的性能。该算法并不消耗大量的运算去估算待识别标签的数量，只是去统计碰撞时隙、空闲时隙的次数。当接入信道连续的发生1/C次碰撞或空闲时，Q值进行加1或减1操作。因此，大大提高了RFID的识别性能 [3] 。但它也存在如下问题：1) 俘获效应问题，若没有考虑，导致在计算时隙冲突率和成功率时，使得理论值与实际值相差较大；2) 参数C的取值问题，由于没有分开考虑导致时隙冲突和时隙空闲的发生概率及解码时间不同。文献 [5] 中Q⁺⁻算法针对时隙冲突和时隙空闲引进了两个新的参数C_i和C_c，并且通过仿真发现，RFID系统的识别效率与C_i/C_c的值，以及C_i、C_c的值有关。但该算法并没有把俘获效应考虑在内，因此得到的结果并不十分准确。文献 [6] 针对此问题提出了改进的Q_ext算法，通过引进俘获效应，对俘获概率对识别速率以及吞吐率的影响作了详细的研究与分析。但该算法只是提出了俘获效应的俘获概率对RFID系统识别性能的影响，没有给出如何增大俘获效应的俘获概率的方法。针对此问题我们展开研究，得到了下面的改进的Q_gac算法。

3. Q_gac算法描述与分析

3.1. 俘获效应

俘获效应是在标签的识别过程中产生的，它是指标签在答复阅读器请求命令时，由于反射信号功率不同，存在弱功率信号被强功率信号覆盖的标签漏读现象，严重影响系统识别效率。

3.2. 算法描述与分析

参照文献 [7] ，我们先假设如图2这样的场景。在这个场景中，单个阅读器位于整个区域的中心，识别其覆盖范围内的所有标签，而此时所有标签均已按接收信号强度差异被划分到A、B、C三组。其中A

Figure 2. Implementation scenario map of Q_gac algorithms based on packet access control

图2. 基于分组访问控制的Q_gac算法实施场景图

组的接收信号最强，B组其次，最后是C组。然后我们假定当同一组中的多个标签同时响应阅读器，或者相邻的两组A和B或者B和C中的多个标签同时响应阅读器时都会发生碰撞，而只有当A中的一个标签和C中一个或多个标签同时响应时才会发生俘获效应。其中当A和C各有一个标签同时响应阅读器时，俘获概率 $\alpha =1$ ；当A中有一个标签，而C中有多个标签同时响应阅读器时，俘获概率 $\alpha <1$ 。在Q_gac算法中，我们用N来表示标签的总数量，Q表示帧时隙尺寸的指数，k表示某个时隙的标签数量， ${\alpha }_{k+1}$ 表示A中的1个标签和C中k个标签同时响应时，识别成功的概率。N_A、N_B、N_C分别用来表示A、B、C三组的标签数量，于是就有 $N=N_A+N_B+N_C$ 。我们用如下三个式子来分别计算一个时隙冲突、成功、空闲的概率：

$p_{succ}^{N,Q}=\left(\begin{array}{c}N\\ k\end{array}\right)\frac{1}{2^{Qk}}{\left(1-\frac{1}{2^Q}\right)}^{N-k}+p_{cap}\left(k=1\right)$ (1)

$p_{idle}^{N,Q}=\left(\begin{array}{c}N\\ 0\end{array}\right){\left(1-\frac{1}{2^Q}\right)}^N\left(k=0\right)$ (2)

$p_{coll}^{N,Q}=1-p_{succ}^{N,Q}-p_{idle}^{N,Q}\left(k\ge 2\right)$ (3)

其中P_cap表示发生俘获效应识别成功的概率，

$\begin{array}{c}{p}_{cap}=B\left(N_A,1,1/N\right)B\left(N_C,1,1/N\right)+B\left(N_A,1,1/N\right)B\left(N_C,k,1/N\right){\alpha }_k\\ =\frac{N_A}{N}{\left(1-\frac{1}{N}\right)}^{N_A-1}\frac{N_C}{N}{\left(1-\frac{1}{N}\right)}^{N_C-1}+\frac{N_A}{N}{\left(1-\frac{1}{N}\right)}^{N_A-1}\left(\begin{array}{c}{N}_C\\ k\end{array}\right)\frac{1}{N^k}{\left(1-\frac{1}{N}\right)}^{N_C-k}{\alpha }_{k+1}\left(k>1\right)\end{array}$ (4)

我们用 $\chi ,\beta ,\gamma$ 来分别表示 $N_A/N,N_B/N,N_C/N$ ，当 $N\to \infty$ ，

$p_{cap}=\chi {\text{e}}^{-\chi }\gamma {\text{e}}^{-\gamma }+\chi {\text{e}}^{-\chi }\left(\begin{array}{c}{N}_c\\ k\end{array}\right)\frac{1}{N^k}{\left(1-\frac{1}{N}\right)}^{N_c-k}{\alpha }_{k+1}\left(k>1\right)$ (5)

其中e为自然对数的底， $\chi +\beta +\gamma =1$ ，并且 $0\le \chi ,\beta ,\gamma \le 1$ 。

另外，在文献 [8] 中提到了平均俘获概率 $\alpha$ ，并且有如下等式：

$\alpha ={\displaystyle \underset{i=2}{\overset{N}{\sum }}{p}_{cap}\left(i\right)p_{col}\left(i\right)}$ (6)

其中 $p_{cap}\left(i\right)$ 表示当有i个标签冲突时，发生俘获效应成功识别的概率。而 $p_{col}\left(i\right)$ 表示某个时隙有i个标签冲突的概率，N为实际标签数量。根据文献 [8] 中的结论得知，当 $i>2$ 时， $p_{cap}\left(i\right)$ 和 $p_{col}\left(i\right)$ 的值都非常小，所以当 $k>1$ ， ${\alpha }_{k+1}\approx 0$ 。由此可得，(5)式可以化简成如下形式：

$p_{cap}=\chi {\text{e}}^{-\chi }\gamma {\text{e}}^{-\gamma }$ (7)

对于(7)式，我们可以求得它的最大值：

$\max p_{cap}=\frac{1}{4\text{e}},N\to \infty$ (8)

此时 $\chi =1/2,\beta =0,\gamma =1/2$ 。(8)式说明俘获效应最大值可达1/4e，也就是说按照我们的方案引进了俘获效应之后时隙ALOHA算法最大吞吐率将提高25%。(8)式同样说明当B组标签数量为0，而A组和C组标签数量相等时，俘获效应将达到最大值。

由文献 [9] [10] 得知，在最优条件下，有如下等式成立：

(9)

其中 $T_{coll}$ 、 $T_{idle}$ 分别表示时隙冲突与时隙空闲时的解码时延，然后我们由文献 [5] ，我们可以得到如下结论：

1、当待识别标签数量N已知时，

$C_c=-0.0491\ln \left(N\right)+0.534$ (10)

$C_i=1.98\times \left(\text{e}-2\right)\left(1-p_{cap}\right)C_c$ (11)

2、当待识别标签数量N未知时，

$C_c$ 从(0.1，0.5)中任取一值，

$C_i=1.98\times \left(\text{e}-2\right)\left(1-p_{cap}\right)C_c$ (12)

改进后的Q算法亦即Q_gac算法流程如图3所示。

4. Q_gac算法的仿真与分析

在Matlab平台下，我们在考虑了俘获效应的情况下对EPC-G2协议中的传统Q算法，文献 [6] 中的Q⁺算法，文献 [11] 中的快速Q算法，以及本文提出的基于分组访问控制的Q_gac算法进行了仿真实验。在该过程中，我们假设待识别标签数T为1000，且这些标签被划分成A、B、C三组。其中，只有A组和C组之间存在俘获效应，然后将B组标签数占总标签数的比例 $\beta$ 分别取值为0.7、0.5、0.3，对于 $\beta$ 的每一种取值我们将以上4种算法反复运行100次，对得到结果求平均值。其中，4种算法( $\beta =0.7$ )识别1000标签的识别效率对比如图4所示，4种算法()识别1000标签的识别效率对比如图5所示，4种算法( $\beta =0.3$ )识别1000标签的识别效率对比如图6所示。

观察图4、图5、图6这3个仿真结果图可以得出以下结论：

1) 在包含俘获效应的环境下，传统Q算法、Q⁺算法、快速Q算法以及本文提出的Q_gac算法的识别效率均比没有俘获效应的情况下要高。在没有俘获效应的情况下，时隙ALOHA算法的极限效率为1/e，亦即约为0.368，从上面的仿真结果图可以看出，4种算法在 $\chi =0$ 时，即A组标签数为0时，也就是不会和C组发生俘获效应的情况下，它们的识别效率几乎相同，均约为0.34，接近最优值。但当A组标签数由0逐渐增加时，也就是和C组发生俘获效应的俘获概率增加时，它们的识别效率也逐渐提高，并很快超过了没有俘获效应时的时隙ALOHA算法的极限效率0.368这一值。这充分证实了RFID系统中的俘获效应可以大大提高系统的识别效率；

Figure 3. Q_gac algorithm flow chart

图3. Q_gac算法流程图

Figure 4. Comparison of recognition efficiency of four (β = 0.7) algorithms for 1000 labels recognition

图4. 4种算法(β = 0.7)识别1000标签的识别效率对比

Figure 5. Comparison of recognition efficiency of four (β = 0.5) algorithms for 1000 labels recognition

图5. 4种算法(β = 0.5)识别1000标签的识别效率对比

Figure 6. Comparison of recognition efficiency of four (β = 0.3) algorithms for 1000 labels recognition

图6. 4种算法(β = 0.3)识别1000标签的识别效率对比

2) 在同等环境下，传统Q算法、Q⁺ 算法、快速Q算法以及本文提出的Q_gac算法的性能依次提高。相对于EPC-Gen2中的传统Q算法，Q⁺ 算法通过将时隙冲突和时隙空闲时参数Q的浮动因子C分开来考虑，引进了C_coll和C_idle，提高了Q值的精确度，使其更加接近最优值，从而提高了识别效率；快速Q算法，在Q⁺ 算法的基础上，考虑到了系统参数中的冲突解码时延T_coll和空闲解码时延T_idle之间的差异，改进了C_coll和C_idle比例关系，进一步提高了Q值的精确度，使其更快地收敛于最优值；而本文的Q_gac算法则在快速Q算法的基础之上，从提高俘获效应的俘获概率这一角度出发，通过根据标签接收到阅读器信号的强弱，将所有标签进行分组，然后选取其中最有可能发生俘获效应的两组，并静默其余分组进行识别，最大程度利用俘获效应，有效提高俘获概率，大大提高了系统的识别效率。

3) 当B组标签数占总标签数的比例逐渐减少时，4种算法识别效率的峰值逐渐增大。其中本文建议的Q_gac算法的峰值由 $\beta =0.7$ 时的0.47增加到 $\beta =0.5$ 时的0.55，最后增加到 $\beta =0.3$ 时的0.64。这充分说明了当A、C组标签数占总标签数的比例越大，并且A组和B组标签数相当时，RFID系统的俘获效应的俘获概率达到最大值。

由以上结论，我们可以总结得出，提高RFID系统的俘获效应的俘获概率可以有效提高系统的识别效率。而本文提出的基于EPC-G2协议，通过采用分组访问控制策略的Q_gac算法，能最大程度的利用俘获效应，提高俘获概率，从而大大提高RFID系统的识别性能。

5. 结语

影响RFID系统识别性能关键因素之一是冲突问题。而根据文献 [3] 中Q_ext算法得知，增大RFID系统中的俘获效应的俘获概率可以大大提高系统的识别效率。本文就如何提高RFID系统的俘获效应，提出了一种分组访问控制的Q_gac算法。为了尽可能利用俘获效应，该算法在识别过程开始之前，根据标签接收信号的强度将标签分组，然后先选取其中最能发生俘获效应的两组进行识别，直到没有俘获效应发生为止，最后对剩下的所有标签进行识别，直到结束。仿真结果表明，Q_gac算法能有效提高RFID系统的俘获效应，且识别效率明显高于现有的各种改进的Q算法，对RFID系统的识别性能有很大的提升。在未来的研究工作当中，我们将继续进一步研究如何提高RFID系统俘获效应的俘获概率，从而进一步降低RFID系统的识别冲突率，提高系统的整体性能。