基于二进制搜索的rfid标签防碰撞算法研究

《基于二进制搜索的rfid标签防碰撞算法研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、总第２５８期２０１１年第４期计算机与数字工程Ｃｏｍｐｕｔｅｒ＆ＤｉｇｉｔａｌＥｎｇｉｎｅｅｒｉｎｇＶｏｌ．３９Ｎｏ．４２９基于二进制搜索的ＲＦＩＤ标签防碰撞算法研究＊江城黄立波（武汉数字工程研究所武汉４３００７４）摘要标签碰撞是射频识别（ＲＦＩＤ）技术的常见问题，该问题影响了ＲＦＩＤ系统数据通信过程中的数据传输的完整性。目前主要有两类标签防碰撞的算法：基于ＡＬＯＨＡ的算法和基于二进制搜索的算法。文中主要对基于二进制搜索的算法做了详细的介绍，包括基本二进制搜索算法，动态二进制搜索算法和后退式动态二进制搜索算法，最后提出了一些算法改进的思路。关键词ＲＦＩＤ；标签防碰撞；二

2、进制搜索中图分类号ＴＰ３０１．６ＳｔｕｄｙｏｎＴａｇＡｎｔｉ－ｃｏｌｌｉｓｉｏｎＡｌｇｏｒｉｔｈｍｓｏｆＲＦＩＤＢａｓｅｄｏｎＢｉｎａｒｙＳｅａｒｃｈＪｉａｎｇＣｈｅｎｇＨｕａｎｇＬｉｂｏ（ＷｕｈａｎＤｉｇｉｔａｌＥｎｇｉｇｅｅｒｉｎｇＩｎｓｔｉｔｕｔｅ，Ｗｕｈａｎ４３００７４）ＴａｇｃｏｌｌｉｓｉｏｎｉｓａｃｏｍｍｏｎｐｒｏｂｌｅｍｉｎＲＦＩＤ，ａｎｄｉｔｉｎｆｌｕｅｎｃｅｓｔｈｅｉｎｔｅｇｒｉｔｙｏｆｄａｔａｔｒａｎｓｍｉｓｓｉｏｎｉｎｔｈｅｐｒｏｃｅｓｓＡｂｓｔｒａｃｔｏｆＲＦＩＤｄａｔａｃｏｍｍｕｎｉｃａｔｉｏｎｓｙｓｔｅｍ．Ｔｈｅｒｅａｒｅｔｗｏｋｉｎｄｓｏ

3、ｆａｎｔｉ－ｃｏｌｌｉｓｉｏｎａｌｇｏｒｉｔｈｍｓｔｏｓｏｌｖｅｔｈｉｓｐｒｏｂｌｅｍ：ｏｎｅｂａｓｅｄｏｎＡＬＯＨＡａｌｇｏｒｉｔｈｍａｎｄｔｈｅｏｔｈｅｒｓｂａｓｅｄｏｎｂｉｎａｒｙｓｅａｒｃｈａｌｇｏｒｉｔｈｍ．Ｔｈｉｓｐａｐｅｒｍａｉｎｌｙｓｔｕｄｉｅｓａｎｔｉ－ｃｏｌｌｉｓｉｏｎａｌｇｏｒｉｔｈｍｓｂａｓｅｄｏｎｂｉｎａｒｙｓｅａｒｃｈｉｎｄｅｔａｉｌ，ｉｎｃｕｌｄｉｎｇｂａｓｅｂｉｎａｒｙｓｅａｒｃｈ，ｄｙｎａｍｉｃｂｉｎａｒｙｓｅａｒｃｈａｎｄｒｅｇｒｅｓｓｉｖｅ－ｓｔｙｌｅｄｙｎａｍｉｃｂｉｎａｒｙｓｅａｒｃｈ，ｔｈｅｎａｔｌａｓｔｇｉｖｅｓｓｏｍｅａ

4、ｄｖｉｃｅｔｏｉｍｐｒｏｖｅｔｈｅａｌｇｏｒｉｔｈｍ．ＫｅｙＷｏｒｄｓＲＦＩＤ，ｔａｇａｎｔｉ－ｃｏｌｌｉｓｉｏｎ，ｂｉｎａｒｙｓｅａｒｃｈＣｌａｓｓＮｕｍｂｅｒＴＰ３０１．６ＲＦＩＤ技术简介基本概念ＲＦＩＤ技术是一种非接触的自动识别技术，其器模块和天线两个部分，有的阅读器将阅读器模块和天线集成在一个设备单元中，即所谓的集成式阅读器。１．２ＲＦＩＤ标签防碰撞ＲＦＩＤ的一个优点就是多个目标识别［８］。在ＲＦＩＤ系统工作是，在阅读器的作用范围内，可能会有多个标签同时存在，即产生标签碰撞。在这种形式的系统中，存在着两种基本的通信：由读写器到标签的通信；由标签到读写器的通信［

5、１］。从读写器到标签的通信，类似于无线电广播方式，多个接收机（标签）同时接收同一个发射机（读写器）发出的信息。这种通信方式也被称为“无线电广播”。１１．１基本原理是利用无线射频信号的空间耦合（电磁感应或电磁传播）的传输特性，实现对被识别对象的自动识别。ＲＦＩＤ系统一般由两个部分组成，即电子标签和阅读器［２］。在ＲＦＩＤ技术的实际应用［７］中，电子标签附着在被识别物体（表面或者内部）上，当带有电子标签的被识别物品通过阅读器的可识读区域时，阅读器自动以无接触的方式将电子标签中的约定识别信息取出，从而实现自动识别物品或自动收集物品标识信息的功能。阅读器本身可包括阅读＊收稿日

6、期：２０１０年１０月１４日，修回日期：２０１０年１１月１８日作者简介：江城，男，硕士研究生，研究方向：无线射频识别技术与应用。黄立波，男，博士，硕士生导师，高级工程师，研究方向：无线射频识别技术与应用。从标签到读写器的通信称为多路存取，即在阅读器的作用范围内有多个标签的数据同时传送给阅读器。无线电通信系统中，多路存取方法或者标签防碰撞问题的解决方式一般具有以下几种形式：空分多路（ＳｐａｃｅＤｉｖｉｓｉｏｎＭｕｌｔｉｐｌｅＡｃｃｅｓｓ，ＳＤＭＡ）法、时分多路（ＴｉｍｅＤｉｖｉｓｉｏｎＭｕｌｔｉｐｌｅＡｃｃｅｓｓ，ＴＤ－ＭＡ）法、频分多路（ＦｒｅｑｕｅｎｃｙＤｉｖｉｓｉｏ

7、ｎＭｕｌｔｉｐｌｅＡｃｃｅｓｓ，ＦＤＭＡ）法、码分多路（ＣｏｄｅＤｉｖｉｓｉｏｎＭｕｌ－ｔｉｐｌｅＡｃｃｅｓｓ，ＣＤＭＡ）法。·空分多路（ＳＤＭＡ）法是在分离的空间范围内进行多个目标识别的技术。ＳＤＭＡ法的缺点是复杂的天线系统和相当高的实施费用，因此采用这种技术的系统一般是在一些特殊的应用场合，如这种方法在大型的马拉松活动中就获得了成功。·频分多路（ＦＤＭＡ）法是把若干个使用不同载波频率的传输通路同时供通信用户使用的技术。ＦＤＭＡ法的一个缺点是阅读器的成本高，因为每个接收通路必须有自己的单独接收器供使用，射频标签的差异更为麻烦。因此，这种防碰撞方法也