祝 青

?

一種改進(jìn)的WSN數(shù)據(jù)在線恢復(fù)方案

祝 青

(湖南城市學(xué)院信息科學(xué)與工程學(xué)院，湖南 益陽 413000)

傳感器節(jié)點(diǎn)容易發(fā)生軟件或機(jī)械故障，從而導(dǎo)致節(jié)點(diǎn)數(shù)據(jù)部分或全部丟失。為保證無線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集的可靠性，提出一種改進(jìn)的數(shù)據(jù)在線恢復(fù)方案。采用分布式存儲(chǔ)機(jī)制對(duì)節(jié)點(diǎn)數(shù)據(jù)進(jìn)行冗余處理，依據(jù)節(jié)點(diǎn)發(fā)出的恢復(fù)請(qǐng)求，給出改進(jìn)的多項(xiàng)式時(shí)間數(shù)據(jù)恢復(fù)算法，支持請(qǐng)求接納控制，并對(duì)數(shù)據(jù)恢復(fù)文件塊大小進(jìn)行限制，可在非循環(huán)網(wǎng)絡(luò)上取得恒定的近似率邊界。理論分析與仿真實(shí)驗(yàn)結(jié)果表明，該方案可準(zhǔn)確恢復(fù)網(wǎng)絡(luò)數(shù)據(jù)，對(duì)各數(shù)據(jù)恢復(fù)請(qǐng)求均可實(shí)現(xiàn)數(shù)據(jù)恢復(fù)成本最小化。

傳感器節(jié)點(diǎn)；節(jié)點(diǎn)故障；數(shù)據(jù)恢復(fù)；分布式存儲(chǔ)；近似率；成本

1 概述

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network, WSN)節(jié)點(diǎn)的可靠性給網(wǎng)絡(luò)數(shù)據(jù)存儲(chǔ)帶來了巨大挑戰(zhàn)，使用的大量節(jié)點(diǎn)很有可能發(fā)生軟件或機(jī)械故障，這些故障可能造成數(shù)據(jù)部分或全部丟失。為保證數(shù)據(jù)安全性，每個(gè)節(jié)點(diǎn)可以在其他節(jié)點(diǎn)上保存數(shù)據(jù)，雖然存在數(shù)據(jù)冗余度，但可以使用復(fù)制或糾刪碼來克服冗余問題[1]。通過與一定數(shù)量的節(jié)點(diǎn)通信，sink可以重建任意節(jié)點(diǎn)的數(shù)據(jù)。

考慮對(duì)部分?jǐn)?shù)據(jù)進(jìn)行分布式存儲(chǔ)的一組節(jié)點(diǎn)，該組節(jié)點(diǎn)中任意一個(gè)節(jié)點(diǎn)發(fā)生故障，都會(huì)降低數(shù)據(jù)的冗余度。然而，如果向網(wǎng)絡(luò)中加入新的節(jié)點(diǎn)，則從一定數(shù)量的活躍節(jié)點(diǎn)下載部分?jǐn)?shù)據(jù)，便可以恢復(fù)數(shù)據(jù)的冗余度。這一恢復(fù)過程稱為再生。當(dāng)然，如果故障沒有導(dǎo)致數(shù)據(jù)丟失，則不需要數(shù)據(jù)重建[2]?；謴?fù)能力是指在任意給定時(shí)間，網(wǎng)絡(luò)恢復(fù)請(qǐng)求總體數(shù)量?；謴?fù)能力的主要限制因素是節(jié)點(diǎn)能量儲(chǔ)備：需要處理的恢復(fù)請(qǐng)求越多，參與處理該請(qǐng)求的節(jié)點(diǎn)就需要消耗更多的能量。最后，可能導(dǎo)致沒有足夠數(shù)量的節(jié)點(diǎn)具有足夠多的能量來接受更多的請(qǐng)求。對(duì)某恢復(fù)請(qǐng)求，如網(wǎng)絡(luò)部分節(jié)點(diǎn)處理該請(qǐng)求消耗的能量超出閾值，則實(shí)現(xiàn)恢復(fù)能力最大化的算法拒絕這樣的請(qǐng)求。將離線oracle算法[3-4]能夠?qū)崿F(xiàn)的最大恢復(fù)能力與在線算法恢復(fù)能力之比定義為競爭比。

本文將數(shù)據(jù)重建和再生統(tǒng)稱為數(shù)據(jù)恢復(fù)，并提出一種可以實(shí)現(xiàn)數(shù)據(jù)恢復(fù)能力最大化的在線算法。

2 簡單網(wǎng)絡(luò)示例

圖1 簡單網(wǎng)絡(luò)示例

3 相關(guān)工作

無線傳感器網(wǎng)絡(luò)中的數(shù)據(jù)恢復(fù)問題是目前研究的熱點(diǎn)問題，它對(duì)于保證數(shù)據(jù)收集的可靠性具有重要影響。相繼有眾多研究者提出一系列用于數(shù)據(jù)恢復(fù)的方法，如文獻(xiàn)[5]為提高無線傳感器網(wǎng)絡(luò)數(shù)據(jù)壓縮感知中恢復(fù)算法的實(shí)時(shí)性，提出一種基于二次規(guī)劃的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)恢復(fù)算法。該算法將壓縮感知重構(gòu)中的欠定線性方程組求解轉(zhuǎn)化為有界約束二次規(guī)劃問題，在此基礎(chǔ)上結(jié)合阿米霍步長準(zhǔn)則對(duì)二次規(guī)劃進(jìn)行求解，從而對(duì)網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行恢復(fù)。理論分析和仿真結(jié)果表明，所提算法可準(zhǔn)確恢復(fù)網(wǎng)絡(luò)數(shù)據(jù)，并且相比傳統(tǒng)壓縮感知恢復(fù)算法，可明顯降低數(shù)據(jù)恢復(fù)的計(jì)算復(fù)雜度，有效提高網(wǎng)絡(luò)數(shù)據(jù)恢復(fù)算法的實(shí)時(shí)性；文獻(xiàn)[6]為減小無線傳感器網(wǎng)絡(luò)數(shù)據(jù)傳輸過程中相關(guān)性發(fā)生變化對(duì)壓縮感知重構(gòu)精度的影響，提出一種相關(guān)性自適應(yīng)的網(wǎng)絡(luò)數(shù)據(jù)重構(gòu)方法。該方法首先通過迭代對(duì)待重構(gòu)數(shù)據(jù)的相關(guān)性進(jìn)行估計(jì)，進(jìn)而采用支集元素的兩步相關(guān)檢驗(yàn)方法對(duì)網(wǎng)絡(luò)數(shù)據(jù)稀疏系數(shù)向量中非零元素進(jìn)行重構(gòu)，最終得到更為精確的重構(gòu)數(shù)據(jù)。仿真結(jié)果表明，該算法能有效抑制實(shí)際傳輸過程中各種干擾對(duì)網(wǎng)絡(luò)數(shù)據(jù)重構(gòu)的影響，提高網(wǎng)絡(luò)數(shù)據(jù)相關(guān)性變化情況下的重構(gòu)準(zhǔn)確度。

另外，文獻(xiàn)[7]針對(duì)傳統(tǒng)壓縮采樣匹配追蹤(CoSaMP)算法中測量次數(shù)多、數(shù)據(jù)恢復(fù)精度低等問題，利用信號(hào)的小波系數(shù)所形成的連通樹的結(jié)構(gòu)特性，提出了基于小波樹模型的壓縮采樣匹配追蹤算法。將該算法應(yīng)用到無線傳感器網(wǎng)絡(luò)監(jiān)測信號(hào)的數(shù)據(jù)恢復(fù)實(shí)驗(yàn)中，結(jié)果表明該算法在一定范圍內(nèi)對(duì)無線傳感器網(wǎng)絡(luò)中的溫度信號(hào)具有更好的重構(gòu)性能；文獻(xiàn)[8]提出了一種可以實(shí)現(xiàn)網(wǎng)絡(luò)壽命最大化的多項(xiàng)式時(shí)間算法TROY。TROY在數(shù)據(jù)恢復(fù)時(shí)選擇最優(yōu)節(jié)點(diǎn)集合及對(duì)應(yīng)的路由，實(shí)現(xiàn)非循環(huán)網(wǎng)絡(luò)壽命的最大化。相反，本文以在線方式考慮滿足一個(gè)序列的數(shù)據(jù)恢復(fù)請(qǐng)求，且目標(biāo)函數(shù)有所不同。文獻(xiàn)[9]通過對(duì)存儲(chǔ)文件塊采取分布式處理，提出一種數(shù)據(jù)持久算法，假設(shè)故障具有關(guān)聯(lián)性，當(dāng)發(fā)生故障時(shí)，可以從現(xiàn)有節(jié)點(diǎn)中恢復(fù)數(shù)據(jù)。但是，本文考慮的是節(jié)點(diǎn)故障發(fā)生后的數(shù)據(jù)恢復(fù)。此外，沒有對(duì)節(jié)點(diǎn)故障和數(shù)據(jù)恢復(fù)請(qǐng)求做出任何統(tǒng)計(jì)假設(shè)。文獻(xiàn)[10]提出了CMAX算法來實(shí)現(xiàn)網(wǎng)絡(luò)數(shù)據(jù)的精確恢復(fù)。然而他們的數(shù)據(jù)針對(duì)的是隨機(jī)數(shù)據(jù)流。因此，他們的算法無法直接拓展至傳感器網(wǎng)絡(luò)中的數(shù)據(jù)恢復(fù)問題。本文在已有工作的基礎(chǔ)上，提出了一種改進(jìn)的數(shù)據(jù)在線恢復(fù)方案，并通過仿真實(shí)驗(yàn)驗(yàn)證了本文方案的有效性。

4 系統(tǒng)模型

4.1 冗余機(jī)制

在本文的研究中，主要考慮采用如下的3種冗余機(jī)制來存儲(chǔ)網(wǎng)絡(luò)上的任何數(shù)據(jù)：

(1)復(fù)制機(jī)制

(2)MDS碼[11]

(3)RC碼[12]

4.2 網(wǎng)絡(luò)模型

本文使用的標(biāo)記法相關(guān)符號(hào)含義如表1所示。

表1 相關(guān)符號(hào)含義

5 在線數(shù)據(jù)恢復(fù)

RECO算法：

要求：滿足式(12)

4： end if

5: end for

8: else

10: end if

11: end while

6 一種低計(jì)算復(fù)雜度的數(shù)據(jù)在線恢復(fù)算法

圖2 非循環(huán)網(wǎng)絡(luò)

DOR算法

要求：式(12)滿足

3：end for

6： repeat

12： end if

13: end for

7 實(shí)驗(yàn)評(píng)估

本節(jié)采用Matlab2012對(duì)文中提出的數(shù)據(jù)恢復(fù)算法進(jìn)行實(shí)驗(yàn)評(píng)估。對(duì)于節(jié)點(diǎn)和路由選擇，使用本文提出的數(shù)據(jù)恢復(fù)算法DOR。用隨機(jī)生成的50個(gè)25節(jié)點(diǎn)拓?fù)浣Y(jié)構(gòu)進(jìn)行仿真。MDS和RC碼使用(25, 6)碼設(shè)計(jì)。網(wǎng)絡(luò)請(qǐng)求統(tǒng)一隨機(jī)發(fā)出。如果有節(jié)點(diǎn)發(fā)出請(qǐng)求但被拒絕，則該節(jié)點(diǎn)進(jìn)入睡眠狀態(tài)。

圖3討論對(duì)每條曲線及曲線上的每個(gè)點(diǎn)，非循環(huán)網(wǎng)絡(luò)的構(gòu)建采取寬度優(yōu)先搜索策略，BFS的根隨機(jī)選擇。

圖3 使用DOR進(jìn)行服務(wù)器/路由選擇時(shí)的累積分布情況

圖4 DOR基于不同樹構(gòu)建策略時(shí)的恢復(fù)能力

8 結(jié)束語

本文針對(duì)節(jié)點(diǎn)故障序列未知的功率受限分布式存儲(chǔ)系統(tǒng)提出一種數(shù)據(jù)恢復(fù)技術(shù)。此外，分別針對(duì)隨機(jī)網(wǎng)絡(luò)和無循環(huán)網(wǎng)絡(luò)，提出2種可按一定比率穩(wěn)定近似最優(yōu)離線算法的多項(xiàng)式時(shí)間算法。下一步研究的重點(diǎn)是提出針對(duì)故障節(jié)點(diǎn)，尤其是永久故障節(jié)點(diǎn)的最優(yōu)數(shù)據(jù)布局算法。

[1] Han Yunghsiang, Omiwade O, Zheng Rong. Progressive Data Retrieval for Distributed Networked Storage[J]. IEEE Transactions on Parallel and Distributed Systems, 2012, 23(12): 2303-2314.

[2] Beutel J, Gruber S, Hasler A, et al. PermaDAQ: A Acientific Instrument for Precision Sensing and Data Recovery in Environmental Extremes[C]//Proc. of 2009 International Conference on Information Processing in Sensor Networks. [S. 1.]: IEEE Computer Society, 2009: 265-276.

[3] Huang D, Qin Z, Doblar D G, et al. Analog Baud Rate Clock and Data Recovery: U.S. Patent 8,243,866[P]. 2012-08-14.

[4] Candes E J, Plan Y. Tight Oracle Inequalities for Low-rank Matrix Recovery from a Minimal Number of Noisy Random Measurements[J]. IEEE Transactions on Information Theory, 2011, 57(4): 2342-2359.

[5] 吳桂峰, 王 軒. 基于二次規(guī)劃的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)恢復(fù)算法[J]. 計(jì)算機(jī)應(yīng)用, 2013, 33(4): 935-938.

[6] 周 劍, 張明新. 無線傳感器網(wǎng)絡(luò)數(shù)據(jù)的相關(guān)性自適應(yīng)壓縮感知[J]. 計(jì)算機(jī)應(yīng)用, 2013, 33(2): 374-377.

[7] 蘇維均, 王紅紅, 于重重. 基于小波樹模型的CoSaMP壓縮感知算法[J]. 計(jì)算機(jī)應(yīng)用研究, 2012, 29(12): 4530-4533.

[8] Omiwade S, Zheng R. Maximum Lifetime Data Regeneration for Persistent Storage in Wireless Sensor Networks[C]//Proc. of GLOBECOM’11. [S. 1.]: IEEE Press, 2011: 1-6.

[9] Greenan N B K M, Wacha R, Long E L M D D E. Energy- Reliability Tradeoffs in Sensor Network Storage[C]//Proc. of the 5th ACM Workshop on Embedded Networked Sensors. [S. 1.]: ACM Press, 2008: 111-123.

[10] Kar K, Kodialam M, Lakshman T V, et al. Routing for Network Capacity Maximization in Energy-constrained Ad-hoc Net- works[C]//Proc. of INFOCOM’03. [S. 1.]: IEEE Press, 2003: 673-681.

[11] La G G G. New Quantum MDS Codes[J]. IEEE Transactions on Information Theory, 2011, 57(8): 5551-5554

[12] Yazdani M R, Banihashemi A H. On Construction of Rate-compatible Low-density Parity-check Codes[J]. IEEE Communications Letters, 2004, 8(3): 159-161.

編輯 索書志

An Improved Wireless Sensor Network Data Online Recovery Scheme

ZHU Qing

(School of Information Science and Engineering, Hunan City University, Yiyang 413000, China)

Since the sensor nodes prone to the software or mechanical failure, this may cause the permanent data loss of some or all of the data. In order to ensure the reliability of data collection in Wireless Sensor Network(WSN), this paper proposes an improved data online recovery scheme. The data of nodes are redundant processed by using the distributed storage mechanism, and based on the recovery request sent by the sensors, a constant approximation competitive ratio polynomial time data recovery algorithm is proposed, which can have the low complexity competitive ratio when admission control is allowed, and the size of recovery pieces is constrained, and achieves the constant approximation ratio bound in acyclic networks. Analysis and simulation experimental results show that the proposed algorithm can recover network data exactly and attain minimum recovery cost for any recovery request.

sensor node; node failure; data recovery; distributed storage; approximation ratio; cost

1000-3428(2014)03-0006-06

A

TP393

10.3969/j.issn.1000-3428.2014.03.002

祝青(1974－)，女，副教授、碩士，主研方向：信息檢索，無線傳感器網(wǎng)絡(luò)。

2013-09-22

2013-10-23 E-mail：2889683220@qq.com