In Partial Fulfillment of the Requirements for the Degree of
Doctor of Philosophy
Will defend his dissertation
Prior to uploading sensed data to a sink, nodes in a wireless sensor network can store any one locally sensed data using robust distributed storage solutions. A variety of replication and erasure coding methods exist to store data in such systems so that when a subset of nodes in the system fails, the original data can still be reconstructed from live nodes. Our work concerns data recovery with minimal energy costs as nodes fail in an unknown sequence. In particular, we propose algorithms to maximize the network recovery capacity--the total number of successful data recoveries until an insufficient number of nodes exist to reconstruct the original data. We propose an online polynomial-time algorithm, RECO that is within a constant approximation ratio of the optimal oracle algorithm having complete knowledge of failures patterns. Then we propose a more computation-efficient polynomial-time algorithm, THAM, that with a constant approximation ratio in acyclic networks. Our simulation results show that THAM performs well even in general networks.