通信技术 一 种 新 颖 的 RFID 防 冲 突 算 法 张 明 , 张 建 华 , 徐 国 鑫 , 张 平 ( 北 京 邮 电 大 学 92# 无 线 新 技 术 研 究 室 , 北 京 100876) 摘 要 : 提 出 一 种 应 用 于 RFID 系 统 上 行 链 路 的 多 标 签 冲 突 检 测 算 法 , 并 给 出 了 参 考 实 现 电 路 。 依 算 法 , 对 电 子 标 签 进 行 随 机 分 群 , 在 群 间 做 随 机 避 让 , 在 群 内 进 行 冲 突 检 测 和 标 签 的 仲 裁 。 与 现 有 的 随 机 避 让 算 法 和 二 进 制 树 算 法 相 比 , 该 算 法 不 但 有 效 降 低 了 碰 撞 次 数 , 实 现 电 路 也 更 简 单 。 关 键 词 : RFID 电 子 标 签 防 冲 突 算 法 仲 裁 无 线 射 频 识 别 ( RFID) 是 一 种 非 接 触 式 的 自 动 识 别 技 术 , 其 基 本 原 理 是 利 用 射 频 信 号 和 空 间 耦 合 ( 电 感 或 电 磁 耦 合 ) 的 传 输 特 性 , 实 现 对 特 定 物 体 的 自 动 识 别 。 RFID 技 术 可 以 追 溯 至 第 二 次 世 界 大 战 期 间 , 后 来 发 展 应 用 到 铁 路 、军 队 的 货 物 跟 踪 甚 至 宠 物 识 别 上 。 在 过 去 的 半 个 多 世 纪 里 , RFID 的 发 展 经 历 了 从 技 术 探 索 、试 验 研 究 、商 业 应 用 和 标 准 化 建 立 等 几 个 重 要 阶 段 。 从 现 有 发 展 趋 势 看 , RFID 将 构 建 虚 拟 世 界 与 物 理 世 界 的 桥 梁 。 可 以 预 见 在 不 久 的 将 来 , RFID 技 术 不 仅 会 在 各 行 各 业 被 广 泛 采 用 , 最 终 RFID 技 术 还 将 会 与 普 适 计 算 技 术 相 融 合 , 对 人 类 社 会 产 生 深 远 影 响 。 RFID 系 统 一 般 由 电 子 标 签 和 读 写 器 两 个 部 分 组 成 , 读 写 器 具 有 同 时 读 取 多 个 电 子 标 签 的 功 能 。在 多 标 签 对 一 个 读 写 器 的 RFID 系 统 中 , 标 签 经 常 会 同 时 向 读 写 器 传 输 数 据 , 这 就 要 求 RFID 系 统 建 立 一 种 仲 裁 机 制 来 避 免 数 据 发 生 碰 撞 。 考 虑 到 电 子 标 签 本 身 尺 寸 、能 耗 的 限 制 , 防 碰 撞 机 制 在 保 障 功 能 的 同 时 还 要 求 尽 量 简 单 易 行 , 这 正 是 RFID 系 统 设 计 的 挑 战 之 一 。 文 献 [1]和 [2]提 出 了 三 种 RFID 系 统 的 防 碰 撞 算 法 。 算 法 A 基 于 随 机 避 让 、冲 突 检 测 的 原 理 , 使 用 1 个 8 位 寄 存 器 和 1 个 8 位 随 机 数 产 生 器 , 最 大 可 以 仲 裁 标 签 的 数 量 只 有 256 个 。 算 法 B 基 于 二 进 制 数 的 原 理 , 使 用 1 个 8 位 寄 存 器 和 1 个 1 位 随 机 数 产 生 器 , 理 论 上 最 大 可 以 实 现 2256 个 标 签 的 仲 裁 。文 献 [3]提 出 了 对 该 算 法 的 一 个 实 现 方 案 , 文 献 [4]对 该 算 法 做 了 很 大 改 进 。算 法 C 类 似 于 算 法 A, 使 用 1 个 16 位 寄 存 器 和 16 个 1 位 随 机 数 产 生 器 , 最 大 可 以 仲 裁 标 签 的 数 量 是 65 536 个 。本 文 中 , 作 者 提 出 一 种 分 群 避 让 、群 内 冲 突 检 测 的 算 法 和 其 改 进 算 法 , 仅 需 要 1 个 8 位 寄 存 器 和 1 个 1 位 随 机 数 产 生 器 就 可 以 实 现 最 大 1 048 576 个 标 签 的 仲 裁 , 而 且 碰 撞 次 数 相 对 于 算 法 B 要 大 大 减 少 。 1 仲 裁 机 制 描 述 并 将 群 随 机 排 序 以 实 现 群 间 的 随 机 避 让 , 然 后 在 群 内 进 行 冲 突 检 测 和 标 签 的 仲 裁 。 实 现 时 标 签 仅 需 一 个 寄 存 器 : 利 用 其 高 位 存 储 群 号 , 低 位 存 储 冲 突 检 测 时 退 避 的 步 数 , 实 现 极 为 简 单 。 下 面 以 8 位 寄 存 器 为 例 具 体 说 明 本 算 法 的 仲 裁 机 制 。 当 读 写 器 初 始 化 标 签 时 , 所 有 标 签 在 0 ～15 之 间 任 选 一 个 整 数 存 入 寄 存 器 高 4 位 ( 相 当 于 随 机 选 择 一 个 群 ) 并 把 寄 存 器 低 4 位 设 为 全 0 , 同 时 产 生 一 个 0 或 1 的 随 机 数 加 到 寄 存 器 中 。 如 果 此 时 寄 存 器 中 的 8 比 特 数 为 全 0 则 回 传 该 标 签 的 ID ( ID 是 指 电 子 标 签 的 惟 一 标 识 , 在 不 同 的 编 码 系 统 中 有 不 同 的 含 义 ) 。 如 果 多 个 标 签 同 时 回 传 数 据 , 则 冲 突 发 生 。 发 生 冲 突 后 , 其 他 寄 存 器 高 4 位 为 0 的 标 签 寄 存 器 中 的 数 加 1, 而 寄 存 器 中 的 8 比 特 数 为 全 0 的 标 签 则 再 产 生 一 个 0 或 1 的 随 机 数 加 到 寄 存 器 中 。如 果 寄 存 器 作 加 法 后 仍 为 全 零 , 则 继 续 回 传 该 标 签 的 ID; 如 果 回 传 时 不 发 生 碰 撞 , 则 其 他 寄 存 器 高 4 位 为 0 的 标 签 仅 把 寄 存 器 低 4 位 减 1 后 重 复 前 面 的 回 传 操 作 。 当 寄 存 器 高 4 位 全 为 0 的 标 签 全 部 回 传 完 ID, 则 所 有 其 他 标 签 把 寄 存 器 高 4 位 减 1 后 重 复 前 面 的 操 作 。 此 外 依 本 算 法 , 由 于 所 有 标 签 随 机 选 择 群 , 有 可 能 会 出 现 某 个 群 中 的 标 签 数 目 过 大 , 使 该 群 中 的 标 签 在 仲 裁 过 程 中 始 终 发 生 碰 撞 , 标 签 寄 存 器 始 终 加 1 , 导 致 寄 存 器 低 4 位 向 高 4 位 进 位 。进 位 意 味 着 所 有 进 位 的 标 签 的 寄 存 器 低 4 位 清 零 而 高 4 位 加 1 , 这 使 得 这 些 标 签 不 再 属 于 原 有 的 群 而 归 入 到 下 一 个 群 中 , 从 而 优 化 了 因 随 机 选 择 而 产 生 的 分 布 不 均 匀 的 群 标 签 数 。 本 算 法 中 , 标 签 最 大 退 让 步 数 为 24=16 步 , 因 此 每 个 群 最 大 能 仲 裁 的 标 签 数 目 为 216=65 536 , 则 本 算 法 能 仲 裁 的 标 签 数 理 论 上 限 是 16×216=1 048 576 。 2 算 法 步 骤 本 节 给 出 算 法 步 骤 , 假 设 使 用 一 个 8 位 寄 存 器 , 则 本 算 法 包 括 以 下 步 骤 : 本 方 法 的 核 心 思 想 是 : 首 先 把 电 子 标 签 随 机 分 群 , ( 1) 在 所 述 RFID 系 统 的 被 动 方- 标 签 中 设 计 一 个 4+4 《电子技术应用》2006 年第 6 期 本 刊 邮 箱 :eta@ncs e . com . cn 127 

通信技术 位 的 寄 存 器 ( Re1 ) 和 1 个 “0 ”、“1 ” 随 机 数 产 生 器 ( RG1 ) , 如 图 1 所 示 。 ( 2 ) 在 所 述 RFID 系 统 的 主 动 方 - 读 写 器 向 所 有 处 在 等 待 态 的 标 签 发 送 初 始 化 命 令 。 标 签 因 此 进 入 仲 裁 态 , 用 RG1 产 生 4 比 特 随 机 数 , 加 载 到 Re1 高 4 位 R7 ~R4 , 低 4 位 R3~R0 全 部 清 零 。 ( 3 ) 读 写 器 等 待 一 定 时 间 后 发 送 允 许 回 传 命 令 。 ( 4 ) Re1 为 全 零 的 标 签 向 读 写 器 回 传 标 签 ID。 ( 5 ) 如 果 当 前 只 有 一 个 标 签 回 传 ID, 读 写 器 正 确 读 取 该 ID, 则 发 送 确 认 命 令 , 附 加 命 令 参 数“ 低 位 减 1 ”。 回 传 了 ID 的 标 签 接 收 到 该 命 令 后 , 进 入 确 认 态 , 其 他 高 4 位 为 全 零 的 标 签 Re1 低 4 位 减 1 , 回 到 步 骤 ( 4 ) 重 复 操 作 。 ( 6 ) 如 果 当 前 有 多 个 标 签 回 传 ID, 读 写 器 通 过 CRC 校 验 或 码 长 校 验 , 检 测 到 错 误 的 ID 号 , 则 发 送 确 认 命 令 , 附 加 命 令 参 数“ 寄 存 器 加 1 ”。 接 收 到 读 写 器 这 个 命 令 后 , 所 有 在 仲 裁 态 且 Re1 为 全 零 的 标 签 由 RG1 产 生 1 比 特 随 机 数 和 寄 存 器 上 的 数 相 加 后 重 新 载 入 到 寄 存 器 中 ; 其 他 仲 裁 态 且 Re1 高 4 位 为 零 而 低 4 位 不 为 零 的 标 签 Re1 加 1 , 回 到 步 骤 ( 4 ) 重 复 操 作 。 ( 7 ) 如 果 当 前 没 有 标 签 回 传 ID, 读 写 器 等 待 一 定 时 间 后 发 送 确 认 命 令 , 附 加 命 令 参 数“ 低 位 减 1 ”。 所 有 在 仲 裁 态 且 高 4 为 全 零 的 标 签 Re1 低 4 位 减 1 , 回 到 步 骤 ( 4 ) 重 复 操 作 。 ( 8 ) 低 4 位 减 1 操 作 重 复 L 次 ( L 是 一 个 系 统 参 数 , 由 系 统 设 定 , 经 验 值 为 4 ) 后 , 读 写 器 认 为 所 有 在 仲 裁 态 且 寄 存 器 高 4 位 为 零 的 标 签 都 已 经 被 正 确 读 取 , 则 发 送 确 认 命 令 , 附 加 命 令 参 数“ 高 4 位 减 1 ”, 回 到 步 骤 ( 4 ) 。 ( 9) 标签接 收到 附 加“高 位 减 1”参 数 的 确 认 命 令 后 , 所 有 Re1 高 4 位 不 为 零 的 标 签 高 4 位 减 1 , 回 到 步 骤 4 重 复 操 作 ; 在 被 要 求 高 位 减 1 前 已 为 零 的 标 签 则 回 到 等 待 态 。 ( 10 ) 重 复 15 次 高 位 减 1 操 作 后 , 读 写 器 认 为 所 有 在 仲 裁 态 的 标 签 都 已 经 被 读 取 , 则 仲 裁 过 程 停 止 , 所 有 还 处 于 仲 裁 态 的 标 签 返 回 等 待 态 。 算 法 步 骤 中 所 述 等 待 态 是 指 电 子 标 签 上 电 后 的 初 始 状 态 ; 仲 裁 态 是 指 未 被 读 写 器 鉴 别 的 电 子 标 签 开 始 响 应 读 写 器 鉴 别 命 令 时 进 入 的 状 态 ; 确 认 态 是 指 已 被 读 写 器 鉴 别 的 电 子 标 签 进 入 的 状 态 。电 子 标 签 状 态 转 移 规 则 如 下 : 上 电 后 电 子 标 签 进 入 等 待 态 ; 处 于 等 待 态 的 电 子 标 签 可 以 进 入 仲 裁 态 ; 处 于 仲 裁 态 的 电 子 标 签 可 以 返 回 等 待 态 ; 处 于 仲 裁 态 的 电 子 标 签 可 以 进 入 确 认 态 ; 处 于 确 认 态 的 电 子 标 签 不 能 返 回 仲 裁 态 ; 确 认 态 与 等 待 态 之 间 不 能 直 接 转 移 。 针 对 上 述 算 法 步 骤 , 在 以 下 几 个 地 方 加 以 改 进 , 形 成 本 算 法 的 改 进 算 法 。 A、步 骤 ( 1 ) 中 , 随 机 数 产 生 器 产 生 两 组 随 机 数 , 分 别 加 载 到 寄 存 器 高 位 和 低 4 位 。其 中 高 位 加 载 的 位 数 M 可 以 动 态 设 为 1 、2 、3 或 4 。 B、步 骤 ( 10 ) 中 的 重 复 操 作 次 数 为 2M 次 。 因 为 改 进 算 法 在 寄 存 器 低 4 位 也 加 载 了 随 机 数 , 使 得 标 签 在 群 间 转 移 的 概 率 ( 即 低 4 位 向 高 位 进 位 的 概 率 ) 大 大 增 加 , 特 别 如 果 最 后 一 个 群 中 标 签 的 寄 存 器 低 4 位 在 退 让 步 骤 中 进 位 , 则 会 产 生 一 个 新 群 , 因 此 需 要 额 外 增 加 一 次 高 位 减 1 操 作 。 3 电 路 实 现 算 法 实 现 的 参 考 电 路 框 图 见 图 1 , 其 中 RG1 是 一 个 “0 ”“1 ”随 机 数 产 生 器 ; Re1 是 一 个 8 位 寄 存 器 。 加 法 器 ADD1 和 ADD2 的 加 减 功 能 根 据 读 写 器 命 令 来 设 定 : 当 执 行 加 法 操 作 时 , 低 4 位 的 ADD2 需 向 高 4 位 的 ADD1 进 位 ; 当 执 行 减 法 操 作 时 , 两 个 器 件 ADD1 和 ADD2 相 互 独 立 。 加 法 器 可 以 工 作 在 同 步 状 态 或 异 步 状 态 , 工 作 在 同 步 状 态 时 可 以 使 用 电 子 标 签 的 最 大 时 钟 。 4 仿 真 结 果 仿 真 1: 为 了 评 估 本 算 法 的 优 劣 , 特 设 计 以 下 仿 真 : 标 签 使 用 8 位 寄 存 器 , 高 4 位 为 高 位 。定 义 0 个 、2 个 和 2 个 以 上 的 标 签 同 时 发 送 数 据 时 为 传 输 冲 突 ; 只 有 一 个 标 签 发 送 数 据 时 为 传 输 成 功 , 平 均 冲 突 次 数 定 义 为 传 输 冲 突 总 次 数 和 传 输 成 功 总 次 数 的 比 ; 空 传 率 定 义 0 个 标 签 发 送 数 据 的 次 数 与 传 输 成 功 总 次 数 的 比 。观 察 标 签 数 为 20～10 000 时 的 平 均 冲 突 次 数 。 仿 真 结 果 如 图 2 所 示 , 本 文 提 出 的 算 法 与 二 进 制 算 法 性 能 接 近 , 平 均 每 成 功 传 输 1 次 都 要 伴 随 2 次 传 输 冲 突 ; 而 改 进 算 法 则 在 标 签 数 为 50～5 000 个 时 明 显 减 少 了 碰 撞 次 数 。同 时 也 注 意 到 当 标 签 个 数 少 于 50 时 , 改 进 算 法 性 能 下 降 , 这 是 因 为 此 时 标 签 数 接 近 分 群 的 群 数 导 致 空 传 率 上 升 所 致 , 解 决 的 办 法 是 减 少 分 群 的 群 数 。 针 对 该 问 题 , 特 设 计 仿 真 2 来 分 析 。 仿 真 2 : 为 了 分 析 低 标 签 密 度 时 改 进 算 法 的 性 能 , 特 设 计 以 下 仿 真 : 采 用 改 进 算 法 , 分 别 使 用 5 ～8 位 寄 存 器 , 高 1 ～4 位 为 高 位 , 即 分 群 群 数 分 别 为 2 、4 、8 和 16 。 128 欢迎网上投稿 www.aetnet.cn www.aetnet.com.cn 《电子技术应用》2006 年第 6 期 

通信技术 仿 真 结 果 如 图 3 所 示 , 可 以 看 到 当 标 签 总 数 为 20 时 , 如 果 把 高 位 寄 存 器 的 位 数 从 4 降 到 1 , 则 平 均 碰 撞 次 数 从 5.5 回 落 到 1.4 。而 当 标 签 总 数 为 200 和 2000 时 , 高 位 寄 存 器 位 数 的 改 变 对 平 均 碰 撞 次 数 的 影 响 不 大 。因 此 如 果 在 某 次 仲 裁 中 出 现 多 次 空 传 , 根 据 这 个 先 验 知 识 , 读 写 器 可 以 在 下 一 次 仲 裁 时 指 示 标 签 改 变 寄 存 器 高 位 个 数 , 以 此 降 低 空 传 率 , 进 而 可 以 降 低 平 均 碰 撞 次 数 。 本 文 提 出 的 防 碰 撞 算 法 仅 需 在 电 子 标 签 中 配 置 1 个 8 位 寄 存 器 、1 个 1 位“ 0 ”、“ 1 ”随 机 数 产 生 器 和 2 个 4 位 加 减 1 计 数 器 以 及 少 量 选 择 电 路 就 能 实 现 最 多 达 1 048 576 个 标 签 的 仲 裁 。 仿 真 表 明 本 算 法 产 生 的 碰 撞 概 率 明 显 小 于 二 进 制 数 算 法 , 同 时 通 过 寄 存 器 高 位 的 灵 活 设 置 , 还 能 有 效 解 决 低 标 签 密 度 时 空 传 率 高 的 问 题 , 从 而 进 一 步 降 低 了 碰 撞 概 率 。 本 算 法 实 现 简 单 , 复 杂 度 低 , 非 常 适 合 在 RFID 系 统 中 应 用 , 因 而 具 有 广 阔 的 应 用 前 景 。 参 考 文 献 1 ISO18000- 6C 标 准 : Information technology- Radio- frequency identification for item management - Part 6C: Parameters for air interface communications at 860 MHz to 960MHz. 2 ISO18000- 6A/B 标 准 :Information technology automatic iden- tification and data capture techniques - Radio frequency identification for item management air interface- Part 6: Parameters for air interface communications at 860- 960MHz. 3 Fukmnizu Y, Ohno S, Nagata M, etc. A highly collision resistive RFID system. In : proc. of APSITT 2003, Nov.2003: 223～228 4 Zhou, F, Jing, D, Huang C et al. Optimizing the power consumption of passive electronic tags for Anti- collision schemes. In:Proceedings of the 5th ASICON, Beijing,China, October 2003:1213～1217 ( 收 稿 日 期 : 2006- 01- 30 ) Alter a 在 Quar tus II 软件 6.0 高密度设计上实现重大改进 在 设 计 软 件 中 为 Synopsys 设 计 约 束 ( SDC) 格 式 提 供 自 然 、 全面支持的第一个 FPGA 供应商 2006 年 5 月 9 日 , 香 港 - Altera 公 司 ( NASDAQ: ALTR ) 近 日 宣 布 开 始 发 售 6.0 版 的 Quartus!II 软 件 。该 版 本 包 括 了 由 FPGA 供 应 商 提 供 的 第 一 款 时 序 分 析 工 具 TimeQuest 时 序 分 析 仪 , 为 业 界 标 准 Synopsys 设 计 约 束 ( SDC) 时 序 格 式 提 供 自 然 、全 面 的 支 持 。 这 一 最 新 版 本 还 包 括 扩 展 的 团 队 设 计 功 能 , 能 够 有 效 管 理 高 密 度 设 计 团 队 之 间 的 协 作 。 这 些 改 进 迎 合 了 当 今 高 密 度 90nm 的 设 计 要 求 , 同 时 为 满 足 客 户 对 更 高 密 度 FPGA 的 需 求 以 及 Altera 发 展 下 一 代 65nm 产 品 系 列 打 下 了 基 础 。 $ """"""""""""""""""""""""""""""""""""""""""""""# " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " $%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%$ 《电子技术应用》2006 年第 6 期 Altera 在 最 新 版 Quartus II 软 件 中 引 入 了 新 的 技 术 改 进 以 满 足 客 户 对 90nm 的 需 求 , 并 为 65nm 工 艺 节 点 打 下 了 基 础 。这 些 新 特 性 最 突 出 的 部 分 包 括 : TimeQuest 时 序 分 析 仪 ; 扩 展 的 团 队 设 计 支 持 ; SystemVerilog 支 持 ; 增 强 的 I/O 引 脚 规 划 器 ; 扩 展 的 电 路 板 级 设 计 支 持 。 Synopsys 战 略 联 盟 总 监 Lonn Fiance 评 论 说 :“FPGA 设 计 人 员 将 业 界 标 准 SDC 时 序 约 束 格 式 直 接 读 取 到 TimeQuest 时 序 分 析 仪 中 , 能 够 更 迅 速 的 实 现 时 序 逼 近 。 采 用 SDC 格 式 可 以 提 高 FPGA 设 计 人 员 的 效 率 , 进 一 步 促 进 标 准 时 序 验 证 方 法 在 半 导 体 业 界 的 应 用 。 ” 关 于 Quartus II 软 件 的 详 细 信 息 , 请 访 问 www.altera.com/quartus2 。了 解 TimeQuest 时 序 分 析 仪 和 其 他 的 Quartus II 特 性 , 请 访 问 Quartus II 软 件 在 线 演 示 网 页 www.altera.com/verificationtraining。 ( Altera 公 司 供 稿 ) 本 刊 邮 箱 :eta@ncs e . com . cn 129