RFID原理与实践 课件 4.5.2 ALOHA算法

ALOHA算法标签防碰撞算法一个优秀的标签防碰撞算法，应该满足以下特性：（1）读写器能够识别作用范围内所有标签。（2）读写器应尽可能快地识别标签，这主要体现在识别标签所需的总的查询次数与总的通信数据量两方面。（3）由于标签通信和计算能力有限，防碰撞协议应设计得尽量简单。（4）某些场合需要信息安全保护机制，确保不会泄漏隐私。在RFID系统中，考虑到系统的功耗、通信形式、成本和复杂性等因素，标签防碰撞算法大多是基于时分多址技术，主要分为两大类：基于Aloha的概率性算法基于树的确定性算法。Aloha防碰撞算法ALOHA防碰撞算法

Aloha协议或称Aloha技术、Aloha网，是世界上最早的无线电计算机通信网。Aloha网络可以使分散在各岛的多个用户通过无线电信道来使用中心计算机，从而实现一点到多点的数据通信。第一个使用无线电广播来代替点到点连接线路作为通信设施的计算机系统是夏威夷大学的ALOHA系统。该系统所采用的技术是地面无线电广播技术，采用的协议就是有名的ALOHA协议，叫做纯ALOHA(PureALOHA)。以后，在此基础上，又有了许多改进过的ALOHA协议被用于卫星广播网和其它广播网络。各种ALOHA算法：纯ALOHA算法、时隙ALOHA算法、帧时隙ALOHA算法、动态帧时隙ALOHA算法。纯ALOHA算法Aloha算法是一种随机接入方法。当读写器请求标签发回它们的ID号时，识别范围内所有标签都会随机选择一个时间发送数据给读写器。如果标签发送的数据没有发生碰撞，读写器就能成功识别这个标签，被正确识别的标签不再响应读写器的命令。如果标签信息发生碰撞，碰撞的标签随机选择一个时间重发数据。重复以上过程，直到所有标签都被读写器成功识别。思想：只要用户有数据要发送，就尽管让他们发送纯ALOHA算法的标签读取过程：（1）各个标签随机的在某时间点上发送信息。（2）阅读器检测收到的信息，判断是成功接收或者碰撞。（3）若判断发生碰撞，则标签随机等待一段时间再重新发送信息。纯ALOHA存在的问题：（1）错误判决。即对同一个标签，如果连续多次发生碰撞，则将导致阅读器出现错误判断，认为标签不在阅读器作用范围内。（2）数据帧的发送过程中发生碰撞的概率很大。过多的碰撞导致吞吐量下降系统性能降低。

解决方向：减小碰撞发生次数缩短重发延时存在的问题？？？纯ALOHA算法时隙ALOHA算法时隙ALOHA算法把标签应答的时间分成等长的时隙(slot)。时隙的长度足够让标签传输完数据，并且能够让读写器能够识别完这些数据。读写器作用范围内的标签必须同步时隙，每个标签在可传输时隙的开始时刻发送数据。在一个时隙内如果仅有一个标签发送数据，读写器就能正确识别这个标签。如果发生碰撞，标签随机选择一个时隙重新发送数据。每个时隙存在以下三种情形：a空闲时隙：此时隙内没有标签发送b成功识别时隙：仅一个标签发送且被正确识别c碰撞时隙：多个标签发送，产生碰撞在时隙Aloha算法中，标签数据传输只在每个时隙的起始，因此它只会发生完全碰撞，完全避免了纯Aloha算法中的部分碰撞，提高了信道的利用率。在隙Aloha算法需要一个时钟使读写器阅读区域内的所有标签时隙同步，这相应地提高了设备的成本，并且标签数目远远大于时隙时，标签碰撞机率就会大大增加，造成标签识别时延。时隙ALOHA算法帧时隙ALOHA算法帧时隙Aloha(framedslottedAloha，FSA)算法是在时隙Aloha算法的基础上，把N个时隙组成一帧，标签在每个帧内随机选择一个时隙发送数据，适用于传输信息量较大的场合，与时隙Aloha算法相同，其也需要一个同步开销，但只需要每个帧同步就可以了，相对于时隙Aloha算法，其同步开销更少。算法特点：

a把N个时隙打包成一帧；b标签在每N个时隙中只随机发送一次信息；c需要读写器和标签之间的同步操作，每个时隙需要读写器进行同步。存在缺点：a标签数量远大于时隙个数时，读取标签的时间会大大增加；当标签个数远小于时隙个数时，会造成时隙浪费。b不能根据读写器周围的标签数而变化，系统无法获得稳定的吞吐量。帧时隙ALOHA算法动态帧时隙Aloha(DFSA)算法动态帧时隙Aloha(DFSA)算法是FSA算法的一种改进算法，也是在RFID应用中防碰撞算法应用得最多的算法之一。思路：一个帧内的时隙数目N能随阅读区域中的标签的数目而动态改变，或通过增加时隙数以减少帧中的碰撞数目。该算法每帧的时隙个数N都是动态产生的，解决了帧时隙ALOHA算法中的时隙浪费的问题。适应RFID技术中标签数量的动态变化的情形。选择一个合适的初始帧长度对DFSA算法非常重要。如果帧长太小，而标签数量过多，碰撞的时隙数会大大增加，整个系统的效率会大打折扣。如果标签数量很少，而帧又设置过长，则会出现大量的空闲时隙。动态帧时隙Aloha(DFSA)算法步骤：（1）进入识别状态，在开始识别命令中包含了初始的时隙数N。（2）由内部伪随机数发生器为进入识别状态的标签随机选择一个时隙，同时将自己的时隙计数器复位为1.（3）当标签随机选择的时隙数等于时隙计数器时，标签向读写器发送数据，当不等时，标签将保留自己的时隙数并等待下一个命令。（4）当读写器检测到的时隙数量等于命令中规定的循环长度N时，本次循环结束。读写器转