EPC C1G2防碰撞算法在RFID读写器中优越性的研究

朱葛俊

（常州机电职业技术学院 信息工程系，常州 213164）

0 引言

EPCClass-1Gen-2标准所采用的是时隙随机防冲突算法（SR算法），这种算法有着自己独特的优越性， SR算法可以根据标签时隙的分布情况随时令标签在下一轮的帧循环操作中进入，这样就避免了必须等这一帧中的时隙全部处理完毕的现象[1]。SR算法与其他动态帧时隙ALOHA算法有很大的相似之处，其算法能够更加灵活地对大小进行调整，来促使其在通信次数与吞吐率上的优越性。

1 基本的RFID防碰撞算法

在一个阅读器内存在很多标签是不可避免的，为了能正确的区分这些相同的标签，RFID的防碰撞算法协议就起到了作用，一般情况下，防碰撞算法主要包含两种形式，一种是二进制的树形搜索算法，另一种是时隙的随机防冲突算法，两种算法各自有着各自的特点。

1.1 帧时隙ALOHA算法（FSA算法）

时隙ALOHA算法（SA算法）是阅读器控制驱动的方法，它把时间分为离散的时隙，同时必须有全局的时间同步。与简单的ALOHA法相比，时隙ALOHA法可能出现的碰撞的时间只有前者的一半。FSA算法在SA算法基础上，把每个时隙进一步分割成若干时隙并打包成帧。标签在帧内只随机发送一次信息包，故该算法进一步降低了碰撞的机会。该算法中帧时隙的长度是固定的，而实际应用中电子标签的数量未知且动态变化。因此其缺点是如果标签数远远多于固定的时隙数，会产生过多碰撞；反之，会产生较多空闲时隙，造成资源浪费。

动态帧时隙ALOHA算法（DFSA算法）对FSA算法又做了进一步的改进，DFSA算法应用于当FSA算法始终遇到有碰撞发生时。阅读器在等待状态中的循环时隙段内发送请求指令，该指令使工作状态的电子标签同步，然后提供1个或2个时隙给电子标签使用，电子标签将选择自己的传送时隙，如果在这1或2个时隙内有较多电子标签发生了数据碰撞，则阅读器就用下一个请求指令增加可使用的时隙数，直至碰撞消失，从而大大提高了吞吐率。该算法由于操作简单和性能良好而成为目前最常用的算法之一。其特点是：帧的时隙数是动态产生且可变的，解决了FSA算法中时隙的浪费问题，但在标签数量很多、发送时隙受限时，DFSA算法几乎显示不出其优越性。

1.2 二进制树形搜索算法

二进制树形搜索算法比较复杂，识别时间较长。在基于序列号的方式中需要电子标签具有唯一标示符以保证识别，同时阅读器所使用的信号编码应能准确确定碰撞的比特位置；在基于随机数和时隙的方式中要求应答器中有一个随机数产生器。该方法采用递归的工作方式，遇到碰撞就分解成两个子集。这些分支越来越小，直到最后分支下面只有一个信息包或者为空。当所有发生碰撞的信息包都被成功识别和传输后，碰撞问题即得解决。

2 EPC C1G2防碰撞算法及仿真

EPCGen2协议是超高频第二代空中接口标准射频识别协议。其防碰撞算法本质上是动态帧时隙ALOHA算法，这种算法可以随意的动态调整每一帧中的时隙数量，并且可以根据标签中时隙的分布情况随时进行下一个指定来进入下一个循环操作，这就避免了要等上一轮循环完成以后才可进行指令的弊端。此算法中的防碰撞机制是通过Q参数控制帧的长度，然后根据读取过程中的读取结果进行实施调整，在一个识别周期内随时更改时隙数，让未识别标签重新选择，实现了时隙数的自适应过程。

2.1 算法概述

在EPC Class1Gen2的空中接口协议中，防碰撞算法通过Query，QueryAdjust，QueryRep等指令完成，这种算法是通过阅读器发送的Query指令，然后开始第一轮的盘点周期，这期间包含了一个参数Q，也就是说该帧有2Q个时隙，Q初始值为4。任何一个标签收到此指令后便会产生0～2Q-1之间的随机数来作为应答时隙，然后通过随机时隙计数器将其载入，时隙计数器中的时隙为0的标签向阅读器发送RN16作为应答信息，这时阅读器发送Query指令，然后对其进行检测RN16的碰撞情况，如果没有遇到碰撞情况，阅读器便很顺利的识别出该标签并发送ACK指令。如果遇到碰撞现象就会发出NAK，标签这时接到ACK指令后发出不参与余下过程的指令。如果遇到标签没有向阅读器发送RN16，这说明所有标签可以从新选择应答时隙，标签时隙可以减1来减少Q值，这样就可以使得标签时隙0的几率大大增加，当遇到标签发送RN16的时候，这说明标签遇到了冲突，这时候阅读器可以把标签时隙减1，增加Q值来扩大标签的随机选择时隙，进而实现减少和避免冲突的概率，这样通过动态的调整Q值来实现的标签的时隙进行数据传输，此时阅读器既可以使所有标签的时隙减1（发送QueryRep指令），也可以通过减少Q值（发送QueryAjust指令）的方法令所有标签重新选择应答时隙，这样便可以使标签的时隙为0的概率增大；如果有多于一个的标签向阅读器发送了RN16，这时便产生了标签间的冲突，此时阅读器既可以使所有标签的时隙减1（发送QueryRep指令），也可以增大Q值（发送QueryAjust指令）使标签在更大的范围内随机选择时隙，从而减少发生冲突的概率。阅读器通过动态调整Q值从而调节各个标签的时隙，使得标签分别占用不同的时隙与阅读器进行数据传输进而实现防碰撞的算法[2]。

图1 所需时隙数

图2 系统吞吐率

Q值的大小会使得随机时隙的大小变化，大的Q值可以减少冲突，但是要增加空闲时隙，小的Q值会增加碰撞几率，但是会减少空闲。过多的空闲时隙会降低识别效率，产生识别效率降低的现象，因此，要在阅读器的时隙状况实施调整的状态下，才能使标签的取值范围更好。

2.2 算法性能仿真及比较

FSA算法、二进制树搜索算法及EPCGen2算法的性能分别用matlab进行仿真并进行了比较，如图1及图2所示。

当标签数超过600时，FSA算法识别标签所需的时隙数呈现大幅增长的趋势。FSA算法的系统吞吐率较低且吞吐稳定性差。FSA算法适合于识别数量在600个以内的电子标签，且在识别效率上与其他两种算法相比存在一定差距。二进制树搜索算法的时隙数与标签数呈线性关系，识别标签所需的时隙数介于其他两者之间，系统吞吐率差。EPCGen2算法的最大时隙数可达215，实际中即使识别大数量的标签也不会受到时隙数限制。采用EPCGen2算法系统吞吐率最高且保持在一个稳定值附近。在识别大数量标签时，EPCGen2算法识别标签所需要的时隙数比其他两种算法少很多，识别速度快。EPCGen2算法相对复杂，适合识别大数量电子标签[3]。

2.3 建立仿真程序

选择Excel2007作为仿真计算软件，首先建立一个标签类CTag，用于进行仿真标签的行为，数据成员分别用槽值表示和用“未响应”、“冲突”和“成功”三种状态来表示，阅读器调用前三个方法查询标签，调用第四个方法把标签设为冲突状态。Query和QueryAdjust需要的随机数可利用Excel2007的新增函数RandBetween生成，来自动选择函数的顺序。然后建立一个阅读器类CReader，该类主要包含三个方法Select、Inventory和AdjustQ，来进行仿真阅读，其中Select用于设置标签数量，并生成对应的标签对象数组。Inventory用于清点所有标签。该方法首先调用所有标签的Query方法，然后重复调用QueryRep或QueryAdjust方法。如果中途发现有多个标签的槽值为0，则调用Collide方法，体现并记录冲突，AdjustQ是私有方法，仅由Inventory方法调用，用于每次查询后根据适当条件调整标签的Q值。目标的变化后文将实现两个版本的AdjustQ方法。退出清点循环的判断条件为：在某一Q值下连续执行2Q次查询都没有发生冲突。Q选择算法执行过程中，标签与Q值得减少为结束条件对整体效率的影响较小。但是当标签较少，而Q的初值较大时，需经多次查询，Q值才能减小到合适的程度，因此Q的初值应较小，一般可取不大于3的值[4]。

3 结束语

关于RFID 读写器多标签冲突现状，结合 EPC Class-1 Gen-2 标准中的读写器与标签的通信指令，研究并实现了防冲突算法，从仿真结果可以看出EPC Gen2算法在标签识别效率及系统吞吐率上的优越性。

[1] Ki Yong JEON,Sung Ho CHO.A R fid Epc C1 Gen2 System With Channel Coding Capability In Awgn Noise Environments [J].IEICE Transactions on Communications,2009,e92/b(2)_4.DOI:10.1587/transcom.E92.B.608.

[2] 罗恰嗣,郭立,周云超,等.一种EPC Gen2 RFID标签时钟校准方法[J].中国科学院研究生院学报,2009,26(6)4.

[3] 周盛华,杨志超,吴南健,等.小面积低功耗RFID射频前端电路设计[J].半导体学报,2006,27(z1)4.

[4] 钟学毅,吕宁,王昌明,等.RFID系统的Matlab/Simulink建模及特性分析[J].电讯技术,2006,46(5)4.