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协议的轮询机制示意图型，并证明了其正确性和性能的上界．实验表明，在 给定精度要求的情况下，该方法明显快于现有其它 方法．此外，为了解决单个标签被多次读取的问题， 文献［１６］提出了一套“复制不敏感”的估算机制来实 现更精确的标签数量统计．文献［１７］提出了一个自 适应的基于划分的估算机制，该机制基于几何分布 规律让单个标签选择同一帧中的多个时隙进行传 输，使得每个标签有１／２狋的概率选择第狋－１个时 隙，有效解决了单个标签被多次读取的问题．表２对 上述研究工作的特点进行了总结和比较． 表２标签数量估算算法的特点总结与比较 估算算法与时隙ＡＬＯＨＡ 协议兼容性 估算参考的指标 概率模型 文献［１３］ 兼容 空时隙与冲突时 隙的数目 二项分布 文献［１４］ 兼容 ３种时隙的数目 基于二项分布的 后验概率模型 文献［１５］ 兼容 第一个标签回复 的位置 二项分布 文献［１６１７］ 不兼容 冲突时隙出现的 边缘位置 几何分布 除了对标签数量进行简单估算之外，一些研究 工作者开始探究如何在ＲＦＩＤ系统上实现更为复杂 的数据分析与挖掘机制．文献［１８］着力研究面对大 量的ＲＦＩＤ标签，如何在不需要读取所有标签具体 信息的前提下快速定位出最热门的标签类别．该文 基于分组测试（ＧｒｏｕｐＴｅｓｔｉｎｇ）的理念，提出了有效 的随机算法来解决上述问题．文献［１９］面向流量追 踪一类的应用问题，针对动态移动的标签集合提出 了保障隐私的快速估算机制．该机制能够快速统计 在时域（狋１，狋２）内从地点Ａ移动到地点Ｂ的标签数 目，从而在无需读取确切标签犐犇信息的前提下有 效地进行流量追踪．总体而言，目前该方面的研究成 果相对较少，随着ＲＦＩＤ数据管理技术以及相关应 用的进一步拓展，基于ＲＦＩＤ的数据分析与挖掘机 制必将得到更为广泛的关注与深入的研究． ２．３犚犉犐犇的标签轮询机制 某些ＲＦＩＤ应用并不需要获取全部ＲＦＩＤ标签 的标识信息，仅需要对指定集合内的标签进行轮询， 来确认标签的状态是存在或丢失．例如，对仓库管理 应用而言，出入库之前管理员需要根据货物清单来 清点指定的货物，确定是否存在货物丢失．在这种情 况下，假设所有的货物都贴有唯一标识的ＲＦＩＤ标 签，能否有效地实现标签的轮询机制成为与此密切 相关的问题．最简单直接的方案便是设计一种类似 于“点名”的机制：阅读器根据清单内容接连地广播 标签的标识符犐犇，每传输一个犐犇后，阅读器会等 待对应的标签返回一个短暂的响应消息．如果接收 到响应，则推断该标签存在于扫描范围内，否则认为 该标签丢失．然而，上述方案存在如下弊病：（１）与 时隙ＡＬＯＨＡ协议不太兼容；（２）长达９６ｂｉｔ的犐犇 传输使得整体扫描时间过长，降低了系统的效率．因 此，研究者们针对上述问题开展了深入的研究，其目 标为基于时隙ＡＬＯＨＡ协议设计出一套有效的标 签轮询机制，尽可能地减少整体扫描时间． 图４基于时隙ＡＬＯＨＡ协议的轮询机制示意图 研究发现，在时隙ＡＬＯＨＡ协议的每一轮中， 处于激活状态的标签会“随机”地在帧中选择一个时 隙进行传输．然而，由于标签的简易性，真正的随机 性很难得到实现．事实上，标签的芯片逻辑实现了一 个“伪随机”的操作：在每一轮中阅读器广播一个随 机数狉，每个被激活的标签接收到狉后随即结合本 地的标识符犐犇进行散列操作，计算出伪随机数狊作 为选定的时隙序号，这里狊＝ｈａｓｈ（犐犇，狉）ｍｏｄ犳，犳 是帧的长度．上述的“伪随机性”意味着，对于任一标 签，一旦阅读器广播的数值狉以及帧的长度犳确定 下来，该标签在帧中相应的位置即被确定，这就使得 对标签的有效轮询成为可能．在实施扫描之前，阅读 器可以预先根据指定集合内各标签在帧中对应的位 置为每个时隙计算出期望的结果：空时隙（０）、单时 隙（１）或者冲突时隙（犆）．对于某一时隙，如果该时 隙期望为单时隙但实际无响应，则表明对应于该时 隙的标签丢失；如果该时隙期望为冲突时隙但实际 无响应，则表明对应于该时隙的所有标签丢失．图４ 给出了基于时隙ＡＬＯＨＡ协议的轮询机制示意图． 如图所示，在标签Ａ～Ｈ中，虚线标识丢失的标签， 实线标识存在的标签．当标签Ｅ、Ｆ以及Ｈ丢失时， 其对应的时隙实际观察到的状态变成空时隙（０），此 时可以判定标签丢失．但对于标签Ｃ丢失的情况， 由于标签Ｂ、Ｄ的存在，使得对应时隙实际观察到的 状态仍为冲突时隙（犆），未能判断出标签Ｃ丢失的 情况，导致假阳性误判（ＦａｌｓｅＰｏｓｉｔｉｖｅ）．上述轮询机 ３期 谢磊等：ＲＦＩＤ数据管理：算法、协议与性能评测 ４６１