传感网络中误差有界的分段逼近数据压缩算法

内容需要下载文档才能查看

软件学报ISSN 1000-9825, CODEN RUXUEW E-mail: jos@http://wendang.chazidian.com

Journal of Software,2011,22(9):2149?2165 [doi: 10.3724/SP.J.1001.2011.03951] http://wendang.chazidian.com

©中国科学院软件研究所版权所有. Tel/Fax: +86-10-62562563

传感网络中误差有界的分段逼近数据压缩算法

张建明1, 林亚平2+, 傅 明1, 周四望2

1

2? (长沙理工大学 计算机与通信工程学院,湖南 长沙 410004) (湖南大学 信息科学与工程学院,湖南 长沙 410082)

Piecewise Approximation Based Data Compression Algorithm with Error Bound in Wireless

Sensor Networks

ZHANG Jian-Ming1, LIN Ya-Ping2+, FU Ming1, ZHOU Si-Wang2

1

2(School of Computer and Communication Engineering, Changsha University of Science and Technology, Changsha 410004, China) (School of Information Science and Engineering, Hu’nan University, Changsha 410082, China)

+ Corresponding author: E-mail: yplin@http://wendang.chazidian.com

Zhang JM, Lin YP, Fu M, Zhou SW. Piecewise approximation based data compression algorithm with error

bound in wireless sensor networks. Journal of Software, 2011,22(9):2149?2165. http://wendang.chazidian.com/

1000-9825/3951.htm

Abstract: Wireless sensor networks usually have limited energy and transmission capacity. A critical and practical

demand is to online compress sensor data streams continuously. This paper makes the following contributions. First,

using the built-in buffer of sensor node, a piecewise constant approximation based data compression algorithm with

infinite norm error bound is presented, which is named PCADC-sensor and is a near online algorithm. Second, with

infinite norm and square norm error bound respectively, this study proposes two online piecewise linear

approximation based data compression algorithms in sensor node, named PLADC-sensor. A necessary and sufficient

condition of PLA uniform approximation is given. Third, a piecewise linear representations based data compression

algorithm in cluster head or sink, named PLRDC-cluster is presented. It does not need raw sensory data and can be

applied to calculate aggregate functions. Last, the experiments on real-world sensor dataset show that the proposed

algorithms match the sensor data stream model and can achieve significant data reduction.

Key words: wireless sensor networks; data compression; segmentation; uniform approximation; square

approximation

摘 要: 无线传感器网络通常能量、带宽有限.一个关键而实用的需求是,在保证数据质量的情况下,对持续到达的

采样数据进行在线式压缩.主要贡献:① 利用传感器节点内置的缓冲区,提出了单传感器节点上基于分段常量逼近

的准在线式数据压缩算法(PCADC-sensor),并给出了在无穷范数误差度量下的实现;② 提出了单传感器节点上基

于分段线性逼近的在线式数据压缩算法(PLADC-sensor).分别在无穷范数和2范数误差度量的情况下给出了计算

PLA的两种简单快速算法,推导了分段线性一致逼近的充要条件;③ 簇头或基站无需接收原始采样数据,提出了基

于原始数据的分段线性表示的压缩算法(PLRDC-cluster),推导了同一节点不同时段、不同节点相同时段两种情况下

? 基金项目: 国家自然科学基金(60973031, 60973127); 湖南省科技计划(2010FJ6005); 长沙理工大学人才引进基金

收稿时间: 2009-09-30; 修改时间: 2010-03-04; 定稿时间: 2010-10-09

内容需要下载文档才能查看

2150 Journal of Software 软件学报 Vol.22, No.9, September 2011

的计算公式.实验结果表明,这些算法较好地匹配了传感器数据流模型,显著减少了冗余数据传输.

关键词: 传感器网络;数据压缩;分段;一致逼近;平方逼近

中图法分类号: TP393 文献标识码: A

无线传感器网络(WSN)能够协作地实时监测、感知、采集网络分布区域内的各种环境或监测对象的数据,并对这些数据进行处理,获得详尽而准确的信息,传送到需要这些信息的用户[1].WSN是物联网时代的关键支撑技术.组成WSN的传感器节点体积小、价格廉,能量和通信带宽有限.直接将节点采集的原始数据传输到基站是不可行的,一是带宽不够,二是能量将很快耗尽.无线通信消耗了大部分能量,研究[2]表明,将1位数据传输100米的耗能可以执行3000条CPU指令.因此,在传感器节点上要有效减少传输的数据量,从而延长网络寿命.在基站或数据中心,将源源不断的原始数据直接存档也是不可行的,需要将其精简近似表示,以减少存储的数据量.这些压缩表示最好能直接(或解压缩后)用于相应的监控、数据分析任务.

受噪音、节点失效、无线通信不可靠等因素影响,感知数据的获取、处理和传输中常常存在一定的误差.如果用户并不需要非常精确的结果,那么通过牺牲数据精度,可以达到减少通信和存储数据量的目的.针对具体应用场景,寻找能效、数据精度/粒度、通信延时的一个折衷.例如:使用聚集函数(aggregate function)可节能,但丢失了数据中大量的原始结构,只提供粗糙的统计量,掩饰了令人感兴趣的局部变化;使用小波概要(wavelet synopses)、分段逼近、直方图等的节能效果不如聚集函数,但可以更好地恢复出近似原始数据.

传感器节点持续产生的数据随时间流逝而变化,可以直观表示为一条平面曲线.平面曲线的逼近表示在模式识别、图像处理、图形学等领域非常重要,可达到特征提取、数据压缩、降噪等目的.除非曲线足够简单,否则多项式逼近或级数展开逼近效果不好,出现Runge现象.分段逼近可以较好地解决这个问题.数值分析中的分段插值不但要求在插值节点上函数值相等,还要求导数值也相等(Hermite插值),甚至要求高阶导数也相等(样条插值).我们通过低阶分段拟合来进行函数逼近,段数远小于采样数据的个数,而每段只需2个或3个数据来表示,实现有损数据压缩;不要求相邻各段连续,也不要求采样数据与逼近数据完全相等.

1 相关工作

时间序列的近似表示本质上就是降维,同时要保证误差有界,已有较丰富的研究成果.由于逼近子空间的不同构造(也就是基的选择或构造)以及范数的不同选取,形成了不同的数值逼近方法.根据逼近子空间的不同分为两类:① 使用分段不连续函数来逼近,包括离散小波变换(DWT)[3]、分段线性逼近(piecewise linear approximation,简称PLA)[4,5]、分段常量逼近(piecewise constant approximation,简称PCA)[6,7]、分段聚集逼近(piecewise aggregate approximation,简称PAA)[8]、符号化的聚集近似(symbolic aggregate approximation,简称SAX)[9].时间序列经过DWT变换后得到一个等长的小波系数序列,由于小波变换可以集中能量、消除相关性,因此小波系数序列中大部分细节分量值很小.精心挑选小波系数的一个子集,得到小波概要,以后可根据小波概要快速响应用户查询,并保证查询结果的精度.PLA用分段线性函数(即若干线段)来表示时间序列.PAA将包含n个数据的时间序列等分为p段(p<<n),每段长度均为n/p,用落在此段中数据的平均值代表本段.与PAA类似, PCA也是用一系列段来近似时间序列,每段用段内数据的均值表示,但是PCA各段的段长是可变的.SAX是时间序列的第1种符号化表示,SAX首先计算时间序列的PAA表示,然后对PAA系数进行量化,最后将每个量化级用单个字符表示;② 使用低阶连续函数来逼近,包括奇异值分解(SVD)、离散傅立叶变换(DFT)、样条函数、非线性回归、Chebyshev多项式.对传感器网络而言,SVD计算开销太大.DFT和Chebyshev多项式逼近类似于DWT,都是用正交函数作为基进行函数(即时间序列)展开和逼近,不同在于基函数的选择.根据众多前人的研究,没有哪种方法在不同应用领域性能都优秀.

数据压缩就是要消除数据间的冗余,即相关性.某个传感器节点采集的某个物理量在某段时间内的数据之间具有相关性(时间相关性);在某一时刻,某个传感器节点采集的不同物理量属性数据之间具有相关性(多属性相关性);在某一时刻,地理上较近的不同传感器节点采集的某个物理量数据之间具有相关性(空间相关性).数据

内容需要下载文档才能查看

张建明 等:传感网络中误差有界的分段逼近数据压缩算法

的相关性越高,数据压缩的效果越好. 2151

采用分段逼近消除数据空间相关性的论文我们暂未见到,因为一般采用分布式压缩算法降低数据的空间相关性.而综合能耗、精度、延时等因素考虑,分段逼近不适合于分布式计算.WSN中,通常将空间邻近的节点组织成簇,这样,簇头收集到的传感数据集便存在较强的空间相关性.对存在空间相关性的传感数据集进行小波变换,不仅可以提高低频小波系数的能量聚集比,还提高数据编码的效率,使得传感数据集的压缩比得以增加. Ciancio等人[10]研究小波压缩的分布式算法,通过在邻近的节点间交换信息,在数据传送到汇聚节点前分布式挖掘网络中数据的空间相关性,极大地减少了冗余数据的传输.虽然分布式压缩算法有效减少了网络中冗余数据的传输,然而节点间需要交换信息,由此产生的能量消耗、网络延时等代价尚需要在理论上进行进一步的定性分析.我们针对任意支撑长度的小波函数,给出了一种基于环模型的分布式时-空小波数据压缩算法[11],该算法可以同时消除传感器网络中数据的时间和空间相关性.实验表明,分布式二级小波变换的性能略优于分布式一级小波变换,因为虽然进行第2级小波变换会增加额外的耗能与延时,却取得了更好的去相关性.分布式小波变 换[10,11]中,不同传感器节点间的同级变换可以并行,但各级变换之间必须串行.随着分解级数的提高,数据的空间相关性在降低.因此,分布式算法不能总是依靠提高小波分解级数来提高性能,那会不断增加通信开销和延时.分布式压缩算法都建立在节点之间具有空间相关性的假设之上,且实现代价较大.如果空间相关性低甚至不存在,分布式算法几乎没有压缩效果反而有实现开销,得不偿失.另一方面,在人工放置传感器节点时,希望用最少的节点监测最大的范围,通常使节点的放置尽量彼此独立.例如,在智能大厦中,每个房间装有温度传感器,由于每个房间使用状况不同(空调的开关、门窗的开闭、人员的多少),相邻房间内温度也有较大差别,即监测值不具有空间相关性.因此,当节点监测值之间不存在空间相关性或空间相关性不稳定时,我们设计在各节点上独立运行的算法是更好的选择.

采用分段逼近来消除数据多属性相关性的核心思想是,选取某属性为基础信号,与之相关度较大的其他信号用分段逼近来表示.Deligiannakis[12]最先研究了多维数据流的多属性相关性.时间序列本身不是线性的,但不同序列在一段时间内可能存在线性相关.他提出的SBR算法将根据同一传感器节点上所有序列的数据分布特征挑出的基信号为自变量,用线性回归模型分段逼近其他序列.原始的多个时间序列可以表示为基信号加上一些回归参数.此方案能够消除多属性相关性和时间相关性,但仍有缺陷:① 需要不断将基信号更新传送到基站;② 压缩过程中未考虑数据误差,只是在满足数据压缩的条件下最大程度地压缩数据,没有保证压缩结果重构后误差有界;③ 回归参数的求解是基于L2误差的.Gandhi提出的GAMPS[7]框架同时对多个数据流进行压缩,可确保重构出的数据L∞误差有界.GAMPS根据各个数据流的相关性进行动态分组,相关大的数据流放在同一组以获得最佳压缩效果.每个组内挑选出一个基信号,采用PCA近似表示;其他信号除以基信号得到比例信号(ratio signal).比例信号比较平坦,再用PCA逼近可获得较高压缩率.但是,GAMPS不是在线算法,只适用于基站或数据中心对传感器数据进行存档处理,不适用于将数据从传感器收集到基站.GAMPS的静态/动态分组算法被转化为设施选址问题,而这是一个NP完全问题.我们提出了基于自适应回归的误差有界的多属性数据压缩算法[13],自适应指该算法可根据误差限和压缩收益自动选择传输原始数据还是传输回归系数,自动确定每次参与回归计算的数据个数.当多属性相关性减小或不稳定时,其压缩效果也很理想.

采用分段逼近来消除数据时间相关性是研究最广泛的[4?6].在许多应用中,用户获得精确值成本太高.设计单遍扫描算法、能实时给出近似查询结果就成为数据流模型下数据处理的目标.Lazaridis等人[6]采用PCA来逼近传感器数据,提出了确保重构L∞误差有界的PMC-MR和PMC-MEAN两个在线压缩算法.PMC-MR是段数最少的最优分段方法,但它不易应用于相似度检索系统中,且当数据分布偏向中值线某一边时,平均误差较大; PMC-MEAN减少了平均误差,但使用了更多的段.Soroush等人[5]采用分段线性逼近传感器数据,定义了确保重构L∞和L2误差有界的两个问题(PLA-PointBound和PLA-SegmentBound),巧妙地提出对应的在线压缩算法.但PLA-PointBound问题需要求各线段包含原始数据的个数个多边形的交集,计算开销太大.

本文采用2范数和无穷范数作为误差度量,研究计算简单、误差有界的分段逼近算法.主要工作是:① 利用传感器节点内置缓冲区,提出了单节点上基于分段常量逼近的准在线数据压缩算法(PCADC-sensor),给出了L∞

内容需要下载文档才能查看

2152 Journal of Software 软件学报 Vol.22, No.9, September 2011

误差有界的一种实现.在这种方式下,计算PLA的时间复杂度较大,故采用PCA;② 提出了单节点上基于分段线性逼近的在线式数据压缩算法(PLADC-sensor),推导了分段线性一致逼近的充要条件.分别在L∞和L2误差度量下给出了计算PLA的两种简单快速算法,而没有采用逼近效果平均稍差的PCA;③ 簇头或基站不需要接收其他传感器节点的原始采样数据,提出了直接基于分段线性表示(PLR)的数据压缩算法(PLRDC-cluster),推导了同一节点不同时间段、不同节点相同时间段这两种情况下的计算公式;④ 模拟实验表明,算法能够显著减少冗余数据的传输,比分布式算法具有更好的实时性和更低的开销.

2 预备知识

2.1 数据流分段逼近模型

设某个传感器节点采集的某个物理量的数据流为s[0],…,s[N?1],…,它是持续到达、潜在无限的.对这些数据进行分段,每段用一个常数(如均值)或一根线段(如斜率、截距)来表示.在保证每段内原始数据与逼近数据的误差小于预定误差限的条件下,在线式输出各段,从而极大地减少待传输的数据量.

%=(s%[0],...,s%[N?1]),记误考察某段时间内采集的N个数据为S=(s[0],…,s[N?1]),分段重构出的近似数据为S

%[i],e=(e[0],…,e[N?1]). 差e[i]=s[i]?s

%)=||e||=定义1(2-范数误差). L2(S,S2

.L2误差体现了两个向量间的整体累积误差,也叫

Euclidean距离.L2误差随数据个数(向量维数)的增加单调非递减.对于给定L2误差限,评价重构数据逼近原始数据的近似程度时,还与时间窗口大小有关.我们用分段逼近数据流时,要求每段的L2误差满足误差限要求.

误差体现了两个向量间的平均累积误差,消除了数 定义2(2-范数平均误差). 2据个数的影响,在实际应用中较有意义.

%)=||e||=max|e[i]|.L∞误差限保证了每个重构出来的数据与对应原始采样之 定义3(∞-范数误差). L∞(S,S∞0≤i<N

间的误差有界.

数据流误差有界的分段逼近,要求原始数据和重构数据之差在某种度量意义下有上界.相似度越大,误差越小,距离越短.采用L2误差作为距离度量时,称为平方逼近或均方逼近;采用L∞误差为距离度量时,称为一致逼近或均匀逼近.在实际应用中,一致逼近更有意义.

2.2 数据流分段算法

数据流分段算法可分为批处理(batch)方式和在线(online)方式两类:在线方式的逼近效果相对不好,但只要对数据顺序扫描一次;批处理方式可以产生高质量的逼近,但需要多次扫描整个数据集.各种资源都有限的传感器节点无法存储所有数据,采用在线方式更好.已有的数据流分段算法可以分为3类[4]:

(1) 滑动窗口分段(sliding window).过程是:① 将数据流的第1个数据作为第1个段的最左点,此时,第1个段的长度为1;② 计算将该段右边相邻的1个数据纳入该段后的拟合误差,如果小于误差限,段长增加1.继续考察该段右边相邻的数据,不断向右增加该段的长度.当到第i个数据点时,拟合误差超过了误差限,则第1~第i?1个数据构成了第1段;③ 第2段将第i个数据作为最左点,段长为1,类似地不断执行步骤②,依次得到后面各段.这种方法简单、直观,是一种在线算法.值得指出的是,当得到某个段以后,对应的数据可以马上释放,适用于传感器节点等存储空间小的情况.

(2) 自顶向下分段(top-down).这种方法逼近效果好、时间复杂度高,是一种批处理算法.过程是:① 将全部数据看成1段,依次考察将其分成2段的各种可能的划分方法,将其在最佳位置分成2段;② 分段后,分别测试这2个子段的拟合误差是否小于用户预定义的误差限.如果都满足误差限,则算法结束;否则,递归地将相应子段继续按步骤①再划分成2段,直到所有最新划分出的子段都满足误差限.

(3) 自底向上分段(bottom-up).这是自顶向下分段的逆过程:① 对长度为N的时间序列建立全部数据的最

内容需要下载文档才能查看

张建明 等:传感网络中误差有界的分段逼近数据压缩算法 2153

精确的逼近,即建立N个段(PCA)或(N+1)/2个段(PLA);② 依次计算序列中顺序相连的两个段如果合并的拟合误差,挑选出最小的合并误差;③ 若最小误差小于预定误差限,则将对应的相连两段进行合并,合并后的新段替换原来的两个段,计算新段与其前后段如果合并的拟合误差,再转步骤②;否则,算法结束.

3 单传感器节点上基于分段常量逼近的数据压缩算法

滑动窗口分段只考虑当前数据,没有纵观全局的能力,压缩效果较差.随着技术的发展,出现了各方面性能都更强大的传感器节点,存储能力有了显著增强,如Crossbow公司的Imote2节点有32MB数据存储空间.节点上可以缓存最近一段时间采集的大量数据,从而可以多次访问这些数据,取得比单纯滑动窗口分段更好的分段逼近效果.我们提出了单传感器节点上基于分段常量逼近的误差有界的数据压缩算法PCADC-sensor (piecewise constant approximation based data compression algorithm with error bound in sensor node).PCADC- sensor利用传感器节点所带缓冲区数据进行自底向上分段,但是增量式计算的,是一种准在线算法.虽然在这种方式下也可用PLA逼近,但反复计算PLA,时间复杂度较大,故采用PCA.

采用双循环队列来组织节点上采样数据缓冲区数组S,如图1所示,S大小为arraysize.定义队头指针指向队列首元素,队尾指针指向队列尾元素的下一个位置.正在进行分段处理的数据为以datafront为队头指针、datarear为队尾指针的处理队列(processing queue).在分段计算的同时,传感器又并发采集了若干数据,为以datarear为队头指针、readin为队尾指针的缓冲队列(buffering queue).带缓冲区的分段算法的基本框架是:① 最开始,两个队列皆空,datafront=datarear=readin,以后两个队列也可以通过队头指针等于队尾指针来判定队空;② 随着采样的进行,readin指针不断循环后移.当采集到arraysize/4个数据后,将readin赋值给datarear,相当于把缓冲队列里的全部数据传到了处理队列;③ 处理队列中的数据按自底向上分段(见算法1),以取得更好的逼近效果;④ 缓冲队列可并发继续存储新来采样.如果(readin+1)%arraysize等于datafront,则说明整个数组空间已满,强制转步骤⑤;⑤ 发送处理队列中计算出的第1个分段的表示数据,将对应采样数据清除出处理队列.在保证处理队列长度不超过arraysize/2的条件下,将缓冲队列中尽量多的数据纳入处理队列;⑥ 若处理队列长度小于arraysize/4,转步骤②.重复以上步骤③~步骤⑥.

Fig.1 Data buffer organization of sensor node (double circular queue)

图1 传感器节点的采样数据缓冲区(双循环队列)

数组空间大小、分段处理速度、采样频率将影响本算法性能.数组空间大的好处有:① 处理队列越长,越接近纯批处理方式的自底向上分段,压缩效果越好;② 当数据变化缓慢总是满足误差限时,整个处理队列中数据合并后只有1段,输出后希望缓冲队列中的数据也已经足够多,从而达到理想的压缩效果.上述算法保证了处理队列长度属于[arraysize/4,arraysize/2],缓冲队列有机会存放新来的采样.段长越长,数组空间就要越大,一般取平均段长的12~20倍为arraysize.数组空间大的缺点有:① 处理队列越长,造成分段速度越慢,从而可能导致缓冲队列溢出,故采用了计算相对简单的PCA;② 数组里数据越多,接收方得到数据的时延越大.易知,设a为待压