Data Collection Oriented Topology Control for Predictable Delay-Tolerant Networks

In predictable delay tolerant networks (PDTNs), the topology is known a priori or can be predicted over time. This kind of networks is often utilized to collect data, in which many to one communication pattern are adopted. Therefore, maintaining efficient tree-based topology will be very helpful to reduce resource consumption by select certain transmitting opportunities to delivery data instead of greedily using all the transmitting opportunities like many DTN routing approaches do. In this paper, we first model such PDTNs as space-time directed graph which includes spatial, temporal and energy cost information. The topology control problem is then formalized as constructing a data collecting tree (DCT) from the established space-time directed graph such that the total energy cost of the DCT is minimized and the demand on time delay is satisfied. We prove that this problem is NP-complete, and two heuristic algorithms are proposed to solve this problem. Extensive simulation experiments demonstrate the efficiency of the proposed topology control methods.