传感器网络中分布式数据压缩方法

—88—无线传感器网络中分布式数据压缩方法王英杰，鞠时光，阴晓加(江苏大学计算机科学与通信工程学院，江苏 镇江 212013)摘 要：针对无线传感器网络节点能量受限及传感数据在时间与空间方向上都存在冗余的问题，基于5/3整数小波方法，提出分布式时空数据压缩算法以及参数包复制策略。

仿真实验结果表明，与提升格式的小波方法相比，该方法不但减少时间与空间方向上的数据量，同时延长1/4左右网络生命周期。

关键词：无线传感器网络；小波变换；数据压缩；网络寿命Distributed Data Compression Method in Wireless Sensor NetworksWANG Ying-jie, JU Shi-guang, YIN Xiao-jia(College of Computer Science & Telecommunication Engineering, Jiangsu University, Zhenjiang 212013, China)【Abstract 】Aiming at the problem of the limited power of sensor and redundancy of sensor data, this paper proposes a distributed space-time wavelet transform method which is based on the 5/3 integer wavelet and a package duplication strategy. Simulation experimental results show that the proposed method effectively reduces amount of data on the time and space orientation, and extends the network life by one-quarter compared with wavelet compression method using lifting.【Key words 】WSNs; wavelet transform; data compression; network life计 算 机 工 程 Computer Engineering 第36卷 第18期Vol.36 No.18 2010年9月September 2010·网络与通信·文章编号：1000—3428(2010)18—0088—03文献标识码：A中图分类号：TP 393.11 概述无线传感器网络主要用来对目标区域的数据进行收集，并采用多跳、无线射频以及光、声通信等方式进行数据传输。

传感、无线等技术的成熟推动了无线传感器网络的发展，使得传感器节点可以自组地构成无线传感器网络，各种应用相继出现。

大量的传感器节点被部署到传感器区域，通过无线通信技术将传感信息发送到处理中心。

由于无线传感器网络中数据量大，使得靠电池供电的节点对通信的开销难以承受，因此对传感数据的压缩传输必不可少[1]。

关于数据压缩传输，国内外已经有了一些研究。

文献[2]提出无线传感器网络的分布式压缩传输模型，其利用压缩数据与未压缩数据之间的相关性进行数据的解压。

文献[3]提出基于贪婪算法和聚合代价的单Sink 节点最优分布式数据压缩算法。

文献[4]提出基于管道思想的网内数据压缩方法，即将传感器数据缓存在网络中，根据指定的延迟值等待合适时间后再传输。

文献[5]提出用小波变换算法来压缩每个节点的数据，利用提升小波消除节点之间的相关性。

本文提出一种在时间与空间上进行小波数据压缩的方法，将计算量分散在各个节点之中，并且充分考虑了参数数据包复制问题，减少了节点能量的消耗与传输错误率。

由于变换期间需要来回传递参数，为了降低参数传递过程中产生的错误以及信息量，本文提出一种参数包复制策略，减少了错误的发生。

仿真实验表明，本文的数据压缩方法较流行的提升格式的小波方法[6]减少了节点数据的传输量以及错误率，有效地延长了网络的生命周期。

2 算法原理本节主要介绍5/3分布式小波的原理，并利用5/3小波，提出一种时空方向上的数据压缩方法，该方法将传感器收集到的数据组成矩阵形式，并且提出了避免参数传递过程中出现错误的包复制策略。

2.1 5/3整数小波典型的无线传感器网络通信模式是多个传感器节点向 一个汇聚节点发送数据，所有传感器节点转发收到的数据，形成一个树型分簇网络结构。

因其信息量巨大，但单个节点的能量又极其有限，必须使用分布式小波算法，使小波变换的计算量分散在各个节点之间，由多个节点共同参与完成小波分解计算。

Harr 小波变换虽然简单，但是压缩效果不好，更常用的是5/3整数小波变换[7]。

5/3整数小波变换公式如下：(0)(0)(1)(0)22221(1)(1)(1)(0)122142n n n n n nn n S S d S d d S S ++−⎧⎡⎤+=−⎪⎢⎥⎪⎣⎦⎨⎡⎤+⎪=++⎢⎥⎪⎣⎦⎩(1) 分布式小波变换分为3个步骤：(1)分裂。

将传感器采集到的数据(S 0,S 1,…,S n )分成2组，即偶数节点S 2n 和奇数节点S 2n +1。

(2)预测。

偶数节点(2n )将采集到的数据传给后面的奇数节点(2n +1)，同时偶数节点(2n +2)也将采集到的数据传给前面的奇数节点(2n +1)。

然后，在(2n +1)节点处进行预测计算：(0)(0)'(0)222212n n nn S S d S++⎡⎤+=−⎢⎥⎣⎦(2)其中，'n d 称为小波细节系数，其值比起(2n +1)节点的原始信息少了很多。

基金项目：国家自然科学基金资助项目(60773049)作者简介：王英杰(1984－)，男，硕士研究生，主研方向：无线传感器网络；鞠时光，教授、博士生导师；阴晓加，硕士研究生 收稿日期：2010-01-30 E-mail ：yingjie.1@—89—(3)更新。

奇数节点(2n +1)将计算得到的小波细节系数'nd 传给偶数节点2n 和2n +2，然后，在偶数节点完成更新计算：''''12122n nn nd d S S −⎡⎤+=++⎢⎥⎣⎦ (3) 至此，子集{}''''''1212,,,,,,,n n S S S d d d ""取代了原始数据集{}12,,,n S S S "。

最后，把更新后的{}'''12,,,n S S S "看成新的序列，重新划分为偶数序列'2n S 与奇数序列'21n S+重新进行以上步骤，完成二级小波分解系数{}'',n n S d 。

将以上步骤递归下去将得到各层小波分解系数。

将小波系数传达基站后，在基站中进行小波逆变换，得到原始数据。

2.2 分布式时空小波压缩算法(DCMWT)无线传感器网络靠无数的传感器节点连续不断地传感数据，然而，这些传感器节点收集到的数据既庞大又复杂，并且在时间和空间上面都具有很大的冗余性。

因此，有必要采取相应的措施从时间和空间上降低数据冗余，减少传感器节点的能量消耗。

文献[7]提出了一种基于环模型的时空小波变换，并利用了DB2小波进行实验。

本文提出了基于分布式5/3整数小波的时空数据压缩算法，利用参数包复制机制进一步减少数据冗余以及错误的发生。

假设传感器网络中某个簇内的n 个节点为S 0,S 1,…,S n ，其中，第i 个传感器节点收到的随时间到达的数据序列为,col i C ，它的矩阵列的形式为()T,col 0,1,1,i i i N i C C C −=+++C "，这里每个传感器读取N 个数据，其中，,j i C 表示第i 个传感器节点的第j 个数据。

这样，所有的n 个传感器节点的数据就构成了一个n N ×的矩阵：0,00,10,11,01,11,100col 1col (1)col ,0,1,(,,)n n n N N N n C C C C C C C C C C C C −−−⎛⎞⎜⎟⎜⎟=++=⎜⎟⎜⎟⎜⎟⎝⎠C """###" (4) 其中，矩阵的列表示某个传感器节点收到的随时间到达的N 个数据；矩阵的行表示多个传感器节点在某个时刻的N 个数据。

然后，可以对式(4)进行相应的列变换与行变换，即时间变换与空间变换。

下面利用式(1)对式(4)进行列变换，变换如下式所示：1110,00,10,11111,01,11,111110,00,10,11111,01,11,1n N N N n n N N N n S S S S S S d d d d d d −−−−−−−−−−⎛⎞⎜⎟⎜⎟⎜⎟⎜⎟=⎜⎟⎜⎟⎜⎟⎜⎟⎝⎠"###""###"C (5) DCMWT 算法对式(1)进行列变换，在时间方向上压缩数据，由于进行列变换后数据量减少很多，也为下文的行变换节省了很多节点之间传输数据时的能量消耗。

接着利用式(1)对式(5)进行行变换，变换为式(6)：11110,00,00,10,111111,01,01,11,1211110,00,00,10,111111,01,01,11,1s d sdn n s d sd N N N n N n s d sdn n s d sd N N N n N n S S S S S S S S d d d d d d d d −−−−−−−−−−−−−−−−⎛⎞⎜⎟⎜⎟⎜⎟⎜⎟=⎜⎟⎜⎟⎜⎟⎜⎟⎝⎠"####""####"C (6) 经过行变换后的小波系数相比原始数据少了很多信息，在网络上面传输将会节省很多通信的开销。

进行行变换后，从式(6)中提取式(7)：1110,00,10,11111,01,11,111111,01,11,1s s sn ss sn s s s N N N n S S S S S S S S S −−−−−−⎛⎞⎜⎟⎜⎟=⎜⎟⎜⎟⎜⎟⎝⎠""###"C (7)对式(7)依照上面同样的方法进行列变换与行变换，如此递归下去，最后得到各级小波系数。

所得小波系数较传感器节点采集的原始数据数据量少了很多，很大程度上减少网络通信能量的开销，这对于能量严重受限的传感器网络至关 重要。

2.3 参数包复制策略网络模型中对于小波变换后的小波系数进行打包传输是必不可少的，然而，数据包在网络中传输又难免进行包的复制，在这里称其为参数包复制。