基于RFID木制品物流多目标识别算法的优化

陈清耀, 林宇洪, 邱荣祖

(福建农林大学交通与土木工程学院，福建 福州 350002)



基于RFID木制品物流多目标识别算法的优化

陈清耀, 林宇洪, 邱荣祖

(福建农林大学交通与土木工程学院，福建 福州 350002)

摘要:为了提高木制品物流多目标识别效率，选用基于ALOHA的动态帧时隙的防冲突算法，并采用概率学方法对RFID碰撞现象进行分析和仿真试验，设计了智慧的防冲突算法，实现了通过上一次扫描的标签数推算下一次扫描应开设的最优帧长.

关键词:RFID; SDK; 多目标识别; 防冲突算法

2014年我国林产品出口总额达到722.0亿美元，其中木家具、板材等木制品为353.3亿美元，中国已经成为木制品加工大国和贸易输出国[1].国际上通用的2种RFID防冲突算法分别是ALOHA算法和二进制搜索算法[2].木制品物流RFID管理系统一般选择UHF(超高频)频段915 MHz频率，当多标签同时出现在阅读器可读取范围内时，阅读器无法有效读取各个标签信息，即发生标签碰撞[3].UHF频段的防碰撞算法则以ALOHA算法为主，Haidars et al[4]提出运用帧时隙(FSA)ALOHA算法促使识别周期的时间达到最小，这比传统的ALOHA算法更为优越和高效，避免了发生不完全碰撞.大规模标签会出现严重的碰撞现象，而当标签数量较少时则会造成时隙的资源浪费.目前国内外有多种动态帧时隙(DFSA)算法，DFSA算法通过动态调整Q值(RFID阅读器的扫描指令Query中包含了参数Q，用于改变下一次扫描帧长)，使帧长以2Q形式动态进行调整[5].总体而言，DFSA算法能有效解决固定帧时隙算法在标签数量较少时的时隙资源浪费问题，而随着标签数量增大至一定规模，帧的调整能力下降，标签的识别效率也随之降低[6,7].随机推迟算法(P-ALOHA)利用重发模式有效解决标签碰撞问题，然而此方法仅适用于标签规模较小的多目标识别情况，如门禁系统等；当读取大规模标签时，该系统的时延变长，读取速率降低[8].木制品物流作业环境的标签数量变化范围大，因此还要对优化算法做适当的改良才能投入林业生产应用.本文基于ALOHA的动态帧时隙算法，并进行了改良，实现了木制品物流中的多目标识别.

1改进的防冲突算法设计

1.1数学模型

ALOHA时隙类算法的数学证明结果表明，当标签数与时隙数相等时，系统的识别效率最高.证明过程表示如下.

假设有n个RFID标签同时处于能量区域内等待RFID读卡器识别，RFID读卡器初始帧长度为L，N个RFID标签自由选择通讯间隙，恰好选择同一个时隙的标签数目随机量R服从“总数为N，概率为1/L”的二项分布数学模型[9]，即R～B(N，1/L)，所以有：

(1)

(2)

(3)

当标签数与时隙数相等时系统的识别效率最高，证明如下：

故：Ps=λe-λ，λ∈(0,+∞).

(4)

对Ps关于λ求一阶导数得：

表明当L=N(标签数等于时隙数)时，系统的识别效率最高，系统的信道利用率最大.

1.2算法的优化

以M表示帧长与标签数一定时的系统的识别标签数期望值，则

M=L×Ps

(5)

EPCGEN2标准规定动态帧时隙的帧长L以2Q形式选取[9]，帧长与标签数相等时系统的信道利用率最高，将式(4)带入式(5)，且令N=2Q，得：

(6)

当帧长一定时，Q与M一一对应.以Q为自变量，以M为因变量，在MATLAB中编程，绘制Q与识别标签数期望值M的关系图，以帧长为26为例，如图1所示.

图1中横坐标反映的是外界标签数的规模，由图1可知，外界标签数为26时，理论上系统可以识别最大的标签数，这与上述证明的结果即时隙数与标签数相等时系统的信道利用率最大相吻合.

1.3标签的估计

市面上所能购买到的超高频手持RFID读写器型号有C6631WB-15693、C8000UHFWB1D及DS5等，系统内置WiFi、蓝牙、进口超高频模块及天线，提供开发包DLL、demo源码、SDK，Manual等底层接口，支持ISO18000-6C(EPCGEN2)协议，这些读写器只能通过改变扫描指令Query中携带的参数Q(Q为时隙计数器参数，帧长大小为2Q)来改变下一次扫描的帧长[10].设置一次扫描指令仅工作一帧后，通过识别的标签数反推外界标签的规模数，设置下一次扫描的帧长，从而实现扫描级别的优化，而无法做到盘存周期内的帧级别优化.推算外界标签规模的算法见图2.其工作原理是：首先取RFID读卡器初始帧长N=24，系统发出读卡请求，获得识别数A，此时可能的Q值有较小和较大的2种可能，分别为3和4或者7和8.设L1、L2、L3和L4对应的标签数分别为N1、N2、N3和N4，为了避免帧长过大而标签数过少造成的时隙浪费，设帧长为L1对应的标签数为N1，获得新的识别效率P1，若P1>P，则帧长N=N1；设帧长为L2对应的标签数为N2，获得新的识别效率P2，若P2>P，则帧长N=N2；设新的帧长为L3对应的标签数为N3，获得新的识别效率P3，若P3>P，则帧长N=N3；设新的帧长为L4对应的标签数为N4，获得新的识别效率P4，若P4>P，则设新的帧长N=N4，否则新的帧长仍为初始N；当连续2个帧长相等时跳出循环，获得最优帧长.

因为Q从1至10取值，所以系统最多只要记忆10条曲线就可以完成全部优化过程.帧长=128时的识别时隙数的概率曲线见图3.帧长=256时的识别时隙数的概率曲线见图4.

2仿真检验

基于概率模型，设计了通过识别数推算外界标签规模的算法.因为RFID设备识别标签速度比仿真程序慢，无法进行大规模测试[11]，所以分别按照标签、读卡器工作原理编写了仿真程序.小规模测试时仿真程序与真实设备的结果相似，证明仿真程序可以模拟读卡器识别标签的流程.首先在MATLAB中编程，Q值从1到10变化，做150×3矩阵，3列分别对应帧长、外界标签数以及识别标签数期望值，再将矩阵转为txt文档保存起来，利用MATLAB自带的随机数生成器生成(1，2Q)范围内的随机数.每个标签在该范围内随机抽取1个随机数表示该标签可能应答的时隙，计算1帧内正确识别的时隙数，在txt文档中通过查询与之最接近识别标签数期望值来确定下一帧的最佳帧长.从图2可知，当连续2次帧长相等时跳出循环，表明当前帧长识别外界标签效率最高.对外界标签数1至1 000随机取值，进行104次仿真，仿真结果显示RFID读卡器最多4次判断能猜中外界标签的规模，从而确定合理的Q值.之后识别效率接近0.368，包含判断Q值时所浪费的时隙数，104次仿真综合识别效率稳定在0.341，这意味着本算法平均每3个时隙就可以正确识别1个标签.

3系统实测

以空降兵DS5 RFID一体机为例，系统处理器为ARM Cortex A8 1GHz，支持高频/超高频，采用2 800 mAH锂电池可连续工作6 h，系统内存为512 Mb/1GB，识别距离可达3 m，内置Wince6.0嵌入式系统.因此，可采用Microsoft Visual Studio 2010智能终端开发方法.采用C++.net重写上文仿真验证的防冲突算法，使其能够工作于一体机的嵌入式系统中，便于实测识别效率[12].固定帧时隙算法有2种工作原理设备，一种固定帧时隙设备，厂商通常将Q锁定为4，不能修改，外界标签数在32以内时，识别效果很好，但是当外界标签超过64张之后，识别效率接近于0，无法完成外界标签数1至1 000变化的实测；另一种固定帧时隙设备，厂商在出厂前可以按客户常见的工作场景，调整设备帧时隙的出厂设置.以标签规模在1至1 000动态变化的工作场景为例，厂商通常会把帧时隙设定为平均值附近的512，实测识别效率仅为0.139.而随机帧时隙算法通过每次随机取Q值的方式，Q值的取值范围是1至10，因此可以完成外界标签数1至1 000不定变化的识别任务，实测识别效率只有0.254，即平均每4个时隙识别1个标签.本文提出的算法实测效率为0.326，略低于理想环境仿真效率(0.341)，但优于固定帧时隙和随机帧时隙的算法.

4小结

木制品在物流过程中待识别目标数在1至1 000范围内大幅变化，RFID系统无法高效识别.本文基于ALOHA防冲突算法，采用概率学方法，通过上一次扫描的标签识别数推算下一次扫描应开设的最优帧长.标签数在1至1 000范围内动态变化的工作场景中，实测结果证明了优化后算法的识别效率优于固定帧时隙和随机帧时隙的识别效率.该优化算法能够适应木制品物流环境中标签数量变化幅度大的特点，可广泛应用于木制品运输及追踪过程，技术柔性和扩展性较好.

参考文献

[1] 国家林业局计财司．2014年全国林业统计年报分析报告[EB/OL]．(2015-05-06)[2015-07-05]http://www.forestry.gov.cn/main/225/content-763186.html．

[2] KIM S C, CHO J S, KIM S K. Performance improvement of hybrid tag anti-collision protocol for radio frequency identification systems[J]. International Journal of Communication Systems, 2013，26(6):706-710.

[3] 孙奇燕,王宜怀,冯德旺,等.基于K60的多协议防碰撞RFID读卡器设计[J].福建农林大学学报(自然科学版),2014,43(1):107-112.

[4] HAIDAR S, WASSIM E H, CHRISTINE M. A distributed multi-channel reader anti-collision algorithm for RFID environments[J]. Computer Communications, 2015，64:44-56.

[5] 李建雄,冯鑫,史伟光,等.基于动态Q值的RFID防碰撞算法[J].天津工业大学学报,2015,34(6):55-60.

[6] 邱荣祖,陈锦斌,林宇洪.基于RFID的茶叶物流追溯系统[J].福建农林大学学报(自然科学版),2014,43(2):220-224.

[7] 陈鸿俊.RFID多标签识别防碰撞算法的研究与分析[J].电子测试,2015，23:29-31.

[8] 谢胜眉,赵军辉.基于最优化原理的RFID系统中的ALOHA防冲突算法研究[J].电路与系统学报,2009,14(4):8-12.

[9] 江建.RFID中多标签防碰撞技术的研究[D].成都：电子科技大学,2009.

[10] 林宇洪,沈嵘枫,邱荣祖.南方林区林产品运输监管系统的研发[J].北京林业大学学报,2011,33(5):130-135.

[11] 黄仁,张静,程平.一种ALOHA算法的帧长度调整方法[J].计算机工程与应用,2011,47(9):115-117.

[12] 林宇洪,林森,景锐,等.木材运输IC卡读写器的开发[J].福建农林大学学报(自然科学版),2010,39(4):435-438.

(责任编辑:叶济蓉)

收稿日期：2015-07-02修回日期：2015-09-20

基金项目:福建省科技厅重点资助项目(2014H0010).

作者简介:陈清耀(1992-)，男，硕士研究生.研究方向：交通运输工程.通讯作者邱荣祖(1961-)，男，教授，博士生导师.研究方向：物流技术及交通运输.

中图分类号:F316.2

文献标识码:A

文章编号:1671-5470(2016)04-0476-05

DOI:10.13323/j.cnki.j.fafu(nat.sci.).2016.04.018

Optimization of the multi-object recognition algorithm based on RFID for woodwork logistics

CHEN Qingyao, LIN Yuhong, QIU Rongzu

(College of Transportation and Civil Engineering, Fujian Agriculture and Forestry University, Fuzhou, Fujian 350002, China)

Abstract:To improve the efficiency of multi-object recognition for woodwork logistics, an intellectual anti-collision algorithm was developed upon a ALOHA-based dynamic frame slotted anti-collision algorithm and analysis of simulation experiment on RFID collision via probabilistic method. After validation, the new algorithm was capable of calculating the optimal frame length for next scanning based on the number of tags from previous scanning.

Key words:RFID; SDK; multi-object recognition; anti-collision algorithm