基于动态Q学习的防碰撞算法的研究

陈　浩，张海峰，应屹航

(1．杭州电子科技大学电子信息学院，浙江 杭州 310018；2．杭州国芯科技股份有限公司，浙江 杭州 310012)



基于动态Q学习的防碰撞算法的研究

陈浩1，张海峰1，应屹航2

(1．杭州电子科技大学电子信息学院，浙江 杭州 310018；2．杭州国芯科技股份有限公司，浙江 杭州 310012)

在射频识别系统中防碰撞是很关键的技术之一，针对EPC-C1G2协议的防碰撞算法中Q值调节不够灵敏的不足，提出了一种双参数且参数动态变化调节Q值的改进算法(EDQ算法).在EDQ算法中，将单一参数C分为双参数Cs和Cc，分别用来调节空闲和碰撞时隙的Q值.通过大量的实验分析，提出了在不同Q值下双参数Cs和Cc的最优值.仿真实验表明，算法能够减少时隙的浪费，从而增大系统吞吐率，减少标签的识别时间.

射频识别；防碰撞算法；Q值；系统吞吐率

0　引　言

无线射频识别技术(Radio Frequency Identification，RFID)，是从二十世纪九十年代兴起的一种非接触的自动识别技术[1].对于一个RFID系统，同一时间可能有多个电子标签进入射频区域，在与阅读器进行通讯时发生信号混叠，产生所谓的碰撞.为了解决这个问题，各国的学者提出了一系列的标签防碰撞算法[2].目前，防碰撞算法主要分为两类：一类是确定性防碰撞算法，主要是基于二进制搜索方法，如动态二进制搜索算法、后退索引二进制算法等[3-4]；另外一类是随机性防碰撞算法，主要是基于ALOHA的算法，如时隙ALOHA算法、帧时隙ALOHA算法和动态帧时隙ALOHA算法[5-7].EPCglobal公司提出的EPC-C1G2协议采用的防碰撞算法叫Q学习算法，称为DQ算法，它是在帧时隙ALOHA算法基础上提出的，该算法不用进行未识别标签数目的估计，而是使用一种启发式的方法使帧大小趋向最优[8].但是DQ算法采用单一参数C调整Q值，且C是固定的，使得Q值的调整不够灵敏.针对这个缺点，本文提出将参数C分成两个不同的参数，并且随着未识别标签数目的变化找到它们的最优值.

1　EPC-C1G2防碰撞算法

EPC-C1G2协议提出的DQ算法使用Query命令初始化一个轮询周期，包含一个时隙计数参数Q，参与轮询的标签在收到Query命令后在(0，2Q-1)范围内产生一个随机数，并将这个数写入自身的时隙计数器.时隙计数器为0的标签向读卡器发送一个RN16(16位的随机数).随机数不为0的标签等待下一条QueryRep或QueryAdjust命令.标签接收到QueryRep命令时，时隙计数器减1，当时隙计数器为0时，标签发送应答信息.标签接收到QueryAdjust命令时，调整Q值，并重新在(0，2Q-1)范围内产生一个随机数写入自身的时隙计数器，重复以上操作.

DQ算法使用参数Q使得帧长趋于最优，Q参数是计算帧长的指数参数，帧长=2Q，同时取Q的浮点数NQ，用来进行Q参数的计算.当发送一个Query命令开启一个轮询周期时，读卡器会在每个时隙接收标签的回复.将时隙分为成功、碰撞和空闲时隙，依据这3个参数改变下一帧的大小.当时隙为空闲时，NQ减去常数C；时隙为碰撞时，NQ加上常数C；时隙为成功时，NQ不变.在下一个时隙开始时取Q=round(NQ)，如果Q发生变化，则发送QueryAdjust命令，完成对帧长的调节.在EPC-C1G2协议中建议0.1≤C≤0.5，单参数DQ算法流程图如图1所示.

2　改进的防碰撞算法(EDQ算法)

2.1EDQ算法对DQ算法的改进

本文从两点来优化DQ算法：

1)C的动态性.如果C比较大，那么帧长将会很快地收敛到最佳点，但是会在最佳点发生很大的震荡；如果C比较小时，收敛到最佳点后改变会很小，但是收敛的速度将比较慢.由此可知，当Q较大时，C应该较小；Q较小时，C应该较大.所以改进的算法让C跟随标签数目的变化而取最佳值.

图1　单参数DQ算法流程图

2)C的差异性.一般情况下，在一个时隙里发生碰撞的概率要小于空闲的概率，所以在一帧中出现碰撞时隙的数目要小于空闲时隙的数目.DQ算法中，在碰撞时隙和空闲时隙使用单一参数C来调整Q值，是不合理的，不利于达到时隙的最佳分布，从而不利于提高系统的效率.本文提出使用两个参数来调整Q值.

2.2EDQ算法流程

通过对DQ算法改进的描述可知，本文设计算法流程如图2所示.从图2中可以看出，EDQ算法使用了两个新的变量Cc和Cs，在碰撞时隙用Cc来调整NQ，而在空闲时隙，用Cs来调整NQ.如果Q值改变，读卡器会发送QueryAdjust命令来改变帧长；如果Q值不变时，则发送QueryRep命令继续进行读取操作.并且在轮询过程中，Cc和Cs会根据Q值动态的变化.

图2　双参数且参数动态变化EDQ算法流程图

2.3Cs与Cc的取值与优化

在帧时隙ALOHA算法中，如果帧长为S，而未识别标签数为N，那么当S=N的时候，系统效率最高.在系统效率最高时，可以得出系统碰撞概率pc和空闲概率ps：

(1)

(2)

如果N取无限大，可以得到pc=1-2/e,ps=1/e.在S=N的条件下，Q取值为最优取值，显然Cs与Cc的比值成反比，可得：

Cc/Cs=ps/pc=1/(e-2)≈1.4

(3)

在DQ算法中，Q值与参数C的最佳关系如表1所示.当Q值增大时，C值变小.

在EDQ算法中，Cc和Cs需要符合下列条件：

1)Cc=1.4Cs；2)0.1≤Cc≤0.5；3)0.1≤Cs≤0.5.

假设在相同的Q值情况下，取一个参数t作为调节因子，且与参数C有如下的关系：Cs=tC；Cc=1.4Cs.其中，t是Cs和Cc的调节因子.

通过EQD算法，在Matlab中分别对相同Q值下的不同调节因子t的取值进行仿真，得到系统效率.例如在Q=8，C=0.2，标签数目为256的情况下进行仿真，如图3所示，当t=0.9时，系统效率最高.所以当Q=8时，最优参数Cc=0.25，Cs=0.18.

表1　Q值与C值最佳关系

图3　Q=8时，参数Cs和Cc最优值

通过Maltab仿真，得到在不同Q值下的调节因子t和最佳参数Cc，Cs的值，如表2所示.

表2　不同Q值下的最佳参数

3　系统仿真及性能分析

图4　基于lowbound估计的DFSA，DQ和EDQ算法仿真

本文采用蒙特卡洛方法，在计算机上使用Matlab进行仿真来验证本文提出的EDQ算法，所有的实验结果都是经过100次的独立实验平均得到的.

在RFID防碰撞算法中，系统效率是衡量系统性能的重要指标.在Matlab软件中，分别对基于lowbound预测的动态帧时隙、DQ算法以及EDQ算法的吞吐率进行仿真.标签范围在100～1 000，仿真结果如图4所示.可以看到基于lowbound估计的动态帧时隙算法的系统吞吐率基本保持在31.5%，而DQ算法的系统吞吐率基本维持在33%，本文提出的EDQ算法的系统吞吐率保持在34.5%，特别在标签数目很大时，EDQ算法更具有优势.

4　结束语

本文在研究EPC-C1G2协议的DQ防碰撞算法的基础上，发现使用单一且不变的参数C对Q值进行调节时，不能迅速地使帧长接近未识别的标签数目，从而提出了使用两个参数Cc和Cs分别调节碰撞和空闲时隙的Q值，而且这两个参数具有一定的比值关系，同时这两个参数随着Q值的变化而动态地做出改变.EDQ算法可以通过参数Cc和Cs迅速调节Q值，使帧长更加接近未识别标签数目，获得更高的系统吞吐率.

[1]米志强,杨曙,王武,等.射频识别(RFID)技术与应用[M].北京:电子工业出版社,2011:3-4.

[2]FINKENZELLER K.RFID Handbook:Radio-frequency Identification Fundamentals and Application (Second Edition)[M].England:John Wiley and Sons,2003:1-10.

[3]杜海涛,徐昆良,王威廉.基于返回式二进制树形搜索的反碰撞算法[J].云南大学学报(自然科学版),2006,28(1):133-136.

[4]MYUNG J,LEE W,SRIVASTAVA J,et al.Tag-Splitting:Adaptive Collision Arbitration Protocols for RFID Tag Identification[J].Parallel and Distributed Systems,IEEE Transactions on,2007,18(6):763-775.

[5]CHEN W T.An accurate tag estimate method for improving the performance of an RFID anti-collision algorithm based on dynamic frame length ALOHA[J].Automation Science and Engineering,IEEE Transaction on,2009,6(1):9-15.

[6]NAMBOODIRI V, DESILVA M, DEEGALA K,et al.An extensive study of slotted Aloha-basedRFID anti-collision protocols[J].Computer communications,2012,35(16):1955-1966.

[7]郭志涛,程林林,周艳聪,等.动态帧时隙ALOHA算法的改进[J].计算机应用研究,2012,29(3):907-909.

[8]马倩,石良平,周力宏.ISO18000_6C标准的防碰撞算法研究[J].计算机应用,2008,28(S2):341-343.

Research on Anti-collision Algorithm Based on Dynamic Q Learning

CHEN Hao1, ZHANG Haifeng1, YING Yihang2

(1.SchoolofElectronicInformation,HangzhouDianziUniversity,HangzhouZhejiang310018,China;2.HangzhouNationalChipScience&TechnologyCo.Ltd.,HangzhouZhejiang310012,China)

Anti-collision is the key technology in the radio frequency identification system, as the insufficient ofQadjustment is not sensitive enough in anti-collision algorithm for EPC-C1G2 protocol, an improved algorithm(EDQ algorithm) is proposed for adjusting theQvalue of the dual-parameter and parameter can be dynamic changing. In the EDQ algorithm, the single parameterCis divided into two parametersCsandCc, which are used to adjust theQvalue of the idle and collision slots. Through the analysis of a lot of experiments, the optimal values of the dual-parameterCcandCsare presented under differentQvalue. The simulation experiments show that the algorithm can reduce the waste of time slots, thus increasing the system throughput rate and reducing the time of label identification.

radio frequency identification; anti-collision algorithm;Qvalue; system throughput rate

10.13954/j.cnki.hdu.2016.01.006

2015-06-23

陈浩(1990-)，男，江苏泰州人，硕士研究生，电子与通信工程.通信作者:张海峰副教授，E-mail: hfzhang0811@hdu.edu.cn.

TP391.41

A

1001-9146(2016)01-0027-05