传感器网络小波数据压缩算法的设计与实现

基金项目：国家高技术研究发展计划(“863”计划)资助项目(2006AA01Z227)

    数量众多的传感器节点在无线传感器网络中产生了大量的传感数据，需要在网内进行处理以避免原始传感数据的传输，以减少数据收集中参与通信的数据量，从而节省传输耗能与存储开销。数据压缩是传感器网络数据处理的一项关键技术[1-2]。

    无线传感器网络中，单个传感器节点收集到的数据在时间上可能是相关的，地理位置相邻的传感器节点收集到的数据在空间上往往也是相关的。既然无线传感器网络收集到的数据存在某种相关性，那么我们有理由使用某种变换来去除其中的冗余信息，达到数据压缩的目的。小波变换是一种能同时表征信号时域和频域行为的数学工具，具有多分辨分析的特性，在不同的尺度或者说压缩比下仍然能保持信号的统计特性[3]。小波变换已经成功应用于信号处理，目前在无线传感器网络数据压缩中的应用也有探索性的研究。Servetto首先研究了小波变换的分布式实现，并将其应用到无线传感器网络中的广播问题[4-5]。Ciancio等人的一系列工作进一步研究了无线传感器网络中的分布式小波数据压缩算法[6-7]。文献[8-9]研究了单向提升小波的二维变换问题，提出了一种小波压缩与传感数据路由相结合的联合压缩方案，节省了压缩开销。文献[10]进一步研究了传感器网络中的单向提升小波变换问题。当数据沿着传感器网络路由树向簇头节点传送时，路由节点使用该数据和邻居节点的广播数据计算小波变换，取得了较好的数据压缩效果。

    然而，在传感器网络中，节点的计算能力和存储容量非常有限，真正应用于传感器网络的小波压缩算法应该是轻量级的，不能给节点带来过大的负担。另外，传感器网络节点使用的往往是实时操作系统，压缩算法不能有长的计算耗时，同时也必须尽量不要让程序进入空闲等待状态，否则会给程序的编写带来很大的麻烦。

1 渐进式Haar小波变换原理
    Haar小波是小波家族的一员，具有小的支撑长度和简单快捷的变换算法，特别适合计算和存储等资源受限的无线传感器网络。

    和理论上的小波变换不同，在传感器节点上实现Haar小波变换时，需根据具体的情况做一些改进，只做加减法，并避免除法带来的精度降低。对一个给定的长度为l2n的采样值序列，Haar小波变换要计算相邻两个采样值的均值和差值。均值(低频系数)代表的是采样值的总体信息，差值(高频系数)代表的是细节信息。
例1：一个采样序列为{2, 6, 5, 11}，那么经过2级Haar小波变换后得到的数据就是{6, -2, -2, -3}。表1给出了对其进行2级Haar小波变换的详细运算过程。

    设节点的采样周期为T 秒，若节点只在收集传感数据的个数达到一定数目后才做一次Haar变换，那么在进行表1所示的运算前节点需要空等待4个T 秒的时间，并且需要有4个单位的缓存存储这些采样数据。在采样数据全部到齐后，节点还需要4个单位的缓存来进行运算。因此，节点完成表1所提供的Haar小波变换需要4T 的空闲等待时间和8个单位的缓存。以此类推，节点对2n个采样数据进行一级Haar小波变换需要2nT 秒的等待时间，2n＋1个单位的缓存。随着n 的增大，节点的空闲等待处理时间和缓存都是指数形式的增长，数据的实时性会被严重破坏，节点的存储资源会被严重占用。

    本文提出的渐进Haar小波变换的基本原理如图1所示。节点进行两次采样以后即对数据进行变换，对相邻的数据进行加法求均值和减法求差值运算。从图1可以看出，进行2n 个数据的渐进式一级Haar小波变换我们只需要2n＋2个单位的缓存，节点的空闲等待时间为2T 秒。

2 小波压缩算法实现方案

2.1 基于信号量机制的渐进Haar小波变换
    在分簇无线传感器网络中，传感器节点的存储能力都是十分有限的，簇头节点的硬件结构与传感器节点相同，但相对来说要比其他节点存储更多的数据。如何管理簇头节点的存储空间，实现渐进小波变换，必须要解决两个问题。一是簇头节点需要额外的存储空间存放其他节点传送来的数据。在数据收集过程中，由于媒体访问控制(MAC)层信道的竞争，某个节点传送给簇头节点的数据可能会有一定的延迟，簇头在等待此节点的数据的时候，不得不接收其他节点多次发送的数据，因而需要更大的存储空间。二是簇头面临缓存数据的保护问题。传感器网络一般都使用实时的操作系统。实时操作系统的中断优先级很高，有可能会打断目前正在进行的运算。如何保护缓存的数据不被重复的进行读写操作，也是需要解决的一个重要问题。以下基于此两个问题研究渐进Haar小波变换中的信号量机制。

    首先研究簇头的存储空间分配方法。设簇内每个节点设为采样周期为ts，采集m 个样本后把采集的数据发送给簇头。节点的通信带宽为R，每个簇内节点发送的帧长度为Fi。簇头节点上在收到压缩或者融合算法所规定的数据量后，需要进行一次处理，耗费时间为tp。假设簇头所拥有的簇内节点数量为n，那么所有簇内节点通过竞争信道发送完一个数据帧所要耗费的时间最少为。

    如果 。这样，势必会出现一个问题，在簇头正在对上一轮采样数据进行运算处理时下一轮数据已经到达。当程序员为簇头节点开辟的内存仅为大小时，则由于缓存过少会产生数据的丢失。

    对这个式子的运算结果进行向上取整，得到一个整数值L，那么在汇聚节点上总共需要开辟的缓存为m×n×L。在实际实施过程中节点竞争信道耗费的时间，和CPU对特定操作的处理时间都是不确定的，故一般可以先分配整数倍的m×n大小的缓冲区。然后通过试验结果看有无数据丢失，来调整缓冲区的大小。

    然后研究缓存数据保护方案，解决在汇聚节点正在对采样数据进行运算处理时簇内其他节点发送数据的问题。由于传感器网络节点使用的TinyOS实时性很强，一个新的数据包的达到在操作系统中会被定义为一个中断或一个事件，可以打断一些非实时的处理或者运算。这时候由于系统中断，原有的操作将暂停。虽然在存储空间分配方法中定义了额外的缓冲区存储新的数据，但若簇头节点正在进行运算处理时被中断打断，那么新的数据到来时，操作系统会认为参与运算处理的存储数据已经被释放掉了，就会直接占用已经参与运算处理的存储数据的空间。另外，当簇头的运算任务从中断恢复后，再参与运算，将会使用原存储地址但是非原始的数据来完成剩下的操作，那么簇头节点最后传送给无线网关的必然是错误的结果。

    因此，本文提出了一种信号量机制来保护簇头上缓存的数据，该机制运作步骤如下:
    (1)实时操作系统初始化

• 设置两个整数变量和一个逻辑变量作为信号量。3个变量的名字分别为PageRead、PageWrite、isPageFull；在对每个变量进行操作时必须设置为原子执行。
• 每个页面初始时都设置isPageFull为非真值；PageRead、PageWrite采用无符号8比特数表示的话可以设置为255，总之初始设置为无意义的值。

    (2)写操作进程

• 首先看是否有页面的isPageFull为非真值。
• 如果有，那么按照页面号的从小到大的次序选择同时看是否PageRead、PageWrite是相同的值，如果不相同那么PageWrite的值赋为当前选择页面号；如果没有该页面就继续寻找等待。
• 当页面写满后PageWrite设置为初始值，isPageFull设置为真值；然后重复写操作的步骤1。

    (3)读操作进程

• 首先看是否有页面的isPageFull为真值。
• 如果有，那么按照页面号的从小到大的次序选择，PageRead的值赋为当前选择页面号。如果没有该页面就继续寻找等待。
• 当页面中数据运算完成后，PageRead设置为初始值，isPageFull设置为非真值；然后重复读操作步骤1。

    信号量在读写线程的操作流程如图2所示。该信号量保护机制关键通过PageRead、PageWrite、isPageFull来保护读写的原子操作。

2.2 游程编码原理
    数据经过小波变换后能量会集中在低频系数上，小波系数按一定的规律出现，适合应用游程编码，以取得进一步的压缩效果。在例1中，经过二级Haar小波变换后，小波系数为{6, -2, -2, -3}。如果一个小波系数的存储空间需要两个字节，那么上面的小波系数需要8个字节来存储。

    游程编码的思想是对数据流中连续出现多次相同数值的数据以个数和数值的形式来表示。表1给出的小波系数通过游程编码后就以{6, 2, -2, -3}的形式表示出来。其中个数2只需要一个字节就可以表示，这样通过游程编码可以节省一个字节。如果对一个比较长的采样序列进行多级小波变换，那么游程编码可以取得更好的效果。

3 原型系统实现
    本节首先依据压缩误差和压缩比两个性能指标对小波数据压缩算法的实现方案进行评估，然后给出一个原型系统实现的实例。

3.1 性能评估
    实验环境为：硬件方面，采用25个CROSSBOW公司生产的micaz节点，一个无线网关。软件方面主要使用了TinyOS的1.1.15版本，eclipse编译器和ncc编译器。

    节点上的嵌入式程序采用nesC语言开发。25个micaz节点组成6个簇的传感器网络。

    首先我们比较压缩并还原后的数据与原始数据的误差。簇头在进行2维小波变换后如果直接使用游程编码并不会取得很好的压缩效果，因为在高频小波系数中有很多小的数值波动。因此，我们对2维小波变换后的系数取了一个阀值，当高频小波系数的绝对值低于此阀值时就被置为0。图3为解压后的温度数据和传感器采集的原始温度数据。从图3可以看出，采用阀值的解压缩后的数据与原始数据相差很小，约在1％~2％左右。然后，我们比较数据压缩比。原型系统中节点采集的是温度数据，该数据具有较强时间和地理相关性，压缩效果比较明显。图4为原型系统中统计的1号簇头的压缩比变化曲线。从图4可以看出，随着时间的变换，该簇头压缩比的平均值基本保持在7~8之间，压缩效果比较明显。

3.2 原型系统实例
    原型系统实例在湖南农业大学智能人工气候室搭建，用于温室大棚中的光度和温度监测。实验设备包括18个MICAZ节点，4个iMote2节点，2个mib510网关，一台笔记本电脑。参与实验的有两个簇，其中一个簇进行光强的测量，另一个簇进行温度的测量。由于智能人工气候室的热源(出风口)在气候室的顶部和中部，气候室垂直方向上环境数据分布具有很强的不均匀性，因此节点采用悬挂式的方法摆放。实验中，我们将智能人工气候室的日光灯和暖风机全部打开。智能人工气候室的环境如图5所示。节点的悬挂顺序从上到下为：光强组节点号为4, 2, 3, 5；温度组节点号为15, 13, 14, 12。图6给出了温度组测到的温度变化情况。

4 结束语
    数量众多的传感器节点在无线传感器网络中产生了大量的传感数据，需要进行压缩以节省有限的能量、计算和存储等传感器网络资源。本文研究无线传感器网络中小波数据压缩算法的设计与实现问题，提出了一种适合无线传感器网络的渐进式Haar小波变换和一种基于信号量机制的小波数据压缩的实现方案。实验结果表明，在压缩误差和压缩比方面，方案均取得了比较好的效果。

5 参考文献
[1] AKYILDIZ I F, SU W, SANKARASUBRAMANIAM Y, et al. Wireless sensor networks: A survey[J]. Computer Networks, 2002,38(4):393-422.
[2] 李建中, 高宏. 无线传感器网络的研究进展[J]. 计算机研究与发展, 2008,45(1):115.
[3] DAUBECHIES I. Ten lectures on wavelets[M]. Philadelphia, PA,USA: SLAM, 1992.
[4] SERVETTO S D. Sensing lena-massively distributed compression of sensor images[C]//Proceedings of IEEE International Conference on Image Processing (ICIP’03):Vol 1,Sep 14-17,2003,Barcelona, Spain. Piscataway, NJ,USA:IEEE,2003:613-616.
[5] SERVETTO S D. Distributed signal processing algorithms for the sensor broadcast problem[C]//Proceedings 37th Conference on Information Science and Systems(CISS’03), Mar 12-14, 2003, Baltimore,MD,USA. Piscataway, NJ,USA:IEEE,2003.
[6] CIANCIO A, PATTEM S, ORTEGA A, et al. Energy-efficient data representation and routing for wireless sensor networks based on a distributed wavelet compression algorithm[C]//Proceedings of 5th International Symposium on Information Processing in Sensor Networks (IPSN’06),Apr 19-21,2006, Nashville,TN,USA. Piscataway,NJ,USA:IEEE, 2006:309-316.
[7] CIANCIO A, ORTEGA A. A dynamic programming approach to distortion-energy optimization for distributed wavelet compression with applications to data gathering in wireless sensor networks[C]// Proceedings of the 31th International Conference on Acoustics, Speech and Signal Processing(ICASSP’06):Vol 4,Mar 14-19,2006,Toulouse,France, Piscataway, NJ, USA:IEEE, 2006.
[8] SHEN G, ORTEGA A. Optimized distributed 2D transforms for irregularly sampled sensor network grids using wavelet lifting[C]//Proceedings of the 33rd International Conference on Acoustics, Speech and Signal Processing (ICASSP’08),Mar 1-Apr 4,2008, Las Vegas, NV,USA, Piscataway, NJ, USA:IEEE, 2008:513-1516.
[9] SHEN G, ORTEGA A. Joint routing and 2D transform optimization for irregular sensor network grids Using wavelet lifting[C]//Proceedings of 7th International Symposium on Information Processing in Sensor Networks (IPSN’08), Apr 22-24, 2008, St Louis, MO,USA. Los Alamitos, CA,USA: IEEE Computer Society, 2008:183-194.
[10] SHEN G, PATTEM S, ORTEGA A. Energy-efficient graph-based wavelets for distributed coding in wireless sensor networks[C]//Proceedings of the 34th International Conference on Acoustics, Speech and Signal Processing (ICASSP’09), Apr 19-24, 2009, Taipei, China. Piscataway, NJ, USA: IEEE, 2009.

收稿日期：2009-07-05

[摘要] 无线传感器网络是无线网络重点研究的内容，数据压缩是其中的一项关键技术。文章研究无线传感器网络中基于小波变换的数据压缩算法设计与实现问题。首先提出适合资源受限无线传感器网络的渐进Haar小波变换，然后基于信号量机制和游程编码提出了一种小波数据压缩算法在无线传感器网络中的实现方案。原型系统实验表明，算法具有低的压缩压缩误差和较高的压缩比。

[关键词] 传感器网络；小波；压缩

[Abstract] Wireless Sensor Network (WSN) is an important field in wireless networks, and data compression is a key technique. In this paper, the design and implementation of wavelet data compression algorithm for WSNs are introduced. Firstly, a progressive Haar wavelet transformation is proposed, which is adaptive to WSNs with limited resources. Then, an implementation scheme of wavelet compression algorithm is presented based on the semaphore and run-length code. The prototyping experiment shows that the proposed algorithm has low compression error and high compression ratio.

[Keywords] sensor network; wavelet; compression