李慧玲，路璐

（長治學(xué)院計(jì)算機(jī)系，山西長治046011）

?

基于云架構(gòu)下分布式數(shù)據(jù)壓縮算法的研究

李慧玲，路璐

（長治學(xué)院計(jì)算機(jī)系，山西長治046011）

針對如何使云計(jì)算中存儲過程更高效化這一問題，文章提出了分布式數(shù)據(jù)壓縮算法。理論分析和仿真實(shí)驗(yàn)表明，該算法較之現(xiàn)有算法擁有更高的壓縮比、更快的壓縮速度、更小的均方誤差和數(shù)據(jù)失真，并且可以根據(jù)用戶網(wǎng)絡(luò)的快慢做出相應(yīng)的調(diào)整，達(dá)到最優(yōu)的壓縮方案。

云計(jì)算；預(yù)測編碼；壓縮感知；數(shù)據(jù)壓縮

引言

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

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

文章針對云架構(gòu)實(shí)時(shí)存儲的特點(diǎn)，提出了分布式壓縮編碼的方案，該方案結(jié)合了預(yù)測編碼和壓縮感知兩種算法的優(yōu)點(diǎn)，使用戶得到了更快的云存儲服務(wù)。理論分析和仿真實(shí)驗(yàn)可知，該方案擁有更高的壓縮比、更快的壓縮速度、更小的均方誤差和數(shù)據(jù)失真。

1　數(shù)據(jù)壓縮理論

1.1預(yù)測編碼技術(shù)

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

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

預(yù)測值：

預(yù)測誤差：

預(yù)測誤差記為MSE，

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

1.2壓縮感知

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

壓縮感知采用波形數(shù)目遠(yuǎn)小于信號維數(shù)的采樣信號對信號f進(jìn)行欠采樣。得到的采樣信號的數(shù)目m遠(yuǎn)小于原始信號f的維數(shù)n。所以壓縮感知在采樣的同時(shí)實(shí)現(xiàn)了對信號的壓縮。

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

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

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

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

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

2　分布式壓縮方法

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

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

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

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

圖1　算法流程

3.仿真實(shí)驗(yàn)

3.1MATLAB介紹

本算法在MATLAB環(huán)境下實(shí)現(xiàn)。MATLAB環(huán)境最早在20世紀(jì)70年代出現(xiàn)，到20世紀(jì)90年代，MATLAB已成為國際控制界的標(biāo)準(zhǔn)計(jì)算軟件[15]。

3.2實(shí)驗(yàn)數(shù)據(jù)和硬件環(huán)境介紹

實(shí)驗(yàn)用數(shù)據(jù)是由Naval Research Lab提供的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)集[16]，其中包含大量的網(wǎng)絡(luò)數(shù)據(jù)信息，這些數(shù)據(jù)種類繁多。

實(shí)驗(yàn)使用硬件運(yùn)行環(huán)境為聯(lián)想Y410P筆記本電腦，其CPU為IntelRi5-4200MQTM4CPU、內(nèi)存為4.00GB、操作系統(tǒng)為Ubuntu9.02。

3.3算法間性能對比

對數(shù)據(jù)分別采用預(yù)測編碼、壓縮感知和分布式壓縮算法進(jìn)行處理，其壓縮性能如圖（2），其中預(yù)測多項(xiàng)式為二階，時(shí)間片段為0.01 s。

圖2　三種算法間性能對比

由圖（2）可以看出，文章提出的分布式壓縮算法結(jié)合壓縮感知和預(yù)測編碼技術(shù)的優(yōu)點(diǎn)，在壓縮性能方面比單種算法有較大的提高

3.4時(shí)間片段大小對比

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

實(shí)際上，該算法的目的就是尋找使得運(yùn)算時(shí)間加數(shù)據(jù)傳輸時(shí)間最小的算法。

文中分別對時(shí)間片段為0.01 s、0.05 s、0.1 s三種長度進(jìn)行了仿真，預(yù)測多項(xiàng)式為1階線性預(yù)測，網(wǎng)絡(luò)帶寬為1 M，數(shù)據(jù)上傳速度平均134.5 kb/s。實(shí)驗(yàn)結(jié)果如圖（3）。

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

圖3　時(shí)間片段不同性能對比

3.5預(yù)測階數(shù)對比

預(yù)測算法采用不同階數(shù)的多項(xiàng)式，則運(yùn)算時(shí)間不同，壓縮后的數(shù)據(jù)量也不同，預(yù)測多項(xiàng)式階數(shù)越高，壓縮性能越好，同時(shí)運(yùn)算時(shí)間也就越長，階級越小則結(jié)果相反。

現(xiàn)使用分布式壓縮算法對數(shù)據(jù)進(jìn)行壓縮，預(yù)測多項(xiàng)式為2，3，4階，時(shí)間片段為0.05 s，其結(jié)果如圖（4）所示。

圖4　預(yù)測多項(xiàng)式不同階數(shù)性能對比

從實(shí)驗(yàn)結(jié)果中可以看出，預(yù)測多項(xiàng)式為二階時(shí)，運(yùn)算速度雖然很快，但是壓縮后數(shù)據(jù)量較大，受到網(wǎng)絡(luò)帶寬的影響，壓縮性能較差。預(yù)測階數(shù)為4時(shí)，運(yùn)算耗時(shí)明顯增加，導(dǎo)致了壓縮時(shí)實(shí)性較差。當(dāng)然，壓縮性能還需要根據(jù)網(wǎng)絡(luò)帶寬的大小來決定，在當(dāng)前帶寬下采用3階預(yù)測多項(xiàng)式效果是比較理想的。

當(dāng)網(wǎng)絡(luò)帶寬改變?yōu)? M時(shí)，采用2，3，4階預(yù)測多項(xiàng)式壓縮結(jié)果如圖（5）所示。

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

由圖可知當(dāng)帶寬較小時(shí)，采用階數(shù)較高的預(yù)測多項(xiàng)式壓縮性能更好，而帶寬較大時(shí)，可采用低階預(yù)測多項(xiàng)式來提高算法壓縮速率，用戶可根據(jù)本地網(wǎng)絡(luò)帶寬來調(diào)整算法，達(dá)到最高效的目的。

4　結(jié)論

文章提出了分布式數(shù)據(jù)壓縮算法用來去除冗余數(shù)據(jù)，保證了云計(jì)算的高效性。無論是理論上還是實(shí)驗(yàn)上都證明，文中的方案比傳統(tǒng)的數(shù)據(jù)壓縮算法性能有明顯的提高。云存儲采用的分布式數(shù)據(jù)存儲，適當(dāng)?shù)娜哂嗍潜匾?，因?yàn)槿哂鄶?shù)據(jù)分散存儲可以提高系統(tǒng)的抗摧毀性，處理好數(shù)據(jù)的冗余度，能夠用最少的投入得到最多的回報(bào)是下一步的研究方向。

［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］郝永志,陳俊杰.基于數(shù)據(jù)壓縮的無線傳感器網(wǎng)絡(luò)節(jié)能方法［J］.華中科技大學(xué)學(xué)報(bào)(自然科學(xué)報(bào)),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

（責(zé)任編輯張劍妹）

TP391.5

A

1673-2014（2016）02-0017-04

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

2015—10—24

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