基于模型拟合的传感器网络数据处理算法

陈园园,朱欣颖

无线传感器网络(Wireless Sensor Network,WSN)是集传感器技术、嵌入式计算技术、分布式信息处理技术和无线通信技术为一体,由一系列带有无线射频发射模块和数据感知模块的无线传感器节点组成的无线网络系统.无线传感器网络技术具有多学科融合的知识特点,被广泛的应用在军事、医疗等诸多领域.但在实际的应用过程中,无线传感器网络的能量和带宽有限,难以满足数据传输的需求.有研究指出,数据通信的能耗远高于数据计算的能耗,数据传输消耗了总能量的70%[1].如果不对这些数据进行处理,则网络通信开销巨大,将消耗大量的节点能量.如何有效地减少网络内部的数据量,从而降低网络能量消耗是人们面临的一个重要挑战.

为了适应WSN的应用而产生了数据融合技术,它主要关注如何有效的对采集或接收到的其他传感器节点发送的大量数据进行融合处理,重点在于减少需要传输的数据.在无线传感器网络中,数据融合技术利用节点的本地计算和存储能力进行数据融合,去除冗余信息,减少通信过程中的数据量.数据融合技术可以与传感器网络的多个协议层结合,已经在目标跟踪、目标自动识别等领域得到了广泛应用.

目前,数据融合技术的多数研究主要集中在如何利用节点之间的时空相关性,来节省能量的传输数据.文献[2]提出了一种小波压缩算法,该算法依据传感数据的时间相关性和节点可用通信带宽选择待传输的小波系数、确定量化位和编码方法,能够在允许的误差范围内控制输出的数据量.文献[3]利用传感器网络中节点的空间相关性,用一部分节点的监测值来推算另一部分节点的监测值,通过相关节点的轮流工作和休眠来节省能量.文献[4]基于小波变换提出了一种渐进数据压缩算法,根据感知数据的空间相关性来选择传送数据的传感器节点,使得渐进传送的数据单元能产生大的编码增益,取得较高的压缩效率,减少了网络能耗.文献[5]中提到感知数据在传输过程中基于层次簇的方法进行数据压缩,减少网络中的数据传输量,从而节省了能量.

以上文献提到的算法并不适用于节点监测值直接不存在时空相关性或相关性不稳定的情况,因此笔者提出一种新的算法:基于三次B样条插值的拟合算法.该算法通过在传感器节点上对采集的数据进行模型拟合,来达到压缩数据,减少网络中数据传输量,从而减少网络数据传输能耗之目的.

1 模型建立

首先将传感器节点的监测数据组织成一个感知数据序列,然后在该感知数据序列上寻找具有最小数据传输比的拟合模型.

如图1所示为基于拟合模型的算法流程图.

第一步:数据集是由监测区域的传感器网络节点采集.

第二步:无线传感器网络中的每个节点数据缓存至本地节点的存储器内.

第三步:当存储器内的监测数据集达到一个给定的阀值时,依据样条插值算法对数据进行拟合处理.

第四步:找到一个最佳模型M,然后把模型M及其参数传回给汇聚节点.

图1 基于拟合模型的算法流程图

2 样条方法

在遇到一组给定的离散有序样本点时,经常用线段将它们光滑的连接起来进行曲线拟合,WSN中的感知数据刚好符合这些特点.曲线拟合的方法很多,其中B样条曲线是连续的且不用通过每个样本点,比贝塞尔曲线更加光滑,另外B样条函数在做曲线拟合的时候如果一个样本点改变了,也仅仅影响到附近的一段曲线而不是整条曲线,比其他拟合方法更加有效[6].

样条即一类分段(片)光滑并且在各段交接处也有一定光滑性的函数,可克服高次多项式插值出现的振荡现象,具有良好的数值稳定性和收敛性.它既保持了多项式的简单性质和逼近的可行性,又在各段之间保持了相对独立的局部性质.因此样条是一类特别有效的逼近工具.设给定一组结点:

又设分段函数S(x)满足条件:

(1)在每个区间[xj,xj+1](j=0,…,N)上,S(x)为次数不超n的实系数代数多项式;

(2)S(x)在(-∞,+∞)上有直到n-1阶的连续导数.

则称y=s(x)为n次样条函数.常把以(1)式为结点的n次样条函数的总体记为Sn(x1,x2,…,xN-1,xN),x1,x2,…,xN-1,xN称为样条节点.

B样条曲线是由一组基函数和一些控制顶点定义.其中三次B样条应用最广,三次B样条的基函数可以表述为下列形式:

设有n+1个感知数据点p0,p1,…,pn,每四个相邻的点可以构造一段三次B样条曲线,例如pi,pi+1,pi+2,pi+3这四个点决定的三次B样条曲线的表达式为:

变换成矩阵形式为:

其中1≤i≤n-3,参数u∈[0,1]

这n-3段三次抛物线就光滑的拼接成了一条完整的三次B样条曲线.

假设{a=t0＜t1＜…＜tN=b}为N+1个节点,令

再设以U为节点向量的参数三次B样条曲线满足容差要求,由于t0=a,tN=b,设r={r1,r2,…,rN-1},0＜ri＜1,i=1,2,…,N-1,那么,

整理得对角占优的三对角线

将样条节点的分布问题转化为(5)式中三对角矩阵的构造问题上来,显然,如果r={r1,r2,…,rN-1}选择得当,将其代入方程组(6)中很容易用追赶法求得内节点{t1,…,tN-1},容易看出,用参数的三次B样条曲线插值能够很好的逼近给定数据点.

3 基于样条的BFM算法

数据拟合被分为多项式插值和样条插值[7],要拟合无线传感器采集到的大量数据,样条插值比多项式插值的效果要好很多.

图2 多项式插值与样条插值拟合比较图

图3 B样条曲线拟合模型图

如图2所示,取sin函数部分值为一观测序列,分别用多项式和B样条进行拟合逼近,图中蓝色曲线为B样条插值拟合结果,红色曲线为分段多项式插值拟合结果,明显看到红色曲线有空隙而蓝色几乎看不到空隙,蓝色的曲线比红色曲线逼近程度要高,所以B样条插值拟合效果更好.图3显示了B样条曲线拟合模型,图中绘出了各个控制点,光滑的曲线就是由这些控制点形成的.

BFM算法设计思想:结合拟合模型算法,为使数据序列能够得到更逼近的曲线拟合,笔者采用三次B样条曲线拟合模型,在选取的数据序列上建立拟合模型,根据三次B样条曲线的理论知识,笔者的数据序列上的每四个数据点都可以形成一段光滑的三次B样条曲线,进而拟合所有的数据点,得到最佳拟合模型传送给汇聚节点,未被拟合的数据直接传送给汇聚节点.

基于样条拟合模型BFM算法问题定义如下:

设传感器节点采集的单一属性数据量为N,属性种类为k,则共有N×k个数据点,选择B样条曲线拟合次数为三次,称未被拟合的数据为奇异点.

对长度为N的数据序列y1,y2,…,yN,每四个点yi,yi+1,yi+2,yi+3,i∈[1,N]决定一段三次B样条曲线,根据前面三次样条基函数表达式(2),则一段三次B样条曲线的表达式为

根据系数矩阵可得

这N-2段三次样条曲线就构成了一段完整光滑的样条曲线.被拟合的基函数数目为k.其中

最终拟合模型中的序列^y为原始序列y的近似序列,残差平方和为

4 仿真结果与分析

本实验仿真采用两个数据集,其中一个数据集是英特尔伯克利实验室已采集的各属性监测值[8],是由54个mica2传感器节点在36 d内每31 s一次收集的监测数据,数据收集在Tiny DB网络查询处理系统中完成,系统是建立在Tiny OS平台上,数据类型包含了温度、湿度和光照电压值.另一个是由韩伯电子开发的ZigbeX无线传感器采集的真实数据,该无线传感器模块内含传感器节点10个,能够获得一个月内所产生的监测数据,这些数据分别是对湿度、温度和光照进行的采样.实时采样的串口通信软件参数设置为:端口连接COM3,波特率为57 600,数据位为8,停止位为1,数据缓存位置为D:CO MDATA,数据保存形式为十进制.

有研究指出,无线传感器网络的监测数据随时间呈周期性连续变化,而且在许多应用中的数据也有类似变化规律[9],为了减少数据冗余,减少数据传输能耗,笔者采用BFM算法最大限度的拟合监测数据的这种变化趋势.

WSN中的数据并不需要非常精确或者完备,只需它在一个允许的误差范围内即可,因此,为降低网络通信能耗可以在减少数据冗余和降低数据量的时候损失一些数据精度.

常用的数据压缩算法性能指标有:传输比(Transmission Ratio,TR)

其中,S(x)是压缩后的数据序列,S原(x)是原始未被压缩的数据序列.传输比与压缩后数据成正比,传输比TR越小,压缩后的数据越少,说明传输的数据量越小,则通信能量消耗就越小.

另一个性能指标是残差平方和(Sum of Squares for Error,SE)

其中,n代表输入的数据序列长度,S(x)是压缩后的数据序列,S原(x)是原始未被压缩的数据序列.

用C++实现了三次B样条自适应算法,并在监测数据集上对其性能进行了测试.

表1和表2分别对用户的误差容忍度、节点的存储容量等方面对节点的数据传输量进行了对比.温度的一般误差容忍度是0.5,湿度的误差容忍度是2%,根据节点的存储能力,设定节点的存储容量在200-500内变动.从表1中可以看出整体的SE还是很小,随着允许容错的增大,SE也变大了,因为允许的误差范围越大,能够被拟合的数据相对就减少了,拟合数据与原始数据的方差会变大,那么残差也会相应的变大.在表2中显示的一组温度数据在不同节点容量下的SE,可以看出随着节点容量的增多,SE也逐渐增大.

表1 一组温度数据在不同容错下的SE

表2 一组温度数据在不同节点容量下的SE

目前,在节点不具有时空相关性的情况下,一个传统的检测数据采集策略是加州大学伯克利分校的Tiny DB,该策略是向sink节点传送所有监测数据.而笔者的策略是仅传回一个最佳拟合模型M.

图4中,显示了Tiny DB策略和BFM算法在不同容错下的室内、室外温度数据传输率,横坐标代表允许的误差,纵坐标代表传输率.虽然笔者的算法丢失了部分精度,但是并不影响算法的性能.从图中也很明显的看到,BFM算法的传输率比Tiny DB策略高很多.

图4 不同容错下数据传输比

5 结论

针对无线传感器网络能源有限且难以补充的特点,提出了一种基于三次B样条插值的BMF算法,该算法通过传输模型及其参数来代替传输实际的监测值,以达到压缩数据,减少数据传输量的目的.且笔者给出的算法能够保证在一定的误差容忍范围内有可靠的置信度.由于该算法不依赖数据的时空相关性,因此在节点的监测值之间不存在时间相关性或相关性较低时,仍可以发挥原有的性能,使得该算法具有更广阔的应用范围和空间.

参考文献:

[1]Kimura N,Latifi S.A survey on data compression in wireless sensor networks[J].Proc of the Int’l Conf on Information Technology:Coding and Computing.Piscataway:IEEE Press,2005(2):8-13.

[2]Chen Huamin,Li Jian,Mohapatra P.RACE:Time Series Compression with Rate Adaptivity and Error Bound for Sensor Networks[C]//Proc.of IEEE International Conference on Mobile Ad-hoc and Sensor Systems.[S.1.]:IEEE Press,2004.

[3]Q Cao,T Abdelzaher,T He,et al.Towards optimal sleep scheduling in sensor networks for rare event detection[C]//Information Processing in Sensor Networks,Los Angeles,USA,2005.

[4]周四望,林亚平,叶松涛,等.传感器网络中一种存储有效的小波渐进数据压缩算法[J].计算机研究与发展,2009,46(12):2085-2092.

[5]贺智勇,龙陈锋,王桐森,等.传感器网络中层次簇模型数据压缩算法[J].计算机工程,2009,35(13):105-108.

[6]戴仕全.自适应三次样条插值逼近算法研究[D].大连:大连理工大学,2008.

[7]李庆阳,王能超,易大义.数值分析[M].北京:清华大学出版社,2008:25-28.

[8]MaddenS.Intel Berkeley research lab data[EB/OL].(2003).http//berkeleyi.ntel-research.net/labdata.

[9]G Tolle,Sonoma redwoods data[OL],http//www.cs.berkeley.edu/～get/sonoma,2005.