Data Preservation in Intermittently Connected Sensor Networks With Data Priority

摘要

Data generated in sensor networks may have different importance and priority. Different types of data contribute differently for scientists to analyze the physical environment. In a challenging environment, wherein sensor nodes do not always have connected paths to the base station, and not all the data can be preserved inside the network due to severe energy constraints and storage constraints at sensor nodes, how to preserve data with maximum priority is a new and challenging problem. In this paper, we study how to preserve data that yield maximum total priorities, under the constraints that each sensor node has limited energy level and storage capacity. We design an efficient optimal algorithm and prove its optimality. The core of the problem is a maximum weighted flow problem, which is to maximize the total weight of flow in the network considering different flows have different weights. Maximum weighted flow is a generalization of the classic maximum flow problem, wherein each unit of flow has the same weight. To the best of our knowledge, our work is the first to study and solve the maximum weighted flow problem. We propose a more time efficient heuristic algorithm. Via simulation, we show that it performs comparably to the optimal algorithm and performs better than the classic maximum flow algorithm, which does not consider data priority. Finally we design a distributed data preservation algorithm based on push-relabel algorithm, analyze its time and message complexities, and empirically show that it outperforms the push-relabel distributed maximum flow algorithm in terms of the total preserved priorities.