《一种新颖快速的二进制搜索防碰撞算法》由会员分享，可在线阅读，更多相关《一种新颖快速的二进制搜索防碰撞算法（3页珍藏版）》请在金锄头文库上搜索。
1、解 决 方 案Presentation Solution26 2 0 0 8 年第3 期1 概述射频识别 （R F I D ） 技术是一种方便、 快速的非接触式自动识别技术，它通过射频信号自动识别目标对象，获取相关数据，无需光学可视即可完成对信息的输入和处理。现已广泛应用于工业自动化、商业自动化、交通运输控制管理、产品证件防伪、防盗等众多领域。 R F I D 系统主要包括阅读器 （r e a d e r ） 、 标签 （t a g ）和计算机三部分。如果阅读器的作用范围内存在多个标签，当有两个或两个以上的标签同时返回信息给阅读器时，就会引起信号冲突，使阅读器不能正确识别标签，这种现象称为标签
2、冲突或碰撞 （c o l l i s i o n ） 。 解决冲突的算法称为防碰撞算法。 防碰撞算法对于系统运行的速度和可靠性有着非常大的影响，是R F I D关键技术之一。在现有的R F I D 系统中，防碰撞算法主要包括频分多路（F D M A ） 、空分多路（S D M A ）和时分多路（T D M A ）三大类。 其中， 时分多路算法在I S O 标准中占主导地位， 它包括A L O H A算法和二进制树等防碰撞算法 1 。本文提出了一种二进制搜索防碰撞快速新算法。该算法在充分利用二进制算法优点的基础上，通过引入一种新颖的查询循环来提高二进制搜索防碰撞算法的效率。 该算法可以减少R F
3、 I D系统的查询次数，提高R F I D 系统的识别效率，系统的识别效率一种新颖快速的二进制搜索防碰撞算法许武忠 胡斌杰 （华南理工大学电子与信息学院）摘 要：本文讨论了R F I D系统中能同时识别多个标签的防碰撞算法，分析了A L O H A 和二进制树两类防碰撞算法的特点，提出了一种新颖快速的二进制搜索防碰撞算法。该防碰撞算法不仅具有二进制树算法的优点，而且能通过查询循环来获取所有的标签前缀，减少查询次数。分析和仿真结果表明，该防碰撞算法系统识别效率最高可达8 3 . 0 ，远高于系统识别效率为5 0 的跳跃式二进制算法( J D S ) 和系统识别效率为4 3 . 0 的前缀查询树算
4、法( P R Q T ) 。关键词：R F I D 、防碰撞算法、A L O H A 、二进制树A New Rapid Binary Search Anti- Collision AlgorithmXu Wu Zhong Hu Bin Jie (South China University of Technology, Institute of Electronics and Information) Abstract: This article describes an anti-collision algorithm to prevent collision in the RFID sys
5、tem when reading multiple tags. The article also analyses the characteristics of two anti-collision algorithm, ALOHA and Binary Tree, and propose a new Rapid Anti-collision binary search algorithm. The new anti-collision algorithm not only has the advantages of the binary tree algorithm, it is also
6、able to obtain all of the label prefix by cycling through and enquiring all the labels, reducing the amount of enquiring cycles. Analysis and simulation results show that the new anti-collision algorithm identification system has an efficiency of as high as 83.0%, which is a much better than the Jum
7、ping Binary Algorithm (JDS) and the Prefix Questioning Tree Algorithm (PRQT), which only have an efficiency of 50%.and 43.0% respectively. Keywords: RFID, Anti-Collision Algorithm, ALOHA, Binary Tree最高可达8 3 . 0 。2 时分多路防碰撞算法2 . 1 A L O H A 算法A L O H A 算法属于不确定算法，该算法中标签利用随机时间响应读写器的命令。此类算法主要有A L O H A 算
8、法、时隙A L O H A算法、帧时隙A L O H A 算法、动态帧时隙A L O H A 算法等。其中，系统识别效率最高的是动态帧时隙 A L O H A算法。动态帧时隙A L O H A 算法执行过程如下： ( 1 ) 阅读器估算在作用范围内未识别标签的数量， 以此决定下一帧的时隙数量N 并对未被识别标签进行分组； ( 2 ) 阅读器发送N 个时隙的帧，标签随机选择其中的一个时隙返回数据包，而此次执行中被识别的标签将不再返回数据包。阅读器重复执行( 1 ) 、 ( 2 ) 操作，直至识别完所有标签。该算法的系统识别效率可保持在3 4 . 6 和3 6 . 8 之间。在A L O H A算
9、法中，虽然系统设计比较简单，但是这种算法存在无法识别某个或某些标签的可能，即错误判决无法消除 2 。 2 . 2 二进制树算法二进制树算法的系统识别效率比较高，不存在错误判决，但系统的设计比较复杂。其基本思想是将处于冲突的标签分成左右解 决 方 案Presentation Solution2 0 0 8 年第3 期 272 个子集0 和1 ，先查询子集0 ，若没有冲突，则正确识别标签，若仍有冲突则再分裂， 把子集0 分成0 0 和0 1 两个子集， 依次类推，直到识别出子集0 中的所有标签，再按此步骤查询子集1 。一次查询中实现阅读器发送请求和标签响应阅读器请求并返回数据的过程。二进制树算法主
10、要有随机二进制树算法、查询树算法、前缀查询树算法、二进制搜索算法、跳跃式动态树型算法等。其中，系统效率较高的是前缀查询树算法和跳跃式动态树型算法。2 . 2 . 1 前缀查询树算法在查询树( Q T ) 3 算法中， 阅读器每次查询发送一个比特前缀S 。在阅读器中，设置一个前缀队列Q ，存储需要查询的前缀。只有当标签I D 前缀与这个查询前缀相符时，标签才响应并返回自己的I D 。当只有一个标签响应时，阅读器识别该标签；当有多个标签响应就发生冲突，此时阅读器将S 0 和S 1 插入Q 的队尾；当没有标签响应时，阅读器不执行任何操作。阅读器每次查询结束后，从Q 的队头中取出一个前缀以供下次查询。
11、当队列Q 为空时，阅读器识别完所有标签，算法执行结束。前缀查询树算法( P R Q T ) 4 是在上述查询树算法基础上提出的一种改进算法，它根据标签数确定最优的初始请求前缀长度，由此得到查询树算法中的比特前缀S ；对于每个比特前缀S ， 按照查询树算法识别标签。前缀查询树算法的系统识别效率约为4 3 。2 . 2 . 2 跳跃式动态树形算法二进制搜索算法( B S ) 需要采用合适的编码方法， 来辨认出标签返回数据中冲突位的具体位置。 通常采用M a n c h e s t e r 编码 1 。在这种算法中， 阅读器根据标签返回数据的第一个冲突位来确定哪些标签需要响应：从高位算起， 标签I
12、D 第一个冲突位k 的数据为0 的标签响应并返回整个标签I D ，而冲突位为1 的则进入“无声”状态。当识别完一个标签后，上次处于“无声”状态的标签才能在下一次识别中响应阅读器的请求。阅读器请求码格式：请求码长度与I D 长度相同，第k 位之前的数据保持不变，第k 位置0 ，第k 位后置1 。也就是说，只有I D 小于或等于请求码的标签才能响应。执行每次请求后，返回数据中的冲突位数越来越少。当返回数据中没有发生冲突时，阅读器识别一个标签。阅读器重复执行前面所述操作，当识别完所有标签时，算法结束。跳跃式动态树形算法( J D S ) 5 是在上述二进制搜索算法的基础上改进的一种算法。这种算法采用
13、前缀发送请求命令，标签I D与请求命令中的前缀相同的返回I D 剩余比特位数。 另外， 这种算法在阅读器中用堆栈存储识别过程中的请求命令中的前缀，在某次请求识别一个标签后（不存储这个前缀） ，弹出栈顶的一个前缀，继续发送请求命令，直至识别所有标签。用跳跃式动态树形算法识别n 个标签，所需的总请求数为2 n 1 ，系统识别效率达到 5 0 % 。3 新颖快速的二进制搜索防碰撞算法3 . 1 查询循环本节先解释新颖快速的二进制搜索防碰撞算法( N F B S ) 中采用的两种查询循环。假设在阅读器作用范围内有n 个标签，每个标签识别码( I D ) 长度为L 。 则设标签的I D 为q L - 1
14、 q 1 q 0 ， 其中， q L -1 , , q 1 , q 0 的每位取0 或者取1 。 R e q 表示阅读器向标签发送请求。查询循环：R e q ( q L - 1 q k + 1 q k ) ，阅读器发出带有前缀q L - 1 q k + 1 q k ( 0 k L - 1 ) 的请求，标签检察自身I D 的前L -k 位是否与阅读器发出的前缀相同， 若是则返回识别码的剩余位q k - 1 q 1 q 0 ，若不是则不回应。查询循环：R e q q L - 1 q 1 q 0 ， 阅读器向标签发送请求的碰撞位位置，若第i ( 0 i L - 1 ) 位是所要请求的碰撞位位置，q
15、i 1 ， 否则q i 0 。 假定阅读器请求的碰撞位长度为l ， 由此得到标签返回的二进制数的长度N = 2 l ， 标签返回 q N - 1 q 1 q 0 。 其中，标签根据阅读器发送的请求碰撞位位置，从自身识别码I D中获取相应位置上的l 位二进制数， 并转化为十进制数j ( 0 jN - 1 ) ，则取q j = 1 ，而其余N 1 位均为0 。如果阅读器要获取碰撞位长度为 l的请求前缀 q L - 1 q k + 1 q k ，就需要知道l 个碰撞位有哪些值。执行查询循环，接收返回数据q N - 1 q 1 q 0 ：若q j ( 0 j N - 1 ) 发生碰撞，将j 转化为l
16、位二进制码，可获取请求前缀。 3 . 2 算法描述该防碰撞算法包括以下步骤： （1 ） 阅读器初始化系统， 所有标签都处于活动状态； （2 ） 阅读器发出R e q ( n u l l ) 请求， 所有标签返回整个I D ； （3 ）根据标签的个数n 和识别码长度L ，阅读器确定请求碰撞位长度l ，执行查询循环，获取请求前缀并压入堆栈S 中； （4 ）阅读器从堆栈S 中弹出一个请求前缀，并执行查询循环：如果没有发生碰撞，则可以识别一个标签。如果发生碰撞，返回步骤（3 ） 。当S 为空时，识别所有标签，算法执行结束。图1 和图2 给出了一个识别五个标签的实例， 标签I D 分别为0 0 1 1 1 0 1 0 、01001011 、10000101 、1 0 0 1 1 0 0 1 和1 0 0 1 1 1 0 0 。 图2 中，X表示在相应位上发生碰撞。图2 阅读器与标签通信图1 识别五个标签1 2
