Data preservation in intermittently connected sensor network with data priority

Abstract

In intermittently connected sensor networks, the data generated may have different importance and priority. Different types of data will help scientists analyze the physical environment differently. In a challenging environment, wherein sensor nodes are not always connected to the base station with a communication path, and not all data may be preserved in the network. Under such circumstances, due to the severe energy constraint in the sensor nodes and the storage limit, how to preserve data with the maximum priority is a new and challenging problem. In this thesis, we will study how to preserve data to produce the maximum total priority under the constraints of the limited energy level and storage capacity of each sensor node. We have designed an efficient optimal algorithm, and prove it is optimal. The core of the problem is Maximum weighted flow problems, which is in order to maximize the total weight of the flow network, taking into account the different flows having different weights. The maximum weighted flow is a generalization of the classical maximum flow problem, characterized in that each unit of flow has the same weight. To the best of our knowledge, our work first study and solve the maximum weighted flow problems. We also propose a more efficient heuristic algorithm. Through simulation, we show that it performs comparably to the optimal algorithm, and perform better than the classical maximum flow algorithm, which does not consider the data priority. Finally, we design a distributed data preservation algorithm based on the push-relabel algorithm and analyze its time and message complexity, experience has shown that it is superior to push-relabel distributed maximum flow algorithm according to total preserved priorities.