基于三層存儲模型的RFID數(shù)據(jù)壓縮存儲方法

　　0 引言

　　所謂物聯(lián)網(wǎng)就是物物相連的互聯(lián)網(wǎng),是指通過射頻識別、紅外感應(yīng)器等信息傳感設(shè)備把物品與互聯(lián)網(wǎng)相連接,進(jìn)行信息交互和通信的一種網(wǎng)絡(luò)[1-3]。物聯(lián)網(wǎng)這個概念在1999年被提出之后,并沒有引起人們廣泛的關(guān)注,由于其包含技術(shù)的復(fù)雜性,社會普遍質(zhì)疑物聯(lián)網(wǎng)大規(guī)模實施的可行性。但隨著構(gòu)建物聯(lián)網(wǎng)的電子芯片費用的不斷降低與電子標(biāo)簽(Electronic Product Code, EPC)技術(shù)的日漸成熟[4-5],物聯(lián)網(wǎng)的普及逐漸變得切實可行。

　　普遍認(rèn)為,射頻識別(Radio Frequency IDentification, RFID)的特性為:時空關(guān)聯(lián)性、海量性、不確定性、實時性等[6-7]。隨著物聯(lián)網(wǎng)技術(shù)的日益發(fā)展,如何有效并快速地存儲與查詢RFID數(shù)據(jù)逐漸引起人們的重視。如果電子標(biāo)簽被放置在每個物品上,那么類似于沃爾瑪這樣的大型超市將會在一天之內(nèi)得到7TB左右的數(shù)據(jù),所以像Oracle、IBM、Teradata和一些其他的數(shù)據(jù)庫公司不得不考慮將RFID信息整合到企業(yè)級數(shù)據(jù)庫中[8]。

　　在物聯(lián)網(wǎng)被廣泛應(yīng)用的背景下,RFID數(shù)據(jù)存儲與管理逐漸成為物聯(lián)網(wǎng)技術(shù)的研究方向之一[9-10]。之前的研究工作主要采用單一數(shù)據(jù)層的方式存儲RFID數(shù)據(jù),較少涉及壓縮存儲與歷史數(shù)據(jù)的處理。如文獻(xiàn)[11]首次給出了一般意義上的RFID數(shù)據(jù)存儲結(jié)構(gòu)與數(shù)據(jù)管理的體系結(jié)構(gòu),但是其結(jié)構(gòu)并不能完全適應(yīng)當(dāng)前的RFID應(yīng)用系統(tǒng);文獻(xiàn)[12]提出了一個以位置為關(guān)鍵字的RFID數(shù)據(jù)存儲模型,并給出了在這個模型之上的查詢語句,但是對于歷史數(shù)據(jù)卻并沒有進(jìn)行處理;文獻(xiàn)[8]提出了一個簡單的RFID數(shù)據(jù)壓縮方法,其主要思想是將一個固定的編號來代表一連串情境相關(guān)的EPC編號(如一箱牛奶等),但是對于這個編號的尚未完成的劃分方式卻是實施這一方法的阻礙;文獻(xiàn)[13]提出了一個RFID數(shù)據(jù)壓縮方法,該方法的主要思想是通過合并與連接那些用戶不感興趣的路徑片段進(jìn)行路徑的語義壓縮,但是如何確定哪些路徑用戶不感興趣是一個很大的難題。

　　故本文根據(jù)RFID數(shù)據(jù)的特點,提出了RFID三層數(shù)據(jù)存儲模型,并給出了相應(yīng)數(shù)據(jù)層的數(shù)據(jù)匯總算法。

　　1 RFID數(shù)據(jù)壓縮存儲模型

　　為了更好地區(qū)別與闡述當(dāng)前數(shù)據(jù)與歷史數(shù)據(jù),給出RFID歷史數(shù)據(jù)的定義。

　　定義1RFID歷史數(shù)據(jù)。RFID歷史數(shù)據(jù)為在某一特定事件驅(qū)動前的RFID數(shù)據(jù),該特定事件與具體的RFID系統(tǒng)應(yīng)用相關(guān)。

　　例如在一個超市RFID系統(tǒng)之中,一個物品在被賣給消費者之后,它之前被閱讀器掃描得到的數(shù)據(jù)被稱為歷史數(shù)據(jù)。而在一個物流監(jiān)控系統(tǒng)當(dāng)中,在物品離開物流系統(tǒng)最終到達(dá)零售商店中之后,之前它在物流中產(chǎn)生的數(shù)據(jù)稱為歷史數(shù)據(jù)。如圖1所示。

圖片圖1RFID歷史數(shù)據(jù)的產(chǎn)生

　　本文采用了三層存儲結(jié)構(gòu),并給出了相應(yīng)的數(shù)據(jù)匯總方法,以達(dá)到數(shù)據(jù)壓縮的目的。本文的存儲模型結(jié)構(gòu)如圖2所示。

圖片圖2三層存儲模型結(jié)構(gòu)

　　圖2中各層之間通過相應(yīng)的數(shù)據(jù)匯總算法進(jìn)行數(shù)據(jù)的匯總。本文RFID數(shù)據(jù)流的傳遞順序是:閱讀器層→當(dāng)前數(shù)據(jù)層→臨時數(shù)據(jù)層→歷史數(shù)據(jù)層，并且高層數(shù)據(jù)層的數(shù)據(jù)量比低層數(shù)據(jù)層的數(shù)據(jù)量小。

　　在一個RFID系統(tǒng)中,將從閱讀器得到的原始數(shù)據(jù)的集合稱為觀測數(shù)據(jù)集。其數(shù)據(jù)形式為Observation{E,L,T},其中E表示被掃描的物品的EPC編碼,L表示物品被掃描的地點,T表示物品被掃描的時間。其具體形式如表1所示。

　　隨著時間的推移,觀測數(shù)據(jù)集中的數(shù)據(jù)量將異常龐大,這時需要將觀測數(shù)據(jù)向當(dāng)前數(shù)據(jù)層進(jìn)行匯總。當(dāng)前數(shù)據(jù)層的數(shù)據(jù)形式為CurrentData{EL,LocID,TS,TE,Count},其中TS與TE分別表示該物品在這個位置第一次被掃描到的時間與最后一次被掃描到的時間,Count代表該物品在TS到TE這個時間段內(nèi)在該位置出現(xiàn)的次數(shù)。

　　當(dāng)觀測數(shù)據(jù)集向當(dāng)前數(shù)據(jù)集進(jìn)行匯總時,首先會進(jìn)行EPC編號的匹配。如果在CurrentData集中不存在這個EPC編號,則將這條信息存入CurrentData集中;否則將會進(jìn)行位置信息的匹配,即查找該信息的LocID是否存在于CurrentData集中,如果存在則將計數(shù)增加,否則同樣將這條信息存入CurrentData集中。

　　下面給出當(dāng)前數(shù)據(jù)層的匯總算法:

　　算法1當(dāng)前數(shù)據(jù)集(Current Data Gather, CDG)匯總算法。

　　輸入最低粒度集Observation{E,L,T}。

　　輸出當(dāng)前數(shù)據(jù)集CurrentData{EL,LocID, TS, TE,Count}。

　　例1在一個物聯(lián)網(wǎng)系統(tǒng)中,實體epc1的標(biāo)簽在分別在時刻t1、t2、t3在loc1被讀取到,t4、t5、t6在loc2被讀取到,epc2的標(biāo)簽在時刻t7、t8在loc1被讀取到,此時Observation集的內(nèi)容如表1所示。則當(dāng)運行完CDG算法之后,CurrentData集合中的內(nèi)容如表2所示。

　　通過這個例子可看出：經(jīng)過CDG算法之后得到的數(shù)據(jù)集要比原始的RFID數(shù)據(jù)集的數(shù)據(jù)量小,即有效地進(jìn)行了數(shù)據(jù)壓縮。

　　1.2臨時數(shù)據(jù)層模型

　　臨時數(shù)據(jù)層是中間數(shù)據(jù)層,其主要工作是將當(dāng)前數(shù)據(jù)層中的位置點信息轉(zhuǎn)化為路徑信息進(jìn)行存儲,以達(dá)到壓縮存儲的目的。為了便于描述,下面給出RFID數(shù)據(jù)路徑的定義。

　　定義2RFID數(shù)據(jù)路徑。RFID數(shù)據(jù)路徑是一串有序的位置點編號的集合,形如PathIDi{locIDj|j∈N},其中,PathIDi表示路徑的編號,locIDj表示出現(xiàn)在這條路徑上的位置點。

　　為了更好地闡述路徑之間的關(guān)系,下面給出RFID數(shù)據(jù)子路徑與主路徑的定義。

　　定義3RFID數(shù)據(jù)子路徑。對于兩條路徑tracex與tracey,如果對于任意按序的loci∈tracex(其中i∈N),loci∈tracey,則說明tracex為tracey的子路徑,記為tracex→tracey。

　　定義4RFID數(shù)據(jù)主路徑。RFID數(shù)據(jù)主路徑是指不包含父路徑的路徑,即如果tracei為主路徑,則不存在tracej∈Trace,使得tracei→tracej。反之,我們稱不是RFID數(shù)據(jù)主路徑的路徑為RFID非主路徑。

　　對于路徑的編號采用改進(jìn)的二進(jìn)制哈夫曼編碼,其主要思想是將路徑的前n/2個碼位置為其父路徑編碼的前n/2個碼位,而后n/2個碼位為其自身的自然序號。一條RFID非主路徑編號編碼如式(1)所示。

　　例4對例3中的TempData集合執(zhí)行HDG算法之后,History集中的內(nèi)容如表5所示。

　　本部分對該三層存儲模型及其數(shù)據(jù)匯總算法進(jìn)行實驗驗證。本文的硬件環(huán)境是:2.1GHz的Intel Core 2 Duo CPU,2.0GB的主存,160GB的硬盤。軟件環(huán)境是:操作系統(tǒng)為Windows XP,編程環(huán)境為JDK1.6,數(shù)據(jù)匯總算法采用Java語言編寫。實驗主要分析算法的時間性能、數(shù)據(jù)壓縮率、數(shù)據(jù)的失真率以及查詢的響應(yīng)時間。

　　2.1實驗數(shù)據(jù)

　　由于場地與應(yīng)用的限制,本文采用了模擬的數(shù)據(jù)集,即通過程序模擬了物品跟蹤系統(tǒng)產(chǎn)生的105條RFID數(shù)據(jù)。為了更全面地驗證算法的可靠性,將這105條數(shù)據(jù)劃分為4個子集,分別包含1×104,2×104,3×104和4×104條數(shù)據(jù),分別記為數(shù)據(jù)集1、數(shù)據(jù)集2、數(shù)據(jù)集3和數(shù)據(jù)集4。

　　2.2算法的時間性能

　　本文分別針對上述4個數(shù)據(jù)集進(jìn)行3層數(shù)據(jù)匯總算法,實驗得到算法消耗時間如圖3所示。

　　通過圖3可看出：隨著數(shù)據(jù)集數(shù)據(jù)量的增大,時間消耗將隨之增加,并且大部分的時間均消耗在第3層數(shù)據(jù)匯總即HDG算法之中,因此可以考慮改進(jìn)該算法以進(jìn)一步降低時間開銷。

　　2.3算法的數(shù)據(jù)壓縮率

　　數(shù)據(jù)的壓縮率是指每個算法運行結(jié)束之后得到的數(shù)據(jù)集的大小與原始數(shù)據(jù)集的大小之比。本實驗的數(shù)據(jù)壓縮率如圖4所示。

　　圖片圖4數(shù)據(jù)壓縮率

　　通過圖4可看出：HDG算法的數(shù)據(jù)壓縮率最高,TDG算法次之,而CDG算法的數(shù)據(jù)壓縮率最低。同時,隨著數(shù)據(jù)集的不斷增大,這3個算法的數(shù)據(jù)壓縮率變化不大,即這3個算法的數(shù)據(jù)壓縮率趨于固定值。

　　2.4數(shù)據(jù)的失真率

　　由于只有第3層數(shù)據(jù)匯總即HDG算法采用的是有損壓縮方法,所以本實驗過程只考慮HDG算法的失真率。RFID數(shù)據(jù)失真率(Data Lost, DL)的計算公式為:

　　DL=lost_colums/N(3)

　　其中:lost_colums表示已經(jīng)失效的數(shù)據(jù)條數(shù),N表示總的數(shù)據(jù)條數(shù)。

　　通過在4個數(shù)據(jù)集上運行3層匯總算法之后,實驗得到HDG算法的失真率如圖5所示。

圖片圖5數(shù)據(jù)的失真率

　　從圖5可看出：隨著數(shù)據(jù)集數(shù)量的增大,HDG算法的失真率將會變小,這是由于主路徑數(shù)量的增加隨著數(shù)據(jù)集的增大而趨于緩慢所造成的。該實驗數(shù)據(jù)表明,隨著主路徑數(shù)據(jù)量的增加,使用主路徑替代原始路徑將使數(shù)據(jù)更加真實。

　　2.5查詢的響應(yīng)時間

　　分別在本文提出的三層模型與原始數(shù)據(jù)集下運行1000條標(biāo)準(zhǔn)查詢語句來檢驗?zāi)Ｐ偷牟樵冺憫?yīng)時間,實驗結(jié)果如圖6所示。

圖片圖6查詢的響應(yīng)時間

　　從圖6可看出：隨著數(shù)據(jù)集數(shù)據(jù)量的不斷增加,查詢的響應(yīng)時間也相應(yīng)增大。但是在不同的數(shù)據(jù)集中,運行在原始數(shù)據(jù)之上的查詢響應(yīng)時間與運行在本文提出的模型數(shù)據(jù)之上的查詢響應(yīng)時間基本相同,說明本文數(shù)據(jù)的壓縮存儲結(jié)構(gòu)對數(shù)據(jù)的查詢影響并不明顯。

　　3 結(jié)語

　　本文建立了一種針對RFID數(shù)據(jù)的三層壓縮存儲模型,并給出了相應(yīng)的數(shù)據(jù)層的數(shù)據(jù)匯總算法。對數(shù)據(jù)匯總算法的復(fù)雜度分析及實驗數(shù)據(jù)分析,表明本文提出的三層數(shù)據(jù)存儲結(jié)構(gòu)可以有效地壓縮數(shù)據(jù),具有較低的時間復(fù)雜度和較少的查詢響應(yīng)時間,同時,存儲模型的第三層壓縮數(shù)據(jù)具有較低的數(shù)據(jù)失真率,說明該模型可適應(yīng)大規(guī)模RFID數(shù)據(jù)集。

　　參考文獻(xiàn):

　　[1]GUSTAVO R, MARIO M, CARLOS D. Early infrastructure of an Internet of things in spaces for learning [C]// Proceedings of the 8th IEEE International Conference on Advanced Learning Technologies. Piscataway, NJ: IEEE Press,2008:381-383.

　　[2]HU YING, SUNDARA S, CHORMA T, et al. Supporting RFID-based item tracking applications in Oracle DBMS using a bitmap datatype [C]// Proceedings of the 31st International Conference on Very Large Data Bases. New York: ACM

　　[3]COCCI R, TRAN T, DIAO Y, et al. Efficient data interpretation and compression over RFID streams [C]// Proceedings of the 24th International Conference on Data Engineering. Piscataway, NJ: IEEE Press, 2008:1445-1447.