RFID数据管理：算法、协议与性能评测（南京大学：谢磊、殷亚凤、陈曦、陆桑璐、陈道蓄）

第36卷第3期 计算机学报 Vol.36 No.3 2013年3月 CHINESE JOURNAL OF COMPUTERS Mar.2013 RFD数据管理：算法、协议与性能评测 谢磊殷亚凤陈曦陆桑璐陈道蓄 (南京大学计算机软件新技术国家重点实验室南京210093) 摘要随着物联网关键理论及技术的发展，RFD作为物联网的核心支撑技术，成为物联网领域备受关注的研究 热点之一.文中以RFID的数据管理为切人点，从算法、协议以及性能评测3个层面对RFD的研究工作进行阐述 与分析，者重介绍了RFD的防冲突算法、认证与隐私保护协议以及真实环境下系统的性能评测与分析等方面的研 究成果及进展，最后展望了未来的研究方向. 关键词射频识别；数据管理：防冲突算法：认证与隐私保护；性能优化；物联网 中图法分类号TP393 D0I号10.3724/sP.J.1016.2013.00457 RFID Data Management:Algorithms,Protocols and Performance Evaluation XIE Lei YIN Ya-Feng CHEN Xi LU Sang-Lu CHEN Dao-Xu (State Key Laboratory for Novel Software Technology,Nanjing University,Nanjing 210093) Abstract With the development of critical theories and technologies in Internet of Things (IOT),as a key supporting technology,RFID has become one of the hotspots in the field of Internet of Things.Focusing on RFID data management,this paper describes and analyzes the re- search work on three aspects:algorithm,protocol and performance evaluation.In this paper,we introduce the research progress in RFID with anti-collision algorithm,authentication and privacy protection protocols,as well as performance evaluation of RFID systems in realistic settings.Fi- nally,we outlook the future research directions and conclude. Keywords RFID;data management;anti-collision algorithm;authentication and privacy protec- tion;performance optimization;Internet of Things 追踪等.随着RFID的技术原理被进一步深人理解、 引言 廉价的RFID组件相继出现以及RFID的安全得到 保障，RFID技术将会在物联网应用中发挥越来越 随着“物联网”时代的来临，新一代T技术将 重要的作用. 被充分运用在各行各业之中.射频识别(RFD)作为 物联网的核心理念是在普适环境下实现“物物 物联网应用的一项核心支撑技术，在学术界与工业 相联”，即通过对物理世界信息化、网络化，将传统上 界已经得到广泛关注.目前，RFD技术正在越来越 分离的物理世界与信息世界实现互联与整合.这就 频繁地出现在大量的物联网应用中，包括物流管理、 需要将“智能”嵌入到每一个物理对象当中，并且提供 电子支付、RFD护照、安全访问控制、目标监测与 一种有效的、低成本的通信方式，RFID技术的出现 牧稿日期：2012-02-08：最终修改稿收到日期：2012-05-27.本课题得到国家“九七三”重点基础研究发展规划项目基金(2009CB320705)、国家 自然科学基金(61100196,61073028,61021062)以及江苏省自然科学基金(BK2011559)资助.谢磊，男，1982年生，博士，讲师，中国计算机 学会(CCF)会员，主要研究方向为传感器网络、RFID系统、车联网、高性能计算.E-mail:lxie@ju,edu.cn殿亚凤，女，l989年生，博士研究 生，中国计算机学会(CCF)学生会员，主要研究方向为RFID.陈曦，男，1988年生，硕士研究生，中国计算机学会(CCF)学生会员，主要研究 方向为RFID.陆秦璐，女，1970年生，博士，教授，博士生导师，中国计算机学会(CCF)会员，主要研究领域为普适计算、分布式计算、传感 器网络.陈道蓄，男，1947年生，数授，博士生导师，中国计算机学会(C℃)高级会员，主要研究领域为普适计算、分布式计算、计算机网络

第 36卷 第 3期 2013年 3月 计 算 机 学 报 CHINESE JOURNAL OF COMPUTERS Vol_36 NO．3 M ar． 2O13 1 RFID数据管理 ：算法 、协议与性能评测 谢 磊 殷亚凤 陈 曦 陆桑璐 陈道蓄 (南京大学计算机软件新技术 国家重点实验室 南京 210093) 摘 要 随着物联网关键理论及技术 的发展 ，RFID作为物联 网的核心支撑技术 ，成为物联 网领域备受关 注的研究 热点之一．文 中以 RFID的数据管理为切入点 ，从算法 、协议 以及性 能评测 3个层 面对 RFID 的研 究工作进 行 阐述 与分析 ，着重介 绍了 RFID的防冲突算法 、认证 与隐私保护协议 以及真实环境下 系统 的性能评测 与分析等方 面的研 究 成果 及进展．最后 展望了未来的研究方 向． 关键词 射频识别 ；数据管理 ；防冲突算法 ；认证与隐私保护 ；性能优化 ；物联 网 中 图 法 分 类 号 TP393 DOI号 10．3724／SP．J．1016．2013．00457 RFID Data M anagem ent：Algorithm s，Protocolsand Perform ance Evaluation XIE Lei YIN Ya—Feng CH EN Xi LU Sang—Lu CH EN Dao—Xu (StateKeyLaboratoryforNovelS0ftwareTechnology，NanjingUniversity，Nanjing 210093) Abstract W ith the development of critical theories and technologies in Internet of Things (IOT)，as a key supporting technology，RFID has become one ofthe hotspots in the field of InternetofThings．Focusing on RFID datamanagement，thispaperdescribes and analyzesthere— search work on threeaspects：algorithm ，protocoland performanceevaluation． In thispaper，we introducetheresearch progressin RFID with anti—collision algorithm ．authentication andprivacy protection protocols，aswellasperformanceevaluation ofRFID system sin realisticsettings．Fi— nally，we outlook thefutureresearch directionsand conclude． Keywords RFID ；datamanagem ent；anti—collision algorithm ；authentication and privacyprotec tion；perform anceoptim ization；InternetofThings 引 目 随 着 “物 联 网”时 代 的来 临 ，新 一 代 IT 技 术将 被充 分 运用 在各 行各业 之 中．射 频识 别 (RFID)作 为 物联 网应用 的一 项 核 心支 撑 技 术 ，在 学 术 界 与 工 业 界 已经 得到 广泛 关 注．目前 ，RFID 技术 正 在 越 来 越 频 繁地 出现 在大 量 的物联 网应 用 中 ，包 括物 流管 理 、 电子支 付 、RFID 护 照 、安 全 访 问控 制 、目标 监 测 与 追踪 等 ．随着 RFID 的技 术原 理被 进 一步 深 入理 解 、 廉 价 的 RFID组件 相继 出 现 以及 RFID 的安 全 得 到 保 障 ，RFID技 术 将 会 在 物联 网应 用 中 发 挥 越 来 越 重要 的作用 。 物 联 网 的核 心理 念是 在普 适 环境 下 实现 “物一物 相联”，即通过对物理世界信息化、网络化 ，将传统上 分 离 的 物 理世 界 与信 息世 界 实现 互 联 与整 合 ．这 就 需要将“智能”嵌入到每一个物理对象当中，并且提供 一 种 有效 的 、低 成 本 的通 信 方式 ，RFID技 术 的 出现 收稿 日期 ：2012—02—08；最终修改稿收到 日期 ：2012—05—27．本课题得到国家 “九七 三”重点基础研究 发展规划项 目基金(2009CB320705)、国家 自然科学基金(61100196，61073028，61021062)以及江苏省 自然科学基金 (BK2O11559)资助．谢 磊 ，男 ，1982年生 ，博士 ，讲师 ，中国计算机 学会(CCF)会员 ，主要研究方向为传感器网络 、RFID系统 、车联 网、高性能计算．E-mail：lxie@niU．edu．cn．殷亚凤，女，1989年生 ，博士研究 生 ，中国计算机学会 (CCF)学生会员 ，主要研究方向为 RFID．陈 曦 ，男 ，1988年生 ，硕士研究生 ，中国计算机学会(CCF)学生会员 ，主要研究 方 向为 RFID．陆桑璐 ，女 ，1970年生 ，博士 ，教授 ，博士生导师 ，中国计算机 学会 (CCF)会员 ，主要研究领域为 普适 计算 、分布式计算 、传 感 器 网络．陈道蓄 ，男 ，1947年生 ，教授 ，博士生导师 ，中国计算 机学会 (CCF)高级会员 ，主要研究领域为普适计算、分布式计算、计算机 网络．

458 计算机学报 2013年 正好满足了这一需求.RFID是一种非接触式的自 为数据管理提供基本的安全保障，能够有效地实现 动识别技术，它通过射频信号自动识别目标对象并 认证并且保护用户隐私，实现RFID数据管理的可 获取相关数据，识别工作无须人工干预.作为一种简 信性；对RFID系统进行性能评测与分析，其目的在 单的无线系统，RFID系统只有两个基本器件，一个 于验证在真实环境下物理层的关键因素对系统识别刷 是阅读器，另一个是标签.其基本工作原理是：阅读器 性能的影响，确保数据管理的可靠性.深入探究三者 以广播方式连续向周围发送携带能量的基准信号， 之间的联系，我们发现任一研究问题均对其余二者 感应到能量的标签通过调制电路信号以反射的方式 产生影响：防冲突算法能够提供最根本的数据传输 向阅读器返回自身携带的数据，阅读器对接收到的 支持，安全协议能够实现必要的安全保障，性能评测 数据进行解码，并传给主机进行处理.通过上述方 能够验证在真实环境下的系统运行性能.上述三方 式，RFID系统能够提供有效的身份信息(Identity) 面研究问题与RFID系统协议栈的对应关系如图1 和地址信息(Location).相比于其它智能系统， 所示，可以看到三者之间相互联系，又各有侧重. RFID系统具有如下鲜明特点：(1)能够实现非接触 RFD数据管理 式的快速自动识别；(2)标签内能够永久存储一定 可靠性 高效性 可信性 大小的数据：(3)标签内含一定数目的逻辑门能够 价 进行简单的逻辑处理；(4)标签具有普通无线设备 性能 防冲突 安全 的物理属性：(5)标签成本低廉，可以大量部署.因 评测 算法 协议 此，作为物联网感知识别层面的一项关键技术， RFID技术能够使得物联网中的每一个物体被唯一 物理层 媒体访问 控制层 应用层 地识别，并且能够携带规范而具有互用性的信息，在 RFID系统协议栈 无源的情况下有效实现“被动智能”，为“物-物相联” 提供根本保障。 图1各研究问题之间的逻辑层次关系 在物联网环境下，RFID系统被部署和应用的 本文第2节主要介绍RFID的标签识别协议与 根本目的是：针对具体的应用需求，对被标识的物理 防冲突算法，着重阐述RFID标签识别机制、数目估 对象进行合理有效的信息收集，为上层应用提供最 算机制以及轮询机制方面的研究工作：第3节主要 基本的数据支持.因此，任何一种具体的RFD应用 介绍RFID的认证与隐私保护协议，对RFID的安 都依赖于对RFID数据实现有效的数据管理.所谓 全与隐私问题进行探讨与分析，并对RFID安全方 数据管理是指结合RFID系统的应用需求实现有效 面的三类主流技术进行总结；第4节对真实环境下 且有针对性的数据收集、分析挖掘以及数据安全保 RFID系统性能的评测与分析方面的研究工作进行 障等操作.在现有的物联网体系架构中，数据管理起 介绍；第5节对RFID数据管理相关的其它开放性 着承上启下的关键作用：一方面，物联网需要从感知 问题的研究进展进行总结；第6节展望RFID未来 到的海量原始数据中提取有效信息并进行管理，为 的研究方向；最后对全文进行总结 上层的特定应用提供数据支撑；另一方面，物联网需 要结合具体的数据管理需求来组织感知识别层面的 2RFID标签识别协议与防冲突算法 众多节点，在网络层面进行优化调度与资源配置，以 更有效地指导下层协议与算法的设计实现. 2.1RFID的标签识别协议 基于上述认识，本文关注RFID数据管理问题， 在通常的RFID应用中，大量的RFID标签往 以数据管理的核心技术为切入点，分别从RFID的 往被广泛地部署在指定区域中.为了能够快速有效 防冲突算法、RFID的认证与隐私保护协议以及真 地识别这些标签，阅读器需要在RFID标签识别协 实环境下RFID系统数据收集的性能评测与分析 议中使用一套有效的防冲突算法来逐一读取这些标 3个方面对RFID数据管理技术的研究与进展进行 签.在无线通信环境下，普通的无线设备主要基于载 分析与讨论.图1展示了上述3个方面研究问题之 波侦听多路访问/冲突避免(CSMA/CA)的竞争机 间的逻辑层次关系.其中，研究防冲突算法的目的是 制来实现多个设备之间的通信，如802.11协议.与 为MAC层提供一套快速的标签识别机制，实现 普通的无线节点不同，RFID标签是极为简单的无 RFID数据管理的高效性；研究安全协议的目的是 线设备，标签上的资源极其有限，不能够自发地通过

458 计 算 机 学 报 正 好满 足 了这 一 需 求 ．RFID是 一 种 非 接 触 式 的 自 动 识别 技术 ，它 通 过 射频 信 号 自动 识 别 目标 对 象 并 获 取相 关 数据 ，识别 工作 无 须人 工干 预．作 为 一种 简 单 的无 线 系 统 ，RFID 系统 只有 两 个 基 本 器件 ，一 个 是 阅读器 ，另 一个是标 签．其基本 工作原 理是 ：阅读 器 以广播方式连续向周 围发送携带能量 的基准信号 ， 感应到能量的标签通过调制 电路信号以反射的方式 向阅读 器 返 回 自身 携 带 的数 据 ，阅读 器 对 接 收 到 的 数据进行解码 ，并 传给 主机进行处理．通过 上述方 式 ，RFID 系统 能够 提 供 有 效 的身 份 信 息 (Identity) 和地 址 信 息 (Location)．相 比 于 其 它 智 能 系 统 ， RFID 系统 具有 如下 鲜 明特点 ：(1)能 够实 现 非 接触 式 的快速 自动识 别 ；(2)标 签 内能 够 永 久 存 储 一 定 大小 的数 据 ；(3)标 签 内含 一 定 数 目的逻 辑 门能 够 进行 简单 的逻 辑处 理 ；(4)标 签 具 有 普 通 无 线 设 备 的物理 属性 ；(5)标 签 成 本 低 廉 ，可 以 大 量 部 署 ．因 此 ，作 为 物 联 网感 知 识 别 层 面 的 一 项 关 键 技 术 ， RFID技术能够使得物联 网中的每一个物体被 唯一 地识 别 ，并且 能 够携 带规 范而 具有 互用 性 的信 息 ，在 无 源 的情况 下有 效 实现 “被动 智 能”，为 “物一物相 联 ” 提 供根 本保 障 ． 在 物联 网环 境 下 ，RFID 系 统 被 部 署 和 应 用 的 根 本 目的是 ：针 对具 体 的应用 需 求 ，对 被标 识 的物 理 对象进行合理有效 的信息收集 ，为上层应用提供最 基本的数据支持．因此 ，任何一种具体的 RFID应用 都 依赖 于 对 RFID 数 据 实 现 有 效 的数 据 管 理 ．所 谓 数据管理是指结合 RFID系统的应用需求实现有效 且 有 针对 性 的数据 收 集 、分 析挖 掘 以及 数 据 安 全 保 障等操 作 ．在 现有 的物 联 网体 系架构 中 ，数据 管理 起 着承 上启 下 的关键 作 用 ：一 方 面 ，物 联 网需要 从感 知 到 的海量 原始 数 据 中 提 取有 效 信 息 并 进 行 管 理 ，为 上层 的特 定应 用 提供 数据 支撑 ；另 一方 面 ，物联 网需 要结 合具 体 的数 据管 理需 求来 组织 感 知识 别层 面 的 众 多节 点 ，在 网络 层 面进 行优 化调 度 与资 源配 置 ，以 更有效地指导下层协议与算法 的设计实现． 基 于上 述认识 ，本文关 注 RFID数 据 管 理 问题 ， 以数据管理的核心技术为切入点 ，分别从 RFID的 防 冲突算 法 、RFID 的认 证 与 隐私 保 护 协 议 以及 真 实 环境 下 RFID 系 统 数 据 收 集 的 性 能 评 测 与 分 析 3个 方 面对 RFID数据 管 理 技术 的研 究 与 进 展进 行 分 析 与讨论 ．图 1展 示 了上 述 3个 方 面 研 究 问题 之 间的逻辑层次关系．其中，研究防冲突算法的目的是 为 MAC层 提供 一套 快 速 的标 签识 别 机 制，实 现 RFID数 据管 理 的 高 效 性 ；研 究 安 全 协 议 的 目的 是 为数据 管 理提供 基 本 的安 全 保 障 ，能 够 有 效地 实 现 认 证并 且保 护 用 户 隐 私 ，实 现 RFID数 据 管 理 的 可 信 性 ；对 RFID 系统 进行 性能 评测 与 分 析 ，其 目的 在 于验证 在 真实 环境 下物 理层 的关 键 因素对 系统 识 别 性能 的影 响 ，确保数 据 管理 的可 靠性 ．深入 探究 三 者 之 间的联 系 ，我们 发 现 任 一研 究 问题 均 对 其 余 二 者 产生 影 响 ：防冲突 算 法 能 够 提供 最 根 本 的数 据 传 输 支持 ，安全 协 议能 够实 现必 要 的安全 保 障 ，性 能评 测 能够 验证 在 真实 环境 下 的 系统 运 行 性 能．上 述 三 方 面研 究 问题 与 RFID 系统 协 议 栈 的对 应 关 系 如 图 1 所示 ，可 以看 到 三者 之间相 互 联系 ，又各 有侧 重． 图 1 各研 究 问 题 之 I司的逻 辑 层 次 关 系 本 文第 2节 主要 介 绍 RFID的标 签 识别 协 议 与 防冲 突算法 ，着 重 阐述 RFID标签 识 别 机制 、数 目估 算 机制 以及 轮 询机 制 方 面 的研究 工 作 ；第 3节 主 要 介 绍 RFID 的认 证 与 隐私 保 护 协 议 ，对 RFID 的 安 全 与 隐私 问题 进 行 探 讨 与 分 析 ，并 对 RFID 安 全 方 面 的三类 主 流技术 进 行 总 结 ；第 4节 对 真 实 环 境 下 RFID 系统性 能 的评 测 与 分析 方 面 的研 究 工 作 进 行 介 绍 ；第 5节 对 RFID 数 据 管 理 相 关 的 其 它 开 放 性 问题 的研 究 进展 进 行 总 结 ；第 6节 展 望 RFID 未 来 的研 究方 向 ；最后 对全 文进 行 总结 ． 2 RFID标签识别协议 与防冲突算 法 2．1 RFID的标 签识 别协 议 在 通常 的 RFID 应 用 中 ，大 量 的 RFID 标 签 往 往被广泛地部署在指定区域 中．为了能够快速有效 地 识别 这些 标 签 ，阅读 器 需 要 在 RFID标 签 识 别 协 议 中使用一套有效的防冲突算法来逐一读取这些标 签 ．在 无线 通信 环境 下 ，普通 的无 线设 备 主要基 于载 波侦听多路访 问／冲突避免 (CSMA／CA)的竞争机 制来实现多个设备之间的通信 ，如 802．11协议．与 普通的无线 节点不 同，RFID 标签是极为简单 的无 线 设备 ，标 签 上 的资源极 其 有 限 ，不 能够 自发 地通 过

3期 谢磊等：RFD数据管理：算法、协议与性能评测 459 调节自身的无线传输机会来避免标签间的传输冲 表1两类防冲突算法的优缺点比较 突.具体来说，标签没有足够的处理能力与能源来实 基于二进制树防冲突算法基于ALOHA防冲突算法 现上述竞争机制，避免通信冲突.鉴于RFD的系统 使用随机算法，算法实现逻粗简 通常使用确定性的算法， 特点，RFID标签识别协议需要具备如下性质： 算法实现逻辑简单：基于 单：平均情况下，标签识别性能良 优点 (1)简单.由于RFID标签上的计算、存储资源极其 查询树结构的算法不需 好：随机算法使得各时隙的结果 要存储中间状态变量 在统计意义上符合一定的概率分 布，有助于进行各种统计性分析 有限，标签识别协议的处理逻辑（包括执行流程和状 算法的随机性导致存在“饿死”问 态迁移关系)需要尽可能简单；(2)高效.面对大量 对基于查询树结构的算 题，某些标签可能永远选择不到 的RFID标签，标签识别协议需要提供轻量级的通 缺点 法，标签识别的时延受扫 描范围内标签ID的分 单时隙进行传输：最环情况下，标 布以及ID的长度影响 签识别的时延趋向于十∞，其性 信机制，尽可能避免不必要的控制报文的传输，确保 能无法保障 传输的高吞吐率与低延迟性。 隙，导致时隙的浪费；如果帧长过小，则该帧大部分 目前的RFID防冲突算法主要分为两大类：基 时隙会出现标签传输冲突，导致大部分标签需要在 于二进制树的防冲突算法1]和基于ALOHA的防 下一帧重传.因此，研究者们对该问题进行了深入研 冲突算法[3]，前者利用二叉搜索树，按照递归的方 究.文献[5]分析了在时隙ALOHA协议中采用动 式将冲突的标签集合划分为两个标签子集，对于可 态帧长的方法对读取性能的影响.文献[6]基于贝叶 能产生冲突的相关标签集合，采用沉默的方式来解 斯的概率模型提出了优化动态帧长的决策机制.文 决冲突问题.划分子集的方法包括随机二进制树算 献[7]利用马尔可夫过程来对读取过程进行建模，并 法和查询二进制树算法.文献[1]提出了一套自适应 且由此计算出读取过程中应该使用的一系列优化的 的基于树形结构的防冲突算法来实现有效的标签识 帧长.文献[8]进一步针对最大化信道使用效率的目 别.文献[2]提出了-一套基于查询树结构的智能遍历 标推导出优化的动态帧长，该文指出，如果每一轮中 机制，能够以低延迟的方式实现标签的识别. 帧长与当前未读取的标签数相同，则整个信道能够 ALOHA协议最早被用在分组无线网络中实现随机 达到最大的使用效率.其原理阐述如下：假设当前标 访问机制.在RFID系统中，为了提高标签识别的效 签数目为n,帧长为f；由于标签对时隙的选择符合 率，文献[3-4]提出了时隙ALOHA协议来有效解 二项分布，则根据二项分布，当前帧中单时隙的期望 决冲突，实现标签的高效识别.时隙ALOHA协议 数目为E[n]=n×(1一1/f)-1,为了最大化信道 将若干个时隙组织为一帧，在每一帧开始时，阅读器 的使用效率，即单时隙数目在当前帧中的比例 广播帧的长度f,即当前帧所包含的时隙个数，并通 n/f,我们采用求极值的方法计算f的取值，即 过发送连续的电磁波来激活扫描范围内所有标签. 每个标签在接收到帧长f之后随机独立地在第1~ E[m]f=0→∫·=n,得到此时信道的使用效率 8f f个时隙中选择一个时隙发送标识符.如果成功，即 为n/f”→1/e.对于上述性质，我们在图2和图3 无冲突发生，该标签进入静默状态；如果有冲突发 中给出更为形象的描述，图2展示了给定标签数目 生，则该标签将继续等待在下一帧中再选择一个时 n=100,帧长f变化对信道使用效率的影响.可以 隙重新发送标识符.因此，每一帧的时隙会存在如下 看到当帧长∫由小及大变化时，信道的使用效率逐 3种情况之一：(1)空时隙(Empty Slot).没有任何 渐增大后又逐渐减小，在f=100时取到最大值1/e. 一个标签选中该时隙；(2)单时隙(Singleton Slot).. 图3展示了随着标签数目n变化，使用最优帧长 仅有唯一一个标签选中该时隙；(3)冲突时隙 f·=n对信道使用效率的影响.可以看到当n取值 (Collision Slot).多个标签选中该时隙.上述每种时 较小时，所达到的最优效率大于1/e,例如，当仅有 隙所包含的信息量各不相同.目前，时隙ALOHA 一个标签时(n一1)，帧长为1可以达到最优效率 协议已经成为RFID系统在EPC-CIG2标准下使用 100%.当n逐渐增大时，其最优效率快速收敛到 的通信协议.在表1中，我们分别从优缺点两个方面 1/e.这就意味着，当n>5时，每一轮帧长f取值为 对上述两种防冲突算法进行了比较，总体而言，两者 当前待读的标签数n时，使用效率趋向于1/e,可以 在性能与功能实现方面各有利弊， 达到当前每一轮的局部最优效率.如果在识别过程 对于时隙ALOHA协议而言，每一轮所采用的 中每一轮都使用该策略，则整体效率可接近1/e.由 帧长对总体的识别性能至关重要.对于给定的待读 于1/e是整体效率的上限值，因此当前整体效率接 标签集合，如果帧长过大，则该帧大部分时隙为空时 近全局最优

3期 谢 磊等 ：RFID数 据管理 ：算法 、协议与性能评测 459 调节 自身 的无线传 输机会来避免标签 间的传输 冲 突．具体 来说 ，标签 没有 足够 的处 理能 力 与能源 来实 现上述竞争机制，避免通信冲突．鉴于 RFID的系统 特 点 ，RFID 标 签 识 别 协 议 需 要 具 备 如 下 性 质 ： (1)简单 ．由于 RFID标签 上 的计 算 、存 储 资 源 极其 有 限 ，标 签识 别协 议 的处理 逻辑 (包括 执行 流程 和状 态迁 移关 系 )需 要 尽 可 能 简单 ；(2)高 效 ．面对 大量 的 RFID标 签 ，标 签识 别 协 议 需 要 提 供 轻 量 级 的通 信 机制 ，尽 可能避 免不 必要 的控 制报 文 的传输 ，确保 传输 的高吞吐率与低延迟性． 目前 的 RFID 防 冲突 算法 主要 分 为 两 大 类 ：基 于二 进制 树 的防 冲突算 法 l_】]和基 于 ALOHA 的 防 冲 突算法 _3]．前 者 利 用 二叉 搜 索 树 ，按 照递 归 的方 式将 冲突 的标签集 合划 分 为 两 个 标 签 子集 ，对 于 可 能产生冲突的相关标签集合 ，采用沉默 的方式来解 决 冲突 问题 ．划分 子 集 的方 法 包 括 随机 二 进 制 树算 法 和查询 二进 制树 算法 ．文 献 [1]提 出 了一 套 自适应 的基 于树 形结 构 的防 冲突算 法来 实现 有效 的标 签识 别 ．文献 E2]提 出了一套 基 于查询 树结 构 的智能 遍 历 机 制 ，能 够 以 低 延 迟 的 方 式 实 现 标 签 的 识 别 ． ALOHA协 议最 早被 用在 分组 无线 网络 中实 现 随机 访 问机制 ．在 RFID系统 中 ，为 了提 高 标 签识 别 的效 率 ，文献 [3—4]提 出 了 时 隙 ALOHA 协 议 来 有 效 解 决 冲突 ，实 现标 签 的 高 效 识 别 ．时 隙 ALOHA 协 议 将若 干个 时 隙组织 为一 帧 ，在每 一帧 开始 时 ，阅读器 广播帧的长度 ．厂，即当前帧所包含的时隙个数，并通 过发 送连 续 的 电磁 波来 激 活 扫 描 范 围 内所 有 标 签 ． 每个 标签 在接 收到 帧长 -厂之 后 随机 独立 地 在第 1～ ，个时隙中选择一个时隙发送标识符．如果成功 ，即 无 冲突发 生 ，该 标 签 进 入 静 默 状 态 ；如果 有 冲 突发 生 ，则该标签将继续等待在下一 帧中再选择一个 时 隙重新发送标识符．因此 ，每一帧的时隙会存在如下 3种 情 况之 一 ：(1)空 时 隙 (EmptySlot)．没 有 任 何 一 个 标签 选 中该时 隙 ；(2)单 时 隙 (SingletonSlot)． 仅有 唯 一 一 个 标 签 选 中 该 时 隙 ；(3)冲 突 时 隙 (CollisionSlot)．多个标 签 选 中该 时 隙．上 述 每 种 时 隙所包含 的信息量各 不相 同．目前 ，时隙 ALOHA 协议 已经 成为 RFID系统 在 EPC—c1G2标 准下 使用 的通信 协 议．在 表 1中 ，我们 分别从 优 缺点 两个 方面 对上述两种防冲突算法进行 了比较 ，总体而言 ，两者 在性 能与 功能 实现 方 面各有 利弊 ． 对于时隙 ALOHA协议而言 ，每一轮所采用 的 帧长对总体的识别性能至关 重要．对于给定 的待读 标签集合 ，如果帧长过大 ，则该帧大部分时隙为空时 表 1 两类防冲突算法的优 缺点比较 基 于二进制树 防冲突算法 基于 ALOHA 防冲突算 法 莩妻孽要塞譬 墨焉 卺磊譬 优点 誊笙 l辋 萋需孬：嚣 葫 缮巢芬 要存储中间状态变量 茬 翌 慧I 篓惹 缺点鎏布以及I内D的篷长度影响分军 凳毽～螽；’，”：霍 隙 ，导致 时 隙的浪 费 ；如 果 帧 长 过 小 ，则该 帧 大部 分 时 隙会 出现标 签传 输 冲 突 ，导 致 大 部 分标 签 需 要 在 下 一帧重 传 ．因此 ，研究 者们 对该 问题 进行 了深入 研 究 ．文献 [5]分 析 了在 时 隙 ALOHA 协议 中采 用 动 态 帧长 的方 法对读 取性 能 的影 响．文 献E6]基 于 贝 叶 斯 的概率 模 型提 出 了优 化 动 态 帧 长 的决 策 机 制．文 献 [7]利 用 马尔可 夫过 程来 对读取 过 程进行 建模 ，并 且 由此计 算 出读取 过程 中应 该使 用 的一系列 优化 的 帧 长．文 献 [8]进一 步针 对最 大化 信道 使用效 率 的 目 标 推导 出优 化 的动态 帧长 ，该文 指 出 ，如果 每一 轮 中 帧 长与 当前 未读取 的标 签 数 相 同 ，则 整个 信 道 能 够 达到最大的使用效率．其原理阐述如下：假设 当前标 签数 目为 ，帧长为 -厂；由于标签对时隙的选择符合 二项 分布 ，则 根据 二项分 布 ，当前 帧 中单时 隙的期 望 数 目为 E[ ]一 ×(1—1／f)一 ；为了最大化信道 的使 用 效 率 ，即单 时 隙 数 目在 当前 帧 中 的 比例 ／f，我 们 采 用 求 极 值 的 方 法 计 算 -厂的 取 值 ，即 aF r ] ／ 一0一 f 一 ，得 到此 时信道 的使用效率 Uj 为 m／f 一 1／e．对 于 上述 性 质 ，我们 在 图 2和 图 3 中给 出更 为形 象 的描 述 ．图 2展 示 了给定 标 签 数 目 7"／z100，帧长 厂变化对信道使用效率的影响．可 以 看到当帧长 厂由小及大变化 时，信道的使用效率逐 渐增 大后 又逐 渐减 小 ，在 ．厂一100时取 到最 大值 1／e． 图 3展 示 了 随 着 标 签 数 目 n变 化 ，使 用 最 优 帧 长 f 一 对信 道使 用效 率 的影 响．可 以看 到 当 n取 值 较小 时 ，所达 到 的最 优 效 率 大 于 1／e，例 如 ，当仅 有 一 个 标签 时 ( 一 1)，帧 长 为 1可 以 达 到 最 优 效 率 100 ．当 逐 渐 增 大 时 ，其 最 优 效 率 快 速 收 敛 到 1／e．这 就意 味着 ，当 > 5时 ，每 一 轮 帧长 ．厂取 值 为 当前待读 的标签数 n时，使用效率趋 向于 1／e，可 以 达到当前每一轮的局部最优效率．如果在识别过程 中每一轮都使用该策略 ，则整体效率可接近 1／e．由 于 1／e是整体效率 的上限值 ，因此 当前整体效率接 近全局 最 优．

460 计算机学 报 2013年 0 出了一套RFID标签读取性能的概率模型，基于时 隙ALOHA协议设计出优化的标签识别参数，相比 8 传统的识别机制更为有效地提升了识别的性能， 2.2RFID的标签数量估算机制 0.2 随着RFID应用的进一步拓展，某些应用仅需 要获取一些统计性信息来为上层的数据分析以及挖 0.1 掘提供数据基础.在这种情况下，RFD系统不需要 逐个识别标签，仅仅需要快速获取扫描范围内标签 100 200 300 400 的统计信息，其中一个关键的信息就是标签数量.此 顿长f 外，基于动态帧长的时隙ALOHA协议也需要估算 图2给定标签数目n=100,信道使用效率与帧长f的关系 标签的大体数量来决定动态帧的长度.因此，近年来 1.0 出现了很多关注于如何快速、精确地估算标签数目 的研究工作，其核心思想主要是使用基于随机算法 0.8 罗 的时隙ALOHA协议来实现估算，研究者们意识 到，尽管时隙ALOHA协议是以随机的方式让标签 0.6 选择时隙进行数据传输，然而从统计意义上来看，整 0.4 个空时隙、单时隙以及冲突时隙的分布事实上是符 合二项分布的.当对时隙的采样次数足够多时，完全 0.2 可以基于二项分布规律来估算出实际参与标签的数 量.基于上述思路，文献[13]提出了一套快速而可靠 20 40 60 80 100 顿长f 的标签数量估算机制，以一种实用的方式实现了 RFID标签的快速统计.其主要思想为：假设在某一 图3随着标签数目n变化，使用最优帧长f·=n 对应的信道使用效率 轮中帧的长度为f,空时隙的数目会随着实际参与 的标签数n增加而减少，冲突时隙的数目会随着标 上述提到的协议与防冲突算法多数是在较为理 签数n增加而增加，而单时隙的数目会随着标签数 想的部署环境下得出，并未充分考虑实际应用环境 n增加先增加再减少，因此，空时隙（冲突时隙）的 下所遇到的种种雄题，例如，标签的频繁移动、多个 数目与标签数存在明确的单调减（增）关系.该文作 RFID阅读器之间的信号干扰、RFID标签传输的信 者基于二项分布的概率模型给出了空时隙与冲突时 号衰减以及多径效应等.因此，一些研究工作开始关 隙的数值期望计算公式，提出了空时隙与冲突时隙 注并尝试解决上述问题.鉴于之前的研究工作大多 相结合的估算算法，并通过重复采样的手段有效降 关注于解决标签之间的传输冲突问题，并未考虑到 低了估算的误差.研究者们通过进一步研究发现，尽 多个阅读器之间以及标签与阅读器之间的信号干 管单时隙数目与标签数目不存在单调关系，无法利 扰，文献[9-10]在多个RFID阅读器环境下提出了 用单时隙数目推算出确切的标签数目，但是3种时 优化的阅读器激活与调度机制，使得多个阅读器能 隙的数目结合起来能够指导系统更精确地估算标签 够协作地识别标签，有效避免信号的传输冲突.考虑 数目.文献[14]根据观察到的3种时隙的数目提出 到单个RFID阅读器的有效读取范围相对有限，文 了一套后验概率模型，基于最大化后验概率的决策 献[11]利用“时空关联”关系提出了性能高效的连续 来更精确地实现标签数量估算机制.上述机制均需 扫描机制，来实现对大规模部署标签的快速识别.之 要对3种时隙进行大量采样来提高估算的精确度， 前大部分的研究工作主要考虑在相对理想状态下针 事实上，完全可以借助其它参量来更快速有效地估 对静态环境设计优化的标签识别机制，并未考虑移 算标签数目.我们在文献[15]中提出了一种基于 动环境以及传输环境中普遍存在的信号衰诚对标签 Ball-and-Bin概率模型的快速估算方法.其核心思想 识别性能带来的影响.有鉴于此，我们针对上述问题 在于：每个标签会随机选择位置回复，系统可以通过 开展了相应的研究工作，文献[12]针对移动环境下 观察第一个标签回复的位置来估算最有可能造成该 持续变化的信号衰减情形，基于跨层优化的思路提 事件发生的标签数量.该文从理论上建立了概率模

460 计 算 机 学 报 图 2 给定标签数 目，z一100，信道使用效率与帧长 ，的关系 趔 _K Ⅲ【苷 薰 槲 较 旺 图 3 随着标签数 目 变化 ，使用 最优 帧长厂 — 对 应的信道使用效率 上述 提 到 的协议 与 防冲 突算法 多数 是在 较 为理 想 的部署 环境 下 得 出 ，并 未 充 分 考 虑实 际应 用 环 境 下所 遇 到 的种 种 难 题 ，例 如 ，标 签 的频 繁 移 动 、多 个 RFID阅读器之间的信号干扰、RFID标签传输 的信 号衰减以及多径效应等．因此 ，一些研究工作开始关 注并 尝试 解决 上 述 问 题．鉴 于 之 前 的研 究 工 作 大 多 关 注于解 决 标签 之 间 的 传输 冲 突 问题 ，并 未 考 虑 到 多个 阅读 器 之 间 以及 标 签 与 阅 读 器 之 间 的 信 号 干 扰 ，文献 [-9一lo3在 多 个 RFID 阅读 器 环 境 下 提 出 了 优 化 的阅读 器激 活 与 调 度 机 制 ，使 得 多 个 阅 读 器 能 够 协作 地识 别标 签 ，有效 避 免信号 的传输 冲突 ．考 虑 到 单个 RFID 阅读 器 的有 效 读 取 范 围相 对 有 限 ，文 献[11]利用“时空关联”关系提出了性能高效的连续 扫 描机 制 ，来实 现对 大 规模 部署 标签 的快 速识 别 ．之 前大部分的研究工作主要考虑在相对理想状态下针 对 静 态环 境设 计优 化 的标 签 识 别 机 制 ，并 未 考 虑 移 动环境以及传输环境中普遍存在的信号衰减对标签 识别 性能 带来 的影 响．有鉴 于此 ，我 们针 对上 述 问题 开展 了相应的研究工作 ，文献 [12]针对移动环境下 持续变化 的信号衰减情形，基于跨层优化 的思路提 出 了一套 RFID标 签 读 取 性 能 的概 率 模 型 ，基 于 时 隙 ALOHA协 议设 计 出优 化 的标 签识 别 参 数 ，相 比 传统 的识 别机 制 更为 有效 地提 升 了识别 的性 能． 2．2 RFID 的标签 数 量估算 机 制 随 着 RFID应 用 的进 一 步 拓 展 ，某 些 应 用 仅 需 要获 取 一些 统计 性信 息来 为上 层 的数据 分析 以及 挖 掘提 供 数据基 础 ．在 这 种 情况 下 ，RFID 系统 不 需 要 逐个 识 别标 签 ，仅 仅 需 要 快 速 获 取 扫描 范 围 内标 签 的统计 信息 ，其 中一个 关键 的信息 就是 标签数 量 ．此 外 ，基于 动态 帧长 的时隙 ALOHA 协议 也 需 要估 算 标 签 的大体 数量 来决 定动 态 帧 的长度 ．因此 ，近 年来 出现 了很 多关注 于 如 何 快 速 、精 确 地估 算 标 签 数 目 的研 究 工作 ，其 核 心思 想 主 要 是 使 用基 于 随机 算 法 的时 隙 ALoHA 协 议 来 实 现 估 算 ．研 究 者 们 意 识 到 ，尽 管 时隙 ALOHA协 议是 以随机 的方 式 让标 签 选 择 时隙进 行数 据 传输 ，然 而从统 计 意义上 来 看 ，整 个 空 时隙 、单 时隙 以及 冲 突时 隙 的分 布 事 实 上 是符 合 二项 分布 的．当对 时 隙 的采样次 数 足够 多时 ，完全 可 以基 于 二项 分布 规律 来估 算 出实 际参 与标签 的数 量 ．基 于上 述思 路 ，文献 [-13]提 出 了一 套快 速而 可靠 的标签 数 量 估 算 机 制 ，以 一 种 实 用 的 方 式 实 现 了 RFID标 签 的快速 统 计．其 主要 思 想 为 ：假 设 在 某 一 轮 中帧 的长度 为 厂，空 时 隙 的 数 目会 随着 实 际 参 与 的标 签数 n增加 而减 少 ，冲 突 时 隙 的数 目会 随 着 标 签数 增 加 而增加 ，而 单 时 隙 的数 目会 随 着 标 签 数 n增加 先增 加 再 减 少 ，因 此 ，空 时 隙 (冲 突 时 隙 )的 数 目与标 签数 存在 明确 的单 调 减 (增 )关 系．该 文 作 者基 于二 项分 布 的概 率模 型 给出 了空 时隙与 冲 突时 隙 的数值 期 望计算 公 式 ，提 出 了 空 时 隙与 冲突 时 隙 相结 合 的估算 算 法 ，并 通 过 重 复 采样 的手 段 有 效 降 低 了估算 的误差 ．研究 者们 通 过进 一步 研究 发现 ，尽 管 单时 隙数 目与标 签 数 目不 存 在 单 调 关 系 ，无 法 利 用 单时 隙数 目推 算 出 确 切 的标 签 数 目，但 是 3种 时 隙的数 目结 合起 来 能够 指导 系统更 精 确地估 算 标签 数 目．文献 [-14]根据 观 察 到 的 3种 时 隙 的数 目提 出 了一套 后验 概率 模 型 ，基 于最 大 化 后 验 概率 的决 策 来更精确地实现标签数量估算机 制．上述机制 均需 要对 3种时隙进行大量采样来提高估算 的精确度 ， 事实上，完全可以借 助其它参量来更快速有效地估 算标签数 目．我 们在 文献 [15]中提 出了一 种基 于 Ball—and—Bin概率模型的快速估算方法．其核心思想 在 于 ：每个 标 签会 随机 选择 位置 回复 ，系 统可 以通 过 观察第一个标签 回复的位置来估算最有可能造成该 事件 发 生 的标签 数量 ．该 文 从 理论 上建 立 了概 率 模

3期 谢磊等：RFD数据管理：算法、协议与性能评测 461 型，并证明了其正确性和性能的上界.实验表明，在 标签的标识符ID,每传输一个ID后，阅读器会等 给定精度要求的情况下，该方法明显快于现有其它 待对应的标签返回一个短暂的响应消息，如果接收 方法.此外，为了解决单个标签被多次读取的问题， 到响应，则推断该标签存在于扫描范围内，否则认为 文献[16们提出了一套“复制不敏感”的估算机制来实 该标签丢失，然而，上述方案存在如下弊病：(1)与 现更精确的标签数量统计.文献[17]提出了一个自 时隙ALOHA协议不太兼容；(2)长达96bit的ID 适应的基于划分的估算机制，该机制基于几何分布 传输使得整体扫描时间过长，降低了系统的效率.因 规律让单个标签选择同一帧中的多个时隙进行传 此，研究者们针对上述问题开展了深入的研究，其目 输，使得每个标签有1/2的概率选择第t一1个时 标为基于时隙ALOHA协议设计出一套有效的标 隙，有效解决了单个标签被多次读取的问题.表2对 签轮询机制，尽可能地减少整体扫描时间。 上述研究工作的特点进行了总结和比较， 研究发现，在时隙ALOHA协议的每一轮中， 表2标签数量估算算法的特点总结与比较 处于激活状态的标签会“随机”地在帧中选择一个时 估算算法 与时腺ALOHA 隙进行传输.然而，由于标签的简易性，真正的随机 协议兼容性 估算参考的指标 概率模型 性很难得到实现.事实上，标签的芯片逻辑实现了一 文款[13] 兼容 空时隙与冲突时 二项分布 个“伪随机”的操作：在每一轮中阅读器广播一个随 隙的数目 基于二项分布的 机数r,每个被激活的标签接收到，后随即结合本 文献[14] 兼容 3种时隙的数目 后验概率模型 地的标识符ID进行散列操作，计算出伪随机数s作 文献[15] 兼容 第一个标签回复 的位置 二项分布 为选定的时隙序号，这里s=hash(ID,r)modf,f 文献[16-17] 不兼容 冲突时隙出现的 几何分布 是帧的长度.上述的“伪随机性”意味着，对于任一标 边缘位置 签，一旦阅读器广播的数值？以及帧的长度∫确定 除了对标签数量进行简单估算之外，一些研究 下来，该标签在帧中相应的位置即被确定，这就使得 工作者开始探究如何在RFID系统上实现更为复杂 对标签的有效轮询成为可能.在实施扫描之前，阅读 的数据分析与挖掘机制.文献[18]着力研究面对大 器可以预先根据指定集合内各标签在帧中对应的位 量的RFID标签，如何在不需要读取所有标签具体 置为每个时隙计算出期望的结果：空时隙(0)、单时 信息的前提下快速定位出最热门的标签类别.该文 隙(1)或者冲突时隙(C).对于某一时隙，如果该时 基于分组测试(Group Testing)的理念，提出了有效 隙期望为单时隙但实际无响应，则表明对应于该时 的随机算法来解决上述问题.文献[19]面向流量追 隙的标签丢失；如果该时隙期望为冲突时隙但实际 踪一类的应用问题，针对动态移动的标签集合提出 无响应，则表明对应于该时隙的所有标签丢失.图4 了保障隐私的快速估算机制.该机制能够快速统计 给出了基于时隙ALOHA协议的轮询机制示意图. 在时域(t,t2)内从地点A移动到地点B的标签数 如图所示，在标签A~H中，虚线标识丢失的标签， 目，从而在无需读取确切标签ID信息的前提下有 实线标识存在的标签.当标签E、F以及H丢失时， 效地进行流量追踪。总体而言，目前该方面的研究成 其对应的时隙实际观察到的状态变成空时隙(0)，此 果相对较少，随着RFID数据管理技术以及相关应 时可以判定标签丢失.但对于标签C丢失的情况， 用的进一步拓展，基于RFID的数据分析与挖掘机 由于标签B、D的存在，使得对应时隙实际观察到的 制必将得到更为广泛的关注与深人的研究。 状态仍为冲突时隙(C),未能判断出标签C丢失的 2.3RFID的标签轮询机制 情况，导致假阳性误判(False Positive).上述轮询机 某些RFID应用并不需要获取全部RFID标签 标签A标签B标签C标签D标签E标签F标签G标签H 的标识信息，仅需要对指定集合内的标签进行轮询， 来确认标签的状态是存在或丢失.例如，对仓库管理 应用而言，出入库之前管理员需要根据货物清单来 期望的 状态 0010c00 …c11oo 清点指定的货物，确定是否存在货物丢失.在这种情 况下，假设所有的货物都贴有唯一标识的RFID标 签，能否有效地实现标签的轮询机制成为与此密切 轮询判断 未能判断出标 标签E 相关的问题.最简单直接的方案便是设计一种类似 的结果 签C丢失，假 阳性误判 标签F丢失标签H丢失 于“点名”的机制：阅读器根据清单内容接连地广播 图4基于时隙ALOHA协议的轮询机制示意图

3期 谢 磊等 ：RFID数据管理 ：算法 、协议 与性 能评 测 461 型 ，并 证 明 了其 正 确 性 和性 能 的上 界 ．实 验 表 明 ，在 给定精 度 要求 的情 况 下 ，该 方 法 明显 快 于 现有 其 它 方法 ．此外 ，为 了解 决 单 个 标 签 被 多 次读 取 的 问题 ， 文献 [16]提 出了一套 “复 制不 敏感 ”的估 算 机制来 实 现更精确的标签数量统计．文献[17]提出了一个 自 适 应 的基 于划分 的估 算 机 制 ，该 机 制基 于几 何 分 布 规律让单个标签选择 同一 帧中的多个时 隙进行传 输 ，使 得 每 个 标 签 有 1／2的 概 率 选 择 第 一1个 时 隙 ，有 效解 决 了单个 标签 被 多次读 取 的问题 ．表 2对 上 述研 究 工作 的特 点进行 了总结 和 比较． 表 2 标签数量估 算算法的特点总结与 比较 估算算法 与 协 H~ 议兼 A 容 LO 性 HA 估算参考 的指标 概率模型 除 了对标签数量进行简单估算之外 ，一些研究 工作 者 开始探 究 如何 在 RFID 系统 上实 现更 为复 杂 的数 据 分析 与挖 掘机 制 ．文 献 E18]着 力 研 究 面 对 大 量的 RFID标签 ，如何在不需要读取所有标签具体 信 息 的前提 下快 速 定 位 出最 热 门 的标 签 类 别．该 文 基 于分 组测 试 (GroupTesting)的理 念 ，提 出 了有 效 的随机 算法 来解 决 上述 问题 ．文 献 [19]面 向流 量 追 踪 一类 的应 用 问题 ，针 对 动 态 移 动 的标 签 集 合 提 出 了保 障隐私 的快 速 估算 机 制 ．该 机制 能 够 快 速 统 计 在 时域 ( ，tz)内从 地 点 A 移 动到 地 点 B的 标 签 数 目，从而 在无 需 读 取 确 切 标 签 ID 信 息 的 前 提 下 有 效 地进 行 流量追 踪．总体 而言 ，目前 该方 面 的研究 成 果 相对 较少 ，随 着 RFID 数 据 管 理 技 术 以及 相 关 应 用 的进 一步 拓 展 ，基 于 RFID 的数 据 分 析 与 挖 掘 机 制 必将 得 到更为 广泛 的关 注 与深入 的研 究． 2．3 RFID的标签 轮 询机 制 某 些 RFID应 用并 不需 要 获 取 全部 RFID标 签 的标 识 信息 ，仅需 要对 指定 集合 内的标签 进行 轮询 ， 来确 认 标签 的状 态是存 在 或丢 失．例 如 ，对仓 库管 理 应 用而 言 ，出入库 之 前 管 理 员 需要 根 据 货 物 清 单 来 清点指定的货物 ，确定是否存在货物丢失．在这种情 况下 ，假设所有 的货物都贴有唯一标识 的 RFID标 签 ，能否有效地实现标签 的轮询机制成为与此密切 相关 的问题．最简单直接的方案便是设计一种类似 于“点名 ”的机制 ：阅读 器 根 据 清单 内容 接 连 地 广 播 标签 的标 识符 ID，每 传 输 一 个 ID 后 ，阅 读 器会 等 待对 应 的标签 返 回一 个 短 暂 的 响应 消 息．如 果 接 收 到 响应 ，则 推 断该标 签存 在 于扫描 范 围 内，否 则认 为 该标 签丢 失．然 而 ，上 述 方 案 存 在 如 下 弊 病 ：(1)与 时 隙 ALOHA 协议不 太兼 容 ；(2)长达 96bit的 ID 传输使得整体扫描时间过长 ，降低了系统的效率．因 此 ，研究 者 们针 对上 述 问题 开 展 了深 入 的研究 ，其 目 标为基 于 时 隙 ALOHA 协 议 设 计 出一 套 有 效 的 标 签轮 询机 制 ，尽 可 能地减 少整 体扫 描 时间． 研 究 发现 ，在 时 隙 ALOHA 协 议 的 每 一 轮 中 ， 处 于激 活状 态 的标 签会 “随机 ”地在 帧 中选择 一个 时 隙进行 传输 ．然 而 ，由于 标签 的简 易 性 ，真 正 的随机 性 很难 得 到实现 ．事 实上 ，标签 的芯 片逻 辑实 现 了一 个 “伪 随机 ”的操 作 ：在 每 一 轮 中 阅读 器 广 播 一个 随 机数 r，每个 被 激 活 的标 签 接 收 到 r后 随 即结 合 本 地 的标 识 符 ID 进行 散列 操作 ，计算 出伪 随机数 S作 为选定 的时 隙序 号 ，这里 S—hash(ID，r)roodf，f 是 帧 的长度 ．上 述 的“伪 随机性 ”意 味着 ，对于 任一标 签 ，一旦 阅读器 广播 的数 值 r以及 帧 的 长 度 ．厂确定 下 来 ，该 标 签在 帧 中相应 的位 置 即被 确定 ，这 就使得 对 标签 的有 效轮 询成 为可 能．在实施 扫描 之前 ，阅读 器 可 以预先 根据 指定 集合 内各 标签 在 帧中对应 的位 置为 每个 时隙计 算 出期 望 的结 果 ：空 时 隙 (O)、单 时 隙(1)或者冲突时隙(C)．对 于某一时隙 ，如果该 时 隙期望 为单 时 隙但 实 际 无 响应 ，则 表 明对 应 于 该 时 隙 的标 签 丢失 ；如果 该 时 隙 期 望 为 冲 突时 隙 但 实 际 无 响应 ，则 表 明对 应 于该 时 隙 的所 有 标 签 丢失 ．图 4 给出 了基 于时 隙 ALOHA 协议 的轮询 机 制 示 意 图． 如 图所 示 ，在标 签 A～H 中 ，虚线 标 识 丢失 的标 签 ， 实 线标 识存 在 的标 签 ．当标 签 E、F以及 H 丢失 时 ， 其 对应 的时 隙实际 观察 到的状 态变 成 空时 隙(O)，此 时可 以判定 标 签 丢 失 ．但 对 于 标 签 C丢 失 的情 况 ， 由于标签 B、D的存在 ，使得对应时隙实际观察到的 状 态仍 为 冲突 时 隙 (C)，未 能 判 断 出标 签 C丢失 的 情 况 ，导 致假 阳性 误判 (FalsePositive)．上述 轮 询机 i 、 ’照’ 囤} 睡一 、 、 ． ＼ } ／ lOlol c oI… lcll o 旺Ⅱ王旺[二Ⅱ口珂 呈失 双 图 4 基 于时 隙 ALOHA协议 的轮询机制示 意图