Maximum Lifetime Data Regeneration for Persistent Storage in Wireless Sensor Networks

Erasure codes have been employed to achieve persistent storage in distributed storage networks. Recent work has shown that, in addition to reduction in storage space requirements, the communication bandwidth in the data regeneration process can be further reduced by using Regenerating Codes. In this paper, we consider the issue of energy-efficient data regeneration in wireless sensor networks with the objective of minimizing energy expenditure and thereby maximizing network lifetime. We formally prove the NP-hardness of finding the optimal set of source nodes and corresponding routes for data regeneration in general networks, and devise an optimal polynomial algorithm, TROY, for acyclic networks; the cardinality of the set is predefined. Building upon TROY, we devise a heuristic algorithm for general networks and show, through extensive simulation studies, that this heuristic is near-optimal.