无线射频识别系统中的标签防碰撞算法综述

计算机科学　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　无线射频识别系统中的标签防碰撞算法综述　肖菊兰　（成都工业学院电气与电子工程系，成都６１１７３０）　摘要：由于应用环境的要求，阅读器或标签必须要进行防碰撞处理。同时防碰撞算法的优劣直接关系到标签　与阅读器通信性能的好坏。所以防碰撞算法的研究对扩展物联网的应用非常必要。本文讲述了现今存在的标签防碰　撞算法，包括二进制树系列算法、ＡＬＯＨＡ系列算法和标签估计算法，并指出算法的研究方向。　关键词：标签；二进制数；ＡＬＯＨＡ；标签估计　中图分类号：ＴＰ３９１．４４　文献标识码：Ａ　文章编号：１６７４—７７１２（２０１４）１８－０１２９－０２　ＲＦＩＤ（Ｒａｄｉｏ　Ｆｒｅｑｕｅｎｃｙ　Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ），＆口射　页身　份鉴别，由阅读器和标签组成。利用无线电波在无人工干预　条件下能够实现多目标自动识别，已被广泛用于生产销售、　物流配置、交通运输、医疗器具、国防科技等各个行业。　由于单个阅读器读取范围有限，所以很多应用中使用多　个阅读器来识别目标区域中的多个标签。碰撞是指多个标签　或多个阅读器间相互干扰，使得标签或阅读器无法正确接收　到阅读器或标签发送来的信号，可分为由多个阅读器同时发　送信息给标签引起标签无法正确与阅读器通信的阅读器碰撞　和由多个标签同时与阅读器通信引起的阅读器无法正确识别　标签的标签碰撞两大类。而针对这两种碰撞所采取的应对措　施，分别称为阅读器防碰撞算法和标签防碰撞算法。本文主　要介绍无线射频识别系统中的标签防碰撞算法。　一、标签防碰撞算法　按照碰撞时标签响应方式，防碰撞算法可分为确定性算　法和不确定性算法。目前，确定性算法大多基于树结构算法，　而不确定性算法大多是基于ＡＬＯＨＡ算法。　（一）基于树结构算法　系统识别的可靠性较高，大多基于二进制树。当阅读器　接收到标签发送的ＩＤ信息遇到碰撞时，将标签分支成两个子　集进行通信，如再遇碰撞再分支成两个子集，这些子集分支　会越来越小，一直到分支下面只有一个标签与其通信时，完　成一次识别，再返回最近的另一个子集与标签通信，如此递　归完成所有标签的识别。　１．基本二进制树算法。基本二进制树搜索算法中阅读器　首先发送指令给标签，标签通过比较接收序列号与自身序列　号，如果小于等于，则发送自己的ＩＤ给阅读器，否则等待。　直到识别某个标签后让其进入休眠状态，又重新搜索。此算　法是所有二进制树搜索算法的基础，阅读器与标签的每次通　信时间受标签ＩＤ的长短的控制。　基本的树分裂算法也为阅读器先说型，即阅读器首先向　其作用场内标签发送查询指令，然后标签做出响应。当标签　响应信息产生冲突时，阅读器会命令标签生成一位二进制数　（“０”或“１”），将场内标签分为两个子集，其中一个子　集先响应。若碰撞，再分子集。子集分支越来越小，一直到　分支下面只有一个标签与其通信时，完成一次识别，再返回　最近的另一个子集与标签通信，如此递归完成所有标签的识　别。　２．改进二进制搜索算法。现有的二进制防碰撞搜索算法　选用曼彻斯特编码以确定碰撞位的准确信息，进而阅读器可　以根据碰撞的位置，重新搜索标签。　返回式二进制防碰撞算法规定阅读器在收到标签返回信　息检查碰撞位，下次通信时寻找第一位碰撞位上为０的标签，　并让其响应；阅读器如果收到标签返回信息又有碰撞，那么　又搜索此次返回信息第一碰撞位为０的标签，直到识别到标　签，然后将搜索最开始一次碰撞位为１的标签；若遇碰撞，　则搜索此次第一碰撞位为０的标签，直到所有位碰撞位都搜　索完，再搜索第二碰撞位上为１的标签，如此，直至所有标　１２９　焉贯电子２０１４　签都被识别。此算法不会在每次识别到标签后就又开始新一　轮的搜索，而是基于其父节点进行搜索，故而系统的识别效　率有所提高。修剪枝二进制搜索算法利用二进制搜索法顺利　读出第一个标签后，并不返回第一个碰撞位，而是采用就近　原则，返回到最近一级的碰撞位，将碰撞位取反获得新的ＩＤ　进行搜索，等搜索成功后再返回更上一级碰撞位　。修剪枝　二进制搜索算法由于返回就近，并非返回父节点，故而所需　时问更短，但程序较为复杂，适用于标签数量较多且ＩＤ较长　的场合。文献［２］提出一种基于后退式二进制防碰撞搜索算　法：在原有后退式二进制防碰撞搜索算法的基础上增加了休　眠状态，并将不参与发送数据的标签转为休眠状态，减少了　标签不必要的信息比对。　动态二进制树防碰撞算法在基本二进制搜索算法的基础　上，规定标签不需要每次都返回完整的信息，而是返回碰撞　位以后部分。由于标签与阅读器的通信位数变少，使得此算　法中阅读器与标签的通信时间少于基本的二进制搜索算法。　文献［３］中提出了一种四叉树ＲＦＩＤ防碰撞算法，将碰　撞位两位为一组，由于两位二进制具有四种组合，所以可使　其构成一个四叉树进行搜索。　３．改进的二进制分裂算法。自适应二进制分裂算法要　求阅读器和标签都有计数器，分别用于对进展时隙数计数和　对分配时隙数计数。相对于基本的树分裂算法，当碰撞时，　分组不再是两组，而是标签产生一个随机数，当当前时隙与　随机数相同时标签响应，否则标签不响应。利用此算法识别　完标签后，理论上场内所有标签都有唯一的分配时隙与其对　应，但是此算法识别标签的能力受阅读器最大分配时隙数的　限制。　（二）ＡＬＯＨＡ系列算法　总体而言，基于树的算法硬件设计较为复杂。故而，在　考虑低成本时，ＲＦＩＤ标签一般是基于ＡＬＯＨＡ系列算法设计。　而如何提高该防碰撞算法系统识别的可靠性便成为目前低成　本ＲＦＩＤ标签应用系统的一个研究重点。　１．基本ＡＬＯＨＡ算法。基本ＡＬＯＨＡ算法采用标签先发言，　即一旦标签进入阅读器场内，便向阅读器发送自身ＩＤ。可能　会出现标签完全碰撞和标签部分碰撞。若碰撞，阅读器命令　标签随机等待一段时间再次发送信息。此算法实现简单，但　在标签数量少或阅读器与标签之间信息较小时，传输信道大　部分时间都处于空闲状态；而在标签数量多或阅读器与标签　之间信息较大时，标签群之间的碰撞严重。故而，ＡＬＯＨＡ在　多标签环境下的标签碰撞往往会造成链路的吞吐率较低，最　高可为１８．４％。　２．时隙ＡＬＯＨＡ算法和帧时隙ＡＬＯＨＡ算法。时隙ＡＬＯＨＡ算　法是在纯ＡＬＯＨＡ算法的基础上，规定标签只能在每个时隙开　始的时候才能够向读写器发送自己的信息，这样避免了多标　签环境下的部分碰撞，使吞吐率提高一倍，但此算法在标签　数量比较大的时候系统的效率还是很低。帧时隙ＡＬＯＨＡ算法　将信道分成ｍ个帧，标签选择一帧当中的一个时隙来与读写　器进行通信。　计算机科学　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　矗　３．动态帧时隙ＡＬＯＨＡ算法。时隙ＡＬＯＨＡ算法和帧时隙　ＡＬＯＨＡ算法，由于标签处于流动状态而数目不定，所以从始　至终固定时隙会使效率低下，从而有了动态帧时隙ＡＬＯＨＡ算　法。　动态帧时隙ＡＬＯＨＡ算法是在帧时隙ＡＬＯＨＡ算法的基础上，　为０．ｉ００　０．３５４，且碰撞时的Ｃ是空闲时的１．４１２２倍；文献　［６］中Ｑ与ｃ的关系为：　Ｑ＝１时：Ｃ＝Ｏ．５；Ｑ＝２时：０．３３≤Ｃ＜０．５；Ｑ＝３时：　０．２５≤Ｃ＜Ｏ．３３；Ｑ＝４或时：０．２≤Ｃ＜Ｏ．２５；Ｑ－６或７时：　０．１６７≤Ｃ＜Ｏ．２；Ｑ＝８或９时：０．１４３≤Ｃ＜Ｏ．１６７；Ｑ＝ＩＯ或１１　时：０．１２５≤Ｃ＜Ｏ．１４３；Ｑ＝１２时：０．１１１≤Ｃ＜Ｏ．１２５；Ｑ＞１２时：　０．１≤Ｃ＜Ｏ．１ｌ１５；　为了避免链路中空时隙太多而影响整个链路中的读取延迟，　根据每次读取过程中时隙的类型（分为空时隙、碰撞时隙和　单标签时隙），对读写器射频场内的标签估计，从而设定每　帧中时隙总数。　现存的标签估算中分为三种：有利用碰撞时隙总数乘以　２的最小剩余标签预测法、的利用实际各种时隙数和预测的　各种时隙数的来估计剩余标签和Ｓｃｈｏｕｔ提出的利用碰撞时隙　乘以２．３９来估算剩余标签。　４．随机槽时隙防碰撞算法。ＩＳ０１８０００—６Ｃ协议中阅读器　与标签通信时采用随机槽时隙防碰撞算法（Ｒａｎｄｏｍ—ｓｌｏｔｔｅｄ　ｃｏｌ１ｉｓｉｏｎ　ａｒｂｉｔｒａｔｉｏｎ），即标签根据阅读器向标签发送　的Ｑ值（时隙因子）产生随机数，并由随机数决定在哪个时　隙向阅读器发送信息；而Ｑ值初值为４，然后根据标签的响　应情况，动态改变时隙因子的值。　Ｑ值的调整过程中需要注意调整因子的取值问题，即Ｃ　值取值偏大会使Ｑ值变化太快，进而时隙总数变化过快；Ｃ　值取值偏小会使Ｑ值变化会迟钝，进而时隙总数变化过慢。　Ｑ值的调整过程中需要注意调整因子的取值问题，即Ｃ值取　值偏大会使Ｑ值变化太快，进而时隙总数变化过快；Ｃ值取　值偏小会使Ｑ值变化会迟钝，进而时隙总数变化过慢。如果　能动态调整Ｃ值，Ｃ值又根据当前Ｑ值来确定，那么时隙总　数变化也将由Ｑ值的大小而决定，即Ｑ值较小时Ｃ大，时隙　调整的快；Ｑ值较大时Ｃ小，调整地慢。文献［４］中Ｃ取０．８／　Ｑ；文献［５］中规定碰撞时Ｃ为０．１４１２２　０．４９９９２，空闲时Ｃ　二、结束语　对于现存的两种算法来说，二进制树系列算法具有确　定性，但是这种算法实现比较复杂；而ＡＬＯＨＡ系列算法存在　着标签“饿死”状况，即标签始终没能够与阅读器通信。所　以在以后的研究中既要考虑算法时隙的难易性和消灭标签的　“饿死”状况。　参考文献：　［１］余松森，詹宜巨．基于修剪枝的二进制树形搜索反碰　撞算法与实现Ⅱ１．计算机工程，２００５（３１）：２１７—２１９．　［２】李秉璋，景征骏，罗烨．基于后退式二进制的ＲＦＩＤ　防碰撞搜索算法卟计算机应用与软件，２００９（２６）：９６－９８．　『３１孙耀磊，昊晓波，陈元文．一种改进的四叉树ＲＦＩＤ　防碰撞算法Ⅱ１．计算机工程与应用，２０１４（０￣：９３—９８．　【４］Ｂｅｈｚａｄ　Ｒａｚａｖｉ．Ｄｅｓｉｇｎ　ｏｆ　ａｎａｌｏｇ　ＣＭＯＳ　ｉｎｔｅｇｒａｔｅｄ　ｃｉｒｃｕｉｔｓ［Ｍ］．Ｎｅｗ　Ｙｏｒｋ，ＵＳＡ：ＭｃＧｒａｗ—Ｈｉｌｌ，２０１　１．　『５１吴淼，刘德盟，张钊锋．基于ＥＰＣＧｅｎ２防碰撞机制的　研究与优化Ⅱ］．微电子学与计算机，２０１３（３０）：１ｏｏ一１０７．　『６１王晓梅，张英梅．基于Ｑ值的ＲＦＩＤ防碰撞改进算法　的研究　．太原理工大学学报，２０１４（４５）：３３９—３４２．　［作者简介］肖菊兰，女，专职教师，助教，硕士研究生，　研究方向：电子科学技术。　（上接第１２８页）　使用自我评价、组内互评和教师评价相结合的方式进行评价。　学生完成任务过程中既要强调学生的主体性，又不能忽略教　师的主导作用，因此教师的评价和指导对于学生的能力培养　具有重要作用。教师对学生任务的评价应积极肯定，如果评　价过于形式化和简单，可能会影响对学生的激励效果。教师　在点评时要有技巧地既肯定学生的优点又指出不足之处，还　可以将评价作为该学生的考查成绩。同时在学生完成任务的　不同阶段，教师应就学生完成任务过程中出现的问题和困难　给予指导和帮助，这不仅有利于教师掌握学生的学习活动情　况，而且为学生下一步活动指明改进和优化的策略，让学生　充分体验到成就感。　四、建筑识图与ＣＡＤ绘图课程教学改革的改进方法　建筑识图与ＣＡＤ绘图课程改革过程中，实施任务驱动教　学取得了一定的成绩，但教学改革步骤仍然相对封闭，今后　将逐步改进为开放式教学。　首先，将“创设情境、引起注意、提出任务”改进为“创　设情境、引起注意、提出框架”。教师不再先演示绘制好的　成品图，再由学生讨论分析仿绘，而是转变为提出框架，如　绘制家具时，学生可以根据自己的构思设计绘制。　其次，将“针对问题、明确思路、提示重点”改进为“共　同讨论、分析框架、进行分组”。教师要给学生更多的自主性，　充分发挥其个人创意，同时增强团队协作能力。　再次，将“自主探索、领会意图、解决任务”改进为“自　主探索、积极合作、解决任务”。通过上面两个步骤的实施，　让学生把学习重点放在独立构思创意上，通过小组协作来解　决实际问题，完成工作任务。　还有，将“检查结果、发现不足、总结经验”改进为　“作品展示、经验交流、总结提升”，实施开放式教学以后，　要展示更丰富的更新奇的学生作品，让学生真正体验到成功　的感觉。教师点评时不仅是对其知识与技能掌握情况进行评　价，还应关注学生完成任务期间的合作精神、创造性、解决　问题能力等综合素质评价，评价要及时，方法要灵活运用。　五、结束语　总之，基于工作过程的建筑识图与ＣＡＤ绘图课程改革与　实践要以职业情境为依托，以项目为载体，注重过程评价，　通过创设职业情境实施课程教学改革，从而培养学生学习的　积极性，提高学生的专业技能水平，达到有效教学的目的。　参考文献：　『１１刘敏．浅谈建筑ＣＡＤ课程教学的改革ＩＡ１．土木建筑　教育改革理论与实践『ｃ１，２００９．　『２１刘利，莎滕斌，罗亚琼．浅析建筑工程制图与识图与　建筑ＣＡＤ的融合［Ｉ１＿青春岁月，２０１３（１５）．　『３张多峰．｛Ａｕｔ３１ｏＣＡＤ建筑制图》教、学、做一体化教　学改革的设计与实践【Ｉｌ＿山东水利职业学院院刊，２０１１（０１）．　杨继红，孔永红．“行动导向、任务驱动”教学模式　的　研究与实践　．山西广播电视大学学报，２０１１（Ｏ１）．　『５李杰，王海文．基于工作过程的建筑ＣＡＤ识图与制　５１图课程改革与实践盯］．中国教育技术装备，２０１３（１５）．　ｆ６１张冲．基于工作过程的《建筑制图与ＣＡＤ》课程教　学改革研究［『１．科技致富向导，２０１３（３０）．　［作者简介］刘晓光（１９７３．ｉ卜），女，辽宁辽阳人，　讲师，研究方向：建筑识图与ＣＡＤ绘图、３ｄｓ　ｍａｘ效果图绘　制及ｐｈｏｔｏｓｈｏｐ图形图像后期处理。　叭４　ｉ肓费电子１３０