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是整体效率的上限值，因此当前整体效率接 标签集合，如果帧长过大，则该帧大部分时隙为空时 近全局最优，调节自身的无线传输机会来避免标签间的传输冲 突．具体来说，标签没有足够的处理能力与能源来实 现上述竞争机制，避免通信冲突．鉴于ＲＦＩＤ的系统 特点，ＲＦＩＤ标签识别协议需要具备如下性质： （１）简单．由于ＲＦＩＤ标签上的计算、存储资源极其 有限，标签识别协议的处理逻辑（包括执行流程和状 态迁移关系）需要尽可能简单；（２）高效．面对大量 的ＲＦＩＤ标签，标签识别协议需要提供轻量级的通 信机制，尽可能避免不必要的控制报文的传输，确保 传输的高吞吐率与低延迟性． 目前的ＲＦＩＤ防冲突算法主要分为两大类：基 于二进制树的防冲突算法［１２］和基于ＡＬＯＨＡ的防 冲突算法［３８］．前者利用二叉搜索树，按照递归的方 式将冲突的标签集合划分为两个标签子集，对于可 能产生冲突的相关标签集合，采用沉默的方式来解 决冲突问题．划分子集的方法包括随机二进制树算 法和查询二进制树算法．文献［１］提出了一套自适应 的基于树形结构的防冲突算法来实现有效的标签识 别．文献［２］提出了一套基于查询树结构的智能遍历 机制，能够以低延迟的方式实现标签的识别． ＡＬＯＨＡ协议最早被用在分组无线网络中实现随机 访问机制．在ＲＦＩＤ系统中，为了提高标签识别的效 率，文献［３４］提出了时隙ＡＬＯＨＡ协议来有效解 决冲突，实现标签的高效识别．时隙ＡＬＯＨＡ协议 将若干个时隙组织为一帧，在每一帧开始时，阅读器 广播帧的长度犳，即当前帧所包含的时隙个数，并通 过发送连续的电磁波来激活扫描范围内所有标签． 每个标签在接收到帧长犳之后随机独立地在第１～ 犳个时隙中选择一个时隙发送标识符．如果成功，即 无冲突发生，该标签进入静默状态；如果有冲突发 生，则该标签将继续等待在下一帧中再选择一个时 隙重新发送标识符．因此，每一帧的时隙会存在如下 ３种情况之一：（１）空时隙（ＥｍｐｔｙＳｌｏｔ）．没有任何 一个标签选中该时隙；（２）单时隙（ＳｉｎｇｌｅｔｏｎＳｌｏｔ）． 仅有唯一一个标签选中该时隙；（３）冲突时隙 （ＣｏｌｌｉｓｉｏｎＳｌｏｔ）．多个标签选中该时隙．上述每种时 隙所包含的信息量各不相同．目前，时隙ＡＬＯＨＡ 协议已经成为ＲＦＩＤ系统在ＥＰＣＣ１Ｇ２标准下使用 的通信协议．在表１中，我们分别从优缺点两个方面 对上述两种防冲突算法进行了比较，总体而言，两者 在性能与功能实现方面各有利弊． 对于时隙ＡＬＯＨＡ协议而言，每一轮所采用的 帧长对总体的识别性能至关重要．对于给定的待读 标签集合，如果帧长过大，则该帧大部分时隙为空时 表１两类防冲突算法的优缺点比较 基于二进制树防冲突算法 基于ＡＬＯＨＡ防冲突算法 优点 通常使用确定性的算法， 算法实现逻辑简单；基于 查询树结构的算法不需 要存储中间状态变量 使用随机算法，算法实现逻辑简 单；平均情况下，标签识别性能良 好；随机算法使得各时隙的结果 在统计意义上符合一定的概率分 布，有助于进行各种统计性分析 缺点 对基于查询树结构的算 法，标签识别的时延受扫 描范围内标签犐犇的分 布以及犐犇的长度影响 算法的随机性导致存在“饿死”问 题，某些标签可能永远选择不到 单时隙进行传输；最坏情况下，标 签识别的时延趋向于＋∞，其性 能无法保障 隙，导致时隙的浪费；如果帧长过小，则该帧大部分 时隙会出现标签传输冲突，导致大部分标签需要在 下一帧重传．因此，研究者们对该问题进行了深入研 究．文献［５］分析了在时隙ＡＬＯＨＡ协议中采用动 态帧长的方法对读取性能的影响．文献［６］基于贝叶 斯的概率模型提出了优化动态帧长的决策机制．文 献［７］利用马尔可夫过程来对读取过程进行建模，并 且由此计算出读取过程中应该使用的一系列优化的 帧长．文献［８］进一步针对最大化信道使用效率的目 标推导出优化的动态帧长，该文指出，如果每一轮中 帧长与当前未读取的标签数相同，则整个信道能够 达到最大的使用效率．其原理阐述如下：假设当前标 签数目为狀，帧长为犳；由于标签对时隙的选择符合 二项分布，则根据二项分布，当前帧中单时隙的期望 数目为犈［狀１］＝狀×（１－１／犳）狀－１；为了最大化信道 的使用效率，即单时隙数目在当前帧中的比例 狀１／犳，我们采用求极值的方法计算犳的取值，即 !犈［狀１］／犳 !犳 ＝０→犳＝狀，得到此时信道的使用效率 为狀１／犳→１／ｅ．对于上述性质，我们在图２和图３ 中给出更为形象的描述．图２展示了给定标签数目 狀＝１００，帧长犳变化对信道使用效率的影响．可以 看到当帧长犳由小及大变化时，信道的使用效率逐 渐增大后又逐渐减小，在犳＝１００时取到最大值１／ｅ． 图３展示了随着标签数目狀变化，使用最优帧长 犳＝狀对信道使用效率的影响．可以看到当狀取值 较小时，所达到的最优效率大于１／ｅ，例如，当仅有 一个标签时（狀＝１），帧长为１可以达到最优效率 １００％．当狀逐渐增大时，其最优效率快速收敛到 １／ｅ．这就意味着，当狀＞５时，每一轮帧长犳取值为 当前待读的标签数狀时，使用效率趋向于１／ｅ，可以 达到当前每一轮的局部最优效率．如果在识别过程 中每一轮都使用该策略，则整体效率可接近１／ｅ．由 于１／ｅ是整体效率的上限值，因此当前整体效率接 近全局最优． ３期 谢磊等：ＲＦＩＤ数据管理：算法、协议与性能评测 ４５９