Each node in a wireless sensor network has some data storage capability that preserves gathered data until that data is either requested by a data collector, or utilized by the network itself. Local storage, where every node stores its own data locally, is disadvantageous because a software or mechanical failure may cause permanent data loss of some or all of the data. Robust distributed networked storage, where each node stores its data amongst other nodes in a redundant manner, offers higher levels of data persistence than local storage. Using a distributed storage scheme, a data collector can reconstruct any node's data by downloading a portion of data from a previously defined threshold number of nodes. Consider a set of nodes storing some data distributively. The failure of any node in that set, reduces the data's level of redundancy. However, if a newcomer joins the network, it can be used to restore the data's level of redundancy, by downloading some data from a threshold number of live nodes. This recovery process is termed regeneration. In the case of a software failure, the node that failed may be reassigned to be the newcomer, if it is able to return to its previous working state. In this paper, we generalize the terms reconstruction and regeneration to the term recovery. We propose a framework that serves as a measure of performance for algorithms targeting data persistence. We then propose one such algorithm and show that it achieves a constant approximation ratio of the optimal, with respect to the framework. Finally, we conclude with simulations analyzing the proposed data recovery framework.

We propose a decentralized progressive data retrieval (PDR) mechanism for data reconstruction in a network of Byzantine and crash-stop nodes. The scheme progressively retrieves stored data, such that it achieves the minimum communication cost possible. In particular, PDR gracefully adapts the cost of successful data retrieval to the number of Byzantine and crash-stop storage nodes. At the core of PDR is an incremental Reed-Solomon decoding (IRD) procedure that is highly computation efficient for data reconstruction. IRD's computation efficiency arises from its ability to utilize intermediate computation results. In addition, we provide an in-depth analysis of PDR and compare it to decentralized erasure coding and decentralized fountain coding algorithms for distributed storage systems. Moreover, our implementation results show that PDR has up to 35 times lower computation time over the state-of-the-art error-erasure decoding scheme for distributed storage systems. In our analysis, we also show that the code structure of PDR and the number of available storage nodes are independent of each other, and they can be used to control both the data dissemination and retrieval complexity.

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 pre- defined. Building upon TROY, we devise a heuristic algorithm for general networks and show, through extensive simulation studies, that this heuristic is near-optimal.

We propose a storage-optimal and computation efficient primitive to spread information from a single data source to a set of storage nodes, to allow recovery from both crash-stop and Byzantine failures. A progressive data retrieval scheme is employed, which retrieves minimal amount of data from live storage nodes. The scheme adapts the cost of successful data retrieval to the degree of errors in the system. Implementation and evaluation studies demonstrate comparable performance to that of a genie-aid decoding process.

In this paper, BFLY-a practical localized network coding protocol for wireless mesh networks-is proposed. To supplement forwarding packets in classical networks, intermediate wireless nodes code packets from different sources, so that each transmission's information content is increased. Prior work allowed intermediate nodes to code (i.e, XOR) packets such that the recipient of the coded message must decode the message before forwarding. BFLY, however, allows intermediate recipients to, in addition to XOR-ing, forward coded packets; and thus further exploits network coding opportunities in multihop wireless networks. BFLY utilizes knowledge of local topologies and source route information in packet headers. We have developed network coding modules in ns-2 that facilitate simulations with large networks. Simulation studies show that BFLY can increase overall network throughput by a factor of 1.2 - 2 and reduce end-to-end latency.