第３６卷第５期 ２０１５年９月 肇庆学院学报 ＪＯＵＲＮＡＬ ＯＦ ＺＨＡＯＱＩＮＧ ＵＮＩＶＥＲＳＩＴＹ Ｖｏ１．３６，Ｎｏ．５ Ｓｅｐ．２０１５ ＵＨＦ ＲＦＩＤ多标签防碰撞检测技术综述及发展趋势 黄 伟 ，程 顺 （肇庆学院ａ．电子信息与机电工程学院；ｂ．计算机学院，广东肇庆５２６０６１） 摘要：介绍了基于二进制搜索的确定性算法和基于ＡＬＯＨＡ的非确定性算法．对该２类算法进行了综述和分 析，评述了各种具体算法的优与劣，为进一步研究ＲＦＩＤ防碰撞问题提供了参考． 关键词：ＲＦＩＤ；多标签；ＡＬＯＨＡ防碰撞算法；二进制树防碰撞算法 中圈分类号：ＴＮ９２ 文献标志码：Ａ 文章编号：１００９．８４４５（２０１５）０５．００１１－０４ 射频识别（ＲＦＩＤ，ｒａｄｉｏ ｆｒｅｑｕｅｎｃｙ ｉｄｅｎｔｉｉｆｃａｔｉｏｎ）技术是众多自动识别技术的一种，也是物联网的关键技 术之一．它利用射频信号及其空间耦合的传输特性，实现对静止和移动物品的非接触式自动识别．由于ＲＦＩＤ 具有非接触性、非可视读取、操作距离远、可靠性高、安全性好、存储介质容量大和便于与应用系统集成等优 势，因而被广泛应用于智能交通、物流、门禁、食品安全、产品质量跟踪、零售业、生产流水线管理等诸多信息 化应用领域中． 相比低频和中高频ＲＦＩＤ系统，ＵＨＦ ＲＦＩＤ阅读器的读写距离更远，天线信号有效区域内的电子标签更 多，阅读器对电子标签信息的读写速度更高．同时，ＵＨＦ ＲＦＩＤ系统的标签内部不提供电源，通信距离有限， 标签设计得相对简单，通常不提供计算能力很强的ＣＰＵ，以上种种原因导致ＵＨＦ ＲＦＩＤ系统的标签碰撞异 常严重，因此用于ＵＨＦ ＲＦＩＤ系统的防碰撞算法相较其他算法的要求更为严格． ＵＨＦ ＲＦＩＤ系统主要由阅读器和标签构成，随着ＲＦＩＤ技术的发展及其在各领域的广泛应用，ＲＦＩＤ系 统中标签的规模随之增大，要求阅读器同时识别多个标签的能力也与日俱增，其关键技术——防碰撞技术愈 发引人关注，成为该领域众多科研人员的研究重点． １ Ｕ Ｈ Ｆ Ｒ Ｆ Ｉ Ｄ防碰撞算法 碰撞是指在阅读器的天线磁场区域内会出现多个标签，或者有其他阅读器存在．当阅读器查询标签时， 多个标签同时响应阅读器的命令或者一个标签同时要选择响应２个阅读器的查询信号时，出现信号干扰产 生的信道冲突问题．ＵＨＦ ＲＦＩＤ系统能够在很短时间内读取大量标签，且其磁场区域相较ＨＦ ＲＦＩＤ系统及 ＬＦ ＲＦＩＤ系统要大，且磁场相对均匀，因此ＵＨＦ ＲＦＩＤ系统的碰撞问题更为突出． ＵＨＦ ＲＦＩＤ系统的碰撞问题分为标签碰撞和阅读器碰撞２种．当阅读器的天线磁场区域内出现多个标 签时，阅读器查询标签出现多个标签信道冲突的情况称为标签碰撞；当同一标签处在多个阅读器的天线磁 场范围内，多个阅读器同时发送查询命令，而标签无法判断响应哪个阅读器的情况称为阅读器碰撞． １．１ 防碰撞算法分类 ＲＦＩＤ防碰撞算法是指在ＲＦＩＤ系统中使用的一些用来避免信道冲突的策略或方法，通过其控制标签逐 个响应阅读器的盘存命令，并识别标签的有效信息．防碰撞算法分类情况如图１所示． 收稿日期：２０１５—０７．１０ ． 基金项目：肇庆市科技计划项目（２０１２Ｇ０２７） 作者简介：黄伟（１９６４－），男，湖北武汉人，肇庆学院电子信息与机电工程学院副教授． 第５期 黄伟等：ＵＨＦ ＲＦＩＤ多标签防碰撞检测技术综述及发展趋势 １３ ＡＬＯＨＡ算法（ｄｙｎａｍｉｃ ｆｒａｍｅ ｓｌｏ ＬＯＨＡ——＿ＤＦＳＡ）算法． 标签估计算法：常见的标签估计算法主要有简单的最小值估计算法、基于概率的泊松估计、基于切比雪 夫不等式的切比雪夫不等式估计算法，以及基于标签碰撞概率的碰撞率估计算法等，之后有国内外学者又 提出了ＰＺＥ估计及ＬｏＦ估计． 最小值估计算法：对于最小值估计算法，当阅读器读写范围内的标签数量相对很大时，其估计误差也会 很大。且其误差随标签数量的增大而增大． Ｓｃｈｏｕｔｅ估计算法：Ｓｃｈｏｕｔｅ估计算法虽然考虑了碰撞时隙中同时存在大于２个标签的情况，但是其系数 相对固定；当标签数量增大时，其与最小值估计算法一样，误差也相对增大，效率严重降低． 切比雪夫不等式估计算法：切比雪夫不等式标签估计算法在阅读器读写范围内标签数量相对较小时 （小于５ １ ２个），其估计算法的估计精度相对较高，但是其精确度是基于相对大的运算量基础之上的，算法的 复杂度相对较高，严重影响了算法的速度． Ｌｏｆ算法：上面３种标签估计算法，都依赖于盘存命令获得的空闲时隙个数和碰撞时隙个数．在标签数量 较小时，其估计精确度表现很好；但是当标签数量增大时，其估计误差随标签数量的增加而增大． １．３确定性标签识别算法 在图ｌ中，确定性算法均基于二进制搜索算法，主要包括二进制搜索算法、动态二进制搜索算法、预处 理二进制搜索算法、后退式二进制搜索算法等．实现二进制搜索算法的前提是阅读器能够准确地对多个标 签的碰撞位进行检测，并且基于标签中ＩＤ号的唯一性，可以在多次查询后识别标签的ＩＤ号． 二进制搜索算法：二进制搜索算法是基于二叉树分叉原理，把碰撞位分为０和１这２个分支进行搜索， 实现标签群中标签的逐个识别．在标签数量较小时，其系统的吞吐率相对较大，当标签数量增大到５０之后， 系统的吞吐率会严重降低．鉴于以上原因，有研究者又提出了动态二进制搜索算法及一些改进算法． 动态二进制搜索算法：ＩＳＯ １４４４３Ａ标准推荐动态二进制搜索算法，作为其防碰撞算法．动态二进制搜索 算法是在二进制搜索算法的基础上，只传输最高碰撞位之前的ＩＤ信息，标签只传输最高碰撞位之后的信 息，减少了传输的信息，以增加系统的传输效率．动态二进制搜索算法避免了多余信息的传输，使得标签信 息的单次传输时间大幅度缩短，但是该算法的时间复杂度相较二进制搜索算法并未降低． 后退式二进制搜索算法：基于二进制搜索算法的改进算法很多，较常用的是后退式二进制搜索算法．后 退式二进制搜索算法相较二进制搜索算法的不同点在于成功识别完一个标签后，阅读器不再重新发送 ｌ１１１ｌ１１ｌ，而是在上次检测到的碰撞位的位置回溯查询，直到查询完所有标签为止后退式二进制搜索算法， 提高了读写时间及系统的吞吐率，但是该算法存在着天然缺陷，当标签的数量过大时，阅读器必须保存所有 的碰撞信息，因此需增大阅读器的堆栈空间． ２ Ｕ Ｈ Ｆ Ｒ Ｆ Ｉ Ｄ标准中采用的防碰撞算法及发展趋势 目前ＲＦＩＤ存在３个主要的技术标准体系：总部设在美国麻省理工学院（ＭＩＴ）的Ａｕｔｏ—ＩＤ Ｃｅｎｔｅｒ（自动识 别中心）、ＩＳＯ标准体系以及Ｅｌ本的Ｕｂｉｑｕｉｔｏｕｓ ＩＤ Ｃｅｎｔｅｒ（泛在ＩＤ中心，ｕＴｃ）．ＩＳＯ组织针对超高频射频识别应 用制定了ＩＳＯ１８０００－－－６系列标准．在超高频（８６０—９６０ＭＨｚ）这个频段内，目前由国际标准化组织ＩＳＯ颁布的 国际标准ＩＳＯ／ＩＥＣ １８００ｏ＿－６中有３种协议标准，分别为ＩＳＯ／ＩＥＣ １８００ｏ－．６Ａ、ＩＳＯ／ＩＥＣ １８０００－－６Ｂ和ＩＳＯ／ ＩＥＣ １８０００－－－６Ｃ．该系列协议规定了读写器与标签之间的物理接口、协议和命令以及防碰撞算法．该系列协议 包含ＴｙｐｅＡ、Ｔｙｐｅ Ｂ和Ｔｙｐｅ Ｃ ３种无源标签的接口协议，其中Ｔｙｐｅ Ｃ在读写速度、存储容量、防碰撞算法和 安全性能等方面有较大提高．Ｔｙｐｅ Ａ处理标签碰撞采用的是ＡＬＯＨＡ协议，Ｔｙｐｅ Ｂ采用自适应二进制树协 ｌ４ 肇庆学院学报 第３６卷 议，而Ｔｙｐｅ Ｃ则采用时隙ＡＬＯＨＡ协议． 有源电子标签和半有源电子标签的应用不断发展，这些类型标签的防碰撞技术均不会脱离上述防碰撞 算法．即使是无源电子标签以后发展的防碰撞技术，在针对不同应用领域和不同应用场合时，会有对基于二 进制搜索确定算法和基于ＡＬＯＨＡ算法的修改、补充和完善，使其识别效率更高，漏识别更少，但要在实现 防碰撞技术基本原理上有性突破是非常困难的． ３ 结语 本文较全面地介绍了基于二进制搜索算法的确定性算法和基于ＡＬＯＨＡ算法的非确定性算法，对基于 该２类算法所衍生出来的各种具体算法进行了综述和分析，点评了各种具体算法的优与劣，旨在为进一步研 究ＲＦＩＤ防碰撞问题提供一些有益的参考． 参考文献： 【ｌ】王雪，钱志鸿．基于二叉树的ＲＦＩＤ防碰撞算法的研究【Ｊ］．通信学报，２０１０，３ １（６）：４９．５７． ［２】孙文胜，胡玲敏．基ｆｆ－￣／ＩＬ式搜索的自适应多叉树防碰撞算法［Ｊ】．计算机应用，２０１１，３１（８）：２ ０５２．２ ０５５． 【３】张航，唐明浩，程晖．改进的返回式二进制防碰撞算法【 ．计算机工程与应用，２０１１，４７（２５）：２０８－２１１． ［４】程文青，赵梦欣，徐晶．改进的ＲＦＩＤ动态帧时隙ＡＬＯＨＡ算法【Ｊ】．华中科技大学学报（自然科学版），２００７，３５（６）：１４．１６． 【５】李萌，钱志鸿．基于时隙预测的ＲＦＩＤ防碰撞ＡＬＯＨＡ算法川．通信学报，２０１１，３２（１２）：４３—５０． 【６】ＪＵＮＩＵＳ Ｈ，ＤＡＮＩＥＬ Ｗ Ｅ，ＳＡＪＡＹ Ｅ Ｓ．Ａｈｉｅｒａｒｃｈｉｃａｌ Ｑ・ｌｅｍｉｎｇ ａｌｇｏｒｉｔｈｍ ｔｏ ｓｏｌｖｅ ｔｈｅ ｒｅａｄｅｒ ｃｏｌｌｉｓｉｏｎ ｐｒｏｂｌｅｍ［／］．ＩＥＥＥ Ａｐｐｌｉ－ ｃａｔｉｏｎ ａｎｄ ｔｈｅ Ｉｎｔｅｍｅｔ Ｗｏｒｋｓｈｏｐｓ，２００６，２（４）：２－１０． ［７】 ＥＯＭ Ｊ Ｂ，ＬＥＥ Ｔ Ｊ．Ａｃｃｕｒａｔｅ ｔａｇ ｅｓｔｉｍａｔｉｏｎ ｆｏｒ ｄｙｎａｍｉｃ ｆｒｍａｅｄ—ｓｌｏｔｔｅｄ ＬＡＯＨＡ ｉｎ ＲＦＩＤ ｓｙｓｔｅｍｓ［Ｊ］．ＩＥＥＥ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ Ｌｅｔｔｅｒｓ，２０１２，１４（１）：６０．６２． Ｏｖｅｒｖｉｅｗ ｏｖｅｒｖｌｅｗ ａｎｄ ｎａＯ ＤｅｖｅｌｏｏｍｅｎｔＤ Ｄｍ ａｌ Ｔｌｌｒｅ ｒｅｎｄ ｏｆ唧ＵＨ Ｒ．一Ｆ］Ｐ ｌＪ口［ ）Ｍｕｌｌｔｉｔｌ Ｌａｂｌ－ＬａＯｌｅｅ ｎａｄ Ａｎｔｉ－Ｃｏｌｌｉｓｉｏｎ Ｄｅｔｅｃｔｉｎｇ Ｔｅｃｈｎｏｌｏｇｙ ＨＵＡＮＧＷｅｉ。，ＣＨＥＮＧ Ｓｈｕｎｂ （ａ．Ｃｏｌｌｅｇｅ ｏｆＩｎｆｏｒｍａｔｉｏｎ Ｍｅｃｈａｎｉｃａｌ ａｎｄ Ｅｌｅｃｔｒｉｃａｌ Ｅｎｇｉｎｅｅｒｉｎｇ； ｂ．Ｃｏｌｌｅｇｅ ｏｆＣｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，Ｚｈａｏｑｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ，Ｚｈａｏｑｉｎｇ，Ｇｕａｎｇｄｏｎｇ ５２６０６１，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｄｅｔｅｒｍｉｎｉｓｔｉｃ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｂｉｎａｒｙ ｓｅａｒｃｈ ａｌｇｏｒｉｔｈｍ ａｎｄ ｎｏｎ—ｄｅｔｅｒｍｉｎｉｓｔｉｃ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ＡＬＯＨＡ ａｌｇｏｒｉｔｈｍ ａｒｅ ｉｎｔｒｏｄｕｃｅｄ．Ｔｈｅ ｓｐｅｃｉｉｆｃ ａｌｇｏｒｉｔｈｍ ｏｆ ｈｔｅ ｔｗｏ ｋｉｎｄｓ ｏｆ ａｌｇｏｒｉｈｔｍｓ ｉｓ ｓｕｍｍａｒｉｚｅｄ ａｎｄ ｎａａｌｙｚｅｄ．Ｔｈｅ ａｄｖａｎｔａｇｅｓ ａｎｄ ｄｉｓａｄｖａｎｔａｇｅｓ ｏｆ ｖａｒｉｏｕｓ ａｌｇｏｒｉｔｈｍ ａｒｅ ｇｉｖｅｎ ｔｏ ｐｒｏｖｉｄｅ ｔｈｅ ｒｅｆｅｒｅｎｃｅ ｆｏｒ ｆｕｒ－ ｔｈｅｒ ｒｅｓｅａｒｃｈ ｏｎ ＲＦＩＤ ｎａｔｉ－ｃｏｌｌｉｓｉｏｎ ｐｒｏｂｌｅｍｓ． Ｋｅｙ ｗｏｒｄｓ：ＲＦＩＤ；ｍｕｌｔｉ－ｌａｂｌｅ；ＡＬＯＨＡ ｎａｔｉ—ｃｏｌｌｉｓｉｏｎ ａｌｇｏｒｉｔｈｍ；ｂｉｎａｒｙ ｒｔｅｅ ｎａｔｉ－ｃｏｌｌｉｓｉｏｎ ａｌｇｏｒｉｔｍｈ （责任编辑：陈静）
