Topology Control for Time-Evolving and Predictable Delay-Tolerant Networks

Previous DTN research mainly focuses on routing and information propagation. However, with large number of wireless devices' participation, how to maintain efficient and dynamic topology of the DTN becomes crucial. In this paper, we study the topology control (TC) problem in a predictable DTN where the time-evolving network topology is known a priori or can be predicted. We first model such time-evolving network as a directed space-time graph which includes both spacial and temporal information. The aim of TC is to build a sparse structure from the original space-time graph such that (1) the network is still connected over time and supports DTN routing between any two nodes; (2) the total cost of the structure is minimized. We prove that this problem is NP-hard, and then propose two greedy-based methods which can significant reduce the total cost of topology while maintain the connectivity over time. We also introduce another version of the TC problem by requiring that the least cost path for any two nodes in this constructed structure is still cost-efficient compared with the one in the original graph. Two greedy-based methods are provided for such problem. Simulations have been conducted on both random DTN networks and real-world DTN tracing data. Results demonstrate the efficiency of the proposed methods.