基于云架构下分布式数据压缩算法的研究

李慧玲，路璐

（长治学院计算机系，山西长治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—），女，山西长治人，讲师，主要从事云计算、地理信息系统研究。