Whether it be for environmental sensing or Internet of Things (IoT) applications, sensor networks are of growing use thanks to their large-scale sensing and distributed data storage abilities. However, when used in hazardous conditions and thus undergoing technical failures, data within sensor networks may never be retrieved due to critical node failures. For this purpose, data redundancy can be introduced to relieve this data loss but comes at a cost of increased data transmission and storage, hence reducing the network’s lifetime through increased power consumption. Here, a novel distributed storage strategy based on graph topology estimations is proposed to optimise the use of redundancy in fallible sensor networks. The storage strategy is found to outperform other strategies in providing the highest robustness whilst ensuring considerable lifetime, in the form of limited data transmission and storage use.