On gateway selection in disruption tolerant networks

Disruption tolerant networks (DTNs) consist of a set of nodes communicating with each other opportunistically. Due to the lack of continuously connected paths between every pair of nodes, communication usually adopts a "store-carry-and-forward" manner. To achieve information access, some nodes are chosen as gateways to connect with the Internet via cellular networks. Gateways obtain data from the Internet and distribute it to the nodes they encounter. All other nodes rely on ad hoc wireless communication only and exchange data whenever they meet in an epidemic fashion. In this paper, we address the problem of choosing suitable gateways from all the nodes to reduce traffic overhead and delay of information access in DTNs. We formulate the gateway selection problem as k-GW Selection problem, where k nodes are to be selected as gateways to distribute data in order to minimize the overall delay until all nodes receive the data which is defined as expected broadcast delay. We prove that the problem is #P-hard. To solve it, we propose four heuristic algorithms, namely Random, MCS (Monte Carlo-based gateway Selection), CBS (Central-ity Based gateway Selection), and FT (Frequent Trajectory based gateway selection). The Random algorithm chooses gateways randomly, which is used as a benchmark for comparison. MCS employs Monte Carlo simulation to calculate the average broadcast delay from a set of nodes, and chooses the node set with minimal delay as gateways. CBS selects gateway nodes greedily based on the centrality metric. FT considers the delay of the frequent trajectory from a set of nodes, and applies an exhaustive strategy for gateway selection. We propose both theoretical models and simulations for performance analysis. Extensive experiments on a java simulator and real mobility traces show the effectiveness of the proposed algorithms.