基于时空冗余数据清除的数据备份算法*

潘燕燕，陈冬隐，程红举

(1.福州大学 数学与计算机科学学院，福建 福州 350108;2.福州大学 福建省网络计算与智能信息处理重点实验室，福建 福州 350108)

基于时空冗余数据清除的数据备份算法*

潘燕燕1,2，陈冬隐1,2，程红举1,2

(1.福州大学 数学与计算机科学学院，福建 福州350108;2.福州大学 福建省网络计算与智能信息处理重点实验室，福建 福州350108)

传感器节点易受环境影响，会出现节点失效的现象，导致感知数据丢失。然而无线传感器网络是以数据为中心，因此对感知数据进行备份问题的研究显得尤为重要。针对无线传感器网络中数据备份问题，提出基于时空冗余数据清除的数据备份算法(TS_DB)，该算法首先用k-means算法对网络分簇，然后挖掘出节点间的关联模式消除空间冗余数据，同时在传感节点建立一元线性回归模型消除时间冗余数据，最后根据簇头的能量进行数据备份。仿真实验表明，TS_DB算法能有效节省节点的能量，对延长网络的寿命具有重要的意义。

无线传感器网络；时空冗余数据；分簇；数据备份

0 引言

无线传感器网络由大量自组织的传感器节点组成，节点采用无线通信方式互连[1]。考虑到物理世界中许多限制，尤其在偏远和敌对区域，传感器节点产生的数据可能无法实时且不断地被收集，所以网络需要缓存感知数据一段时间。传感器节点部署在户外易受自然灾害的影响而失效,使得收集的数据残缺不全，数据质量不高，导致数据不能被有效地利用。针对此问题，已提出一些数据备份策略[2-8]。文献[2-3]提出的数据备份算法需要对所有的感知数据进行简单的均值等处理。JARDAK C等人[4]提出DISC算法，但其容错能力较弱。文献[5-6]提出基于编码的数据存储系统，这个系统能容忍一个簇中所有存储节点失效，但是所需的存储节点比数据节点的数量多。文献[7-8]提出备份算法，其需要加入额外的存储节点进行备份，增加额外的开销。

针对以上问题以及网络特性，本文提出了TS_DB算法。先对网络进行分簇，挖掘簇头节点和簇内节点的关联模式，对与簇头节点不存在关联模式的节点进行备份，与簇头节点存在关联模式的节点用簇头节点作为代表节点，来消除空间冗余数据。然后在与簇头节点不存在关联模式的节点上建立一元线性回归模型消除时间冗余数据，最后根据簇头的能量使用贪心算法尽可能多地进行备份数据。该算法能有效地减少传输和备份的数据量，大大节省网络的能量，对延长网络的寿命具有重要的意义。

1 网络模型及问题定义

假设无线传感器网络是由一组平面上部署的静态节点V={s1,s2,…,sn}组成，且节点具有相同的传输半径r。不失一般性，本文使用si和i表示同一个传感器节点。网络可描述为无向图G=(V,E)，其中V是传感器节点集，E是链路集合。在通信半径r内，任意两个节点间存在链路。本文设置的场景中，为了保证感知数据在网络中保存一段时间，sink节点每隔m个采集周期收集数据，文中用到的一些概念如表1所示。

表1 符号说明

定义1原始数据序列：节点si在数据序列长度为n内感知数据集合记为Xi={(t1,xi(1)),(t2,xi(2)),…,(tn,xi(n))}，可简化为Xi={xi(1),xi(2),…,xi(n)}。特别地，为了区分簇头节点和普通节点，将簇头节点的数据集标记为Ui={ui(1),ui(2),…,ui(n)}。

定义3差值序列：传感节点si和sj在数据序列长度为n内形成的差值序列为ΔX(i,j)={Δx(i,j)(1),Δx(i,j)(2),…,Δx(i,j)(n)}，其中Δx(i,j)(k)=xi(k)-xj(k)。

定义4关联模式矩阵：用常数l来拟合两节点si和sj间感知数据差值序列的均值。若拟合的误差小于给定的误差阈值，则判定两节点是相关的，标记关联模式矩阵为C[i,j]=l。

定义5代表节点：在一个簇内，簇头节点与簇内节点存在关联模式，簇头的感知数据可代表簇内的节点，则称簇头为代表节点。

2 算法

2.1 分簇

文献[9]提出传感器节点由6个工作模块组成，其中数据传输模块耗能是最大。因此，若直接将节点的感知数据发送到sink节点，易造成节点能量耗尽而死亡。本文采用k-means算法进行分簇，先将传感数据传送给簇头，再由簇头传送给基站，避免大量的节点直接将感知数据传送给sink节点，造成节点能量消耗过大而过早死亡。

k-means算法是典型的基于距离的聚类算法，用欧氏距离作为相似度测量的评价指标，即认为两个对象的距离越小，其相似度就越大。网络中传感节点是密集部署的，距离相近的节点感知数据的空间相关性越强。分簇算法的具体步骤如下：

(1)在网络中随机选取k个聚类质心节点。

(2)判断每个传感节点si所属的簇。需计算节点si到每个聚类质心节点uj的欧氏距离，节点si选取最小的欧氏距离作为该节点的聚类质心节点，并标记O[j,i]=1,表示质心节点uj是节点si的质心节点。

(3)重新计算每个聚类的均值。

(4)重复步骤(2)和步骤(3)，直至聚类质心节点不再移动。

2.2 空间相关性关联判断

根据实际物理现象的空间渐变性特征，节点间的空间相关性一般表现为：在一定的时间范围内，邻近的传感节点间采集的感知数据相同或相近，或者差值近似恒定。本文通过两节点的历史感知数据来挖掘它们之间的关联模式，如果簇头节点ui和簇内节点sj的历史原始数据序列的拟合误差小于给定的误差阈值ε,可判定簇内节点sj与簇头节点ui是空间相关的，则ui是sj的代表节点。只需簇头节点将关联模式传给sink节点来恢复簇内节点sj的感知数据，不需要传输节点sj的感知数据。

在一定时间范围内，簇头节点ui和簇内节点sj连续最新的m个连续历史感知数据分别为Ui={ui(1),ui(2),…,ui(m)}和Xj={xj(1),xj(2),…,xj(m)}，则节点ui和sj空间相关性判定步骤如下：

(1)节点ui和sj形成的差值序列为ΔX(i,j)={Δx(i,j)(1),Δx(i,j)(2),…,Δx(i,j)(m)}，其中Δx(i,j)(k)=ui(k)-xj(k)。

(2)由差值序列计算节点ui和sj原始数据序列均值为：

l=Mean(ΔX(i,j))=(Δx(i,j)(1)+Δx(i,j)(2)+…

Δx(i,j)(m))/m

(1)

(3)根据均值l计算两序列的拟合误差Error：

(2)

(4)若拟合误差Error小于给定的误差阈值ε，则可判定两节点的感知数据是关联的，并将关联模式l存入关联矩阵C[i,j]，反之不相关。

(5)重复步骤(1)～(4)，直至所有的簇内节点与簇头节点的关联模式都判定完。

当sink节点接收到簇头节点ui的感知数据时，利用簇头节点sj=ui(t)-l恢复出sj的感知数据，使得恢复的误差Error小于ε。

2.3 时间相关性关联判断

传感节点以周期性方式高频地采集数据，感知数据具有周期性的变化规律。对于单个节点采集的感知数据，可以看成以采样时间t作为自变量，对应的感知数据xi(t)作为因变量的分段线性函数关系。对于要发送感知数据的节点本文采用一元线性回归模型来消除时间冗余数据。

假设节点si的采集时间t和感知数据xi(t)形成的线性关系为回归方程式：

xi(t)=β0t+β1

(3)

已知节点si的数据序列为Xi={xi(1),xi(2),…,xi(m)}，根据最小二乘法拟合出一元线性回归模型中的β0和β1参数，求解β0和β1参数方程式为：

(4)

节点si采集的m个感知数据沿着时间轴依次分布于拟合的回归线附近。构建的一元线性回归模型如图1所示。若是第m+1个传感数据与预测的感知数据的绝对误差在给定的误差阀值内，则满足该模型，存在时间相关性，不需要传送该数据。时间相关性的判定步骤如下。

(1)利用节点si连续的m个历史数据，根据公式(4)计算ρ0和ρ1参数，并建立一元线性回归模型。

(4)若是δ≥ε，则不满足该模型，需要传送并备份该感知数据。若是连续m个感知数据都不满足该模型，则用最小二乘法重新计算β0和β1参数，重建新模型。

图1 一元线性回归模型示意图

2.4 数据备份

根据文献[10]中的能量模型，设置能量模型参数值分别为Eelec=50 nJ/bit,εfs=10 pJ/bit/m2,εmp=0.001 3 pJ/bit/m4。通过时空相关性的判定来确定簇头节点需要备份的感知数据，本节利用贪心算法根据簇头的剩余能量，进行备份。

文献[2]指出节点的剩余能量是最有意义的特征来预测节点的失效情况，而且与簇头存在关联模式的节点不需要传送数据，这些节点能节省大部分的能量，备份的节点可从关联矩阵中选择剩余能量最大的节点作为备份节点进行备份。备份的数量取决于簇头节点ui的剩余能量Energyi，尽可能多地备份到其他簇中，以应对多个簇中所有节点同时失效而造成的感知数据丢失。具体步骤如下。

(1)对每个簇中与簇头节点存在关联模式的节点进行剩余能量排序。

(2)簇头节点ui从关联矩阵中挑选剩余能量最大的节点进行备份并计算出传输能量Eelec。

(3)若是簇头节点ui的剩余能量与传输能量Eelec之间满足Energyi>Eelec,则进行备份，直至备份到所有的簇中满足Energyi

(4)重复步骤(1)～(3)，直至其他所有的簇头节点都选择好了备份节点。

(5)若是簇头节点失效，从关联矩阵中选择与簇头节点ui关联且剩余能量最大的节点作为簇头节点。

(6)计算各簇头节点以及sink节点之间的距离，存入矩阵A[i,j]。根据矩阵A[i,j]和Dijkstra算法计算各个簇头节点到sink节点最短路径，每隔m个采集周期进行数据收集。

2.5 算法实现

TS_DB算法伪代码如下。

Input:k,ε,m,Energy1,Energy2,…,Energyi,i∈V;

Output: C[i,j].

1 Run k-means algorithm to divide into k cluters,b=0;

2 For i=1; i≤k; i++ do

3 For j=1; j≤n; j++ do

4 Calculate Error with Formula(2);

5 If O[i,j]=1 and Error<ε then;

6 C[i,j]=Mean[Ui-Xj];

7 Else

8 Calculate β0and β1with Formula(4);

10 backup data to ui;b++;

11 If b>m then;

12 Recalculate β0and β1with Formula(4);

13 Sort every cluster correlative node energy

14 For z=1;z≤k;z++ do

15 If i≠z and Energyi-Eelec>0

16 backup data to the max remaining energy of node;

17 End for

18 End for

19 End for

3 实验

本文使用MATLAB作为仿真实验工具，在100 m×100 m的矩形区域内随机部署了|V|个完全相同的传感节点每个节点，的初始能量为1 J，将网络分为5个簇，其他的实验参数如表2所示。

表2 实验参数设置

采用文献[11]合成感知数据集中，随机产生h个事件Event={Event1(t),Event2(t),…,Eventh(t)}，每个事件的值从[20,40]中随机选取。事件Eventi在时刻t的值为Eventi(t)=Eventi(t-interval)+Z，其中Z是一个服从N～(0,0.1)的随机变量。

本文以网络寿命、数据恢复率、平均每个节点的能耗三个指标来对比本文提出的TS_DB算法和与数据备份相关的算法DISC[4]、Centralized Algorithm[8]。

设置节点数100到500，每次增加100，实验的结果如图2所示，网络寿命随着网络的节点个数增加而增加。TS_DB算法的网络寿命比相关算法的网络寿命长，由于随着传感节点数的增多，网络中节点间的空间冗余也增多，从而更多的冗余节点被用于延长传感网络的寿命。

图2 网络规模对网络寿命的影响

实验中设置节点死亡百分比从0到1.0，每次增加0.2。如图3所示，随着死亡节点百分比的增加，数据恢复百分比降低。TS_DB的算法优于其他算法。本文提出的数据备份算法是基于贪心算法尽可能多地进行数据备份，而且部分传感数据也可以通过关联矩阵进行恢复。

图3 死亡节点百分比对数据恢复百分比的影响

图4 时间对平均每个节点能耗的影响

设置网络中的时间从0到100，每次增加20。随着时间的增长，三种算法的平均每个节点的能耗的变化如图4所示。DISC和Centralized Algorithm两种算法的能耗基本上保持相对平缓的趋势，TS_DB算法由于挖掘出单个节点的时间相关性，减少数据的发送量，数据波动变化较大，但总体来说优于其他两种算法。

4 结论

数据备份能有效地解决传感器节点失效造成数据丢失的问题。本文提出基于时空冗余数据清除的数据备份算法，挖掘出传感节点在时间和空间纬度上的相关性，并消除冗余数据，最后利用贪心算法尽可能多地进行备份。实验结果表明，提出的TS_DB算法在网络寿命、数据恢复率、平均每个节点能耗明显优于DISC和Centralized Algorithm算法。

[1] YICK J,MUKHERJEE B,GHOSAL D. Wireless sensor network survey[J]. Computer networks,2008,52(12): 2292-2330.

[2] NEUMANN J,REINKE C,HOELLER N,et al. Adaptive quality-aware replication in wireless sensor networks[C]. Proceedings of WAMSNET 2009,Communications in Computer and Information Science (CCIS),2009,56: 413-420.

[3] GONIZZI P,FERRARI G,GAY V,et al. Data dissemination scheme for distributed storage for IoT observation systems at large scale[J]. Information Fusion,2015,22:16-25.

[4] KAYACAN E,ULUTAS B,KAYNAK O. Grey system theory-based models in time series prediction[J]. Expert Systems with Applications， 2010，37(2): 1784-1789．

[5] ALBANO M,CHESSA S. Distributed erasure coding in data centric storage for wireless sensor networks[C]. IEEE Symposium on Computers & Communications,2009: 22-27.

[6] DIMAKIS A,PRABHAKARAN V,RAMCHANDRAN K. Decentralized erasure codes for distributed networked storage[J]. IEEE Transactions on Information Theory,2006,52(6): 2809-2816.

[7] TALLNER B,MOSER H. Topology control for faulttolerant communication in highly dynamic wireless networks[C].Procaedings of the 3rd International Workshop on Intelligent Solutions in Embedded Systems(WISES 2005),2005,16(2): 89-100.

[8] Tian Jie,Yan Tan,Wang Guiling. A network coding based energy efficient data backup in survivability heterogeneous sensor networks[J]. IEEE Transactions on Mobile Computing,2015,14(10): 1992-2006.

[9] ESTRIN D. Wireless sensor networks tutorial part IV: sensor network protocols[C]. Proceedings of the Invited Speech of International Conference on Mobile Computing and Networking (MobiCom),2005: 23-28.

[10] HEINZELMAN W B,CHANDRAKASAN A P,BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networks[J].IEEE Transactions on Wireless Communications,2002,1(4):660-670.

[11] HUNG C C，PENG W C，LEE W C．Energy-aware set-covering approaches for approximate data collection in wireless sensor networks[J].IEEE Transactions on Knowledge and Data Engineering，2012，24(11): 1993-2007.

A data backup algorithm based on spatiotemporal correlation redundancy data clearance

Pan Yanyan1,2,Chen Dongyin1,2,Cheng Hongju1,2

(1. College of Mathematics and Computer Science,Fuzhou University,Fuzhou 350108,China;2.Fujian Key Laboratory of Network Computing and Intelligent Information Processing,Fuzhou University,Fuzhou 350108,China)

Sensor nodes are subject to environmental impact and appear the phenomenon of node failure,leading to loss of sensing data. However,the wireless sensor network is data-centric,so it is very important to study the backup of the sensing data. In this paper,a data backup algorithm (TS_DB) based on spatiotemporal redundancy data clearance is proposed for the data backup problem in WSNs. The algorithm firstly uses the k-means algorithm to cluster the networks and then digs out the association patterns between nodes to eliminate spatial redundancy data. Meanwhile,at sensor nodes a linear regression model is established to eliminate time redundant data,and finally according to the energy of cluster head data backup is realized. Simulation results show that TS_DB algorithm can effectively save the node’s energy,which is of great significance to extend the life of network.

wireless sensor networks; spatiotemporal redundancy data; clustering; data backup

国家自然科学基金(61370210)；福建省教育厅A类科技项目(2013JA12027)；福州大学科技发展基金(2013-XQ-35)资助

TP393

A

10.19358/j.issn.1674-7720.2017.24.016

潘燕燕，陈冬隐，程红举.基于时空冗余数据清除的数据备份算法J.微型机与应用，2017,36(24)：54-57，61.

2017-06-30)

潘燕燕(1991-)，女，硕士研究生，主要研究方向：无线传感器网络。

陈冬隐(1991-)，男，硕士研究生，主要研究方向：无线传感器网络。

程红举(1975-)，男，博士，教授，CCF高级会员，主要研究方向：计算机网络、无线传感器网络。