（电路与系统专业论文）无线传感器网络数据压缩算法研究.pdf

杭州电子科技大学硕士学位论文 摘要 无线传感器网络( w i r e l e s ss e n s o r n e t w o r k s ，w s n ) 作为一种新型的网络技术，将逻辑上 的信息世界与客观上的物理世界融合在一起，改变了人类与自然界的交互方式，因此广泛应 用于工业控制、医疗护理、军事监测和智能交通等领域。然而，无线传感器网络具有许多不 同于传统网络的特殊性，这也使得它的发展面临许多亟待解决的问题。在无线传感器网络中， 传感器节点所感知的一维数据往往存在大量的冗余，包括同一节点在相邻时刻所采集数据在 时间上的冗余，地理区域上邻近的节点所采集数据在空间上的冗余，以及不同属性数据间存 在的冗余。此外，传感器节点所感知的二维图像中相邻像素的灰度值往往是高度相关的，同 样存在着大量的冗余。由于传感器节点的计算能力、存储能力以及电源能量严重受限，如果 直接传输带有大量冗余信息的原始数据，将浪费通信带宽、增加网络延时和节点能耗，进而 会影响整个传感器网络系统的稳定性和寿命。 针对无线传感器网络一维数据和二维图像存在的冗余信息，本文提出了三种新的无线传 感器网络数据压缩算法： ( 1 ) 针对传感器网络单属性数据存在的时间和空间相关性，提出了基于自适应最优消零 的传感器网络数据压缩算法，该算法分别在各个传感器节点和簇头节点对相应的数据序列进 行递增排列并进行相关位和位数因子分析，以寻找一个最优位数因子，然后利用该最优位数 因子对数据序列进行消零运算和二进制编码，从而去除时间和空间冗余，减小数据传输量。 ( 2 ) 针对传感器网络多属性数据间的相关性以及感知数据可能存在的突变性，提出了基 于异常点筛选和分段多项式回归的传感器网络数据压缩算法，该算法根据不同属性数据的分 布特征选取基信号，然后采用多项式回归模型分段近似其它数据序列，同时对数据序列中可 能存在的异常值进行检测和筛选，从而在保证数据精度满足系统要求的前提下，有效地减小 数据传输量，降低节点能耗。 ( 3 ) 针对无线多媒体传感器网络中二维图像数据存在的相关性，提出了基于簇内分布式 处理的无线多媒体传感器网络图像压缩算法，该算法通过能量优先选择原则在簇内选取若干 个辅助节点，将图像的多级小波变换和编码压缩分布到辅助节点上完成，从而平衡各个节点 的能耗，延长网络生命周期。 上述三种算法分别面向传感器网络的单属性一维数据、多属性一维数据和二维图像数据， 从降低节点能耗、减小网络延时和延长网络生命周期的目的出发做了相应的研究工作。本文 通过m a t l a b 仿真实验分别对三种算法的性能进行了验证，仿真结果表明，三种算法均能在 保证数据精度符合系统要求的前提下，对各自的研究对象进行有效压缩，降低节点能耗，延 长网络生命周期。 关键词：无线传感器网络，数据压缩，自适应最优消零，分段多项式回归，小波变换，分布 式处理 杭州电子科技大字坝士学位论又 a b s t r a c t a san e wn e t w o r kt e c h n o l o g y , w i r e l e s ss e n s o rn e t w o r k s ( w s n s ) c o m b i n et h el o g i c a l i n f o r m a t i o nw o r l dw i t ht h eo b j e c t i v ep h y s i c a lw o r l d ，a n dc h a n g et h ei n t e r a c t i v ew a yb e t w e e n h u m a nb e i n g sa n dn a t u r e ，t h u si ti sw i d e l yu s e di ni n d u s t r i a lc o n t r o l ，m e d i c a lc a r e ，m i l i t a r y m o n i t o r i n ga n di n t e l l i g e n tt r a f f i c ，e t c h o w e v e r , t h ed e v e l o p m e n to fw s n sf a c e sal o to fp r o b l e m s t h a tn e e dt ob es l o v e du r g e n t l yd u et oi t ss p e c i f i c i t i e s i nw s n s ，t h e r ei sal a r g ea m o u n to f r e d u n d a n c yi nt h ec o l l c t e do n e - d i m e n s i o nd a t a , i n c l u d i n gt h et e m p o r a lr e d u n d a n c yi n t h ed a t a a c q u i r e db yt h es a m es e n s o rn o d ea n dt h es p a t i a lr e d u n d a n c yi nt h ed a t aa c q u i r e db yt h ea d j a c e n t s e n s o rn o d e s ，a n dt h er e d u n d a n c ya m o n gt h ed a t ao fd i f f e r e n tm e a s u r e m e n t s i na d d i t i o n ，t h e r ei s a l s oal a r g ea m o u n to fr e d u n d a n c yi nt h ec o l l e c t e dt w o d i m e n s i o ni m a g ed u ot ot h es t r o n g c o r r e l a t i o nb e t w e e na d j a c e n tp i x e l s t h ec o m p u t i n ga b i l i t y , s t o r a g ea b i l i t ya n db a t t e r yp o w e ro f s e n s o rn o d e sa r er e s t r i c t e ds e v e r e l y , t h e r e f o r e ，i ft h eo r i g i n a ld a t aw i t hr e d u n d a n c yi st r a n s m i t t e d d i r e c t l y , i tw o u l dl e a dt o aw a s t eo fc o m m u n i c a t i o nb a n d w i d t ha n de n e r g yc o n s u m p t i o n ，a n d u l t i m a t e l ya f f e c tt h el i f e t i m eo f s e n s o rn e t w o r k c o n s i d e r i n gt h er e d u n d a n c yi nt h ec o l l e c t e do n - d i m e n s i o nd a t aa n dt w o - d i m e n s i o ni m a g eo f w s n s ，t h r e en o v e ld a t ac o m p r e s s i o na l g o r i t h mf o rw s n s a r ep r o p o s e di nt h i sp a p e r ( 1 ) c o n s i d e r i n gt h et e m p o r a la n ds p a t i a lc o r r e l a t i o na m o n g t h ec o l l e c t e do n e - d i m e n s i o nd a t a , a d a t ac o m p r e s s i o nm e t h o df o rw i r e l e s ss e n s o rn e t w o r k sb a s e do na d a p t i v eo p t i m a lz e r os u p p r e s s i o n ( a o z s ) i sp r o p o s e d t h ea o z sa l g i r h t ms o r t st h ec o l l e c t e dd a t ai na s c e n d i n go r d e ri ns e n s o rn o d e s a n dc l u s t e r - h e a dn o d e sr e s p e c t i v e l y , a n dt h ec o r r e l a t i v eb i ta n dd i g i t a lf a c t o ri sa n a l y s e dt of i n da n o p t i m a ld i g i t a lf a c t o r , f i n a l l yt h ea o z sa l g o r i t h mp e r f o r m sz e r os u p p r e s s i o na n de n c o d eo p e r a t i o n b a s eo nt h eo p t i m a ld i g i t a lf a c t o lt h u sr e m o v i n gt h et e m p o r a la n ds p a t i a lr e d u n d a n c y , d e c r e a s i n g t h ed a t at r a n s m i s s i o ni nt h en e t w o r k ( 2 ) c o n s i d e r i n gt h ec o r r e l a t i o n sb o t hw i t h i nt h ev a l u e so fas i n g l em e a s u r e m e n ta sw e l la s a m o n gt h ev a l u e so f d i f f e r e n tm e a s u r e m e n t s ，a n dt h em u t a b i l i t yt h a tm a ye x i s ti nc o l l e c t e dd a t a ，a w i r e l e s ss e n s o rn e t w o r kd a t ac o m p r e s s i o na l g o r i t h mb a s e do no u t l i e rs c r e e n i n ga n dp i e c e w i s e p o l y n o m i a lr e g r e s s i o n ( o p r ) i sp r o p o s e d t h eo p ra l g o r i t h mf i r s tc h o o s e sab a s es i g n a la c c o r d i n g t ot h ed i s t r i b u t i o nc h a r a c t e r i s t i c so ft h ec o l l e c t e dd a t a ，a n dt h e ni m p l e m e n t sp o l y n o m i a lr e g r e s s i o n t oa p p r o x i m a t et h ep i e c e w i s ed a t as e q u e n c et ot h eb a s es i g n a l ，m e a n w h i l e ，t h ep o s s i b l eo u t l i e r sa r e d e t e c t e da n ds c r e e n e d t h u se n s u r i n gt h ed a t aa c c u r a c yc a ns a t i s f yt h es y s t e m sr e q u i r e m e n t s ，a n d d e c r e a s i n gt h ed a t at r a n s m i s s i o na n de n e r g yc o n s u m p t i o ne f f e c t i v e l y ( 3 ) c o n s i d e r i n gt h es t r o n gc o r r e l a t i o na m o n gt h et w o - d i m e n s i o ni m a g e ，a ni m a g ec o m p r e s s i o n 杭州电子科技大学硕十学位论文 a l g o r i t h mb a s e do ni n c l u s t e rd i s t r i b u t e dp r o c e s s i n gf o rw i r e l e s sm u l t i m e d i as e n s o rn e t w o r k s ( i c d p ) i sp r o p o s e d t h ei c d pa l g o r i t h ms e l e c t sap l u r a l i t yo fa u x i l i a r ys e - n s o rn o d e si nt h ec l u s t e r sb y u s i n gt h ee n e r g yp r i o r i t ys e l e c t i o np r i n c i p l e ，a n dt h e nt h ec o m p u t i n gp r o c e s so fm u l t i - l e v e lw a v e l e t t r a n s f o r ma n de n c o d i n go p e r a t i o na r ed i s t r i b u t e dt ot h ea u x i l i a r yn o d e s ，s oa st ob a l a n c et h ee n e r g y c o n s u m p t i o no fe a c hs e n s o rn o d e sa n dp r o l o n gt h el i f e t i m eo fs e n s o rn e t w o r k t h ea b o v et h r e ea l g o r i t h m sa r eg e a r e dt ot h en e e d so fo n e - d i m e n s i o nd a t aw i t hs i n g l ea t t r i b u t e ， o n e - d i m e n s i o nd a t aw i md i f f e r e n ta t t r i b u t e sa n dt w o d i m e n s i o ni m a g er e s p e c t i v e l y t h e s ew o r k s a i mt od e c r e a s et h ee n e r g yc o n s u m p t i o n ，r e d u c et h en e t w o r kd e l a ya n dp r o l o n gt h en e t w o r kl i f e t i m e i nt h i sp a p e r , m a t l a bs i m u l a t i o ne x p e r i m e n t sa r ed o n et oa n a l y s et h ep e r f o r m a n c eo ft h ea b o v e t h r e ea l g o r i t h m s ，a n do u rs i m u l a t i o nr e s u l t sd e m o n s t r a t et h a ta l lt h r e ea l g o r i t h m sc a ne n s u r et h e d a t aa c c u r a c ym e e t st h es y s t e m sr e q u i r e m e n t s ，c o m p r e s s i n gt h i e rr e s p e c t i v er e s e a r c ho b j e c t e f f e c t i v e l y , d e c r e a s i n gt h ee n e r g yc o n s u m p t i o na n dp r o l o n i n gt h en e t w o r kl i f e t i m e k e y w o r d s ：w i r e l e s ss e n s o rn e t w o r k s ，d a t ac o m p r e s s i o n ，a d a p t i v eo p t i m a lz e r os u p p r e s s i o n ， p i e c e w i s ep o l y n o m i a lr e g r e s s i o n ，w a v e l e tt r a n s f o r m ，d i s t r i b u t e dp r o c e s s i n g i l l 杭州电子科技大学硕士学位论文 第1 章绪论 1 1 无线传感器网络数据压缩意义 无线传感器网络( w i r e l e s ss e n s o rn e t w o r k s ，w s n s ) 是由部署在监测区域内大量廉价的，集 传感能力、计算能力和通信能力于一身的微型传节点组成，通过无线通信方式形成的一个多 跳自组织网络。各传感器节点能够互相协作，实时地感知和采集监测区域各种数据，然后对 这些数据进行处理并传送到需要的用户【l 】。无线传感器网络作为一种新型的网络技术，涉及 多学科高度交叉，综合了传感器技术、嵌入式技术、现代网络技术及无线通信技术、分布式 信息处理技术、微机电系统等方面的知识，将逻辑上的信息世界与客观上的物理世界融合在 一起，改变了人类与自然界的交互方式，人们可以通过无线传感器网络感知客观世界，而不 必亲自去观测区进行观测，从而极大地扩展了现有网络的功能和人类认识世界的能力，实现 了物理世界、人类社会和计算机网络三大领域的信息交互【2 】。无线传感器网络广泛应用于军 事监测【3 4 】、智能家居【5 6 】、环境监控【7 ，8 】、工业应用 9 1 、医疗护理【1 0 , 1 1 】、交通控制【1 2 1 、抢险救灾 1 1 3 等领域，被列为2 1 世纪最有影响的2 1 项技术和改变世界的1 0 大技术之一，同时，传感器 网络、塑料电子学和仿生人体器官又被称为全球未来的三大高科技产业。 无线传感器网络作为一种新型的网络技术，与传统网络相比具有一些独有的特点： ( 1 ) 网络节点数量大，密度高。传感器网络通常工作在一些人类难以接近的或者危险的 区域中，为了对这些区域执行监测任务，往往有成千上万的传感器节点部署到该区域。通过 部署大量传感器节点不仅能够提高监测的精确度，而且可以利用节点之间的高度连接性来提 升传感器网络的容错性和抗毁性。 ( 2 ) 能量有限。由于传感器网络特殊的应用领域，使得网络节点一般由电池供电，一旦 电池能量用完，节点也就失去作用，因此节点的能耗直接决定了传感器网络的工作寿命，任 何传感器网络技术的研究都要以节能为前提条件。 ( 3 ) 硬件资源有限。传感器网络节点受体积、功耗和成本的影响，其计算能力和存储容 量有限，不能进行复杂的计算，只能运行简单有效的协议和算法。 ( 4 ) 自组织。传感器网络的建立无需任何预设的网络设施，节点能够通过网络协议和拓 扑控制算法自动进行匹配和管理协调，快速地组建一个独立的网络。即使一部分节点失效， 剩余的节点依然能够自动组建网络。 ( 5 ) 网络拓扑动态性。由于传感器网络节点随时可能会因为故障或能量耗尽而失效退出 网络，或者因为工作需要需添加新的节点到网络中，这些特点都会使得传感器网络的拓扑发 生变化，因此传感器网络需要具备动态的拓扑组织功能。 ( 6 ) 多跳路由。传感器网络节点的通信距离有限，如果节点希望与其通信范围以外的节 仉州电于科披入子耿工子性w 义 点进行通信，则需要经过中间节点的路由，传感器网络中的多跳路由一般是由普通的节点完 成的，没有特定的路由设备。因而每个传感器节点既可以是信息的发起方，也可以是信息的 转发方。 上述这些特点使得传感器网络的发展和应用面临着诸多亟待解决的问题，而如何降低节 点能耗以延长整个网络的寿命，是目前研究的一个重点。传感器节点消耗能量的模块包括传 感器模块、处理器模块和无线通信模块。随着集成电路工艺的进步，处理器和传感器模块上 的功耗变得很低，近8 0 的节点能量消耗在无线通信模块上，传输l b i t 数据的能耗至少是执 行一条加法指令能耗的4 8 0 倒1 4 】。然而传感器网络采集的原始数据存在着大量的数据冗余， 包括同一传感器节点在相邻时刻所采集的数据在时间上的冗余，以及地理区域上邻近的节点 所采集的数据在空间上的冗余，由于传感器网络只有有限的能量和传输带宽，如果传感器节 点数据采集率很高并且直接传输带有大量冗余信息的原始数据，不仅会造成通信带宽的浪费， 导致网络通信产生较大的时延，基站不能实时处理接收到的数据，还会增加传感器节点的功 耗，严重影响整个传感器网络系统的稳定和寿命。无线多媒体传感器网络( w m s n s ) 是在传 统的传感器网络基础上发展起来的，能够感知音频、视频、图像等大数据量的多媒体信息， 在环境监测、战场监控、智能家居等领域具有广阔的应用前景。然而，图像作为w m s n s 主 要感知信息之一，具有大数据量、高复杂度和高内存需求等特点，图像中相邻像素的灰度值 往往是高度相关的，存在着大量的冗余信息，相邻节点采集的图像也往往具有大量的空间冗 余信息，资源( 能量、计算能力、存储能力) 严重受限的单个w m s n s 节点难以完成图像信 息的采集、处理和传输 1 5 , 1 6 。因此，传感器网络的数据压缩起着十分重要的作用，主要表现 在以下两个方面： ( 1 ) 节省能耗 传感器网络是由大量的传感器节点覆盖到监测区域而组成的，传感器节点所采集的数据 具有大量的冗余信息，数据压缩就是针对这些冗余数据进行网内处理，节点在发送或转发传 感器数据之前，首先对数据进行压缩处理，去除掉冗余信息，在满足系统应用要求的前提下 尽量将所要传输的数据量最小化，从而减少传感器节点的能耗，延长网络的生命周期。 ( 2 ) 提高数据收集效率 一个传感器网络拥有大量的传感器节点，数据压缩减少了需要传输的数据量，从而减轻 了网络的传输拥塞，降低了数据的传输延迟，提高无线信道的利用率，因此在网内进行数据 压缩，可以在一定程度上提高传感器网络收集数据的整体效率。 1 2 无线传感器网络数据压缩算法的研究现状 无线传感器网络起源于2 0 世纪9 0 年代，由部署在监测区域内大量传感器节点组成，用 以监测温度、湿度、压力、位移、噪音和光强等多种属性的一维数据，并能够向基站返回监 测对象的数据信息，随着它的应用越来越广泛，对无线传感器网络一维数据压缩问题的研究 2 杌州电于科玟大字坝- 1 7 字位论又 也就逐渐展开了。无线传感器网络对某一区域进行监测时，传感器节点采集的数据通常是连 续性的变量，由于这些变量在时间上具有一定的相关性，因此研究人员最初就利用这种时间 相关性对数据进行压缩，比如引入预测模型，小波变换等方法来消除节点所采集数据在时间 上的冗余。随后研究人员发现，在传感器网络中不仅同一节点在邻近时刻所采集的数据具有 时间相关性，地理区域上邻近的节点在相同或相邻时刻所采集的数据在空间上也具有相关性， 因此研究人员开始关注利用这种空间相关性来对数据进行压缩，比如根据分簇协议将传感器 网络分成若干个簇，在簇内对数据进行压缩，消除数据在空间上的冗余后再传往基站。由于 传感器网络所采集的数据同时具有时间相关性和空间相关性，现在人们普遍研究同时基于数 据时间相关性和空间相关性的压缩算法，一方面在单个传感器节点内消除数据在时间上的冗 余，另一方面通过节点间信息的交互消除数据在空间上的冗余，从而尽可能减小节点能耗， 延长整个传感器网络的寿命。近年来，无线传感器网络的研究范围由只能采集简单一维数据 的传统无线传感器网络延伸到了能够采集大数据量二维图像、视频信息的无线多媒体传感器 网络，因此针对无线多媒体传感器网络二维图像数据的压缩也受到越来越多的关注。图像中 相邻像素的灰度值往往是高度相关的，存在着大量的冗余信息，研究人员最初往往借助一些 成熟的图像编码算法( 如j p e g 、e z w 、s p i h t 、e b c o t 等) 来消除图像冗余信息，达到压 缩图像的目的。然而，资源严重受限的单个节点难以完成高复杂度、大数据量、高内存需求 的图像的采集、处理和传输，因此研究人员逐渐开始利用网络节点部署较为密集的特点，将 单个节点的计算负荷有效地分布到多个节点上，分布并行地实现图像的处理、存储和传输， 从而降低单个节点的能耗，平衡整个网络的能耗分布，延长网络生命周期。 1 2 1 面向一维数据的无线传感器网络数据压缩算法 1 2 1 1基于数据时间相关性的传感器网络数据压缩算法 在无线传感器网络中，传感器节点会周期性地感知和采集数据，这些邻近时刻采集的数 据可以表示为时间序列。传感器节点产生的时间序列存在着许多冗余信息，为了节省节点能 耗，提高通信带宽利用率和数据收集效率，需要对这样的时间序列进行压缩，去除时间冗余 信息，从而形成了一类基于数据时间相关性的压缩算法。基于数据时间相关性的压缩算法主 要是面向于单个传感器节点，以邻近时刻所采集的单个物理量的数据或特定时刻所采集的多 个物理量的数据为研究对象，根据无线传感器网络不同的应用场合采用不同的方法，在应用 允许的精度范围内对传感器节点采集的数据进行压缩，尽可能地消除传感器节点所采集数据 在时间上的冗余信息。针对无线传感器网络所采集数据的时间冗余问题，国内外学者做了大 量的研究工作，提出了许多不同的解决方法。 刘向宇，王雅哲等人提出了一种采用线性回归和非线性回归中的多项式拟合技术对流数 据进行分段拟合，实现数据流压缩传输的算法【1 7 】，简称c o d s t 算法。该算法把传感器节点 3 七j i 7 ”吧丁科教人子耿_ - 1 7 子但w 义 要发送到基站的m 个数据点存入缓存拟合成多项式，传送数据包括节点i d 号、拟合参数， 并根据数据点采集时间是否均匀来选择传送采集数据的时间序列或数据点个数。大多数情况 下，某一时间段内数据的变化符合某种模式，如果对每个时间段进行拟合传输会导致数据处 理效率不高，因而c o d s t 算法采用基于拟合验证的方法来减少拟合次数，提高数据处理效 率。c o d s t 算法压缩后的流数据能够非常接近原始流数据，但如何确定一个最优的拟合阶数， 文献中并没有相关考虑，如果拟合阶数过小，就不能提高数据压缩率；而如果拟合阶数过大， 算法又会消耗过多的能量，并且增加网络延时。 后小亮，刘奇志等人针对传感器节点采集数据的多态性，提出了一种线性预测综合压缩 算法【1 8 】，该算法对常态数据流和非常态数据流采用不同的压缩算法，对常态数据流根据误差 需要进行可变误差阈值线性压缩以尽可能去除时间冗余信息，而对非常态数据流则直接向基 站传递预测模型参数，在基站实现对非常态数据流的预测，该算法能够通过动态调整移动系 数和模型来尽可能去除时间冗余信息，提高压缩性能，但困难在于如何为特定的应用建立一 个合适的预测模型。 k i my o u n g d a e 和h w a n gs e u n g - w o n 提出的算法【l9 】则需要在基站和传感器节点处建立一 个估计模型，通过传感器节点所采集数据的时问相关性来进行数据的估计，如果估计值与实 际值的误差在系统允许的误差范围内，则不需要传送所采集的原始数据，基站可以直接采用 估计值，这样可以大大减少了需要传送的数据量，从而降低节点功耗，减小网络延时，但该 算法的稳定性往往会受到外界环境与节点本身故障的影响。 t h a r i n ic 和v a n a j ar a n j a np 提出了一种改进的自适应h u f f m a n 编码算法【2 0 】，该算法通过 对一组数据赋于相同的概率值来降低算法运行时的计算量，使其可以应用于无线传感器网络 的无损数据压缩。类似的基于h u f f m a n 编码的数据压缩算法还有文献【2 1 ，2 2 2 3 】中提出的算法，基 于h u f f m a n 编码的算法虽然能够较大程度地去除数据的时间冗余，但往往需要在节点中构建 和维护一个二叉编码树，这将增加传感器节点的存储开销，并且基于二叉编码树的解码中， 若发送节点的数据有丢失，则接收节点将无法正确地解码以得到原始数据，因而限制了该类 算法的应用。 基于数据时间相关性的传感器网络数据压缩算法还有很多，如b a n a e ik a s h a n i 和s h a l l a b i c y r u s 提出的数据压缩算法【2 4 】基于查询模式，通过优化后的查询算法，基站发出请求信号， 传感器节点接收到后则发送当前采集的数据，否则对采集的数据按照时间序列进行压缩，并 保留压缩特征值，从而在一定程度上去除了数据的时间冗余，降低节点能耗。f r a n c e s c o m a r c e l l o n i 提出的基于相关性挖掘与熵编码的传感器网络数据压缩算法【2 5 1 ，通过对原始数据 间的差值进行熵编码去除数据的时间冗余。a a r o nk i e l y 和m i n g s e nx u 等人提出的自适应的 线性滤波压缩算法a l f c t 2 6 1 ，通过自适应滤波机制来预测样本值并进行熵编码，将可变长度 的样本编码成固定长度的数据包，自适应预测机制使得a l f c 算法能够根据采集数据的变化 情况进行动态压缩，而不需要提前确定预测系数。文献【27 】提出了两种改进的基于l z w 的无 损数据压缩算法，通过不同的方式对数据进行预处理，从而适应不同类型数据的特点。文献 4 杭州电子科技大学硕士学位论文 2 8 1 深入探讨了传感数据压缩的问题，基于有限几何的广义多边形原理提出了一种低存储需求 的数据矩阵压缩方案，同时还利用广义多边形的几何性质开发出了数据精确恢复的算法。 基于数据时间相关性的压缩算法主要是针对单个节点在邻近时刻所采集的单个物理量数 据或特定时刻所采集的多个物理量数据，压缩处理过程均在节点内部进行，网络的能耗主要 取决于节点在相邻时刻所采集数据相关性的大小，若相关性较大，则压缩后的数据占原始数 据的比例将越小，因而传感器网络需要传输的数据量越小，网络能耗也越小。不过在基于数 据时间相关性这类压缩算法中，阈值的选取会影响压缩比以及数据的重构精度，若阈值选取 较大，则压缩比越小，网络传输的数据量越小，但数据的重构精度会下降；若阈值选取较小， 则压缩比越大，网络传输的数据量越大，但数据的重构精度则会提高。由于基于数据时间相 关性的压缩算法处理过程只限于节点内部，不像基于数据空间相关性压缩算法和基于数据时 间空间相关性压缩算法为了去除数据的空间冗余而需要节点间频繁地交互信息，或者通过相 关算法不断地搜寻数据传递的最优路径，因而算法复杂度较另外两类算法要低，同时网络延 时也较小，但传感器网络具有网络节点数量大，密度高的特点，地理上邻近的节点所采集数 据在空间上具有一定的冗余，而这类算法恰恰没有考虑空间冗余，随着网络规模的增大，网 络中传递的数据将携带大量的空间冗余，从而造成节点的平均能耗迅速增加。 1 2 1 2 基于数据空间相关性的传感器网络数据压缩算法 在无线传感器网络中，为了能够提高监测精度，并提升网络的容错性和抗毁性，监测区 域的传感器节点往往数量大，密度高，相邻传感器节点采集到的数据在空间上往往也具有相 关性，为了节省节点能耗，提高通信带宽利用率和数据收集效率，需要使用一些方法来去除 其中的空间冗余信息，从而形成了一类基于数据空间相关性的压缩算法。基于数据空间相关 性的压缩算法主要是面向地理区域上邻近的节点，以邻近节点在若干个连续采样周期中采集 的数据为研究对象。大多数基于数据空间相关性的压缩算法是通过分簇协议将整个无线传感 器网络划分成若干个簇，并且簇内各节点可以互相通信。簇内节点可以将采集到的数据传送 到簇头节点，簇头节点通过压缩算法去除空间冗余信息，或者簇内节点之间互相通信，协作 去除空间冗余信息后再将数据传送到簇头节点，而簇头节点之间也可以进行通信，从而能够 在更大范围内去除无线传感器网络所采集数据的空间冗余。此外，越来越多的基于数据空间 相关性的压缩算法与路由选择结合在了一起，通过路由算法搜寻一条节点至基站的最优路径 来去除数据的空间冗余。在无线传感器网络实际应用中需要根据不同的场合采用不同的方法， 在应用允许的精度范围内对传感器节点采集的数据进行压缩，尽可能去除传感器节点采集数 据在空间上的冗余。针对无线传感器网络所采集数据的空间冗余问题，国内外学者做了大量 的研究工作，提出了多种不同的方法。 刘刚等人针对传感器网络的空间冗余提出了一种基于差异化加权数据压缩的汇聚算法 ( d a d w ) 2 9 】，d a d w 算法基于传感器网络的事件驱动模型，通过对来自事件发生点周围传 5 仉州电丁科技灭子坝士罕位比义 感器节点的数据进行差异化加权处理，选择一个合理的融合点来去除数据的空间冗余，并提 高融合数据的精度。文献首先介绍了近源汇聚( c n s ) 、最短路径树( s p t ) 和贪心增长树( g i t ) 三 种融合树建立方案，但在基于事件驱动的传感器网络中，这三种融合树建立方案都没有考虑 数据本身的特点以及不同传感器节点数据的权重，因而文献中提出了一种基于差异化加权处 理的数据汇聚算法( d a d w ) ，选择距离事件中心最近的节点作为融合节点，对其它节点传送 过来的数据进行融合，去除空间冗余，然后选择一条最短路径将数据发送到基站。d a d w 算 法相比g i t 算法能耗略有增加，但其在数据的融合精度上却有显著的提高，然而d a d w 算 法主要是面向于事件驱动型传感器网络，这限制了它在查询驱动型和连续性型传感器网络中 的应用。 l u j u nj i a 和g u e v a r an o u b i r 提出的g i s t 算法【3 们，通过不断调用递归函数 g i s t ( i ，( 西，y 1 ) ，( 恐，耽) ) 将无线传感器网络的覆盖区域进行分层和分簇，并且通过基站的一个请 求信息，下层节点将采集数据传送到头节点，由头节点对数据进行压缩，去除空间冗余后再 传送到上一层的头节点，反复迭代运算直到基站，从而去除数据的空间冗余。然而g i s t 算 法对网络传输结构的建立过程较为复杂，并且需要各个节点知道自身以及基站的地理坐标， 这些都在一定程度上影响了g i s t 算法在实际中的应用。 s u n d e e pp a t t e m 和b h a s k a rk r i s h n a m a c h a r i 提出的结合路由和空间相关性挖掘的压缩算法 【3 l 】，通过平衡簇的大小及相邻节点数据的相关性去除数据空间冗余，但该算法的性能在很大 程度上受监测数据空间相关性的影响，表示相邻节点数据相关性的联合熵中的相关性经验常 数需要大量的实际检测进行估计，并且该算法需要知道节点的精确位置以及节点间的距离， 因而在实际应用中较难实现。 谢志军和王雷等人提出的基于v o r o n o i 网格的数据压缩算法【3 2 】也是针对传感器网络数据 空间冗余问题的。文献首先对分布式数据汇聚模型( d d a m ) 进行改进得到分布式域剖分模型 ( d d p m ) ，然后设计了一种分布式的多层次迭代路由，并在此基础上提出了一种基于h a a r 小 波的分布式多分辨率数据压缩模型( m d c m ) 。在该算法中v o r o n o i 网格是关于空间临近关系的 一种基本数据结构，因而充分挖掘了节点间数据的空间相关性，并且算法采用通信带宽作为 压缩代价的衡量机制，即网络中层次越高就需要将越多的数据整合到某一特定带宽中，因而 算法在高层运行中更能体现出优良的性能。但是该算法的分布式域划分模型d d p m 较复杂， 而且需要依赖g p s 来计算自己的坐标，这显然会增加网络的延时和成本。 以上介绍了几种近年来较为典型的基于数据空间相关性的传感器网络数据压缩算法，此 外还有很多基于数据空间相关性的数据压缩算法。如文献【3 3 】通过定义可选择排列的传感器节 点，探讨了如何对离散空间信号向量的样本进行重排列，同时在寻找传感器节点次优排列顺 序的基础上设计了一种能够提升传感器网络数据压缩效率的方法。文献瞰】针对空间相邻的监 测区域提出了一种基于簇的压缩机制，主要面向于事件驱动的传感器网络，挖掘空间相关性， 去除冗余信息。基于数据空间相关性的数据压缩算法往往要通过分簇算法将传感器网络划分 为若干个簇，近年来也有许多学者对传感器网络的分簇协议进行了研究，例如文献【3 5 , 3 6 , 3 7 均 杭州电子科技大学硕士学位论文 提出了针对传感器网络的分簇机制，旨在充分挖掘数据空间相关性，去除冗余信息，降低并 且平衡网络各节点的能耗。 基于数据空间相关性的压缩算法主要是针对地理上邻近节点在若干连续采样周期中采集 的数据，该类算法大多都会对整个传感器网络进行分簇，先通过簇内各节点之间互相通信与 协作去除空间冗余信息，再将数据发往簇头节点，然后逐层进行压缩直至基站；或者簇内各 节点先将采集到的数据发往簇头，由簇头进行压缩处理去除空间冗余信息。在传感器网络的 分层分簇拓扑结构中，下层节点在地理区域上较为邻近，不仅数据量较小，数据间空间相关 性也更大，但随着网络规模的扩大，需要划分的层次增多，上层各节点的空间跨度和需要处 理的数据量也越来越大，数据的空间相关性则呈下降趋势，这使得该类算法的复杂度要一般 高于基于数据时间相关性的压缩算法，为了有效去除空间冗余，节点间需要频繁地进行通信， 并逐层对数据进行压缩处理，因而该类算法的网络延时要比基于数据时间相关性的压缩算法 大，同时，节点间频繁的通信使得该类算法更容易受到外界噪声的干扰，从而影响数据的重 构精度。 1 2 1 3 基于数据时间和空间相关性的传感器网络数据压缩算法 在无线传感器网络中，不仅单个传感器节点在邻近时刻收集到的数据在时间上具有相关 性，地理区域上邻近的传感器节点收集到的数据在空间上往往也具有一定的相关性，因此现 在人们普遍研究同时基于数据时间相关性和空间相关性的压缩算法，尽可能去除节点采集数 据的时间和空间冗余信息，降低节点能耗，合理利用带宽资源，并提高系统处理数据的效率。 基于数据时问和空间相关性的压缩算法同时面向单个节点和邻近区域的节点，以单个节点在 邻近时刻采集的数据以及邻近节点在若干连续采样周期中采集的数据为研究对象。大多数基 于数据时间和空间相关性的压缩算法会将整个无线传感器网络划分成若干个簇或小区域，首 先消除簇内或小区域内单个节点所采集数据在时间上的冗余，然后以簇或小区域为单位去除 节点间所采集数据在空间上的冗余。根据无线传感器网络不同的应用场合采用不同的方法， 在应用允许的精度范围内对传感器节点采集的数据进行压缩，尽可能地消除传感器节点所采 集数据在时间和空间上的冗余信息。针对无线传感器网络所采集数据的时间和空间冗余问题， 国内外学者做了大量的研究工作，提出了许多不同的解决方法。 d e e p a kg a n e s a n 和d e b o r a he s t r i n 等人提出的d i m e n t i o n 算法是一种典型的基于数据 时间和空间相关性的压缩算法【3 引，该算法通过迭代的方式对整个无线传感器网络进行分层和 分簇，簇内各节点对采集的数据进行小波变换和阈值滤波，去除时间冗余，减小下一步去除 空间冗余运算时网络的数据传输量。然后各节点将提取的时间序列数据特征发往簇头节点， 由簇头节点进行小波子带分解，经阈值处理后再进行量化编码，该空间域的小波分解将在网 络的各个层次间被执行，从而去除空间冗余。该算法利用了小波的多分辨率分析特性，因此 可以根据实际需要来选取不同的小波系数进行分析，以获得数据的不同特性，此外，在源节 7 杌州吧于科玟大罕坝士字位比又 点内就去除了数据的时间冗余，大大减少了接下来去除空间冗余运算时网络的数据传输量， 降低了节点的能耗。然而，当传感器网络的规模较大，需要划分的层较多时，小波变换的级 数会增加，而越接近基站的层次，数据量越大，小波变换的计算量也越大，这对高层节点的 计算能力，存储容量和节点能耗提出了很高的要求，同时，当网络规模较大时，如何确定一 个最优的小波变换级数，使得网络节点的平均能耗最小，还需要进一步探讨。 a c i m o v i cj 和c r i s t e s c ur 等人提出的算法 3 9 1 首先将监测区域内的节点进行奇偶排序，奇 节点将采集到的数据发送到相邻的偶节点，偶节点运用h a a r 小波对接收到的数据以及本节点 采集到的数据进行小波变换，并将得到的高频系数进行阈值处理后发往基站，同时对偶节点 进行新一轮的奇偶排序，将排序后奇节点内的低频系数发送到相邻偶节点，而偶节点继续运 用h a a r 小波对接收到的低频系数以及本节点的低频系数进行小波变换，重复以上变换过程直 到最后一组小波变换，最后将