基于云架構下分布式數據壓縮算法的研究

李慧玲，路璐

（長治學院計算機系，山西長治046011）

?

基于云架構下分布式數據壓縮算法的研究

李慧玲，路璐

（長治學院計算機系，山西長治046011）

針對如何使云計算中存儲過程更高效化這一問題，文章提出了分布式數據壓縮算法。理論分析和仿真實驗表明，該算法較之現有算法擁有更高的壓縮比、更快的壓縮速度、更小的均方誤差和數據失真，并且可以根據用戶網絡的快慢做出相應的調整，達到最優的壓縮方案。

云計算；預測編碼；壓縮感知；數據壓縮

引言

云計算的發展歷程經過了四個階段：電廠計算、效用計算、網格計算和云計算[1]。自2006年由Google首席執行官埃里克·施密特在搜索引擎大會上首次提出以來，Google、IBM、Microsoft、Amazon、騰迅、阿里巴巴等知名IT企業都開始大力開發和推進云計算，并推出了自己的云計算服務平臺[2]。

云計算即將互聯網上的資源和服務虛擬化，這些虛擬的資源和服務是由專門的公司負責管理、調度和維護的，而用戶只要付少量的費用就可以使用這些服務。云計算實質就是給用戶提供類似傳統的電力、水、天然氣一樣的按需計費服務[3]。云計算融合了分布式計算、效用計算、虛擬化技術、Web服務等網絡上現有的技術，云計算的目標就是使用戶隨時隨地可以在互聯網上最大限度地使用虛擬資源，處理大規模計算問題，云計算甚至可以讓你體驗每秒十萬億次的運算能力。但標準不統一、過度依賴于網絡帶寬、安全性不高以及數據冗余度較高等問題限制了云計算的進一步發展。

文章針對云架構實時存儲的特點，提出了分布式壓縮編碼的方案，該方案結合了預測編碼和壓縮感知兩種算法的優點，使用戶得到了更快的云存儲服務。理論分析和仿真實驗可知，該方案擁有更高的壓縮比、更快的壓縮速度、更小的均方誤差和數據失真。

1　數據壓縮理論

1.1預測編碼技術

預測編碼技術根據數據間的時間相關性[4-11]，利用前面已有的數據，來預測下一個數據，然后對實際值和預測值之間的差額進行編碼，上傳數據時只發送數據的差額信息集，這樣就降低數據中的冗余信息。預測編碼技術還可以根據工程需要，設定預測階數及編碼結果的比特數，使算法在保證數據準確性的基礎上盡量簡化計算復雜度。

預測是根據前n個數據的測量參數，估計當前數據的測量值，再用測量參數減去預測值得到預測數據與實際數據的差值，這個差值就是需要編碼的內容。x0為當前數據的測量值，表示估計值，同時{ ai|i=1，2，…，n}為預測系數，n為預測階數。

預測值：

預測誤差：

預測誤差記為MSE，

預測多項式階數n越大，預測越準確，所需存儲的數據越短，同時計算復雜度也急劇增加。在現實通信中，緊鄰時間內測量參數方差相對較小，其增量便可由更少的代碼表示，從而減少網絡數據流量。文中分別采用了1，2，3，4階預測多項式進行仿真預測。在本實驗中預測編碼還未涉及大數據量的圖像傳輸，因此文章對于圖像視頻壓縮、一些特殊格式的數據采用壓縮感知算法實現數據壓縮。

1.2壓縮感知

對某一信號f進行采樣實際上就是將該信號同一系列波形進行內積運算。例如：奈奎斯特采樣就是信號f與一組頻率大于2f的脈沖信號的內積。

壓縮感知采用波形數目遠小于信號維數的采樣信號對信號f進行欠采樣。得到的采樣信號的數目m遠小于原始信號f的維數n。所以壓縮感知在采樣的同時實現了對信號的壓縮。

壓縮感知將n維可壓縮信號x∈∑k通過采樣矩陣φ∈Cm,n（m＜＜n）投影到低維空間上，得到m維的采樣向量y∈Rm：

如果信號f在φ域是稀疏的，那么式（5）就可以寫為

其中x為信號f在φ域的系數，A=φφ是一個m×n階的矩陣，稱之為感知矩陣。

定義：對于矩陣φ∈Cm,n（m＜＜n）和所有稀疏信號x∈∑k滿足

的最小數值?k定義為矩陣φ的約束等距常數。如果?k∈(0，1)，就說矩陣φ滿足k階約束等距性。

2　分布式壓縮方法

云計算壓縮存儲需要一種壓縮比高、壓縮速度快的算法，用來去除冗余數據。通常云服務器上接收到的數據在時間空間上是相關的，基于這種時間相關性，文章提出了分布式縮編碼的方法來解決這一問題。

當數據從客戶端向服務器上傳數據前，對數據同時使用預測編碼和壓縮感知的方法進行壓縮，每隔一個時間片段就比較采用兩種不同方法壓縮后數據的大小，將壓縮后數據量小的數據上傳給服務器，文中使用的時間片段為0.01、0.05、0.1s三種。每個片段的數據可以在其開頭字段約定壓縮數法，采用預測編碼時開頭編碼為0，采用壓縮感知算法時開頭編碼為1。

數據上傳到服務器上，主要將時間耗費在數據的壓縮運算及信道傳輸上。采用上述兩種方法運算時間不同，壓縮后得到的數據量不同，因此上傳時間不同。當壓縮數據完成后，對其估算數據傳輸時間TS，傳輸時間為數據量C除以信上傳速度S，再加上運算時間TC，將用時最短的壓縮方法作為該片段壓縮算法。

具體過程如下圖所示（1）。

圖1　算法流程

3.仿真實驗

3.1MATLAB介紹

本算法在MATLAB環境下實現。MATLAB環境最早在20世紀70年代出現，到20世紀90年代，MATLAB已成為國際控制界的標準計算軟件[15]。

3.2實驗數據和硬件環境介紹

實驗用數據是由Naval Research Lab提供的無線傳感器網絡數據集[16]，其中包含大量的網絡數據信息，這些數據種類繁多。

實驗使用硬件運行環境為聯想Y410P筆記本電腦，其CPU為IntelRi5-4200MQTM4CPU、內存為4.00GB、操作系統為Ubuntu9.02。

3.3算法間性能對比

對數據分別采用預測編碼、壓縮感知和分布式壓縮算法進行處理，其壓縮性能如圖（2），其中預測多項式為二階，時間片段為0.01 s。

圖2　三種算法間性能對比

由圖（2）可以看出，文章提出的分布式壓縮算法結合壓縮感知和預測編碼技術的優點，在壓縮性能方面比單種算法有較大的提高

3.4時間片段大小對比

計算機處理數據時，將時間片段劃分為0.01、0.05、0.1 s三種，使用分布式壓縮算法對數據進行壓縮，每經過一個時間片段，就對壓縮后的數據進行對比，上傳數據量小的片段。但是，使用預測算法壓縮數據時，多項式選用不同的階數，一個時間片段內處理的數據量是不同，采用壓縮感知也是這樣，這就出現了單位時間片段內處理后數據量小的原因是處理的數據少，而不是算法性能憂越，壓縮比高。這里給出單位時間壓縮比的定義：

實際上，該算法的目的就是尋找使得運算時間加數據傳輸時間最小的算法。

文中分別對時間片段為0.01 s、0.05 s、0.1 s三種長度進行了仿真，預測多項式為1階線性預測，網絡帶寬為1 M，數據上傳速度平均134.5 kb/s。實驗結果如圖（3）。

由圖（3）可知，如果時間片段分割的太小，數據片段就會非常短，數據的時間空間相關性差，壓縮比不高。如果時間片段太長，數據長度太大，那就幾乎等于只采用了其中一種壓縮算法，而不是文中提出的分布式壓縮算法，壓縮性能得不到明顯提升，時間片段在0.05 s時，算法的壓縮性能最好，時間分段最優解還有待進一步實驗。

圖3　時間片段不同性能對比

3.5預測階數對比

預測算法采用不同階數的多項式，則運算時間不同，壓縮后的數據量也不同，預測多項式階數越高，壓縮性能越好，同時運算時間也就越長，階級越小則結果相反。

現使用分布式壓縮算法對數據進行壓縮，預測多項式為2，3，4階，時間片段為0.05 s，其結果如圖（4）所示。

圖4　預測多項式不同階數性能對比

從實驗結果中可以看出，預測多項式為二階時，運算速度雖然很快，但是壓縮后數據量較大，受到網絡帶寬的影響，壓縮性能較差。預測階數為4時，運算耗時明顯增加，導致了壓縮時實性較差。當然，壓縮性能還需要根據網絡帶寬的大小來決定，在當前帶寬下采用3階預測多項式效果是比較理想的。

當網絡帶寬改變為2 M時，采用2，3，4階預測多項式壓縮結果如圖（5）所示。

圖52　M帶寬下算法性能對比

由圖可知當帶寬較小時，采用階數較高的預測多項式壓縮性能更好，而帶寬較大時，可采用低階預測多項式來提高算法壓縮速率，用戶可根據本地網絡帶寬來調整算法，達到最高效的目的。

4　結論

文章提出了分布式數據壓縮算法用來去除冗余數據，保證了云計算的高效性。無論是理論上還是實驗上都證明，文中的方案比傳統的數據壓縮算法性能有明顯的提高。云存儲采用的分布式數據存儲，適當的冗余是必要的，因為冗余數據分散存儲可以提高系統的抗摧毀性，處理好數據的冗余度，能夠用最少的投入得到最多的回報是下一步的研究方向。

［1］Garg V K.Elements of Distributed Computing［J］. Wiley-IEEEPress,2002,45(2):234-239

［2］Foster I,Kesselman C,Tuecke S.The anatomy of the grid:Enabling Scalable Virtual organizations ［J］.International Journal of High Performance Computing Applications,2001,15(3):200-222

［3］Schoder D,Fischbach K.Peer-to-Peer prospects ［J］.Communications of the ACM,2003,46(2): 27-29

［4］郝永志,陳俊杰.基于數據壓縮的無線傳感器網絡節能方法［J］.華中科技大學學報(自然科學報),2008,36(S1):232-234.

［5］Zhang Chen,Sun Gui-ling,Li Wei-xiang,et al. Research on Datacompression based on Prediction Coding for WSN nodes［C］.InternationForum on InformationandApplications，2009,45(7): 283-286.

［6］E.J.Candes.Compressive sampling［C］Proceedings ofInternationalCongressofMathematicians. Zürich,Switzerland:EuropeanMathematical Society Publishing House，2006.22(5)1433-1452.

［7］E.J.Candes,J.Romberg,T.Tao.Robust uncertaintyprinciples:exact signal reconstruction from highly incompletefrequency information［J］IEEE.T.Inform.Theory,2006,52(2):489-509.

［8］E.J.Candes,T.Tao.Near-optimal signal recovery fromrandomprojections:universalencoding strategies[J].IEEE.T.Inform.Theory,2006,52(12): 5406-5425.

［9］D.L.Donoho.Compressedsensing［J］.IEEE.T. Inform.Theory,2006,52(4):1289-1306.

［10］D.L.Donoho,Y.Tsaig.Fast solution of l1-norm minimizationproblems when the solution may be sparse［R］.DepartmentofStatistics,Stanford University,USA,2008.

［11］E.J.Candes,M.B.Wakin.An introduction to compressivesampling［J］.IEEE.Signal Proc.Mag, 2008,25(2):21-30.

［12］E.J.Candes,T.Tao.Decodingbylinear programming［J］.IEEE.T.Inform.Theory,2005, 51(12):4203-4215.

［13］D.L.Donoho,M.Elad,V.N.Temlyakov.Stable recoveryof sparse overcomplete representations in the presence ofnoise［J］.IEEE.T.Inform.Theory, 2006,52(1):6-18.

［14］S.S.B.Chen,D.L.Donoho,M.A.Saunders. Atomic decompositionby basis pursuit［J］SIAM J. Sci.Comput.1998,20(1):33-61.

［15］周建興.MATLAB從入門到精通［M］.北京:人民郵電出版社,2008.

［16］Yan K Q,Wang S C,Liu C W.A Hybrid Intrusion Detection Systemof Cluster-Based Wireless Sensor Networks［C］.Proceedings of the International Multi Conference of Engineers and Computer Scientists,2009I:956-963

（責任編輯張劍妹）

TP391.5

A

1673-2014（2016）02-0017-04

長治學院校級教改課題“MOOCs+面對面課堂模式下《數據庫技術應用(ACCESS)》課程教學改革”（JY201503）。

2015—10—24

李慧玲（1979—），女，山西長治人，講師，主要從事云計算、地理信息系統研究。