RFID中基于EPC G1G2的DTJ-ALOHA防碰撞算法仿真

杨晓娇 叶 润 吴必造

1(重庆交通大学信息技术中心 重庆 400074)2(电子科技大学 四川 成都 611731)3(中移物联网有限公司 重庆 401336)

RFID中基于EPC G1G2的DTJ-ALOHA防碰撞算法仿真

杨晓娇1叶 润2吴必造3

1(重庆交通大学信息技术中心 重庆 400074)2(电子科技大学 四川 成都 611731)3(中移物联网有限公司 重庆 401336)

针对EPC G1G2标准中的动态帧时隙防碰撞算法，在标签数量较多时，会导致Q值频繁的更改，从而增加了阅读器的负担等问题，提出一种以碰撞、空闲和成功时隙的差值，作为判断Q值改变门限的DTJ(Devalue Threshold Judgment)-ALOHA算法。通过Matlab仿真与EPC中算法做对比，验证了DTJ-ALOHA算法无论在Q值改变次数、平均吞吐率，还是阅读器的开销上都优于常见改进算法。

动态帧时隙 ALOHA算法 吞吐率 防碰撞 射频识别RFID

0 引 言

目前，国内外现有的针对RFID系统的大多数论文所研究以及改进的防碰撞算法，大都是基于TDMA的时分多路算法的基础上提出的[1-3]。根据算法思想的不同可分为下面几类：1) 基于分时隙思想的，识别结果不确定的ALOHA及其衍生算法；2) 基于二分查找思想的，识别结果确定的二进制及其衍生算法。ALOHA虽然属于不确定性算法，但是由于其对硬件的要求没有二进制算法高而且其实现过程也相对简单且易于实现，因此RFID系统在阅读器作用域内存在大量标签待识别时(此时防碰撞算法需要满足：快速准确地识别阅读器作用域内的所有标签)，由于系统实现简单，自效率高等优势首选就是ALOHA及其衍生算法[4]。因此，本文提出的DTJ-ALOHA算法也是基于ALOHA的基础上提出的。

现在国内外大多数针对基于ALOHA的改进算法的论文，主要是通过将阅读器作用域中存在的标签分成几组来对标签进行分流而达到减少碰撞概率的目的，或者通过某种策略来动态地改变帧长等方法来提高RFID系统的吞吐率。但这些算法大都停留在理论层面，没有和实际的国际标准协议中的防碰撞算法结合起来，因此，在工程中应用得并不广泛。本文就是针对EPC G1G2中推荐的DSF(Dynamic Framed Slotted)-ALOHA算法，对EPC G1G2协议中规定的DFS-ALOHA防碰撞算法在标签数量较多时，由于总时隙数的增加会导致空闲以及碰撞时隙也相应的增多，使得Q值发生频繁波动，以及频繁计算Qfp(Q的浮点数形式)导致阅读器负担较重等缺陷，提出了一种根据碰撞、空闲以及成功时隙的差值作为Q值跳变门限的DTJ-ALOHA算法。最后通过在Matlab7.0平台上Matlab编程模拟算法的执行过程，对结果绘图对比分析，验证了DTJ-ALOHA算法不论在控制Q值改变次数、时隙吞吐率以及系统阅读器开销等性能上都优于推荐的EPCG1G2推荐的算法。

1 EPC中的动态帧时隙DFS-ALOHA算法

EPCglobal标准委员会的EPCC1G2中推荐的算法也是基于ALOHA的即DFS-ALOHA算法[5]。协议规定通过定义一个Q来根据时隙状态灵活改变帧长，阅读器通过向其作用域内广播发送Query、QueryAdjust和QueryRep等命令来改变帧长。并且根据标签的回复记录下当前时隙的状态，然后根据统计的标签状态来动态调整帧长，若Q值发生变化，则标签工作在2Q的动态帧长下[6]。

1.1EPCG1G2中DFS-ALOHA的涉及到的命令简介

本节将对EPCG1G2协议中用到的命令(在第2节中DTJ-ALOHA算法中也会用到的命令)简介[8]。

Query(Q)命令：目的是向标签发送Q值，标签从Query(Q)中获取Q值后选择x属于[0，2Q-1]放到标签的SC(SlotCount)中，当且仅当SC中存储的值通过QueryRep(n)命令自减为0时，标签才请求通信。

QueryAdjust(Q)：协议中规定的更新时隙的命令，用于向标签广播用于计算时隙的参数Q。标签从QueryAdjust(Q)命令中获取Q值后，先将其SC中数值清零，然后选择x属于[0，2Q-1]放到标签的SC(SlotCount)中。

QueryRep(n)：减少SC值命令，该命令携带一个参数n，阅读器作用域范围内标签收到该命令广播的n值后，根据SC=SC-n计算SC的值将其重新存储在SC中(EPCG1G2中n=1)。

1.2EPCG1G2中的防碰撞算法思想

EPCG1G2中采用DSF-ALOHA算法识别标签的过程，如图1所示，主要是根据当前时隙的状态来动态地调整Q值从而改变帧长，调整方法是：1) 若为空闲时隙则Qfp=Qfp-C；2) 若为碰撞时隙则Qfp=Qfp+ C；3) 若为成功时隙则Qfp=Qfp。每个时隙过后就对Qfp进行计算Q=round(Qfp)(取整方法为四舍五入)。若本时隙结束后，经过计算发现Q不等于Qstart，即需要更新Q值，接着发送QueryAdjust(Q)命令对Q值进行更新；反之，则表示不需要更新Q值，只需阅读器继续处理下一个时隙即可，即发送QueryRep(1)命令继续识别[9]。

图1 EPC G1G2中建议调整Q值的方法(Qfp为Q的浮点形式)

在EPCG1G2协议规定C为浮点数，其取值范围为0.1～0.5，且C取值由于Q的增大而减小[8]。这是因为当阅读器作用域内存在大量标签时，总时隙N也会很大，从而使得碰撞以及空闲时隙数也相应的增加，由于推荐算法在每寻呼一个时隙就要对Q进行一次浮点运算，当总时隙N很大时阅读器进行浮点数的运算量也很大，此时阅读器的负担就很大，即便取C=0.1也会同样会导致Q值频繁的更新。因此，针对上述不足，本文提出了一种改进的基于差值门限判决来决定Q值是否改变的DTJ-ALOHA算法。新算法不用进行浮点预算，并且再标签数增加时不会导致Q值的频繁更新。

2 DTJ-ALOHA算法

在实际RFID系统中时隙数N不能为任意值，N的取值只能是2Q(Q=0,1,2,…)则可以计算得出，标签根据接收到的Q值生成的时隙数可为0,2,4,…,128,256,512，且当Q值越大对Q值进行加或者减1操作后，对N的波动会越大。本文根据碰撞、空闲、和成功时隙个数的差值表达式来作为Q改变的依据，从而规避了上述问题，提出了一种新的算法。下面介绍DTJ-ALOHA算法是如何提出的。

在ALOHA算法的基础上面，可推导得出在FS-ALOHA算法中，某时隙中存在k个标签的概率为：

(1)

同理，由式(1)令X=1即可得出有且仅有一个标签选择当前时隙(表示当前时隙为成功时隙)的概率为：

(2)

对式(2)进行Matlab仿真分别令N=16,32,64,128,256时可以得出算法的吞吐率随标签个数的变化规律，如图2所示(从左到右依次为N=16,32,64,128,256的图像)。

图2 N=16，32，64，128，256时FS-ALOHA 算法吞吐率与标签个数的关系

由图2可知，要保持吞吐率较高，则取两条曲线的交点间部分对应的时隙数(如标签个数在ab段时取时隙数N=64)，吞吐率较高的两条直线的交点即为时隙数为N的曲线与时隙数为2N和N/2的交点(以N=64这条曲线的吞吐率为例分析，与2N的交点即为b点与2/N的交点即为a点)。可以推出时隙数分别为N以及2N的两条吞吐率曲线的交点所对应的标签个数nN=2N为：

(3)

(4)

由式(1)令k=0可以推出，没有一个标签选择某时隙的概率(该时隙为空闲时隙)Pnull为：

(5)

同理k>1可推出不止一个标签选择某时隙的概率(即该时隙为碰撞时隙)Pcoll为：

(6)

以图2中ab段对应的N=64的吞吐率曲线为例，该曲线的顶点(即吞吐率最高)所对应的x轴标签个数也大概为64左右，其余吞吐率曲线也是当N约等于n时，吞吐率最高。下面以N=16时碰撞、成功以及空闲时隙占总时隙的概率，随标签个数的变化规律为例进行Matlab仿真，结果如图3所示。从图中的概率曲线可以得出当算法吞吐率较高时，碰撞概率与成功概率差值以及空闲概率与成功概率的差值较小。

图3 帧长为N=64时FS-ALOHA算法时碰撞、成功以及空闲时隙概率随标签个数n的变化图

所以，本文提出了一种根据碰撞与成功以及空闲与成功时隙的差值作为阈值来控制Q值的改变，将Q值由Q变为Q+1的阈值Th+定义为：Th+=N×(Pcol-Psuc)，将Q值由Q变为Q-1的阈值Th-定义为：Th-=N×(Pnull-Psuc)将前面定义的式(5)、式(6)代入阈值Th+和Th-表达式化简可得出：

Th+= N×(Pcol-Psuc)=

(7)

Th-= N×(Pnull-Psuc)=

(8)

由式(7)和式(8)可以得出Q值及其与Th+和Th-取值为表1所示。

表1 Q值与其对应的阈值Th

表1中提前计算好了Q跳变的阈值，阅读器只需要根据每个时隙的状态做一个简单的比较以及加减法运算，这样就有效解决了本节开始提出的由于做浮点运算而导致阅读器负担增加的问题。

因此，下面简单介绍DTJ-ALOHA算法的程序流程图。

按照如图4所示的流程，当阅读器向标签发出通信请求后，根据回复的个数确定本时隙碰撞、空闲还是成功时隙。接着统计本帧中空闲、碰撞以及成功时隙的个数。

图4 DTJ-ALOHA算法的详细程序流程图

如果本时隙为非成功时隙，则比较碰撞时隙与空闲时隙大小，1)若Qcoll>Qsuc将碰撞时隙与成功时隙差值与表1中对应Th+的阈值进行比较，如果统计的时隙数差超过阈值，则表示碰撞时隙过多，应增加时隙数，发送QueryAdjust(Q)命令调整Q值来更新时隙数，反之没有超过阈值表示时隙数不变发送QueryRep(1)命令继续读取下一个时隙。2)若Qcoll≤Qsuc将空闲时隙与成功时隙差值与表1中对应Th-的阈值进行比较，如果统计的时隙数之差超过阈值，则表示空闲时隙过多，应减少总时隙数，发送QueryAdjust(Q)命令通过调整Q值来更新总时隙数，反之没有超过阈值表示时隙数不变发送QueryRep(1)命令继续读取下一个时隙。

由表1可以看出，DTJ-ALOHA算法的阈值Th+和Th-是根据Q值动态变化的，且Q值越大Th+和Th-越大。这样就避免了在标签数量较大时，由于Q值的频繁改变而增加阅读器负担的问题。因此，DTJ-ALOHA算法在标签数量不确定时，特别是个数动态变化，或者有大规模标签待识别时，优势明显。

3 DTJ-ALOHA算法的仿真以及结果分析

本文的所有仿真实验都是在Matlab7.0平台上进行的。分别编程实现不同算法识别标签的过程，再统计运行的结果，为了减小偶然因素对算法评估造成影响，本文中所有图中的结果都是识别相同的标签50次后的结果所取的平均值。

首先分别编程实现EPCG1G2算法以及DTJ-ALOHA算法的执行过程，得出它们发送QueryAdjust(Q)改变Q值的次数对比如图5所示。

图5 采用阈值跳变来更改Q值与EPC G1G2推荐方法改变Q值需要发送QueryAdjust()命令次数的对比图

由图5可看出EPCG1G2算法当标签个数增加时不论C取何知，Q值改变次数都称线性增加，反之DTJ-ALOHA算法的控制在30以内，从而减少了阅读器的负担。

通过图5与表2可看出，不论标签多与少，改进算法都将Q值改变次数控制在一定范围30内。即改进算法相比于EPCG1G2算法适应性较好。

表2 Q值改变次数对比图

本文中将RFID系统中ALOHA算法的平均吞吐率定义为：有效时隙数(成功时隙数)/总时隙(阅读器识别完其作用域内全部标签共需要的时隙数)。

从图6可以看出，大规模标签识别过程中，改进算法DTJ-ALOHA的吞吐率稳定在35.5%左右，EPC G1G2算法吞吐率稳定在34.5%(C=0.1)和33%(C=0.5)左右，验证了改进算法即DTJ-ALOHA阈值跳变算法比EPCG1G2算法的吞吐率更优。

图6 吞吐率比较图

当前针对动态帧时隙ALOHA的改进算法主要是基于对标签数估计算法，算法的主要思路是阅读器先读取完N个时隙的信息，并统计碰撞率空闲率，并根据某种算法来估计待识别标签的数量，然后调整Q值，这类常见动态ALOHA改进的算法，优势是Q值改变次数相对较小。但由于这类算法每次对待识别标签数进行估计前，都需要先统计N个时隙的状态，并以此为依据结合算法来调整帧长，因此这类改进算法适应性即吞吐率没有DTJ-ALOHA算法好。

由于阅读器开销大小直接决定了识别其作用范围内所有标签的耗时长短，也就直接影响了识别的准确率。是衡量算法效率的关键指标。为了证明本文提出的DTJ-ALOHA算法的可行性，下面将常见的动态帧时隙的改进算法与本文提出的DTJ-ALOHA算法在阅读开销上进行仿真对比。

根据表3中规定的命令长度，对DTJ-ALOHA算法、基于标签数估计的动态帧时隙ALOHA算法以及EPCG1G2算法对阅读器读取标签过程中的开销(发送数据量)做仿真。

表3 EPC C1G2协议命令/参数长度

图6和图7的结果已经验证了改进的DTJ-ALOHA算法在关键性能指标上不仅优于EPC G1G2推荐的算法也优于常见的改进(基于标签估计的动态帧时隙ALOHA)算法。

图7 三种不同算法对应的阅读器开销对比图

4 结 语

本文在EPC G1G2的DFS-ALOHA算法基础上提出了一种基于差值门限判决的DTJ-ALOHA算法，改进算法采用差值判决替代C值来触发Q值的改变，因而不用进行浮点运算，减轻了阅读器的计算量。由于阈值的动态变化也使得算法在标签个数不确定时始终能保持较优的吞吐率。相比于其他改进的动态帧时隙算法(读完N个时隙再改变Q值)本算法延续了EPCG1G2 快速动态调整Q值的优势。然后通过在Matlab7.0平台上编程模拟算法的执行过程，仿真证明了DTJ-ALOHA算法将Q值改变次数控制在30以内，且算法的平均吞吐率稳定在35.5%左右。最后通过仿真证明了本文提出的DTJ-ALOHA算法在阅读器开销这一衡量算法的关键指标上是优于常见的基于标签估计的改进的动态帧时隙ALOHA算法，且DTJ-ALOHA算法并没有额外的增加寻呼命令，因此可以在EPCG1G2协议上直接实现。由于基于EPCG1G2协议的实现的RFID系统常用于有大规模标签待识别的系统比如大型港口、大型商场等实际应用环境，因此本文提出的DTJ-ALOHA算法有一定的实用价值，可应用在RFID系统大规模标签待识别环境中。

[1] 孙其博,刘杰,黎羴,等.物联网:概念、架构与关键技术研究综述[J].北京邮电大学学报,2010,33(3):2-3.

[2] 黄玉兰,夏璞,夏岩,等.物联网射频识别(RFID)核心技术详解[M].北京:人民邮电出版社,2012:22-25.

[3] 石封查,崔琛,余剑.基于标签运动的一种新型RFID防碰撞算法[J].计算机科学,2013,40(6):76-79.

[4]FinkenZellerK.射频识别(RFID)技术―无线电感应的应答器和非接触IC卡原理与应用[M].2版.北京:电子工业出版社,2001:98-101.

[5]EPCGlobal.EPCRadio-FrequencyIdentityProtocolsGengernation-1[S].American:UCC,2013-10-31.

[6] 肖海慧,王红明.一种基于DFSA防碰撞协议的FBF改进算法研究[J].计算机应用与软件,2013,30(7):305-308.

[7]ChaJR,KimJH.DynamicframedslottedALOHAalgorithmsusingfasttagestimationmethodforRFIDsystem[C]//ConsumerCommunicationsandNETWORKINGConference,2006.Ccnc.2006:768-772.

[8]EPCGlobal.EPCRadio-FrequencyIdentityProtocolsGengernation-2UHFRFIDProtocolforCommunicationat860MHZ～ 960MHZVersion[S].California:EPCGlobal,2008.

[9] 徐圆圆,曾隽芳,刘禹.基于Aloha算法的帧长及分组数改进研究[J].计算机工程,2008,3(12):57-59.

[10] 吴淼,刘德盟,张钊锋.基于EPCGen2防碰撞机制的研究与优化[J].微电子学与计算机,2013,30(5):101-104.

SIMULATION OF DTJ-ALOHA ANTI-COLLISION ALGORITHM BASED ON EPC G1G2 IN RFID

Yang Xiaojiao1Ye Run2Wu Bizao3

1(InformationTechnologyCentre,ChongqingJiaotongUniversity,Chongqing400074,China)2(UniversityofElectronicScienceandTechnologyofChina,Chengdu611731,Sichuan,China)3(ChinaMobileIOTCompanyLimited,Chongqing401336,China)

In the dynamic frame slot ALOHA in the EPC G1G2 standard, when the number of tags is large, the Q value frequently changes, thereby increasing the burden on the reader and other problems. DTJ-ALOHA algorithm is proposed, which takes the difference of the collision, idle and success slots as the threshold to judge the Q value. Compared with the EPC algorithm through Matlab simulation, it is proved that the DTJ-ALOHA algorithm is better than the common improved algorithm in terms of the number of change of Q value, the average throughput, and the cost of the reader.

Dynamic frame slot ALOHA algorithm Throughput Anti-collision RFID

2015-05-25。杨晓娇，工程师，主研领域：RFID防碰撞算法。叶润，博士生。吴必造，工程师。

TP312

A

10.3969/j.issn.1000-386x.2017.06.054