王永华，杨 健，詹宜巨，万 频

(1. 广东工业大学自动化学院 广州 510006；2. 中山大学工学院 广州 510006)

RFID网络中读写器冲突指由一个读写器检测到的、由另一个读写器引起的干扰，包含两种情况。读写器-读写器冲突频率冲突和读写器-标签冲突[1]。读写器频率冲突发生在两个或两个以上读写器同时使用相同的频率与标签通信时；读写器-标签冲突是指两个或更多读写器同时与一个标签通信时发生的冲突。目前解决读写器冲突的方法主要有EPC CLASS-1 Gen-2标准[2]、ETSI EN 302 208标准[3]、PULSE[4]、Colorwave算法[5]、DiCa算法[6]等，但均未彻底避免读写器冲突。为了解决RFID网络中的读写器冲突，本文在参考自组织网络中的多址接入协议[7-9]基础上提出了一种RFID系统中自适应多信道读写器冲突避免MAC(RCA)协议。其主要思想为：读写器选取各自业务信道并向其他读写器声明该结果，而不是等待其他读写器给它分配业务信道，采用资源预约方式，使读写器在异步方式时灵活、有效地在多个时段和频段工作。

1 RCA协议

假定系统中各读写器均有一个互不相同的ID号，分别为1，2，，N，其中，N为系统中的读写器总数。将可用的频率资源等分成2M－1份，其中的一个频率作为控制信道，用于各读写器发送预约分组，从而完成它的信道获取和通信接入过程，其余2M个信道作为业务信道。读写器用其中的偶数信道，标签用相应的奇数信道通信。假定读写器的控制信道的通信距离大于数据信道的2倍，可以有效避免RFID网络中的隐藏终端问题[6]。

邻读写器指2个读写器有覆盖区域重叠并且能相互通信。在RCA协议中，所有读写器共用控制信道，并且每个读写器用一个信道使用表记录业务信道的状态(忙闲)和必要的参数。假设读写器能够通过控制信道交换控制信息，逐个发现自己的邻居读写器并建立连接，每个读写器维护一个邻居读写器表和非相邻读写器列表。

邻居读写器表内记录与该读写器能发生冲突的相邻读写器，非相邻读写器表则记录不会与其发生冲突的读写器。每个读写器预先监测记录邻居读写器的通信及信道使用情况，从而自适应地为自己选择发送数据的信道及时刻，并且利用在控制信道上发送的RTS数据通知其他读写器，从而实现无冲突的通信。

网络内的读写器可以充分利用多个业务信道避免频率干扰，此外业务信道的空分复用机制还大大提高了信道利用率。

图1 RTS帧和COL帧格式

RTS和COL帧格式如图1所示。其中，读写器编号指发送信息的读写器编号。

RAC协议的优点是只有控制信息才有可能发生碰撞，请求通信的读写器一旦成功发送了RTS，并且未出现碰撞，则开始与标签通信，之后它将不会干扰其他读写器或被其他读写器所打断。

1.1 读写器接入过程

当一个读写器需要与标签通信时，它监测控制信道，并在控制信道空闲一段时间后准备接入信道。为了避免多个读写器的分组碰撞，读写器还会按照某种退避算法再随机延迟一段时间，若控制信道仍然空闲，此时该读写器发送RTS请求，通知相邻读写器将使用的信道，并继续侦听控制信道一段时间(为一个往返时间+其他读写器发送COL信号所需的时间)。在没有RTS冲突，并且未收到COL信号的情况下，读写器进入与标签通信状态，然后相邻读写器进入延迟状态并监测控制信道。如果有冲突或相邻读写器处于通信状态, 则会收到相邻读写器发送的冲突信号，并立即随机延迟，尝试选择其他未用信道并广播，直至没有冲突发生为止，如图2所示。

图2 读写器接入过程

最后，各读写器交换并存储整个系统内读写器信道使用情况表。读写器的移动可能导致占用相同发送信道的两个读写器变成相邻，其公共邻读写器或它们本身会通过监测控制信道发现这种情况，先发现者告知ID号更大的读写器延迟，然后重新接入。在这期间两个读写器的数据通信有可能造成冲突，但是从上述过程中可以看出，这段时间非常短暂。

2 协议模型

设RTS的发送时间为 ，读写器与标签的通信时间的平均长度为δ>1，γ<δ<∞；信道上的传播时延为 ，τ<γ。各读写器通信需求符合参数为 的泊松过程。定义系统输出S为读写器利用率。

定义相邻性参数为：

发生RTS冲突的情况是当一个读写器发送一个RTS后，在Y时间内一个或者多个相邻读写器也发送RTS，其中0

由于算法中的读写器在成功发送RTS后可以保证无冲突通信。由图2可知成功发送期时间长度为：

另一种发送失败的情况是有邻居读写器在通信，此时一个读写器发送RTS后，将收到COL信号。所以发送失败期2的时间长度为：

考虑读写器i在时刻t开始与标签通信，首先发送RTS，易知成功发送RTS的条件为：1) 与读写器i相邻的读写器均处于未通信状态。2) 读写器i相邻的读写器在持续 时间内都不在公共信道上发送RTS。因为读写器i发出RTS信息经传播时延τ后，其他读写器也会收到该RTS信息，此时即使有通信需求也不再发送RTS，而是选择退避。3) 读写器有空闲的业务信道可选择，即不会与相邻的读写器信道冲突。由于该协议中，相邻读写器不能同时通信，所以读写器有空闲信道可选择的概率为1。

可得到成功发送RTS的概率为：

读写器处于忙的状态为两种情况：一种是成功与标签通信，另一种是发送RTS失败。所以平均忙碌期为：

有效的读写器利用是指读写器成功与标签通信的时间，即:

协议中，读写器在成功通信完毕后或者发送RTS失败后均需要退避。在成功通信后，等待时间是γ，发送RTS失败后等待时间是2。所以平均空闲期为：

3 结果分析

3.1 RTS分组长度变化时的系统输出

图3给出了每个读写器均有5个相邻读写器，读写器与标签的通信时间平均长度δ=1.5，给定不同的RTS分组时间长度γ时，系统输出S随泊松参数的变化情况。从图中可以看出，随着RTS分组时间长度γ的增大，协议的输出将会减少。这是由于RTS分组时间长度γ的增大会使读写器接入时间增加，进而导致系统输出S减少。

图3 RTS分组长度变化时的系统输出

3.2 通信时间变化时的系统输出

图4 通信时间变化时的系统输出

在每个读写器周围均有5个相邻读写器、RTS分组时间长度γ=0.1的情况下，给定不同的读写器与标签的通信时间γ时，系统输出S随泊松参数γ的变化情况如图4所示。随着读写器与标签的平均通信时间δ的增大，系统输出S将会增大，这是因为读写器在成功接入后可以保证无冲突的通信，减少由冲突引起的系统开销，增加读写器的利用率。

3.3 相邻读写器数量变化时的系统输出

图5 相邻读写器数量变化时的系统输出

3.4 与其他算法对比

图6 输出对比

4 结 论

为解决异步的分布式读写器网络中的读写器冲突，本文提出了一种自适应多信道读写器冲突避免多址接入协议。该协议为异步协议，基于预约和多信道思想，可以有效解决读写器冲突问题。读写器和标签建立通信前先发送RTS，若无冲突状态则选择一个业务信道开始与标签通信，否则进行退避。该协议避免了相邻读写器同时与标签通信，解决了读写器-标签干扰。同时，多个信道的通信机制以及频率的可空分复用避免了读写器频率干扰的发生。对该协议分析表明，在RTS数据长度较短、读写器平均通信时间较长、泊松参数λ较小时，读写器利用率较高。

[1] ENGELS D W, SARMA S E. The reader collision problem[C]//Proceedings of IEEE International Conference on Systems, Man and Cybernetics. Hammamet, Tunisia:IEEE, 2002: 6-9.

[2] EPCGlobal. EPC radio-frequency identity protocols class-1 generation-2 UHF RFID protocol for communications at 860-960 MHz version 1.0.9[EB/OL]. [2005-03-10].http://www.epcglobalinc.org/Standards.2005.

[3] ETSI. ETSI EN 302 208-1 V1.1.1[EB/OL]. [2004-05-22].http://www.esti.org.2004.

[4] BIRARI S M, IYER S. PULSE: a MAC protocol for RFID networks[C]//1st International Workshop on RFID and Ubiquitous Sensor Networks (USN). Nagasaki, Japan: [s.n.],2005: 1036-1046.

[5] WALDROP J, ENGELS D W, SARMA S E. Colorwave: an anti-collision algorithm for the reader collision problem[C]//IEEE Wireless Communications and Networking Conference (WCNC). New Orleans, Louisiana,USA: IEEE, 2003: 1701-1704.

[6] HWANG K, KIM K, EOM D. DiCa: Distributed tag access w ith collision-avoidance among mobile RFID readers[C]//Conferenceon: Embedded and Ubiquitous Computing– EUC.[S.l.]: IEEE, 2006: 413-422.

[7] 刘凯, 李建东, 周亚建. 多跳分布式无线网络环境下自适应获取冲突避免的多址接入协议[J]. 计算机学报, 2002,25(10): 1046-1051.

LIU Kai, LI Jian-dong, ZHOU Ya-jian. Multiple access protocol for adaptive acquisition collision avoidance in multihop w ireless Ad hoc networks[J]. Chinese Journal of Computers, 2002, 25(10): 1046-1051.

[8] 刘凯, 李建东, 张文柱. 一种用于多跳分布式无线网络的多址接入协议及其性能分析[J]. 计算机学报, 2003, 26(8):925-933.

LIU Kai, LI Jian-dong, ZHANG Wen-zhu. A novel multiple access protocol for multihop w ireless Ad hoc networks[J].Chinese Journal of Computers, 2003, 26(8): 925-933.

编 辑 漆 蓉