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

　　0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　當(dāng)觀測(cè)數(shù)據(jù)集向當(dāng)前數(shù)據(jù)集進(jìn)行匯總時(shí),首先會(huì)進(jìn)行EPC編號(hào)的匹配。如果在CurrentData集中不存在這個(gè)EPC編號(hào),則將這條信息存入CurrentData集中;否則將會(huì)進(jìn)行位置信息的匹配,即查找該信息的LocID是否存在于CurrentData集中,如果存在則將計(jì)數(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在一個(gè)物聯(lián)網(wǎng)系統(tǒng)中,實(shí)體epc1的標(biāo)簽在分別在時(shí)刻t1、t2、t3在loc1被讀取到,t4、t5、t6在loc2被讀取到,epc2的標(biāo)簽在時(shí)刻t7、t8在loc1被讀取到,此時(shí)Observation集的內(nèi)容如表1所示。則當(dāng)運(yùn)行完CDG算法之后,CurrentData集合中的內(nèi)容如表2所示。

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

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

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

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

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

　　定義3RFID數(shù)據(jù)子路徑。對(duì)于兩條路徑tracex與tracey,如果對(duì)于任意按序的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非主路徑。

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

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

　　本部分對(duì)該三層存儲(chǔ)模型及其數(shù)據(jù)匯總算法進(jìn)行實(shí)驗(yàn)驗(yà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語(yǔ)言編寫。實(shí)驗(yàn)主要分析算法的時(shí)間性能、數(shù)據(jù)壓縮率、數(shù)據(jù)的失真率以及查詢的響應(yīng)時(shí)間。

　　2.1實(shí)驗(yàn)數(shù)據(jù)

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

　　2.2算法的時(shí)間性能

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

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

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

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

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

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

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

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

　　DL=lost_colums/N(3)

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

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

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

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

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

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

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

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

　　3 結(jié)語(yǔ)

　　本文建立了一種針對(duì)RFID數(shù)據(jù)的三層壓縮存儲(chǔ)模型,并給出了相應(yīng)的數(shù)據(jù)層的數(shù)據(jù)匯總算法。對(duì)數(shù)據(jù)匯總算法的復(fù)雜度分析及實(shí)驗(yàn)數(shù)據(jù)分析,表明本文提出的三層數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)可以有效地壓縮數(shù)據(jù),具有較低的時(shí)間復(fù)雜度和較少的查詢響應(yīng)時(shí)間,同時(shí),存儲(chǔ)模型的第三層壓縮數(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.