基于上下文的碰撞检测树：一种用于移动式RFID标签识别的可靠防碰撞协议

《Computer Networks》：Context-Scheduled Collision Tree: A Reliable Anti-collision Protocol for Mobile RFID Tags Identification

抗冲突与任务调度机制在移动RFID系统中的应用研究。提出CSCT协议通过碰撞事件解析和任务优先级调度提升系统吞吐量，Mod-Grouping机制实现碰撞信息结构化处理，仿真显示在5000 tags/s负载下效率比基线高70%。

　　

周洪全|贾晓琳|杜忠|顾亚军|杨红

中国四川省绵阳市绵阳移动物联网与射频识别技术重点实验室，621010

摘要

在移动射频识别（RFID）系统中，标签的识别面临一个主要挑战，即标签的驻留时间是随机的。这种时间不确定性对传统的基于预测和确定性的协议构成了限制。本文提出了基于上下文的碰撞树（CSCT）架构方法，将防碰撞问题视为实时任务调度问题。CSCT采用了一种称为“Mod-Grouping”的后缀哈希机制，从碰撞事件中提取结构信息，从而将其转换为标准化的、可调度任务，由优先级驱动的引擎进行管理。该引擎遵循“剩余任务最短优先”的原则，始终优先处理剩余未解决比特数最少的任务。仿真结果表明，在高负载条件下，CSCT的调度效率比领先的基线协议高出约70%。此外，这种反应式架构防止了内部任务队列的饱和——这是其他竞争方法中的一个关键限制——使得系统能够稳定、高效地处理接近500个标签/秒的吞吐量，且损失率可以忽略不计。这项工作表明，基于事件的调度方法可以为动态RFID环境提供一种有效且稳健的替代方案。代码可在以下链接获取：https://github.com/ZoeLoveHGJ/Project_CSCT。

引言

射频识别（RFID）技术是物联网（IoT）中自动识别的重要组成部分[1]。在物体处于持续运动状态的大规模、动态应用中，其优势尤为明显。例如，在智能交通系统中，必须能够在高速公路速度下可靠地识别车辆以进行电子收费。在自动化物流和供应链管理中，必须实时跟踪高速传送带上的数千个带标签的包裹或叉车上的托盘，以确保准确的分类和库存管理[2]、[3]。

这些具有挑战性的场景有一个共同特点：标签数量不是静态的，而是一个非平稳流，其特点是快速且不可预测的到达和离开[4]。这种物理动态性在协议层带来了重大挑战：每个标签仅在随机的、有限的驻留时间内可用于识别。如果未能在这个短暂且不确定的时间窗口内识别出标签，可能会导致系统级问题。因此，解决这种时间不确定性是部署稳健且高效的移动RFID系统的关键前提。

在静态环境中，假设标签始终可用，防碰撞协议主要沿着两种策略发展：基于Aloha的随机访问[5]和基于树的确定性解决[6]、[7]。前者，特别是动态帧时分Aloha（DFSA），依赖于标签数量估计来动态调整帧大小。后者采用固定的、顺序的过程来解决碰撞问题，虽然保证了完全识别，但牺牲了动态适应性。这些 established 方案在面对移动环境的时间不确定性时的有效性需要仔细评估。

一个常见的研究方向是将这些 established 策略适应于移动场景。然而，这两种方法都存在特定的局限性。DFSA 的“预测-适应”策略基于一个准静态假设，即标签数量在估计-适应周期内保持稳定。移动环境中标签到达的非平稳特性挑战了这一假设，导致预测滞后——即估计与现实之间的持续偏差——这可能导致参数配置错误。相反，虽然基于树的协议避免了对外部预测的依赖，但它们的程序刚性限制了它们在管理动态标签数量方面的有效性。固定的解决序列无法有效管理异步到达和离开的标签，可能会将信道资源分配给已经离开询问区域的标签。

为了克服这些限制，本文将防碰撞问题视为实时任务调度问题。我们提出了基于上下文的碰撞树（CSCT）协议，该协议基于两个核心原则运作。首先，它利用碰撞事件从标签ID中提取结构信息，将无意义的失败事件转化为结构化、信息丰富的任务。其次，它使用一个基于优先级的引擎来管理这些任务，该引擎依赖于一个稳定的、确定性的指标：任务本身的难度，而不是不稳定的外部预测。这种架构使CSCT能够响应式且高效地管理非平稳的标签数量。

本工作的主要贡献有三个方面：

1.

一种基于调度的移动RFID反应式框架：我们提出并验证了一种新的架构方法，将防碰撞问题重新定义为实时任务调度问题。这种基于事件的框架无需标签数量估计，因此能够适应移动环境中典型的非平稳标签到达情况。

2.

一种将碰撞事件转换为可调度任务的机制：我们设计了一种过程，将原始碰撞事件转换为结构化、可调度任务。首先使用基于后缀的哈希方法（Mod-Grouping）从碰撞的标签ID中提取确定性信息。然后将这些信息封装成一个我们称之为Collision Context的标准数据单元，作为调度引擎的基本输入。

3.

一个高效的、基于优先级的调度引擎：我们设计了一个统一的优先级驱动引擎来管理这些任务。该引擎采用“剩余任务最短优先”的策略，其中任务优先级由一个确定性指标（D_rem）确定。这确保了即使在高流量负载下也能有效减少系统负载并提供有界的识别延迟。

部分摘录

移动RFID系统的挑战

移动RFID系统中MAC层协议的操作挑战在图1所示的模型中得到了概念化。图1(a)中描绘的环境物理动态导致了协议层的一个主要后果：每个标签的随机驻留时间（T_res）。图1(b)中抽象出的这一时间约束因移动环境固有的几个因素而进一步加剧。

相关工作

RFID系统的防碰撞协议大致分为基于Aloha的方法和基于树的方法。在移动应用的背景下，最近的研究已经扩展到了不仅仅是基本识别，还包括连续监控和概率采样。

数学基础

CSCT协议采用了一种后缀哈希机制，我们称之为Mod-Grouping，从标签ID中提取结构信息。其有效性依赖于二进制系统中模运算的一个基本属性，我们在下面对其进行形式化，以便清晰和逻辑上的完整性。

属性1 相同模数的后缀唯一性

设