无线传感器网络数据压缩算法研究

刘河　陈宇

摘要：传感器网络中由于节点部署密度大，传感器节点的覆盖区域是相互重叠，因此，容易产生较多的冗余数据。而通过数据压缩能够有效减少冗余数据、最小化传输量、节省节点能量。对无线传感器网络中的数据冗余从时间、空间等角度进行了分析，对应用于传感器网络中的几种典型数据压缩算法进行了分类和比较。

关键词：无线传感器网络； 数据冗余； 数据压缩算法

中图分类号：TP393 文献标识码：A[HT5”H]文章编号：2095-2163（2013）05-0028-03

0引言

传感器节点是一个配备了无线电收发器、微控制器、能量源的信息接收处理单元。因为体积小，同时考虑到成本问题，传感器节点受到有限的带宽、电量和计算能力的限制。对于大规模部署无线传感器节点的网络来说，如何提高节点的能量效率，延长整个WSN寿命是需要解决的首要问题[1]。

对于监测区域内的传感器节点来说，其数据采集行为往往具有：同一个信号可能被不同传感器捕获；对于多维度信息采集，多个传感器的并行采集数据能够形成互补等特点，这些都容易产生冗余数据[2]。

1数据冗余

1.1时间冗余

时间冗余来自于提高精度传感器节点的读数和在传感和通信时承受瞬时故障。时间冗余的应用较为复杂，主要用于无线传感器网络的环境参数频繁变动的场景，传感器节点通过发送连续多个采集报告以提高数据置信水平，这种类型的冗余通常是在视频监视和多代支持基于特定的数据压缩技术的编解码器等应用中采用。时间冗余可以分为：时间感知冗余、时间通信冗余。

1.2空间冗余

空间冗余来自于传感器网络中某个特定地理区域内，多个传感器节点采集的信息出现重叠现象。这种空间冗余产生的目的，主要是为了提供容错或提高测量数据的可靠性以达到一定的安全水平。

空间冗余几乎在任何一个传感器网络部署时都会发生，因为在无线传感器网络的应用中通常需要密集部署节点以保证网络的连通性。从覆盖问题的角度来说，空间冗余可以划分为物理冗余和分析冗余，具体分析如下。

物理冗余是一种非常普遍的技术，通过节点在某一区域的高密度部署用于保证系统的可靠性，尤其是考虑到网络受到安全威胁时，这种冗余非常有必要。当然，由于节点之间距离过近，易造成节点采集的数据具有一定的相似性，而这些数据的产生在无线信道传输过程中无疑会消耗大量的节点能量，因此，需要通过一定的数据融合方法来降低数据冗余度，以节约资源。

分析冗余则是指通过一定的数学模型根据历史监测数据推导出的预估测量值，用于与节点发送过来的实际测量值进行比较，目的是获取出现故障或恶意攻击的节点。通常，当节点数量过多或者数据模型过于复杂时，分析冗余的计算代价太大，[JP2]另外，分析冗余产生的冗余数据与真实的数据本身不一定能完全契合，因此，这种冗余只出现在较少的应用中。

1.3信息冗余

信息冗余则主要是用于信息表示方法上对冗余数据的描述，常常定义为使用冗余数据（例如，特殊bit）来重新构造丢失的信息。因此，信息冗余意味着额外的信息是用来检测和从故障中恢复。奇偶校验位附加到数据块，使误差检测即可以视为一个实例信息冗余。另一个例子是信息冗余擦除码，都是通过使用的信息冗余，无需重传机制即可构造出原始消息。

2数据压缩算法

大量原始数据转发到基站的路途中将很快耗尽所经过节点的能量，导致传感器网络死亡，为了减少数据传输过程的数据量，从而节省网络能量，延长网络生命周期，很多专家学者提出，通过节点间的协作对传感器网络采集到的数据进行网内处理，也就是适当地采用数据压缩方法，使得数据量减少[3]。

2.1数据压缩方法分类

对观测数据的压缩处理，可在传感器节点和基站两端分别采用压缩和解压缩技术。在数据发送前提高编码效率，或者是根据不同应用需求（例如图像特征的信息，直接处理非常复杂）对信息进行数据变换，实现发送数据前的压缩操作。基站收到数据后再进行解压缩，降低传输过程中大量冗余数据造成的能量损耗。

常见的数据压缩方法有：

（1） 压缩编码。按照特定的编码机制利用较少的数据位元（或者其他信息相关的单位）表示信息，从压缩结果来看可以分为有损压缩和无损压缩，由于传感器采集的多数为模拟信息，所以主要采用有损压缩算法。而针对不同的传感器数据特征又可以采用标量数据压缩算法或者矢量数据压缩算法，并根据不同的数据类别选择对应的数据压缩算法。

（2） 汇聚节点处融合。对于覆盖范围较大的传感器网络，源节点到基站之间的数据转发采用多跳方式比点对点直接通信更能节省能耗。转发路径上的节点作为汇聚节点，可以在不丢失信息的前提下通过排序编码丢弃部分于汇聚节点汇合的数据，实现数据压缩。

（3） 依据数据空间相关性。地理位置相邻的传感器节点收集到的数据存在相关性，在多个节点中选取一个有代表性的节点数据，将其完整地发送至基站，而其他节点的数据提取出偏差部分并压缩后发送，基站最后通过压缩数据和未压缩数据之间的相关性进行解压缩来重构得到原始数据。

（4） 依据数据时间相关性。单个传感器节点收集到的数据在时间上可能是相关的，使用例如小波变换等信号处理办法来去除其中的冗余信息，并在保持信号的统计特性的基础上实现数据压缩的目的。

2.2典型的数据压缩算法

文献[4]提出了一种能量高效的分布式线性回归数据采集优化策略，根据同一监测区域附近的传感器节点采集的数据测量值具有极大相关性这一特点，通过构建线性回归模型表示传感器的感知数据。

假设传感器在时间t1，t2，…tm上感知的数据为y1，y2，…ym，则构建满足逼近误差最小δi=Y（ti）-yi的函数Y（函数用多项式表示，Y（t）=

λ1+λ2t+λ3t2+λ4t3）；构建函数模型之后，多个实际测量值仅仅需要在网内传输4个参数值，即λ1、λ2、λ3和λ4即可得到原始数据。为了使估计值的逼近误差δi最小，选定使得逼近误差向量的范数最小为优化目标，即min（‖δ‖=（∑[DD（]m[]i=1[DD）]δ2i）1/2）。另外，文中还提出了回归模型的参数更新方法以采用增量方式更新线性回归系统模型的矩阵和向量参数。该模型大大减少了传感器节点间频繁数据传输带来的通信开销，降低了节点的能量消耗，不足之处在于模型中矩阵的运算量偏大。

文献[5]利用一维Haar小波分解算法，对数据向量通过逐级分解以得到近似分量和细节分量，针对误差‖e‖∞形成小波系数的误差树，再根据小波系数的值和误差限ε来判定哪些节点可以被零化，并通过量化系数的熵编码提高数据的压缩效率，从而减少传输的数据。此外，文中还提出了多属性的误差有界小波数据压缩算法，对每个节点在某时刻采集的多种不同属性的数据进行数据压缩。方案中，首先对数据进行规范化，用二维Haar 小波变换进行全分解；再根据不同属性的感知数据以及同一属性不同时段的数据具有相关性的特点，选出基信号，回归表示其他信号。方案的不足之处在于，基信号挑选算法将不同的属性按相关性分到某个基代表的组中，而为了使得误差越小，需要的基就越多，压缩效果也将变差。另外，将基信号等分分段实现多次回归，但当基分段太多时，却易造成该段回归结果可能会超过规范化误差的结果。

考虑到网络中部署的传感器节点在监测数据行为上存在数据相关性，比如在某些应用中，一个特定区域可能被多个传感器覆盖，这些传感器很可能监测到同一时间，产生相同的数据而造成不必要的能耗上的浪费，文献[6]介绍了一种通过各传感器节点遵循关联机制，来实现网内数据压缩以减少数据量的行为策略。主要步骤为：

（1）网络中包含n个传感器节点，构成集合S={s1，s2，……，sn}，时间片λ根据用户可任意设置大小。每个传感器均有一个大小为B的缓冲池，每经过一个时间片，各传感器节点根据是否监测到事件发生来设置缓冲区入口。

（2）传感器的行为数据在一定的时间间隔后发送至基站，基站通过行为数据获知在这段时间内该节点监测到事件发生的次数。

（3）该网络中的数据约简是借助创建数据收集树实现的，称之为最小的节点的数据收集树（minimum nodes data gathering tree， MNDGT），另外结合分布式的约减机制。MNDGT树中只包含了参与制定传感器关联规则的节点以及与基站距离近的部分节点。

（4）数据收集沿着树形结构从最低层至最高层。在MNDGT最后一级每个叶节点将参与集合发送至双亲节点。双亲节点则根据这些集合来计算所有子节点的交集，并依据一定的规则设置活动节点。

文献[7]提出了一个分布式数据融合算法，其主要思想是在中间节点将传入的多个数据包通过PCA（principal component Analysis）方法将其压缩成一个数据包，再将融合结果发至父亲节点。具体的数据压缩过程是基于多跳网络，即假设网络中的节点需通过多跳方式将采集的数据发至基站，但是最多只能经过两跳，路径可以任意选择且不一定为最短的路径。再将路径上的节点构造成一棵树型结构，基站为该数据结构中的根节点。

文献[8]首先提出了一种具有普遍性的体系结构来减少数据流造成的能量开销和延迟方面的影响，在该体系结构中，把监测节点采集过程中数据的产生（感知流）或是当一个节点转发数据至另一个节点（路由流）视为输入流，当传感器获取过多的样本，并且不能动态校准处理比目前更多的数据处理时，通过应用层对感知流进行数据压缩；根据不同应用的需求，当网络中不需要对过多的数据进行数据转发时，则交给路由层进行数据压缩以避免无法控制的丢包行为。应用层的数据压缩算法主要分为随机采样、居中采样、多元抽样、概要数据等环节，压缩后的数据流如果需要转发给其他节点，则通过网络层进行重新封装后再发给sink节点。

3结束语

在传统的数据传输模式下，无线传感器网络中的各节点如果传输全部的感测信息，将因为大量冗余信息的传输使得能量消耗过大，因此，先对数据进行融合处理再发给基站是非常必要的。本文对时间冗余、空间冗余和信息冗余等方面进行了分析，对数据压缩算法进行了简单的分类，并对几种典型的数据压缩算法进行了分析比较，[JP2]下一步的工作将在这些研究的基础上，提出考虑数据的空间相关的数据压缩算法。