Abstract—In traditional Delay Tolerant Networks (DTNs), unpredictable mobility pattern, network partitioning and the lack of continuous end-to-end path make it challenging to design network protocols. However, the applicable range of DTNs has been extended to some new types of networks such as Mobile Social Network (MSN), vehicular ad-hoc network (VANET), etc. Based on these DTN traces, we first reveal two major characteristics namely periodicity and path redundancy by quantitative analysis, which substantially provides the feasibility and operability of topology control. In this paper, we study the topology control problem in DTN by modeling such time-evolving network as a space-time graph and connecting it with the classical set cover problem. The aim of topology control is to build a sparse subgraph from the original space-time graph such that 1) any two nodes are connected; 2) the cost of subgraph is minimized. Furthermore, we propose a topology control algorithm that can significantly reduce the total cost of network while guarantee the connectivity. We conduct our experiments on both random DTN networks and realistic DTN traces. Evaluation results demonstrate the efficiency of the proposed algorithm.

Index Terms—Topology control, delay tolerant networks, set cover

Cite: Xuyan Bao, Xiaojin Zhou, Xiaojuan Wang, Yong Zhang, Mei Song, “Topology Control based on Set Cover for  Delay-Tolerant Networks," Journal of Communications, vol. 11, no. 3, pp. 272-281, 2016. Doi: 10.12720/jcm.11.3.272-281