基于动态帧时隙ALOHA的危险品运输RFID防碰撞算法*

魏福禄，刘 攀，李志斌，孙 锋，郭永青，曹宁博

(1.东南大学 交通学院，南京 210096；2.山东理工大学 交通与车辆工程学院，山东 淄博 255000；3.长安大学 经济与管理学院，西安 710064)

射频识别(radio frequency identification，RFID)技术在物联网应用中需要对大量的标签进行实时处理[1]，可能会出现两个以上的电子标签同时处于阅读器工作范围内的情况，如果这些电子标签同时发送数据将会造成通信冲突；类似地，也会有多个标签同时处于多个阅读器工作范围内的情况，这些标签在传输数据时也会造成数据间通信的干扰，以上问题是当前需要解决的难题.射频识别系统的相关算法常用于工业、物联网、交通运输等领域，通过设定一些相应的规则、命令和研判策略来减少冲突问题的产生，这些规则、命令和研判策略则被称为防碰撞算法.

目前，ALOHA算法主要有纯ALOHA算法、时隙ALOHA算法、帧时隙ALOHA算法、动态帧时隙ALOHA算法等.同时，二进制树算法又包含：查询树算法、二进制树搜索算法、动态二进制树搜索算法、回退式索引二进制树搜索、跳跃式动态搜索算法等[2-5].结合ALOHA算法和二进制树算法这两种算法的混合型算法在理论层面可以实现识别速度的提升，然而在RFID系统的应用层面上，此类防碰撞算法的识别能力和识别率却并不理想[6].

动态帧时隙ALOHA算法能够动态调整时隙的数量，实现对标签的快速识别[7].通过优化达到最佳帧长的步数，将冲突时隙进一步划分，降低轮询空时隙，从而可以使动态帧时隙ALOHA算法延时降低，系统运行效率提高[8].Haida等人采用分布式方法，通过引入多通道协议能够提高RFID读取器对RFID网络资源的利用率，该算法能有效减少标签识别时间，从而提高了成功询问速度[9].王达等[10]对动态RFID环境准确识别标签估计的动态帧时隙ALOHA算法进行改进，从而能够有效降低标签的丢失率，提高标签的准确识别率.

为了降低标签的碰撞率，提升标签的识别效率，可通过对识别标签进行分组，设置一定阀值再确定优先级，然后优先响应当前需要响应的标签，从而提升效率[11].基于时分多址/频分多址建立的RFID阅读器防碰撞算法对信标进行分析和管理，可以使无法访问信道的阅读器在下一个轮回中通过信标信息发送优先级码，从而更有机会访问该信道.为了解决现有动态帧时隙ALOHA标签防碰撞算法的系统吞吐率及效率低等问题，部分学者提出一种可并行识别的分组动态帧时隙ALOHA标签防碰撞算法，在很大程度上提升了算法的识别效率[12-13].

危险品在运输过程始终处于一个动态变化的环境中，需要对大量的标签进行实时处理，标签在进入和离开阅读范围时，会降低帧结束时估算标签数量的精确度，这就对防碰撞算法提出了更高的标准.鉴于危险品运输的特殊性，如何提高RFID系统识别标签的效率和通过率便成为最为关键的问题之一.本文提出了基于动态帧时隙ALOHA的危险品运输RFID防碰撞算法，将RFID系统应用在危险品运输管理过程中，可以为危险品运输管理提供更安全、准确的服务.

1 基于ALOHA的系统防碰撞算法

1.1 RFID系统工作原理

RFID作为一种射频系统，主要包括电子标签、读写器、RFID应用系统三部分，RFID系统结构如图1所示.电子标签指的是内置天线和芯片的微型收发装置，包含电压调节器、调制器、解调器和存储单元.读写器用来收集数据并将其写入RFID标签中.RFID应用系统包括中间件和应用软件，中间件是提供系统软件和应用软件之间连接的软件，能够对数据进行采集、过滤、信息整合与传递；应用软件对读写器和标签内的信息交互进行控制，从而对信息进行接收、采集、统计与执行.

图1 RFID系统结构

1.2 标签防碰撞算法

RFID系统主要采取两种防碰撞算法来解决标签的防碰撞问题，第一种是确定性防碰撞算法，这种算法比较复杂，工作效率低，识别过程中延迟比较明显；第二种是随机性防碰撞算法，它是一种概率性算法，包括ALOHA算法、帧时隙ALOHA算法、动态帧时隙ALOHA算法等.判断算法的可行性需要对多个指标进行考察，如平均数据包交换量、吞吐量以及信号传输的平均延迟等指标.

1.3 帧时隙ALOHA算法(FSA)

帧时隙ALOHA算法是以时隙ALOHA算法为基础，把m个时隙打包成一帧的算法，算法示意图如图2所示.

图2 帧时隙ALOHA算法示意图

图2中，N为帧长，它表示每帧中含有的时隙数，中心标有圆圈的方块表示每个标签在对应的时隙内发送的数据包.这种算法首先是由阅读器发送N值来限定周围标签发送的时隙，然后标签选择一个整数来加载自身的时隙计数器，这个数是随机选择出来的；随着时隙的推移，每个时隙中时隙计数器为0的标签可以立即响应，其它标签各自的时隙计数器为-1；对于帧中发生碰撞的标签将在下一帧中被处理，未碰撞成功识别的标签退出系统，帧时隙ALOHA算法过程如表1所示.

表1中每帧包含3个时隙，前后连续两帧，分别为第1帧和第2帧.最初开始读取数据时，标签1和标签3、标签2和标签5分别在时隙1和时隙2中传输数据，但一个时隙只能同时传输一组序列号，所以这些标签将在下一帧即第2帧中进行传输，标签4在时隙3中成功被识别后从系统中撤离出去.假设有n个待识读标签，且每个标签选择任意一个时隙的概率相等，帧长为N，则标签选择任意时隙i响应的概率为

表1 帧时隙ALOHA算法过程

p=1/N

(1)

根据二项式定理，有r个标签同时响应时隙i的概率为

(2)

当r=1时，该时隙成功识别的概率为

(3)

当r=0时，该时隙空闲的概率为

(4)

当r的取值超过1时，时隙由于有多个标签同时响应，故产生碰撞，则碰撞概率为

pcoll=1-psucc-pidle=

(5)

FSA算法的系统吞吐率为

(6)

当N=n时，S取得最大值且S≈0.367 88

帧时隙ALOHA算法的优点是简单易行，而且帧的大小相对来说比较固定；缺点是识别标签的吞吐率较低，在每一个时隙中都会有多个标签发生碰撞，从而使读取过程易陷入无限循环.

1.4 动态帧时隙ALOHA算法(DFSA)

为了对标签进行动态管理，使标签的数量和帧长相等，帧长N的大小要随着标签数量变化动态地进行调节，这需要对待读标签数目进行估计.

1)标签数量估算方法.DFSA算法的核心工作是尽可能地使帧长N接近待读标签数量n，所以对DFSA算法进行改进必须围绕这个工作前提展开.时隙ALOHA算法的工作流程为：

① 读写器通过发送Query指令来对时隙数帧长Ln进行规定；

② 电子标签随机选择帧长范围内的一个时隙来对读写器的指令进行响应并返回信息包；

③ 算法会根据之前一帧的信息反馈(即观测值，包括成功时隙数Csucc，空闲时隙数Cidle以及碰撞时隙数Ccoll)，运用电子标签估算方法对工作场区内的标签数量进行估算，并根据估算出的标签数量来选择一个适合的时隙数帧长Ln+1；

④ 将选择值Ln+1作为下一帧的帧长，重复上述方法步骤进行电子标签的识读，直到读写器工作场区中的电子标签全部被识别完全.

Crate的理想值为

(7)

因此，碰撞时隙中期望的标签数为

(8)

假设碰撞标签的数量分布符合泊松分布，即在每一个时隙中平均有2.39个电子标签发生碰撞.这种方法是通过对碰撞标签数量Ccoll的估计来对未识别标签的数量n进行估计，并据此方法进行帧长的动态调整，从而获得较高的系统效率.通过分析比对不同初始帧长(N=64，N=128，N=256)，采用Schoute算法来估计系统吞吐量，可以看出帧长与未标签数量越接近，用来调节帧长的时隙就越少，效率就越高.

2)帧长调整.若要有效减少帧长的调整次数，需要减少每一帧内电子标签产生碰撞的概率，增加每一帧内成功识别的电子标签的时隙数.通过增加帧内时隙数帧长L可以减少帧长的调整次数，但当L增大时，系统的吞吐率会随之下降，所以既想要增大L的值又想要保持一定的系统吞吐率需要进行讨论.定义系统的吞吐率为35%，则

(9)

运用线性回归统计方法求出L和n的关系.表2中列出了当S=0.35时，L和n的数据情况.通过观察表2中的数据可知，L/n的值平均在1.40左右，因此L和n的关系符合一元线性回归L=an+b，即需要对a和b进行优化取值.采用最小平方误差的方法，并运用Matlab软件中的polyfit函数求出a和b的最优值，线性回归拟合方程如图3所示.

表2 时隙数帧长与标签数n的对应关系

通过图3可以看到，所绘制的7组数据基本都在一条直线上，拟合准确度较高.通过理论计算和实验分析，在满足系统的吞吐率为35%的情况下，得到时隙数帧长和标签数量的关系为

L=1.36n+3.08

(10)

将式(10)代入到式(9)中得到

(11)

检验结果符合系统吞吐率为35%的最初设定，对于所有的正整数n，算法能保证系统吞吐率在35%以上.

2 实例仿真验证

2.1 仿真实验设计

本文选取广州市某公司的危险品运输数据进行实例分析，通过对不同数量的标签系统效率状态进行仿真，比较动态帧时隙和固定帧时隙ALOHA算法来确定最优的方案，从而对市区道路和仓库危险品进行有效管理.

选取珠海至中山的危险品运输路线，危险品运输车的额定载重量最大不超过20 t，中山市危险品每天运输车辆约为1 489辆，其中珠海市到中山市的货运占比为5%.经计算，每天从珠海市运输到中山市的危险品运输车辆约为75辆.设L的初值为8，随着标签数目的增多，以2的倍数增长.一天内在一条公路上危险品的运输车辆约为75辆，即设置在道路旁的阅读器最少需要对75个标签进行识别.

2.2 仿真结果及分析

固定帧时隙ALOHA算法和动态帧时隙ALOHA算法的系统效率对比如图4所示.在固定帧时隙中时隙数帧长L=64，标签数为60时，系统最高效率为35.2%，但之后随着标签数增多，系统效率迅速下降；在动态帧时隙算法中，在标签数为0～100时，随着n的增加，系统的效率在随之逐渐上涨，最后保持在35.2%稳定不变.

图4 仿真结果对比

由此可知，动态帧时隙ALOHA算法能够更好地解决系统防碰撞问题，使其能够在标签数量较多的情况下发挥自身的优势，在危险品运输中能够避免更多麻烦，更好地解决实际问题.物流危险品运输公司运到中山市产生的标签数至少为75，而且中山市道路每天产生的标签数在1 000以上，通过图4仿真结果可知，动态帧时隙ALOHA算法稳定性更好，且省时、省力.

3 结 论

本文分析了RFID系统的工作原理及帧时隙ALOHA算法的优缺点，在此基础上提出了利用动态帧时隙来处理危险品运输中RFID系统标签冲突的方法.建立了基于固定帧时隙ALOHA和基于动态帧时隙ALOHA的危险品运输RFID防碰撞模型，并通过理论分析和仿真验证，论证了基于动态帧时隙ALOHA的危险品运输RFID防碰撞算法的实用性.在固定帧时隙ALOHA算法基础上发展的动态帧时隙ALOHA算法的系统效率有所提高，动态帧时隙ALOHA算法在危险品运输RFID系统中更加稳定、高效，对于危险品运输管理具有重要意义.