摘 要：针对卷烟物流管理系统中多标签密集产生的数据碰撞问题，基于二进制树搜索的确定性算法思想，提出一种改进的防碰撞算法。通过减少RFID标签识别过程中的通信量以及遍历节点的数目，提高标签的识别效率，从而保证了卷烟仓库中件烟托盘的信息读写速度，进一步提高了卷烟仓储物流、过程监管的技术水平。
关键词：卷烟物流;RFID技术;托盘标签;防碰撞
中图分类号：TP301 文献标识码：A 文章编号：2095-1302（2015）01-00-03
0 引 言
随着行业流通体制改革的不断深化和物流体系建设的快速推进，行业物联网技术的应用取得了较大进步和发展。国家烟草专卖局先后组织开发了行业卷烟生产经营决策管理系统一期二期工程、烟草商业企业数字仓储管理系统、工商卷烟物流在途信息系统、烟草商业企业仓储监控系统等物流信息系统，在这些系统中，射频识别技术（RFID）、全球定位系统（GPS）、地理信息系统（GIS）等物联网技术得到了广泛的运用， 文献[1]中分析了RFID技术在武汉卷烟集团一号成品仓库中的应用，阐述了该仓库的扫码组盘和读托盘出库的功能。文献[2]中，研究设计了漳州市烟草卷烟物流配送监控系统，本着“全面感知，全程监控”的现代物流建设目标，利用RFID技术实现了对卷烟配送过程中人、车、物的全程监控和智能管理。可见，作为物联网的核心技术，RFID技术已经广泛应用于我国卷烟物流管理体系中，降低了物流工作人员的劳动强度，提高了企业的管理效率和运作效率，达到了卷烟配送过程信息化、网络化和可视化。
然而近年来，随着烟草行业的蓬勃发展，卷烟市场也在不断地扩大，使得卷烟仓库进出量大大提高，必须部署大量的读写器和标签，多个标签同时响应读写器的查询时会相互干扰，即数据产生了碰撞，导致读写器无法正确读出标签数据，大大降低了物流管理系统的效率和稳定性。因此，用于解决密集型 RFID 系统中多标签识别问题的防碰撞算法已成为该领域研究的热点。
1 超高频RFID技术
RFID技术是一种非接触式自动识别的技术，利用射频信号和空间耦合的传输特性，无需机械或光学接触即可通过无线电信号识别特定目标并读写相关数据。按工作频率可分为低频、高频、超高频、微波等，由于超高频RFID技术具有批量读取、穿透性强、数据记忆容量大、抗干扰能力性强等优点，被广泛应用于行业物流管理系统。一套完整的超高频RFID系统由以下三部分组成：标签、阅读器和应用软件[3-4]。
（l）标签： 是带有线圈、天线、存储器与控制系统的低电集成电路，其内部存有唯一标识编码，贴在被识别物上，用来存储物品信息并能把存储的信息发射出去。
（2）阅读器：一般包含射频模块、控制单元和天线。阅读器通过天线与 RFID 标签进行无线通信，可实现对标签识别码和内存数据的读取和写入，具有相当复杂的状态控制、奇偶校验与更正等功能。
（3）应用软件：确保阅读器和标签通信的有效性和安全性，对读取的信息进行数据处理。
2 RFID数据碰撞
在卷烟物流管理系统中，一般采用的是体积小、功耗低的无源RFID标签，以托盘为单位贴签，通过阅读器将托盘上的件烟信息和RFID标签ID号绑定在一起，每个卷烟成品仓库的托盘数量较多，标签密度大，且进出库工作频繁，标签识别过程中会出现数据碰撞从而导致系统稳定性下降。
2.1 阅读器碰撞
当一个有限范围内部署多个阅读器时，由于阅读器工作区域的相互重叠或者多个阅读器使用了相同的工作频率，会产生干扰从而形成了数据冲撞，称为阅读器碰撞。多个阅读器之间往往可以互相通信，这种碰撞问题相对容易解决。
2.2 标签碰撞
标签碰撞是指多个标签同时发射无线信号所产生的信号冲突，会导致阅读器无法准确识别标签。根据标签类型不同，标签冲撞又分为有源RFID碰撞和无源RFID碰撞[5]。由于有源RFID系统受到了有源标签的成本、体积及功耗的制约，不适合应用于物流管理中，因此无源标签的防碰撞问题成为了研究重点。
标签本身功能较简单、计算能力有限且不能互相通信，因此防碰撞技术主要涉及到无线电通信中的多路存取问题，一般有以下几种[6]：
空分多路法：在分离的空间范围内进行多个目标的识别。这种方法是以牺牲硬件成本为代价的。
频分多路法：把传输信道分解成若干个不同载波频率的子信道，各子信道之间有隔离区域，使得各路信号不会互相干扰。其缺点是各子信道必须有单独的接收模块，浪费频谱资源，成本较高。
时分多路法：将整个信道传输的信息划分为若干时隙，其特点是时隙分配固定，适用于数字信息的传输。
码分多路法：采用不分频段传输，用编码区分同时传送的多路信息，能将不需要的无用信号丢弃，提取需要的有用信号。
3 防碰撞算法
目前，无源RFID防碰撞的研究主要是基于时分多址的，分为概率性算法和确定性算法两大类，概率性算法中具有代表性的是动态帧时隙ALOHA算法，确定性算法主要是二进制树搜索算法。国内学者对这两类算法进行了一定的改进研究，文献[7]中郭志涛针对动态帧时隙ALOHA算法提出了改进方案，结合hash函数和三维估计方法将标签分配到不同的时隙，估计标签数并调整帧长为标签数的1.7倍，以获得最好的识别效果;文献[8]中袁正午等人提出了一种基于堆栈存储的改进二进制搜索算法，通过对标签进行预处理以及在阅读器中设置堆栈，有效地减少碰撞算法中的识别次数和传输冗余信息;文献[9]中高金辉通过设置堆栈和设置标签内部休眠计数器来有效地提高RFID标签识别效率。 根据分析得知，ALOHA算法简单，但识别碰撞的稳定性相对较差，最高信道利用率不到50%，可以应用在对实时性要求不高、标签数量较少的场合。二进制树搜索算法相对较复杂，但标签识别正确率较高，稳定性强，在卷烟仓库中标签数量较多的情况下应优先考虑这种算法，且算法实现目标主要是缩短标签识别延迟时间和降低标签碰撞率。
3.1 算法改进思想
3.1.1 尽可能减少标签识别过程中的查询次数。
传统二进制防碰撞算法中，阅读器每次读取一个电子标签后，都会从根节点开始重新操作，即读取标签平均查询次数与阅读器范围内电子标签的数量有线性关系。为了尽可能减少查询次数，可以使阅读器返回父节点进行查询，一定程度上可减少查询次数。
3.1.2 尽可能减少通信过程中传输的信息量。
阅读器在发出REQUEST命令后，有效范围内所有的标签都要做出应答。假设阅读器在译码后得知有n位发生碰撞，即无法识别n个比特位信息，由于最高碰撞位之前的若干比特位总是固定的，下一次阅读器发出REQUEST命令时只需发送最高碰撞位之前的信息以及发生的碰撞位置，电子标签再次响应时也只需发送最高碰撞位后面的几位信息，显然可以有效减少阅读器与标签的通信量，提高识别速度。
3.2 算法实现流程
改进后的二进制防碰撞算法的流程图如图1所示。
下面通过一个具体的例子来说明改进算法识别一组标签的过程。
假设某读写器有效作用范围内有6个件烟托盘，每个托盘上有一个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，至此，整个识别过程结束。
3.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，显然减少了阅读器与标签之间的通信量。
综上分析，改进后的二进制防碰撞算法在多标签的密集环境下具有较高的识别效率，尤其适用于卷烟仓库的物流管理系统，可大大提高件烟托盘的信息读写效率，最终有效提高卷烟仓储物流、过程监管的技术服务水平。
4 结 语
本文分析了卷烟物流管理系统中的射频识别技术，研究了RFID系统中数据碰撞问题及其解决方法。为了得到更高的标签识别效率，在原有二进制搜索算法的基础上提出了一种改进算法，有效地减少了阅读器与标签之间的通信量，同时减少了阅读器的查询次数和时间延迟。在卷烟仓库中多标签密集的环境下，可大大提高件烟托盘的信息读写速度，使仓储物流系统具有更强的稳定性。
参考文献
[1]米志强.射频识别技术与应用[M].北京：电子工业出版社，2011.
[2]黄恒博.基于物联网的配送监控系统的设计与实现[D].厦门：厦门大学，2013.
[3] FINKEN ZELLERK. RFID Handbook[M].2nd.NewYork： Wiley，2003.
[4] WANG B S， ZHANG Q S. Study of anti-collision performance in parallelizable identification UHF RFID system[J].Journal on Communications，2009，30（6）：108-113.
[5]侯晓波，孙玲玲，钱.RFID二进制防碰撞算法研究与改进[J].杭州电子科技大学学报，2009，29（3）： 16-19.
[6] JIA X，FENG Q. An efficient anti-collision protocol for RFID tag identification[J]. IEEE Communications letters，2010，14（11）：1014-1016
[7]郭志涛，程林林，周艳聪，等.动态帧时隙ALOHA算法的改进[J].计算机应用研究，2012，29（3）：907-909
[8]袁正午，段莉丹.改进的基于堆栈存储的二进制搜索算法[J].计算机应用，2012，32（11）： 3089-3091
[9]高金辉，郑晓彦.RFID系统中二进制搜索防碰撞改进算法[J].计算机测量与控制，2012，20（10）：2754-2756
[10]周晓光，王晓华.射频识别（RFID）技术原理与应用实例[M].北京：人民邮电出版社，2006.
