rfid二进制搜索防碰撞算法的研究与改进

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

1、RFID二进制搜索防碰撞算法的研究与改进摘要RFID（电子射频标签）近几年在国内外受到关注的程度不断提高，越来越多的国家和企业都开始引进RFID技术作为其发展的一部分，作为RFID系统中的主要问题，防碰撞算法一直是系统设计中关注的重点，二进制搜索防碰撞算法是其中一重要分支，针对基本二进制搜索防碰撞算法重复低效的不足、动态二进制搜索防碰撞算法提出了改进，但效率仍无法突破N/2N-1，本文将提出一种新颖的改进算法，执行此算法的读取效率将提高到N/N-1。关键词RFID防碰撞二进制搜索1引言RFID(RadioFrequencyIdent

2、ification)是目前国际上热门的研究方向之一，常见的RFID系统由以下几部分组成（图1-1）：1、标签：由耦合元件及芯片组成，每个标签具有唯一的电子编码，附着在物体上标识目标对象。2、读写器：RFID系统的重要组成部分，通过读写器可读取或写入标签信息，读写器可设计为手持式或固定式；其与标签的通信通过天线(Antenna)对射频信号的传递完成。3、中间件[4]：位于后台网络和读写器终端之间的硬件设备和软件程序，配合读写器工作，获取并处理信息同时将处理后的信息传递给后台。4、后台网络：系统信息管理中心，负责对RFID系统识别，追踪

3、的信息进行管理和分析，同时负责对网络进行管理，确保网络正常运行。7图1-1RFID系统的运行流程图1-2RFID系统碰撞原理当RFID读写器发出读卡命令时，在有效区域内可能会存在多于一张以上的卡相应命令并反馈其卡号给读写器，这样的应答形式称为多路存取，多张卡的信号干扰导致读写器无法正确读取数据，这种情况称为碰撞（图1-2），针对碰撞所设计的算法成为防碰撞算法。防碰撞方法基本上分为四类：空分多路法(SDMA)、频分多路法(FDMA)、时分多路法(TDMA)和码分多路法(CDMA)。在RFID系统中，应用最广泛的是时分多路法(TDMA)

4、，其中ALHOA算法（及在其基础上加以改进的时隙ALOHA算法）[5][7]和二进制搜索防碰撞算法是目前最为流行的两种方式。本文以下部分将针对二进制搜索防碰撞算法进行详细讨论。2现有二进制搜索防碰撞算法及分析在通常的RFID系统中，人们习惯采用曼彻斯特(Manchester)编码（图2-1）方式以辨认出数据碰撞位的准确位置，在这种编码方式中，根据电平的改变(上升沿/下降沿)来表示编码某位为“0”或为“1”。在数据传输的过程中“没有变化”的状态将作为错误被识别。当两个或多个标签同时返回的某一数位有不同的值，则会发生上升沿和下降沿互相抵

5、消的现象，以致出现“没有变化”的状态，阅读器可由此判断该位出现了碰撞。tag1:10110010tag2:10101010reader:101??010（第四、五位产生碰撞）图2-1Manchester编码表现的碰撞形式7对于所有的二进制搜索防碰撞算法，均需定义以下几种操作：1、读卡请求操作call，其格式为call(code,m)：读写器向其覆盖范围内的所有卡发出读卡请求，若某张卡的卡号与call命令中的参数code前m位相同，则对读写器的请求作出回应。2、选择操作select：当读写器区分出某张卡时，需要对其进行select操作

6、以继续对卡中存储数据的操作。3、读/写数据操作，当对相应的卡进行select操作且卡回应后，读写器便可对卡中数据进行读取，某些读写器还具有修改卡中数据的功能。4、去选择操作sleep，当完成对某张卡的数据操作后，读写器需要对此卡进行sleep操作以去除其活性，这样在接下的一定时间内此卡将无法对读写器的任何call指令进行回应，以正确完成其他卡的读取。本文的算法分析将基于以下实例环境，假设在某个时刻有四张卡进入读写器范围，卡号分别为：EPC1=00101001；EPC2=10010110；EPC3=10110111；EPC4=1110

7、0010。2.1基本二进制搜索防碰撞算法基本二进制搜索防碰撞的想法非常简单：读写器最开始发送call(11111111,0)让其功能区域内所有卡做出反应，当检测到有碰撞时，将code碰撞的最高位置“0”，m加1以形成下一次call指令的参数，反复发送call指令直到某个时刻有唯一的卡做出回应，读写器对其进行selectà读写数据àsleep命令序列，随后重复上述过程，直到最后所有卡被识别。对实例的四张卡，基本二进制搜索防碰撞算法的流程如下：call回应nextcall认出卡号(11111111,0)1,2,3,4(01111111,

8、1)(01111111,1)1(11111111,0)EPC1:00101001(11111111,0)2,3,4(10111111,2)(10111111,2)2,3(10011111,3)(10011111,3)2(1111111