一种快速获取同频数据的防碰撞算法

郑 凯,李 冰,刘 勇,赵 霞,张 林

（东南大学集成电路学院，江苏 无锡 214035）

1 引言

433 MHz频段下的标签识别是一种使用标签进行无线数据存储和检索的自动识别技术。一旦无线信号在接收范围之内，处在433 MHz频段下的标签能够响应来自于阅读器特定频段的序列。与早期的二进制编码技术不同，433 MHz频段下的标签识别不需要近距离的接触。由于该技术相比二进制编码技术能够提供绝对的灵活度，该灵活度可以很好地对各类土地的地形分布数量等特征进行测量，因此该技术被广泛应用于土地测量领域。

在一个433 MHz的系统中，阅读器识别区域内可能存在多个标签，为了识别所有的标签，该系统需要一个通讯协议。因为在阅读器和标签之间的数据传输都是在一个共享的无线频段上的，所以当不止一个标签与阅读器进行通讯时就产生了冲突。这些通讯协议被统称为防碰撞算法。目前存在两种防碰撞算法：确定性算法和随机性算法。确定性算法都是基于二叉树的算法，例如质询二叉树算法（QT）和防碰撞二叉树算法（CT）。基于二叉树的算法通常都是将整个标签分成两个子类别，以此类推，直到把所有的标签都识别出来。而随机算法则是基于时分复用的算法的，其主要的思想是强制设定不同标签的响应时间从而避免了碰撞的发生。以上这两种算法都存在着自身的优点和缺陷。

由于433 MHz系统的整体性能绝大部分取决于系统中所使用的特定的防碰撞算法，因此对于433 MHz系统来说，一个好的碰撞算法是十分重要的。通常来说，判断一个防碰撞算法好坏的标准包括这个算法需要多少个周期将所有的标签都识别出来，算法的复杂程度以及传输的数据量的大小。因此，一个较好的防碰撞算法应具备以下特征：较少的识别周期，计算简单，资源消耗少，能耗低，识别速率快。

本文采用改进型碰撞二叉树（ICT）的快速防碰撞算法。在标签识别中，ICT算法在每一个标签中引入了一个计数器和指针，用于记录阅读器之前发送的序列差异。由于存在了计数器和指针，因此阅读器不需要传输整个序列，阅读器只需要传输上次已经识别的后一个bit位，这样便大大减少了阅读器和标签之间的数据传输量。

2 改进型碰撞二叉树算法

2.1 改进型碰撞二叉树算法简介

在ICT算法中，曼彻斯特编码用于查找冲突的比特位。为了能够精确查找冲突的比特位，假设所有识别区域内的标签能够同时响应阅读器序列中的质询位。这里所讲的序列中的质询位指的是上次已经查询过的前缀的后一个bit，阅读器可以通过这一个质询位来将所有的标签区别开来，而不需要前面的前缀序列。阅读器中有一个用于存储前缀序列的堆栈，并且在每一个标签中都有状态寄存器（SC）和指针寄存器（Pointer），状态寄存器用于分类标签，只有当状态寄存器为0时标签才会响应；指针用于指向与当前bit对比的那个标签bit位，只有当标签比对正确的时候才向阅读器发出响应信号。也就是说，标签的响应是从当前bit位的后一位一直持续到序列结束的最后一位为止。当阅读器接收到了标签的响应信号后，会发出一个反馈信号，并且所有的标签根据这个反馈信号自行调整标签中的状态寄存器和指针。

2.2 改进型防碰撞二叉树算法的实现

在初始化阶段中，堆栈中是空的，不存在任何内容，而标签中的指针指向了标签ID的最高位，随着不断地识别操作，指针逐渐向后面的bit位移动；状态寄存器中的值为0，即说明所有的ID当前bit匹配的标签都应当响应阅读器的序列。由于在等待周期中不会有任何的标签响应阅读器，因此ICT可以省略掉等待的周期，所以只存在两种处理周期：识别和碰撞周期。

关于这两个周期的定义如下：

（1）识别周期是指有且只有一个标签的状态寄存器值为0，并且当前的bit位与阅读器序列中的匹配；

（2）碰撞周期是指有不止一个标签的状态寄存器的值为0，并且当前的bit位与阅读器序列中的匹配。

在ICT中，阅读器需要通过传输目前前缀序列的后一个bit位（当前序列的后一个bit）来区分所有的标签，只有那些状态寄存器为0并且与ID中的前缀序列相同的标签才响应阅读器。当那些满足状态寄存器为0并且当前指针指向的bit位与前缀序列中的bit相同时则将ID中余下的bits发送给阅读器。而阅读器则根据接收到的信号来判决该返回信号对应的正确操作。当发生碰撞时，阅读器则根据冲突的那个bit位产生两个新的前缀序列并且将其压入堆栈中。与此同时，阅读器从堆栈中获取新的前缀并且反馈相应信号。如果没有碰撞时，阅读器则能够识别出当前的序列对应的标签，其对应的ID就是当前的前缀序列和阅读器收到的剩余ID的bits。在后面时间里，阅读器则可以通过这个ID号进一步和已经识别的标签进行数据的交换传输，在此之后，同样的，阅读器从堆栈中获取新的前缀并且反馈相应的信号。而那些不对阅读器进行响应的标签则相应地改动内部的状态寄存器。在这个过程中，简单的对状态寄存器进行+1操作是远远不够的，因为这可能会导致在处理过程中插入较多的等待周期。为了有效避免等待周期，在每一个标签中都设置了一个Flag标记符。Flag用于标注上一个判别周期的状态，Flag=1意味着上一个判别周期是识别周期。如果Flag=1，那么在当前的判别状态下，状态寄存器不变；反之，当Flag=0，则将状态寄存器中的值加1。当标签收到阅读器的反馈信号的时候，则将Flag重新置位。

反馈信号用于通知所有标签当前阅读器的识别状态，由于识别过程中存在两种周期，因此阅读器发送两种类型的反馈。根据不同类型的反馈信号，标签做出如下的响应：

识别：所有的标签都将状态寄存器中的值-1并且将Flag设置为1，直到再次将状态寄存器-1时其值变为-1，则表明，当前的标签处于静默状态，并且不再继续响应阅读器的序列。

碰撞：这一种类型的反馈信号中包括了一个参数k，表明当前接收的新的前缀长度（bit）。当标签接收到这种类型的反馈信号时则设置状态寄存器为0，并且将指针设置为k-1个bit的位置，将Flag设置为0。

图1所示的是ICT算法流程图。表1中列举了一个使用ICT识别4个标签的过程，四个标签分别为0001、0010、1100和1111。

表1 采用ICT识别4个标签

图1 ICT算法流程

3 性能对比

将ICT算法和参考文献[4]中的CT算法就通信开销和识别速度两个方面进行对比，ICT中的一些性能参数，例如识别一个标签消耗的时间和识别效率与参考文献[4]中是一样的。

通信开销被定义为单位时间内通过阅读器的平均bit的数量和识别一个标签耗费的时间，识别速度定义为识别标签的平均数量/s。数据信道的数据传输速率设置为96 kbps。并且使用一个bit定义了两种不同类型的反馈信号（1表示识别，0表示冲突），在冲突周期中，变量k的长度不能大于7 bits。

主要从以下三个不同方面对提出的算法进行了仿真和性能评估。

初次实验中，使用ICT和CT算法分别识别一些标签，标签的数量从2个至512个之间变化，ID的长度设置为96 bits，并且这些标签的ID都是随机产生的，尽管在ICT算法中使用一些技术避免传输不必要的bits，但是其性能并非如同之前所期望的那样好，ICT只能够取得与CT算法等同的性能。通过对实验数据进行分析，发现由于标签ID是完全随机离散的，因此每一个标签都有一个十分独特互不相关的ID，几乎所有标签的开始8个bits都是不一样的，因此在使用CT算法的时候并不需要大量传输标签的ID。故此，在本次的测试中，并不能完全体现出ICT的优越性。

经由上述的试验分析，可以看出尽管ICT算法在算法的层面上对CT进行了大量的改进，但取得的性能却并不能达到我们预期的效果。而导致这一现象主要的原因是随机生成的ID在最开始的几个bits是高度离散不相关的，因此ICT算法并没有得到很高的发挥。

在接下来的实验中，每一个标签都有一个高度相关的识别前缀。在本次实验中，仍然使用ICT和CT两种算法识别256个标签，每个标签ID的长度都是96 bits，并且每一个标签都有一个彼此相关的识别前缀，这个前缀的长度在4～80 bits之间不等，而ID中其余剩下的bits都是随机产生的。如图2所示是本次实验的结果。从图2（a）我们可以清楚看到ICT的优越性，并且随着识别前缀的长度的不断增加，相比CT算法其性能愈加明显。这是由于在CT算法中阅读器需要传输整个识别序列，而在使用ICT算法的时候，阅读器只需要传输当前的bit。图2（b）所示是两种算法的识别速度，ICT能够明显获得快于CT算法的速度，试验说明ICT算法比CT算法更适合前缀相关的序列的标签识别。

4 结论

本文提出了一种用于土地地形分布特征测量的ICT快速获取同频数据的防碰撞算法。这种算法是从CT算法中衍生而来，通过某些技术方式避免了传输不必要的数据。本文的创新点是根据碰撞原理找到碰撞的具体位置之后，在这些碰撞的位置后面加上一位或者多位比特来增加质询前缀，减少质询位数而增加质询效率。实验结果表明ICT能够在ID前缀序列相关的情况下获得比CT算法更好的性能。ICT算法可以被应用到433 MHz土地测量系统中来解决碰撞问题，同时可以获得优于CT算法的性能。

图2 前缀序列的仿真结果

[1]L Zhu,T S P Yum.IEEE Communications Magazine[J].2011,49:214.

[2]M A Bonuccelli,F Lonetti,F Martelli.Ad Hoc Networks[J].2007,5:1220.

[3]J H Choi,D Lee,H Lee.IEEE Communications Letters[J].2007,11:85.

[4]X Jia,Q Feng,C Ma.IEEE Communications Letters[J].2010,14:1014.

[5]J Myung,W Lee,J Srivastava.IEEE Communications Letters[J].2006,10:144.

[6]K Finkenzeller.RFID Handbook: Fundamentals and Applications in Contactless Smart Cards and Identification,Second Edition[M].John Wiley & Sons,2003.Chapter 7.

[7]F Schoute.IEEE Transactions on Communications[J].1983,31: 565.

[8]K C Shin,S B Park,G S Jo.Sensors[J].2009,9: 845.