Topology control for predictable delay-tolerant networks based on probability

In wireless networks, topology control can improve energy effectiveness and increase the communication capacity. In predictable delay tolerant networks (PDTNs), intermittent connectivity, network partitioning, and long delays make most of the researchers focus on routing protocol, and the research on topology control is in the very early stage. Most existing topology control approaches for PDTN assume the underlying connections are deterministic, which excludes a large amount of probabilistic connections existing in the challenged environments. In this paper, probabilistic connections are taking into consideration. The predictable delay tolerant networks are modeled as a three dimensional space–time weighted directed graph which includes spatial, temporal and connection probability information. The topology control problem is formulated as finding a sub graph to balance the energy cost and data transferring reliability. This problem is proved to be NP-complete, and two heuristic algorithms are proposed to solve the problem. The first one is to find a sub graph that assures the maximum connection probability between each pair of nodes. The other one is to find the sub graph in which the connection probabilities between each pair of nodes satisfy the given threshold with the minimum energy cost. Extensive simulation experiments demonstrate that the proposed topology control algorithms can achieve our goal.