防碰撞技术研究与分析.doc

防碰撞技术研究与分析

在RFID系统通信的过程中，防碰撞技术是实现多标签和多读写器环境下通信质量和性能的保障，也是保证数据传输完整性的关键技术。这需要克服外界的各种干扰和多标签和多个读写器同时占用信道发送数据产生碰撞冲突。
RFID系统中的碰撞与冲突
射频识别别系统工作时，在读写器的作用范围内，可能会有多个射频标签同时存在。此外，在多个读写器和多标签的射频识别系统中，存在着两种形式的碰撞：一种情况是称为多标箍碰撞即同一读写器同时收到多个不同标签返回的数据，如何区别每个标签的信息；另一种情况是多读写器冲突即同一标签同时收到不同读写器发出的命令，如何区分不同读写器的命令操作信息。

在单读写器和多个射频标签组成的系统中，存在着两种不同的基本通信形式：从读写器到射频标签的通信称为无线电广播、从射频标签到读写器的通信称为多路存取。
在无线通信技术中，通信冲突的问题是长久以来存存的问题，但同时也研究出许多相应的解决方法。基本上有四种不同的方法：空分多路(SDMA)，频分多蹄(FDMA)．码分多路(CDMA) 和时分多路(TDMA)。
在射频识别系统中，主要是采用时分多路法的原理和思想，使每个标签在单独的某个时隙内占用信道与读写器进行通信，防止碰撞产生，使数据能够准确地在读写器和标签之间进行传输。以下介绍基于时分多路思想的两种多标签防碰撞算法，ALOHA法和二进制算法，并分析它们的改进思想和实现流程。
ALOHA是一种简单的TDMA的算法，这种算法多采取标签先发言的方式，即标签一进入读写器的阅读区域就自动向读写器发送自身的ID，标签和读写器间开始通信。
纯ALOHA存在一个严重的问题是存在错误判决问题，即对同一个标签，如果多次发生冲突，将导致读写器出现错误判断，认为这个标签不在自己作用范围。另外一个问题是数据帧的发送过程中冲突发生的概率很大，其冲突期为2帧时间，如下图所示，存在部分冲突和完全冲突两种冲突期。

若G为平均交换的数据包量，T为观察时间，那么平均交换的数据包量G可由数据包的传输时间τ计算出来，见式(1)，n为系统的标签数量，rn是在观察时间T内由标签n发送的数据包数量；吞吐率S指无错误的传输数据包，传输通路的平均吞吐率S和交换数据包量之间的关系，见式(2)。当G=0.5时，S的最大值为18.4％，可参见下图虚线所示。
式(1) 式(2) 式(3)

为提高系统吞吐率，可以划分时隙，只在规定的同步时隙内才传输数据。称为时隙ALOHA（S-ALOHA法），这种情况下，所有的标签必须同步，且由读写器控制。由于此时数据包的传送总是在同步的时隙内才开始，所以发生冲突的时间区域缩短到T=τ，时隙ALOHA法的吞吐率S，如公式(3)所示。当G=I时，吞吐量S达到最大值为36.8％，可见上图实线所示。
S-ALOHA法与纯ALOHA算法相比，碰撞的区间缩小了一半，信道利用率提高了一倍。在S-ALOHA算法的基础上，将时间域进一步离散，且把N个时隙打包成一帧，在每帧中标签只随机发送一次信息，该方法称为帧时隙ALOHA(FS-ALOHA)，该方法需要读写器进行同步。每帧的最大时隙数N可以为固定，也可以动态变化。时隙数N不变的算法为帧长固定ALOHA算法(FFS-ALOHA)，N=4，见下图。将最大时隙数N动态变化的算法称为动态帧时隙ALOHA(DFS-ALOHA)，N=2，4，3，见下图。动态帧时隙ALOHA算法是读写器为适应下个周期的标签信息清点，动态地增大或者减小一帧中的时隙数，最大限度的减小碰撞几率，提高标签清点的效率。

二进制搜索算法及其改进思想
二进制树搜索算法的基本思想是将处于冲突的标签分成两个子集0和1，先查询子集0，若没有冲突，则正确识别标签，若仍有冲突则再分裂，把子集0分成00和01两个子集，依次类推，直到识别出子集0中的所有标签，再按此步骤查询子集1，如下图所示。

该算法有3个关键要素：1、选用适当的基带编码(易于识别碰撞)；2、标签序列号的唯一性；3、设计一组有效的指令规则，高效、迅速地实现选卡。
二进制搜索算法系统采用位编码法一曼彻斯特编码(Manchester)，该编码可以有效辨认出读写器中数据冲突的比特位置。Manchester编码的0和1是在一个位窗口电平的改变表示。数据传输过程中没有变化的状态是不允许的，作为错误被识别。当有两个或两个以上标签同时发送它们的唯一标志符中有不同的值时，则接收数据流中部分位的上升沿和下降沿相互抵消。从而没有变化的状态指示出错误，算法发现碰撞比特位，如下图所示。

在基于标签ID的二进制搜索算法中，标签ID用K位二进制串表示，算法流程图见下图。

假设有6个标签ID分别为1010101 1，l 1001010，00101 101，1001001 1，
01101101，10110010，上表说明了二进制搜索算法的实现过程。
但用于传输识别序列号的数据量很大，识别时间也会相应增长，动态二进制搜索算法正是基于这样的考虑而提出的。动态二进制搜索算法在读写器检测到冲突后，只发送当前确定位数查询前缀，而具有相同确定比特位编码的标签响应只发送其余比特位。因而，动态二进制搜索算法大大减少算法系统消耗在序列号上的传送时间，提高了系统的执行效率。正是从这个角度考虑，余松森提出了修剪枝的二进制树形搜索算法，杜海涛等人提出了基于返回式二进制树形搜索算法。

多读写器防冲突机制
目前对RFID系统防冲突算法的研究主要是标签之间的防冲突算法，对读写器防冲突算法研究不是很多，目前主要算法有Colorwave算法、Q-Learning算法、Pulse算法等。见下图。

(1)图着色(Colorwave)算法
Colorwave算法通过给读写器分配不同的颜色来避免读写器之间的冲突，是基于TDMA的一种分布式算法。该算法规定每个读写器从0到最大颜色数(maxColors)中随机选择一个颜色(时隙)传输数据。如果发生了冲突，读写器选择一个新的颜色，并且发送一个较小的控制包给它所有邻近的读写器，告之它选择了一个新的颜色。如果邻近的读写器有同样的颜色，它重新选择一个新的颜色并发送控制包。这样一直继续下去。这种转换和驻留的动作就被称为kick。每个读写器跟踪当前的时隙颜色。
该算法需要所有读写器之间的时间同步，同时还要求所有的读写器都可以检测RFID系统中的冲突。然而，若标签不具有冲突检测功能，需多个读写器联合检测在标签处发生的冲突。另读写器移动将会重新分配时隙，重新分配的时隙传播整个网络，将会导致整个系统的无效。
(2)HIQ算法
该算法是一个分等级的在线学习算法，通过学习读写器冲突模型，动态的解决RFID系统中读写器冲突问题，有效地分配频率给读写器。其思想类似于无线传感器网络中分簇算法。
Q学习算法多层结构如下图所示。读写器发送冲突消息给读写器级服务器层(R-Server)。然后单个的R-server分配资源给它的读写器，这样的方式可使它们之间的相互通信不出现干扰。R-Server通过Q学习服务器(Q-server)被分配到频率和时隙。根Q-server具有所有频率和时隙资源的全部知识，并且能分配它们。Q-server不像R-Server一样，没有单个读写器问约束关系，这种关系通过该层下面的服务器之问的相互作用来推断。

Q学习算法不适合应用在拓扑结构变化比较频繁的读写器网络中，即移动读写器网络中。该算法由于读写器级服务器任务繁重，会造成该读写器的能量消耗远大于其它读写器，也会可能导致该读写器由于能耗过量而不能工作；协议保持多层结构需要额外的管理开销；Q学习假定读写器的冲突检测不在读写器相互的侦听范围内。然而，并不是所有的冲突都能检测到，这将导致协议的不正确操作。
(3)Pulse算法
该算法将通信信道分为控制信道和数据信道两个部分。控制信道用于读写器之间的通信，发送忙音信号。数据信道用于标签与读写器之间通信。实现较简单，比较适合于动态拓扑变化频繁的网络。
除了上面涉及到的算法之外，还有控制读写器读写范围、减小读写器的发送功率、分时与色波结合等方法来减小读写器之间的冲突。

简要说明产牛冲突机理，重点在第5章中分析超高频系统的密集读写器模式。

以下简要说明读写器与标签的通信方式