随着RFID技术在物联网中的大量应用，大量标签进入阅读器的识别范围，阅读器应能准确及时地识别出所有标签。但是同一RFID系统中所有的标签工作在相同的频率，同一时刻多个标签从阅读器获得能量并向阅读器发送信息，这时就会出现相互干扰，使阅读器不能正确识别标签，称为标签冲突。为此出现了防冲突协议，以解决识别过程中多个标签的信道共享和访问冲突的问题。在无源电子标签系统中，存在着如下约束：标签自身不能提供电能，需要阅读器在通信时为它提供能量；识读范围内的标签总数未知，标签间不能通信；标签的内存和计算能力有限。因此，理想的防冲突协议应当具有如下特点：(1)标签端电路简单；(2)最小的识别时延，阅读器与标签的通信数据量应尽可能少，识别时间应尽可能短；(3)识别过程中电能消耗尽可能少，否则可能因电能不足而不能完成识别;(4)识别率应能达到100%，即处于识别范围内的所有标签都能全部正确识别[1]。
    现有的各种防冲突协议可以分为两类：随机性协议和确定性协议[2]。随机性协议发生冲突时标签延迟一个随机时间后响应阅读器，目前形成了以 Aloha为基础的随机性协议簇，如纯 Aloha、时隙Aloha、帧时隙Aloha。确定性协议中，阅读器不断发送要查询的标签ID的前缀，与前缀匹配的标签响应阅读器，阅读器根据检测到冲突信息，将待识别的标签进行分组，在组内重复进行上述查询过程（识别修正下次发送的查询前缀），直至识别出一个标签。对每一组内所有标签进行识别，阅读器范围内的所有标签都被识别。确定性协议按照识别过程中标签是否需要内存储器可以分为内存协议和无内存协议，目前形成了以二进制树搜索协议为基础的系列协议，如位仲裁搜索（BA）、查询树搜索（Q-tree）、基本二进制搜索（BS）、动态二进制搜索（DBS）、自适应二进制搜索（ABS）[1]、具有后退索引的二进制搜索(BDBS)[2]及其他改进协议[3-5]。随机性协议比确定性协议识别速度快，但存在不稳定工作区间, 理论吞吐量被限制在 1/e以内，会导致“标签饥饿问题”, 即特定的标签可能会在很长一段时间内都无法被正确识别。确定性协议能提供100%的识别成功率，因而得到了广泛的应用。
    本文提出了一种时间优先级分组二进制树搜索协议TGBS(Time-based Grouping  Binary Splitting)，该协议以确定性协议为基础，首先根据进入阅读器识别范围内的时间长短将范围内的标签进行分组，然后再利用动态二进制树搜索协议对组内标签进行识别。该协议对先进入阅读器范围内的标签先识别，符合先来先服务的思想。同时由于将众多标签先按时间分组，降低了各组内标签的冲突概率，缩短了识别时间。该协议实现简单，标签端开销小，仅需要在每个标签中设定一个时间计数器（分组计数器）。
1 二进制树搜索协议
     基于二进制树的防冲突协议必须解决好以下三个问题:(1)冲突检测方法，确定通信信道处于何种状态（空闲、冲突、使用）。目前普遍采用曼彻斯特编码来检测冲突。(2)以何种策略来搜索树。目前有确定地址法和随机地址法。确定地址法以ID中的每一位（0或1）决定是搜索左子树还是右子树，具有吞吐率高，搜索树深度确定的优点，在二进制树搜索协议中得到广泛使用。(3)在一个冲突解决期CRI(Conflict Resolution in-Interval)内到达的新标签, 应以何种策略决定是否参与信道的竞争。可分为阻塞型信道访问策略和自由信道访问策略。前者要求在CRI内到达的新标签不能加入到当前CRI中, 直到当前CRI结束, 然后加入下一次CRI的信道竞争; 后者则是任何新到达的标签都被加入到当前CRI竞争中。一般情形下，在二进制搜索协议中均假定RFID冲突解决过程有比较明显的间歇性和突发性。如超市自动结帐系统、出入库管理系统等每隔一段时间就会有一批数据集中到达, 在短时间内, 阅读器必须读出所有的数据,然后阅读器停止工作等待下一批数据的到达。因此可以假定“RFID系统在一个CRI内不会有新的标签到达”[6]。在上述前提下，出现了基本二进制搜索、动态二进制搜索、自适应二进制搜索等典型算法及其他改进算法[7]。下面的分析中假定标签ID的长度为N，有M个标签待识别。
1.1 基本二进制搜索算法
    基本二进制搜索算法中，阅读器发送一长度为N的查询序列号，各个标签将自身的ID与接收的序列号比较，其值小于或等于查询序列号的标签返回其ID。阅读器检测信道的冲突情况，按确定地址法先后选择进入左子树和右子树，修正发出的查询序列号，重复冲突检测过程，直至识别出一个标签（到达叶结点），然后将其去激活（不再响应阅读器命令）。重复上述过程，直到完成所有标签的识别（树搜索）。
    完成所有标签的识别过程主要由阅读器发出查询命令的次数、发送命令参数的长度及标签响应数据的长度决定。在基本二进制树搜索协议中，阅读器在发送的序列号和标签返回的序列号长度均为N，而请求命令中最高冲突位后面的部分被置为1，对标签的识别无用，同时标签返回命令中最高冲突位的前部分对阅读器来说是已知的，也是多余的。在识别出一个标签后又从树根开始下一轮的识别，没有充分利用前面检测到的冲突信息，来减少查询次数。
1.2 对基本二进制搜索协议的改进
    对二进制树形搜索协议的改进主要从减少查询次数、减少发送数据和响应数据的长度着手。
1.2.1降低通信数据位长度的改进
     降低数据长度的改进协议主要有动态二进制搜索协议、引入预处理的二进制搜索协议、传输冲突位位置的二进制搜索协议[8]。
     动态二进制协议中，阅读器检测到最高冲突位（假设第M位）后，下一次查询命令的序列号是最高冲突位在前的（N-M）位加上1位0。各个标签将自身ID号的前N-M+1位与查询序列号比较，匹配标签返回其序列号的后面M-1位。在一次发送和响应过程中，发送数据长度和标签响应数据长度的和为N，与基本二进制协议中一次发送和响应数据的长度2N相比降低了50%。
     预处理的二进制树搜索协议在基本算法之前进行一次预处理：阅读器第一次发送查询命令，所有标签都返回自己的ID，阅读器检测所有冲突位，有冲突的标签为1，无冲突的标记为0。将此冲突信息发给各标签，以后各标签只返回有冲突标记的位。这样也可降低发送和响应的数据位长度。
    传输冲突位位置的二进制树搜索协议在发送查询命令时不是发送查询ID或前缀，而是根据检测到的冲突信息发送最高冲突位的位置信息，这对ID长度较长的标签，也可降低发送的数据长度。
1.2.2 降低查询次数的改进
     降低查询次数的方法主要有基于堆栈的二进制搜索、基于分组的二进制搜索等协议。
     基于堆栈的二进制搜索协议[9]将搜索过程中发送的查询命令参数放入堆栈，在识别出一个标签从堆栈中取出上一次的查询命令修改后即可进入另一右子树的搜索，不需要再次从根结点搜索来识别下一个结点。这样可以大大减少发送查询命令的次数。
    基于分组的二进制搜索协议[4,9-11]则是根据某种策略将待识别标签进行分组，然后依次识别出各组标签。分组后组内标签碰撞概率降低，再利用二进制搜索协议就可以降低查询次数。如ABS协议、自适应多叉树协议、不平衡完全区组协议。
    此外降低查询次数的协议是基于只有1位碰撞位的互斥特性，可以直接识别两个标签。
2 时间优先级分组的二进制搜索协议
    随着RFID在物联网中的大量应用，出现了这样一种场景[12]：在RFID应用于物流生产线、传送带、物流等快速移动领域时，多个标签以分组的形式快速进入阅读器的识别范围内，然后又快速移出。如图1所示。虚线表示阅读器的阅读范围，多个标签以分组的形式（如一个托盘）依次通过阅读器。

    在这种场景下，使以前的二进制搜索协议遇到了挑战。“RFID系统在一个 CRI 内不会有新的标签到达”这一假定不太适用。在标签快速移动的场景下，在识别前一标签组的过程（冲突解决期）内有新的标签到达，而新进入的标签采用自由信道访问策略则会加大先进入标签组的识别延时。如图2所示。

    当先进入的标签A、B、C、D利用二进制搜索协议识别标签B时，有两个标签E、F进入，其中标签E位于B的左边，标签F位于标签B的右边。此时由于标签E的ID前缀与查询前缀ID不匹配，将不影响B右边结点的C、D的识别延迟。但结点F的加入，造成了和结点C、D的冲突，为解决此冲突，加大了识别结点C和D的延迟时间。如果进一步考虑识别出结点F后阅读器的读写数据的通讯时间，则识别结点D的时间将进一步延迟。若有多个后进入的标签都位于结点D的前面，就可能导致结点D已经离开阅读器的读写范围，造成漏读。但由于标签在快速移动，导致标签离开了阅读器的识别范围，从而导致了漏读现象。因此，必须对二进制搜索协议进行改进。
　时间优先级二进制协议采用先进先出FIFO(First In First Out)的服务原则，结合标签分组识别的思想，按照标签进入阅读器阅读范围的时间长短进行确定识别优先级，并根据优先级将标签划分为若干待识别标签组，按照时间优先级的高低依次识别各组标签。该协议与二进制搜索协议的实现过程不同的地方有：
    (1)在阅读器中设置一查询优先级变量Q, 每个标签中各设一个动态优先级变量P。标签在获得能量后，将其动态优先级P设定为0。
　 (2)阅读器每隔一定时间T,发出一个优先级更新命令，各标签收到此命令后，将动态优先级P加1。
　 (3)阅读器在发送查询命令时,除了发送查询前缀外,还附加一查询优先级Q，Q的取值按照轮询的方法来赋值即Q依次为Pmax,Pmax-1,…,1,0，其中Pmax为标签中动态优先级的最大值。
　 (4)标签在响应查询命令时，只有其动态优先级P与查询优先级Q相符的标签才返回其ID的后辍部分。
　 (5)对于相同优先级的防冲突过程，采用基于堆栈的动态二进制搜索协议。
3 协议性能分析
    二进制搜索协议的性能主要从降低识别延时和提高识别率来考虑，延迟时间主要由识别过程中要传输的数据量多少决定，具体由查询命令次数及每次查询中传输的数据位来决定。时间分组二进制搜索协议，在每次查询命令参数中增加优先级这一参数，增加了每次的传输通信量，但由于将阅读器范围内的标签进行了分组，每组内标签的个数大大减少，降低了组内标签碰撞的概率，降低了查询次数，总体上降低了传输通信量，减少了识别延时。下面将时间分组二进制搜索协议与动态二进制搜索协议、基于堆栈的动态二进制搜索协议进行比较，以说明其性能的提高。设阅读器范围内有N个标签，标签ID长度为L位，依据时间分组的组数为G。
　对于动态二进制搜索协议，其查询次数为N(N+1)/2, 每次查询的数据量为(L+1)/2，则总的传输数据量S1为：

    图3显示了堆栈动态二进制协议与时间分组二进制协议的通信数量。其中L为32位，P=4。可以看出识别一组内标签的数据量远小于识别所有标签的数据量，即识别延时大大降低。

    图4显示了在L=32,N=500的情况下，分组数P与数据量的变化关系。可以看出随着分组数的增加，识别一组内标签所需的延时将急剧降低。

    动态二进制搜索协议在面向越来越普及的快速移动的物联网应用时遇到了漏读率提高的新挑战。本文提出了一种时间优先级分组的二进制搜索协议TGBS。TGBS协议按照先来先服务（FCFS）的公平原则，将进入阅读器范围内的多个标签按进入时间的长短进行优先级分组，并按优先级高低进行分组识别。与动态二进制搜索协议相比，在标签内只需增加一个优先级变量，电路实现简单；阅读器发送查询命令时增加查询优先级参数，尽管单次查询发送的数据量有所增加，但分组后组内碰撞标签数大幅减少，后进入的标签组不对先进入的标签组产生识别干扰，可以有效地保证先进入的标签能完整地正确识别，降低了标签漏读率。理论分析和仿真表明，在移动场景下在识别的准确率上，协议比动态二进制协议更优。
参考文献
[1] PRAPASSARA P, BELASTANTIC. Unified q-ary tree for RFID tag anti-collision resolution[C]. the 20th Australasian Database Conference.2009.
[2] 魏欣. RFID标签及阅读器防冲突算法研究[D].成都：电子科技大学,2009.
[3] 丁治国,朱学永,郭立,等.自适应多叉树防碰撞算法研究[J]. 自动化学报，2010，36(2):237-241.
[4] 李世煜,冯全源,鲁飞. 基于 BIBD(4,2,1)的 RFID防碰撞算法[J].计算机工程,2009,35(3):279-281.
[5] 向垂益,何怡刚,李兵,等.动态二进制树搜索算法的改进[J]. 计算机工程, 2010,36(2):260-262.
[6] 冯波,李锦涛,郑为民. 一种新的RFID标签识别防冲突算法[J]. 自动化学报,2008,34(6):632-638.
[7] DONG Her Shih, SUN Po Ling, YEN D C. Taxonomy and survey of RFID anti-collision protocols[J]. Computer Communications,2006(29):2150-2166.
[8] SHI X L, SHI X W, HUANG Q L, et al. An enhanced  binary anti-collision algorithm of backtracking in RFID system[J]. Progress In Electromagnetics Research B,2008(4):263-271.
[9] MYUNG J, LEE W J, SRIVASTAVA J. Adaptive binary splitting for effcient RFID tag anti-collision[J].IEEE Communications Letters,2006,10(3):144-146.
[10] WANG Tsan Pin. Enhanced binary search with cutthrough operation for anti-collision in RFID systems[J]. IEEE Communications Letters,2006,10(4):236-238.
[11] 尹君,何怡刚,李兵,等.基于分组动态帧时隙的RFID防碰撞算法[J]. 计算机工程,2009,35(20):267-269.
[12] 赵曦，张有光. 一种新颖的 RFID多标签防碰撞算法[J].北京航空航天大学学报,2008(3):276-279.