A Network Coding Based Energy Efficient Data Backup in Survivability-Heterogeneous Sensor Networks

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.