《传感器网络小波数据压缩算法的设计与实现》由会员分享，可在线阅读，更多相关《传感器网络小波数据压缩算法的设计与实现（8页珍藏版）》请在金锄头文库上搜索。
1、传感器网络小波数据压缩算法的设计与实现The Design and Implementation of Wavelet Data Compression Algorithm for Sensor Networks2009-09-25作者:林亚平,周四望摘要:无线传感器网络是无线网络重点研究的内容，数据压缩是其中的一项关键技术。文章研究无线传感器网络中基于小波变换的数据压缩算法设计与实现问题。首先提出适合资源受限无线传感器网络的渐进Haar 小波变换，然后基于信号量机制和游程编码提出了一种小波数据压缩算法在无线传感器网络中的实现方案。原型系统实验表明，算法具有低的压缩压缩误差和较高的压缩比。关键
2、字:传感器网络；小波；压缩英文摘要: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 propo
3、sed, 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.英文关键字:sens
4、or network; wavelet; compression基金项目：国家高技术研究发展计划(“863”计划)资助项目(2006AA01Z227)数量众多的传感器节点在无线传感器网络中产生了大量的传感数据，需要在网内进行处理以避免原始传感数据的传输，以减少数据收集中参与通信的数据量，从而节省传输耗能与存储开销。数据压缩是传感器网络数据处理的一项关键技术1-2。无线传感器网络中，单个传感器节点收集到的数据在时间上可能是相关的，地理位置相邻的传感器节点收集到的数据在空间上往往也是相关的。既然无线传感器网络收集到的数据存在某种相关性，那么我们有理由使用某种变换来去除其中的冗余信息，达到数据压缩的
5、目的。小波变换是一种能同时表征信号时域和频域行为的数学工具，具有多分辨分析的特性，在不同的尺度或者说压缩比下仍然能保持信号的统计特性3。小波变换已经成功应用于信号处理，目前在无线传感器网络数据压缩中的应用也有探索性的研究。Servetto 首先研究了小波变换的分布式实现，并将其应用到无线传感器网络中的广播问题4-5。Ciancio 等人的一系列工作进一步研究了无线传感器网络中的分布式小波数据压缩算法6-7。文献8-9研究了单向提升小波的二维变换问题，提出了一种小波压缩与传感数据路由相结合的联合压缩方案，节省了压缩开销。文献10进一步研究了传感器网络中的单向提升小波变换问题。当数据沿着传感器网络
6、路由树向簇头节点传送时，路由节点使用该数据和邻居节点的广播数据计算小波变换，取得了较好的数据压缩效果。然而，在传感器网络中，节点的计算能力和存储容量非常有限，真正应用于传感器网络的小波压缩算法应该是轻量级的，不能给节点带来过大的负担。另外，传感器网络节点使用的往往是实时操作系统，压缩算法不能有长的计算耗时，同时也必须尽量不要让程序进入空闲等待状态，否则会给程序的编写带来很大的麻烦。1 渐进式 Haar 小波变换原理Haar 小波是小波家族的一员，具有小的支撑长度和简单快捷的变换算法，特别适合计算和存储等资源受限的无线传感器网络。和理论上的小波变换不同，在传感器节点上实现 Haar 小波变换时，
7、需根据具体的情况做一些改进，只做加减法，并避免除法带来的精度降低。对一个给定的长度为 l2n 的采样值序列，Haar 小波变换要计算相邻两个采样值的均值和差值。均值(低频系数)代表的是采样值的总体信息，差值(高频系数)代表的是细节信息。例 1：一个采样序列为2, 6, 5, 11，那么经过 2 级 Haar 小波变换后得到的数据就是6, -2, -2, -3。表 1 给出了对其进行 2 级 Haar 小波变换的详细运算过程。设节点的采样周期为 T 秒，若节点只在收集传感数据的个数达到一定数目后才做一次 Haar 变换，那么在进行表 1 所示的运算前节点需要空等待 4 个 T 秒的时间，并且需要
8、有 4 个单位的缓存存储这些采样数据。在采样数据全部到齐后，节点还需要 4 个单位的缓存来进行运算。因此，节点完成表 1 所提供的Haar 小波变换需要 4T 的空闲等待时间和 8 个单位的缓存。以此类推，节点对 2n 个采样数据进行一级Haar 小波变换需要 2nT 秒的等待时间，2n1 个单位的缓存。随着 n 的增大，节点的空闲等待处理时间和缓存都是指数形式的增长，数据的实时性会被严重破坏，节点的存储资源会被严重占用。本文提出的渐进 Haar 小波变换的基本原理如图 1 所示。节点进行两次采样以后即对数据进行变换，对相邻的数据进行加法求均值和减法求差值运算。从图 1 可以看出，进行 2n
9、个数据的渐进式一级 Haar小波变换我们只需要 2n2 个单位的缓存，节点的空闲等待时间为 2T 秒。2 小波压缩算法实现方案2.1 基于信号量机制的渐进 Haar 小波变换在分簇无线传感器网络中，传感器节点的存储能力都是十分有限的，簇头节点的硬件结构与传感器节点相同，但相对来说要比其他节点存储更多的数据。如何管理簇头节点的存储空间，实现渐进小波变换，必须要解决两个问题。一是簇头节点需要额外的存储空间存放其他节点传送来的数据。在数据收集过程中，由于媒体访问控制(MAC)层信道的竞争，某个节点传送给簇头节点的数据可能会有一定的延迟，簇头在等待此节点的数据的时候，不得不接收其他节点多次发送的数据，
10、因而需要更大的存储空间。二是簇头面临缓存数据的保护问题。传感器网络一般都使用实时的操作系统。实时操作系统的中断优先级很高，有可能会打断目前正在进行的运算。如何保护缓存的数据不被重复的进行读写操作，也是需要解决的一个重要问题。以下基于此两个问题研究渐进 Haar 小波变换中的信号量机制。首先研究簇头的存储空间分配方法。设簇内每个节点设为采样周期为 ts，采集 m 个样本后把采集的数据发送给簇头。节点的通信带宽为 R，每个簇内节点发送的帧长度为 Fi。簇头节点上在收到压缩或者融合算法所规定的数据量后，需要进行一次处理，耗费时间为 tp。假设簇头所拥有的簇内节点数量为 n，那么所有簇内节点通过竞争信
11、道发送完一个数据帧所要耗费的时间最少为 。如果 。这样，势必会出现一个问题，在簇头正在对上一轮采样数据进行运算处理时下一轮数据已经到达。当程序员为簇头节点开辟的内存仅为大小时，则由于缓存过少会产生数据的丢失。对 这个式子的运算结果进行向上取整，得到一个整数值 L，那么在汇聚节点上总共需要开辟的缓存为 mnL。在实际实施过程中节点竞争信道耗费的时间，和 CPU 对特定操作的处理时间都是不确定的，故一般可以先分配整数倍的 mn 大小的缓冲区。然后通过试验结果看有无数据丢失，来调整缓冲区的大小。然后研究缓存数据保护方案，解决在汇聚节点正在对采样数据进行运算处理时簇内其他节点发送数据的问题。由于传感器
12、网络节点使用的 TinyOS 实时性很强，一个新的数据包的达到在操作系统中会被定义为一个中断或一个事件，可以打断一些非实时的处理或者运算。这时候由于系统中断，原有的操作将暂停。虽然在存储空间分配方法中定义了额外的缓冲区存储新的数据，但若簇头节点正在进行运算处理时被中断打断，那么新的数据到来时，操作系统会认为参与运算处理的存储数据已经被释放掉了，就会直接占用已经参与运算处理的存储数据的空间。另外，当簇头的运算任务从中断恢复后，再参与运算，将会使用原存储地址但是非原始的数据来完成剩下的操作，那么簇头节点最后传送给无线网关的必然是错误的结果。因此，本文提出了一种信号量机制来保护簇头上缓存的数据，该机
13、制运作步骤如下:(1)实时操作系统初始化 设置两个整数变量和一个逻辑变量作为信号量。3 个变量的名字分别为PageRead、PageWrite、isPageFull；在对每个变量进行操作时必须设置为原子执行。 每个页面初始时都设置 isPageFull 为非真值；PageRead、PageWrite 采用无符号 8 比特数表示的话可以设置为 255，总之初始设置为无意义的值。(2)写操作进程 首先看是否有页面的 isPageFull 为非真值。 如果有，那么按照页面号的从小到大的次序选择同时看是否 PageRead、PageWrite 是相同的值，如果不相同那么 PageWrite 的值赋为当
14、前选择页面号；如果没有该页面就继续寻找等待。 当页面写满后 PageWrite 设置为初始值，isPageFull 设置为真值；然后重复写操作的步骤 1。(3)读操作进程 首先看是否有页面的 isPageFull 为真值。 如果有，那么按照页面号的从小到大的次序选择，PageRead 的值赋为当前选择页面号。如果没有该页面就继续寻找等待。 当页面中数据运算完成后，PageRead 设置为初始值，isPageFull 设置为非真值；然后重复读操作步骤 1。信号量在读写线程的操作流程如图 2 所示。该信号量保护机制关键通过PageRead、PageWrite、isPageFull 来保护读写的原子
15、操作。 2.2 游程编码原理数据经过小波变换后能量会集中在低频系数上，小波系数按一定的规律出现，适合应用游程编码，以取得进一步的压缩效果。在例 1 中，经过二级 Haar 小波变换后，小波系数为6, -2, -2, -3。如果一个小波系数的存储空间需要两个字节，那么上面的小波系数需要 8 个字节来存储。游程编码的思想是对数据流中连续出现多次相同数值的数据以个数和数值的形式来表示。表 1 给出的小波系数通过游程编码后就以6, 2, -2, -3的形式表示出来。其中个数 2 只需要一个字节就可以表示，这样通过游程编码可以节省一个字节。如果对一个比较长的采样序列进行多级小波变换，那么游程编码可以取得
16、更好的效果。3 原型系统实现本节首先依据压缩误差和压缩比两个性能指标对小波数据压缩算法的实现方案进行评估，然后给出一个原型系统实现的实例。3.1 性能评估实验环境为：硬件方面，采用 25 个 CROSSBOW 公司生产的 micaz 节点，一个无线网关。软件方面主要使用了 TinyOS 的 1.1.15 版本，eclipse 编译器和 ncc 编译器。 节点上的嵌入式程序采用 nesC 语言开发。25 个 micaz 节点组成 6 个簇的传感器网络。首先我们比较压缩并还原后的数据与原始数据的误差。簇头在进行 2 维小波变换后如果直接使用游程编码并不会取得很好的压缩效果，因为在高频小波系数中有很多小的数值波动。因此，我们对 2 维小波变换后的系数取了一个阀值，当高频小波系数的绝对值低于此阀值时就被置为 0。图 3 为解压后的温度数据和传感器采集的原始温度数据。从图 3 可以看出，采用阀值的解压缩后的数据与原始数据相差很小，约在12左右。然后，我们比较
