Maximizing data preservation in intermittently connected sensor networks

摘要

In intermittently connected sensor networks, wherein sensor nodes do not always have connected paths to the base station, preserving generated data inside the network is a new and challenging problem. We propose to preserve the data items by distributing them from storage-depleted data generating nodes to sensor nodes with available storage space and high battery energy, under the constraints that each node has limited storage capacity and battery power. The goal is to maximize the minimum remaining energy among the nodes storing the data items, in order to preserve them for maximum amount of time until next uploading opportunity arises. We first give feasibility condition of this problem by proposing and applying a Modified Edmonds-Karp Algorithm (MEA) on an appropriately transformed flow network. We then show that when feasible solutions exist, finding the optimal solution is NP-hard. We develop a sufficient condition to solve the problem optimally. We then design a centralized greedy heuristic with less time complexity than that of the optimal, which also works when feasibility can not be satisfied and network partitions arise. Via extensive simulations, we show that the heuristic performs comparably to optimal.