董 輝，馬 健，方 曉，姚宏亮

(1.亳州職業(yè)技術(shù)學(xué)院，安徽 亳州 236800；2.合肥工業(yè)大學(xué)計算機與信息學(xué)院,安徽 合肥 230000)

船聯(lián)網(wǎng)是指基于物聯(lián)網(wǎng)技術(shù)并結(jié)合傳統(tǒng)信息技術(shù)，利用各種感知和傳輸方式，將艦船、船載設(shè)備及貨物、航道及岸基設(shè)施、水文氣象及航道環(huán)境信息、企業(yè)及管理部門的航運監(jiān)管系統(tǒng)和相關(guān)人員等有效地連接，完成對航運信息的標(biāo)記、采集、分析處理和運用，增強各航運要素之間的信息交互和智能化決策的一種綜合性網(wǎng)絡(luò).[1]參照傳統(tǒng)網(wǎng)絡(luò)及物聯(lián)網(wǎng)的體系結(jié)構(gòu)，船聯(lián)網(wǎng)可由檢測感知層、網(wǎng)絡(luò)傳輸層、數(shù)據(jù)處理層和綜合應(yīng)用層構(gòu)成.檢測感知層作為船聯(lián)網(wǎng)的基礎(chǔ)，其主要功能是充分利用物聯(lián)網(wǎng)技術(shù)來采集與航運相關(guān)的各要素對象的信息，并將感知的數(shù)據(jù)傳遞給上一層結(jié)構(gòu)作為船聯(lián)網(wǎng)的各種應(yīng)用系統(tǒng)的數(shù)據(jù)支撐.物聯(lián)網(wǎng)是感知層的核心，無線射頻識別(Radio Frequency Identification，RFID)技術(shù)是物聯(lián)網(wǎng)的核心.許多港口、船運企業(yè)或船閘都采用RFID技術(shù)來快速感知并采集船舶的航線、載貨、證照和違章等相關(guān)信息，并通過網(wǎng)絡(luò)傳輸?shù)礁劭?、船舶航運企業(yè)或航運管理部門的綜合監(jiān)管系統(tǒng)中，從而為港口、航企及艦船航務(wù)監(jiān)管部門提供數(shù)據(jù)支持.可見船聯(lián)網(wǎng)對各類數(shù)據(jù)的感知采集是保障航運安全、智能化航運服務(wù)管理及提高航運效率的基礎(chǔ).然而由于每時每刻都在產(chǎn)生的原始數(shù)據(jù)來源多樣且數(shù)量龐雜，存在大量的冗余數(shù)據(jù)，因此如何清洗數(shù)據(jù)中的冗余、為船聯(lián)網(wǎng)上層應(yīng)用系統(tǒng)提供規(guī)范化信息服務(wù)是亟待解決的問題.

1 RFID數(shù)據(jù)清洗的研究進展

RFID技術(shù)擁有強大的感知能力，可滿足人們進行目標(biāo)監(jiān)控、跟蹤及定位的需求.但是在應(yīng)用過程中，RFID原始數(shù)據(jù)往往存在大量冗余，影響數(shù)據(jù)的正確性和精確度，因此對RFID原始數(shù)據(jù)進行清洗至為重要.國內(nèi)外眾多學(xué)者對RFID數(shù)據(jù)清洗技術(shù)進行了深入的研究，取得了一定的成果，其中基于滑動窗口的清洗算法是最為經(jīng)典的清洗算法.該算法可分為定長滑動窗口算法和自適應(yīng)滑動窗口算法.定長窗口清洗算法通過滑動長度固定的窗口對數(shù)據(jù)進行平滑填補，[2]把每個窗口分為多個閱讀周期，若某個閱讀周期讀取到了標(biāo)簽數(shù)據(jù)，則后續(xù)周期讀取到標(biāo)簽數(shù)據(jù)的幾率就很大，否則很可能發(fā)生漏讀現(xiàn)象.此外，該算法根據(jù)一定的規(guī)則對RFID閱讀器漏讀的數(shù)據(jù)進行自動填補以實現(xiàn)RFID數(shù)據(jù)的有序輸出.但是由于RFID系統(tǒng)的工作環(huán)境存在大量變化因素，因此固定窗口大小的算法難以滿足真實生產(chǎn)環(huán)境的需求，窗口過大或過小又可能導(dǎo)致平滑處理后的數(shù)據(jù)流難以還原出標(biāo)簽的真實移動狀態(tài)[3].Shawn Ryan Jeffery等[4]提出的自適應(yīng)滑動窗口清洗(Statistical sMoothing for Unreliable RFid Data，SMURF)算法克服了滑動窗口大小難以選擇的缺點.SMUFR算法基于隨機事件統(tǒng)計學(xué)理論，根據(jù)閱讀器閱讀標(biāo)簽的閱讀率，采用RFID數(shù)據(jù)二項分布模型，自適應(yīng)調(diào)節(jié)窗口的大小以實現(xiàn)對RFID數(shù)據(jù)流的清洗.該算法減少了定長滑動窗口算法帶來的積極或消極讀的負(fù)面影響；但是如果標(biāo)簽移動速度過快導(dǎo)致閱讀器的閱讀率突然下降，就會加大滑動窗口，從而產(chǎn)生積極讀的問題，而且也無法完全消除消極讀的缺陷.另外還有更多的學(xué)者在RFID數(shù)據(jù)處理方面作了探索，S R Jeffery等[5]提出了可擴展的傳感器數(shù)據(jù)管道清洗方法，利用傳感器的時空特性對RFID數(shù)據(jù)流進行清洗；Lee Chun-Hee等[6]提出了基于時間間隔布隆過濾器(Time Interval Bloom Filter，TIBF)算法，清洗RFID數(shù)據(jù)流僅需很少的內(nèi)存且錯誤率(Error Rate，ER)很低；劉云恒等[7]運用最大熵特征選擇機制對RFID數(shù)據(jù)流進行清洗，在降低清洗成本的前提下提高清洗策略的準(zhǔn)確性.以上研究注重RFID數(shù)據(jù)流的清洗算法的準(zhǔn)確性，卻忽略了清洗效率.現(xiàn)實中要根據(jù)不同的應(yīng)用場景，從具體應(yīng)用出發(fā)選用合適的清洗算法，從而保證RFID數(shù)據(jù)清洗的精確度和時效性.

筆者針對船聯(lián)網(wǎng)中RFID原始數(shù)據(jù)存在冗余的問題，提出一種基于矩陣型布隆過濾器的船聯(lián)網(wǎng)RFID數(shù)據(jù)清洗(MBF-IRCD)算法，實現(xiàn)對船聯(lián)網(wǎng)應(yīng)用系統(tǒng)中的RFID原始數(shù)據(jù)進行清洗，刪除其中冗余數(shù)據(jù)，獲取規(guī)范化數(shù)據(jù)，為船聯(lián)網(wǎng)上層應(yīng)用系統(tǒng)提供有效的數(shù)據(jù)支持，為業(yè)務(wù)決策提供有力的信息保障.

2 基于矩陣型布隆過濾器的船聯(lián)網(wǎng)RFID數(shù)據(jù)清洗

2.1 矩陣型布隆過濾器

布隆過濾器 (Bloom Filter，BF)是由二進制向量和哈希函數(shù)組成的一種高效靜態(tài)的數(shù)據(jù)結(jié)構(gòu)，可快速判斷元素是否在某數(shù)據(jù)集中.[8]BF是一種靜態(tài)的數(shù)據(jù)結(jié)構(gòu)，存在一定的ER和數(shù)據(jù)刪除困難的缺點.當(dāng)持續(xù)地插入新元素時，BF的ER會不斷增大，最壞的情況是ER為100%[9].若采用傳統(tǒng)BF對RFID數(shù)據(jù)流這種動態(tài)的數(shù)據(jù)集進行處理，則需要動態(tài)調(diào)整BF，重新計算BF的全部元素，這顯然是不科學(xué)的.

引用矩陣?yán)碚摱x矩陣型BF(Matrix BF,MBF)并以此表示動態(tài)數(shù)據(jù)集S.該數(shù)據(jù)結(jié)構(gòu)具有矩陣型位空間s×m,擁有d+1個哈希函數(shù)hi(i=0,1,…,d)，其中h0的范圍為{1,2,…,s}，h1，h2,…,hd的范圍為{1,2,…,m}.h0用于確定元素插入的行，其他函數(shù)將該行對應(yīng)的位賦值為1.

由于船聯(lián)網(wǎng)的感知層RFID原始數(shù)據(jù)中存在大量冗余數(shù)據(jù)，需經(jīng)過處理才能供船聯(lián)網(wǎng)的上層應(yīng)用系統(tǒng)使用，因此在RFID數(shù)據(jù)清洗的過程中，可能因誤報而造成一些重要的數(shù)據(jù)被刪除，導(dǎo)致輸出的數(shù)據(jù)不完整，從而使RFID系統(tǒng)所感知的世界與真實世界不一致；也可能產(chǎn)生漏報錯誤，導(dǎo)致輸出的數(shù)據(jù)流中仍有大量的冗余數(shù)據(jù)存在，達不到數(shù)據(jù)清洗的目的.

2.2 RFID冗余數(shù)據(jù)的判定

RFID數(shù)據(jù)流可以表示成一個序列S={s1,s2,…,sn}，任意一個si可以用一個三元組模型d(TID,RID,Time)表示,其中RID為RFID系統(tǒng)閱讀器EPC標(biāo)識編碼，TID為標(biāo)簽EPC標(biāo)識編碼，Time標(biāo)識標(biāo)簽被感知的時間戳.RFID數(shù)據(jù)流中，對于數(shù)據(jù)x，當(dāng)且僅當(dāng)存在數(shù)據(jù)y,且滿足y.TID=y.TID,x.Time-y.Time≤τ(τ為具體應(yīng)用設(shè)定的一個較小的時間段)，x.Time>y.Time,則判定數(shù)據(jù)x是冗余數(shù)據(jù).RFID冗余數(shù)據(jù)可分局部冗余和全局冗余.在滿足上述條件下，若x對應(yīng)的標(biāo)簽持續(xù)不斷被1個標(biāo)簽讀取到，即x.RID=y.RID,則x為局部冗余數(shù)據(jù);若x所對應(yīng)的標(biāo)簽被多個閱讀器讀到，即x.RID≠y.RID,則x是全局冗余數(shù)據(jù).RFID數(shù)據(jù)冗余具有傳遞性.對于RFID數(shù)據(jù)x和y，若存在zS，且滿足x.TID=y.TID，z.TID=x.TID，x.Time-z.Time≤τ,z.Time-y.Time≤τ，則可由S中x是z的冗余數(shù)據(jù)且z是y的冗余數(shù)據(jù)推斷出x也是y的冗余數(shù)據(jù).

2.3 基于MBF的船聯(lián)網(wǎng)RFID數(shù)據(jù)清洗算法

由于RFID標(biāo)簽只在感知區(qū)才可被檢測，且冗余數(shù)據(jù)是根據(jù)位置及時間聚簇的，因此利用時間信息可以測RFID的冗余數(shù)據(jù).在MBF引入了2個時間因素Starttime和Interval,其中Starttime 為第i行的開始時間，Interval為第i行與第i+1行開始的時間間隔.根據(jù)標(biāo)簽的感知時間即可判定數(shù)據(jù)是否冗余.這種優(yōu)化的BF能適應(yīng)動態(tài)數(shù)據(jù)集，非冗余數(shù)據(jù)不會被清洗掉，即不會有消極讀錯誤問題，但有可能把冗余數(shù)據(jù)保留并輸出，即具有有限的積極讀錯誤問題.

MBF-IRDC冗余數(shù)據(jù)清洗算法首先要在MBF中保存每個單元的開始時間和時間間隔.若只有1個哈希函數(shù),則1個RFID標(biāo)簽對應(yīng)過濾器的1個單元；若RFID數(shù)據(jù)x非冗余，當(dāng)x(其TID為1)被讀取時，設(shè)置其對應(yīng)的MBF單元的開始時間是x.Time，結(jié)束時間也是x.Time，則初始時間間隔Interval為0.接下來檢測是否存在1個單元使得MBF[hi(x.TID)].TID=x.TID且x.Time-MBF[hi(x.TID)].Time<τ成立.若存在這樣的單元，說明在設(shè)定的τ時間段內(nèi)該標(biāo)簽數(shù)據(jù)已剛剛被讀取，則可判定x為冗余數(shù)據(jù).這種計算冗余數(shù)據(jù)的算法是很苛刻的，因為通常只要計算出標(biāo)簽數(shù)據(jù)x是冗余的，則x就一定是冗余數(shù)據(jù).當(dāng)然此方法也存在一定的積極讀問題，即極少部分冗余數(shù)據(jù)未被識別出，出現(xiàn)漏報錯誤，漏報率的大小與設(shè)定的時間段τ相關(guān).最后，無論x是否為冗余數(shù)據(jù)，都要更新MBF單元內(nèi)的x.TID，x.Startime及Interval.MBF-IRDC(RFID_Datax)算法的流程如下：

輸入：RFID數(shù)據(jù)x(TID,RID,Time)

輸出：Whetherxis a duplicate

x.Flag=False；∥數(shù)據(jù)x冗余標(biāo)志為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∥數(shù)據(jù)x冗余標(biāo)識為True值,x是冗余數(shù)據(jù)

}

Endfor

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

{MBF[hi(x.TID)].TID=x.TID;∥更新標(biāo)簽ID

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

}

Endfor

End

當(dāng)然,MBF-IRDC算法也會有一定的漏報錯誤，即把冗余數(shù)據(jù)當(dāng)作非冗余數(shù)據(jù)輸出，其漏報ER為(1-(1-1/m)kn′)k-p.其中：p是非冗余數(shù)據(jù)的概率；m是位數(shù)組的大小；k是哈希函數(shù)的個數(shù)；n′是設(shè)定的時間段τ內(nèi)的數(shù)據(jù)流非冗余數(shù)據(jù)的數(shù)值.

3 實驗分析

本實驗將模擬傳統(tǒng)BF算法和TIBF算法的船聯(lián)網(wǎng)RFID數(shù)據(jù)流清洗過程.模擬實驗環(huán)境為服務(wù)器和PC機各1臺.PC機配置：i7 6700K CPU，8G內(nèi)存，1T硬盤，Win7 OS.服務(wù)器配置：XEON E5-2609 CPU，8G內(nèi)存，1T硬盤，Linux OS.算法程序?qū)崿F(xiàn)環(huán)境為JDK1.8，Eclipse4.7.2,編程語言為Java.

3.1 實驗設(shè)計

RFID閱讀器的感知范圍大致可劃分為強感知區(qū)、弱感知區(qū)和零感知區(qū)(圖1).在主感知區(qū)范圍內(nèi)，標(biāo)簽被感知的概率很高，被讀取率在95%以上；在弱感知區(qū)范圍內(nèi)，標(biāo)簽被檢測到的概率隨距離的遠(yuǎn)近而線性變化；零感知區(qū)是指閱讀器和標(biāo)簽之間的距離太遠(yuǎn)，標(biāo)簽無法被感知到的區(qū)域.

圖1 RFID閱讀器的感知區(qū)域Fig. 1 RFID Reader's Sensing Area

3.2 結(jié)果

本實驗是驗證數(shù)據(jù)流和不同參數(shù)對MBF-IRDC算法的ER的影響.首先驗證ER與RFID數(shù)據(jù)流的關(guān)系，再驗證ER與不同參數(shù)的關(guān)系.

圖2 數(shù)據(jù)流與ER的關(guān)系Fig. 2 Relationship Between Data Stream and ER

3.2.1 數(shù)據(jù)流與ER的關(guān)系 數(shù)據(jù)清洗算法的錯誤有誤報和漏報2種情況.設(shè)固定位數(shù)組為5×107，k=5，數(shù)據(jù)流與ER的關(guān)系如圖2所示.由圖2可知，3種算法的ER都隨著數(shù)據(jù)流的增大而略有增加.在數(shù)據(jù)流相同的情況下，BF數(shù)據(jù)清洗算法的ER最大，原因是當(dāng)數(shù)據(jù)流足夠大時，全部的單元空間BF幾乎都被填為1；TIBF算法的ER相比BF算法的要小得多,MBF-IRDC算法的ER是最小的，這是因為前兩者的錯誤都含有漏報和誤報錯誤，后者的錯誤只包含很少的漏報.實驗結(jié)果表明，相較于其他算法，MBF-IRDC算法能更好地適應(yīng)RFID數(shù)據(jù)流的動態(tài)特征，且ER非常小.

3.2.2 不同參數(shù)與ER的關(guān)系 設(shè)數(shù)據(jù)流為5×107，位數(shù)組為m,τ時間內(nèi)非冗余數(shù)為n′，哈希函數(shù)個數(shù)為k.

(1)位數(shù)組與ER的關(guān)系.設(shè)n′,k值不變時，ER與m的關(guān)系如圖3所示.從圖3可知：BF算法的ER并沒有隨著m的變化而出現(xiàn)明顯變化；MBF和TIBF算法的ER隨著m的變化而發(fā)生明顯變化，m增大，ER明顯減小.3種算法中MBF的ER最小，可見MBF-IRDC算法能以較小的存儲空間來快速刪除RFID數(shù)據(jù)中的冗余，從而提高數(shù)據(jù)清洗效率.

(2)其他參數(shù)與ER的關(guān)系.當(dāng)m，n′，k都變化時，實驗結(jié)果如圖4所示.從圖4可知：當(dāng)k不變時，ER隨著m/n′的變化而變化，兩者近似成反比；當(dāng)k≈(m/n′)×ln 2時，ER取最小值，如m/n′=6，k=4,m/n′=5，k=3，m/n′=4，k=3等情況.雖然ER受多種因素影響，但是當(dāng)k≈(m/n′)×ln 2時，其值最優(yōu).

圖3 位數(shù)組與ER的關(guān)系Fig. 3 Relationship Between Bit Array Size and ER

圖4 各種參數(shù)與ER的關(guān)系Fig. 4 Relationship Between Parameters and ER

4 結(jié)語

物聯(lián)網(wǎng)可為船舶航運提供強大的支持，因此研究RFID技術(shù)對于船聯(lián)網(wǎng)來說有重要的意義.筆者針對船聯(lián)網(wǎng)環(huán)境下RFID數(shù)據(jù)冗余的問題，設(shè)計了基于矩陣型BF的冗余數(shù)據(jù)的清洗算法，該算法以有限內(nèi)存高效地對RFID數(shù)據(jù)流中的冗余數(shù)據(jù)進行清洗，從而可為船聯(lián)網(wǎng)的上層應(yīng)用提供有效數(shù)據(jù).