第九章-射频识别中的碰撞与防碰撞算法

射频识别技术

RFIDTechnology射频识别中的碰撞与防碰撞算法2第10章射频识别中的碰撞与防碰撞算法10.1射频识别系统中的碰撞在多个阅读器和标签的应用场合，会有标签之间或阅读器之间的相互干扰。这种干扰统称为碰撞。为了防止这些碰撞的产生，在RFID系统中需要设置一定的相关命令来解决防碰撞问题---防碰撞命令/算法。

10.1.1标签的碰撞标签有可被识别的唯一信息（序列号）。一个标签位于阅读器的可读范围内---正常应答；多个标签位于阅读器的可读范围内---出现干扰。10.2标签的碰撞

Adhoc网络:（点对点）模式：ad-hoc模式就和以前的直连双绞线概念一样，是P2P的连接。移动通信网络一般都是有中心的，要基于预设的网络设施才能运行。例如，蜂窝移动通信系统要有基站的支持；无线局域网一般也工作在有AP接入点和有线骨干网的模式下。但对于有些特殊场合来说，有中心的移动网络并不能胜任。比如，战场上部队快速展开和推进，地震或水灾后的营救等。这些场合的通信不能依赖于任何预设的网络设施，而需要一种能够临时快速自动组网的移动网络。Adhoc网络可以满足这样的要求。在Adhoc网络中，结点具有报文转发能力，结点间的通信可能要经过多个中间结点的转发，即经过多跳（MultiHop），这是Adhoc网络与其他移动网络的最根本区别。结点通过分层的网络协议和分布式算法相互协调，实现了网络的自动组织和运行。因此它也被称为多跳无线网（MultiHopWirelessNetwork）、自组织网络（SelfOrganizedNetwork）或无固定设施的网络（InfrastructurelessNetwork）。在RFID工业应用中，需要搭建多个阅读器，如仓储管理、零售、图书馆管理等。所有的阅读器形成一个Adhoc网络，需要所有的阅读器周围有一个有限空间，即阅读器的询问区域，标签和阅读器进行通讯。在供应链中一个阅读器管理的覆盖空间在很多方位上会有很多重叠的询问区域，在询问区域交叉的阅读器之间会相互干扰，导致不能够与在询问区域内的标签进行通信。阅读器检测到的或者导致的干扰都成为阅读器的碰撞，有以下三种类型：1阅读器间频率干扰阅读器工作时发射的无线信号功率为30~36dBm，辐射范围较大；而标签背向反射调制的工作方式使得返回信号的强度很小；同时在发射和接收信号的两个阅读器之间会造成干扰，阅读器接收到的标签反射信号的信噪比降低，无法正确读取标签信息。2多阅读器---标签干扰当一个标签同时位于两个或多个阅读器的询问区域内时，多余一个阅读器同时尝试与这个标签进行通信时就会发生标签干扰。vTag3Tag2Tag1Reader2Reader1图10-1多阅读器-标签干扰3隐藏终端干扰两个阅读器的阅读区域没有重叠，但Reader2发出的信号在标签上会干扰从Reader1发出的信号。vTagReader2Reader1图10-2隐藏终端干扰如何避免频率干扰？---阅读器在不同频率上、在使用距离范围内进行另一个操作便可以避免频率干扰；如何避免标签干扰？---在相邻阅读器在不同时间工作时。如何最小化阅读器碰撞？---阅读器防碰撞问题。10.2射频识别系统中的标签防碰撞算法10.2.1通信中的防碰撞算法无线通信技术中，通信碰撞的四种解决防碰撞方法：空分多址(SDMA)、频分多址(FDMA)、码分多址(CDMA)、时分多址(TDMA).1空分多址(SDMA)

概念：利用空间分割构成不同的信道。举例来说，在一颗卫星上使用多个天线，各个天线的波束射向地球表面的不同区域。地面上不同地区的地球站，它们在同一时间、即使使用相同的频率进行工作，它们之间也不会形成干扰。空分多址（SDMA）是一种信道增容的方式，可以实现频率的重复使用，充分利用频率资源。在RFID系统中的实现有两种方法：一，把大量的阅读器和天线的覆盖面积并排的安置在一个阵列中，当标签经过这个阵列时离它最近的阅读器就可以通信，不受到相邻的标签的干扰。多个标签在该阵列中，由于空间的分布可以同时被识别而不会相互影响。二，在阅读器上使用电子控制定向天线，即自适应的SDMA，天线的方向由各个不同方向的偶极子的单个波叠加出来的。2频分多址(FDMA)

概念：把信道频带分割为若干更窄的互不相交的频带（称为子频带），把每个子频带分给一个用户专用（称为地址）。频分复用（FDM）是指载波带宽被划分为多种不同频带的子信道，每个子信道可以并行传送一路信号的一种技术。频分复用技术下，多个用户可以共享一个物理通信信道，该过程即为频分多址复用（FDMA）。FDMA模拟传输是效率最低的网络，这主要体现在模拟信道每次只能供一个用户使用，使得带宽得不到充分利用。

RFID系统中FDMA技术，具有可自由调整的、非发送频率谐振的标签。标签能量的供应及控制信号的传输有若干个供选择的频率及可以使用最佳的频率，缺点为每个接收通路必须由自己单独的接收器提供，阅读器的费用高。3码分多址(CDMA)

概念：不同用户传输信息所用的信号不是靠频率不同或时隙不同来区分，而是用各自不同的编码序列来区分，或者说，靠信号的不同波形来区分。如果从频域或时域来观察，多个CDMA信号是互相重叠的。CDMA是利用不同的码序列分割成不同信道的多址技术。在CDMA蜂窝通信系统中，用户之间的信息传输是由基站进行转发和控制的。为了实现双工通信，正向传输和反向传输各使用一个频率，即通常所谓的频分双工。无论正向传输或反向传输，除去传输业务信息外，还必须传送相应的控制信息。为了传送不同的信息，需要设置相应的信道。但是，CDMA通信系统既不分频道又不分时隙，无论传送何种信息的信道都靠采用不同的码型来区分。类似的信道属于逻辑信道，这些逻辑信道无论从频域或者时域来看都是相互重叠的，或者说它们均占用相同的频段和时间。

CDMA的频带利用率低，信道容量较小，地址码选择较难、接收时地址码捕获时间较长，其通信频带和技术复杂性在RFID系统中难以应用。4时分多址(TDMA)

概念：时分多址是把时间分割成周期性的帧(Frame)每一个帧再分割成若干个时隙向基站发送信号，在满足定时和同步的条件下，基站可以分别在各时隙中接收到各移动终端的信号而不混扰。同时，基站发向多个移动终端的信号都按顺序安排在予定的时隙中传输，各移动终端只要在指定的时隙内接收，就能在合路的信号中把发给它的信号区分并接收下来。在RFID系统中TDMA是被广泛采用的多路方法。具体分为标签控制（驱动法）和阅读器控制（询问驱动法）。大多数RFID系统采用由阅读器作为主控制器的控制方法。实现：在所有标签中，在某个时间内只建立唯一的阅读器和标签的通信关系，可以很好的解决标签碰撞问题。10.2.2ALOHA防碰撞算法

Aloha协议或称Aloha技术、Aloha网，是世界上最早的无线电计算机通信网。它是1968年美国夏威夷大学的一项研究计划的名字。70年代初研制成功一种使用无线广播技术的分组交换计算机网络，也是最早最基本的无线数据通信协议。取名Aloha，是夏威夷人表示致意的问候语，这项研究计划的目的是要解决夏威夷群岛之间的通信问题。Aloha网络可以使分散在各岛的多个用户通过无线电信道来使用中心计算机，从而实现一点到多点的数据通信。第一个使用无线电广播来代替点到点连接线路作为通信设施的计算机系统是夏威夷大学的ALOHA系统。该系统所采用的技术是地面无线电广播技术，采用的协议就是有名的ALOHA协议，叫做纯ALOHA(PureALOHA)。以后，在此基础上，又有了许多改进过的ALOHA协议被用于卫星广播网和其它广播网络。各种ALOHA算法：纯ALOHA算法、时隙ALOHA算法、帧时隙ALOHA算法、动态帧时隙ALOHA算法。纯ALOHA算法

纯ALOHA算法的标签读取过程：（1）各个标签随机的在某时间点上发送信息。（2）阅读器检测收到的信息，判断是成功接收或者碰撞。（3）标签在发送完信息后等待随机长时间再重新发送信息。（4）假设某一帧信息的长度为F，起始时间为t0，另一帧的起始时间t1满足关系式t0-F≦t1≦t1+F

时，碰撞发生。当输入负载G=0.5时，系统的吞吐率达到最大值0.184。由于纯ALOHA算法中存在碰撞概率较大，在实际中，该算法较适合于阅读器只负责接收标签发射的信号，标签只负责向阅读器发射信号的情况。时隙ALOHA算法在ALOHA算法的基础上把时间分成多个离散时隙(slot)，并且每个时隙长度要大于标签回复的数据长度，标签只能在每个时隙内发送数据。每个时隙存在：

a无标签响应：此时隙内没有标签发送

b一个标签响应：仅一个标签发送且被正确识别

c多个标签响应：多个标签发送，产生碰撞当输入负载G=1时，系统的吞吐量达到最大值0.368，避免了纯ALOHA算法中的部分碰撞，提高了信道的利用率。需要一个同步时钟以使阅读器阅读区域内的所有标签的时隙同步。3帧时隙ALOHA算法在时隙ALOHA算法基础上把N各时隙组成一帧，标签在每个帧内随机选择一个时隙发送数据。当阅读器发送读取命令后，等待标签回答。每个时隙的长度足够一个标签回答完，当在一个时隙中只有一个标签回答时，阅读器可以分辨出标签；当没有回答时跳过该时隙；当多个标签回答时，发生碰撞，需重新读取。该算法特点：

a把N个时隙打包成一帧；

b标签在每N个时隙中只随机发送一次信息；

c需要阅读器和标签之间的同步操作，每个时隙需要阅读器进行同步。缺点：标签数量远大于时隙个数时，读取标签的时间会大大增加；当标签个数远小于时隙个数时，会造成时隙浪费。输入负载G=1时，吞吐率为最大。如果G<1，空时隙数目增加；G>1，碰撞的时隙数增加，降低系统实时性。4动态帧时隙ALOHA算法一个帧内的时隙数目N能随阅读区域中的标签的数目而动态改变，或通过增加时隙数以减少帧中的碰撞数目。步骤：（1）进入识别状态，在开始识别命令中包含了初始的时隙数N。

（2）由内部伪随机数发生器为进入识别状态的标签随机选择一个时隙，同时将自己的时隙计数器复位为1.

（3）当标签随机选择的时隙数等于时隙计数器时，标签向阅读器发送数据，当不等时，标签将保留自己的时隙数并等待下一个命令。（4）当阅读器检测到的时隙数量等于命令中规定的循环长度N时，本次循环结束。阅读器转入（2）开始新的循环。该算法每帧的时隙个数N都是动态产生的，解决了帧时隙ALOHA算法中的时隙浪费的问题。适应RFID技术中标签数量的动态变化的情形。10.2.3RFID中的二进制防碰撞算法将处于碰撞的标签分成左右两个子集0和1，基于轮询，按照二进制树模型和一定的顺序对所有的可能进行遍历。不是基于概率的算法，而是一种确定性的防碰撞算法。

011011100101图10-3二进制防碰撞算法模型冲突节点非冲突节点1二进制搜索算法阅读器查询的不是一个比特，而是一个比特前缀，只有序列号与这个查询前缀相符的标签才响应阅读器的命令而发送其序列号。当只有一个标签响应时，阅读器可以成功识别标签，但当多个标签响应时，阅读器就把下一次循环中的查询前缀增加一个比特0，通过不断增加前缀，阅读器就可以识别所有标签。四种命令：（1）REQUEST：发送一序列号作为参数给区域内标签。标签把自己的序列号与接收的相比较。（2）SELECT：用某个序列号作为参数发送给标签。具有相同序列号的标签将以此作为执行其他命令（读出和写入）的切入开关，即选择了标签。（3）READDATA：选中的标签将存储的数据发送给阅读器。（4）UNSELECT：取消一个事先选中的标签，标签进入无声状态，即对REQUEST命令不做应答。

2动态二进制搜索算法3基于二进制搜索算法的后退式索引算法4跳跃式动态树形反碰撞算法10.2.4Class1标准中的防碰撞算法10.2.5Gen2标准中的ALOHA算法

1标签识别层概述

2链路时序

3标签状态

4相关指令

5时隙计数器

6标签随机数发生器

7防碰撞算法过程

10.3RFID系统中阅读器的防碰撞算法如何有效的解决阅读器之间的碰撞问题，是阅读器网络中的一个至关重要的问题。有两种方式：主动式和被动式。主动式为正在工作的阅读器主动告知近邻阅读器它正处于工作状态，被动式为通过想要占用信道的临近阅读器的询问，该阅读器才告诉其工作状态。10.3.1多路存取机制载波侦听法（CDMA）是从ALOHA算法演变出的一种改进协议，又称载波侦听多点访问。要传输数据的站点首先对媒体上有无载波进行监听，以确定是否有别的站点在传输数据。如果媒体忙碌，该站点就避让一段时间后再做尝试。常用的退避算法有非坚持、L-坚持、P-坚持三种，来决定避让的时间。

载波监听多路访问/碰撞检测协议（CSMA/CD）：在传输过程中