4.5.3 二进制数搜索算法

二进制树搜索算法二进制树型搜索算法基本思想是：当发生碰撞时，二叉树算法根据标签ID或者随机产生的二进制“0”和“1”把标签集划分成两个子集。先查询子集0，若没有碰撞，则正确识别标签，若仍有碰撞则分裂，把1子集分成00和01两个子集，直到每个集合中只含有一个标签，读写器就能识别作用范围内所有标签。基于二进制树的标签防碰撞算法基于Aloha的算法比较简单，但是因为标签之间通过竞争来获取信道资源，该方法有很大的随机性，不能完全防止标签碰撞，存在个别标签长时间不能被识别的严重缺陷，即“标签饥饿”问题。基于树的算法是一种确定性的防碰撞算法。读写器以查询时隙为基本处理单元，在一次查询中，读写器发送查询命令，符合的标签返回响应。若响应的标签集包含多个标签则出现碰撞，此时将标签划分为两个子集0和1，查询子集0，若没有冲突则正确识别，若有冲突继续分裂成00和01两个子集，依次类推，直至将子集0中标签识别完毕，再按此步骤查询子集1。树型搜索算法原理基于树的算法是以查询时隙为基本处理单元去识别标签的。在一次查询中，读写器发送查询命令给标签，符合应答条件的标签发送自身的ID给读写器，读写器根据接收到的标签的信息来确定下一轮查询命令。如果在一轮查询中，只有一个标签响应读写器，这个标签就能被正确识别。读写器发送查询命令，一个标签集响应读写器，如果响应的标签集中包含多个标签就会出现标签碰撞。该算法有3个关键要素：

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

b标签序列号必须唯一；

c设计一组有效的指令规则，高效、迅速地实现选卡。101100001110??????射频卡1射频卡2读写器译码曼彻斯特编码检测碰撞位

在二进制搜索算法的实现中，利用标签ID序列号的唯一性划分标签子集，要求读写器所使用的信号编码必须能够确定碰撞的准确比特位置。曼彻斯特编码中，位中间存在跳变，向低电平跳变表示二进制1，向高电平跳变表示二进制0，中间不发生跳变为错误编码。由此，曼彻斯特编码能够检测出数据中是否有碰撞发生，可以按位识别出碰撞。基于二叉树的算法普遍使用曼彻斯特编码。范例A:10100111B:10110101C:10101111D:10111101R:11111111R:11111111送REQUEST（11111111）命令，要求区域内所有标签应答，根据曼彻斯特编码，解码数据为101??1?1,发生碰撞，算法做下如下，将碰撞的最高置0，其它碰撞位置1。得下次的REQUEST(10101111)???R表示阅读器二进制搜索树算法的实现步骤A:10100111C:10101111R:10101111R:10101111

送REQUEST（10101111）命令，标签A和C应答。解码数据为1010?111,发生碰撞，算法做下如下，将碰撞的最高置0，其它碰撞位置1。得10100111?R表示阅读器二进制搜索树算法的实现步骤A:10100111C:10101111R:10100111R:10100111

送REQUEST（10100111）命令，只有标签A应答。解码数据为1010?111,没有发生碰撞，阅读器对标签A进行阅读操作。R表示阅读器可以识别A二进制搜索树算法的实现步骤ImprovedAnti-collisionAlgorithm搜寻过程二进制搜索树算法的实现步骤第一次搜寻第二次搜寻第三次搜寻第四次搜寻第五次搜寻发送序号接收序号TagATagBTagCTagD1010011110110101101011111011110111111111101??1?11010111110100111101011111010?1111010011110100111识别TagA10110101101011111011110111111111101??1?11010111110101111识别TagCImprovedAnti-collisionAlgorithm搜寻过程二进制搜索树算法的实现步骤第六次搜寻第七次搜寻第八次搜寻第九次搜寻第十次搜寻发送序号接收序号TagATagBTagC

TagD1011010110111101111111111011?10110110101101101011011110110111101识别TagB识别TagD

射频卡进入读写器的工作范围，读写器发出一个最大序列号让所有射频卡响应；同一时刻开始传输它们的序列号到读写器的接收模块。

读写器对比射频卡响应的序列号的相同位数上的数。出现不一致的现象即有的序列号该位为0，而有的序列号该位为1

把有不一致位的数从最高位到低位依次置O再输出系列号，即依次排除序列号大的数，至读写器对比射频卡响应的序列号的相同位数上的数完全一致时，说明无碰撞。选出序列号最小的数后，对该标签进行数据交换，然后使该卡进入“无声”状态。YN二进制搜索算法的工作流程是：二进制搜索树算法的实现步骤（1）所有处于“识别”状态且内部计数器为0的应答器发送它们的识别码。（2）当有一个以上的标签发送时，读写器因不能正确识别信号为发送FAIL指令。（3）所有接收到FAIL指令且内部计数器不等于0的标签计数器加1。所有接收到FAIL指令且内部计数器等于0的标签将产生一个1或者0的随机数，如果是1，则标签计数器加1，如果是0，则标签计数器保持不变，并再次发送其识别码。1当进入“识别”有多个标签----碰撞仲裁

防碰撞机制的实现

所有接收到FAIL指令且内部计数器不等于0的标签计数器加1。所有接收到FAIL指令且内部计数器等0的标签将产生一个1或者0的随机数，如果是1，则标签计数器加1，如果是0，则标签计数器保持不变，并再次发送其识别码。（4）a、若有一个以的标签发送，则重复步骤（2）;b、若只有一个发送，则读写器发送包含识别码的“DATA_READ”，指令，标签正确接收此指令进入“数据交互”，通信完成后，发送SUCCESS指令；C、当标签没有被正确接收，则读写器将发送一个RESEND指令。（1）REQUEST——请求(序列号)。此命令发送一序列号作为参数给射频卡。应答规则是，射频卡把自己的序列号与接收到的序列号比较，如果自身序列号小于或等于REQUEST指令序列号参数，则此射频卡回送其序列号给读写器。这样可以缩小预选的射频卡的范围；如果大于，则不响应。2当进入“识别”有多个标签----防碰撞指令规则

所有接收到FAIL指令且内部计数器不等于0的标签计数器加1。所有接收到FAIL指令且内部计数器等0的标签将产生一个1或者0的随机数，如果是1，则标签计数器加1，如果是0，则标签计数器保持不变，并再次发送其识别码。

(2)SELECT——选择(序列号)。用某个(事先确定的)序列号作为参数发送给射频卡。具有相同序列号的射频卡将以此作为执行其他命令(例如读出和写入数据)的切入开关，即选择这个射频卡。具有其他序列号的射频卡只对REQUEST命令应答。

防碰撞机制的实现（3）READ-DATA——读出数据。选中的射频卡将存储的数据发送给读写器。

3当进入“识别”有多个标签----防碰撞指令规则

(4)UNSELECT

——去选择。取消一个事先选中的射频卡，射频卡进入"无声"状态，在这种状态下射频卡完全是非激活的，对收到的REQUEST命令不作应答。为了重新话化射频卡，必须先将射频卡移出读写器的作用范围再进入，以实行复位。

防碰撞机制的实现读写器防碰撞技术密集读写器环境是指RFID系统应用中，在预定区域内部署多个RFID读写器，以满足对区域内的所有标签进行完全的、高可靠的读取要求。系统网络中包含多个读写器和一个中央计算机，读写器与中央计算机之间一般采用局域网（LAN）或无线局域网（WLAN）方式进行通信连接。目前对RFID系统防冲突算法的研究主要是标签之间的防冲突算法，对读写器防冲突算法研究不是很多，目前主要算法有图着色（Colorwave）算法、Q．Learning算法、Pulse算法等。读写器防碰撞技术(1)图着色(Colorwave)算法Colorwave算法通过给读写器分配不同的颜色来避免读写器之间的冲突，是基于TDMA的一种分布式算法。该算法规定每个读写器从0到最大颜色数(maxColors)中随机选择一个颜色(时隙)传输数据。如果发生了冲突，读写器选择一个新的颜色，并且发送一个较小的控制包给它所有邻近的读写器，告之它选择了一个新的颜色。如果邻近的读写器有同样的颜色，它重新选择一个新的颜色并发送控制包。这样一直继续下去。这种转换和驻留的动作就被称为kick。每个读写器跟踪当前的时隙颜色。该算法需要所有读写器之间的时间同步，同时还要求所有的读写器都可以检测RFID系统中的冲突。然而，若标签不具有冲突检测功能，需多个读写器联合检测在标签处发生的冲突。另读写器移动将会重新分配时隙，重新分配的时隙传播整个网络，将会导致整个系统的无效。读写器防碰撞技术(2)HIQ算法该算法是一个分等级的在线学习算法，通过学习读写器冲突模型，动态的解决RFID系统中读写器冲突问题，有效地分配频率给读写器。其思想类似于无线传感器网络中分簇算法。Q学习算法中，读写器发送冲突消息给读写器级服务器层(R．Server)。然后单个的R-server分配资源给它的读写器，这样的方式可使它们之间的相互通信不出现干扰。R．Server通过Q学习服务器(Q．server)被分配到频率和时隙。根Q．server具有所有频率和时隙资源的全部知识，并且能分配它们。Q