登录
注册
RFID读写器抗冲突问题研究
作者：王爱明 李艾华 穆晓曦
来源：RFID世界网
日期：2011-03-14 11:04:27
摘要：当一个RFID读写器发射的信号和另一个读写嚣发射的信号相干扰时，就会产生读写器冲突。除了误操作，读写器冲突的同时，使射频识别系统总的阅读速率减慢，而且这些问题在移动或手持式读写器中更加严重。读写器抗冲突算法，通过在控制通道上周期地发送信标以达到抗冲突的目的。该算法不仅适用于固定式读写器，同时还适合移动或手持式读写器的射频网络。
1 读写器的干扰
读写器的冲突是指由一个读写器检测到，并且由另一个读写器所引起的干扰。它主要有三种表现形式。
(1)读写器与读写器之问的干扰：当一个读写器发射较强的信号与一射频标签反射回的微弱信号相干扰时，就引起了读写器与读写器之间的干扰，其示意图如图1所示。读写器R1位于读写器R2干扰区。从射频标签Tl反射回的信号到达读写器R1，很容易被读写器R2发射的信号干扰。这种干扰即使两个读写器阅读范围没有重叠也有可能产生。
(2)多读写器到标签问的干扰：当多个读写器同时阅读同一个标签时引起了多读写器到标签间的干扰，如图2所示，两个读写器阅读范围重叠。从读写器Rl和R2发射的信号可能在射频标签Tl处产生干扰。在这种情况下，标签T1不能解密任何查询信号并且读写器R1和R2都不能阅读T1。因为读写器冲突，读写器Rl能阅读标签T2和T3，但是不能阅读标签Tl，因此，读写器R1指示两个射频标签存在而不是3个。
2 相关工作和研究
2．1 读写器冲突的主要特点
读写器冲突主要有下列特点：
①隐藏节点问题是读写器冲突问题的一个方面。两个读写器不在相互侦听范围内而在标签处干扰时，使射频识别网络中正常的载波侦听无法工作。
②当多个读写器询问／发射的信号在某射频标签处冲突时，该点的信号会变得非常杂乱并且射频标签不能再接收任何读写器询问／发射的信号。
③所研究的射频标签是被动式标签，因此标签本身既不能调整也不能主动与读写器通信以避免冲突。射频标签是在被读写器询问信号激活后才能通信。
2．2 相关的多址机制
常用的多址机制不能直接应用在射频识别系统中，因为：
①FDMA。FDMA方式中，读写器使用不同的频率和射频标签通信。由于射频标签没有频率调谐电路，因此射频标签不能选择一个特定的读写器与其通信。如果射频标签增设频率调谐电路功能，将大大增加射频标签的成本，因此FDMA不适合应用在射频识别系统中。
②TDMA。TDMA方式中，读写器被分配不同的时隙，以避免读写器同时询问／发送射频信号。这类似于图论中的图形着色问题，是一个NP-hard问题。在移动式网络中，没有干扰的读写器因为移动靠近而出现干扰，需要重新分配时隙。动态的分配时隙减小了RFID系统阅读速率。
③CSMA。RFID网络，像其他的无线网络一样，存在隐藏节点问题。读写器不在互相侦听范围内在标签处发生干扰，因此仅仅依靠载波侦听无法避免RFID网络中的冲突问题。
④CDMA。CDMA需要在射频标签上增设额外的电路，大大增加了标签的成本，并且分配码给所有网络中的标签是一件非常复杂的工作。因此CDMA不是一种成本低且有效的方案。
2．3 相关的抗冲突机制
常见的抗冲突协议，如RTS-CTS，不能直接应用在RFID系统中，因为：
①传统的无线网络，只有一个节点回发CTS信号给发送者。然而在RFID系统中，如果读写器广播发送一RTS信号，所有在读写器阅读范围内的标签都得回发CTS信号给发送者读写器。这需要给这些CTS信号设计另外的抗冲突机制，将使这种协议更加复杂。
②有可能因为冲突，一些标签(如T1)没有接收到RTS信号而另外一些标签(如T2)接收到了RTS信号。在这种情况下，从T2回发的CTS信号不能确定在读写器的阅读范围内没有冲突。如何确定读写器接收了在其阅读范围内的所有标签的CTS信号，对于读写器是否存在冲突是非常重要的。
2．4 相关的读写器抗冲突方法
2.4.1 UHF第二代标签标准：UHF第二代标签标准是由EPCglobal制定的。该标准把读写器和射频标签的信号传输分割开，这样冲突只能在标签与标签间或者读写器与读写器问发生。这种分割使读写器和射频标签信号在不同的频道上传输，解决了读写器问的干扰。然而，标签没有频率选择性。因为当两个读写器用不同的频率同时与标签通信时，标签不能调谐到特定的频率．所以会在标签处发生冲突。因此该标准仍存在多读写器到标签间的干扰。
2.4.2 Colorwave算法：Colorwave算法是一种基于TDMA分布式算法。该算法规定每一个读写器从0到maxColors中随机选择一个时隙(颜色)传输数据。如果发生了冲突，读写器选择一个新的时隙(颜色)，并且发送一个kick(较小的控制包)给它所有邻近的读写器，告诉它们它选择了一个新的时隙(颜色)。如果邻近的读写器有同样的时隙(颜色)，它重新选择一个新的时隙(颜色)并发送一个kick。这样一直继续下去。这种转换和驻留的动作就被称为kick。每一个读写器跟踪当前的时隙是什么颜色。Colorwave算法要求在读写器之间时间同步，同时假定读写器能够检测到RFID系统中的冲突。然而，仅仅用一个读写器检测在标签处发生的冲突是不可行的，除非标签也参加冲突检测，并且读写器移动将会重新分配时隙，重新分配的时隙传播整个网络，将会导致整个系统的无效。
2.4.3 ETSl EN 208标准：ETSI EN 208是一个为RFID读写器开发的标准，它基于CSMA协议的“先听再说”。读写器首先在一特定的小时间段里侦听数据通道里任何正在进行的通信。如果在那段时间里，数据通道空闲，它将阅读标签；如果通道忙，它随机选择一段退避时间。然而，正如前面所讲，读写器仅仅依靠载波侦听不能检测到冲突。
2.4.4 Q学习算法：Q学习算法提出了一种HiQ、多层、在线的学习算法。该算法通过学习读写器的冲突模式和有效地分配频率给读写器，动态地解决RFID系统中读写器的冲突问题。Q学习算法多层结构如图4所示。读写器发送冲突消息给读写器级服务器层(R-Server)。然后单个的R-server然后分配资源给它的读写器，这样的方式可使它们之间的相互通信不出现干扰。R-Server通过Q学习服务器(Q-server)被分配到频率和时隙。根Q-server具有所有频率和时隙资源的全部知识，并且能分配它们。Qserver不像R-Server一样，没有单个读写器问约束关系，这种关系通过该层下面的服务器之问的相互作用来推断。
①协议保持多层结构需要额外的管理开销。
②对于移动的读写器来说，网络拓扑结构不确定的变化将会改变Q学习算法的多级结构。这就需要重新分配时隙，将花去更多的时间并使系统无效。
③Q学习假定读写器的冲突检测不在读写器相互的侦听范围内。然而，并不是所有的冲突都能检测到，这将导致协议的不正确操作。
④使用时隙需要所有的读写器同步，这种同步将是整个系统的额外开销。
综上所述，这些读写器抗冲突方法不适合具有移动读写器的RFID网络系统。因此，必须寻求一种具有实际意义且有效的适合各种情况的RFID系统。
3 一种减少读写器冲突的新算法
3．1 新算法的提出
在设计读写器抗冲突协议时，要考虑的一个重要因素就是射频标签是被动式的，因此不能参与抗冲突；同时任何增加给标签的新功能都将增加标签的成本。因此希望寻求一种标签不参与的抗冲突协议。
RFTD网络存在隐藏节点问题，如图5所示。R1和R2不在相互的侦听范围内，但是在T处从读写器R2发射的信号与从读写器R1发射的信号发生干扰。在这种情形下，R1和R2间需要一个通知机制。这样，当Rl和T正在通信，R2被通知R1的通信，因此R2可以延迟与射频标签的通信。我们把这种通过广播形式发送的消息称为“信标”。当一个读写器正在与射频标签通信时，它将周期性地在一个独立的控制通道里发送信标。
3.2 新算法信标的帧格式
新算法只为读写器设计，因为射频标签不参与抗冲突活动。信标的帧格式如下：
②源地址，包括发射信标的读写器的地址。在该结构中信标没有目标地址，因为信标是在控制通道广播发送。
③CRC检验，用来检测错误和校正，是数据包循环冗余检验部分。
3．3 新算法的工作流程和步骤
图6为该算法的工作流程图，主要包括下列步骤：
②读写器如果在时长tmin消耗完了还没有接收到任何信标，读写器推断出在其附近没有其他的读写器在阅读标签。于是读写器进入竞争阶段，并且从时间间隔[OACW]中选择一随机退避时间。如果它选择i，那么读写器必须在竞争状态等待i个信标时间间隔时间。如果读写器现在接收到一个信标，它就丢失现在的周期，在下一个周期等待。例如在tmin时长接收到了信标，它将在下一个tmin时长等待。如果随机退避时间结束，读写器还没有接收到信标，该读写器就认为没有其他的读写器和它竞争，因此该读写器就在控制通道上发送信标，并且在数据通道上和标签通信。该随机退避时间帮助读写器问避免产生冲突。否则，许多其他读写器在等待时长tmin后会同时发送信标。随机退避时间是多倍的信标间隔长，提高了竞争的公平性。
③当读写器与标签通信时，读写器在控制通道上每隔一信标间隔时长发送一个信标。该信标通知邻近的读写器，以便阻止它们与标签的通信，这样避免了冲突。在与标签通信结束后，读写器重新回位到等待状态，继续余下的周期。
④每次读写器发送一信标，它首先检测控制通道。如果控制通道忙，就一直检测下去。一旦检测到控制通道空闲，读写器就等待一随机延迟并再一次检测通道和发送信标。该随机延迟是多倍的信标传播延迟，以避免冲突。否则，许多读写器在信道空闲时会同时发送信标。算法中的竞争延迟及发信标前延迟与通常的无线网络中的退避相似。一旦控制通道检测到空闲竞争延迟和发信标前延迟，计数器减少；当检测到发送时，计数器停止计时；当控制通道检测到空闲后，计数器重新计数。并且，如果读写器在竞争阶段的退避期间接收到信标，它就会存储余下的退避计算时间等待下一次机会。例如，在tmin时间内读写器接收了信标，当读写器重新进入竞争阶段时，读写器利用余下的退避时间。这样做的目的是提高读写器间的公平。
4 结论
分布式读写器抗冲突算法，通过在控制通道上周期地发送信标来达到抗冲突的目的。与CSMA机制相比，它可以降低读写器冲突1％～2％，提高读写器的阅读速率高达98％。它需要读写器较少的花销，完全不需要射频标签参与抗冲突。该算法同时还适合移动或手持式阅读器的射频网络，具有重大的实用价值。
读写器的冲突是指由一个读写器检测到，并且由另一个读写器所引起的干扰。它主要有三种表现形式。
(1)读写器与读写器之问的干扰：当一个读写器发射较强的信号与一射频标签反射回的微弱信号相干扰时，就引起了读写器与读写器之间的干扰，其示意图如图1所示。读写器R1位于读写器R2干扰区。从射频标签Tl反射回的信号到达读写器R1，很容易被读写器R2发射的信号干扰。这种干扰即使两个读写器阅读范围没有重叠也有可能产生。
(2)多读写器到标签问的干扰：当多个读写器同时阅读同一个标签时引起了多读写器到标签间的干扰，如图2所示，两个读写器阅读范围重叠。从读写器Rl和R2发射的信号可能在射频标签Tl处产生干扰。在这种情况下，标签T1不能解密任何查询信号并且读写器R1和R2都不能阅读T1。因为读写器冲突，读写器Rl能阅读标签T2和T3，但是不能阅读标签Tl，因此，读写器R1指示两个射频标签存在而不是3个。
图１ 读写器到读写器间的干扰
图２ 读写器到标签间的干扰
图３ 读写器冲突使载波侦听无效
2 相关工作和研究
2．1 读写器冲突的主要特点
读写器冲突主要有下列特点：
①隐藏节点问题是读写器冲突问题的一个方面。两个读写器不在相互侦听范围内而在标签处干扰时，使射频识别网络中正常的载波侦听无法工作。
②当多个读写器询问／发射的信号在某射频标签处冲突时，该点的信号会变得非常杂乱并且射频标签不能再接收任何读写器询问／发射的信号。
③所研究的射频标签是被动式标签，因此标签本身既不能调整也不能主动与读写器通信以避免冲突。射频标签是在被读写器询问信号激活后才能通信。
2．2 相关的多址机制
常用的多址机制不能直接应用在射频识别系统中，因为：
①FDMA。FDMA方式中，读写器使用不同的频率和射频标签通信。由于射频标签没有频率调谐电路，因此射频标签不能选择一个特定的读写器与其通信。如果射频标签增设频率调谐电路功能，将大大增加射频标签的成本，因此FDMA不适合应用在射频识别系统中。
②TDMA。TDMA方式中，读写器被分配不同的时隙，以避免读写器同时询问／发送射频信号。这类似于图论中的图形着色问题，是一个NP-hard问题。在移动式网络中，没有干扰的读写器因为移动靠近而出现干扰，需要重新分配时隙。动态的分配时隙减小了RFID系统阅读速率。
③CSMA。RFID网络，像其他的无线网络一样，存在隐藏节点问题。读写器不在互相侦听范围内在标签处发生干扰，因此仅仅依靠载波侦听无法避免RFID网络中的冲突问题。
④CDMA。CDMA需要在射频标签上增设额外的电路，大大增加了标签的成本，并且分配码给所有网络中的标签是一件非常复杂的工作。因此CDMA不是一种成本低且有效的方案。
2．3 相关的抗冲突机制
常见的抗冲突协议，如RTS-CTS，不能直接应用在RFID系统中，因为：
①传统的无线网络，只有一个节点回发CTS信号给发送者。然而在RFID系统中，如果读写器广播发送一RTS信号，所有在读写器阅读范围内的标签都得回发CTS信号给发送者读写器。这需要给这些CTS信号设计另外的抗冲突机制，将使这种协议更加复杂。
②有可能因为冲突，一些标签(如T1)没有接收到RTS信号而另外一些标签(如T2)接收到了RTS信号。在这种情况下，从T2回发的CTS信号不能确定在读写器的阅读范围内没有冲突。如何确定读写器接收了在其阅读范围内的所有标签的CTS信号，对于读写器是否存在冲突是非常重要的。
2．4 相关的读写器抗冲突方法
2.4.1 UHF第二代标签标准：UHF第二代标签标准是由EPCglobal制定的。该标准把读写器和射频标签的信号传输分割开，这样冲突只能在标签与标签间或者读写器与读写器问发生。这种分割使读写器和射频标签信号在不同的频道上传输，解决了读写器问的干扰。然而，标签没有频率选择性。因为当两个读写器用不同的频率同时与标签通信时，标签不能调谐到特定的频率．所以会在标签处发生冲突。因此该标准仍存在多读写器到标签间的干扰。
2.4.2 Colorwave算法：Colorwave算法是一种基于TDMA分布式算法。该算法规定每一个读写器从0到maxColors中随机选择一个时隙(颜色)传输数据。如果发生了冲突，读写器选择一个新的时隙(颜色)，并且发送一个kick(较小的控制包)给它所有邻近的读写器，告诉它们它选择了一个新的时隙(颜色)。如果邻近的读写器有同样的时隙(颜色)，它重新选择一个新的时隙(颜色)并发送一个kick。这样一直继续下去。这种转换和驻留的动作就被称为kick。每一个读写器跟踪当前的时隙是什么颜色。Colorwave算法要求在读写器之间时间同步，同时假定读写器能够检测到RFID系统中的冲突。然而，仅仅用一个读写器检测在标签处发生的冲突是不可行的，除非标签也参加冲突检测，并且读写器移动将会重新分配时隙，重新分配的时隙传播整个网络，将会导致整个系统的无效。
2.4.3 ETSl EN 208标准：ETSI EN 208是一个为RFID读写器开发的标准，它基于CSMA协议的“先听再说”。读写器首先在一特定的小时间段里侦听数据通道里任何正在进行的通信。如果在那段时间里，数据通道空闲，它将阅读标签；如果通道忙，它随机选择一段退避时间。然而，正如前面所讲，读写器仅仅依靠载波侦听不能检测到冲突。
2.4.4 Q学习算法：Q学习算法提出了一种HiQ、多层、在线的学习算法。该算法通过学习读写器的冲突模式和有效地分配频率给读写器，动态地解决RFID系统中读写器的冲突问题。Q学习算法多层结构如图4所示。读写器发送冲突消息给读写器级服务器层(R-Server)。然后单个的R-server然后分配资源给它的读写器，这样的方式可使它们之间的相互通信不出现干扰。R-Server通过Q学习服务器(Q-server)被分配到频率和时隙。根Q-server具有所有频率和时隙资源的全部知识，并且能分配它们。Qserver不像R-Server一样，没有单个读写器问约束关系，这种关系通过该层下面的服务器之问的相互作用来推断。
图４ Q学习算法多层结构
①协议保持多层结构需要额外的管理开销。
②对于移动的读写器来说，网络拓扑结构不确定的变化将会改变Q学习算法的多级结构。这就需要重新分配时隙，将花去更多的时间并使系统无效。
③Q学习假定读写器的冲突检测不在读写器相互的侦听范围内。然而，并不是所有的冲突都能检测到，这将导致协议的不正确操作。
④使用时隙需要所有的读写器同步，这种同步将是整个系统的额外开销。
综上所述，这些读写器抗冲突方法不适合具有移动读写器的RFID网络系统。因此，必须寻求一种具有实际意义且有效的适合各种情况的RFID系统。
3 一种减少读写器冲突的新算法
3．1 新算法的提出
在设计读写器抗冲突协议时，要考虑的一个重要因素就是射频标签是被动式的，因此不能参与抗冲突；同时任何增加给标签的新功能都将增加标签的成本。因此希望寻求一种标签不参与的抗冲突协议。
RFTD网络存在隐藏节点问题，如图5所示。R1和R2不在相互的侦听范围内，但是在T处从读写器R2发射的信号与从读写器R1发射的信号发生干扰。在这种情形下，R1和R2间需要一个通知机制。这样，当Rl和T正在通信，R2被通知R1的通信，因此R2可以延迟与射频标签的通信。我们把这种通过广播形式发送的消息称为“信标”。当一个读写器正在与射频标签通信时，它将周期性地在一个独立的控制通道里发送信标。
图５ 新算法控制通道范围
3.2 新算法信标的帧格式
新算法只为读写器设计，因为射频标签不参与抗冲突活动。信标的帧格式如下：
②源地址，包括发射信标的读写器的地址。在该结构中信标没有目标地址，因为信标是在控制通道广播发送。
③CRC检验，用来检测错误和校正，是数据包循环冗余检验部分。
3．3 新算法的工作流程和步骤
图6为该算法的工作流程图，主要包括下列步骤：
图６ 新算法流程图
②读写器如果在时长tmin消耗完了还没有接收到任何信标，读写器推断出在其附近没有其他的读写器在阅读标签。于是读写器进入竞争阶段，并且从时间间隔[OACW]中选择一随机退避时间。如果它选择i，那么读写器必须在竞争状态等待i个信标时间间隔时间。如果读写器现在接收到一个信标，它就丢失现在的周期，在下一个周期等待。例如在tmin时长接收到了信标，它将在下一个tmin时长等待。如果随机退避时间结束，读写器还没有接收到信标，该读写器就认为没有其他的读写器和它竞争，因此该读写器就在控制通道上发送信标，并且在数据通道上和标签通信。该随机退避时间帮助读写器问避免产生冲突。否则，许多其他读写器在等待时长tmin后会同时发送信标。随机退避时间是多倍的信标间隔长，提高了竞争的公平性。
③当读写器与标签通信时，读写器在控制通道上每隔一信标间隔时长发送一个信标。该信标通知邻近的读写器，以便阻止它们与标签的通信，这样避免了冲突。在与标签通信结束后，读写器重新回位到等待状态，继续余下的周期。
④每次读写器发送一信标，它首先检测控制通道。如果控制通道忙，就一直检测下去。一旦检测到控制通道空闲，读写器就等待一随机延迟并再一次检测通道和发送信标。该随机延迟是多倍的信标传播延迟，以避免冲突。否则，许多读写器在信道空闲时会同时发送信标。算法中的竞争延迟及发信标前延迟与通常的无线网络中的退避相似。一旦控制通道检测到空闲竞争延迟和发信标前延迟，计数器减少；当检测到发送时，计数器停止计时；当控制通道检测到空闲后，计数器重新计数。并且，如果读写器在竞争阶段的退避期间接收到信标，它就会存储余下的退避计算时间等待下一次机会。例如，在tmin时间内读写器接收了信标，当读写器重新进入竞争阶段时，读写器利用余下的退避时间。这样做的目的是提高读写器间的公平。
4 结论
分布式读写器抗冲突算法，通过在控制通道上周期地发送信标来达到抗冲突的目的。与CSMA机制相比，它可以降低读写器冲突1％～2％，提高读写器的阅读速率高达98％。它需要读写器较少的花销，完全不需要射频标签参与抗冲突。该算法同时还适合移动或手持式阅读器的射频网络，具有重大的实用价值。
