基于時空冗余數據清除的數據備份算法*

潘燕燕，陳冬隱，程紅舉

(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高級會員，主要研究方向：計算機網絡、無線傳感器網絡。