1536-1233 (c) 2013 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.
This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TMC.2014.2374168, IEEE Transactions on Mobile Computing 1
A Network Coding Based Energy Efficient
Data Backup in Survivability-Heterogeneous
Jie Tian, Tan Yan, and Guiling Wang
Department of Computer Science, New Jersey Institute of Technology
Email: fjt66, ty7, email@example.com
Abstract—Sensor nodes deployed outdoors are subject to environmental detriments and often need to cache data for an extended period of time. This paper introduces sensor nodes which are robust to environmental damages, and proposes to utilize Network Coding to back up data in the robust sensors for future data retrieval in an energy efficient way. Our goal is to help regular sensors select robust sensors to back up their data with low energy consumption, such that when needed, all the data can be retrieved by querying only a subset of robust sensors. We formally formulate this backup problem, theoretically prove its NP-Completeness, discover two novel theoretical guidelines for problem solving, and propose two algorithms accordingly to tackle this NP-C problem. The guidelines are based on random linear network coding and provide lower bounds of the number of robust sensors that each regular sensor should choose for data backup, such that the required fault tolerance is provided.
A centralized algorithm and a distributed algorithm are developed based on the guidelines such that regular sensors can back up their data efficiently. Both analysis and simulation show our algorithms are effective in achieving fault tolerance, low energy consumption and high retrieval efficiency.
Index Terms—Heterogeneous sensor networks, data backup, network coding
F 1 INTRODUCTION
Due to the small size and low cost of a sensor node, a wireless sensor network composed of a large number of such nodes can be deployed close to the phenomena or events of interest, monitoring them and generating data.
The generated precious data may not be able to be collected constantly and immediately considering many constraints in the physical world, especially in remote and hostile areas.
For example, in Great Duck Island, a sensor network has been monitoring the habitat of wild birds . The habitat data can only be collected from the sensors occasionally to minimize the interference on birds’ natural life. To let sensors increase the transmission power and remotely send data to human operator drains the battery power quickly or simply is infeasible if the distance between a data collector and the sensor network is too large. Therefore, a sensor network has to act as a distributed data storage before data collection. The duration that data have to be cached in a sensor network varies from minutes to months.
The environments in which a sensor network needs to cache data for an extended period of time before data collection are generally remote or less accessible. Especially in these environments, sensor nodes, which are tiny electronic devices, are subject to environmental damages, such as rain and fire. When a sensor node dies due to the physical damages, the data in the node are lost. Therefore, it is important to back up the data. To simply duplicate
This work is supported by the National Science Foundation grants NSF1128369. data in multiple tiny sensor nodes cannot provide enough fault tolerance because sensors are likely to fail at the same time when the harsh environmental attributes act on them.
For example, after a storm, most of these small electronic devices may fail simultaneously. Even though after they are dried in sunshine and are able to work again, it is not likely that the lost data can be recovered. To deal with the problem, we propose to incorporate sensor nodes which are robust to environmental damages. We assume they are water-proof, can tolerate high temperature and withstand other environmental attributes. Considering such robust sensor nodes are of higher cost, we propose to construct heterogeneous sensor networks with both regular and robust sensors. The focus of the paper is to design schemes for regular sensors to back up data in robust sensors.
Our objective is to design energy-efficient data-backup schemes for the proposed heterogeneous sensor networks to achieve high fault tolerance in harsh environment. Considering in harsh environment, all regular sensors may lose data after a storm and some robust sensors may fail due to energy depletion or other reasons, a desired scheme should be able to tolerate the failure of all regular sensors and a portion of the robust sensors. In another word, by accessing any b out of n robust sensors (b 6 n), all the data stored in the network can be recovered. Existing distributed data storage systems – cannot be directly applied to solve our problem either because they cannot achieve the desired fault tolerance or because their system requirement is too high. For example, cluster based storage systems ,  cannot tolerate the failure of all storage nodes in a clus1536-1233 (c) 2013 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.
This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TMC.2014.2374168, IEEE Transactions on Mobile Computing 2 ter. Some coding-based data storage systems ,  can tolerate that, but they are under the prerequisite that there are more storage nodes than the data nodes. This means we have to budget more robust sensors than regular sensors and the cost of a sensor network is greatly increased. Moreover, the energy consumption of communication for backup is not considered in many existing schemes. This paper aims to develop energy-efficient data backup schemes which can provide required level of fault tolerance.