基于二进制搜索的RFID标签防碰撞算法研究

　　1 RFID技术简介

　　1．1　基本概念

　　RFID技术是一种非接触的自动识别技术，其基本原理是利用无线射频信号的空间耦合(电磁感应或电磁传播)的传输特性，实现对被识别对象的自动识别。

　　RFID系统一般由两个部分组成，即电子标签和阅读器。在RFID技术的实际应用中，电子标签附着在被识别物体(表面或者内部)上，当带有电子标签的被识别物品通过阅读器的可识读区域时，阅读器自动以无接触的方式将电子标签中的约定识别信息取出，从而实现自动识别物品或自动收集物品标识信息的功能。阅读器本身可包括阅读器模块和天线两个部分，有的阅读器将阅读器模块和天线集成在一个设备单元中，即所谓的集成式阅读器。

　　1．2　RFID标签防碰撞

　　RFID的一个优点就是多个目标识别。在RFID系统工作是，在阅读器的作用范围内，可能会有多个标签同时存在，即产生标签碰撞。在这种形式的系统中，存在着两种基本的通信：由读写器到标签的通信；由标签到读写器的通信。

　　从读写器到标签的通信，类似于无线电广播方式，多个接收机(标签)同时接收同一个发射机(读写器)发出的信息。这种通信方式也被称为“无线电广播”。

　　从标签到读写器的通信称为多路存取，即在阅读器的作用范围内有多个标签的数据同时传送给阅读器。

　　无线电通信系统中，多路存取方法或者标签防碰撞问题的解决方式一般具有以下几种形式：空分多路(Space Division Multiple Access，SDMA)法、时分多路(Time Division Multiple Access，TD—MA)法、频分多路(Frequency Division MultipIe Access，FDMA)法、码分多路(Code Division Mul—tiple Access，CDMA)法。

　　空分多路(SDMA)法是在分离的空间范围内进行多个目标识别的技术。SDMA法的缺点是复杂的天线系统和相当高的实施费用，因此采用这种技术的系统一般是在一些特殊的应用场合，如这种方法在大型的马拉松活动中就获得了成功。

　　频分多路(FDMA)法是把若干个使用不同载波频率的传输通路同时供通信用户使用的技术。FDMA法的一个缺点是阅读器的成本高，因为每个接收通路必须有自己的单独接收器供使用，射频标签的差异更为麻烦。因此，这种防碰撞方法也限制在少数几个特殊的应用上。

　　时分多路(TDMA)法是个整个可供使用的通路容量按时间分配给多个用户的技术。TDMA法由于应用简单，容易实现大量标签的读写，所以一般的防碰撞算法主要以TDMA方式实现。对RFID系统来说，TDMA构成了防碰撞算法最大的一类。

　　最灵活的和应用最广泛的是“二进制搜索法”。对这种方法来说，为了从一组标签中选择其中之一，读写器发出一个请求命令，读写器通过合适的信号编码，能够确定发生碰撞的准确的比特位置，从而对电子标签返回的数据做出进一步的判断，发出另外的请求命令，最终确定读写器作用范围内的所有标签。本文对基于二进制搜索的算法做了详
细介绍，包括基本的二进制搜索算法。，动态二进制搜索算法和后退式动态二进制搜索算法。

　　2　基于二进制搜索的算法

　　2．1　基本的二进制搜索算法

　　实现“二进制搜索”算法系统的必要前提是能辨认出在阅读器中数据碰撞的比特的准确位置。为此，必须有合适的位编码法。首先要对NRZ编码和Manchester编码的碰撞状况做一个比较。选择ASK调制副载波的负载调制电感耦合系统作为标签应答器系统。基带编码中的“1”电平使副载波接通，“0”电平是副载波断开。

　　NRZ编码：某位之值是在一个位窗(bit window)内由传输通路的静态电平表示的。这种逻辑“1”编码为静态“高”电平，逻辑“o”编码为静态“低”电平。

　　Manchester编码：某位之值是在一个位窗内由电平的改变(上升／下降边)来表示的。这里，逻辑“o”编码为上升边，逻辑“1”编码为下降边。在数据传输过程中“没有变化”的状态是不允许的，并且作为错误被识别。

　　由两个(或多个)标签同时发送的数位有不同之值，则接收的上升边和下降边互相抵消，以致在整个位窗的持续时间内接收器接收到的是不间断的副载波信号。在Manchester编码中对这种状态未作规定。因此，这种状态将导致一种错误，从而用这种方法可以按位回溯跟踪碰撞的出现，如图1所示。

 图1　 NRZ编码和Manchester编码的碰撞情况

　　为了实现“二进制搜索”算法系统，就要选用Manchester编码。下面介绍算法系统本身：

　　“二进制搜索”算法系统是由一个阅读器和多个标签之间规定的相互作用(命令和应答)顺序(规则)构成的。目的在于从较大的一组中选出任一个标签。

　　为了实际实现这个算法系统，需要一组命令。这组命令能由标签应答器处理。此外，每个标签拥有一个唯一的序列号。为了举例说明，这里用8位的序列号；最多可使256个标签处于运行状态，这是为了保证序列号的唯一性。

{$page$}

　　REQUEST(SNR)：请求(序列号)。此命令发送一序列号作为参数给标签应答器。标签把自己的序列号与接受的序列号比较，如是小于或相等，则此应答器回送其序列号给阅读器。这样就可以缩小预选的标签范围。

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

　　READ—DATA：读出数据。选中的标签将存储的数据发送给阅读器(在实际的系统中，还有鉴别或写入、出纳登帐、取消预定等命令…)。

　　UNSELECT：去选择。取消一个事先选中的标签，标签进入“无声”状态，在这种状态中标签完全是非激活的，对收到的REQUEST命令不做应答。为了重新活化标签，必须暂时离开阅读器的作用范围(等于没有供应电压)以实行复位。

　　在“二进制搜索”算法系统中使用上述命令，现以四个在阅读器作用范围内的标签作演示说明。它们在00～FFh(等于十进制o～255，或者二进制00000000～11111111)的范围内具有唯一的序列号：

　　标签1：10110010；标签2：10100011；标签3：1011001l；标签4：11100011。

　　算法系统在重复操作的第一次中由阅读器发送REQUEST(≤11111111)命令。序列号为11111111b，在本例中的系统最大可能的8位序列号。阅读器作用范围内的所有标签的序列号都小于或等于11111111b，从而此命令被阅读器作用范围内的所有标签应答，如图2所示。

图2　二进制搜索算法选择一个标签的流程

　　对二进制树形搜索算法系统功能的可靠性起决定性作用的是所有标签需准确的同步，使这些标签准确的在同一时刻开始传输它们的序列号。只有这样，才能按位判定碰撞的发生。

　　在接收序列数的0位、4位和6位时，由于应答的标签在这些位的不同内容的重叠造成了碰撞。可以就阅读器作用范围内的两个或多个标签得出结论：在接收的序列号中出现了一次或多次碰撞。更仔细的观察表明：由于接收的位顺序为1XlX001X，从而可以得出所接收的序列号的八种可能性，如表所示。

　　第6位是最高值的位，在重复操作的第一次中此位上出现了碰撞。这意味着：不仅在序列号≥n000000b的范围内，而且在序列号≤10111111b的范围内至少各有一个标签存在。为了能选择到一个单独的标签，必须根据已有的了解限制下一次重复操作的搜索范围。可随意区分，例如，在≤10111111b的范围内进一步搜索。为此，将第6位
置“o”(有碰撞的最高值位)，仍将所有的低位置“1”，从而暂时对所有的低值位置之不理。

　　限制搜索范围形成的一般规则如下：

　　阅读器发命令REQUEST(≤10111111)后，所有满足此条件的标签都做出应答，并将它们自己的序列号传输给阅读器。本例中，这些标签是标签l、2和3，如图所示。现在接收的序列号的。位和4位上出现了碰撞(x)。可以由此得出结论：在第二次重复操作的搜索范围内至少还存在有两个标签。还需要进一步确定的序列号的四种可能性是从接
收的位顺序101X001X中得出的。

　　在第二次重复操作中仍然出现的碰撞要求在第三次重复操作中进一步限制搜索范围。使用表中形成的规则，把我们引向搜索范围≤10101111。于是，阅读器将命令REQUEST(≤10101111)发送给标签。这个条件只有由标签2(“10100011”)能满足，该标签即单独对命令作出应答。这样，终于发现了一个有效的序列号一另外的重复操作就不
需要了。

　　用SELECT命令，在所发现的标签地址选择了标签2，现在可以无干扰地撇开其他标签，由阅读器读出或写入了。所有其他标签处于静止状态，因为只有一个被选择的标签对READ—DATA命令做出应答。

　　在写入／读出动作完成后，用UNSELECT命令使标签2完全去活化，这样标签2对后继的请求命令不再作出应答。加入在阅读器作用范围内有许多标签“等待”着对它们的处理，可以用这种方法使一个单独的标签所必需的重复操作次数逐步减少。在本例中，可重复运用上述防碰撞算法自动选择至今未处理的标签1、3或4中的一个标签。

　　为了从较大量的标签中发现一个单独的标签，需要重复操作。其平均次数L取决于阅读器作用范围内的标签总数N，并且很容易得出：

　　如果只有唯一的一个标签处在阅读器作用范围内，那么只需要唯一的一次重复操作，以便发现标签的序列号一在这种情况下不出现碰撞。如果有一个以上的标签处在阅读器作用范围内，那么重复操作的平均数很快增加。

　　2．2　动态二进制搜索算法

　　上述的二进制搜索算法，不仅搜索的范围标准，而且标签的序列号总是一次次完整地传输的。然而，在实践中标签的序列号不像上例中那样仅由一个字节组成，而是按系统的规模可能长达10个字节，以致不得不传输大量的数据，而仅仅是选择一个单独的标签。如果我们更仔细地研究阅读器和单个标签之间的数据流，则立刻可以得出：

　　命令中(X一1)～o各位不包含标签的补充信息，因为(X一1)～o各位总是被置为“1”的。

　　标签应答的序列号的N～X各位不包含给阅读器的补充信息，因为N～X这些位是已知且给定的。

　　由此可见：传输的序列号的各自互补的部分是多余的，本来也是不必传输的。

　　由此引导我们很快使用一种最佳的算法：代替序列号在两个方向上完整地传输，序列号或搜索的范围标准的传输现在简单地改变为部分位(X)。

{$page$}

　　阅读器在REQUEST(请求)命令中只发送要搜索的序列号的已知部分(N～X)作为搜索的依据，然后中断传输。所有在(N～X)位中的序列号与搜索依据相符的标签，则传输的序列号的剩余各位即(X一1)位为应答。在REQUEST命令中的附加参数(有效位的编号)将下余各位的数量通知标签。

　　一种动态的二进制搜索算法的过程如图3所示，做了更详细的说明。标签都使用了同前例中相同的序列号。由于没有改动的使用了形成规则，所以重复操作的过程也与前例相同。然而，要传输的数据量和所需的时间减少可达50％。

　　2．3　后退式动态二进制搜索算法

　　仔细观察发现，动态二进制搜索算法的策略是不断缩小搜索的范围来一步步识别标签。在基本的动态二进制搜索算法中，当查询到第一个标签后，阅读器重新发送REQUEST(≤11111111)指令，搜索又从最初的大范围开始。如果采用后退策略，当识别到第一个标签后，下一个查询指令的序列号参数为上一查询指令的序列号值，则本次查询的范围大大减小，可以很快识别到下一个标签，如此递归下去，从而可以大大减少识别所有标签的搜索总次数。

　　后退式动态二进制搜索算法是目前最高效的算法，识别N个标签的总查询次数只需要2N一1，而且用阅读器记录发送指令不需要标签有记忆功能，对标签的要求低。

　　2．4　算法改进的一些思路

　　在后退式动态二进制搜索算法的基础上，提出了两点改进思路：阅读器碰撞检测时，增加一位碰撞位的特殊处理；阅读器发送查询指令时，不必发送所有的前缀，只发送标识碰撞位的二进制代码。

　　当阅读器检查碰撞位的情况时，如果发现只有一位碰撞位，可以立即识别两个标签ID号，而没必要继续进行搜索，因此，增加一位碰撞位的特殊处理可以大大减少搜索的总次数。

　　当标签的序列号很短时，后退式动态二进制搜索算法不会对传输时间造成很大的影响，但当标签的序列号很长时，如64bit，128bit等时，阅读器每次发送的查询指令位数将很多，就会较大地影响传输效率。以64位标签为例，如果碰撞位发生在第30位，则进行一次查询就要发送34位序列号来标识碰撞位。如果直接用一组短的数据包来标识发生碰撞的位置，则可以大大减少发送的数据量，例如，把碰撞位的信息用其二进制代码表示，则对一个长度为N的序列，只需一个109zN位的序列即可表示所有可能的碰撞位。对于16位的序列号只需要4位数据即可表示，对于64位的序列号则只需6位。如：假设解码出的数据为1100lx01，碰撞位为D2，则可用2的二进制数10来表示该信息，
而不必传输1100lo。标签应答时，则发送该碰撞位以后的序列号。这样，当标签序列号较长时，就可以极大地减少数据传输时间，从而提高算法的效率。

　　这两点思路从理论上可以提高二进制搜索算法的效率，但实现中增加了电路设计的复杂性，有待实践中进一步验证研究。

　　3　结语

　　文中介绍了三种基于二进制搜索的算法，包括基本的二进制搜索算法，动态二进制搜索算法和基于后退式的动态二进制搜索算法，并在此基础上，提出了算法的一些改进思路。通过增加一位碰撞位的特殊处理，可以有效的减少阅读器搜索的次数；阅读器发送查询指令时，只发送标识碰撞位的二进制代码，可以减少数据传输量，从而可以提高算法的效率。但这些改进思路必然增加了电路设计的复杂性，有待实践中进一步研究，使二进制搜索算法更好的应用于实际。