RFID标签防碰撞算法及详细研究
常见RFID防碰撞算法有哪几种？比较各自的优缺点，详细论述其中一种算法的工作原理。
1.RFID简介
射频识别技术(Radio Frequency Id,RFID)是一种非接触式自动识别技术，与传统的识
别方式相比，RFID技术无需直接接触、无需光学可视、无需人工干预即可完成信息输入和处
理，具有操作方便快捷、存储数据量大、保密性好、反应时间短、对环境适应性强等优点，
现在已广泛应用于工业自动化，商业自动化和交通运输管理等领域，成为当前IT业研究的热
点技术之一。典型的RFID系统主要包括三个部分：电子标签(Tag)、阅读器(Reader)和数据
处理o电子标签放置在被识别的对象上，是RFID系统真正的数据载体。通常电子标签处于休
眠状态，一旦进入阅读器作用范围之内就会被激活，并与阅读器进行无线射频方式的非接触
式双向数据通信，以达到识别并交换数据的目的。此外，许多阅读器还都有附加的通信接口，
以便将所获得的数据传进给数据处理子系统进行进一步的数据处理。
2.系统防碰撞
RFID系统工作的时候，当有2个或2个以上的电子标签同时在同—个阅读器的作用范围内
向阅读器发送数据的时候就会出现信号韵干扰，这个干扰被称为碰撞(collision)，其结果
将会导致该次数据传输的失败，因此必须采用适当的技术防止碰撞的产生。
从多个电子标签到—个阅读器的通信称为多路存取。多路存取中有四种方法可以将不同
的标签信号分开：空分多路法(SDMA)、频分多路法（FDMA)、对分多路法（TDMA)和码分多路
法(CDMA)。针对RFID系统低成本、较少硬件资源和数据传输速度以及数据可靠性的要求，TDMA
构成了RFID系统防碰撞算法最为广泛使用的一族。
TDMA是把整个可供使用的通路容量按时间分配给多个用户的技术，可分为电子标签控制
法和阅读器控制法。电子标签控制法主要有ALOHA法，阅读器控制法有轮询法和二进制搜索
法。
2.1 空分多路法(SDMA)
空分多路法(Space Division Multiple Access，SDMA)是在分离的空间范围内实现多个
目标识别。其实现的方法有两种：一种方法是将读写器和天线之间的作用距离按空间区域进
行划分，把大量的读写器和天线安置在一个天线阵列中。当标签进入这个天线阵列的覆盖范
围后，与之距离最近的读写器对该标签进行识别。由于每个天线的覆盖范围较小，相邻的读
写器识别范围内的标签同样可以进行识别而不受到相邻的干扰，如果多个标签根据在天线阵
列中的空间位置的不同，可以同时被识别。另外一种方法是，读写器利用一个相控阵天线，
通过让天线的方向性图对准单独的标签，这样标签根据其在读写器作用范围内的角度位置的
不同而区别开来。空分多路法的缺点是需要使用复杂的天线系统，会大幅提高RFID设备的成
本，因此这种方法只适用于一些特殊的应用场合。
2.2 频分多路法(FDMA)
频分多路法(Frequency Division Multiple Access，FDMA)是把若干个使用不同载波频
率的调制信号传输通路同时供通信用户使用的技术。通常情况下，RFID系统的前向链路(从读写器到标签)频率是固定的，用于能量的供应和数据的传输。对于反向链路(从标签到读写器)，不同的标签采用不同频率的载波石～Z对数据进行调制，这些信号之间不会产生干扰，读写器根据接收到的不同频率的信号后，可以将不同频率的信号进行分离，从而实现对不同标签的识别。频分多路法的缺点是对读写器和标签的成本要求较高，因此在实际RFID系统的应用中，频分多路法也很少使用。
2.3 码分多路法(CDMA)
码分多路法(Code Division Multiple Access，CDMA)是在扩频通信技术的基础上发展起来的一种无线通信技术。扩频技术包含扩频(Spread Spectrum)与多址(Multiple Access)两个基本的概念。扩频是将信息带宽扩展，即把需要发送的具有一定信号带宽的信息数据，用一个带宽远大于其信号带宽的伪随机码进行调制，这样使原来的信息数据的带宽被扩展，最后通过载波调制发送出去。解扩是指在接收端采用完全一致的伪随机码，与接收到的宽带信号作相关处理，把宽带信号转换成原来的信息数据。码分多路法具有抗干扰性好，保密安全性高，信道利用率高的优点。但是该技术也存在频带利用率低、信道容量小，伪随机码的产生和选择较难，接收时地址码捕获时间长等缺点，所以该方法很难应用于实际的RFID系统中。
2.4 时分多路法(TDMA)
时分多路法(Time Division Multiple Access，TDMA)是把整个可供使用的通路容量按时间分配给多个用户的技术。目前RFID系统的标签防碰撞算法中大多采用时分多路法。该方法可以分为标签控制法和读写器控制法。标签控制法中，读写器没有对数据传输控制，标签的工作是非同步的。按照标签被成功识别后是否通过读写器发出的命令进入“静默”状态，标签控制法可以分为“开关断开法”和“非开关法”。在读写器控制法中，所有标签同时由读写器进行观察和控制。按照规定的算法，在读写器作用范围内，首先在标签组中选中一个标签，然后完成读写器器对标签的识别。在同一时间内读写器只能与一个标签建立通信关系，所以如果要选择另外一个标签进行通信，就必须解除与原来标签的通信关系，也就是说在同一时间内只能有单个标签占用通信信道。目前时分多路法中常见的两大类标签防碰撞算法是ALOHA算法和二进制树算法。ALOHA算法是一种随机性的算法，会出现某一标签在很长一段时间内无法得到识别，即标签饥渴(Tag tarvation)Ihl题。二进制树算法是一种确定性的算法，该类算法比较复杂，识别时间较长，但不存在标签饥渴(Tag starvation)Ih-J题。现阶段，在高频(HF)频段，标签的防碰撞算法一般采用ALOHA算法。标签通过随机选择一个时间向读写器发送数据，来避免冲突，绝大多数高频读写器能同时扫描几十个标签。
3． RFID系统中防碰撞算法
3.1 ALOHA算法
ALOHA系统采用无规则的时分多址，或叫随机多址。ALOHA算法采取“标签先发言”的方
式，即标签一进入阅读器的作用区域就自动向阅读器发送其自身的信息。在标签发送数据的过程中，若有其它标签也在发送数据，那么将会导致冲突。阅读器检测接收到的信号有无冲突，一旦检测到冲突，阅读器就发送命令让标签先停止发送，随机等待一段时间后再重新发送以减少冲突。ALOHA算法的数据传送和碰撞过程如图3.1所示。
图3.1 ALOHA算法数据传送
ALOHA算法的主要特点是各个标签发射时间是完全随机的，当工作范围内标签的数量不多时ALOHA算法可以很好的工作。缺点就是数据帧发送过程中冲突发生的概率很大，冲突周期是，而且标签不能自己检测冲突，只能通过接收阅读器的命令判断有无冲突。当工作范围内的标签数增加时，发生碰撞的概率增加，性能急剧下降，信道利用率只有18.4%。针对以上问题，提出了时隙ALOHA算法和帧时隙ALOHA算法等来改善ALOHA算法。采用时隙ALOHA算法的RFID系统因为有阅读器控制在同步时隙内传送数据，可能发生碰撞的时间区就缩短了一半，吞吐率最大可达36.8%，相对于纯ALOHA算法增加了一倍，但仍局限于只读型电子标签。采用帧时隙ALOHA算法的RFID系统适用于传输信息量较大的场合，但当标签数量远大于时隙个数时，读取标签的时间将会大大增加，在标签数远小于时隙个数时，就会造成时隙的浪费。
3.2 二进制树算法
二进制树算法的基本思想是将处于冲撞状态的标签分成左右两个子集0和1，先查询子集0，若没有冲突，则正确识别标签；若仍有冲突，则再分裂，把子集0分为00和01两个子集，依次类推，直到识别出子集0中的所有标签，再按此步骤查询子集1。使用基本的二进制树形算法的标签能够记忆以前的查询结果从而减少平均查询时间，但对功率要求很高。二进制树算法如图3.2所示
图3.2 二进制树算法
二进制树搜索算法是一种无记忆的算法，即标签不必储存以前的查询情况，这样可以降低成。在这种算法中阅读器查询的不是一个比特，而是一个比特前缀，只有序列号与这个查询前缀相符的标签才响应阅读器的命令而发送其序列号。当只有一个标签响应的时候阅读器可以成功识别标签，但是当有多个标签响应的时候，下一次循环中阅读器就把查询前缀增加一个比特0，通过不断增加前缀阅读器就能识别所有的标签。二进制树搜索的前提是要辨认出阅读器中数据碰撞的准确位置，选用曼彻斯特编码可以检测出碰撞位。采用二进制树搜索算法的RFID系统特点是：具有较高的稳定性，易于用软件实现，吞吐率最高可达36.4%，但ID不能太长，ID越长所需要的时间就越长，当时间超过一定限度时，这种算法将不再适用。
后退式二进制树搜索算法与二进制树形搜索算法相似，先识别出一个单独的标签，下一次查询命令采用后退策略，从父节点获得，直到二进制树根节点无冲突发生后结束。后退式二进制树搜索算法的RFID系统特点是：识别单个标签平均只需2次，识别N个标签共需2N+1次，信道利用率稳定在50%，但是也存在ID过长时不适用的缺点。二进制树搜索算法和后退式二进制树搜索算法在标签的ID长度增加时，不能正确识别出标签，而且会增加系统的负担。
3.3 二进制搜索树的程序流程
如图3.3所示；