一种改进的防碰撞算法的设计与实现

高玉珍　孟祥敏

摘要：通过对RFID系统的防碰撞问题的分析，设计了一种改进的防碰撞算法——改进型查询树算法。此算法充分运用阅读器接收到的信息中第一位碰撞位信息，阅读器根据收到的碰撞位信息的不同去分解相应的标签组。此算法在通信负载和识别速度等方面相对于查询树算法和碰撞树算法均有明显的提高。

关键词. RFID 防碰撞算法 改进 查询树

1算法描述

改进型查询树算法，它应用在电子标签编码连续的场合中有较好的识别效率。此算法是在查询树算法和碰撞树算法的基础上实现的改进算法，它汲取了碰撞树算法中用第一个碰撞位分解标签组的思想，使得实现过程略过了不少步骤，使用效率和性能得到了较高。

改进型查询树算法的实现对标签的制作工艺相对较高，需要在标签中设置两个计算器，两个计算器分别是状态计算器sc和指针计算器PC。其中，状态计算器是用来记录标签分组信息的，即满足sc等于0的标签就可以“回答”阅读器的查询，指针计算器用于记录标签序列号的位置信息，此位置信息是标签中与阅读器发送的查询位进行比较的位置信息。在辨认过程中的阅读器部分，阅读器中需要有一个保存待发送查询序列数据信息的容器，并且要求这个容器还必须具有“后进先出”的特点，因此就想到了堆栈，此时在阅读器端增加一个堆栈。

在改进型查询树算法中定义一个查询过程包含三个阶段的时间，分别是阅读器发送查询“指示”阶段、标签“回答”阶段、阅读器发送“应答”信息阶段。对应到改进型查询树算法中，在RFID系统中识别一组标签的过程，共可能存在“成功辨认”时间、“拥挤碰撞”时间和“不认识空闲”时间三种类型的查询时间。

2改进型查询树算法工作流程

通过上述的理论分析，下面将对改进型查询树算法的工作流程进行描述。

（1）阅读器操作：

初始阶段：系统开始工作后，阅读器发送一个初始命令，此命令是对阅读器和其工作识别范围内的待识别标签进行相关的初始工作。阅读器的堆栈数据信息被初始置为“O”和“l”，同时将标签内的状态计算器sc和指针计算器PC的值均置为O，状态计算器的值sc为O表明所有的标签都处于“激活”状态，都有可能响应阅读器的查询操作;指针计算器的值PC为0表示在初始阶段指针计算器指向标签序列号的最高位，随着信息识别的推进，PC的值将逐步向后推进，其值也越来越大。实现过程分别有以下三种情况。

“成功辨认”：在工作范围内只有一个标签“回答”此次查询指示。

“拥挤碰撞”：在这种状态下，出现了两个或两个以上的标签“回答”了该查询，标签出现了碰撞情况。

“不认识空闲”：在这个阶段内没有标签“回答”该阅读器的查询。在此情况下，阅读器直接发送应答信息给工作范围内的标签，同时再次用当前的查询位进行查询，这样直接进入下一个碰撞过程。

（2）标签操作：

工作在阅读器范围内的标签在接收到阅读器的查询指示后，标签将根据两个计算器的值来判断是否要“回答”阅读器的此次查询，这两个计算器分别是状态计算器sC的值和指针计算器PC。当状态计算器sc的值等于O时存在以下两类情况：第一种是指针计算器所指的标签信息位与阅读器发送的指令数据位相同，则标签就被成功识别;第二种情况是PC所指的数据位与阅读器的指令数据位不相同，此时标签不响应阅读器的访问，接着所有标签等待阅读器的“应答”信息。

阅读器发出的“应答”信息是用来告知所有电子标签本次查询结果的，同样也是存在着三个阶段。

3算法实例

通过一个例子说明改进型查询树算法的应用过程。首先，设无线射频RFID系统阅读器的工作范围内有4个标签，它们的数据信息是：1100、1110、0010和0001。在表1—1中列举了改进型查询树算法识别4个标签的流程，其中，在表格中尽量简化操作，省略了阅读器的初始化操作，同时查询位指的是前缀序列中的末位，同时对标签收到阅读器的“应答”信息之后的操作也进行了简化，让第一轮操作的结果直接反应在下一次的标签状态中。

第一轮查询过程，所有电子标签都处于激活状态，因此其状态计算器SC的值均为0。在这种状态下，与阅读器前缀序列查询位相同的标签响应，也就是前两个标签回答阅读器指令;后面两个标签1100和1110与阅读器的前缀序列查询位不相同，因此这两个标签不“回答”，同时将其状态计算器sc值增l，此时这两个标签等待。

阅读器的此时收到的信息出现了碰撞，为OOX，可以判断标签发生了“拥挤碰撞”，此时阅读器产生两个新的前缀序列000和001并同时将这两个前缀序列压人堆栈中，然后阅读器向工作在其范围的标签发送拥挤“应答”信号碰撞信息。此时，工作在其范围内的標签在接收到此信息后，接着执行响应的状态调整，将其指针计算器Pointer值变为2，等待阅读器下一轮的查询过程。

第二轮查询过程，用阅读器一位数据信息进行查询，这一位信息来自于堆栈，并且这个堆栈是在上一轮查询过程中形成的新堆栈。后面两个标签不做出任何反应，还是处于等待状态，处于等待状态的标签直接将sc值增加1，也就是在上一轮的基础上现在的数据变成了2，;前面两个标签处于活动状态，此时又出现了“碰撞”，只有一个标签0001“回答”，阅读器能够正确辨认一个标签，其标签序列号为000+1，也就是0001。阅读器正确辨认标签0001后，随即发送“应答”信息给其他标签，其他标签接收到此信息后，将其自身的状态计算器sc的值减l，随机将标签0001置为“沉默”状态，标签0010的状态计算器sc=0，又一次回到激活状态，其余两个标签还是处于等待状态。

第三轮查询，这一轮查询过程，标签0010被激活并并且与阅读器查询位的最后一位相同，因此此时标签0010被识别;标签1100和标签1110处于原来的等待状态没有改变。

以后的查询过程与前几次类似，可以从表I-I看出，用改进型查询树算法成功识别4个标签所需要的时间阶段。在现实应用场景中，对于出现大多前缀序列相同的情况的识别效果相对会好得多。此算法在通信负载和识别速度等方面相对于查询树算法和碰撞树算法均有明显的提高，对无线射频信号的识别有较大的实践意义。

参考文献

[1]郭雨齐，钱志鸿，白曦源，刘淼，一种RFID阅读器的列表式读取方式研究[J]. 哈尔滨工业大学学报，2012，44（11）： 96-100.

[2]李秉璋，景征骏，罗烨，基于后退式二进制的RFID防碰撞搜索算法[J].计算机应用与软件，2009，26（12）：96—98

[3]中华人民共和国科学技术部等十五部委.2015年物联网白皮书：全球物联网正在进入发展新阶段，2015.