时间优先级分组的二进制防冲突协议

随着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个标签待识别。