改进的RFID防碰撞算法在仓储管理系统中的应用

无线射频识别技术(RFID)与一维和二维条码技术相比更具现代化,在读取速度、工作距离、存储能力、穿透能力和对标签的适应性等方面有显著的提高.尤其是在读取速度这一方面,RFID系统具有多标签同时识别的优点,这在目前追求以时间取胜的物流仓储环节将发挥举足轻重的作用[1].但是在RFID系统应用过程中,由于信号的传递是通过无线通讯实现的,阅读器在读取标签包含的信息时很容易受到干扰,也就是会产生碰撞的问题,碰撞的发生会增加阅读器识别标签所需要的时间.目前国内外常用的防碰撞算法有基于ALOHA的不确定性算法[2]和二进制的确定算法,基于ALOHA的不确定性算法只适用于解决中低频被动式和只读电子标签的防碰撞问题,在仓储系统中也有用到高频主动式的标签,所以就要选择二进制防碰撞算法.二进制算法的本质是通过判断使处于其阅读范围的可以应答命令的标签的数目逐渐减少,直到发现目标标签.在其识别过程中,大部分标签有可能经过不止一次的判断,所以就有很多不必要的判断过程,导致时间的消耗.本文就二进制算法进行了改进,不再每次搜索都把完整的编号作为搜索命令,而是把一个编号较长的标签分割成几段,分段进行识别,这样就可以减少一些重复的路径,减少不必要的判断次数,识别过程所花的时间就会大大减少,仓储作业的效率就可以得到显著的提升.

在无线射频识别系统中,包含物品信息的电子标签的数据可以被阅读器完整无缺地读取到.RFID电子标签区别于传统的一维和二维条形码,读取方式是非接触式,即阅读器和标签间隔一定的距离就可以读取到标签包含的信息,在这个过程中,数据传输的方式是通过无线通讯.然而一些因素可能会干扰通过无线通讯来获得信息的过程,从而导致阅读器无法正确获得标签的信息.

一般每个标签有固定的发射信号的范围,而阅读器有自己固定的识别范围,当多个标签进入阅读器的识别范围时,每个标签都会发射信号,对阅读器的识别形成干扰,就可能会导致阅读区读取错误[3].同理,如果多个阅读器出现在一个标签的发射信号范围内,这些阅读器都可以读取到标签的信息,但一般应该只有一个阅读器读取到标签信息,而其它的阅读器没有阅读权限.可以用下图来说明碰撞发生的形式,如图1.

不管是上述的哪种原因产生的碰撞,都会加长阅读器识别标签的时间,并且使电子标签消耗更多的能量,从而限制其使用范围的推广.所以从无线射频识别技术出现开始,如何减少碰撞发生、避免碰撞发生的问题就一直被关注.在无线电通信技术中,该问题被称为无线电通信系统中的多路存取法,多路存取法基本分为四种:时分多路法,频分多路法,空分多路法和码分多路法[4].

二进制防碰撞算法是现阶段大多数的标签防碰撞采用的算法,二进制算法的基本原理是可以先给阅读器设置一个命令,命令进入识别距离的标签发送包含编号的信息给它,如果没有符合此命令的标签,那么阅读器停止发送信息,也不读取任何信息,同时所有的标签都进入休眠状态.假如有且仅有一个标签的编号与阅读器发送的编号一致,那么该标签就是目标标签,会被阅读器选中,然后它会将包含的信息发送给阅读器[5].假如同时有2个或2个以上的标签与阅读器发送的编号一致,在此过程中这些标签同时发送信息,这样就会发生信号的干扰,影响识别过程,阅读器就必须继续判断,再发送另一个查询码,此过程一直循环往复,直到只有一个标签符合命令.此时,阅读器就识别到了所有的标签,并且每个标签包含的信息就会全部被阅读器读取到[6].

设现在有如表1所示的4个电子标签,那么二进制算法具体的流程如图2所示.

二进制算法的原理是通过曼彻斯特编码的方法来寻找出发生碰撞的位置.本质是通过判断使处于其阅读范围的可以应答命令的标签的数目逐渐减少,直到发现目标标签.这个算法虽然有效,但是有一些不足之处,在识别的过程中从头到尾都需要标签发送一个完整的ID,没有找到目标标签,就换一个ID发送出去,大部分标签有可能经过不止一次的判断,所以就有很多不必要的判断过程,导致时间的消耗.并且二进制算法在识别一个编号较长的标签时,需要次数更多的搜索,造成更多的时间浪费,时间都消耗在不必要的搜索上,大大降低了工作效率[7].

RFID系统因其无与伦比的优点,在仓储管理系统(WMS)中有着广泛的应用.现阶段,物流公司为了在市场竞争中取得优势,都在千方百计提高仓储作业的效率,所以在WMS中,节约识别货物所需要的时间是很有必要的一件事情.上述算法存在很多不足之处,故对上述算法进行改进,提高算法的性能,使RFID系统在WMS中得到更好的应用.改进算法的基本思路是把一个编号较长的标签分割成几段,分段进行识别,识别完第一段后再对第二段进行识别,逐段进行,直到最后一段被识别,这样就可以减少一些重复的路径,减少不必要的判断次数,识别过程所花的时间就会大大减少.

以A、B、C、D、E、F6个标签为例,6个标签的编号依次为:0100、0101、0110、1010、1100、1110,算法原理及步骤如下:

如图3所示,对上述几个编号长度为4的标签,先对前两位结合成首段进行判断,两位二进制数的组合有00、01、10、11这4种,在上述的6个标签中,前两位有01、11和10这3种情况.当阅读器发送00判断命令时,不存在符合命令的标签,于是判断结束.当阅读器发送01判断命令时,满足此命令的有3个标签为0100、0101和0110,无法识别,所以需要进行下一步的搜索,下一步发送010,还存在0100和0101两个标签,继续分成0100和0101,就不存在干扰了,从而就识别到了这两个标签.另一个分支发送011搜索命令,就直接识别到了0110这个标签.当阅读器发送10搜索命令时,只有1个标签满足条件,所以也不需要进行下一步的判断,可以直接读取.当阅读器发送11搜索命令时,有1100、1110 两个标签满足条件,存在干扰,需要继续搜索,发送110和111的判断命令,这两个标签就识别了出来,所以阅读器发出10次命令就可以把所有标签都识别到.

同理对上述的6个标签作把前3位结合成一段进行判断的处理,判断过程如图4,3位二进制数组合有000、011、001、010、100、101、110、111这8种可能,在上述的6个标签中,前3位二进制数有010、111、101、110和011这5种组合.在阅读器发送000、100和001的判断命令时,无命中的标签,停止判断.当阅读器发送010搜索命令时,有2个标签符合条件,0100和0101,所以继续判断,依次发出0100和0101判断命令,这2个标签就分别被阅读器识别到.当阅读器发送011、111、110和101的判断命令时,符合条件的标签都只有1个,没有信号的干扰,也就不存在碰撞,所以判断终止.综上所述,识别完所有标签共需要10次判断.

具体的算法步骤如图5所示:

设阅读器总共要识别的标签总数是N,阅读器第一次选择电子标签的前l位,那么可以看出,第一次发布的时隙数有2l个,据此可以计算出不存在符合条件标签时隙、可以直接命中的标签时隙和同时有2个及以上个数标签符合条件时隙的数量分别为:

当 时, ,当标签的N很大并且区分度设置太小时,基本上在发出的每个判断码时,符合条件的标签都有不止一个,就会发生标签之间的碰撞,因此每个判断码下都存在一个小二叉树,数量为2l个,同时每个小二叉树内又包含N/2l个标签.

如果用二进制算法来处理N个标签,需要的时隙数的数量为:

在上述的分析中可以得出,在改进的算法中有2l个子二叉树,每个小二叉树包含N/2l个标签,故改进算法的时隙数的数量为:

为了得到改进的算法比二进制算法减少的时隙数,只要将式(4)减去式(5)就可以得到:

由式(6)可以看出,改进算法比二进制算法减少的时隙数跟2个因素相关,一是Nl,二是2l.可以看出,减少的时隙数T与N和l成正相关,在标签数量N越大时,可以减少的时隙数也就越多,也就意味着改进的算法可以比二进制算法节约更多的时间,设置的l越大,比原来的二进制算法节约的时间越多.第二个因素是2l,2l与T成负相关,当2l越小时,减少的时隙数就越多,节约的时间也就越多.所以在N比较大,2l比较小时,改进的二进制算法可以显著地节约识别标签所花的时间,提高阅读器的识别效率.

对上面的式(5)求l的偏导数,可得出当时隙数最小时,标签总量N和区分度l的关系:

在式(5)对l的偏导为0的情况下,由式(8)可以看出N越大,阅读器第一次所需要发布的时隙数2l也就越大.

除了上述的指标之外,还有一个重要检验算法的指标即时隙的吞吐率[8],它等于可以直接阅读标签无需再做判断的时隙除以时隙的总数

对式(9)求l的偏导数,可以得出当时隙吞吐率S最大时,标签总量N与区分度l的关系如下面的式子:

由式(11)可以得出如果需要识别的标签越多的情况下,阅读器第一次需要设置的时隙数也就越大,这个结果和式(8)得出的结论是一致的.

由于l一定为整数,所以取 , 表示取最大的正整数.

通过上述的式(5)可知,改进算法的性能不单和阅读器要识别的标签总量有关,与阅读器第一次选择电子标签的前几位数l也有很大关系.l的设置应参照式(8)来确定,可看出和电子标签总数N有很大关系.在大多数的第三方物流公司仓库中,货物一天中各个时间段到达仓库的数量是有规律的.在货物入库、出库和分拣的高峰期,由于货物流动比较频繁,可能就会有大量的标签需要识别,此时N就很大.而在有些时间段,仓储作业较少,要处理的标签总数N就很小.所以在第三方物流公司的仓库中,需要仓库的工作人员要先统计各个时间段需要识别的标签,寻找出各个时间段标签到达的规律,然后根据式l =log2(N/ln2)设置最合理的区分度l,以便节约更多的时间,提高阅读器的识别效率.

本文针对目前常用的标签防碰撞算法即二进制防碰撞算法进行了改进,把一个编号较长的标签分割成几段,分段进行识别,与二进制算法搜索命令中每次都对整个的标签编号进行判断相比,改进的算法可以明显减少一些重复的路径,减少不必要的判断次数,识别过程所花的时间大大减少.对改进算法的性能通过数学公式进行了定量的分析,得出改进的算法比二进制算法提高了识别的效率,特别是在第三方物流公司仓库中电子标签数量比较大的场合下,能显著地节约识别标签所花的时间,提高仓储的作业效率.最后指出在第三方物流公司的仓库中,需要统计出标签在一天中不同时间段的到达规律,从而为设置合理的区分度提供科学的依据.