基于特征向量的物聯網大數據壓縮算法*

郭雷勇

0 引 言

目前，無線射頻技術已經廣泛應用于倉儲管理、供應鏈管理、醫療、圖書管理中。然而，這些過程中將會產生龐大的數據集。通過深入挖掘研究這些數據集，可以從中發現一些業務趨勢變化，有利于加深理解并改善商業流程。如果在使用這些數據前對其進行預處理（如先對其壓縮），將會更有效地深入挖掘。本文以設計無線射頻物流倉儲中間件項目的過程為例進行分析。

1 無線射頻特征選取及數據壓縮

如何確定特征向量表示一個標簽在讀取過程中的性質，在目前的研究領域缺乏統一認識。不同的應用選取的特性對結果影響很大。因此，對無線射頻數據進行分析檢測前，需要找到最能體現標簽讀取過程的特征。此外，原始標簽數據集中包含多條重復記錄，數據規模達到成百吉字節，甚至達到太字節，處理壓力非常大。為了提高數據的處理效率，分析前一般都需要對無線射頻數據進行預處理[1]。

在無線射頻的生命周期中，通過對業務流程進行梳理，發現很多物品往往都是一整批運輸的。在供應鏈中，越往上游，貨物量越大，數據越集中，而下游階段的數據則呈現分散趨勢。在無線射頻數據集中，很多貨物的地點（Location）、時間（Time）屬性是一致的，即這些貨物以同樣的時間進入同樣的地點，最后再一起離開該地點。

另外，由于無線射頻技術對環境的敏感性，在考慮標簽在整個供應鏈的生命周期中，各地的倉庫環境、閱讀器的廠商等因素差異，其閱讀器的位置、擺放角度等不同，都可能影響無線射頻數據讀取的特性。因此，基于全局數據的無線射頻孤立點所受影響太多，準確性將大大降低，且難以準確表示孤立點的本質，不具有實際應用的意義。另外，如果直接對全局數據集進行孤立點挖掘，數據量龐大，也無法提供實時的數據挖掘[2-3]。借鑒文獻[4-5]數據立方的思想，本文希望可以對海量數據根據某種特性進行壓縮，以更快的方式檢測其中的有效數據，以更準確地挖掘出孤立點所象征的意義，同時大大減少數據計算的規模。

本文對數據進行壓縮，根據無線射頻的業務時間段進行操作，只記錄標簽首次讀取的時間Time_in、最后離開的時間Time_out以及在這段時間內的讀取次數。通過這種方式減少了大量的重復數據，而又保證信息不丟失。標簽的讀取強度是一個能體現標簽讀取過程的特征，本文用SS表示，其取值范圍為（0～100）。SS值越大，表明信號越強。由于無線射頻技術本身的內在敏感性，信號強度往往與貨物的性質（金屬非金屬、液體等）、標簽所貼的商品位置及與閱讀器所處的位置相關。越貼近閱讀器，信號越強；而與閱讀器距離越遠，信號越弱。

2 算法思路

基于以上原因，本文提出按照每個標簽的讀取的實際間隔Time_duration、在該段時間內讀取次數tagCnt以及標簽讀取時的平均信號強度SSavg作為無線射頻標簽的特征。本文以三元組＜Time_duration,tagCnt,SSavg＞代表標簽在讀取過程中的特征向量空間，其中讀取時間間隔Time_duration=Time_in-Time_out，標簽在讀取過程中的平均信號強度為SSavg：

特征選取如圖1所示。

圖1 數據集選取

tagCnt表示該段時間內標簽的讀取次數，SSi表示第i次讀取的信號強度。

通過數據按照上述特征過濾壓縮后，形成X={x1,x2…xn-1,xn}數據集，其中x代表一個標簽。下面將具體講述如何對原始標簽數據進行壓縮。

具體方法如下：

（1）假設在無線射頻中間件獲取的標簽數據流均以四元組方式存在 ＜ EPC,L ocation,T ime,SS＞，其原始標簽記錄如下：

（2）給定閱讀器的位置信息Location，根據業務時段，選取間隔的起始時間T_Start和結束時間T_End。根據三個特性對數據進行過濾，即只有滿足閱讀器位置信息Location一致，讀取時間T_Start≤Time≤T_End的標簽記錄才會被聚合到同以個集合中。因此，會形成多個數據集聚類Cluster。經過聚集分類并壓縮后的數據集，可以以四元組 ＜ EPC,T ime _ Duration,t a gCnt,S Savg＞ 形式表示每個標簽的壓縮結果。聚類后的標簽數據集如表1所示。

表1 聚集分類后的標簽數據集

至此，通過對標簽數據的壓縮處理，大大減少了數據處理的規模。對于每個標簽ID，均可用＜Time_duration,tagCnt,SSavg＞三元組表征標簽讀取過程的特征。每個聚類作為一個局部數據集，單獨進行孤立點的數據挖掘。

3 算法實現

下面將具體介紹海里無線射頻數據壓縮算法的實現流程和偽代碼。

首先給出數據壓縮處理的算法實現，數據均以＜EPC,Location,Time,SS＞的形式存在。根據給定的Location、起始時間T_Start和結束時間T_End 3個屬性，將數據聚類處理。最后，按照＜EPC,Time_duration,tagCnt,SSavg＞格式輸出數據集。

算法實現流程，如圖2所示。根據標簽三元組進行聚類，為每個聚類單獨創建哈希表，然后獲取標簽記錄，再判斷原始數據是否讀取完成；如果數據讀取完成，則將每個哈希表作為一個聚類輸出，作為檢測的數據集；否則，繼續讀取下一條數據。讀取數據后需要判斷在哈希表是否已有該數據，如果已經存在，只需要記錄讀取次數和時間；否則，不僅需要記錄讀取次數和時間，還需要把新的數據插入到哈希表。

圖2 無線射頻數據壓縮算法流程

下面給出數據壓縮算法的偽代碼實現：

輸入：原始數據集RawDataSet(EPC, Location,Time,SS)，設定的閱讀器Location，有效的讀取的時間間隔Time_Start和Time_End

輸出：經過數據壓縮后cleanDataSet(EPC,Time_duration,tagCnt,SSavg)

方法：

//用哈希表儲存每個標簽數據TagNode的記錄

Table←Empty HashTable;

for each item in Raw DataSet

if(item.Location！=Location||item.currentTime＜Time_Start||item.currentTime＞Time_End)//如果標簽的數據流

//不在指定的位置及有效時間間隔內，則丟棄

drop item;

continue;

endif

if item.epc exists in HashTable

then//更新標簽的平均信號強度

HashTable[epc].SS=(HashTable[epc].

tagCnt*SS+item.SS)/tagCnt+1

HashTable[epc].tagCnt+= 1;

HashTable[epc].tLastRead=

item.currentTime;

else//首次讀到標簽TagNode.epc=item.epc;TagNode.tFirstRead=TagNode.tLastRead=item.currentTime;

TagNode.tagCnt=1;

Add TagNode to HashTable

endif

endfor

for each Record in Table//將哈希表中的每條記錄輸出

Time_duration=Record.tLastRead-Record.tfirstRead;

Add (EPC, Time_Duration, tagCnt,SSavg) to Clean DataSet;

endfor

4 實驗仿真與分析

針對本文設計的壓縮算法，特設計如下實驗。主要的實驗工具是Visual Studio 2005與Matlab 7.70。

4.1 實驗數據集來源

本實驗壓縮實驗的數據集是按照＜EPC,Location,Time,SS＞四元組生成的數據集，其中EPC、Location兩個屬性按照均勻分布生成數據，標簽到達時間Time服從泊松分布，平均讀寫強度則按照均值μ=0.75、方差σ=0.05的高斯分布生成數據。按照一定的比例，重復生成該數據。

4.2 數據集壓縮實驗

本實驗按照500、1 000、5 000、20 000、50 000、100 000生成6組原始的無線射頻數據集，得到數據壓縮前后的數據對比，如表2、圖3所示。

表2 原始數據集與壓縮后數據對比

從表3、圖3的實驗結果來看，當原始數據集數據規模較小時，數據的壓縮效果并不明顯；當數據規模不斷增大時，壓縮效果開始顯現；當數據到達100 000時，大概可獲得5倍的壓縮率。從實驗結果來看，本算法對海量無線射頻數據的壓縮處理是有效的，符合預想結果。另外，需要注意的是，本算法的數據集使用隨機函數生成，所以實際的壓縮效果取決于重復數據的個數。經過反復測試，它的壓縮效果仍然比較理想。

圖3 在不同數據規模下數據集的壓縮效果

5 結 語

本文主要討論在海量無線射頻數據中挖掘孤立點的難點及意義，針對海量的標簽數據，按照標簽的位置信息、讀取時間進行數據聚類，大大減少了數據處理量；通過對無線射頻數據讀取過程特性的研究，提出了以標簽在讀寫時間段、在該段時間內的讀寫次數以及標簽平均讀取信號強度作為標簽的特征向量。仿真結果與算法分析表明，隨著數據量的增加，提出的壓縮算法的壓縮效果越來越好。

[1] Yunsik S,MyoungHwan J,Yong-W,et al.Tag Localization in a Two-dimensional RFID Tag Matrix[J].Future Generation Computer Systems,2017,76(11):384-390.

[2] PENG Zi-ran,WANG Guo-jun,JIANG Hua-bin,et al.Research and Improvement of ECG Compression Algorithm Based on EZW[J].Computer Methods and Programs in Biomedicine,2017,145(07):157-166.

[3] Seyed N A,Suriyaprakash N, Shobha V.A Novel Test Compression Algorithm for Analog Circuits to Decrease Production Costs[J].Integration,the VLSI Journal,2017,58(06):538-548.

[4] HAN Jia-wei,Hector G.Warehousing and Mining Massive RFID Data Sets[C].ADMA,2006:1-18.

[5] Arun K B,Mamata J,Sri K K.Warehouse Efficiency Improvement Using RFID in a Humanitarian Supply Chain:Implications for Indian Food Security System[J].Transportation Research Part E: Logistics and Transportation Review,2018,109(01):205-224.