0 引言
射频识别（Radio Frequency Identification， RFID）作为一种无线通信技术，目前已经被广泛地应用到供应链管理、追踪和定位系统中。与传统的条形码相比，它具备较长的识别距离、较高的传输速率等优点[1]。随着RFID技术的广泛应用，经常会有识别多个标签的需求。然而，当多个标签同时响应读写器的请求时会发生碰撞，这使得读写器无法正确地识别标签的传输信息，浪费了通信带宽以及延长了识别时间。RFID防碰撞算法就是致力于解决标签碰撞问题。
目前的RFID防碰撞算法主要分3类[2]：基于ALOHA的防碰撞算法、基于树的算法以及混合类型的防碰撞算法。基于ALOHA的算法，如帧时隙ALOHA（Framed Slotted ALOHA， FSA）算法[3]、动态帧时隙ALOHA算法（Dynamic Framed Slotted ALOHA， DFSA）[4-5]等，将传输时间分成许多个时隙，并将多个时隙组装在一个帧中，处在读写器读写范围的标签随机选择一个时隙传输响应信息，从而降低了碰撞的可能性。但是，会出现标签“饿死”现象，即一个标签在很长时间内无法识别的现象。此外，基于ALOHA的算法的性能还受标签数量、初始帧大小以及标签估计算法的影响。基于树的算法[6-11]，如查询树（Query Tree， QT）算法[6]、二进制树（Binary Tree， BT）算法以及碰撞树（Collision Tree， CT）算法[7-9]等，通过利用标签的ID信息或者标签选择的随机数来不断地将碰撞的标签进行分组直到所有标签均被识别。这类算法简单，易于实施，且能够避免标签“饿死”现象；但是存在识别效率较低、通信量较大等缺点。近年来，有许多学者提出混合类型的防碰撞算法[1-2，12]，通过将ALOHA类算法和基于树的算法的优势结合起来，同时借助标签估计算法、比特追踪技术以及比特恢复技术，能够在避免标签“饿死”的同时，以较高的识别效率对标签进行识别。比如，文献[2]提出的指定树时隙ALOHA（Assigned Tree Slotted ALOHA， ATSA）算法，采用帧时隙的结构，每一帧有一个帧前缀，每一个时隙有时隙前缀，标签通过匹配帧前缀和时隙前缀决定响应与否，该算法能有效地减少碰撞，因此算法具有较高的效率。此外，由于标签只需要响应除去匹配的帧前缀和时隙前缀部分外的ID，因此标签的通信开支也较小。
最近，文献[10]提出多比特标签识别（MultiBit Identification， MBI）协议，协议以一定长度为单位对标签的响应进行识别，当读取的段内有多比特碰撞时，通过开启特殊的时隙对当前时隙内所有标签的ID段进行恢复，减小了这些标签在下一帧中继续发生碰撞的概率，进而提高了识别效率；但是，它存在查询前缀重复发送，以及标签端通信开支较大等问题。
本文在文献[10]的基础上，提出了一种改进的多比特识别（Enhanced MultiBit Identification， EnMBI）协议，通过采用帧时隙的结构和仅对碰撞比特进行恢复的方法，能够很好地降低识别过程的通信开支；此外，本文算法也不需要标签存储编码方案。仿真实验的结果表明，该算法具有相对较低的通信开支。
1 相关工作
本章简要地介绍基于单比特碰撞恢复的碰撞树（CT）算法以及文献[10]提出的基于多比特识别（MBI）的算法。
1.1 CT算法
CT算法是在QT算法上改进的一种树型算法，它们都使用标签的ID去区分碰撞的标签。区别是：CT算法使用曼彻斯特编码对标签响应的第一个碰撞比特进行定位，并将下一次的查询前缀变更为prefix+C0…Cn-1+0和prefix+C0…Cn-1+1。其中：prefix为当前查询前缀，C0…Cn-1为第一碰撞位之前的响应比特。这样减小了空闲时隙的个数，CT算法具有较低的识别延迟。
1.2 MBI
MBI在读写器端以Lb为单位检测标签的响应，在当前检测单元内出现多比特碰撞时，其开启一个多比特时隙即可恢复出所有参与碰撞的标签ID段。
为了在一个时隙中识别出多个标签ID段，MBI提出一种可区分的分组方案，它利用群论的知识将所有的Lb ID段划分为2L/L组，使得同一组的ID段在同一时隙传输能被同时识别出。表1为一种识别长度L=4的ID段分组方案。表1中，每一列为一组，且每一组有一个代表元位于该列下方。同一个组内的ID段满足只有1b不同于代表元，每个ID段的不同于代表元的那1b被称为特征比特。关于其他L时的分组方法，可参考文献[10]中的详细说明。
识别开始时，读写器发送一个前缀和1bit “0”1比特0“1比特0”？此句何意？请明确。是否未说明完整。表明当前时隙是一个基本查询时隙，初始时前缀为空。处于读写器读写范围的标签收到查询请求后，先利用ID匹配前缀，如果匹配，则响应剩余的ID比特。读写器在接收到标签响应后，以Lb为单元检测响应，对于每一个单元Wi，有以下3种情形：
情形1 Wi单元内没有碰撞，此时读写器将当前查询前缀变为prefix+Wi并继续检测下一单元Wi+1，直到prefix长度达到ID的长度。
情形2 Wi单元内只有1b碰撞，此时读写器将碰撞比特分别用0和1替换得到Wi0和Wi1，并分别添加到prefix上，若没有达到ID的长度，则将得到的两个查询前缀存入栈中进行下一次查询；否则，将识别的两个ID存入已识别的ID队列中。
情形3 Wi单元内有两个或多个碰撞比特，此时，读写器发送带有prefix和1bit “1”1比特1同上一个问题。的查询命令开启一个多比特识别时隙。
在多比特识别时隙中，收到命令的标签先利用ID匹配前缀，如果匹配，则取出prefix后的Lb，记为C，并利用C计算响应G。标签用C逐个异或分组方案中每一组的“代表元”，如果异或结果中只有1b为1，则将异或结果追加到G上；否则将Lb 0追加到G上，待与所有分组的代表元比较完成后，响应2Lb G。
读写器在收到响应时，同样以Lb为检测单元，从0单元开始检测。如果当前单元Ui没有碰撞时，则转向检测下一单元。如果有碰撞，则找出第i组中以当前碰撞位置为特征比特的所有ID段，直到整个响应被检测完。将所有恢复出的ID段分别添加到prefix上判断是否需要继续查询。
最后，读写器判断当前查询命令栈是否为空，若为空，则识别完成，停止查询；否则，继续上述查询过程。
由于MBI采用多时隙恢复标签的碰撞，因此能加快查询过程，但是当在基本单元中检测到多比特碰撞时，不管碰撞比特的多少
，都开启一个M时隙进行查询，这样即使碰撞标签很少，参与碰撞的标签都需要响应长为2Lb的串，这使得标签端的通信量太大。此外，在一个多比特时隙结束后，如果恢复出m个ID段，并需要再次查询时，相同的查询前缀重复发送m次，从而导致了很大的通信开支。
2 改进的多比特识别算法
本章将介绍改进的多比特识别（EnMBI）算法。EnMBI采用与MBI不同的帧时隙的结构，在每一帧中，标签先用ID匹配帧前缀，如果匹配，则再继续匹配时隙前缀从而确定在哪一个时隙发送响应。此外，EnMBI不要求标签存储任何标签分组信息。
2.1 算法的描述
为了能够在读写器端准确的检测标签响应的碰撞位置，EnMBI也采用曼彻斯特编码。同时，读写器端需要命令队列（Command Queue， CQ）和ID队列（记为IDmemory）分别存储查询信息以及已经识别的标签ID。表2列举了算法中用到的一些符号和命令。
3）读写器取出命令（0000，0，SQ），并从SQ中取出一个时隙前缀，发送Query（0000，0，0010），所有标签均匹配帧前缀，但只有标签B、E响应。读写器收到响应G后发现只有1b碰撞，B和E被成功识别，并在以后的查询中不再响应。
读写器检测到当前时隙队列SQ非空，于是在接下来两个时隙中发送QueryRep（0110）和QueryRep（0111）命令，分别对应标签A、C、D和F、G响应。时隙2中只有1b碰撞，因此F和G被识别。时隙1中出现多比特碰撞，因此先将xx1x压入队列S中，后将（00000110，1，S）压入CQ中。
4）读写器发送Query（00000110，1，xx1x），标签A、C、D匹配帧前缀，取出ID的第8，9，11位的3b，按步骤2）中方式编码成8b的串返回。在读写器端检测到响应的第1b，6b，7b有碰撞，于是恢复出碰撞位信息001，110，111，最终得到恢复的ID串0011，1110，1111。随后将其压入队列S，并将（00000110，0，S）压入队列CQ。
5）读写器取出命令（00000110，0，SQ），并从SQ中取出一个时隙前缀，发送Query（0000，0，1110），标签A被识别。之后，发送QueryRep（0011）和QueryRep（1111），标签C和D相继被识别。
6）读写器检测到命令队列CQ为空，查询结束。
3 算法仿真及分析
实验采用Monte Carlo的仿真方法，通过C++和Matlab模拟实现了算法的运行过程。仿真涉及1个读写器和多个标签。标签的数量从100到2000，步长100，标签ID长度为96b。对于每个标签数量仿真50次，取平均值作为最后的实验结果。实验涉及本文提出的EnMBI算法、MBI算法[10]、QT[6]、CT[8]以及ATSA[2]算法。下面分别从通信开支和总的时隙数两个方面对算法仿真结果进行分析。
3.1 通信开支
防碰撞算法通信开支通常涉及标签端的通信开支和总的通信开支两种：标签端的通信开支指在一次识别过程中平均每一个标签需要发送的比特数；总的通信开支包括阅读器端的通信开支和标签端的通信开支。为了降低标签的复杂性及能量消耗，标签开支需要越小越好。其次，为了使得识别时间较小且能量消耗较少，总的通信开支也应尽量地小。
图2～3分别是改进的EnMBI算法和MBI算法在L=4和L=8两种情况下的通信开支比较。仿真图中将L=4和L=8的EnMBI算法分别记为EnMBI（4）和EnMBI（8）。
从图2可以看出，改进的EnMBI算法比MBI算法有较小的标签通信开支，这主要得益于EnMBI仅对检测单元里的碰撞比特进行恢复而MBI对碰撞和非碰撞比特均进行恢复。当L=4时效果不明显，这是因为当L较小且标签数量较大时，检测单元W内有很大的几率出现3b或4b碰撞，这时EnMBI的优势不明显。当L=8时，EnMBI对应每个标签的通信量可相对MBI最多减小100b，随着标签数量的增加，L=8检测单元内碰撞数目增加，因此减少的比特数也相应减少。
从图3可以看出，EnMBI相比MBI有较小的总通信开支，当L=4时，约减少10%；当L=8时，约减少20%。这是由于EnMBI减少了MBI的重复前缀发送以及多比特时隙的响应比特数。
为了进一步验证EnMBI算法的优势，图4和图5分别是EnMBI和其他3种算法（QT、CT及ATSA算法）在标签端开支和总通信开支方面的比较。为了进行公平的比较，QT以及CT的Query命令长度为18b，EnMBI和ATSA由于需要在Query中指明帧的大小，因此需要22b。此外EnMBI还需要额外的1b来表明当前的时隙类型。考虑到空闲时隙通常比碰撞时隙和可读时隙持续时间要短，
因此将QT和ATSA中空间时隙维持时间设为6b信号的传输时间。
因此将QT和ATSA中空闲时隙维持时间设为6b此句中，维持时间的单位是bit吗？是否是表达错误，请作相应调整。
从图4可以看出，QT的标签通信开支最大，CT较QT有所减少，这是因为QT算法中标签每次发送整个ID，而CT中只需要发送除去匹配前缀后的ID。EnMBI拥有比CT和QT较少的标签通信开支是因为EnMBI在一个时隙中可以恢复出多个标签，从而减少了标签在下一时隙发生碰撞的概率，而CT和QT在发生碰撞时只根据标签ID的1b进行区分，后续识别过程中碰撞概率仍然很大。ATSA由于利用多比特对碰撞标签进行分组，且每次标签回复匹配后的剩余比特，因此拥有最小的标签通信开支。
从图5可以看出，EnMBI的总通信开支优于QT和CT，主要得益于其利用多时隙恢复多个碰撞标签的方式以及采用帧时隙的方式减小了查询前缀的重复发送。此外，ATSA和EnMBI（4）拥有接近的总的通信开支，当标签数量大于1000时，EnMBI稍优于ATSA。
3.2 总的时隙数
在标签数量一定时，总的时隙数是衡量防碰撞算法性能的重要指标，其为识别标签的过程中所需的空闲时隙、可读时隙以及碰撞时隙的总和。由于EnMBI和MBI算法的效率仅在总通信开支和标签端通信开支上不同，因此本节只绘制了EnMBI和其他方案的总时隙比较。图6是几种算法的总时隙比较。
从图6可以看出，EnMBI（8）在识别相同数量标签时需要最少的总时隙数，因而也具有最高的效率。这主要得益于EnMBI（8）以L=8为识别单元，当识别单元内有碰撞时，可以通过1个多比特识别时隙解决该单元内的所有碰撞，因此花费的时隙较少。此外，EnMBI（4）和ATSA有接近的总时隙数。CT的总时隙数较QT少，是因为CT采用曼彻斯特编码消除了QT中出现的不必要的空闲时隙。
4 结语
基于单碰撞比特恢复的防碰撞算法能够避免不必要的空闲时隙，但是解决碰撞过程较慢，会产生较多的碰撞时隙。
采用多比特识别的方法能够较快地解决碰撞，但是存在标签端通信开支和总通信延迟太大的问题，本文提出了一种改进的多比特识别算法。该算法利用了帧时隙结构的优点，同时仅对碰撞比特进行恢复，能够在不增加总的识别时隙的情况下降低标签端和总的通信量。此外，标签并不需要存储任何有关分组的信息。通过仿真分析可以看出，改进的多比特识别算法具有较小的通信开支，此外在所需总时隙数目上也具有明显优势。
参考文献：
. IEEE Transactions on Mobile Computing， 2013， 12（10）： 2063-2074.
[2]ZHANG L， ZHANG J， TANG X. Assigned tree slotted ALOHA RFID tag anticollision protocols [J]. IEEE Transactions on Wireless Communications， 2013， 12（11）： 5493-5505.
[3]SCHOUTE F C. Dynamic frame length ALOHA [J]. IEEE Transactions on Communications， 1983， 31（4）： 565-568.
// Proceedings of the First International Conference on Pervasive Computing. Berlin： Springer， 2002： 98-113.
. Ad Hoc Networks， 2007， 5（8）： 1220-1232.
// DIALM00： Proceedings of the 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications. New York： ACM， 2000：75-84.
[7]JIA X， FENG Q， MA C. An efficient anticollision protocol for RFID tag identification [J]. IEEE Communications Letters， 2010， 14（11）： 1014-1016.
[8]JIA X， FENG Q， YU L. Stability analysis of an efficient anticollision protocol for RFID tag identification [J]. IEEE Transactions on Communications， 2012， 60（8）： 2285-2294.
