一种改进的基于二叉树的防碰撞算法

１ 引言
近年来 ， 随着物联网概念的提 出 ， 其相关 的理 论研 究得到 迅速发展ｎ 。作为物联 网概念 中一个 重要 的技术应用 ， 频识 射 别技术 （ ＦＤ） Ｒ Ｉ 也是近年来迅速发展 的热点技术之一 。通常 ， ＲＩ Ｆ Ｄ系统 由标签 和 阅读 器两 部分组 成 。由于 工作于 同一频 率， 当多个标签位 于同一阅读器的工作范 围内时 ， 如果 同时回 复 信息 ， 导致 各个 标签之 间 的传输 信息 相互 干扰 ， 之为 将 称 “ 标签碰 撞 ” 。标签 碰撞问题是 影响 Ｒ Ｉ ＦＤ系统 读取效率 的核 心问题 。 在 国内外 的理 论研究 中 ， 标签碰撞 问题主要 有两类解 决
Ｋｅ ｏ ｄ ：Ｒ ｄｏ Ｆｅｕ ｎｙ Ｉｅｔ ｃｔ ｎ Ｒ Ｉ ； ｇ ｏｌｉｎ ｂｎｒ ｎｉ ｏｌｉｎ ａ ｏｉ ｍ ｙ ｗ ｒ ｓ ａ ｉ ｒｑ ｅｃ ｄ ｎｉ ａｏ （ Ｆ Ｄ）ｔ ｓｃｌｓ ；ｉａｙ ａ ｔｃｌｓ ｌ ｒｈ ｉ ｆ ｉ ａ ｉｏ — ｉｏ ｇ ｔ
摘
要 ： 为物联 网应用 中的关键 技术 ， 频识别（ ＦＤ） 作 射 Ｒ Ｉ 技术是近年来的热 门研究领域 。在 大规模的 Ｒ Ｉ 用 中， Ｆ Ｄ应 不可避免地
ａｅ ｉ ｒ ｃ ｎ ｅ ｒ． ｅ ａ ｇ －ｃ ｌ Ｒ Ｄ ａ ｐ ｉ ａｉ ｎ ，ｈ ｒ ｗｉ ｅ ｎ ｖ ｔｂ ｅ ｏ ｌ ｉｎ ｆ ｔ ｇ ｉ ｅ ｔ ｃ ｔｏ ． ａ ｒ ｆ ｒ ｒ ａ ｎ ｅ ｅ ｔ ｙ ａ ｓ ｎ ｔ ｌｒ ｅ ｓ ａｅ ＦＩ Ｉ ｈ ｐ ｌｃ ｔ ｓ ｔ ｅ ｅ ｏ ｌ ｂ ｉ ｅ ｉ ｌ ｃ ｌ ｓｏ ｏ ａ ｓ ｄ ｎ ｉ ａｉ ｎ Ａｓ ｅ ｅ － ｌ ａ ｉ ｉ ｆ
关键词 ： 射频识别（ ＦＤ）标签碰 撞； ＲＩ ； 二进 制防碰撞算法

中图分类号
射 频识别 防碰撞 算法 返 回二进制树 算法
Ｔ Ｐ ３ １ ２ 文献标识码 Ａ Ｄ Ｏ Ｉ ： １ ０ ． ３ ９ ６ ９ ／ ｊ ． ｉ ｓ ｓ ｎ ． １ ０ ０ ０ ￣８ ６ ｘ ． ２ ０ １ ３ ． １ ０ ． ０ ８ ５
ＡＮ Ｉ Ｍ ＰＲＯＶＥＤ ＢＩ ＮＡＲＹ ＡＮＴＩ ． ＣＯＬＬＩ Ｓ Ｉ ＯＮ ＡＬＧ０Ｉ ＵＴＨＭ
杨晓娇 闫 斌 谢光斌
（ 电 子科 技 大学 四川 成都 ６ １ １ ７ ３ １ ） （ 宜 宾 电业 局 四川 宜 宾 ６ ４ ４ ０ ０ ０ ）
摘 要
主要针对 Ｒ Ｆ Ｉ Ｄ系统 中标签 的碰撞 问题 ， 在 返 回式二进制 防碰撞算 法 的基 础上提 出一种 改进 算法。该 改进 算法规 定 当
第３ ０卷第 １ ０期
２ ０ １ ３年 １ ０月
计算机 应 用与软件
Ｃｏ ｍｐ ｕ ｔ ｅ ｒ Ａｐｐ ｌ ｉ ｃ ａ ｔ ｉ ｏ ｎ ｓ ａ ｎ ｄ Ｓ ｏ ｆ ｔ ｗａ ｒ ｅ
Ｖ０ １ ． ３ ０ Ｎｏ ． １ ０ Ｏｃ ｔ ．２ ０１ ３
一
种 改进 的二 进 制 防碰 撞 算 法
标签发 生碰撞 时， 将被识别标 签 Ｕ Ｉ Ｄ从最高碰撞位开始 的 ｋ ｂ ｉ ｔ Ｕ Ｉ Ｄ值 ， 通过计算重新生成 ２ ｂ ｉ ｔ 数据返 回给 阅读器 。该数据包含 了
原标签 的 ｋ ｂ ｉ ｔ Ｕ Ｉ Ｄ 的值 的信息 ， 使得碰撞 后阅读器依 然能正确识 别 出该值 ， 减少 了命令 搜 索次 数。最后通 过仿真 与其它 改进 的二 进制树算法做 了对 比， 证 明该算法在 阅读器寻呼命令和搜寻 时间上 的高效性。 关键词
Ｙ ａ ｎ ｇ Ｘ ｉ ａ ｏ ｊ ｉ ａ ｏ Ｙ ａ ｎ Ｂ ｉ ｎ Ｘ ｉ ｅ Ｇ ｕ ａ ｎ ｇ ｂ ｉ ｎ

收稿日期 : 2007 -12 -10; 修改日期 : 2008 - 02 -25 作者简介 : 单承赣 ( 1942- ) , 男 , 安徽合肥人 , 合肥工业大学教授 , 硕士生导师 .
1802 突问题, 实现标签快速、 高效地读取
[ 2, 3]
合肥工业大学学报( 自然科学版 ) 。
第 31 卷
摘
余春梅,
王聪聪
230009)
( 合肥工业大学 计算机与信息学院 , 安徽 合肥
要 : 在射频识别系统中 , 存在阅读器与多个标签同时通信的碰撞问题 , 标签的防碰撞算法是解决数据冲突
的关键。文章详细阐述了已有的典型的二进制查询树的防碰撞算法 , 并在此基础上提出了一种新的防碰撞算 法 ; 该算法利用二时隙的方法 , 使阅读器的询问次数和标签识别所需的数据流大大减少 , 提高了标签的识别效 率。从仿真实验中表明 , 该算法比已有的二进制查询树算 法具有更明显的优势。 关键词 : 射频识别 ; 防碰撞算法 ; 时分多址 ; 二进制查询树算法 中图分类号 : T N015 文献标识码 : A 文章编号 : 1003 -5060( 2008) 11 - 1801 - 04
每次都是从根来搜索 , 而是选择从最接近的节点 来搜索。位于阅读器一边的便是前缀, 而位于标 签的便是对应的回答 , 从左到右的长度便代表了 标签识别的时延, 如图 2、 图 3 所示。
由上为识别出 5 个标签, 查询树算法需要传 送 22 位的前缀和 15 位应答位 , 因此识别出所有 的标签总共需要 37 位的数。另一方面 , 二时隙查 询树算法需要 7 位前缀和 15 位应答数 , 总共需要 22 位用来进行标签识别。因此, 二时隙查询树算 法更多的比查询树算法减少了传输的前缀。 2 3 仿真试验 进一步实验 , 基于射频识别标签的规范, EPC 编码是与 EAN/ U CC 编码兼容的新一代编码标 准, EP C 提供对物理对象的唯一标识。当前出于

RFID系统中一种改进的防冲撞算法
张颇;崔喆
【期刊名称】《计算机应用》
【年(卷),期】2008(28)8
【摘要】提出了一个在RFID系统中改进的防冲突算法,该算法基于Aloha算法并结合了二叉树算法.当有大量标签同时需要识别时,首先通过对标签上一轮的碰撞情况来估计待识别的标签数,然后对标签进行分类或改变帧的大小来降低标签发生碰撞的概率,从而提高识别的效率.
【总页数】3页(P2141-2143)
【作者】张颇;崔喆
【作者单位】中国科学院,成都计算机应用研究所,成都,610041;中国科学院,成都计算机应用研究所,成都,610041
【正文语种】中文
【中图分类】TP311.11
【相关文献】
1.动态RFID系统中一种准确标签估计的动态帧时隙ALOHA算法 [J], 王达;李晓武
2.大规模RFID系统中一种能量有效的丢失标签快速检测算法 [J], 张士庚;刘光亮;刘璇;王建新
3.RFID系统中一种动态帧时隙算法的研究与仿真 [J], 杜俊宇;何宁
4.RFID系统中一种改进的安全认证协议研究 [J], 徐艳玲
5.RFID系统中一种改良的防冲突算法的研究 [J], 刘洋; 惠晓威
因版权原因，仅展示原文概要，查看原文内容请购买。