基于MBF的船联网RFID数据流清洗算法*

董 辉，马 健，方 晓，姚宏亮

(1.亳州职业技术学院，安徽 亳州 236800；2.合肥工业大学计算机与信息学院,安徽 合肥 230000)

船联网是指基于物联网技术并结合传统信息技术，利用各种感知和传输方式，将舰船、船载设备及货物、航道及岸基设施、水文气象及航道环境信息、企业及管理部门的航运监管系统和相关人员等有效地连接，完成对航运信息的标记、采集、分析处理和运用，增强各航运要素之间的信息交互和智能化决策的一种综合性网络.[1]参照传统网络及物联网的体系结构，船联网可由检测感知层、网络传输层、数据处理层和综合应用层构成.检测感知层作为船联网的基础，其主要功能是充分利用物联网技术来采集与航运相关的各要素对象的信息，并将感知的数据传递给上一层结构作为船联网的各种应用系统的数据支撑.物联网是感知层的核心，无线射频识别(Radio Frequency Identification，RFID)技术是物联网的核心.许多港口、船运企业或船闸都采用RFID技术来快速感知并采集船舶的航线、载货、证照和违章等相关信息，并通过网络传输到港口、船舶航运企业或航运管理部门的综合监管系统中，从而为港口、航企及舰船航务监管部门提供数据支持.可见船联网对各类数据的感知采集是保障航运安全、智能化航运服务管理及提高航运效率的基础.然而由于每时每刻都在产生的原始数据来源多样且数量庞杂，存在大量的冗余数据，因此如何清洗数据中的冗余、为船联网上层应用系统提供规范化信息服务是亟待解决的问题.

1 RFID数据清洗的研究进展

RFID技术拥有强大的感知能力，可满足人们进行目标监控、跟踪及定位的需求.但是在应用过程中，RFID原始数据往往存在大量冗余，影响数据的正确性和精确度，因此对RFID原始数据进行清洗至为重要.国内外众多学者对RFID数据清洗技术进行了深入的研究，取得了一定的成果，其中基于滑动窗口的清洗算法是最为经典的清洗算法.该算法可分为定长滑动窗口算法和自适应滑动窗口算法.定长窗口清洗算法通过滑动长度固定的窗口对数据进行平滑填补，[2]把每个窗口分为多个阅读周期，若某个阅读周期读取到了标签数据，则后续周期读取到标签数据的几率就很大，否则很可能发生漏读现象.此外，该算法根据一定的规则对RFID阅读器漏读的数据进行自动填补以实现RFID数据的有序输出.但是由于RFID系统的工作环境存在大量变化因素，因此固定窗口大小的算法难以满足真实生产环境的需求，窗口过大或过小又可能导致平滑处理后的数据流难以还原出标签的真实移动状态[3].Shawn Ryan Jeffery等[4]提出的自适应滑动窗口清洗(Statistical sMoothing for Unreliable RFid Data，SMURF)算法克服了滑动窗口大小难以选择的缺点.SMUFR算法基于随机事件统计学理论，根据阅读器阅读标签的阅读率，采用RFID数据二项分布模型，自适应调节窗口的大小以实现对RFID数据流的清洗.该算法减少了定长滑动窗口算法带来的积极或消极读的负面影响；但是如果标签移动速度过快导致阅读器的阅读率突然下降，就会加大滑动窗口，从而产生积极读的问题，而且也无法完全消除消极读的缺陷.另外还有更多的学者在RFID数据处理方面作了探索，S R Jeffery等[5]提出了可扩展的传感器数据管道清洗方法，利用传感器的时空特性对RFID数据流进行清洗；Lee Chun-Hee等[6]提出了基于时间间隔布隆过滤器(Time Interval Bloom Filter，TIBF)算法，清洗RFID数据流仅需很少的内存且错误率(Error Rate，ER)很低；刘云恒等[7]运用最大熵特征选择机制对RFID数据流进行清洗，在降低清洗成本的前提下提高清洗策略的准确性.以上研究注重RFID数据流的清洗算法的准确性，却忽略了清洗效率.现实中要根据不同的应用场景，从具体应用出发选用合适的清洗算法，从而保证RFID数据清洗的精确度和时效性.

笔者针对船联网中RFID原始数据存在冗余的问题，提出一种基于矩阵型布隆过滤器的船联网RFID数据清洗(MBF-IRCD)算法，实现对船联网应用系统中的RFID原始数据进行清洗，删除其中冗余数据，获取规范化数据，为船联网上层应用系统提供有效的数据支持，为业务决策提供有力的信息保障.

2 基于矩阵型布隆过滤器的船联网RFID数据清洗

2.1 矩阵型布隆过滤器

布隆过滤器 (Bloom Filter，BF)是由二进制向量和哈希函数组成的一种高效静态的数据结构，可快速判断元素是否在某数据集中.[8]BF是一种静态的数据结构，存在一定的ER和数据删除困难的缺点.当持续地插入新元素时，BF的ER会不断增大，最坏的情况是ER为100%[9].若采用传统BF对RFID数据流这种动态的数据集进行处理，则需要动态调整BF，重新计算BF的全部元素，这显然是不科学的.

引用矩阵理论定义矩阵型BF(Matrix BF,MBF)并以此表示动态数据集S.该数据结构具有矩阵型位空间s×m,拥有d+1个哈希函数hi(i=0,1,…,d)，其中h0的范围为{1,2,…,s}，h1，h2,…,hd的范围为{1,2,…,m}.h0用于确定元素插入的行，其他函数将该行对应的位赋值为1.

由于船联网的感知层RFID原始数据中存在大量冗余数据，需经过处理才能供船联网的上层应用系统使用，因此在RFID数据清洗的过程中，可能因误报而造成一些重要的数据被删除，导致输出的数据不完整，从而使RFID系统所感知的世界与真实世界不一致；也可能产生漏报错误，导致输出的数据流中仍有大量的冗余数据存在，达不到数据清洗的目的.

2.2 RFID冗余数据的判定

RFID数据流可以表示成一个序列S={s1,s2,…,sn}，任意一个si可以用一个三元组模型d(TID,RID,Time)表示,其中RID为RFID系统阅读器EPC标识编码，TID为标签EPC标识编码，Time标识标签被感知的时间戳.RFID数据流中，对于数据x，当且仅当存在数据y,且满足y.TID=y.TID,x.Time-y.Time≤τ(τ为具体应用设定的一个较小的时间段)，x.Time>y.Time,则判定数据x是冗余数据.RFID冗余数据可分局部冗余和全局冗余.在满足上述条件下，若x对应的标签持续不断被1个标签读取到，即x.RID=y.RID,则x为局部冗余数据;若x所对应的标签被多个阅读器读到，即x.RID≠y.RID,则x是全局冗余数据.RFID数据冗余具有传递性.对于RFID数据x和y，若存在zS，且满足x.TID=y.TID，z.TID=x.TID，x.Time-z.Time≤τ,z.Time-y.Time≤τ，则可由S中x是z的冗余数据且z是y的冗余数据推断出x也是y的冗余数据.

2.3 基于MBF的船联网RFID数据清洗算法

由于RFID标签只在感知区才可被检测，且冗余数据是根据位置及时间聚簇的，因此利用时间信息可以测RFID的冗余数据.在MBF引入了2个时间因素Starttime和Interval,其中Starttime 为第i行的开始时间，Interval为第i行与第i+1行开始的时间间隔.根据标签的感知时间即可判定数据是否冗余.这种优化的BF能适应动态数据集，非冗余数据不会被清洗掉，即不会有消极读错误问题，但有可能把冗余数据保留并输出，即具有有限的积极读错误问题.

MBF-IRDC冗余数据清洗算法首先要在MBF中保存每个单元的开始时间和时间间隔.若只有1个哈希函数,则1个RFID标签对应过滤器的1个单元；若RFID数据x非冗余，当x(其TID为1)被读取时，设置其对应的MBF单元的开始时间是x.Time，结束时间也是x.Time，则初始时间间隔Interval为0.接下来检测是否存在1个单元使得MBF[hi(x.TID)].TID=x.TID且x.Time-MBF[hi(x.TID)].Time<τ成立.若存在这样的单元，说明在设定的τ时间段内该标签数据已刚刚被读取，则可判定x为冗余数据.这种计算冗余数据的算法是很苛刻的，因为通常只要计算出标签数据x是冗余的，则x就一定是冗余数据.当然此方法也存在一定的积极读问题，即极少部分冗余数据未被识别出，出现漏报错误，漏报率的大小与设定的时间段τ相关.最后，无论x是否为冗余数据，都要更新MBF单元内的x.TID，x.Startime及Interval.MBF-IRDC(RFID_Datax)算法的流程如下：

输入：RFID数据x(TID,RID,Time)

输出：Whetherxis a duplicate

x.Flag=False；∥数据x冗余标志为False值

For (i=1;i<=k;i++)

{If (MBF[hi(x.TID)].TID=x.TID andx.Time-MBF[hi(x.TID)].Time<τ)

x.Flag=True∥数据x冗余标识为True值,x是冗余数据

}

Endfor

For (i=1;i<=k;i++)

{MBF[hi(x.TID)].TID=x.TID;∥更新标签ID

MBF[hi(x.TID)].Time=x.Time;

}

Endfor

End

当然,MBF-IRDC算法也会有一定的漏报错误，即把冗余数据当作非冗余数据输出，其漏报ER为(1-(1-1/m)kn′)k-p.其中：p是非冗余数据的概率；m是位数组的大小；k是哈希函数的个数；n′是设定的时间段τ内的数据流非冗余数据的数值.

3 实验分析

本实验将模拟传统BF算法和TIBF算法的船联网RFID数据流清洗过程.模拟实验环境为服务器和PC机各1台.PC机配置：i7 6700K CPU，8G内存，1T硬盘，Win7 OS.服务器配置：XEON E5-2609 CPU，8G内存，1T硬盘，Linux OS.算法程序实现环境为JDK1.8，Eclipse4.7.2,编程语言为Java.

3.1 实验设计

RFID阅读器的感知范围大致可划分为强感知区、弱感知区和零感知区(图1).在主感知区范围内，标签被感知的概率很高，被读取率在95%以上；在弱感知区范围内，标签被检测到的概率随距离的远近而线性变化；零感知区是指阅读器和标签之间的距离太远，标签无法被感知到的区域.

图1 RFID阅读器的感知区域Fig. 1 RFID Reader's Sensing Area

3.2 结果

本实验是验证数据流和不同参数对MBF-IRDC算法的ER的影响.首先验证ER与RFID数据流的关系，再验证ER与不同参数的关系.

图2 数据流与ER的关系Fig. 2 Relationship Between Data Stream and ER

3.2.1 数据流与ER的关系 数据清洗算法的错误有误报和漏报2种情况.设固定位数组为5×107，k=5，数据流与ER的关系如图2所示.由图2可知，3种算法的ER都随着数据流的增大而略有增加.在数据流相同的情况下，BF数据清洗算法的ER最大，原因是当数据流足够大时，全部的单元空间BF几乎都被填为1；TIBF算法的ER相比BF算法的要小得多,MBF-IRDC算法的ER是最小的，这是因为前两者的错误都含有漏报和误报错误，后者的错误只包含很少的漏报.实验结果表明，相较于其他算法，MBF-IRDC算法能更好地适应RFID数据流的动态特征，且ER非常小.

3.2.2 不同参数与ER的关系 设数据流为5×107，位数组为m,τ时间内非冗余数为n′，哈希函数个数为k.

(1)位数组与ER的关系.设n′,k值不变时，ER与m的关系如图3所示.从图3可知：BF算法的ER并没有随着m的变化而出现明显变化；MBF和TIBF算法的ER随着m的变化而发生明显变化，m增大，ER明显减小.3种算法中MBF的ER最小，可见MBF-IRDC算法能以较小的存储空间来快速删除RFID数据中的冗余，从而提高数据清洗效率.

(2)其他参数与ER的关系.当m，n′，k都变化时，实验结果如图4所示.从图4可知：当k不变时，ER随着m/n′的变化而变化，两者近似成反比；当k≈(m/n′)×ln 2时，ER取最小值，如m/n′=6，k=4,m/n′=5，k=3，m/n′=4，k=3等情况.虽然ER受多种因素影响，但是当k≈(m/n′)×ln 2时，其值最优.

图3 位数组与ER的关系Fig. 3 Relationship Between Bit Array Size and ER

图4 各种参数与ER的关系Fig. 4 Relationship Between Parameters and ER

4 结语

物联网可为船舶航运提供强大的支持，因此研究RFID技术对于船联网来说有重要的意义.笔者针对船联网环境下RFID数据冗余的问题，设计了基于矩阵型BF的冗余数据的清洗算法，该算法以有限内存高效地对RFID数据流中的冗余数据进行清洗，从而可为船联网的上层应用提供有效数据.