基于三層存儲模型的RFID數據壓縮存儲方法

　　0 引言

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

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

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

　　故本文根據RFID數據的特點,提出了RFID三層數據存儲模型,并給出了相應數據層的數據匯總算法。

　　1 RFID數據壓縮存儲模型

　　為了更好地區別與闡述當前數據與歷史數據,給出RFID歷史數據的定義。

　　定義1RFID歷史數據。RFID歷史數據為在某一特定事件驅動前的RFID數據,該特定事件與具體的RFID系統應用相關。

　　例如在一個超市RFID系統之中,一個物品在被賣給消費者之后,它之前被閱讀器掃描得到的數據被稱為歷史數據。而在一個物流監控系統當中,在物品離開物流系統最終到達零售商店中之后,之前它在物流中產生的數據稱為歷史數據。如圖1所示。

圖片圖1RFID歷史數據的產生

　　本文采用了三層存儲結構,并給出了相應的數據匯總方法,以達到數據壓縮的目的。本文的存儲模型結構如圖2所示。

圖片圖2三層存儲模型結構

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

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

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

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

　　下面給出當前數據層的匯總算法:

　　算法1當前數據集(Current Data Gather, CDG)匯總算法。

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

　　輸出當前數據集CurrentData{EL,LocID, TS, TE,Count}。

　　例1在一個物聯網系統中,實體epc1的標簽在分別在時刻t1、t2、t3在loc1被讀取到,t4、t5、t6在loc2被讀取到,epc2的標簽在時刻t7、t8在loc1被讀取到,此時Observation集的內容如表1所示。則當運行完CDG算法之后,CurrentData集合中的內容如表2所示。

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

　　1.2臨時數據層模型

　　臨時數據層是中間數據層,其主要工作是將當前數據層中的位置點信息轉化為路徑信息進行存儲,以達到壓縮存儲的目的。為了便于描述,下面給出RFID數據路徑的定義。

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

　　為了更好地闡述路徑之間的關系,下面給出RFID數據子路徑與主路徑的定義。

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

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

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

　　例4對例3中的TempData集合執行HDG算法之后,History集中的內容如表5所示。

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

　　2.1實驗數據

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

　　2.2算法的時間性能

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

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

　　2.3算法的數據壓縮率

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

　　圖片圖4數據壓縮率

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

　　2.4數據的失真率

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

　　DL=lost_colums/N(3)

　　其中:lost_colums表示已經失效的數據條數,N表示總的數據條數。

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

圖片圖5數據的失真率

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

　　2.5查詢的響應時間

　　分別在本文提出的三層模型與原始數據集下運行1000條標準查詢語句來檢驗模型的查詢響應時間,實驗結果如圖6所示。

圖片圖6查詢的響應時間

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

　　3 結語

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

　　參考文獻:

　　[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.