基于時空冗余數(shù)據(jù)清除的數(shù)據(jù)備份算法*

潘燕燕，陳冬隱，程紅舉

(1.福州大學(xué) 數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院，福建 福州 350108;2.福州大學(xué) 福建省網(wǎng)絡(luò)計算與智能信息處理重點實驗室，福建 福州 350108)

基于時空冗余數(shù)據(jù)清除的數(shù)據(jù)備份算法*

潘燕燕1,2，陳冬隱1,2，程紅舉1,2

(1.福州大學(xué) 數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院，福建 福州350108;2.福州大學(xué) 福建省網(wǎng)絡(luò)計算與智能信息處理重點實驗室，福建 福州350108)

傳感器節(jié)點易受環(huán)境影響，會出現(xiàn)節(jié)點失效的現(xiàn)象，導(dǎo)致感知數(shù)據(jù)丟失。然而無線傳感器網(wǎng)絡(luò)是以數(shù)據(jù)為中心，因此對感知數(shù)據(jù)進(jìn)行備份問題的研究顯得尤為重要。針對無線傳感器網(wǎng)絡(luò)中數(shù)據(jù)備份問題，提出基于時空冗余數(shù)據(jù)清除的數(shù)據(jù)備份算法(TS_DB)，該算法首先用k-means算法對網(wǎng)絡(luò)分簇，然后挖掘出節(jié)點間的關(guān)聯(lián)模式消除空間冗余數(shù)據(jù)，同時在傳感節(jié)點建立一元線性回歸模型消除時間冗余數(shù)據(jù)，最后根據(jù)簇頭的能量進(jìn)行數(shù)據(jù)備份。仿真實驗表明，TS_DB算法能有效節(jié)省節(jié)點的能量，對延長網(wǎng)絡(luò)的壽命具有重要的意義。

無線傳感器網(wǎng)絡(luò)；時空冗余數(shù)據(jù)；分簇；數(shù)據(jù)備份

0 引言

無線傳感器網(wǎng)絡(luò)由大量自組織的傳感器節(jié)點組成，節(jié)點采用無線通信方式互連[1]。考慮到物理世界中許多限制，尤其在偏遠(yuǎn)和敵對區(qū)域，傳感器節(jié)點產(chǎn)生的數(shù)據(jù)可能無法實時且不斷地被收集，所以網(wǎng)絡(luò)需要緩存感知數(shù)據(jù)一段時間。傳感器節(jié)點部署在戶外易受自然災(zāi)害的影響而失效,使得收集的數(shù)據(jù)殘缺不全，數(shù)據(jù)質(zhì)量不高，導(dǎo)致數(shù)據(jù)不能被有效地利用。針對此問題，已提出一些數(shù)據(jù)備份策略[2-8]。文獻(xiàn)[2-3]提出的數(shù)據(jù)備份算法需要對所有的感知數(shù)據(jù)進(jìn)行簡單的均值等處理。JARDAK C等人[4]提出DISC算法，但其容錯能力較弱。文獻(xiàn)[5-6]提出基于編碼的數(shù)據(jù)存儲系統(tǒng)，這個系統(tǒng)能容忍一個簇中所有存儲節(jié)點失效，但是所需的存儲節(jié)點比數(shù)據(jù)節(jié)點的數(shù)量多。文獻(xiàn)[7-8]提出備份算法，其需要加入額外的存儲節(jié)點進(jìn)行備份，增加額外的開銷。

針對以上問題以及網(wǎng)絡(luò)特性，本文提出了TS_DB算法。先對網(wǎng)絡(luò)進(jìn)行分簇，挖掘簇頭節(jié)點和簇內(nèi)節(jié)點的關(guān)聯(lián)模式，對與簇頭節(jié)點不存在關(guān)聯(lián)模式的節(jié)點進(jìn)行備份，與簇頭節(jié)點存在關(guān)聯(lián)模式的節(jié)點用簇頭節(jié)點作為代表節(jié)點，來消除空間冗余數(shù)據(jù)。然后在與簇頭節(jié)點不存在關(guān)聯(lián)模式的節(jié)點上建立一元線性回歸模型消除時間冗余數(shù)據(jù)，最后根據(jù)簇頭的能量使用貪心算法盡可能多地進(jìn)行備份數(shù)據(jù)。該算法能有效地減少傳輸和備份的數(shù)據(jù)量，大大節(jié)省網(wǎng)絡(luò)的能量，對延長網(wǎng)絡(luò)的壽命具有重要的意義。

1 網(wǎng)絡(luò)模型及問題定義

假設(shè)無線傳感器網(wǎng)絡(luò)是由一組平面上部署的靜態(tài)節(jié)點V={s1,s2,…,sn}組成，且節(jié)點具有相同的傳輸半徑r。不失一般性，本文使用si和i表示同一個傳感器節(jié)點。網(wǎng)絡(luò)可描述為無向圖G=(V,E)，其中V是傳感器節(jié)點集，E是鏈路集合。在通信半徑r內(nèi)，任意兩個節(jié)點間存在鏈路。本文設(shè)置的場景中，為了保證感知數(shù)據(jù)在網(wǎng)絡(luò)中保存一段時間，sink節(jié)點每隔m個采集周期收集數(shù)據(jù)，文中用到的一些概念如表1所示。

表1 符號說明

定義1原始數(shù)據(jù)序列：節(jié)點si在數(shù)據(jù)序列長度為n內(nèi)感知數(shù)據(jù)集合記為Xi={(t1,xi(1)),(t2,xi(2)),…,(tn,xi(n))}，可簡化為Xi={xi(1),xi(2),…,xi(n)}。特別地，為了區(qū)分簇頭節(jié)點和普通節(jié)點，將簇頭節(jié)點的數(shù)據(jù)集標(biāo)記為Ui={ui(1),ui(2),…,ui(n)}。

定義3差值序列：傳感節(jié)點si和sj在數(shù)據(jù)序列長度為n內(nèi)形成的差值序列為ΔX(i,j)={Δx(i,j)(1),Δx(i,j)(2),…,Δx(i,j)(n)}，其中Δx(i,j)(k)=xi(k)-xj(k)。

定義4關(guān)聯(lián)模式矩陣：用常數(shù)l來擬合兩節(jié)點si和sj間感知數(shù)據(jù)差值序列的均值。若擬合的誤差小于給定的誤差閾值，則判定兩節(jié)點是相關(guān)的，標(biāo)記關(guān)聯(lián)模式矩陣為C[i,j]=l。

定義5代表節(jié)點：在一個簇內(nèi)，簇頭節(jié)點與簇內(nèi)節(jié)點存在關(guān)聯(lián)模式，簇頭的感知數(shù)據(jù)可代表簇內(nèi)的節(jié)點，則稱簇頭為代表節(jié)點。

2 算法

2.1 分簇

文獻(xiàn)[9]提出傳感器節(jié)點由6個工作模塊組成，其中數(shù)據(jù)傳輸模塊耗能是最大。因此，若直接將節(jié)點的感知數(shù)據(jù)發(fā)送到sink節(jié)點，易造成節(jié)點能量耗盡而死亡。本文采用k-means算法進(jìn)行分簇，先將傳感數(shù)據(jù)傳送給簇頭，再由簇頭傳送給基站，避免大量的節(jié)點直接將感知數(shù)據(jù)傳送給sink節(jié)點，造成節(jié)點能量消耗過大而過早死亡。

k-means算法是典型的基于距離的聚類算法，用歐氏距離作為相似度測量的評價指標(biāo)，即認(rèn)為兩個對象的距離越小，其相似度就越大。網(wǎng)絡(luò)中傳感節(jié)點是密集部署的，距離相近的節(jié)點感知數(shù)據(jù)的空間相關(guān)性越強。分簇算法的具體步驟如下：

(1)在網(wǎng)絡(luò)中隨機(jī)選取k個聚類質(zhì)心節(jié)點。

(2)判斷每個傳感節(jié)點si所屬的簇。需計算節(jié)點si到每個聚類質(zhì)心節(jié)點uj的歐氏距離，節(jié)點si選取最小的歐氏距離作為該節(jié)點的聚類質(zhì)心節(jié)點，并標(biāo)記O[j,i]=1,表示質(zhì)心節(jié)點uj是節(jié)點si的質(zhì)心節(jié)點。

(3)重新計算每個聚類的均值。

(4)重復(fù)步驟(2)和步驟(3)，直至聚類質(zhì)心節(jié)點不再移動。

2.2 空間相關(guān)性關(guān)聯(lián)判斷

根據(jù)實際物理現(xiàn)象的空間漸變性特征，節(jié)點間的空間相關(guān)性一般表現(xiàn)為：在一定的時間范圍內(nèi)，鄰近的傳感節(jié)點間采集的感知數(shù)據(jù)相同或相近，或者差值近似恒定。本文通過兩節(jié)點的歷史感知數(shù)據(jù)來挖掘它們之間的關(guān)聯(lián)模式，如果簇頭節(jié)點ui和簇內(nèi)節(jié)點sj的歷史原始數(shù)據(jù)序列的擬合誤差小于給定的誤差閾值ε,可判定簇內(nèi)節(jié)點sj與簇頭節(jié)點ui是空間相關(guān)的，則ui是sj的代表節(jié)點。只需簇頭節(jié)點將關(guān)聯(lián)模式傳給sink節(jié)點來恢復(fù)簇內(nèi)節(jié)點sj的感知數(shù)據(jù)，不需要傳輸節(jié)點sj的感知數(shù)據(jù)。

在一定時間范圍內(nèi)，簇頭節(jié)點ui和簇內(nèi)節(jié)點sj連續(xù)最新的m個連續(xù)歷史感知數(shù)據(jù)分別為Ui={ui(1),ui(2),…,ui(m)}和Xj={xj(1),xj(2),…,xj(m)}，則節(jié)點ui和sj空間相關(guān)性判定步驟如下：

(1)節(jié)點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)由差值序列計算節(jié)點ui和sj原始數(shù)據(jù)序列均值為：

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

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

(1)

(3)根據(jù)均值l計算兩序列的擬合誤差Error：

(2)

(4)若擬合誤差Error小于給定的誤差閾值ε，則可判定兩節(jié)點的感知數(shù)據(jù)是關(guān)聯(lián)的，并將關(guān)聯(lián)模式l存入關(guān)聯(lián)矩陣C[i,j]，反之不相關(guān)。

(5)重復(fù)步驟(1)～(4)，直至所有的簇內(nèi)節(jié)點與簇頭節(jié)點的關(guān)聯(lián)模式都判定完。

當(dāng)sink節(jié)點接收到簇頭節(jié)點ui的感知數(shù)據(jù)時，利用簇頭節(jié)點sj=ui(t)-l恢復(fù)出sj的感知數(shù)據(jù)，使得恢復(fù)的誤差Error小于ε。

2.3 時間相關(guān)性關(guān)聯(lián)判斷

傳感節(jié)點以周期性方式高頻地采集數(shù)據(jù)，感知數(shù)據(jù)具有周期性的變化規(guī)律。對于單個節(jié)點采集的感知數(shù)據(jù)，可以看成以采樣時間t作為自變量，對應(yīng)的感知數(shù)據(jù)xi(t)作為因變量的分段線性函數(shù)關(guān)系。對于要發(fā)送感知數(shù)據(jù)的節(jié)點本文采用一元線性回歸模型來消除時間冗余數(shù)據(jù)。

假設(shè)節(jié)點si的采集時間t和感知數(shù)據(jù)xi(t)形成的線性關(guān)系為回歸方程式：

xi(t)=β0t+β1

(3)

已知節(jié)點si的數(shù)據(jù)序列為Xi={xi(1),xi(2),…,xi(m)}，根據(jù)最小二乘法擬合出一元線性回歸模型中的β0和β1參數(shù)，求解β0和β1參數(shù)方程式為：

(4)

節(jié)點si采集的m個感知數(shù)據(jù)沿著時間軸依次分布于擬合的回歸線附近。構(gòu)建的一元線性回歸模型如圖1所示。若是第m+1個傳感數(shù)據(jù)與預(yù)測的感知數(shù)據(jù)的絕對誤差在給定的誤差閥值內(nèi)，則滿足該模型，存在時間相關(guān)性，不需要傳送該數(shù)據(jù)。時間相關(guān)性的判定步驟如下。

(1)利用節(jié)點si連續(xù)的m個歷史數(shù)據(jù)，根據(jù)公式(4)計算ρ0和ρ1參數(shù)，并建立一元線性回歸模型。

(4)若是δ≥ε，則不滿足該模型，需要傳送并備份該感知數(shù)據(jù)。若是連續(xù)m個感知數(shù)據(jù)都不滿足該模型，則用最小二乘法重新計算β0和β1參數(shù)，重建新模型。

圖1 一元線性回歸模型示意圖

2.4 數(shù)據(jù)備份

根據(jù)文獻(xiàn)[10]中的能量模型，設(shè)置能量模型參數(shù)值分別為Eelec=50 nJ/bit,εfs=10 pJ/bit/m2,εmp=0.001 3 pJ/bit/m4。通過時空相關(guān)性的判定來確定簇頭節(jié)點需要備份的感知數(shù)據(jù)，本節(jié)利用貪心算法根據(jù)簇頭的剩余能量，進(jìn)行備份。

文獻(xiàn)[2]指出節(jié)點的剩余能量是最有意義的特征來預(yù)測節(jié)點的失效情況，而且與簇頭存在關(guān)聯(lián)模式的節(jié)點不需要傳送數(shù)據(jù)，這些節(jié)點能節(jié)省大部分的能量，備份的節(jié)點可從關(guān)聯(lián)矩陣中選擇剩余能量最大的節(jié)點作為備份節(jié)點進(jìn)行備份。備份的數(shù)量取決于簇頭節(jié)點ui的剩余能量Energyi，盡可能多地備份到其他簇中，以應(yīng)對多個簇中所有節(jié)點同時失效而造成的感知數(shù)據(jù)丟失。具體步驟如下。

(1)對每個簇中與簇頭節(jié)點存在關(guān)聯(lián)模式的節(jié)點進(jìn)行剩余能量排序。

(2)簇頭節(jié)點ui從關(guān)聯(lián)矩陣中挑選剩余能量最大的節(jié)點進(jìn)行備份并計算出傳輸能量Eelec。

(3)若是簇頭節(jié)點ui的剩余能量與傳輸能量Eelec之間滿足Energyi>Eelec,則進(jìn)行備份，直至備份到所有的簇中滿足Energyi

(4)重復(fù)步驟(1)～(3)，直至其他所有的簇頭節(jié)點都選擇好了備份節(jié)點。

(5)若是簇頭節(jié)點失效，從關(guān)聯(lián)矩陣中選擇與簇頭節(jié)點ui關(guān)聯(lián)且剩余能量最大的節(jié)點作為簇頭節(jié)點。

(6)計算各簇頭節(jié)點以及sink節(jié)點之間的距離，存入矩陣A[i,j]。根據(jù)矩陣A[i,j]和Dijkstra算法計算各個簇頭節(jié)點到sink節(jié)點最短路徑，每隔m個采集周期進(jìn)行數(shù)據(jù)收集。

2.5 算法實現(xiàn)

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的矩形區(qū)域內(nèi)隨機(jī)部署了|V|個完全相同的傳感節(jié)點每個節(jié)點，的初始能量為1 J，將網(wǎng)絡(luò)分為5個簇，其他的實驗參數(shù)如表2所示。

表2 實驗參數(shù)設(shè)置

采用文獻(xiàn)[11]合成感知數(shù)據(jù)集中，隨機(jī)產(chǎn)生h個事件Event={Event1(t),Event2(t),…,Eventh(t)}，每個事件的值從[20,40]中隨機(jī)選取。事件Eventi在時刻t的值為Eventi(t)=Eventi(t-interval)+Z，其中Z是一個服從N～(0,0.1)的隨機(jī)變量。

本文以網(wǎng)絡(luò)壽命、數(shù)據(jù)恢復(fù)率、平均每個節(jié)點的能耗三個指標(biāo)來對比本文提出的TS_DB算法和與數(shù)據(jù)備份相關(guān)的算法DISC[4]、Centralized Algorithm[8]。

設(shè)置節(jié)點數(shù)100到500，每次增加100，實驗的結(jié)果如圖2所示，網(wǎng)絡(luò)壽命隨著網(wǎng)絡(luò)的節(jié)點個數(shù)增加而增加。TS_DB算法的網(wǎng)絡(luò)壽命比相關(guān)算法的網(wǎng)絡(luò)壽命長，由于隨著傳感節(jié)點數(shù)的增多，網(wǎng)絡(luò)中節(jié)點間的空間冗余也增多，從而更多的冗余節(jié)點被用于延長傳感網(wǎng)絡(luò)的壽命。

圖2 網(wǎng)絡(luò)規(guī)模對網(wǎng)絡(luò)壽命的影響

實驗中設(shè)置節(jié)點死亡百分比從0到1.0，每次增加0.2。如圖3所示，隨著死亡節(jié)點百分比的增加，數(shù)據(jù)恢復(fù)百分比降低。TS_DB的算法優(yōu)于其他算法。本文提出的數(shù)據(jù)備份算法是基于貪心算法盡可能多地進(jìn)行數(shù)據(jù)備份，而且部分傳感數(shù)據(jù)也可以通過關(guān)聯(lián)矩陣進(jìn)行恢復(fù)。

圖3 死亡節(jié)點百分比對數(shù)據(jù)恢復(fù)百分比的影響

圖4 時間對平均每個節(jié)點能耗的影響

設(shè)置網(wǎng)絡(luò)中的時間從0到100，每次增加20。隨著時間的增長，三種算法的平均每個節(jié)點的能耗的變化如圖4所示。DISC和Centralized Algorithm兩種算法的能耗基本上保持相對平緩的趨勢，TS_DB算法由于挖掘出單個節(jié)點的時間相關(guān)性，減少數(shù)據(jù)的發(fā)送量，數(shù)據(jù)波動變化較大，但總體來說優(yōu)于其他兩種算法。

4 結(jié)論

數(shù)據(jù)備份能有效地解決傳感器節(jié)點失效造成數(shù)據(jù)丟失的問題。本文提出基于時空冗余數(shù)據(jù)清除的數(shù)據(jù)備份算法，挖掘出傳感節(jié)點在時間和空間緯度上的相關(guān)性，并消除冗余數(shù)據(jù)，最后利用貪心算法盡可能多地進(jìn)行備份。實驗結(jié)果表明，提出的TS_DB算法在網(wǎng)絡(luò)壽命、數(shù)據(jù)恢復(fù)率、平均每個節(jié)點能耗明顯優(yōu)于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

國家自然科學(xué)基金(61370210)；福建省教育廳A類科技項目(2013JA12027)；福州大學(xué)科技發(fā)展基金(2013-XQ-35)資助

TP393

A

10.19358/j.issn.1674-7720.2017.24.016

潘燕燕，陳冬隱，程紅舉.基于時空冗余數(shù)據(jù)清除的數(shù)據(jù)備份算法J.微型機(jī)與應(yīng)用，2017,36(24)：54-57，61.

2017-06-30)

潘燕燕(1991-)，女，碩士研究生，主要研究方向：無線傳感器網(wǎng)絡(luò)。

陳冬隱(1991-)，男，碩士研究生，主要研究方向：無線傳感器網(wǎng)絡(luò)。

程紅舉(1975-)，男，博士，教授，CCF高級會員，主要研究方向：計算機(jī)網(wǎng)絡(luò)、無線傳感器網(wǎng)絡(luò)。