On gateway selection in disruption tolerant networks

Zhuo Li, Wenzhong Li, Song Guo, Xin Liu, Sanglu Lu, Daoxu Chen

Research output: Journal article publicationJournal articleAcademic researchpeer-review

1 Citation (Scopus)

Abstract

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.
Original languageEnglish
Pages (from-to)223-243
Number of pages21
JournalAd-Hoc and Sensor Wireless Networks
Volume20
Issue number3-4
Publication statusPublished - 1 Jan 2014
Externally publishedYes

ASJC Scopus subject areas

  • Computer Science(all)
  • Instrumentation
  • Electrical and Electronic Engineering

Cite this