K-throwbox placement problem in throwbox-assisted delay tolerant networks

Recent advances in Delay Tolerant Networks (DTNs) have overcome limitations in connectivity by relying on intermittent contacts between mobile nodes to deliver packets. However, lack of rich contact opportunities still causes poor delivery ratio and long delay of DTN routing. One of the solutions to improve mobile DTN performance is to place additional stationary nodes, called throwboxes, to create a greater number of contact opportunities. In this paper, we study a key optimization problem in a time-evolving throwbox-assisted DTN: k-throwbox placement problem, to answer 'where should I put my k throwboxes to optimize the performance?'. We model a time-evolving DTN as a weighted space-time graph which includes both spacial and temporal information. We prove that k-throwbox placement problem is NP-hard and propose a set of greedy algorithms which can efficiently provide quality solutions. One of the proposed algorithms can guarantee an (1 - 1/e) approximation for the k-throwbox placement problem. Simulation results based on random time-evolving DTNs and real life DTN traces demonstrate the efficiency of the proposed methods.