潘燕燕，陳冬隱，程紅舉

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

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

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

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

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

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

0 引言

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

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

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

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

表1 符號(hào)說(shuō)明

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

定義3差值序列：傳感節(jié)點(diǎn)si和sj在數(shù)據(jù)序列長(zhǎng)度為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來(lái)擬合兩節(jié)點(diǎn)si和sj間感知數(shù)據(jù)差值序列的均值。若擬合的誤差小于給定的誤差閾值，則判定兩節(jié)點(diǎn)是相關(guān)的，標(biāo)記關(guān)聯(lián)模式矩陣為C[i,j]=l。

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

2 算法

2.1 分簇

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

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

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

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

(3)重新計(jì)算每個(gè)聚類的均值。

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

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

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

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

(1)節(jié)點(diǎn)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)由差值序列計(jì)算節(jié)點(diǎn)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計(jì)算兩序列的擬合誤差Error：

(2)

(4)若擬合誤差Error小于給定的誤差閾值ε，則可判定兩節(jié)點(diǎn)的感知數(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é)點(diǎn)與簇頭節(jié)點(diǎn)的關(guān)聯(lián)模式都判定完。

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

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

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

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

xi(t)=β0t+β1

(3)

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

(4)

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

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

(4)若是δ≥ε，則不滿足該模型，需要傳送并備份該感知數(shù)據(jù)。若是連續(xù)m個(gè)感知數(shù)據(jù)都不滿足該模型，則用最小二乘法重新計(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ò)時(shí)空相關(guān)性的判定來(lái)確定簇頭節(jié)點(diǎn)需要備份的感知數(shù)據(jù)，本節(jié)利用貪心算法根據(jù)簇頭的剩余能量，進(jìn)行備份。

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

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

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

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

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

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

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

2.5 算法實(shí)現(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 實(shí)驗(yàn)

本文使用MATLAB作為仿真實(shí)驗(yàn)工具，在100 m×100 m的矩形區(qū)域內(nèi)隨機(jī)部署了|V|個(gè)完全相同的傳感節(jié)點(diǎn)每個(gè)節(jié)點(diǎn)，的初始能量為1 J，將網(wǎng)絡(luò)分為5個(gè)簇，其他的實(shí)驗(yàn)參數(shù)如表2所示。

表2 實(shí)驗(yàn)參數(shù)設(shè)置

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

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

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

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

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

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

圖4 時(shí)間對(duì)平均每個(gè)節(jié)點(diǎn)能耗的影響

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

4 結(jié)論

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

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

TP393

A

10.19358/j.issn.1674-7720.2017.24.016

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

2017-06-30)

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

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

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