无线传感器网络中基于小波的自适应多模数据压缩算法.doc

第3期朱铁军等：无线传感器网络中基于小波的自适应多模数据压缩算法53无线传感器网络中基于小波的自适应多模数据压缩算法朱铁军1，林亚平1,2，周四望2，徐小龙1（1. 湖南大学 计算机与通信学院, 湖南 长沙 410082；2. 湖南大学 软件学院, 湖南 长沙 410082）摘 要：基于数据的多模性，设计了一个基于小波的自适应多模数据压缩算法。在给定的相关度阈值的条件下，算法能自适应地对数据调整分类，对相关数据采用最小二乘估计进行拟合，把特征数据抽象成一个矩阵，利用小波变换去除数据的空间和时间相关性。理论分析和仿真实验表明，新算法能够有效地去除数据之间的多模相关性和同种数据的空间和时间相关性，新算法有效地提高了压缩比，降低了网络的能耗。关键词：无线传感器网络；小波变换；多模数据；数据压缩中图分类号：TP393 文献标识码：A 文章编号：1000-436X(2009)03-0048-06Adaptive multiple-modalities data compression algorithm using wavelet for wireless sensor networksZHU Tie-jun 1, LIN Ya-ping1,2, ZHOU Si-wang2 , XU Xiao-long 1(1. College of Computer and Communication, Hunan University, Changsha 410082, China;2. Software College, Hunan University, Changsha 410082, China)Abstract: Wireless sensor networks usually have limited resources, such as energy, bandwidth and processing and so on. And they cant match the transmission of a large number of data. So, it is necessary to perform in-network compression of the raw data sampled by sensors. The data sensor node collected normally have multiple-modalities pertinence. Multiple-modalities pertinence refers to the different types of data which the same node sampled have some correlation. A adaptive multiple-modalities data compression algorithm using wavelet was designed. In a given threshold of the correlation, the data can be adaptive classified using this algorithm. the relevant data can be estimated using the least square estimation. The characteristics data are abstracted as a matrix, then can be exploited the spatial and temporal corrections using wavelet transform. Theoretically and experimentally, the proposed algorithm can effectively exploit the correlation of the data, the compression ratio of the algorithm has improved. Effectively, it can provide a significant reduction in energy consumption. Key words: wireless sensor networks; wavelet transform; multiple-modalities data; data compression1 引言收稿日期：2008-06-21；修回日期：2008-11-20基金项目：国家高技术研究发展计划（“863”计划）基金资助项目（2006AA01Z227）；湖南省科技厅科技计划基金资助项目（2007FJ4157）Foundation Items: The National High Technology Research and Development Program of China (2006AA01Z227); The Planned Science and Technology Project of Hunan Province(2007FJ4157)无线传感器网络是由一组在地理上广泛分布、相互之间能够利用无线信道进行通信的传感器节点组成的，每个节点都可以作为接收节点与一个或者多个其他节点进行协作，从而测量环境参数、辨别系统状态、收集实时数据、提取增值信息等。这种特殊的网络系统覆盖范围广、组网灵活、即抛即用，能够广泛应用于军事、环境、家庭、空间探索和灾难拯救等各种领域1。传感器节点体积微小，通常携带能量十分有限的电池，而且部署区域环境复杂，有些区域甚至人员不能到达，所以传感器节点通过更换电池的方式来补充能源是不现实的。传感器节点消耗能量的模块包括传感器模块、处理器模块和无线通信模块。随着集成电路工艺的进步，处理器和传感器模块的功耗变得很低，绝大部分能量消耗在无线通信模块上，传输1bit数据所消耗的能量大约相当于执行1 000条CPU指令2，因此，大量的研究工作围绕最小化传输能耗而展开。由于无线传感器网络节点自身具有一定的计算能力，在进行数据采集或者数据查询的过程中，一部分的计算工作可以从接收节点转移到中继节点上，通过中继节点对数据的处理来减少传输的数据量，从而达到降低网络能耗的目的。部署在自然环境中的传感器节点一般会同时监测多种数据，比如：湿度、温度、光强等，已有文献指出这些数据是可能存在一定相关性的3。本文将节点采集到的不同类型的数据之间具有的某种相关性称为多模相关性。因此，消除数据的多模相关性能够极大地减少传感器节点之间的通信量，同时也能够节省大量的能量。由于小波变换对流数据具有良好的压缩性能4，而传感数据具有流数据的特点，因此，本文提出了一种基于小波的自适应多模数据压缩算法，并采用OMNeT+平台，对提出的压缩算法进行仿真实现。模拟实验表明，在对实时性要求不高的网络应用下，该算法能够减少传输的数据量，从而减少整个系统的能量开销。全文其余部分组织如下：第2节详细描述本研究的相关工作；第3节阐述了基于小波的自适应多模数据压缩算法的主要思想；第4节分析仿真结构、仿真实例及仿真结果；第5节是结束语。2 相关工作及预备知识传感器网络中数据压缩算法目前已有一些基础性的工作，文献5设计了一个用于结构化监测的WISDEN系统。WISDEN先在单个传感器节点内对数据进行小波压缩，然后将其传送到基站进行集中式的处理以减少通信开销与网络延时。RACE6针对单个传感器节点产生的时间序列信号，给出了一种压缩位率自适应的Haar小波压缩算法，通过阈值来选择重要的小波系数，从而调整压缩位率，并且根据小波系数树构建了坡度误差树(gradient error tree)，可以由阈值来估计重构的误差范围。上述算法在单个节点内运行，通过挖掘时间相关性减少冗余数据的传输，但没有考虑邻近节点间数据的空间相关性。 文献7,8分别提出了基于5/3小波提升方案和Haar小波的分布式压缩算法，这些算法通过在邻近的节点间交换信息，在数据传送到汇聚节点前分布式挖掘网络中数据的空间相关性，有效地减少了冗余数据的传输。文献9提出了一种基于环模型的分布式时空小波数据压缩算法。该算法将传感器网络中的数据抽象为一个矩阵，将时间相关性与空间相关性映射为该矩阵的小波列变换与行变换，以同时挖掘传感器网络中数据的时间和空间相关性。以上的文献都没有考虑不同类型的数据之间具有的某种相关性。图1是Intel-伯克利大学联合研究实验室的一个节点在一段时间内采集温度和湿度的关系图，由图1可以看出，一个节点在一段时间内采集的湿度数据随温度的升高而降低。图1 温度与湿度变化的关系基于上面的一些事实，提出了一个基于小波的自适应的多模数据压缩算法。为便于建模，现做如下假设。1) 无线传感器网络各节点均匀分布于X-Y平面，各传感器节点可以通过GPS或者其他方法获取自身的地理位置信息，并保持静止。 2) 所有的传感器节点具有相同的通信半径，传输任意单位比特数据的平均能耗均相同，存在于彼此通信半径之内的两节点互为邻居节点。 3) Sink（基站）位置固定，簇头将处理后的数据传输至Sink。4) 所有传感器节点的配置相同，且每个节点有唯一的节点号来标识自己。本文将要用到的基本概念如下。均方差MSE:设原始信号S=X(t) | t = 1,2,3,k, S* = X*(t) | t = 1,2,3,k为一个估计，则该估计的MSE为压缩比为3 基于小波的自适应多模数据压缩算法传感器节点将采集到的多个不同类型的数据存在不同程度的相关性，数据之间的相关程度反映了数据变化趋势的相似性。为便于讨论，先给出形式化概念。定义1（数据相关度）。 设X1 = x1,1,x1,2,x1,n和X2 = x2,1,x2,2,x2,n分别为数据向量S1和S2中的具有n-数据点的子序列，则子序列X1和X2的相关度为其中， 。定义2 设X1和X2是2个数据向量，对于给定的正数，如果，则称向量X1和X2是-强相关，否则是-弱相关。定义3 （特征向量）设S是由多个数据向量构成的序列集合，如果存在，对于以及给定的正数，满足，则称为集合的特征序列，为相关序列。在上述概念的基础上，以下将对算法进行详细的阐述。3.1 地理成簇利用飞机投放等方法将N个节点部署到检测区域中之后，使用相关定位技术（如GPS）确定各个节点的位置。Sink将检测区域划分为K个虚拟网格，虚拟网格的边长为的正方形区域(其中r为节点的通信半径)，该区域内任意2个节点之间的距离最大为，即任意2个节点均在彼此的有效通信半径之内，因此，同一个虚拟网格中的节点互为邻节点。从每个虚拟网格中选取一个节点作为簇头：Hh1，Hh2,Hhk其中。这些计算均在Sink中完成，此后将这些成簇信息进行广播。节点收到信息后进行对比，确定自己是否为簇头以及所属簇ID（如图2所示）。图2 地理成簇3.2 算法的主要实现在这里，假设簇头在接收到簇内节点发过来的N个数据，每个数据包含M个不同种类的观测值，那么总共的数据量为NM，每一列代表一个同一类型的观测值，分别用X1,Xm表示。先要对这M个序列进行预处理。计算M个不同观测值之间的相关度，把相关度大于某个阈值的变量放到同一组，算法的描述如下。算法1 数据的预处理算法：Pretreatment( )输入：M个不同种类观测的集合X1, X2, Xm,相关度的阈值。输出：相关度大于阈值的序列集合数组。1) for i from 1 to m-12) if flagi = 03) Flagi = 1 and insert i to the new set4) for j from i+1 to m5) if(corr(Xi, Xj) )6) flagj = 1 and insert j to the set which i is belong to 7) return sets array对观测的变量进行预处理以后，数组的每一项是一个集合。每个集合中的第一项是特征序列，其余的是相关序列，然后，对每个集合进行处理，因为同一个集合中的数据是-强相关的，可以用一条拟合的直线来描述它们之间的关系，如对于这种形式，可以采用最小二乘估计的方法来对曲线进行模拟，对于a和b，可以用下面的公式求解 传感器节点在一定时间内检测的同一种数据具有空间和时间相关性，对这些数据进行小波变换，而Harr小波是小波变换中的一种简单易行的方法。对于长度为的信号，将求平均与细节应用到 中。记 ，则多级Harr小波变换的分解过程和重构过程可用图3表示。图3 传感器数据多级小波变换过程利用上述快速Harr算法进行3次小波分解后的空间频率结构如图4所示。小波变换的特点为：传感数据经变换后，绝大部分能量集中在低频系数上，高频部分的大量系数的值趋于0。在图4中，原始传感信号被分解为4个部分，其中，H0,H1,H2是高频部分，L2是低频部分。小波变换具有多尺度空间频率分辨能力和时频局域化的特点，对压缩阵发性的流数据非常有效。对于高频部分可以采用量化的方法来提高压缩率，量化阶段是对小波变换后得到的高频系数和低频系数进行阈值处理，将低于某个阈值的数变为0。对于量化后的小波系数，其高频部分的大部分系数为0。游程编码是通过形图4 传感器数据被分解后的频率结构成串的字符、串的长度及串的位置来进行编码的方法，其实现简单，其压缩率取决于数据流中的重复字符出现的次数和平均游程长度。基于小波的自适应多模数据压缩算法流程如图5所示。图5 基于小波的自适应多模数据压缩算法流程总的算法的描述如下。基于小波的自适应多模数据压缩算法。输入：传感器节点采集的多种数据；输出：编码后的数据。1) 对输入的数据进行预处理Pretreatment( )；2) 对预处理后的集合数组进行扫描，如果扫描的集合项所包含的元素个数大于1，那么利用最小二乘估计的方法对这个集合中除第一个以外的数据进行变化；将拟合得到的数据单独发送给Sink节点；3) 对集合中的第一个元素利用小波变换，然后在误差容许的范围内对变换后的数据进行量化处理；4) 利用游程编码的方法对变化后的数据进行编码。4 模拟实验与分析实验数据是Intel-伯克利大学联合研究实验室利用传感器节点采集的数据，采集的一共有4种数据：温度、湿度、光强和电压10。实验测试平台和主要参数如下。1)CPU为Intel P4 3.06GHz和内存为1GB的计算机。2)操作系统为Windows XP。3)利用面向对象的开源仿真软件OMNeT+3.3 Win32(exe)11和基于其上支持无线和移动仿真框架mobility-fw2.0p312，建立了一个网络Network Compress。在一个300300规则的监测区域随机部署200个传感器节点。假设虚拟网络为100100，则可分为9个簇。4)存储方式为Sun公司的MySql5.1数据库。现进行如下几个方面的实验。4.1 比较不同算法的压缩比在实验中每个节点同时发送4种不同数据的数据包，相关度阈值分别取0.75、0.8、0.85、0.9、0.95、1.0。在给定不同相关度阈值的情况下，研究了相关度与算法的平均压缩比关系，使用以下算法分别进行实验：1)使用文献7中分布式小波压缩算法，简记为DWC；2)使用文献9中的基于环模型的小波数据压缩算法，简记为RWC算法；3)使用自适应的多模数据压缩算法(adaptive multiple-modalities data compression algorithm)，简记为AMMC算法。实验研究了不同算法的压缩比，图6表明，在不同的相关度阈值下，AMMC算法的压缩比最大，DWC算法最低，RWC介于两者之间。其主要原因是：AMMC算法去除了各个不同种类数据之间的相关性和同种类数据之间的空间和时间相关性；RWC去除了同种数据的时间和空间相关性。实验表明，AMMC算法的压缩比随着相关度阈值的升高而降低，主要原因是相关度阈值增大，相关的数据的数量减少，则需要更多的特征向量来表示信息；DWC和RWC没有考虑不同数据的多模相关性，所以，它们的压缩比与相关度阈值没有关系。4.2 比较运行不同算法的网络能耗降低传感器节点的能量消耗可以延长网络生命周期，是传感器网络设计的重要目标。发送同样的数据消耗能量的多少是描述一个算法好坏的重要指标。同样选取相关度阈值为0.75、0.8、0.85、0.9、0.95、1.0，每个节点发送500个数据的情况下，整个网络消耗的总能耗。由于簇头是轮流选举的，网络内的节点是均匀的消耗能量，所以只要根据网络消耗的总能量就可以判别算法的优劣。3种算法的能耗图如图7所示，由图7可以看出，AMMC算法在相关度小于0.95时的能耗最少，在相关度阈值为1时，相关数据的数量很少，而小波变换计算需要耗能，这当然也包含了Sink节点的计算能耗。图6 比较算法的压缩比图7 比较算法消耗的能量4.3 比较不同算法的均方差(MSE)相关度反应了2个向量变化规律的相似程度，2个数据流的相关度越高，变化规律越相似。尽管小波变换是无损变换，但将系数小于给定的阈值进行归零化处理和曲线拟合，则还原的序列和原序列会存在一定的误差；这3个算法为有损压缩。在此，研究了相关度阈值与MSE之间的关系。阈值还是选取上面的6个阈值，分别用3种算法压缩后重构生成新序列的均方差。如图8所示，AMMC算法的相对误差大于其余2种算法，主要原因是，特征序列小波变换量化后会存在一定的误差，而相关序列是使用量化处理过的特征序列经过线性拟合还原的，那么误差相对其他2种算法会大些；相关度越高，特征向量和相关向量的相似程度越高，则特征序列更能准确表示与之相关的序列。从总体来看，AMMC算法相对其他2种算法的MSE较大些。在实际应用中，如果需要高精度的数据，可以将相关度阈值调大些，那么数据就会精确些，反之，可以调小些，这就可以节省能耗。比如把相关度阈值设置为1，那么AMMC的MSE和RWC的差不多。图8 比较算法的均方差5 结束语本文提出了一个针对无线传感器网络的基于小波的自适应多模数据压缩算法。该算法能够去除不同类型数据之间的多模相关性和冗余性，而同种数据之间存在时间和空间相关性，该算法将同种数据的抽象成一个矩阵，利用小波变换去除同种数据的空间和时间相关性。理论分析和仿真实验表明，该算法能够很大程度上去除数据之间的相关性，提高了数据的压缩。现在只在模拟平台上实现了这个算法，下一步的主要工作是在MACIZ节点上实现这个算法，在实际中检测这个算法的性能。参考文献：1李建中，高宏. 无线传感器网络的研究进展J.计算机研究与发展，2008，45(1): 1-15.LI J Z, GAO H. Survey on sensor network rearchJ. Journal of Computer Research and Development, 2008，45(1): 1-15.2CHEN M, FOWLER M L. Data compression trade-offs in sensor networksA.Conference on Information Sciences and SystemsC. 2004.3DELIGIANNAKIS A, KOTIDIS Y. Compressing historical information in sensor networksA. Proceedings of ACM SIGMODC. Paris, France, 2004.4成礼智, 王红霞, 罗永. 小波的理论与应用M. 北京: 科学出版社, 2004.CHENG L Z, WANG H X,LUO Y. Wavelet Theroy and ApplicationM.Beijing:Science Press,2004.5XU N, RANGWALA S,CHINTALAPUDI K K. A wireless sensor network for structural monitoringA. Proc of the 2nd Intl Conf on Embedded Networked Sensor SystemsC. New York, 2004. 13-24.6CHEN H M, LI J, MOHAPATRA P. RACE: time series compression with rate adaptivity and error bound for sensor networksA. Proc of the 2004 IEEE Intl Conf on Mobile Ad-Hoc and Sensor SystemsC. Piscataway, 2004. 124-133.7ACIMOVIC J,CRISTESCU R, LOZANO B. Efficient distributed multiresolution processing for data gathering in sensor networksA. Proc of the Intl Conf on