第36卷第3期 计算机学报 Vol.36 No.3 2013年3月 CHINESE JOURNAL OF COMPUTERS Mar.2013 RFID数据管理：算法、协议与性能评测 谢磊殷亚凤陈曦陆桑璐陈道蓄 (南京大学计算机软件新技术国家重点实验室南京210093) 摘要随着物联网关键理论及技术的发展,RFID作为物联网的核心支撑技术,成为物联网领域备受关注的研究 热点之一.文中以RFID的数据管理为切人点，从算法、协议以及性能评测3个层面对RFID的研究工作进行闸述 与分析，着重介绍了RFID的防冲突算法、认证与隐私保护协议以及真实环境下系统的性能评测与分析等方面的研 究成果及进展.最后展望了未来的研究方向. 关键词射频识别；数据管理；防冲突算法；认证与隐私保护；性能优化；物联网 中图法分类号TP393 DOI号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 Softuare 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的技术原理被进一步深入理解、 1引言 廉价的RFID组件相继出现以及RFID的安全得到 保障，RFID技术将会在物联网应用中发挥越来越 随着“物联网”时代的来临，新一代IT技术将 重要的作用 被充分运用在各行各业之中.射频识别(RFID)作为 物联网的核心理念是在普适环境下实现“物-物 物联网应用的一项核心支撑技术，在学术界与工业 相联”，即通过对物理世界信息化、网络化，将传统上 界已经得到广泛关注.目前，RFID技术正在越来越 分离的物理世界与信息世界实现互联与整合.这就 频繁地出现在大量的物联网应用中，包括物流管理、 需要将“智能”嵌人到每一个物理对象当中，并且提供 电子支付、RFID护照、安全访问控制、目标监测与 一种有效的、低成本的通信方式，RFID技术的出现 收稿日期：2012-02-08：最终修改稿收到日期：2012-05-27.本课题得到国家“九七三”重点基础研究发展规划项目基金(2009CB320705)、国家 自然科学基金(61100196,61073028,61021062)以及江苏省自然科学基金(BK2011559)资助.谢磊，男，1982年生，博士，讲师，中国计算机 学会(CCF)会员，主要研究方向为传感器网络、RFID系统、车联网、高性能计算.E-mail:lxie@nju.edu.cn.殷亚凤，女，1989年生，博士研究 生，中国计算机学会(CCF)学生会员，主要研究方向为RFID.陈曦，男，1988年生，硕士研究生，中国计算机学会(CCF)学生会员，主要研究 方向为RFID.陆桑璐，女，1970年生，博士，教授，博士生导师，中国计算机学会(CCF)会员，主要研究领域为普适计算、分布式计算、传感 器网络.陈道蓄，男，1947年生，教授，博士生导师，中国计算机学会(CCF)高级会员，主要研究领域为普适计算、分布式计算、计算机网络
书 第３６卷第３期 ２０１３年３月 计 算 机 学 报 ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲＳ Ｖｏｌ．３６Ｎｏ．３ Ｍａｒ．２０１３ 收稿日期：２０１２０２０８；最终修改稿收到日期：２０１２０５２７．本课题得到国家“九七三”重点基础研究发展规划项目基金（２００９ＣＢ３２０７０５）、国家 自然科学基金（６１１００１９６，６１０７３０２８，６１０２１０６２）以及江苏省自然科学基金（ＢＫ２０１１５５９）资助．谢磊，男，１９８２年生，博士，讲师，中国计算机 学会（ＣＣＦ）会员，主要研究方向为传感器网络、ＲＦＩＤ系统、车联网、高性能计算．Ｅｍａｉｌ：ｌｘｉｅ＠ｎｊｕ．ｅｄｕ．ｃｎ．殷亚凤，女，１９８９年生，博士研究 生，中国计算机学会（ＣＣＦ）学生会员，主要研究方向为ＲＦＩＤ．陈曦，男，１９８８年生，硕士研究生，中国计算机学会（ＣＣＦ）学生会员，主要研究 方向为ＲＦＩＤ．陆桑璐，女，１９７０年生，博士，教授，博士生导师，中国计算机学会（ＣＣＦ）会员，主要研究领域为普适计算、分布式计算、传感 器网络．陈道蓄，男，１９４７年生，教授，博士生导师，中国计算机学会（ＣＣＦ）高级会员，主要研究领域为普适计算、分布式计算、计算机网络． 犚犉犐犇数据管理：算法、协议与性能评测 谢磊殷亚凤陈曦陆桑璐陈道蓄 （南京大学计算机软件新技术国家重点实验室南京２１００９３） 摘要随着物联网关键理论及技术的发展，ＲＦＩＤ作为物联网的核心支撑技术，成为物联网领域备受关注的研究 热点之一．文中以ＲＦＩＤ的数据管理为切入点，从算法、协议以及性能评测３个层面对ＲＦＩＤ的研究工作进行阐述 与分析，着重介绍了ＲＦＩＤ的防冲突算法、认证与隐私保护协议以及真实环境下系统的性能评测与分析等方面的研 究成果及进展．最后展望了未来的研究方向． 关键词射频识别；数据管理；防冲突算法；认证与隐私保护；性能优化；物联网 中图法分类号ＴＰ３９３ 犇犗犐号１０．３７２４／ＳＰ．Ｊ．１０１６．２０１３．００４５７ 犚犉犐犇犇犪狋犪犕犪狀犪犵犲犿犲狀狋：犃犾犵狅狉犻狋犺犿狊，犘狉狅狋狅犮狅犾狊犪狀犱犘犲狉犳狅狉犿犪狀犮犲犈狏犪犾狌犪狋犻狅狀 ＸＩＥＬｅｉＹＩＮＹａＦｅｎｇＣＨＥＮＸｉＬＵＳａｎｇＬｕＣＨＥＮＤａｏＸｕ （犛狋犪狋犲犓犲狔犔犪犫狅狉犪狋狅狉狔犳狅狉犖狅狏犲犾犛狅犳狋狑犪狉犲犜犲犮犺狀狅犾狅犵狔，犖犪狀犼犻狀犵犝狀犻狏犲狉狊犻狋狔，犖犪狀犼犻狀犵２１００９３） 犃犫狊狋狉犪犮狋 ＷｉｔｈｔｈｅｄｅｖｅｌｏｐｍｅｎｔｏｆｃｒｉｔｉｃａｌｔｈｅｏｒｉｅｓａｎｄｔｅｃｈｎｏｌｏｇｉｅｓｉｎＩｎｔｅｒｎｅｔｏｆＴｈｉｎｇｓ （ＩＯＴ），ａｓａｋｅｙｓｕｐｐｏｒｔｉｎｇｔｅｃｈｎｏｌｏｇｙ，ＲＦＩＤｈａｓｂｅｃｏｍｅｏｎｅｏｆｔｈｅｈｏｔｓｐｏｔｓｉｎｔｈｅｆｉｅｌｄｏｆ ＩｎｔｅｒｎｅｔｏｆＴｈｉｎｇｓ．ＦｏｃｕｓｉｎｇｏｎＲＦＩＤｄａｔａｍａｎａｇｅｍｅｎｔ，ｔｈｉｓｐａｐｅｒｄｅｓｃｒｉｂｅｓａｎｄａｎａｌｙｚｅｓｔｈｅｒｅ ｓｅａｒｃｈｗｏｒｋｏｎｔｈｒｅｅａｓｐｅｃｔｓ：ａｌｇｏｒｉｔｈｍ，ｐｒｏｔｏｃｏｌａｎｄｐｅｒｆｏｒｍａｎｃｅｅｖａｌｕａｔｉｏｎ．Ｉｎｔｈｉｓｐａｐｅｒ，ｗｅ ｉｎｔｒｏｄｕｃｅｔｈｅｒｅｓｅａｒｃｈｐｒｏｇｒｅｓｓｉｎＲＦＩＤｗｉｔｈａｎｔｉｃｏｌｌｉｓｉｏｎａｌｇｏｒｉｔｈｍ，ａｕｔｈｅｎｔｉｃａｔｉｏｎａｎｄｐｒｉｖａｃｙ ｐｒｏｔｅｃｔｉｏｎｐｒｏｔｏｃｏｌｓ，ａｓｗｅｌｌａｓｐｅｒｆｏｒｍａｎｃｅｅｖａｌｕａｔｉｏｎｏｆＲＦＩＤｓｙｓｔｅｍｓｉｎｒｅａｌｉｓｔｉｃｓｅｔｔｉｎｇｓ．Ｆｉ ｎａｌｌｙ，ｗｅｏｕｔｌｏｏｋｔｈｅｆｕｔｕｒｅｒｅｓｅａｒｃｈｄｉｒｅｃｔｉｏｎｓａｎｄｃｏｎｃｌｕｄｅ． 犓犲狔狑狅狉犱狊ＲＦＩＤ；ｄａｔａｍａｎａｇｅｍｅｎｔ；ａｎｔｉｃｏｌｌｉｓｉｏｎａｌｇｏｒｉｔｈｍ；ａｕｔｈｅｎｔｉｃａｔｉｏｎａｎｄｐｒｉｖａｃｙｐｒｏｔｅｃ ｔｉｏｎ；ｐｅｒｆｏｒｍａｎｃｅｏｐｔｉｍｉｚａｔｉｏｎ；ＩｎｔｅｒｎｅｔｏｆＴｈｉｎｇｓ １引言 随着“物联网”时代的来临，新一代ＩＴ技术将 被充分运用在各行各业之中．射频识别（ＲＦＩＤ）作为 物联网应用的一项核心支撑技术，在学术界与工业 界已经得到广泛关注．目前，ＲＦＩＤ技术正在越来越 频繁地出现在大量的物联网应用中，包括物流管理、 电子支付、ＲＦＩＤ护照、安全访问控制、目标监测与 追踪等．随着ＲＦＩＤ的技术原理被进一步深入理解、 廉价的ＲＦＩＤ组件相继出现以及ＲＦＩＤ的安全得到 保障，ＲＦＩＤ技术将会在物联网应用中发挥越来越 重要的作用． 物联网的核心理念是在普适环境下实现“物物 相联”，即通过对物理世界信息化、网络化，将传统上 分离的物理世界与信息世界实现互联与整合．这就 需要将“智能”嵌入到每一个物理对象当中，并且提供 一种有效的、低成本的通信方式，ＲＦＩＤ技术的出现
458 计算 机 学报 2013年 正好满足了这一需求.RFD是一种非接触式的自 为数据管理提供基本的安全保障，能够有效地实现 动识别技术，它通过射频信号自动识别目标对象并 认证并且保护用户隐私，实现RFID数据管理的可 获取相关数据，识别工作无须人工干预.作为一种简 信性；对RFID系统进行性能评测与分析，其目的在 单的无线系统，RFID系统只有两个基本器件，一个 于验证在真实环境下物理层的关键因素对系统识别 是阅读器，另一个是标签.其基本工作原理是：阅读器 性能的影响，确保数据管理的可靠性.深入探究三者 以广播方式连续向周围发送携带能量的基准信号， 之间的联系，我们发现任一研究问题均对其余二者 感应到能量的标签通过调制电路信号以反射的方式 产生影响：防冲突算法能够提供最根本的数据传输 向阅读器返回自身携带的数据，阅读器对接收到的 支持，安全协议能够实现必要的安全保障，性能评测 数据进行解码，并传给主机进行处理.通过上述方 能够验证在真实环境下的系统运行性能，上述三方 式，RFID系统能够提供有效的身份信息(Identity) 面研究问题与RFD系统协议栈的对应关系如图1 和地址信息(Location).相比于其它智能系统， 所示，可以看到三者之间相互联系，又各有侧重 RFID系统具有如下鲜明特点：(1)能够实现非接触 RFID数据管理 式的快速自动识别；(2)标签内能够永久存储一定 可靠性 高效性 可信性 大小的数据；(3)标签内含一定数目的逻辑门能够 个 进行简单的逻辑处理；(4)标签具有普通无线设备 性能 防冲突九N 安全 的物理属性；(5)标签成本低廉，可以大量部署.因 评测 算法 协议 此，作为物联网感知识别层面的一项关键技术， RFID技术能够使得物联网中的每一个物体被唯一 物理层 媒体访问 控制层 应用层 地识别，并且能够携带规范而具有互用性的信息，在 RFID系统协议栈 无源的情况下有效实现“被动智能”，为“物-物相联” 提供根本保障 图1各研究问题之间的逻辑层次关系 在物联网环境下，RFID系统被部署和应用的 本文第2节主要介绍RFID的标签识别协议与 根本目的是：针对具体的应用需求，对被标识的物理 防冲突算法，着重阐述RFD标签识别机制、数目估 对象进行合理有效的信息收集，为上层应用提供最 算机制以及轮询机制方面的研究工作：第3节主要 基本的数据支持.因此，任何一种具体的RFD应用 介绍RFID的认证与隐私保护协议，对RFID的安 都依赖于对RFID数据实现有效的数据管理.所谓 全与隐私问题进行探讨与分析，并对RFID安全方 数据管理是指结合RFID系统的应用需求实现有效 面的三类主流技术进行总结：第4节对真实环境下 且有针对性的数据收集、分析挖掘以及数据安全保 RFID系统性能的评测与分析方面的研究工作进行 障等操作.在现有的物联网体系架构中，数据管理起 介绍：第5节对RFID数据管理相关的其它开放性 着承上启下的关键作用：一方面，物联网需要从感知 问题的研究进展进行总结；第6节展望RFID未来 到的海量原始数据中提取有效信息并进行管理，为 的研究方向；最后对全文进行总结 上层的特定应用提供数据支撑：另一方面，物联网需 要结合具体的数据管理需求来组织感知识别层面的 2 RFID标签识别协议与防冲突算法 众多节点，在网络层面进行优化调度与资源配置，以 更有效地指导下层协议与算法的设计实现. 2.1 RFD的标签识别协议 基于上述认识，本文关注RFID数据管理问题， 在通常的RFID应用中，大量的RFID标签往 以数据管理的核心技术为切入点，分别从RFD的 往被广泛地部署在指定区域中，为了能够快速有效 防冲突算法、RFD的认证与隐私保护协议以及真 地识别这些标签，阅读器需要在RFD标签识别协 实环境下RFD系统数据收集的性能评测与分析 议中使用一套有效的防冲突算法来逐一读取这些标 3个方面对RFID数据管理技术的研究与进展进行 签.在无线通信环境下，普通的无线设备主要基于载 分析与讨论.图1展示了上述3个方面研究问题之 波侦听多路访问/冲突避免(CSMA/CA)的竞争机 间的逻辑层次关系.其中，研究防冲突算法的目的是 制来实现多个设备之间的通信，如802.11协议.与 为MAC层提供一套快速的标签识别机制，实现 普通的无线节点不同，RFD标签是极为简单的无 RFID数据管理的高效性；研究安全协议的目的是 线设备，标签上的资源极其有限，不能够自发地通过
正好满足了这一需求．ＲＦＩＤ是一种非接触式的自 动识别技术，它通过射频信号自动识别目标对象并 获取相关数据，识别工作无须人工干预．作为一种简 单的无线系统，ＲＦＩＤ系统只有两个基本器件，一个 是阅读器，另一个是标签．其基本工作原理是：阅读器 以广播方式连续向周围发送携带能量的基准信号， 感应到能量的标签通过调制电路信号以反射的方式 向阅读器返回自身携带的数据，阅读器对接收到的 数据进行解码，并传给主机进行处理．通过上述方 式，ＲＦＩＤ系统能够提供有效的身份信息（Ｉｄｅｎｔｉｔｙ） 和地址信息（Ｌｏｃａｔｉｏｎ）．相比于其它智能系统， ＲＦＩＤ系统具有如下鲜明特点：（１）能够实现非接触 式的快速自动识别；（２）标签内能够永久存储一定 大小的数据；（３）标签内含一定数目的逻辑门能够 进行简单的逻辑处理；（４）标签具有普通无线设备 的物理属性；（５）标签成本低廉，可以大量部署．因 此，作为物联网感知识别层面的一项关键技术， ＲＦＩＤ技术能够使得物联网中的每一个物体被唯一 地识别，并且能够携带规范而具有互用性的信息，在 无源的情况下有效实现“被动智能”，为“物物相联” 提供根本保障． 在物联网环境下，ＲＦＩＤ系统被部署和应用的 根本目的是：针对具体的应用需求，对被标识的物理 对象进行合理有效的信息收集，为上层应用提供最 基本的数据支持．因此，任何一种具体的ＲＦＩＤ应用 都依赖于对ＲＦＩＤ数据实现有效的数据管理．所谓 数据管理是指结合ＲＦＩＤ系统的应用需求实现有效 且有针对性的数据收集、分析挖掘以及数据安全保 障等操作．在现有的物联网体系架构中，数据管理起 着承上启下的关键作用：一方面，物联网需要从感知 到的海量原始数据中提取有效信息并进行管理，为 上层的特定应用提供数据支撑；另一方面，物联网需 要结合具体的数据管理需求来组织感知识别层面的 众多节点，在网络层面进行优化调度与资源配置，以 更有效地指导下层协议与算法的设计实现． 基于上述认识，本文关注ＲＦＩＤ数据管理问题， 以数据管理的核心技术为切入点，分别从ＲＦＩＤ的 防冲突算法、ＲＦＩＤ的认证与隐私保护协议以及真 实环境下ＲＦＩＤ系统数据收集的性能评测与分析 ３个方面对ＲＦＩＤ数据管理技术的研究与进展进行 分析与讨论．图１展示了上述３个方面研究问题之 间的逻辑层次关系．其中，研究防冲突算法的目的是 为ＭＡＣ层提供一套快速的标签识别机制，实现 ＲＦＩＤ数据管理的高效性；研究安全协议的目的是 为数据管理提供基本的安全保障，能够有效地实现 认证并且保护用户隐私，实现ＲＦＩＤ数据管理的可 信性；对ＲＦＩＤ系统进行性能评测与分析，其目的在 于验证在真实环境下物理层的关键因素对系统识别 性能的影响，确保数据管理的可靠性．深入探究三者 之间的联系，我们发现任一研究问题均对其余二者 产生影响：防冲突算法能够提供最根本的数据传输 支持，安全协议能够实现必要的安全保障，性能评测 能够验证在真实环境下的系统运行性能．上述三方 面研究问题与ＲＦＩＤ系统协议栈的对应关系如图１ 所示，可以看到三者之间相互联系，又各有侧重． 图１各研究问题之间的逻辑层次关系 本文第２节主要介绍ＲＦＩＤ的标签识别协议与 防冲突算法，着重阐述ＲＦＩＤ标签识别机制、数目估 算机制以及轮询机制方面的研究工作；第３节主要 介绍ＲＦＩＤ的认证与隐私保护协议，对ＲＦＩＤ的安 全与隐私问题进行探讨与分析，并对ＲＦＩＤ安全方 面的三类主流技术进行总结；第４节对真实环境下 ＲＦＩＤ系统性能的评测与分析方面的研究工作进行 介绍；第５节对ＲＦＩＤ数据管理相关的其它开放性 问题的研究进展进行总结；第６节展望ＲＦＩＤ未来 的研究方向；最后对全文进行总结． ２犚犉犐犇标签识别协议与防冲突算法 ２．１犚犉犐犇的标签识别协议 在通常的ＲＦＩＤ应用中，大量的ＲＦＩＤ标签往 往被广泛地部署在指定区域中．为了能够快速有效 地识别这些标签，阅读器需要在ＲＦＩＤ标签识别协 议中使用一套有效的防冲突算法来逐一读取这些标 签．在无线通信环境下，普通的无线设备主要基于载 波侦听多路访问／冲突避免（ＣＳＭＡ／ＣＡ）的竞争机 制来实现多个设备之间的通信，如８０２．１１协议．与 普通的无线节点不同，ＲＦＩＤ标签是极为简单的无 线设备，标签上的资源极其有限，不能够自发地通过 ４５８ 计 算 机 学 报 ２０１３年
3期 谢磊等：RFID数据管理：算法、协议与性能评测 459 调节自身的无线传输机会来避免标签间的传输冲 表1两类防冲突算法的优缺点比较 突，具体来说，标签没有足够的处理能力与能源来实 基于二进制树防冲突算法基于ALOHA防冲突算法 现上述竞争机制，避免通信冲突.鉴于RFID的系统 使用随机算法，算法实现逻辑简 通常使用确定性的算法， 特点，RFID标签识别协议需要具备如下性质： 算法实现逻辑简单，基于 单，平均情况下，标签识别性能良 优点 查询树结构的算法不需 好：随机算法使得各时隙的结果 (1)简单.由于RFID标签上的计算、存储资源极其 要存储中间状态变量 在统计意义上符合一定的概率分 布，有助于进行各种统计性分析 有限，标签识别协议的处理逻辑（包括执行流程和状 算法的随机性导致存在“饿死”问 态迁移关系)需要尽可能简单；(2)高效.面对大量 对基于查询树结构的算 法，标签识别的时延受扫 题，某些标签可能永远选择不到 的RFID标签，标签识别协议需要提供轻量级的通 缺点 描范围内标签ID的分 单时隙进行传输：最坏情况下，标 布以及ID的长度影响 签识别的时延趋向于十∞，其性 信机制，尽可能避免不必要的控制报文的传输，确保 能无法保障 传输的高吞吐率与低延迟性. 隙，导致时隙的浪费：如果帧长过小，则该帧大部分 目前的RFID防冲突算法主要分为两大类：基 时隙会出现标签传输冲突，导致大部分标签需要在 于二进制树的防冲突算法[1-]和基于ALOHA的防 下一帧重传.因此，研究者们对该问题进行了深入研 冲突算法[3].前者利用二叉搜索树，按照递归的方 究.文献[5]分析了在时隙ALOHA协议中采用动 式将冲突的标签集合划分为两个标签子集，对于可 态帧长的方法对读取性能的影响.文献[6]基于贝叶 能产生冲突的相关标签集合，采用沉默的方式来解 斯的概率模型提出了优化动态帧长的决策机制.文 决冲突问题.划分子集的方法包括随机二进制树算 献[7]利用马尔可夫过程来对读取过程进行建模，并 法和查询二进制树算法.文献[1]提出了一套自适应 且由此计算出读取过程中应该使用的一系列优化的 的基于树形结构的防冲突算法来实现有效的标签识 帧长.文献[8]进一步针对最大化信道使用效率的目 别.文献[2]提出了一套基于查询树结构的智能遍历 标推导出优化的动态帧长，该文指出，如果每一轮中 机制，能够以低延迟的方式实现标签的识别. 帧长与当前未读取的标签数相同，则整个信道能够 ALOHA协议最早被用在分组无线网络中实现随机 达到最大的使用效率.其原理阐述如下：假设当前标 访问机制.在RFID系统中，为了提高标签识别的效 签数目为，帧长为f;由于标签对时隙的选择符合 率，文献[3-4]提出了时隙ALOHA协议来有效解 二项分布，则根据二项分布，当前帧中单时隙的期望 决冲突，实现标签的高效识别.时隙ALOHA协议 数目为E[m1]=n×(1一1/f)-1:为了最大化信道 将若干个时隙组织为一帧，在每一帧开始时，阅读器 的使用效率，即单时隙数目在当前帧中的比例 广播帧的长度f,即当前帧所包含的时隙个数，并通 1/f,我们采用求极值的方法计算f的取值，即 过发送连续的电磁波来激活扫描范围内所有标签. 每个标签在接收到帧长f之后随机独立地在第1一 正[]近=0→f'=m,得到此时信道的使用效率 af f个时隙中选择一个时隙发送标识符.如果成功，即 为/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-C1G2标准下使用 100%.当n逐渐增大时，其最优效率快速收敛到 的通信协议，在表1中，我们分别从优缺点两个方面 1/e.这就意味着，当n>5时，每一轮帧长f取值为 对上述两种防冲突算法进行了比较，总体而言，两者 当前待读的标签数n时，使用效率趋向于1/e,可以 在性能与功能实现方面各有利弊。 达到当前每一轮的局部最优效率.如果在识别过程 对于时隙ALOHA协议而言，每一轮所采用的 中每一轮都使用该策略，则整体效率可接近1/e.由 帧长对总体的识别性能至关重要.对于给定的待读 于1/e是整体效率的上限值，因此当前整体效率接 标签集合，如果帧长过大，则该帧大部分时隙为空时 近全局最优
调节自身的无线传输机会来避免标签间的传输冲 突．具体来说，标签没有足够的处理能力与能源来实 现上述竞争机制，避免通信冲突．鉴于ＲＦＩＤ的系统 特点，ＲＦＩＤ标签识别协议需要具备如下性质： （１）简单．由于ＲＦＩＤ标签上的计算、存储资源极其 有限，标签识别协议的处理逻辑（包括执行流程和状 态迁移关系）需要尽可能简单；（２）高效．面对大量 的ＲＦＩＤ标签，标签识别协议需要提供轻量级的通 信机制，尽可能避免不必要的控制报文的传输，确保 传输的高吞吐率与低延迟性． 目前的ＲＦＩＤ防冲突算法主要分为两大类：基 于二进制树的防冲突算法［１２］和基于ＡＬＯＨＡ的防 冲突算法［３８］．前者利用二叉搜索树，按照递归的方 式将冲突的标签集合划分为两个标签子集，对于可 能产生冲突的相关标签集合，采用沉默的方式来解 决冲突问题．划分子集的方法包括随机二进制树算 法和查询二进制树算法．文献［１］提出了一套自适应 的基于树形结构的防冲突算法来实现有效的标签识 别．文献［２］提出了一套基于查询树结构的智能遍历 机制，能够以低延迟的方式实现标签的识别． ＡＬＯＨＡ协议最早被用在分组无线网络中实现随机 访问机制．在ＲＦＩＤ系统中，为了提高标签识别的效 率，文献［３４］提出了时隙ＡＬＯＨＡ协议来有效解 决冲突，实现标签的高效识别．时隙ＡＬＯＨＡ协议 将若干个时隙组织为一帧，在每一帧开始时，阅读器 广播帧的长度犳，即当前帧所包含的时隙个数，并通 过发送连续的电磁波来激活扫描范围内所有标签． 每个标签在接收到帧长犳之后随机独立地在第１～ 犳个时隙中选择一个时隙发送标识符．如果成功，即 无冲突发生，该标签进入静默状态；如果有冲突发 生，则该标签将继续等待在下一帧中再选择一个时 隙重新发送标识符．因此，每一帧的时隙会存在如下 ３种情况之一：（１）空时隙（ＥｍｐｔｙＳｌｏｔ）．没有任何 一个标签选中该时隙；（２）单时隙（ＳｉｎｇｌｅｔｏｎＳｌｏｔ）． 仅有唯一一个标签选中该时隙；（３）冲突时隙 （ＣｏｌｌｉｓｉｏｎＳｌｏｔ）．多个标签选中该时隙．上述每种时 隙所包含的信息量各不相同．目前，时隙ＡＬＯＨＡ 协议已经成为ＲＦＩＤ系统在ＥＰＣＣ１Ｇ２标准下使用 的通信协议．在表１中，我们分别从优缺点两个方面 对上述两种防冲突算法进行了比较，总体而言，两者 在性能与功能实现方面各有利弊． 对于时隙ＡＬＯＨＡ协议而言，每一轮所采用的 帧长对总体的识别性能至关重要．对于给定的待读 标签集合，如果帧长过大，则该帧大部分时隙为空时 表１两类防冲突算法的优缺点比较 基于二进制树防冲突算法 基于ＡＬＯＨＡ防冲突算法 优点 通常使用确定性的算法， 算法实现逻辑简单；基于 查询树结构的算法不需 要存储中间状态变量 使用随机算法，算法实现逻辑简 单；平均情况下，标签识别性能良 好；随机算法使得各时隙的结果 在统计意义上符合一定的概率分 布，有助于进行各种统计性分析 缺点 对基于查询树结构的算 法，标签识别的时延受扫 描范围内标签犐犇的分 布以及犐犇的长度影响 算法的随机性导致存在“饿死”问 题，某些标签可能永远选择不到 单时隙进行传输；最坏情况下，标 签识别的时延趋向于＋∞，其性 能无法保障 隙，导致时隙的浪费；如果帧长过小，则该帧大部分 时隙会出现标签传输冲突，导致大部分标签需要在 下一帧重传．因此，研究者们对该问题进行了深入研 究．文献［５］分析了在时隙ＡＬＯＨＡ协议中采用动 态帧长的方法对读取性能的影响．文献［６］基于贝叶 斯的概率模型提出了优化动态帧长的决策机制．文 献［７］利用马尔可夫过程来对读取过程进行建模，并 且由此计算出读取过程中应该使用的一系列优化的 帧长．文献［８］进一步针对最大化信道使用效率的目 标推导出优化的动态帧长，该文指出，如果每一轮中 帧长与当前未读取的标签数相同，则整个信道能够 达到最大的使用效率．其原理阐述如下：假设当前标 签数目为狀，帧长为犳；由于标签对时隙的选择符合 二项分布，则根据二项分布，当前帧中单时隙的期望 数目为犈［狀１］＝狀×（１－１／犳）狀－１；为了最大化信道 的使用效率，即单时隙数目在当前帧中的比例 狀１／犳，我们采用求极值的方法计算犳的取值，即 !犈［狀１］／犳 !犳 ＝０→犳＝狀，得到此时信道的使用效率 为狀１／犳→１／ｅ．对于上述性质，我们在图２和图３ 中给出更为形象的描述．图２展示了给定标签数目 狀＝１００，帧长犳变化对信道使用效率的影响．可以 看到当帧长犳由小及大变化时，信道的使用效率逐 渐增大后又逐渐减小，在犳＝１００时取到最大值１／ｅ． 图３展示了随着标签数目狀变化，使用最优帧长 犳＝狀对信道使用效率的影响．可以看到当狀取值 较小时，所达到的最优效率大于１／ｅ，例如，当仅有 一个标签时（狀＝１），帧长为１可以达到最优效率 １００％．当狀逐渐增大时，其最优效率快速收敛到 １／ｅ．这就意味着，当狀＞５时，每一轮帧长犳取值为 当前待读的标签数狀时，使用效率趋向于１／ｅ，可以 达到当前每一轮的局部最优效率．如果在识别过程 中每一轮都使用该策略，则整体效率可接近１／ｅ．由 于１／ｅ是整体效率的上限值，因此当前整体效率接 近全局最优． ３期 谢磊等：ＲＦＩＤ数据管理：算法、协议与性能评测 ４５９
460 计 算 机 学报 2013年 0.4 出了一套RFID标签读取性能的概率模型，基于时 隙ALOHA协议设计出优化的标签识别参数，相比 03 传统的识别机制更为有效地提升了识别的性能， 2.2RFD的标签数量估算机制 0.2 随着RFD应用的进一步拓展，某些应用仅需 要获取一些统计性信息来为上层的数据分析以及挖 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 帧长∫ 的标签数量估算机制，以一种实用的方式实现了 图3随着标签数目n变化，使用最优幀长∫=n RFID标签的快速统计.其主要思想为：假设在某一 对应的信道使用效率 轮中帧的长度为∫，空时隙的数目会随着实际参与 的标签数n增加而减少，冲突时隙的数目会随着标 上述提到的协议与防冲突算法多数是在较为理 签数n增加而增加，而单时隙的数目会随着标签数 想的部署环境下得出，并未充分考虑实际应用环境 n增加先增加再减少，因此，空时隙（冲突时隙）的 下所遇到的种种难题，例如，标签的频繁移动、多个 数目与标签数存在明确的单调减（增）关系.该文作 RFID阅读器之间的信号干扰、RFID标签传输的信 者基于二项分布的概率模型给出了空时隙与冲突时 号衰减以及多径效应等.因此，一些研究工作开始关 隙的数值期望计算公式，提出了空时隙与冲突时隙 注并尝试解决上述问题.鉴于之前的研究工作大多 相结合的估算算法，并通过重复采样的手段有效降 关注于解决标签之间的传输冲突问题，并未考虑到 低了估算的误差.研究者们通过进一步研究发现，尽 多个阅读器之间以及标签与阅读器之间的信号干 管单时隙数目与标签数目不存在单调关系，无法利 扰，文献[9-10]在多个RFD阅读器环境下提出了 用单时隙数目推算出确切的标签数目，但是3种时 优化的阅读器激活与调度机制，使得多个阅读器能 隙的数目结合起来能够指导系统更精确地估算标签 够协作地识别标签，有效避免信号的传输冲突，考虑 数目.文献[14]根据观察到的3种时隙的数目提出 到单个RFD阅读器的有效读取范围相对有限，文 了一套后验概率模型，基于最大化后验概率的决策 献[11]利用“时空关联”关系提出了性能高效的连续 来更精确地实现标签数量估算机制，上述机制均需 扫描机制，来实现对大规模部署标签的快速识别.之 要对3种时隙进行大量采样来提高估算的精确度， 前大部分的研究工作主要考虑在相对理想状态下针 事实上，完全可以借助其它参量来更快速有效地估 对静态环境设计优化的标签识别机制，并未考虑移 算标签数目.我们在文献[15]中提出了一种基于 动环境以及传输环境中普遍存在的信号衰减对标签 Ball-and-Bin概率模型的快速估算方法.其核心思想 识别性能带来的影响，有鉴于此，我们针对上述问题 在于：每个标签会随机选择位置回复，系统可以通过 开展了相应的研究工作，文献[12]针对移动环境下 观察第一个标签回复的位置来估算最有可能造成该 持续变化的信号衰减情形，基于跨层优化的思路提 事件发生的标签数量.该文从理论上建立了概率模
图２给定标签数目狀＝１００，信道使用效率与帧长犳的关系 图３随着标签数目狀变化，使用最优帧长犳＝狀 对应的信道使用效率 上述提到的协议与防冲突算法多数是在较为理 想的部署环境下得出，并未充分考虑实际应用环境 下所遇到的种种难题，例如，标签的频繁移动、多个 ＲＦＩＤ阅读器之间的信号干扰、ＲＦＩＤ标签传输的信 号衰减以及多径效应等．因此，一些研究工作开始关 注并尝试解决上述问题．鉴于之前的研究工作大多 关注于解决标签之间的传输冲突问题，并未考虑到 多个阅读器之间以及标签与阅读器之间的信号干 扰，文献［９１０］在多个ＲＦＩＤ阅读器环境下提出了 优化的阅读器激活与调度机制，使得多个阅读器能 够协作地识别标签，有效避免信号的传输冲突．考虑 到单个ＲＦＩＤ阅读器的有效读取范围相对有限，文 献［１１］利用“时空关联”关系提出了性能高效的连续 扫描机制，来实现对大规模部署标签的快速识别．之 前大部分的研究工作主要考虑在相对理想状态下针 对静态环境设计优化的标签识别机制，并未考虑移 动环境以及传输环境中普遍存在的信号衰减对标签 识别性能带来的影响．有鉴于此，我们针对上述问题 开展了相应的研究工作，文献［１２］针对移动环境下 持续变化的信号衰减情形，基于跨层优化的思路提 出了一套ＲＦＩＤ标签读取性能的概率模型，基于时 隙ＡＬＯＨＡ协议设计出优化的标签识别参数，相比 传统的识别机制更为有效地提升了识别的性能． ２．２犚犉犐犇的标签数量估算机制 随着ＲＦＩＤ应用的进一步拓展，某些应用仅需 要获取一些统计性信息来为上层的数据分析以及挖 掘提供数据基础．在这种情况下，ＲＦＩＤ系统不需要 逐个识别标签，仅仅需要快速获取扫描范围内标签 的统计信息，其中一个关键的信息就是标签数量．此 外，基于动态帧长的时隙ＡＬＯＨＡ协议也需要估算 标签的大体数量来决定动态帧的长度．因此，近年来 出现了很多关注于如何快速、精确地估算标签数目 的研究工作，其核心思想主要是使用基于随机算法 的时隙ＡＬＯＨＡ协议来实现估算．研究者们意识 到，尽管时隙ＡＬＯＨＡ协议是以随机的方式让标签 选择时隙进行数据传输，然而从统计意义上来看，整 个空时隙、单时隙以及冲突时隙的分布事实上是符 合二项分布的．当对时隙的采样次数足够多时，完全 可以基于二项分布规律来估算出实际参与标签的数 量．基于上述思路，文献［１３］提出了一套快速而可靠 的标签数量估算机制，以一种实用的方式实现了 ＲＦＩＤ标签的快速统计．其主要思想为：假设在某一 轮中帧的长度为犳，空时隙的数目会随着实际参与 的标签数狀增加而减少，冲突时隙的数目会随着标 签数狀增加而增加，而单时隙的数目会随着标签数 狀增加先增加再减少，因此，空时隙（冲突时隙）的 数目与标签数存在明确的单调减（增）关系．该文作 者基于二项分布的概率模型给出了空时隙与冲突时 隙的数值期望计算公式，提出了空时隙与冲突时隙 相结合的估算算法，并通过重复采样的手段有效降 低了估算的误差．研究者们通过进一步研究发现，尽 管单时隙数目与标签数目不存在单调关系，无法利 用单时隙数目推算出确切的标签数目，但是３种时 隙的数目结合起来能够指导系统更精确地估算标签 数目．文献［１４］根据观察到的３种时隙的数目提出 了一套后验概率模型，基于最大化后验概率的决策 来更精确地实现标签数量估算机制．上述机制均需 要对３种时隙进行大量采样来提高估算的精确度， 事实上，完全可以借助其它参量来更快速有效地估 算标签数目．我们在文献［１５］中提出了一种基于 ＢａｌｌａｎｄＢｉｎ概率模型的快速估算方法．其核心思想 在于：每个标签会随机选择位置回复，系统可以通过 观察第一个标签回复的位置来估算最有可能造成该 事件发生的标签数量．该文从理论上建立了概率模 ４６０ 计 算 机 学 报 ２０１３年
3期 谢磊等：RFID数据管理：算法、协议与性能评测 461 型，并证明了其正确性和性能的上界.实验表明，在 标签的标识符ID,每传输一个ID后，阅读器会等 给定精度要求的情况下，该方法明显快于现有其它 待对应的标签返回一个短暂的响应消息.如果接收 方法.此外，为了解决单个标签被多次读取的问题， 到响应，则推断该标签存在于扫描范围内，否则认为 文献[16]提出了一套“复制不敏感”的估算机制来实 该标签丢失.然而，上述方案存在如下弊病：(1)与 现更精确的标签数量统计.文献[17]提出了一个自 时隙ALOHA协议不太兼容：(2)长达96bit的ID 适应的基于划分的估算机制，该机制基于几何分布 传输使得整体扫描时间过长，降低了系统的效率.因 规律让单个标签选择同一帧中的多个时隙进行传 此，研究者们针对上述问题开展了深入的研究，其目 输，使得每个标签有1/2的概率选择第1一1个时 标为基于时隙ALOHA协议设计出一套有效的标 隙，有效解决了单个标签被多次读取的问题.表2对 签轮询机制，尽可能地减少整体扫描时间， 上述研究工作的特点进行了总结和比较 研究发现，在时隙ALOHA协议的每一轮中， 处于激活状态的标签会“随机”地在帧中选择一个时 表2标签数量估算算法的特点总结与比较 隙进行传输.然而，由于标签的简易性，真正的随机 估算算法 与时隙ALOHA 估算参考的指标 概率模型 协议兼容性 性很难得到实现.事实上，标签的芯片逻辑实现了一 文献[13] 兼容 空时隙与冲突时 二项分布 个“伪随机”的操作：在每一轮中阅读器广播一个随 隙的数目 机数r,每个被激活的标签接收到r后随即结合本 文献[14] 兼容 3种时隙的数目 基于二项分布的 后验概率模型 地的标识符D进行散列操作，计算出伪随机数s作 文献[15] 兼容 第一个标签回复 的位置 二项分布 为选定的时隙序号，这里s=hash(ID,r)modf,f 文献[16-17] 不兼容 冲突时隙出现的 几何分布 是帧的长度，上述的“伪随机性”意味着，对于任一标 边缘位置 签，一旦阅读器广播的数值r以及帧的长度f确定 除了对标签数量进行简单估算之外，一些研究 下来，该标签在帧中相应的位置即被确定，这就使得 工作者开始探究如何在RFID系统上实现更为复杂 对标签的有效轮询成为可能.在实施扫描之前，阅读 的数据分析与挖掘机制.文献[18]着力研究面对大 器可以预先根据指定集合内各标签在帧中对应的位 量的RFID标签，如何在不需要读取所有标签具体 置为每个时隙计算出期望的结果：空时隙(0)、单时 信息的前提下快速定位出最热门的标签类别.该文 隙(1)或者冲突时隙(C).对于某一时隙，如果该时 基于分组测试(Group Testing)的理念，提出了有效 隙期望为单时隙但实际无响应，则表明对应于该时 的随机算法来解决上述问题.文献[19]面向流量追 隙的标签丢失；如果该时隙期望为冲突时隙但实际 踪一类的应用问题，针对动态移动的标签集合提出 无响应，则表明对应于该时隙的所有标签丢失.图4 了保障隐私的快速估算机制.该机制能够快速统计 给出了基于时隙ALOHA协议的轮询机制示意图， 在时域(t1,t2)内从地点A移动到地点B的标签数 如图所示，在标签A~H中，虚线标识丢失的标签， 目，从而在无需读取确切标签ID信息的前提下有 实线标识存在的标签.当标签E、F以及H丢失时， 效地进行流量追踪.总体而言，目前该方面的研究成 其对应的时隙实际观察到的状态变成空时隙(0)，此 果相对较少，随着RFD数据管理技术以及相关应 时可以判定标签丢失.但对于标签C丢失的情况， 用的进一步拓展，基于RFID的数据分析与挖掘机 由于标签B、D的存在，使得对应时隙实际观察到的 制必将得到更为广泛的关注与深入的研究 状态仍为冲突时隙(C),未能判断出标签C丢失的 2.3RFD的标签轮询机制 情况，导致假阳性误判(False Positive).上述轮询机 某些RFD应用并不需要获取全部RFID标签 -=-=- 标签A标签B标签C标签D 标签E标签F标签G标签H! 的标识信息，仅需要对指定集合内的标签进行轮询， 来确认标签的状态是存在或丢失.例如，对仓库管理 应用而言，出入库之前管理员需要根据货物清单来 期望的 状态 清点指定的货物，确定是否存在货物丢失.在这种情 况下，假设所有的货物都贴有唯一标识的RFD标 实际观察 的状态 o 0 1 o c oo 01000 签，能否有效地实现标签的轮询机制成为与此密切 轮询判断 末能判断出标 标签E, 相关的问题.最简单直接的方案便是设计一种类似 的结果 签C丢失，假 阳性误判 标签F丢失标签H丢失 于“点名”的机制：阅读器根据清单内容接连地广播 图4基于时隙ALOHA协议的轮询机制示意图
型，并证明了其正确性和性能的上界．实验表明，在 给定精度要求的情况下，该方法明显快于现有其它 方法．此外，为了解决单个标签被多次读取的问题， 文献［１６］提出了一套“复制不敏感”的估算机制来实 现更精确的标签数量统计．文献［１７］提出了一个自 适应的基于划分的估算机制，该机制基于几何分布 规律让单个标签选择同一帧中的多个时隙进行传 输，使得每个标签有１／２狋的概率选择第狋－１个时 隙，有效解决了单个标签被多次读取的问题．表２对 上述研究工作的特点进行了总结和比较． 表２标签数量估算算法的特点总结与比较 估算算法与时隙ＡＬＯＨＡ 协议兼容性 估算参考的指标 概率模型 文献［１３］ 兼容 空时隙与冲突时 隙的数目 二项分布 文献［１４］ 兼容 ３种时隙的数目 基于二项分布的 后验概率模型 文献［１５］ 兼容 第一个标签回复 的位置 二项分布 文献［１６１７］ 不兼容 冲突时隙出现的 边缘位置 几何分布 除了对标签数量进行简单估算之外，一些研究 工作者开始探究如何在ＲＦＩＤ系统上实现更为复杂 的数据分析与挖掘机制．文献［１８］着力研究面对大 量的ＲＦＩＤ标签，如何在不需要读取所有标签具体 信息的前提下快速定位出最热门的标签类别．该文 基于分组测试（ＧｒｏｕｐＴｅｓｔｉｎｇ）的理念，提出了有效 的随机算法来解决上述问题．文献［１９］面向流量追 踪一类的应用问题，针对动态移动的标签集合提出 了保障隐私的快速估算机制．该机制能够快速统计 在时域（狋１，狋２）内从地点Ａ移动到地点Ｂ的标签数 目，从而在无需读取确切标签犐犇信息的前提下有 效地进行流量追踪．总体而言，目前该方面的研究成 果相对较少，随着ＲＦＩＤ数据管理技术以及相关应 用的进一步拓展，基于ＲＦＩＤ的数据分析与挖掘机 制必将得到更为广泛的关注与深入的研究． ２．３犚犉犐犇的标签轮询机制 某些ＲＦＩＤ应用并不需要获取全部ＲＦＩＤ标签 的标识信息，仅需要对指定集合内的标签进行轮询， 来确认标签的状态是存在或丢失．例如，对仓库管理 应用而言，出入库之前管理员需要根据货物清单来 清点指定的货物，确定是否存在货物丢失．在这种情 况下，假设所有的货物都贴有唯一标识的ＲＦＩＤ标 签，能否有效地实现标签的轮询机制成为与此密切 相关的问题．最简单直接的方案便是设计一种类似 于“点名”的机制：阅读器根据清单内容接连地广播 标签的标识符犐犇，每传输一个犐犇后，阅读器会等 待对应的标签返回一个短暂的响应消息．如果接收 到响应，则推断该标签存在于扫描范围内，否则认为 该标签丢失．然而，上述方案存在如下弊病：（１）与 时隙ＡＬＯＨＡ协议不太兼容；（２）长达９６ｂｉｔ的犐犇 传输使得整体扫描时间过长，降低了系统的效率．因 此，研究者们针对上述问题开展了深入的研究，其目 标为基于时隙ＡＬＯＨＡ协议设计出一套有效的标 签轮询机制，尽可能地减少整体扫描时间． 图４基于时隙ＡＬＯＨＡ协议的轮询机制示意图 研究发现，在时隙ＡＬＯＨＡ协议的每一轮中， 处于激活状态的标签会“随机”地在帧中选择一个时 隙进行传输．然而，由于标签的简易性，真正的随机 性很难得到实现．事实上，标签的芯片逻辑实现了一 个“伪随机”的操作：在每一轮中阅读器广播一个随 机数狉，每个被激活的标签接收到狉后随即结合本 地的标识符犐犇进行散列操作，计算出伪随机数狊作 为选定的时隙序号，这里狊＝ｈａｓｈ（犐犇，狉）ｍｏｄ犳，犳 是帧的长度．上述的“伪随机性”意味着，对于任一标 签，一旦阅读器广播的数值狉以及帧的长度犳确定 下来，该标签在帧中相应的位置即被确定，这就使得 对标签的有效轮询成为可能．在实施扫描之前，阅读 器可以预先根据指定集合内各标签在帧中对应的位 置为每个时隙计算出期望的结果：空时隙（０）、单时 隙（１）或者冲突时隙（犆）．对于某一时隙，如果该时 隙期望为单时隙但实际无响应，则表明对应于该时 隙的标签丢失；如果该时隙期望为冲突时隙但实际 无响应，则表明对应于该时隙的所有标签丢失．图４ 给出了基于时隙ＡＬＯＨＡ协议的轮询机制示意图． 如图所示，在标签Ａ～Ｈ中，虚线标识丢失的标签， 实线标识存在的标签．当标签Ｅ、Ｆ以及Ｈ丢失时， 其对应的时隙实际观察到的状态变成空时隙（０），此 时可以判定标签丢失．但对于标签Ｃ丢失的情况， 由于标签Ｂ、Ｄ的存在，使得对应时隙实际观察到的 状态仍为冲突时隙（犆），未能判断出标签Ｃ丢失的 情况，导致假阳性误判（ＦａｌｓｅＰｏｓｉｔｉｖｅ）．上述轮询机 ３期 谢磊等：ＲＦＩＤ数据管理：算法、协议与性能评测 ４６１