射频识别（RFID）技术与应用 课件 第六章 RFID防碰撞算法设计与实现

RFID防碰撞算法设计与实现教师：xxxx2025/01/01CONTENTS01碰撞危机：RFID为何频发冲突02四大多路策略：空分频分码分时分03ALOHA家族：非确定型概率算法04二进制树：确定型精准识别05查询树算法：前缀堆栈遍历06MATLAB仿真：帧时隙ALOHA实战碰撞危机：RFID为何频发冲突01RFID系统两大碰撞场景拆解多读写器碰撞定义在RFID系统中，当多个读写器同时扫描同一区域内的标签时，读写器之间会产生干扰和冲突，导致一些标签无法被读取或被多个读写器同时读取，这种情况称为‘多重访问干扰’。多标签碰撞定义当多个RFID标签同时处于阅读器的覆盖范围内时，标签之间会发生干扰和冲突，导致阅读器无法同时读取所有标签的数据，或者读取的数据出现错误，这种情况称为‘多重标签干扰’。碰撞后果碰撞会导致标签漏读、读取速率骤降，严重影响RFID系统的效率和准确性。因此，研究防碰撞算法至关重要，以提高系统的吞吐率和信道利用率。多读写器碰撞机理与干扰模型多读写器碰撞模型利用图6-1展示，当三读写器覆盖三标签正常时，重叠区标签4同时收到两路载波，相位差引发数据混叠，导致读写器无法正确解析标签数据。影响因素多读写器碰撞的程度取决于读写器的功率、天线增益、频率和距离等因素。即使是小功率差异，也可能导致标签解调失败。多读写器碰撞机理与干扰模型图6-1多读写器碰撞多读写器碰撞是指当多个读写器同时扫描同一区域内的标签时，这些读写器之间会产生干扰和冲突，从而导致一些标签无法被读取或者被多个读写器同时读取的情况，这种情况也称为“多重访问干扰”。多标签碰撞的电磁叠加原理电磁叠加示例以图6-2为例，三标签同时回波，基带帧在接收机前端叠加成非解析波形，导致阅读器无法正确解析数据。碰撞强度碰撞强度随标签数量、响应速率、场强呈指数上升，这为算法效率评估提供了量化需求。多标签碰撞的电磁叠加原理在RFID系统中，多标签碰撞是指当多个RFID标签同时处于RFID阅读器的覆盖范围内时，这些标签之间会发生干扰和冲突，从而导致阅读器无法同时读取所有标签的数据，或者读取的数据出现错误，这种情况也称为“多重标签干扰”。图6-2多标签碰撞四大多路策略：空分频分码分时分02空分多路：用空间隔离同时读取天线阵列分区把读写区切成蜂窝格，各读写器独管一格，硬件成本高，但可彻底避免同频干扰。相控波束利用相控阵实时指向标签，通过RSSI区分，适合高端场景，但部署费用与施工复杂度较高。空分多路：用空间隔离同时读取空分多路法采用空间分离特性的天线技术实现标签的信息读取，即在分离的空间范围内实现多个目标识别。主要分为两种实现方法。一种是按照空间区域规则划分天线的覆盖范围，如图6-3所示图6-3空分多路法划分天线的覆盖范围频分多路：每标签独占载波信道01频分模型图6-4展示四标签各用不同上行频点，叠加后互不干扰，但需为每信道配独立接收机，成本随标签规模线性增加。02适用场景频分在无线监测、航空行李等特许频段可行，但对普通UHFRFID并不经济。频分多路：每标签独占载波信道频分多路法将传输通道划分为若干条信道，同时为每条信道分配不同的载波频率后分别提供给标签使用，以此实现不同信道的标签可以同时与读写器传输数据，其模型如图6-4所示。图6-4频分多路法模型码分多路：扩频地址码区分标签扩频与多址发端用高速伪随机码展宽信号，收端用相同码解扩，每标签分配唯一地址码，实现同频同时回传。优缺点码分多路具有抗干扰与保密优势，但标签需集成相关器，功耗与芯片面积翻倍，容量受限于可用码组数量。时分多路：把时间切片轮流传输时分多路特点将信道按时间轴划分为时隙，标签被调度到不同时隙回传，彻底避免波形叠加。时分可软件实现、无需额外射频硬件，因此成为RFID防碰撞算法的主流选择。ALOHA家族：非确定型概率算法03纯ALOHA：随机发言遇撞再退避01纯ALOHA模型图6-6示意三标签任意时刻发送，碰撞周期为2T。02吞吐率计算在泊松过程假设下，吞吐率η=Ge^{-2G}，在G=0.5时取得极限18.4%。03优缺点纯ALOHA优点为无需同步、实现极简，缺点是效率低且存在饥饿，适用于标签少于10的小规模场景。纯ALOHA：随机发言遇撞再退避纯ALOHA算法（PureALOHA,PA）是时分多路里一种典型的防碰撞算法，运用冲突监听和随机避让策略使得各标签能够在随机时刻发送信号。其算法的工作原理是基于“标签先发言机制”的方法，也就是说标签进入读写器产生的磁场区域后，通过天线接收到电磁波而被激活，激活后的标签主动向读写器发送消息，这个主动发送不受时间的先后限制。纯ALOHA：随机发言遇撞再退避如下图6-6所示为纯ALOHA算法的碰撞原理图。读写器识别范围内有三个标签，当标签2和标签3发生碰撞后，读写器命令他们随机延迟一段时间后再发送消息，直到读写器检测出只有一个标签1与其通信，则成功识别出该标签。在这过程中，有没有发生碰撞而成功识别，也有在信道中出现部分或完全碰撞后而无法成功识别，这时各标签会随机等待一定时长并继续传输数据包，直至读写器成功接收完整数据包。图6-6

纯ALOHA算法碰撞模型时隙ALOHA：同步时隙削半碰撞窗时隙ALOHA原理引入读写器广播时钟，标签只能在时隙起点发送，碰撞周期缩至T。性能提升吞吐率η=Ge^{-G}，极限36.8%，是纯ALOHA的两倍，被EPCGen2标准采纳为基准模式。时隙ALOHA：同步时隙削半碰撞窗SA的原理表现为时隙ALOHA要求所有用户（在RFID系统中为标签）在每个时间片的开始时刻发送数据，如果在同一时间片内有多个用户尝试发送，则会发生碰撞，用户必须等待下一个时间片再尝试。这种机制减少了数据冲突的可能性，使得信道利用率得到提高。时隙ALOHA：同步时隙削半碰撞窗当标签进入读写器的识别范围后，标签自身携带的随机数发生器产生一随机数，标签按此随机数选择时隙，若查询时的时隙数与标签选择的时隙相匹配时标签即响应，并立即发送自身的数据信息；若时隙内有碰撞时，读写器将终止标签继续发送信息并令标签等待下一次查询。在SA算法中，标签只能选择在每个时隙的开始阶段发送数据，而不是随机的选择时间发送数据，所以需要一个同步机制来控制标签，这个同步时钟的控制由读写器来完成，并且每个时隙的长度要满足标签成功传输完一数据包所需的时间。图6-8

时隙ALOHA算法碰撞模型帧时隙ALOHA：帧长动态逼近标签数帧时隙ALOHA模型图6-10模型把N时隙打包成帧，标签每帧只选一时隙回传。吞吐率公式吞吐率公式η=(n/L)(1-1/L)^{n-1}，当L≈n时效率最高。读写器可通过观察上一帧空/忙比例，动态调整L。帧时隙ALOHA：帧长动态逼近标签数FAS算法采用了以下策略，将多个时隙组织成一个帧，其中帧长代表了该帧内所包含的时隙数量。阅读器会将帧长信息传递给识别范围中的标签。在收到帧长信息后，标签会在该帧内随机选择一个时隙进行响应。在这一过程中，如果信息发生冲突，那么本帧内涉及到冲突的标签将暂停操作，等待下一帧的开始时再次执行上述策略。这样的设计有助于减少时隙浪费，提高识别和通信的准确性和效率。FSA算法的碰撞模型如图6-10所示。图6-10FSA算法的碰撞模型ALOHA类算法饥饿问题与公平性饥饿问题持续高负载下部分标签长期选不到独占时隙，导致‘标签饥饿’。公平性解决方案采用指数退避+随机重试的缓解方案，确定性算法能根本解决公平性问题。二进制树：确定型精准识别04二叉分裂思想与曼彻斯特碰撞位二叉分裂原理读写器利用曼彻斯特编码过零点检测，可直接定位ID碰撞位。把碰撞最高位置0，其余低位置1，形成新查询前缀，从而把标签群一分为二。优点无需标签随机数，只要ID唯一即可保证收敛，适用于对识别顺序有严格要求的场景。二进制搜索树流程八步拆解初始Query广播全1初始Query，所有标签响应。检测碰撞接收并检测碰撞，生成新前缀。分裂与Silence若无碰撞则Select+Silence，否则继续分裂。循环搜索回跳继续搜索，直到堆栈空，每次分裂至少识别一张标签。二进制搜索树流程八步拆解循环搜索回跳继续搜索，直到堆栈空，每次分裂至少识别一张标签。二进制搜索树算法（BinarySearchTree,BST）的核心思想在于利用曼彻斯特码检测到的碰撞位，找寻最高碰撞位置（设为0）并作为划分界限。在此基础上，保持高位不变，将低位全设为1，从而生成新的身份标识（Identitydocument，ID）。随后，该算法将标签ID与查询指令中的ID进行对照，然后进行细分标签，直到达到最小单元。将持续执行这一过程，直到阅读器成功识别区域内的所有标签。BST吞吐率与标签规模关系吞吐率公式识别n标签所需平均查询次数M=log2(n!)+n，吞吐率η=n/M。性能表现图6-16显示n=5时η≈0.42，n=150降至0.15。BST在标签<20时效率优于ALOHA，但随规模增大开销显著。动态BST：ID长度压缩与跳跃搜索01优化策略一是只传输碰撞位以上部分，降低空中比特；二是跳跃式查询，跳过已知全0子树。02性能提升可把查询次数降至约0.7nlog2n，吞吐率提升20%以上，适用于ID长度>96的超高频场景。查询树算法：前缀堆栈遍历05QueryTree原理：前缀匹配+堆栈驱动算法原理QT无需标签随机数，也不在标签端维护状态；读写器内部维护查询前缀堆栈，初始为空。每轮弹出前缀发Request，标签ID前缀匹配即回送剩余位。碰撞处理若碰撞则在当前前缀后追加0、1再压栈，形成二叉遍历。算法简洁，标签功耗极低。QT识别流程四阶段示例初始阶段发NULL得全体碰撞。压栈阶段压入0、1。查询阶段先查0分支再查1分支。识别阶段若无碰撞则SELECT+UNSELECT使标签休眠。QT与BST复杂度对比复杂度公式QT平均查询次数M≈2.88N-1，η稳定0.35；BST在N>7后η持续下降。适用场景QT适合标签ID较长、数量中等且对公平性要求高的物流盘点；BST适合标签较少、ID短的仓储抽屉管理。查询树改进：混合切割与索引压缩改进策略一是结合碰撞位索引，跳过全空子树；二是对连续相同前缀做游程压缩，减少Request比特。性能提升仿真显示在256标签、128位ID场景下，查询次数可降至1.6N，吞吐率提升至0.45。MATLAB仿真：帧时隙ALOHA实战06FSA仿真目标与场景设定仿真目标用MATLAB验证5标签、5时隙单帧下的碰撞、重传过程。预期结果通过方波可视化看到时隙占用、碰撞位置及再分配，帮助学生直观理解‘碰撞→等待→重选时隙’循环。FSA仿真目标与场景设定

图6-185个标签在一帧内发送情况随机时隙分配代码逻辑逐行解读随机数生成randperm生成1-5不重复排列，floor/N得0-1发送指示。方波扩展K点扩展成方波便于plot，随机种子可重复实验。代码功能代码实现随机时隙分配，为后续碰撞检测和重传提供基础数据。碰撞检测与冲突标签提取算法碰撞检测逻辑按列扫描时隙，记录同一时隙内多标签置1的索引，形成冲突数组Rdx。算法功能该数组长度即下帧需回传的标签数，为动态帧长提供输入。多帧重传过程可视化结果结果展示图6-19、6-20展示第二帧、第三帧波形：第二帧3标签仍碰撞，第三帧成功。性能表现随着帧数增加，碰撞概率指数下降，符合FSA理论1/e收敛速度。参数扩展实验：帧长与标签数匹配01扩展任务保持n=40，把L从20调到80，观察总时隙消耗曲线出现V型谷底。02实验意义验证L≈n最优，通过仿真学生可亲手复现图6-11理论曲线，实现‘理论-仿真-结论’闭环。MATLAB仿真：二进制搜索树实战07BST仿真目标与ID设定仿真目标4个8位ID标签A~D，走读完整二叉分裂流程，输出读写器与标签交互顺序。预期结果通过打印RS数组，让学生看到‘碰撞→分裂→孤立→Silence’全过程，加深对确定型算法无饥饿特性的理解。BST仿真目标与ID设定二进制搜索树算法属于确定性算法防碰撞算法，其核心思想在于利用曼彻斯特码检测到的碰撞位，找寻最高碰撞位置（设为0）并作为划分界限。现有4个标签，每个标签的ID长度为8位，分别为A（1010111）、B（10110101）、C（10101111）以及D（10111101）。第一步，读写器向其识别范围内的标签发送查询指令R(11111111)；第二步，读写器对收到的标签进行响应，如出现不一致的情况（即有的序列号位为0，有的序列号该位为1），则判断有碰撞，如图6-21所示；第三步，确定有碰撞后，把不一致位数的最高位置0后再输出查询条件Q，依次排除序列号大于Q的标签。从图6-1