《二进制树搜索算法》PPT课件

《《二进制树搜索算法》PPT课件》由会员分享，可在线阅读，更多相关《《二进制树搜索算法》PPT课件（23页珍藏版）》请在装配图网上搜索。

1、课 程 回 顾RFID技 术 RFID组 成RFID工 作 原 理 在 RFID系 统 ， 因 为 多 个 读 写 器 和 多 个 标 签 造 成 的读 写 器 之 间 和 标 签 之 间 的 互 相 干 扰 ， 统 称 为 碰 撞 。什 么 是 碰 撞碰 撞 的 类 型1.读 写 器 碰 撞2.标 签 碰 撞防 碰 撞 算 法 2.2 RFID 技术RFID 工作原理 l 现 有 的 基 于 TDMA防 冲 突 算 法 可 以 分 为 基 于ALOHA的 算 法 和 基 于 二 进 制 树 两 种 类 型 。 2.2 RFID 技术RFID 工作原理Binary-Tree(二 进 制 树 )

2、算 法 简 介纯 ALOHA防 冲 突 算 法分 时 隙 的 ALOHA防 冲 突 算 法 （ S-ALOHA）Dynamic Binary-Tree 算 法标 签 防 碰 撞 方 法 在 算 法 执 行 过 程 中 ， 读 写 器 要 多 次 发 送 命 令给 电 子 标 签 ， 每 次 命 令 都 把 标 签 分 成 两 组 ，多 次 分 组 后 最 终 得 到 唯 一 的 一 个 标 签 。 在 这个 分 组 过 程 中 ， 将 对 应 的 命 令 参 数 以 节 点 的形 式 存 储 起 来 ， 就 可 以 得 到 一 个 数 据 的 分 叉树 ， 而 所 有 的 这 些 数 据 节

3、点 又 是 以 二 进 制 的形 式 出 现 的 ， 所 以 称 为 “ 二 进 制 树 ” 。Binary-Tree(二 进 制 树 )算 法 2.2 RFID 技术RFID 工作原理001 10000 0100何 为 “ 二 进 制 树 ” ？ 1 0 1 1 00 0 01 11 0? ? ? 射 频 卡 1射 频 卡 2读 写 器 译 码曼 彻 斯 特 码 (Mancherster)可 在 多 卡 同 时 响 应 时， 译 出 错 误 码 字 ， 可 以 按 位 识 别 出 碰 撞 。 这 样 可以 根 据 碰 撞 的 位 置 ， 按 一 定 法 则 重 新 搜 索 射 频 卡。 如

4、何 确 定 碰 撞 的 准 确 比 特 位 置 ？ 二 进 制 树 搜 索 算 法 的 实 现 步 骤 如 下 ：（ 1） 读 写 器 广 播 发 送 最 大 序 列 号 查 询 条 件 Q， 其 作 用 范 围内 的 标 签 在 同 一 时 刻 传 输 他 们 的 序 列 号 至 读 写 器 。 范 例 ： A:10100111B:10110101C:10101111D:10111101R:11111111R:11111111 R表 示 阅 读 器 二 进 制 树 搜 索 算 法 的 实 现 步 骤 如 下 ：（ 1） 读 写 器 广 播 发 送 最 大 序 列 号 查 询 条 件 Q， 其

5、 作 用 范 围内 的 标 签 在 同 一 时 刻 传 输 他 们 的 序 列 号 至 读 写 器 。（ 2） 读 写 器 对 收 到 的 标 签 进 行 响 应 ， 如 果 出 现 不 一 致 的 现象 （ 即 有 的 序 列 号 位 为 0， 有 的 序 列 号 该 位 为 1） ， 则 可判 断 有 碰 撞 。 范 例 ： A:10100111B:10110101C:10101111D:10111101R:11111111R:11111111 R表 示 阅 读 器101?1?1 二 进 制 树 搜 索 算 法 的 实 现 步 骤 如 下 ：（ 1） 读 写 器 广 播 发 送 最 大 序

6、 列 号 查 询 条 件 Q， 其 作 用 范 围内 的 标 签 在 同 一 时 刻 传 输 他 们 的 序 列 号 至 读 写 器 。（ 2） 读 写 器 对 收 到 的 标 签 进 行 响 应 ， 如 果 出 现 不 一 致 的 现象 （ 即 有 的 序 列 号 位 为 0， 有 的 序 列 号 该 位 为 1） ， 则 可判 断 有 碰 撞 。（ 3） 确 定 有 碰 撞 后 ， 把 有 不 一 致 位 的 数 最 高 位 置 0再 输 出 查询 条 件 Q， 依 次 排 除 序 列 号 大 于 Q的 标 签 。 范 例 ： A:10100111B:10110101C:10101111D

7、:10111101R:11111111R:11111111 R表 示 阅 读 器 R:10101111101?1?1 搜 寻 标 签 过 程 A:10100111C:10101111R:10101111R:10101111送 REQUEST（ 10101111） 命 令 ，标 签 A和 C应 答 。 解 码 数 据 为 1010?111,发 生 碰 撞 ， 算 法 做 下 如下 ， 将 碰 撞 的 最 高 置 0， 其 它 碰 撞位 置 1。 得 10100111 ? R表 示 阅读 器R:10100111 范 例 ： A:10100111C:10101111R:10100111R:10100

8、111 送 REQUEST（ 10100111） 命 令 ， 只 有 标 签 A应 答 。 没 有 发 生 碰 撞 ， 阅 读 器对 标 签 A进 行 阅 读 操 作 。 R表 示 阅读 器可 以 识别 AB:10110101D:10111101 二 进 制 树 搜 索 算 法 的 实 现 步 骤 如 下 ：（ 1） 读 写 器 广 播 发 送 最 大 序 列 号 查 询 条 件 Q， 其 作 用 范 围内 的 标 签 在 同 一 时 刻 传 输 他 们 的 序 列 号 至 读 写 器 。（ 2） 读 写 器 对 收 到 的 标 签 进 行 相 应 ， 如 果 出 现 不 一 致 的 现象 （

9、 即 有 的 序 列 号 位 为 0， 有 的 序 列 号 该 位 为 1） ， 则 可判 断 有 碰 撞 。（ 3） 确 定 有 碰 撞 后 ， 把 有 不 一 致 位 的 数 最 高 位 置 0再 输 出 查询 条 件 Q， 依 次 排 除 序 列 号 大 于 Q的 标 签 。（ 4） 识 别 出 序 列 号 最 小 的 标 签 后 ， 对 其 进 行 数 据 操 作 ， 然后 使 其 进 入 “ 无 声 ” 状 态 ， 则 对 读 写 器 发 送 的 查 询 命 令不 进 行 响 应 。（ 5） 重 复 步 骤 1 ， 选 出 序 列 号 倒 数 第 二 的 标 签 。（ 6） 多 次

10、循 环 完 后 完 成 所 有 标 签 的 识 别 。 Improved Anti-collision Algorithm搜 寻 过 程第 一 次 搜 寻 第 二 次 搜寻 第 三 次 搜寻 第 四 次 搜寻 第 五 次 搜寻发 送 序 号接 收 序 号TagATagBTagCTagD 1010011110110101101011111011110111111111101?1?1 1010111110100111101011111010?111 1010011110100111识 别TagA 10110101101011111011110111111111101?1?1 10101111101

11、01111识 别TagC Improved Anti-collision Algorithm搜 寻 过 程第 六 次 搜 寻 第 七 次 搜 寻 第 八 次 搜 寻 第 九 次 搜 寻 第 十 次 搜 寻发 送 序号接 收 序号TagATagBTagC TagD 1011010110111101111111111011?101 1011010110110101 1011110110111101识 别TagB 识 别TagD 二 进 制 搜 索 算 法 的 工 作 流 程 是 ：出 现 不 一 致 的 现 象射 频 卡 进 入 读 写 器 的 工 作 范 围 ， 读 写 器 发 出 一 个 最

12、大 序 列 号 让所 有 射 频 卡 响 应 ； 同 一 时 刻 开 始 传 输 它 们 的 序 列 号 到 读 写 器 的接 收 模 块 。读 写 器 对 比 射 频 卡 响 应 的 序 列 号 的 相 同 位 数 上 的 数 。即 有 的 序 列 号 该 位为 0， 而 有 的 序 列号 该 位 为 1把 有 不 一 致 位 的 数 从 最 高 位 到 低 位 依 次 置 O再 输 出 系 列 号 ，即 依 次 排 除 序 列 号 大 的 数 ， 至 读 写 器 对 比 射 频 卡 响 应 的序 列 号 的 相 同 位 数 上 的 数 完 全 一 致 时 ， 说 明 无 碰 撞 。 选 出

13、 序 列 号 最 小 的 数 后 ， 对 该 标 签 进 行 数 据 交 换 ， 然 后使 该 卡 进 入 “ 无 声 ” 状 态 。Y N 算 法 性 能 分 析 ：l 为 了 从 N个 标 签 中 找 出 唯 一 一 个 标 签 ， 需 要进 行 多 次 请 求 ， 其 平 均 次 数 L为 ：l L=log2N+1l 则 基 本 二 进 制 树 算 法 识 别 N个 标 签 所 需 的 总查 询 次 数 为 ： SUM(N)=N(log2N+1）l 查 询 次 数 是 一 个 关 于 N和 L的 增 函 数 ， 要 识 别一 个 标 签 ， 请 求 次 数 L随 着 N值 的 增 大 而

14、 迅 速增 加 。 并 且 标 签 每 次 响 应 阅 读 器 的 请 求 命 令时 所 传 的 ID都 是 完 整 ID。 19Dynamic Binary-Tree 算 法l 在 Basic Binary-Tree算 法 中 ， 标 签 每 次 回 送 给阅 读 器 的 序 列 号 必 须 是 全 序 列 号 。 然 而 标 签 的序 列 号 并 不 只 是 由 单 字 节 构 成 ， 而 是 根 据 实 际需 要 可 能 长 达 10 多 个 字 节 。 对 于 这 种 长 序 列号 的 标 签 ， 假 如 每 次 都 完 整 的 传 输 其 ID 值 ， 需要 传 输 的 数 据 量

15、很 大 ， 再 加 上 阅 读 器 也 是 以 同样 长 度 的 ID 值 作 为 参 数 互 相 传 递 ， 则 会 花 费 很长 的 时 间 ， 造 成 识 别 延 迟 ， 降 低 系 统 效 率 。l 为 减 少 标 签 和 阅 读 器 之 间 传 输 的 数 据 量 ， 提 高阅 读 器 的 识 别 效 率 ， 在 Basic Binary-Tree算 法的 基 础 上 ， 提 出 了 一 种 改 进 的 防 碰 撞 算 法 ， 称其 为 Dynamic Binary-Tree 算 法 。 2.2 RFID 技术RFID 工作原理 l 现 有 的 基 于 TDMA防 冲 突 算 法 可

16、 以 分 为 基 于ALOHA的 算 法 和 基 于 二 进 制 树 两 种 类 型 。 2.2 RFID 技术RFID 工作原理Binary-Tree(二 进 制 树 )算 法 简 介纯 ALOHA防 冲 突 算 法分 时 隙 的 ALOHA防 冲 突 算 法 （ S-ALOHA）Dynamic Binary-Tree 算 法标 签 防 碰 撞 方 法 21RFID碰 撞 的 概 念防 冲 突 算 法 分 类详 细 描 述 ALOHA算 法 、 基 于 帧 的 分 时隙 的 ALOHA算 法 、 二 进 制 树 算 法 。重 点 掌 握 作 业 ：在 RFID数 据 传 输 的 工 作 方 式 有 哪 三 种 ？什 么 是 多 路 存 取 的 工 作 方 式 ？现 有 的 RFID防 碰 撞 都 基 于 哪 种 算 法 ？ 23 THANKS 相 关 知 识 点 及 重 难 点 下 载