Optimization Problems in Throwbox-Assisted Delay Tolerant Networks: Which Throwboxes to Activate? How Many Active Ones I Need?

One of the solutions to improve mobile Delay Tolerant Network (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: throwbox selection, to answer the questions such as how many active throwboxes do I need? and which throwboxes should be activated? We formally define two throwbox optimization problems: min-throwbox problem and k-throwbox problem for time-evolving DTNs modeled by weighted space-time graphs. We show that min-throwbox problem is NP-hard and propose a set of greedy algorithms which can efficiently provide quality solutions for both challenging problems.