Topology design in time-evolving delay-tolerant networks with unreliable links

With possible participation of a large number of wireless devices in delay tolerant networks (DTNs), how to maintain efficient and dynamic topology becomes crucial. In this paper, we study the topology design problem in a predictable DTN where the time-evolving network topology is known a priori or can be predicted. We model such network as a weighted space-time graph with both spacial and temporal information. Links inside the space-time graph are unreliable due to either the dynamic nature of wireless communications or the rough prediction of underlying human/device mobility. The aim of our topology design problem is to build a sparse space-time structure such that (1) for any pair of devices, there is a space-time path connecting them with the reliability larger than a required threshold; (2) the total cost of the structure is minimized. We first show that this problem is NP-hard, and then propose several heuristics which can significantly reduce the total cost of the topology while maintain the “reliable” connectivity over time.