基于最大时间阈值与自适应步长的时间相关性感知数据去冗余算法

朱容波, 李媛丽, 丁千傲, 虞脉

(中南民族大学 计算机科学学院，武汉 430074)

能耗始终是制约无线传感器网络性能的主要因素之一.传感器节点能耗主要由计算模块、通信模块、传感模块和电源模块四部分构成[1,2].研究表明，传感器节点间的传输能耗是影响网络生命周期的主要因素[3].随着无线传感器网络结构日趋复杂及逐渐朝大规模方向转变，科学、高效地解决传感网内的海量数据冗余及巨大能量消耗问题变得十分重要[4].

传感器网络数据去冗余技术则为解决上述问题提供了可能[5,6].近几年，数据去冗余的研究主要集中在统计学、数据压缩和机器学习三方面.在基于统计学的数据去冗余方面，GANJEWAR等[7]使用分层式最小二乘法缩减数据传输技术，传输Sink节点要求的数据，从而延长网络寿命.文献[8]提出了一种自适应时空相关预测算法，通过时间相关性与空间相关性预测感知数据，减少数据传输.DIAS等[9]通过数据传输协议(DaT)，减少冗余数据，降低数据传输能耗.

为减少传输数据量与降低数据传输能耗[10],LIAZID等采用历史数据表来更新模型参数的方式[11]，考虑传输率的情况，提高预测模型的精确度.SALMAN等[12]提出双向预测和数据采集的感知模型.RUSSO等[13]提出时间序列模型和基于非监督类型的机器学习预测分析算法.

基于数据压缩的去冗余方法在节省数据传输能耗方面具有良好的性能.李鹏等[14]的压缩感知高能效数据收集方案，将压缩感知应用于路由树协议，然而造成网络能耗不均衡.杨浩等[15]设计的区域化压缩感知数据收集方法，有效降低了数据传输量，且保留了数据原始特征.

尽管基于统计学、机器学习的数据去冗余算法能较好地提高数据压缩性能，但缺少对去冗余数据与原始数据间的关联性分析，在一定程度上降低了算法性能，导致高能耗与低生命周期的问题.基于压缩的方法能很好地减少数据，但存在数据精确度低的不足.虽然上述三类方法在降低数据传输能耗方面效果明显，但在一定程度上导致了部分重要特征数据的缺失，影响了传感器接入点决策的准确性.

为解决上述方法的不足，本文提出一种基于最大时间阈值与自适应步长的时间相关性感知数据去冗余算法(TCDA).TCDA针对数据波动平稳型的情况，引入最大时间阈值T_max控制数据相似阈值Th失效的问题，减少局部特征值的误差，实现通过部分特征数据准确获取感知数据的关键信息.针对计算能耗问题，TCDA采用自适应步长机制，结合数据相似距离计算规则的特点，控制数据相似比较步长，进而减少数据计算量，降低计算能耗.

1 去冗余算法TCDA

1.1 问题描述

传感器网络中包含一个汇聚节点(Sink)与N个传感器节点，汇聚节点位于探测区域外部，传感器节点随机分布在监测区域.系统模型如图1所示.系统主要由3个簇组成，每个簇中包含一个簇头(CHi)和一些簇内节点(SNi)，SNi负责采集自身感知数据，CHi负责采集自身感知数据的同时收集簇内各个节点的数据.Sink主要负责将各个簇头CHi收集的数据汇聚起来，然后发送给用户.TCDA算法涉及的符号如表1所示.

图1 系统模型图

表1 符号表

无线传感器网络中各个节点均以相同的频率对事件进行数据采集(如图2所示).

图2 无线传感器网络数据采集模式

CHi节点采集的数据集DCHi为：

DCHi={DSN1,DSN2,DSN3,…,DSNn}，

(1)

DSNi={x0,x1,x2,x3,x4,…,xn}，

(2)

RSNi=f(DSNi)，

(3)

RCHi={RSN1,RSN2,RSN3,…,RSNn}，

(4)

其中DSNi表示SNi节点在时间T={t0,t1,t2,t3,t4,…,tn}时，所采集的感知数据集合；RSNi表示SNi节点感知的数据DSNi经过冗余处理函数f(DSNi)处理后的结果数据；RCHi表示CHi最终经过冗余处理后的结果数据.由于存在SNi节点在时间T集合内对同一事件连续多次感知的情况，并且感知数据彼此间差异甚小，因此将{x1,x2,x3,x4}视为冗余数据去除，同时将非冗余数据传输给簇头CHi.

1.2 TCDA算法详细介绍

无线传感器网络采集数据具有时序性、有效性以及冗余度高的特点，同时已有方法存在冗余度高和计算量大的问题，TCDA算法不仅对无线传感器网络的时序性与有序性加以考虑，而且解决了冗余度高和计算量大的问题.TCDA算法如下所示.

Input: DSN1Output:RSN1,RTWHILE (sensor is lived)Do m←1;j←0 IF(i==0) RSN1←RSN1∪x0{} RT←RT∪t0{} ELSE FOR (j←j+m To n←len(Temp_Data))Do m←1⌊len(Temp_Data)2」{,⌊len(Temp_Data)2」=0,⌊len(Temp_Data)2」≠0 δi,j←xi-xj|; IF(δi,j≤Th AND t≤T_max) Temp_Data←Temp_Data∪{xi} END IF IF(δi,j>Th AND t>T_max) RSN1←RSN1∪{xi} RT←RT∪{ti} Temp_Data←Null END IF END FOR END ELSE i←i+1; Return RSN1, RTEND WHILE

去冗余算法的具体步骤如下:

Step1：获取传感器的感知数据，对冗余数据进行初步处理.

如图2中节点SN1传感器在时间集合T={t0,t1,t2,t3,…,tn}不同时间对应的感知数据为集合DSN1={x0,x1,x2,x3,x4,…,xn}，将首次感知的数据作为非冗余数据保存传输RSN1={x0},RT={t0}.

Step2：计算当前采集的感知数据与冗余数据集的数据相似距离矩阵S为:

S为对称矩阵，且对角线的元素为0.

ti与tj时刻的感知数据xi与xj的相似距离δi,j=|xi-xj|,0

Step3：设置相似距离阈值Th和最大时间阈值T_max，将数据相似距离δi,j和最大时间差t分别与Th和T_max的比较作为冗余条件；同时在去冗余的过程中，引入自适应步长m降低计算复杂性.

自适应步长m为：

其中，len(Temp_Data)为暂存冗余数据集的长度，即连续冗余数据量；每个冗余周期内的步长自适应更新，动态地改变δi,j=|xi-xj|中xi与xj两个数据的j=i,i=i+m索引位置.

每个周期内连续冗余感知数据的最远时间差t=ti-t0，其中ti表示第i次感知时间，t0表示每个周期内首个感知数据的时间.

冗余数据判断方法为,如果δij≤Th且t≤T_max，标记为冗余感知数据，进行去冗余操作;如果δi,j>Th且t>T_max，将ti时刻感知的数据，视为非冗余感知数据，进行保存传输RSN1=RSN1∪{xi},RT=RT∪{ti}.

Step4：输出时间相关性去冗余后感知数据，作为最终处理结果传输给CH1.

1.3 算法性能分析

假定一个冗余周期判别中的冗余数据量为n，TCDA算法的时间复杂度分析如下：第1步，获取感知数据的时间复杂度为O(n)，输出首次感知的非冗余数据的时间复杂度为O(1)；第2步，计算冗余数据相似距离矩阵的时间复杂度为O(n(n-1)/2)；第3步，在计算数据相似距离矩阵中加入自适应步长来调整比较步长后的时间复杂度为O(n2/m)；第4步，返回非冗余数据的时间复杂度为O(1).TCDA算法在第3步对非冗余数据进行了临时存储，空间复杂度为O(len(RSNi)).因此，TCDA算法的时间复杂度为O(n2/m)；空间复杂度为O(len(RSNi))，消息复杂度为O(len(RSNi)).

1.4 能耗分析

针对节点感知数据在时间相关性方面进行分析，仅讨论冗余数据与能耗的关系和算法性能对计算能耗的影响.

去冗余前的总能耗Et_f=Eut×Num_all，其中Eut是发送一单位数据的能耗，Num_all为去冗余前的总数据量：

去冗余后的总能耗Eall_b=Et_b+Ec，其中Et_b为去冗余后的传输能耗：

Et_b=Eut×(Num_all-Num_exist)，

其中Num_exist是去冗余后的数据量：

求解数据相似距离的计算能耗Ec=Eac×Com_num，其中Com_num为数据计算量.

2 仿真实验

2.1 实验环境

实验借助Anaconda中的函数工具包和Intel Berkeley研究室[16]测得的温度数据，由Python3.6平台实现.实验的主要参数设置如表2所示.

表2 仿真实验的参数设置

为了验证TCDA算法的有效性，实验中以数据丢失量Dnum、去冗余率r、传输能耗Et和计算能耗Ec作为评价指标，并与DaT算法[9]进行对比分析.

数据丢失量Dnum=(ti-ti-1)/0.5，其中ti表示第i个数据感知时间，ti-1表示第i-1个数据感知时间，0.5表示采集时间间隔(单位：min).

实验场景共有54个传感器，每个传感器0.5min采集一次数据，数据量包含一个月的感知数据，数据量达2×106条.实验对节点1的前3000条数据进行分析，如图3所示.

图3 节点1的原始数据

图3中x轴表示时间，y轴表示温度.随着时间的增加，温度缓慢下降，在380min温度达到17.5℃；随着时间继续增加，温度得以回升，在750min达到最高24.9℃；随后，温度呈现出先快后慢的下降趋势，在1830min降到最低17.3℃；在2220min时达到21.6℃，又开始下滑.在温度变化的整个过程中，用户最关注的是380、750、1830和2220min感知的峰值数据.因此，在数据去冗余过程中，需要着重分析这4个特殊位置的数据去冗余情况.

2.2 感知数据丢失情况分析

在数据传输过程中，存在大量数据丢失，若忽略该问题，去冗余过程中，面对感知数据变化平稳的情况，数据相似阈值Th控制失效，将会导致冗余范围更大，使得去冗余结果误差更大，进而影响Sink节点对数据的决策.因此，为解决以上问题，对感知数据的丢失情况做进一步的分析，如图4所示.

图4 数据丢失情况

从图4可以看出，数据丢失在数据采集过程中普遍存在，若不改进算法，会导致更多的数据被去除，Sink节点无法及时获取感知数据，将影响Sink节点对感知数据的最终决策.因此，通过加入最大时间阈值T_max解决相似距离阈值失效的问题.

2.3 算法的性能

以下从5个方面对算法的有效性与可行性进行分析：(1)最大时间控制T_max对去冗余率r的影响；(2)T_max=100，数据相似阈值Th对r的影响；(3)T_max=100，Th={0,0.25,0.5,1}对数据时效性的影响；(4)T_max=100，Th=0.5对传输能耗Et的影响；(5)T_max=100，Th=0.5对计算能耗Ec的影响.

最大时间阈值T_max对数据去冗余率r的影响如图5所示.

图5 T_max与r的关系

从图5可知，在T_max=0的时，T_max对算法不起作用，此时去冗余率r为0.96；随着T_max增加到10时，r急剧减小到0.84，表明T_max在0～10的范围内对去冗余率产生抑制作用；随后从10～100开始对去冗余率产生促进作用，然后在T_max=100之后，开始逐渐稳定，去冗余率维持在0.96左右，由此可以得出，在不影响去冗余率同时又可以解决数据时效性问题的情况下，最大时间阈值T_max=100可获得较优的性能.

当T_max=100时，随着Th的变化，去冗余率r的变化情况如图6所示.

图6 Th与r的关系

从图6可知，当Th=0时，对冗余控制不产生影响；随着阈值Th的增大，去冗余率的变化幅度由急剧转为缓慢再到保持平稳.当Th=0.1时，去冗余率受Th的影响很大，在0.1～0.2的范围内，开始变得缓慢，在0.2～0.5的范围内，变化更为缓慢，最后趋于平稳，说明Th越大对去冗余率的影响越小.因此，选择Th=0.5，对冗余数据的合理性与有效性进行分析.

当T_max=100，Th={0,0.25,0.5,1}时，对去冗余前后的数据时效性进行分析，如图7所示.图7中局部位置展示依次为图8(a)、(b)、(c)、(d)所示.

图7 加入T_max的结果对比

图8 图7局部数据放大图

引入时间间隔的T_max=100后，4个特殊位置的数据去冗余后的结果分析，如表3所示.

表3 去冗余情况

在数据相似距离阈值Th分别为1、0.5、0.25时，非冗余数据分别为59、74、116；图8中，380、750、1830和2220 min的位置，数据误差平均值大约为0.1，说明可以在保证去冗余率的情况下，降低重要位置数据的误差.在误差值均为0.1的情况下，Th=0.5时，传输数据量仅为74，减少了96%的数据量，同时又可以用尽量少的重要特征数据代表原始数据.然而，在数据波动比较细微的情况下，去冗余后的数据无法精细地展现出来，因此，如何在保证数据去冗余率的情况下，更加精细地描述数据的变化，有待进一步深入探索.

当T_max=100，Th=0.5时，TCDA与DaT算法的传输能耗与计算能耗如图9与图10所示.

图9 传输能耗提升率

图10 计算能耗使用率

图9显示，TCDA算法与DaT算法的传输能耗，随着节点规模的增大存在轻微的波动，在节点规模为0～10的范围内，两种算法的传输能耗提升率均大致表现为先升高再降低的趋势，最高分别达到97%与94.5%.随后两种算法的传输能耗均趋于平稳的状态，分别稳定在96%与93%.TCDA算法比DaT算法节省了3%的传输能耗.

如图10所示，TCDA算法与DaT算法的计算能耗随着节点规模的增大而增大.然而，DaT的计算能耗增加的幅度是TCDA的2～3倍.TCDA算法同DaT算法相比，节省了50%～60%的计算能耗.

上述实验结果表明，TCDA算法在传输能耗与计算能耗方面明显比DaT算法更具有优势.同时，在数据去冗余过程中，TCDA算法还考虑了数据丢失的情况，这更符合真实情景.

3 结论

针对传感器网络感知数据去冗余问题，提出了一种基于最大时间阈值及自适应步长的时间相关性感知数据去冗余算法(TCDA).实验结果表明：在不同规模的网络下，与DaT算法相比，TCDA降低了3%的传输能耗和50%的计算能耗，在确保感知数据特征的前提下，传感器网络生命周期得到显著的提升.下一步将对局部数据的精确度作深入研究.