卷烟防碰撞物流管理论文

1RFID数据碰撞

标签碰撞是指多个标签同时发射无线信号所产生的信号冲突，会导致阅读器无法准确识别标签。根据标签类型不同，标签冲撞又分为有源RFID碰撞和无源RFID碰撞[5]。由于有源RFID系统受到了有源标签的成本、体积及功耗的制约，不适合应用于物流管理中，因此无源标签的防碰撞问题成为了研究重点。标签本身功能较简单、计算能力有限且不能互相通信，因此防碰撞技术主要涉及到无线电通信中的多路存取问题，一般有以下几种[6]：空分多路法：在分离的空间范围内进行多个目标的识别。这种方法是以牺牲硬件成本为代价的。频分多路法：把传输信道分解成若干个不同载波频率的子信道，各子信道之间有隔离区域，使得各路信号不会互相干扰。其缺点是各子信道必须有单独的接收模块，浪费频谱资源，成本较高。时分多路法：将整个信道传输的信息划分为若干时隙，其特点是时隙分配固定，适用于数字信息的传输。码分多路法：采用不分频段传输，用编码区分同时传送的多路信息，能将不需要的无用信号丢弃，提取需要的有用信号。

2防碰撞算法

目前，无源RFID防碰撞的研究主要是基于时分多址的，分为概率性算法和确定性算法两大类，概率性算法中具有代表性的是动态帧时隙ALOHA算法，确定性算法主要是二进制树搜索算法。国内学者对这两类算法进行了一定的改进研究，文献[7]中郭志涛针对动态帧时隙ALOHA算法提出了改进方案，结合hash函数和三维估计方法将标签分配到不同的时隙，估计标签数并调整帧长为标签数的1.7倍，以获得最好的识别效果；文献[8]中袁正午等人提出了一种基于堆栈存储的改进二进制搜索算法，通过对标签进行预处理以及在阅读器中设置堆栈，有效地减少碰撞算法中的识别次数和传输冗余信息；文献[9]中高金辉通过设置堆栈和设置标签内部休眠计数器来有效地提高RFID标签识别效率。根据分析得知，ALOHA算法简单，但识别碰撞的稳定性相对较差，最高信道利用率不到50%，可以应用在对实时性要求不高、标签数量较少的场合。二进制树搜索算法相对较复杂，但标签识别正确率较高，稳定性强，在卷烟仓库中标签数量较多的情况下应优先考虑这种算法，且算法实现目标主要是缩短标签识别延迟时间和降低标签碰撞率。

2.1算法改进思想

2.1.1尽可能减少标签识别过程中的查询次数。传统二进制防碰撞算法中，阅读器每次读取一个电子标签后，都会从根节点开始重新操作，即读取标签平均查询次数与阅读器范围内电子标签的数量有线性关系。为了尽可能减少查询次数，可以使阅读器返回广州到鹤岗物流父节点进行查询，一定程度上可减少查询次数。

2.1.2尽可能减少通信过程中传输的信息量。阅读器在发出REQUEST命令后，有珠海到河池物流效范围内所有的标签都要做出应答。假设阅读器在译码后得知有n位发生碰撞，即无法识别n个比特位信息，由于最高碰撞位之前的若干比特位总是固定的，下一次阅读器发出REQUEST命令时只需发送最高碰撞位之前的信息以及发生的碰撞位置，电子标签再次响应时也只需发送最高碰撞位后面的几位信息，显然可以有效减少阅读器与标签的通信量，提高识别速度。

2.2算法实现流程

改进后的二进制防碰撞算法的流程图如图1所示。下面通过一个具体的例子来说明改进算法识别一组标签的过程。假设某读写器有效作用范围内有６个件烟托盘，每个托盘上有一个RFID标签，标签ID号分别为：11000001、11010011、11001001、11010001、11000011、11011001。阅读器发送请求指令REQUEST（11111111），要求6个广州到淮南物流标签都作出响应，具体步骤如下：

（l）标签1~6均响应阅读器发出的请求指令REQUEST（11111111），将自身的ID号发送给阅读器。经过曼彻斯特编码译码得到110XX0X1，可以得到下一步的请求指令为REQUEST（00011010，0）。

（2）阅读器发出REQUEST（00011010，0）指令，标签锁定自身ID号的第1、3、4位。锁定位中最高位为0的标签响应该指令，即标签1、3、5响应，返回锁定位中的剩余位：00、10、01，阅读器解码结果为OXX，得到下一步的请求指令为REQUEST（00）。

（3）阅读器发出REQUEST（00）指令，标签1、5响应，分别返回自身的ID号为O和1，阅读器解码结果为00X，于是得到下一步的请求指令为REQUEST（000）。

（4）阅读器发出REQUEST（000）指令，标签1作出响应，无碰撞发生，阅读器发出SELECT和READ指令对标签1进行读写操作，接着执行SLEEP指令，使标签1休眠。为减少查询次数，采用后退策略从该节点的父节点得到下一步的请求指令为REQUEST（001）。

（5）阅读器发出REQUEST（001）指令，标签5作出响应，无碰撞发生，阅读器完成对标签5的读写后，同样执行SLEEP命令，使之休眠。接着采用后退策略得到下一步的请求指令为REQUEST（01）。

（6）阅读器发出REQUEST（01）指令，标签3作出响应，无碰撞发生，同理，该标签完成读写后进入休眠状态，并得到下一步的请求指令为REQUEST（1）。

（7）阅读器发出REQUEST（1）指令后，标签2、4、6作出响应，产生了碰撞。同上方法将该分支内所有产生碰撞的标签都识别出来，识别先后顺序为标签4、标签2、标签6，至此，整个识别过程结束。

2.3算法分析

（1）假设读写器有效范围内有N个标签，采用传统的二进制搜索算法，从N个标签中识别出一个标签所需要的平均查询次数S为[10]：S（N）=log2N+1显然如果有两个以上甚至更多的标签发生碰撞，则阅读器重复询问的次数将会增加很快，算法的性能也急剧下降。对于改进的二进制搜索算法，每次正确识别一个标签后可得到下一次的REQUEST指令，大大地减少了识别过程中遍历节点的数目，即减少了总的查询次数，因此平均搜索次数S'为：S（'N）=2N－1由公式得知，改进的二进制防碰撞算法中，识别单个标签平均只需要不到2次的查询次数，利用后退思想降低了算法的时间复杂度，算法性能得到了很大的提高。

（2）假设标签ID的长度为M，在传统二进制搜索算法中，REQUEST请求命令必须发送标签完整的序列号，即发送的二进制编码长度L=M；在改进算法中，REQUEST命令中的参数是最高碰撞位，即每次发出的二进制编码长度L'=log2M+1，显然减少了阅读器与标签之间的通信量。综上分析，改进后的二进制防碰撞算法在多标签的密集环境下具有较高的识别效率，尤其适用于卷烟仓库的物流管理系统，可大大提高件烟托盘的信息读写效率，最终有效提高卷烟仓储物流、过程监管的技术服务水平。

3结语

本文分析了卷烟物流管理系统中的射频识别技术，研究了RFID系统中数据碰撞问题及其解决方法。为了得到更高的标签识别效率，在原有二进制搜索算法的基础上提出了一种改进算法，有效地减少了阅读器与标签之间的通信量，同时减少了阅读器的查询次数和时间延迟。在卷烟仓库中多标签密集的环境下，可大大提高件烟托盘的信息读写速度，使仓储物流系统具有更强的稳定性。

作者：深圳到吉林市物流杨斐 黄军 陆垂伟 单位：湖北理工学院计算机学院 湖北省大冶市烟草专卖局