基于二进制搜索的rfid的防碰撞算法提升

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

1、基于二进制搜索的RFID的防碰撞算法提升　摘要：针对RFID系统的碰撞问题，通过对基本的二进制搜索算法的研究，对二进制算法进行了提升改进，减少了RFID系统的数据冗余；提高了运算速度。　　关键词：RFID防碰撞二进制　　　　RFID是上世纪末兴起的一种非接触式的自动识别技术，系统一般由电子标签和阅读器组成。在通常的工作环境下，有许多标签在阅读器的识别范围内，这些标签同时向阅读器发送信息时就产生信道争抢，信号会相互干扰也就是说产生了碰撞。因此，研究防碰撞技术来识别多个目标，保证精度的条件来提高速度具有重大现实意义。　　1、基本的二进制搜索算法　　二进制搜索算法实现的必要前提是能

2、够准确的对阅读器中数据碰撞的比特位置。因此，要采用合理的编码方法，目前一般采用Manchester编码，在这种编码中的某个位置的值是由在一个位窗内的电平升降表示的：逻辑数字0表示上升边；1表示下降边；无状态变化认为是错误被识别。为了更好的说明现取两个标签：ID1:11001001,ID2:01011011,利用Manchester编码识别出的碰撞位示意图如图一所示。两个标签是同时传输，利用Manchester编码阅读器解码为X10X10X1，检测出碰撞位为第一、第四、第七比特位。　　图一　　现举例说明BS算法的过程：　　现工作区域内由四个标签：IDl：11001101；ID2

3、：11011l11；ID3：11011l11；ID4：11010111。读写器发送请求命令，对4个标签识别过程如下：　　（1）读写器发送Request(11111111)命令，工作区域内的四个标签都做出反应。根据Manchester编码，序列号的第1、3、4比特位碰撞。碰撞最高位为4，读写器将位4置0，高于位4的位不变，低于位4的位设置为l，则下一次发送的命令参数为110011l1。　　（2）读写器发送Request(11001111)命令，ID1和ID3应答，第3位发生碰撞。将位3位置0，低于位3的位置1，命令参数为1100011l。　　（3）读写器发送Request(11

4、000111)命令，ID3应答，无碰撞，对ID3进行读写操作并执行Unselect命令，ID3进入无应答状态，算法采用后退策略，命令参数为11001ll1。　　（4）读写器发送Request(11001111)命令，ID1应答，无碰撞，读写器对ID1处理并执行Unseleet命令，ID1进入无应答状态，算法采用后退策略，得到下一次Request命令参数l11111l1。　　（5)读写器发送Request(11111111)命令，ID4和ID2应答，位3位发生碰撞。将位3位置0，低于位3的位置1，得到命令参数ll0l0lll。　　（6）读写器发送Request(11010111

5、)命令，只有ID4应答，无碰撞，读写器ID4做相应处理并执行Unselect命令，ID4进入无应答状态，算法后退，得到下一次Request命令参数11111111。　　（7）写器发送Request(1111lll1)命令，ID2应答，无碰撞，对ID2处理，识别过程完成。　　从以上实例可以看出，在读写器范围内有X个待识别标签，识别一个标签需要的搜索次数I=log2X+1,识别X个标签搜索次数平均为I(bs)=X+log2X　　2、二进制搜索算法提升　　2.1算法分析　　BS法中，每次都必须发送完整的ID序列号，在实际中序列号往往很长，这样每次会有大量数据冗余，降低了计算速度。在

6、改进算法中我们要尽量减少数据冗余和提高计算速度。　　减少冗余：在读写器发送请求指令后，找到最高碰撞位，我们只需把最高碰撞位以下的位数就行传送，比它高的位数就压缩存入堆栈。　　提高运算速度：数据冗余减少后可以相应的提高运算速度，但这样还是不够，我们可以在标签制作的时候预先植入该卡片序列号所具有的1或者0个数为M。这样在搜索过程中就会节约运算时间。　　2.2算法描述：首先要更改Request（N）命令，N为最高碰撞位，具体流程如下：　　（1）读写器发送（N），读写器工作范围内的所有标签应答，读写器识别出最高碰撞位M，将M置0，并将其一起存入堆栈，得到下一环节的Request（M）

7、指令。　　（2）读写器发送Request（M）指令，首先判断碰撞位是否只有两个，如果只有两个碰撞位，读写器停止工作，直接识别该两个标签，并使其进入休眠状态。如果碰撞位大于2就继续（1）步骤，得到下一环节的Request（X）指令。　　（3）继续步骤（2），直至检测出所有标签。　　2.3算法的实例分析：取四个八位标签，ID1:11000001，ID2:11001001，ID3:11000101,ID4:11101010.具体是被过程如下：　　（1）读写器发送Request(11111111)，四个标签全部