Relay placement for latency minimization in delay tolerant networks

Delay tolerant networks (DTN) have shown its great successes in many mobile applications with intermittent connectivity. To increase contact opportunities that play an important role in routing performance and energy efficiency of DTN, the approaches of deploying static relay nodes, which are also referred to as throwboxes, has been widely adopted. In this paper, we study a relay deployment problem with the objective of minimizing communication latency among all nodes in DTN, which has been little studied so far. Upon the concept of latency graph that we propose to model the message delivery latency in DTN, the problem of relay placement for latency minimization (RPLM) is defined and proven NP-hard. To solve the RPLM problem, we propose a heuristic algorithm with low complexity, and conduct extensive simulations to show that it significantly outperforms other two existing schemes.