4.5.3 二进制数搜索算法

二进制树搜索算法yuanyc@njcit.cn基本思想是：当发生碰撞时，二叉树算法根据标签ID

或者随机产生的二进制“0”和“1”把标签集划分成两个子集。先查询子集0,若没有碰撞，则正确识别标签，

若仍有碰撞则分裂，把1子集分成00和01

两个子集，直到每个集合中只含有一个标

签，读写器就能识别作用范围内所有标签。110

11冲突节点100101非冲突节点二进制树型搜索算法O基于Aloha的算法比较简单，但是因为标签之间通过竞争来

获取信道资源，该方法有很大的随机性，不能完全防止标签碰撞，存在个别标签长时间不能被识别的严重缺陷，即“标签

饥饿”问题。※基于树的算法是一种确定性的防碰撞算法。读写器以查询时隙为基本处理单元，在一次查询中，读写器发送查询命令，

符合的标签返回响应。若响应的标签集包含多个标签则出现

碰撞，此时将标签划分为两个子集0和1,查询子集0,若没

有冲突则正确识别，若有冲突继续分裂成00和01两个子集，

依次类推，直至将子集0中标签识别完毕，再按此步骤查询子

集

1

。基于二进制树的标签防碰撞算法子集1子集11子集101子集100图7.2-6

二进制树示意图子集01

子集10子集00子集0树型搜索算法原理必基于树的算法是以查询时隙为基本处理单元去识别标签的。必在一次查询中，读写器发送查询命令给标签，符合应答条件的标签发送自身的ID

给读写器，读写器根据接收到的标签的信息来确定下一轮查询命令。必如果在一轮查询中，只有一个标签响应读写器，这个标签就能被正确识别。读写器发送查询命令，一个标签集响应读写器，如果响应的标签集中包含多个标签就会出现标签碰撞。※该算法有3个关键要素：※

a选用适当的基带编码方式(易于识别碰撞);※

b

标签序列号必须唯一；c设计一组有效的指令规则，高效、迅速地实现选卡。曼彻斯特编码检测碰撞位※在二进制搜索算法的实现中，利用标签ID序列号的唯一性划分标签子集，要求读写器所使用的信号编码必须能够确

定碰撞的准确比特位置。※曼彻斯特编码中，位中间存在跳变，向低电平跳变表示二进制1,向高电平跳变表示

二进制0,中间不发生跳变为错误编码。由此，曼彻斯特编码能够检测出数据中是否

有碰撞发生，可以按位识别出碰撞。基于二叉树的算法普遍使用曼彻斯特编码。射频卡1读写器译码??

??

??00射频卡2工00范例R:11111111送REQUEST

(11111111)

命令，要求区

域内所有标签应答，根据曼彻斯特编码，

解码数据为101??1?1,发生碰撞，算法做

下如下，将碰撞的最高置0,其它碰撞位

置1。得下次的REQUEST(10101111)A:

10

1

0011B:101

10101C:10101111

D:10111

101R:11111111??

?R表示阅

读器A:10100111C:1010111送REQUEST(10101111)

命令，标签A和C应答。解码数据为1010?111,发生碰撞，算法做下如下，将碰撞的最高置0,其它碰撞位置1。得10100111?R:10101111R:10101111R表示阅

读器R:10100111送REQUEST(10100111)

命令，只

有标签A应答。解码数据为1010?111,

没有发生碰撞，阅读器对标签A进行阅

读操作。A:10100111C:10101111R:10100111可以识别AR表示阅

读器第一次搜寻第二

寻次搜第三次搜

寻第四次搜寻第五次搜

寻发送序号111111110101111010011111111110101111接收序号10??1?11010?111识别TagA10??1?1TagA101001111010011110100111识别TagCTagB100101101010ITagC10101111101011111010111110101111TagD10111011011101二进制搜索树算法的实现步骤ImprovedAnti-collisionAlgorithm搜寻过程第六次搜寻第七次搜

寻第八次搜

寻第九次搜

寻第十次搜

寻发送序号11111111011010110111101接收序号101?101识别TagATagB101010110110101TagCTagDTagD101110110111101二进制搜索树算法的实现步骤ImprovedAnti-collisionAlgorithm搜寻过程识别TagB二进制搜索树算法的实现步骤二进制搜索算法的工作流程是：射频卡进入读写器的工作范围，读写器发出一个最大序列号让所有

射频卡响应；同一时刻开始传输它们的序列号到读写器的接收模块。读写器对比射频卡响应的序列号的相同位数上的数。把有不一致位的数从最高位到低位依次置0再输出系列号，

即依次排除序列号大的数，至读写器对比射频卡响应的序列号

的相同位数上的数完全一致时，说明无碰撞。选出序列号最小的数后，对该标签进行数据交换，然后使

该卡进入“无声”状态。即有的序列号该位

为0,而有的序列

号该位为1出现不一致的现象N(4)a、

若有一个以的标签发送，则重复步骤(2);b、若只有一个发送，则读写器发送包含识别码的“DATA_READ”,指令，标签正确接收此指令进入“数据交互”,通信完成后，发送SUCCESS指令；C、当标签没有被正确接收，则读写器将发送一个RESEND指令。(3)所有接收到FAIL指令且内部计数器不等于0的标签计数器加1。所有接收

到FAIL指令且内部计数器等于0的标签将产生一个1或者0的随机数，如果是1,则标签计数器加1,如果是0,则标签计数器保持不变，并再次发送其识别码。(2)当有一个以上的标签发送时，读写器因不能正确识别信号为发送FAIL指令。

(1)所有处于“识别”状态且内部计数器为0的应答器发送它们的识别码。

当进入“识别”有多个标签----碰撞仲裁当进入“识别”有多个标签----防碰撞指令规则(1)REQUEST——请求(序列号)。此命令发送一序列号作为

参数给射频卡。应答规则是，射频卡把自己的序列号与接收

到的序列号比较，如果自身序列号小于或等于REQUEST指令序

列号参数，则此射频卡回送其序列号给读写器。这样可以缩

小预选的射频卡的范围；如果大于，则不响应。(2)SELECT——

选择(序列号)。用某个(事先确定的)序列号

作为参数发送给射频卡。具有相同序列号的射频卡将以此作

为执行其他命令(例如读出和写入数据)的切入开关，即选择

这个射频卡。具有其他序列号的射频卡只对REQUEST命令应答。(4)UNSELECT——去选择。取消一个事先选中的射频卡，射频卡进入

"无声"状态，在这种状态下射频卡完全是非激活的，对收到的REQUEST命

令不作应答。为了重新话化射频卡，必须先将射频卡移出读写器的作用

范围再进入，以实行复位。(3)READ-DATA——读出数据。选中的射频卡将存储的数据

发送给读写器。3

当进入“识别”有多个标签----防碰撞指令规则读写器防碰撞技术※密集读写器环境是指RFID

系统应用中，在预定区域内部署多个RFID读写器，以满足对区域内

的所有标签进行完全的、高可靠的读取要求。系统网络中包含多个读写器和一个中央计算机，

读写器与中央计算机之间一般采用局域网(LAN)或无线局域网(WLAN)方式进行通信连接。※目前对RFID系统防冲突算法的研究主要是标签之间的防冲突算法，对读写器防冲突算法研究

不是很多，目前主要算法有图着色(Colorwave)算法、Q.Learning算法、Pulse算法等。读写器冲突图7-25读写器冲突的分类及算法解决方法读写器与读写器间干扰读写器与标签间干扰图着色

算法模拟

褪火遗传

算法神经

网络HIQ

算法读写器防碰撞技术※(1)图着色(Colorwave)算法※Colorwave

算法通过给读写器分配不同的颜色来避免读写器

之间的冲突，是基于TDMA的一种分布式算法。该算法规定

每个读写器从0到最大颜色数(maxColors)中随机选择一个颜

色(时隙)传输数据。如果发生了冲突，读写器选择一个新的

颜色，并且发送一个较小的控制包给它所有邻近的读写器，

告之它选择了一个新的颜色。如果邻近的读写器有同样的颜

色，它重新选择一个新的颜色并发送控制包。这样一直继续

下去。这种转换和驻留的动作就被称为kick

。每个读写器跟

踪当前的时隙颜色。必该算法需要所有读写器之间的时间同步，同时还要求所有的

读写器都可以检测RFID

系统中的冲突。然而，若标签不具有

冲突检测功能，需多个读写器联合检测在标签处发生的冲突。

另读写器移动将会重新分配时隙，重新分配的时隙传播整个

网络，将会导致整个系统的无效。*

(2)HIQ

算法必该算法是一个分等级的在线学习算法，通过

学习读写器冲突模型，动态的解决RFID

系统中读写器冲突问题，有效地分配频率给读写

器。其思想类似于无线传感器网络中分簇算法。※Q

学习算法中，读写器发送冲突消息给读写器

级服务器层(R

.Server)。然后单个的R-server分配资源给它的读写器，这样的方式可

使它们之间的相互通信不出现干扰。R.Server

通过Q学习服务器(Q.server)被分

配到频率和时隙。根Q.server

具有所有频率

和时隙资源的全部知识，并且能分配它们。Q.server

不像R.Server—样，没有单个读

写器问约束关系，这种关系通过该层下面的服务器之问的相互作用来推断

。冲突信息根

Q-ServerQ-Server

QServerR-ServerR-Server频率与时隙分配读写器图7-26Q学习算法多层结构读写器防碰撞技术读写器防碰撞技术※(3)Pulse

算法※该算法将通信信道分为控制

信道和数据信道两个部分。