On Placement of Passive Stationary Relay Points in Delay Tolerant Networking

Recently, there has been focus on augmenting Delay/Disruption Tolerant Networks (DTNs) with easily deployable stationary relay nodes making an unconnected infrastructure to facilitate the data delivery by increasing forwarding opportunities. Relay nodes are capable of downloading, storing, and forwarding the data messages from/to the mobile nodes. Placing the relay nodes is an important issue in DTNs as the performance of the network is dependent to their positions. Relay placement is an NP-hard problem hence it makes it a more complicated issue in DTNs. Existing works in the literature are based on simulation which are suffering from computational complexities dictated by simulation. Moreover, they are optimizing the relay placement only based on specific scenarios. In this paper, we propose a generic analytical model in order to evaluate the performance of DTNs in presence of relay nodes. Our model is dependent on the mobile nodes´ mobility pattern, and we consider the case when the mobile nodes move according to the random waypoint model. In order to use the proposed model for placing the relays efficiently, we utilize two heuristic approaches. The first approach is based on optimization of the network performance using simulated annealing and the second one relies on a greedy approach to find the best location for each relay one at a time. Our simulation results show that our approaches outperform the simulation based approaches in terms of data delivery performance.