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

# 基于EPC-G2协议的分组访问控制Q算法Q-Algorithm Utilizing Access Control by Group Based on EPC-G2 Protocol

Abstract: This paper presents a novel anti-collision algorithm called Qgac-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, Qgac-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 Qgac-Algorithm can effectively improve the capture-effect in RFID system, and greatly reduce collision probability, outperforming the other existing schemes significantly.

1. 引言

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

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

3. Qgac算法描述与分析

3.1. 俘获效应

3.2. 算法描述与分析

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

${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}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\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}\text{ }\text{ }\left(k=0\right)$ (2)

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

$\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}\text{ }\left(k>1\right)\end{array}$ (4)

${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}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\left(k>1\right)$ (5)

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

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

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

(9)

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

${C}_{c}=-0.0491\mathrm{ln}\left(N\right)+0.534$ (10)

${C}_{i}=1.98×\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×\left(\text{e}-2\right)\left(1-{p}_{cap}\right){C}_{c}$ (12)

4. Qgac算法的仿真与分析

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

Figure 3. Qgac algorithm flow chart

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

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

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

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

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

5. 结语

[1] 陈毅红, 冯全源. 基于捕获效应的预约时隙分配RFID防碰撞协议研究[J]. 计算机学报. 2015, 38(12): 2375-2388.

[2] 陈天鹅, 程载和. 基于冲突树的RFID自适应防碰撞算法[J]. 计算机应用, 2010, 30(7): 1728-1730.

[3] 陈楼, 张伟, 黄瑞玲. 基于EPC-G2协议的带俘获效应的Q算法[J]. 计算机工程, 2012, 38(8): 271-273.

[4] 李慧, 张治国. 不定长RFID 标签反碰撞识别算法[J]. 计算机工程, 2010, 36(20): 241-243.

[5] EPC Global Inc. (2006) EPC® Radio-Frequency Protocols Class-1generation-2 UHF RFID Protocol for Communications at 860 MHz-960 MHz Version 1.2.0.
https://wenku.baidu.com/view/aa406b33b90d6c85ec3ac656.html

[6] Lee, D., Kim, K. and Lee, W. (2007) Q+-Algorithm: An Enhanced RFID Tag Collision Arbitration Algorithm. Ubiquitous Intelligence and Computing, 4th International Conference (UIC 2007), Hong Kong, 11-13 July 2007, 23-32.
https://doi.org/10.1007/978-3-540-73549-6_3

[7] 刘传辉, 李川. 一种基于捕获效应的防碰撞算法设计[J]. 测控技术, 2015, 34(5): 23-30.

[8] Shin, W.J. and Kim, J.G. (2009) A Capture-Aware Access Control Method for Enhanced RFID Anti-Collision Performance. IEEE Communications Letters, 13, 354-356.
https://doi.org/10.1109/LCOMM.2009.081970

[9] Li, B. and Wang, J.Y. (2011) Efficient Anti-Collision Algorithm Utilizing the Capture Effect for ISO 18000-6C RFID Protocol. IEEE Communications Letters, 15, 352-354.
https://doi.org/10.1109/LCOMM.2011.011311.101332

[10] Wang, C., Daneshmand, M., Sohraby, K. and Li, B. (2009) Performance Analysis of RFID Generation-2 Protocol. IEEE Transactions on Wireless Communications, 8, 2592-2601.
https://doi.org/10.1109/TWC.2009.080437

[11] Teng, J., Xuan, X. and Bai, Y. (2010) A Fast Q Algorithm Based on EPC Gen-eration-2 RFID Protocol. 2010 6th International Conference on Wireless Communications Networking and Mobile Computing (WiCOM), Chengdu, 23-25 September 2010, 1-4.
https://doi.org/10.1109/WICOM.2010.5601078

Top