无线射频识别(RFID)技术被广泛应用于各个行业，随着物联网技术的逐渐普及，在可以预见的未来，RFID技术还将被更多地应用到日常生活和生产中。然而伴随着RFID技术的广泛应用，RFID技术中的碰撞问题也日渐严重。碰撞是RFID中常见的问题，碰撞大致分为标签碰撞和阅读器碰撞^{[1, 2]}。标签碰撞是多个标签的回复信号相互干扰使阅读器无法正常识别标签；而阅读器碰撞是多个阅读器的信号相互干扰使标签与阅读器的通信过程无法正常完成。目前市面上使用最多的标签防碰撞算法基于时分复用(time division multiple access，TDMA)方法，TDMA方法分为ALOHA的不确定性算法和基于二叉树的确定性算法。平行双阅读器算法和主从式双阅读器算法是标签碰撞算法中比较有创新的算

法^[3]。现有的阅读器防碰撞算法主要分为基于控制阅读器发射功率的方法^{[4, 5, 6]}、基于时序的方法^[7]、基于载波监听的方法及其他方法^[8]。但是这些阅读器防碰撞算法在确定某些阅读器工作的同时，另外一些阅读器则处于闲置状态，使得阅读器资源未被充分利用。本文提出一种改进算法，该算法利用闲置阅读器协助工作状态的阅读器，从而改进系统效率和吞吐量。

HiQ算法适用于阅读器网络拓扑结构比较稳定的情况，类似于无线传感网络中的分簇算法，将阅读器分3个等级，底层阅读器、上层R-Server服务器和顶层Q-Server服务器，分别相当于传感网络中的节点、簇头和汇聚节点^[2]。但如果阅读器网络拓扑结构变化频繁，HiQ算法效率会比较低。Pulse算法利用了载波监听机制和双信道机制，其流程如下：初始时，阅读器A控制信道侦听，如同时有其他阅读器在读写标签，则阅读器A在控制信道等待，否则阅读器A广播Request信号尝试占用数据信道；若成功占用数据信道，则可以在数据信道和标签通信^[1]，否则执行退避算法。新型阅读器防碰撞算法在Pulse算法基础上做了改进，性能有一定提高^[2]。文献^{[8, 9, 10, 11]}利用DCS(distributed color selection)或VDCS (variable-maximum DCS)算法对阅读器进行着色，不同颜色代表不同时隙，使阅读器网络中任意两个相邻的阅读器发生碰撞的概率达到最小。除了算法上改进，在阅读器天线阵设计上^[12]同样能够有效地减少阅读器碰撞。另外文献^[13]提出了一个名为NFRA(neighbor friendly reader anti-collision algorithm)的基于全局调度的阅读器防碰撞算法，利用一个名为serve的中央处理机为阅读器分配工作，算法能够适用于阅读器网络拓扑结构变化频繁的环境。文献^[14]中提到的方法也是一种全局调度算法，先通过阅读器之间的碰撞情况生成一个存储碰撞信息的二维数组，然后在每一个读写周期打开相互没有碰撞的阅读器，关闭二维数组中有碰撞信息的阅读器，但在阅读器密集环境中系统效率有待改进。文献^[15]是一种基于时隙的阅读器防碰撞算法，算法中利用了多信道和竞争机制，阅读器竞争信道，如果有多信道可用，阅读器会根据每个信道的RSSI (received signal strength indication)值选择最合适的信道。

图1

图1算法应用场景

基于身份竞争与协作的阅读器防碰撞算法(IC²RA)利用了载波监听机制、双信道机制和身份竞争机制。相邻的多个阅读器在控制信道竞争主阅读器身份，竞争成功者成为主阅读器，其余相邻阅读器成为从阅读器，并辅助主阅读器的工作。主阅读器可以在数据信道读写标签。图 1描绘了一个应用场景，虚线标识出了主阅读器控制信道的覆盖范围。

首先，算法将RFID系统通信信道分为控制信道和数据信道。控制信道用于阅读器间的通信；数据信道用于阅读器和标签之间的通信。控制信道的覆盖范围必须保证所有在数据信道可能产生相互干扰的阅读器之间能够通过控制信道互相通信^[2]。可以通过提高控制信道的发射功率保证控制信道的通信范围大于数据信道的通信范围。控制信道是整个RFID系统频段的一部分，和数据信道相互之间不会产生干扰。

其次，算法对后台系统有一定要求。要求后台计算能力相对较强，而阅读器只是作为后台系统的前端终端存在。后台不仅存储了标签ID_Tag等信息，还为每个阅读器分配了一个唯一的ID_reader。后台会对阅读器发送来的消息进行分析，并根据分析结果确定是否接受某个阅读器的消息，具有一定的安全防御作用。

阅读器的有限自动机如图 2所示。其中，阅读器可能经历的状态有6种，大致可分为3类：休眠状态、主阅读器状态、从阅读器状态。从阅读器状态包括侦听、等待、身份竞争、随机延时4个状态，而除休眠状态以外的状态只要收到后台的Sleep信号，都会进入休眠状态。下面就以该状态转换图来描述算法流程。

图2

图2阅读器有限自动机

1) 初始时，所有阅读器处在休眠状态，如果有数据请求来到，阅读器A开始在控制信道侦听；否则继续休眠。

2) 侦听状态的阅读器A在Tmin^[8]时间内若听到Request或Occupy信号，则阅读器A立即进入等待状态；若Tmin时间内没侦听到Request和Occupy，则阅读器A广播Request并立即进入身份竞争状态。

3) 若阅读器A在等待状态收到End信号或者等待时间超过Tmin时限，阅读器A开始随机延时，延时算法类似802.11算法中的backoffs^[8]，延时结束阅读器A进入身份竞争状态。

4) 若阅读器A在竞争状态广播Request信号后，收到Occupy信号，则阅读器A从身份竞争状态回到等待状态。若在Tmin时间内未收到Occupy信号则阅读器A身份标志置Mas，表示阅读器A现在成为主阅读器，可以在数据信道开始读写标签。

5) 一个读写标签周期结束，阅读器A广播End信号并将身份标志位置为Sla，回到侦听状态。

主阅读器在数据信道读写标签，在控制信道广播控制信号避免碰撞。数据信道和控制信道的工作流程描述如下(其中，ID_readerA表示主阅读器ID，ID_readerB表示从阅读器ID，ID_Tag表示标签ID，Sk表示标签密钥，readerA表示主阅读器，readerB表示从阅读器)：

在数据信道，主阅读器广播发送${\rm{Query||IDreaderA}}$，收到标签回复的消息${\rm{Hash(IDTag}} \oplus {\rm{Sk}}||{\rm{IDreaderA)}}$后，主阅读器会将此消息转发给后台。

在控制信道，主阅读器如果收到其他阅读器的Request信号，则进行判断。如果身份标志是Mas且还未广播End信号，则主阅读器在控制信道广播发送Occupy；除此以外，主阅读器不响应Request信号。

从阅读器在控制信道不断尝试竞争成为主阅读器，工作流程无需再赘述。下面主要介绍从阅读器在数据信道的工作。

当从阅读器收到标签消息${\rm{Hash(IDTag}} \oplus $${\rm{Sk}}||{\rm{IDreaderA)}}$后，便在消息末尾加上ID_readerB，此时标签消息变成${\rm{Hash(IDTag}} \oplus {\rm{Sk}}||{\rm{IDreaderA}}||{\rm{IDreaderB)}}$。与此同时，若从阅读器处于随机延时状态便将自身的延时起始时间置0，重新开始随机延时。在标签消息中加上从阅读器的ID让后台能分辨标签消息来源于主阅读器或从阅读器；更新延时起始时间可尽量减少从阅读器发送Request的次数，也减少了主阅读器响应Occupy的次数，增加了主阅读器的有效工作时间，同时减少了阅读器的能耗开销。而一旦延时时间内没收到标签消息，延时结束的从阅读器就可以开始身份竞争。这样既保证了主阅读器的有效工作时间，又保证了每个阅读器都有机会竞争成为主阅读器。

后台系统的工作主要有：

1) 发送Sleep信号和数据请求。

后台系统为每个阅读器维护两个时间戳，一个时间戳记录该阅读器最近一次竞争成为主阅读器的时间，称为最近主阅读器时间戳(latest master timestamp，LMT)，每次阅读器竞争成为主阅读器且在读写周期开始前，便向后台发送一个消息来更新LMT值；另一个时间戳记录该阅读器最近一次作为从阅读器转发标签消息的时间，称为最近从阅读器时间戳(latest slave timestamp，LST)，这个时间戳可以根据后台收到的 ${\rm{Hash(IDTag}} \oplus {\rm{Sk}}||{\rm{IDreaderA}}||{\rm{IDreaderB)}}$ 更新LST值。这两个时间戳都是后台本地时间，不需要进行阅读器和后台系统的时间同步。根据这两个时间戳，可以得到两个时间差值，定义如下：

式中，LT(local time)为后台系统本地时间；DMR描述了阅读器有多长时间没有成为主阅读器；DSR描述了阅读器多长时间没有作为从阅读器辅助其他阅读器工作。根据这两个时间差值可以了解每个阅读器的工作情况，若都大于各自的门限值则表明该阅读器一段时间内没有实际有效的工作，后台系统便向该阅读器发送Sleep信号，使其休眠。当再次有数据请求到达该阅读器时，再将该阅读器打开(如仿真实验中两个门限值都设为10 s，每5 s计算一次DMR和DSR)。

2) 对标签消息进行分析，并根据分析结果做出响应。

① 后台系统根据消息格式判断消息来源。如果收到的标签消息格式为${\rm{Hash(IDTag}} \oplus {\rm{Sk}}||{\rm{IDreaderA)}}$，表明消息来自主阅读器，则判断ID_readerA是否合法。如不合法，则广播通知所有阅读器此后收到的readerA消息都丢弃；若ID_readerA合法，则判断ID_Tag是否合法。如ID_Tag不合法，阅读器就不响应该标签消息，否则响应该标签消息。

② 如果收到的标签消息格式为${\rm{Hash(IDTag}} \oplus $${\rm{Sk}}||{\rm{IDreaderA}}||{\rm{IDreaderB)}}$，表明消息来自从阅读器，则先判断ID_readerB是否合法：如ID_readerB不合法，则后台收到阅读器ID为ID_readerB的消息都丢弃；如ID_readerB合法，则执行步骤①的流程。

该算法使用MATLAB进行仿真，仿真主要对两个指标进行比较：系统吞吐量和系统效率。

Request_i表示第i个阅读器发送的Request请求数，Request_Suci表示第i个阅读器发送且被标签正确回复的Request请求数，Time表示仿真进行的时间。

系统吞吐量定义为：

系统效率定义为：

由于RFID系统的工作模式基本上是阅读器请求越多，请求最终被成功响应的也越多，同时考虑到响应同样数量的请求有时间和成功率的差异，所以选择系统吞吐量和系统效率作为测试指标。为体现该算法的性能，将该算法与已有的Pulse^[1]和ALOHA^[2]算法在同等条件下进行仿真比较。

MATLAB仿真条件为：阅读器数量分别为10、20、30、40、50、60、70。标签数量为400，标签分布在10 mx10 m的范围内。侦听时间选择15 ms，Tmin等待时间也为15 ms，backoffs选择在0～15 ms之间的一个随机值，DMR和DSR门限设为10 s，每5 s计算一次DMR和DSR，仿真时间Time为300 s。图 3给出了3种算法的系统吞吐量的比较曲线。

图3

图3系统吞吐量的比较曲线

图 3中，可以看出ALOHA算法在多阅读器环境中的吞吐量明显低于其他两种算法。ALOHA算法由于每次阅读器收到请求都会立即读写标签，而忽视了其他阅读器在数据信道工作的可能性，碰撞发生频繁，吞吐量较低。IC²RA算法随着阅读器数量的增加较Pulse算法体现出明显优势，这是因为在IC²RA算法中从阅读器协助主阅读器的读写工作的缘故。在IC²RA中，当从阅读器将标签信息转发给后台系统后，后台会对信息进行处理和判断，如果信息合法，后台会立即通知主阅读器读写该标签，从而使主阅读器在一个读写周期能识别多个标签，提高了系统吞吐量。

图 4是系统效率的比较曲线。在系统效率的比较中，ALOHA算法依然明显低于其他两种算法。10个阅读器时效率为9%，70个阅读器时只有4%。IC²RA算法和Pulse算法相差无几，两种算法对阅读器请求的响应成功率都比较高，在10个阅读器时Pulse算法效率几乎为100%，IC²RA算法效率为95%。随着阅读器数量的增加，Pulse和IC²RA算法效率相差不大，但是IC²RA算法的效率更为稳定，在70个阅读器环境中IC²RA算法效率依然有94%。

图4

图4系统效率的比较曲线

本文针对阅读器防碰撞问题进行探讨，提出了一种基于载波监听的阅读器防碰撞算法，该算法采用多阅读器之间进行局部竞争的方法确定工作阅读器，竞争成功者开始读写工作，这相比于全局协调的方法效率更高。该算法利用阅读器网络中的闲置阅读器协助工作阅读器的读写工作，以提高系统效率。仿真结果表明该算法的吞吐量和系统效率相比于已有算法有一定的优势。