一种改进的WSN数据在线恢复方案

祝 青



一种改进的WSN数据在线恢复方案

祝 青

(湖南城市学院信息科学与工程学院，湖南 益阳 413000)

传感器节点容易发生软件或机械故障，从而导致节点数据部分或全部丢失。为保证无线传感器网络数据收集的可靠性，提出一种改进的数据在线恢复方案。采用分布式存储机制对节点数据进行冗余处理，依据节点发出的恢复请求，给出改进的多项式时间数据恢复算法，支持请求接纳控制，并对数据恢复文件块大小进行限制，可在非循环网络上取得恒定的近似率边界。理论分析与仿真实验结果表明，该方案可准确恢复网络数据，对各数据恢复请求均可实现数据恢复成本最小化。

传感器节点；节点故障；数据恢复；分布式存储；近似率；成本

1 概述

无线传感器网络(Wireless Sensor Network, WSN)节点的可靠性给网络数据存储带来了巨大挑战，使用的大量节点很有可能发生软件或机械故障，这些故障可能造成数据部分或全部丢失。为保证数据安全性，每个节点可以在其他节点上保存数据，虽然存在数据冗余度，但可以使用复制或纠删码来克服冗余问题[1]。通过与一定数量的节点通信，sink可以重建任意节点的数据。

考虑对部分数据进行分布式存储的一组节点，该组节点中任意一个节点发生故障，都会降低数据的冗余度。然而，如果向网络中加入新的节点，则从一定数量的活跃节点下载部分数据，便可以恢复数据的冗余度。这一恢复过程称为再生。当然，如果故障没有导致数据丢失，则不需要数据重建[2]。恢复能力是指在任意给定时间，网络恢复请求总体数量。恢复能力的主要限制因素是节点能量储备：需要处理的恢复请求越多，参与处理该请求的节点就需要消耗更多的能量。最后，可能导致没有足够数量的节点具有足够多的能量来接受更多的请求。对某恢复请求，如网络部分节点处理该请求消耗的能量超出阈值，则实现恢复能力最大化的算法拒绝这样的请求。将离线oracle算法[3-4]能够实现的最大恢复能力与在线算法恢复能力之比定义为竞争比。

本文将数据重建和再生统称为数据恢复，并提出一种可以实现数据恢复能力最大化的在线算法。

2 简单网络示例

图1 简单网络示例

3 相关工作

无线传感器网络中的数据恢复问题是目前研究的热点问题，它对于保证数据收集的可靠性具有重要影响。相继有众多研究者提出一系列用于数据恢复的方法，如文献[5]为提高无线传感器网络数据压缩感知中恢复算法的实时性，提出一种基于二次规划的无线传感器网络数据恢复算法。该算法将压缩感知重构中的欠定线性方程组求解转化为有界约束二次规划问题，在此基础上结合阿米霍步长准则对二次规划进行求解，从而对网络数据进行恢复。理论分析和仿真结果表明，所提算法可准确恢复网络数据，并且相比传统压缩感知恢复算法，可明显降低数据恢复的计算复杂度，有效提高网络数据恢复算法的实时性；文献[6]为减小无线传感器网络数据传输过程中相关性发生变化对压缩感知重构精度的影响，提出一种相关性自适应的网络数据重构方法。该方法首先通过迭代对待重构数据的相关性进行估计，进而采用支集元素的两步相关检验方法对网络数据稀疏系数向量中非零元素进行重构，最终得到更为精确的重构数据。仿真结果表明，该算法能有效抑制实际传输过程中各种干扰对网络数据重构的影响，提高网络数据相关性变化情况下的重构准确度。

另外，文献[7]针对传统压缩采样匹配追踪(CoSaMP)算法中测量次数多、数据恢复精度低等问题，利用信号的小波系数所形成的连通树的结构特性，提出了基于小波树模型的压缩采样匹配追踪算法。将该算法应用到无线传感器网络监测信号的数据恢复实验中，结果表明该算法在一定范围内对无线传感器网络中的温度信号具有更好的重构性能；文献[8]提出了一种可以实现网络寿命最大化的多项式时间算法TROY。TROY在数据恢复时选择最优节点集合及对应的路由，实现非循环网络寿命的最大化。相反，本文以在线方式考虑满足一个序列的数据恢复请求，且目标函数有所不同。文献[9]通过对存储文件块采取分布式处理，提出一种数据持久算法，假设故障具有关联性，当发生故障时，可以从现有节点中恢复数据。但是，本文考虑的是节点故障发生后的数据恢复。此外，没有对节点故障和数据恢复请求做出任何统计假设。文献[10]提出了CMAX算法来实现网络数据的精确恢复。然而他们的数据针对的是随机数据流。因此，他们的算法无法直接拓展至传感器网络中的数据恢复问题。本文在已有工作的基础上，提出了一种改进的数据在线恢复方案，并通过仿真实验验证了本文方案的有效性。

4 系统模型

4.1 冗余机制

在本文的研究中，主要考虑采用如下的3种冗余机制来存储网络上的任何数据：

(1)复制机制

(2)MDS码[11]

(3)RC码[12]

4.2 网络模型

本文使用的标记法相关符号含义如表1所示。

表1 相关符号含义

5 在线数据恢复

RECO算法：

要求：满足式(12)

4： end if

5: end for

8: else

10: end if

11: end while

6 一种低计算复杂度的数据在线恢复算法

图2 非循环网络

DOR算法

要求：式(12)满足

3：end for

6： repeat

12： end if

13: end for

7 实验评估

本节采用Matlab2012对文中提出的数据恢复算法进行实验评估。对于节点和路由选择，使用本文提出的数据恢复算法DOR。用随机生成的50个25节点拓扑结构进行仿真。MDS和RC码使用(25, 6)码设计。网络请求统一随机发出。如果有节点发出请求但被拒绝，则该节点进入睡眠状态。

图3讨论对每条曲线及曲线上的每个点，非循环网络的构建采取宽度优先搜索策略，BFS的根随机选择。

图3 使用DOR进行服务器/路由选择时的累积分布情况

图4 DOR基于不同树构建策略时的恢复能力

8 结束语

本文针对节点故障序列未知的功率受限分布式存储系统提出一种数据恢复技术。此外，分别针对随机网络和无循环网络，提出2种可按一定比率稳定近似最优离线算法的多项式时间算法。下一步研究的重点是提出针对故障节点，尤其是永久故障节点的最优数据布局算法。

[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] 吴桂峰, 王 轩. 基于二次规划的无线传感器网络数据恢复算法[J]. 计算机应用, 2013, 33(4): 935-938.

[6] 周 剑, 张明新. 无线传感器网络数据的相关性自适应压缩感知[J]. 计算机应用, 2013, 33(2): 374-377.

[7] 苏维均, 王红红, 于重重. 基于小波树模型的CoSaMP压缩感知算法[J]. 计算机应用研究, 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－)，女，副教授、硕士，主研方向：信息检索，无线传感器网络。

2013-09-22

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