0引言
近年来，随着无线通信、微机电系统、超大规模集成技术 (Very Large Scale Integrated circuits, VLSI )的飞速发展和日益成熟，使得现代传感器具备了强大的感知能力和通信能力，且开启了微型化、智能化、网络化的发展进程，其中最具典型的代表就是无线传感器节点（也称传感器节点）。 这些具有一定感知、计算和通信能力的传感器节点分布在一个特定的区域，通过自组织的方式实时协作地监测、感知并处理网络里的数据，再通过短距离无线通信的方式经多跳将数据传送到汇聚节点(Sink节点)，从而形成了一个集信息感知、信息处理、信息传送于一体的整合网络，并称之为无线传感器网络［1-2］(Wireless Sensor Networks, WSNs)。
WSNs最先在美国军队中得到了广泛的应用并取得了巨大成效。美军远程战场感知系统［3］ (Remotely Monitoring Battlefield Sensor System, REMBASS) 由美国L-3通信公司设计推出，能够全天候地对地面战场实现远程监控，其技术功能主要是实时地探测、分类、定位、报告车辆和人等活动目标的动向。REMBASS最初即应用于上世纪70年代初的越战，当时，美军在北约部队的重要交通运输线—胡志明小道上部署了大量的传感器节点，获得了准确度极高的情报，取得了出众优异的侦查效果。 2001年， DARPA提出了灵巧传感器网络 (Smart Sensor Web, SSW) 计划［4］，于2001-2005财政期间发布实施。SSW的核心思想是在战场上部署大量的传感器节点以收集数据，并对原始数据加以过滤，而后将重要的信息传送到各个数据融合中心，从而得到了一幅由大量信息集结而成的战场全景图。当士兵需要时，即可给其发送相关信息，由此则极大地提高了士兵对战场态势的感知能力。
以数据为中心的WSNs的设计目的就是将数据从网络中传输到汇聚节点(Sink节点)，再进行其后相应的各级处理。因此，如何高效节能地将网络中的数据传输到汇聚节点即成为WSNs研究的关键技术之一。但由于无线传感器网络的存储、计算和通信能力都较为有限，这就给数据的传输带来一定的挑战。在传统无线网络里，数据传输一般都要经过先压缩、后传输的过程。香农(Claude Shannon)于1948年发表的论文“A Mathematical Theory of Communication”当属信息论的开山之作［5］，其在论文中指出任何信息都存在一定程度的冗余，并第一次给出了信息熵的计算公式。而数据压缩的实质就是要消除信息中的冗余部分。通常所理解的数据压缩是指按照一定的编码方法，利用比未经编码少的数据位来表示原数据的技术。数据压缩一般包含两个过程：压缩和解压缩。压缩过程就是对原始数据采用某种算法或者编码机制，实现以更少的数据位元来描述原数据的过程。而解压缩过程则与压缩相反，而是利用压缩后得到的数据位元通过某种算法来进行压缩数据还原的过程。解压缩后，可根据还原得到的数据是否与原数据一样，而将数据压缩算法分为两类，即有损压缩和无损压缩［6］。有损压缩是指通过压缩后的数据无法还原原始数据，因其具有较高的压缩率(衡量压缩性能的一个重要指标)，更常见于多媒体压缩，如图像、视频等的压缩；无损压缩则是指通过压缩后的数据可以完整地还原得到原始数据，只是其压缩率要比有损压缩方法的压缩率低一些，因而多是用于文本文件的压缩，比较常用的无损压缩算法有哈夫曼编码、算术编码等。经过近几十年的发展，已经研发了大量的数据压缩算法，并且广泛应用于各个领域。但是由于WSNs中节点计算、存储和通信能力较为有限，使得大部分传统数据压缩算法很难在WSNs中获得理想的应用，其主要原因如下：
(1)许多传统数据压缩算法所需内存较大，而节点的内存一般非常有限，如bzip压缩算法所需内存为219KB，而TelosB节点的内存仅有10KB［7］；
(2)许多传统数据压缩算法所需计算处理能力较高，而目前许多已开发的节点(Mica系列、Telos系列节点)的CPU时钟频率一般却在1~8MHz范围内；
(3)许多传统数据压缩算法往往最关注算法的压缩性能，即压缩率，而较少论及节能，而在WSNs中，能量有效性却是算法和协议设计的重要参数之一。
基于上述原因，近年来已有大量研究人员开展了WSNs数据压缩算法的研究工作，主要可分为三大类：
(1)基于时间相关性的数据压缩算法研究；
(2)基于空间相关性的数据压缩算法研究；
(3)基于时空相关性的数据压缩算法研究。
下面将分别介绍这三个方面的研究工作。第3期李国华：无线传感器网络数据压缩技术的研究进展智能计算机与应用第4卷
1基于时间相关性的数据压缩算法
在许多WSNs应用中，单个传感器节点连续不断地采集感知对象的数据(简称感知数据)，在短时间内，感知数据的数据值变化并不大，可将这一性质称为WSNs数据的时间相关性；另一方面，由于WSNs中的节点多会部署在一个地理区域，这就使得相邻节点在同一时间内采集到的感知数据值将会较为相近，这一性质则可称为WSNs数据空间相关性。
早期的基于时间相关性的数据压缩算法中，Jagadish［8］提出了一个动态规划算法，通过该算法使得在给定线段条数的情况下，L2误差达到最小化来对数据进行压缩近似。该算法是一个最优算法，但却是一个离线算法，并且算法时间复杂度仅为O(n2)。文献［9］则提出Top-Down算法和Bottom-Up算法。Top-Down算法是在给定精度的前提下，自顶向下地考虑时间序列的每种可能划分，从中选取一个最优的划分点，再不断地迭代下去，直到整个时间序列结束。Bottom-Up算法的主要思想却与Top-Down算法恰好相反，起始是将整个时间序列划分成n/2个小段(n为时间序列的长度)，而后算法不断迭代，即合并代价最低的相邻小段，直到满足某个停止准则才结束。文献［10］又提出了Cache算法，其初始是选择第一个数据点作为近似值，如果后续的数据点在第一个数据点的ε范围内，则将其过滤，否则即结束当前的线段，并且选择不能过滤掉的数据点以作为新的近似值，等待后续数据点的到来。重复前面过程，直到整个时间序列结束。文献［11］还提出了Linear filter算法，算法选择由开始的两个数据点连接而成的直线作为第一部分数据的近似，当新的数据点到直线的距离小于给定阈值ε时，则等待下一个新数据点的到来，否则立即结束第一部分数据的近似，而
由当前未被近似压缩的数据点出发，开始第二部分的数据近似。Franky Kin-Pong Chan等人也提出了基于哈尔小波(Haar wavelets)的时间序列匹配算法［12］。首先，为了描述两个时间序列的相似性，算法给出了一个相似性度量，即传统的欧氏距离。然后，该算法对节点的时间序列进行哈尔小波变换，再利用一个滑动窗口来处理小波系数，继而建立多维索引树，并且还要利用相似性度量来查询多维索引树来确定n个最相邻的时间序列中，序列相似度量值小于给定阈值的所有序列。对于没有超过阈值的序列可用一个编码表示，其余的则分别用不同编码予以表示。需要发送的编码后的数据多会比原数据要少，这就实现了在一定程度上消除序列中的冗余信息。文献［13］又接着提出了一种用直线来近似时间序列的PMC-MR算法。其主要思想是，当第一个数据点到达时，将第一个数据放到第一个桶内(抽象的说法)，令最大值和最小值和第一个数据点的值相等。当第二个数据点到达时，将其与之前的最大、最小值进行比较，并且更新最大、最小值，同时计算最大、最小值之差，Max-Min，是否在给定的阈值2ε内。如果Max-Min小于2ε，即将第二个数据点放入桶内，稍后等待第三个数据点的到来，否则就要用(Max+Min)/2来近似表示当前桶内每个数据点的值，再从第三个数据点开始启用一个新桶来装后续数据。上述过程一直继续，直至整个时间序列结束。该算法能保证近似值与真实值的误差不超过ε。进一步地，文献［14］提出了SBR算法，每个节点可同时监测多个物理量，利用该算法探索各个物理量之间的相关性，通过选定一个物理量信号作为基础，探索该物理量与其他物理量之间的相似性，再用此基信号加上一些参数来表示其他物理量信号。文献［15］提出了BBQ算法，算法是在用户给定的一个误差以及置信区间条件下，利用一个统计模型来减少数据的感知和通信开销。相应地，文献［16］提出了Ken算法，通过使用两个动态概率模型，其中一个运行在汇聚节点(Sink节点)，另一个则运行在网络里的每个节点上，在损失微小精度的前提下可通过这两个模型来尽量减少数据的传输量。其他的研究还有，文献［17］提出了ALVQ算法，就是通过历史数据来构造一个密码本用以探索数据的内在特性，再利用这个密码本对其他数据进行分段线性压缩，如此即减少了数据的传输量。另外，文献［18］提出一个分段线性近似的算法，就是在给定一个误差界限的条件下，运用一条直线来近似当前已出现但未被压缩的数据点，直到新来一个数据点使得这个界限得以突破。其后类似地，从这个新的数据点开始再运用新的直线来近似后续的到达点。而且，文献［19］还提出了EAQ算法，首先将原始时间序列转换成一个特殊的时间序列描述MVA(multi-version array)，利用这个MVA的前缀，就可以恢复出误差一定的原始时间序列的近似版本，而随着前缀的增大，误差将逐渐减少，由此而实现了变误差的时间序列近似。除上述研究外，研究人员还提出了用离散傅立叶变换［20］、离散余弦变换［21］和离散小波变换［22］来进行数据压缩的算法，这些算法均是基于时间序列的时间相关性算法。只是其计算复杂性较高，并不适用于WSNs。
2基于空间相关性的数据压缩算法
由于节点部署多在一个地理区域，地理位置相邻的节点在同一时间采集的数据将具有极大的相似性，为了充分利用节点的带宽资源，减少冗余数据的传输，研究人员开始研究如何消除数据空间冗余。文献［23］提出的算法主要研究了WSNs数据的空间相关性。该算法在开始一段时间内由Sink节点收集节点传来的原始数据，然后Sink节点挖掘节点间数据的相关性，通过契比雪夫不等式确定具有数据相关性的节点。确立了相关性后，则建立了相关性模型，此后再进行数据传输时，只需要传输一个节点的原始数据，以及相关性模型的对应参数即可。文献［24］也提出了基于贪心选择最优路径的算法，其主要思想类似Directed Diffusion算法［25］，不同之处仅在于不同的最优路径的选择准则。在该算法中，每个节点还都会向网络发送一个路径探寻数据包，其中记录了从源节点至当前节点传输该数据包的所需能量。已存在于路径树中的每个节点还能够产生一个递增能耗数据包，该数据包即对应着每个被节点接收到的新的路径探寻数据包，而此递增能耗数据包却只能沿着节点至Sink节点的方向进行发送以及更新，递增能耗数据包经过的区域也只能被最近的节点 (即以最低能耗接收到相应路径探索数据包的节点) 更新，能耗最少的路径将得到记录，由此则构造了由最近节点构成的路径树GIT(greedy incremental tree)。其后在最优路径树上探索具有空间相关性的节点，并在传输数据时进行数据聚集，从而就减少了数据的传输量。文献［26］提出了GIST算法，其中假设节点部署在一个方形区域，每个节点均知道自己的位置信息，其后即递归迭代地划分区域，并构造一棵overlay树，树中的每个点都代表区域内的一个点。构造结束后，Sink节点逐层向下发送数据请求，而在数据传输过程中，当下层非叶子节点向上层节点传输数据时，就要先消除数据的空间冗余后再向上传输。这样一来就递归迭代地依次消除了空间冗余，从而减少了数据的传输量。文献［27］提出了三个算法，分别是：DSC(DistributedSource coding)、 RDC (Routing Driven Compression )和 CDR(Compression Driven Routing)。这三个算法均是在数据传输时，将数据压缩和路由选择综合起来考虑以最大限度地消除数据空间的冗余。文献［28］提出了利用路由选择来实现数据联合最优编码，从而达到消除空间冗余的目的。文献［29］提出了数据传输经过中间结点时进行编码的算法，文中提到了两种编码方法：外编码(foreign coding)和自编码(self coding)。前者中，原始数据只有在数据传输时经过的中间节点处进行编码，而后者中的原始数据则可以在本节点进行编码，只是其前提却是必须有其他节点传输来的数据。文献［30］提出了两个算法E-Span(Energy-aware Spanning Tree)和LPT(Lifetime Preserving Tree)。其中，E-Span算法可用剩余能量最多的节点作为根节点，而其他节点则要根据自己和相邻节点的剩余能量来确定父子关系，结构树建立之后，数据传输时非叶子节点将会融合其孩子节点的数据来消除数据空间冗余，如此即实现了递归地往汇聚节点(Sink节
点)传输。LPT算法则选择Directed Diffusion协议作为路由协议，具有剩余能量最多的节点即当选为聚集父亲 (aggregating parents) 节点，并且LPT具有自我恢复的特性，通过这一特性，当出现某个节点失效或者网络链路中断的情况时，网络的树结构即可得到修复与重建。文献［30］又分别给出了集中式与分布式的LPT算法，进一步通过仿真验证了在处理同一组数据时，两种形式的LPT算法节点的能耗较为相似，同时还验证了LPT算法中节点的平均生命周期是高于E-Span算法中相应指标的。
3基于时空相关性的数据压缩算法
文献［31］提出了针对WSNs数据时空冗余的DIMENTIONS算法，DIMENTIONS先利用小波变换在节点内消除数据的时间冗余，而后在分层的网络拓扑结构中消除数据的空间冗余。该算法的优点在于可以多分辨率提取数据特征，因此可根据实际情况获取不同精度的数据；另外，该算法采用分布式结构及随机簇头产生方案，有利于平衡节点间的能耗。DIMENTIONS算法的缺点却在于需进行多次小波变换，算法复杂度较高，同时对节点计算，存储能力等要求也较高。文献［32］考虑将Slepian-Wolf Coding［33］算法应用到WSNs中来消除数据的时空冗余性。文献［34］提出了GAMPS算法。首先，该算法动态地将节点分簇，使得每个簇里的节点数据都是具有时空相关的，全部时空相关的节点就能进行联合压缩。而后则在给定误差界限的条件下，于时空相关的节点里选择一个基础信号，当进行数据传输时，只需要传输基础信号和相关性参数即可。又有文献提出了一个基于小波变换的算法。算法假设节点部署在一维的直线上，等距排列，并且给所有节点进行编号，奇节点将数据发给偶节点，偶节点接收到数据后，联合本节点的数据进行哈尔小波(Harr wavelets)变换，将得到的高频系数按照一定的阈值压缩后再转发至汇聚节点(Sink节点)。同时，对偶节点重新进行奇偶排序，再进行哈尔小波变换后，又将新奇节点的低频系数发给相邻的新偶节点。此后即递归迭代地对新偶节点进行哈尔小波变换，直到最后一组哈尔小波变换后，且将最后的高频与低频系数传输给汇聚节点。文献［35］提出了一个应用压缩感知技术的算法，其主要思想是从源节点向汇聚节点传输数据的过程中，每经过一个中间节点，则加上一项中间节点的数据值与某个系数的乘积，这样节点传输耗能较均衡，数据的恢复在汇聚节点进行，并通过应用压缩感知方面的理论知识来对数据进行恢复。
4结束语
由于传感器节点具有有限的电池能量，因此如何提高节点的能量有效性就成为无线传感器网络各种协议设计时必须考虑的一个重要问题。而且无线传感器网络是以数据为中心且数据传输是能量消耗的主要部分，因此，减少数据的传输量将极大地减少节点的能量消耗。本文从数据的时间相关性、空间相关性以及时空相关性综述了无线传感器网络中的数据压缩技术的研究进展。现有的数据压缩算法存在的问题是：其中一部分算法对资源有限的传感器网络来说复杂性较高，而另一部分算法则是离线算法，因而具有较大的时延。针对这些问题，可以研究复杂度较低，具有在线特性的数据压缩算法，此类算法对于资源有限的传感器网络将更为适用。
参考文献：
［1］孙利民,李建中,陈渝,等.无线传感器网络［M］.北京: 清华大学出版社,2005.
［2］AKYILDIZ I F, SU W, SANKARASUBRAMANIAM Y, et al. Wireless sensor networks: A survey［J］. Computer networks, 2002, 38(4): 393-422.
［3］MARANDOLA H, MOLLO J, WALTER P. REMBASS-II: the status and evolution of the Army‘s unattended ground sensor system［C］//Proceedings of Unattended Ground Sensor Technologies and Applications IV (SPIE), 2002: 99-107.
［4］PAUL J L. Smart sensor Web: tactical battlefield visualization using sensor fusion［J］. IEEE Aerospace and Electronic Systems Magazine, 2006, 21(1): 13-20.
［5］SHANNON C. A mathematical theory of communication［J］. ACM SIGMOBILE Mobile Computing and Communications Review, 2001, 5(1):3-55.
［6］SRISOOKSAI T, KEAMARUNGSI K, LAMSRICHAN P, et al. Practical data compression in wireless sensor networks: A survey［J］. Journal of Network and Computer Applications, 2012, 35(1):37-59.
［7］TelosB datasheet ［OL］.http://www.willow.co.uk/TelosB_Datasheet.pdf
［8］JAGADISH H V, KOUDAS N, MUTHUKRISHNAN S, et al. Optimal histograms with quality guarantees［C］//VLDB， 1998, 98:24-27.
［9］KEOGH E, CHU S, HART D, et al. An online algorithm for segmenting time series［C］//ICDM, 2001:289-296.
［10］OLSTON C, JIANG J,WIDOM J. Adaptive filters for continuous queries over distributed data streams［C］//Proceedings of the 2003 ACM SIGMOD international conference on Management of data. ACM, 2003:563-574.
［11］JAIN A, CHANG E Y, WANG Y F. Adaptive stream resource management using kalman filters［C］//Proceedings of the 2004 ACM SIGMOD international conference on Management of data. ACM, 2004:11-22.
［12］CHAN F K P, FU A W C, YU C. Haar wavelets for efficient similarity search of time-series: with and without time warping［J］. IEEE Transactions on Knowledge and Data Engineering, 2003, 15(3):686-705.
［13］LAZARIDIS I, MEHROTRA S. Capturing sensor-generated time series with quality guarantees［C］//IEEE ICDE'03, 2003:429-440.
［14］DELIGIANNAKIS A, KOTIDIS Y, ROUSSOPOULOS N. Compressing historical information in sensor networks［C］//Proceedings of the 2004 ACM SIGMOD international conference on Management of data. ACM, 2004:527-538.
