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