Relay placement for latency minimization in delay tolerant networks

Peng Li, Taiko Kawasaki, Toshiaki Miyazaki, Song Guo

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

8 Citations (Scopus)


Delay tolerant networks (DTN) have shown its great successes in many mobile applications with intermittent connectivity. To increase contact opportunities that play an important role in routing performance and energy efficiency of DTN, the approaches of deploying static relay nodes, which are also referred to as throwboxes, has been widely adopted. In this paper, we study a relay deployment problem with the objective of minimizing communication latency among all nodes in DTN, which has been little studied so far. Upon the concept of latency graph that we propose to model the message delivery latency in DTN, the problem of relay placement for latency minimization (RPLM) is defined and proven NP-hard. To solve the RPLM problem, we propose a heuristic algorithm with low complexity, and conduct extensive simulations to show that it significantly outperforms other two existing schemes.
Original languageEnglish
Title of host publication2015 IEEE International Conference on Communications, ICC 2015
Number of pages6
ISBN (Electronic)9781467364324
Publication statusPublished - 9 Sept 2015
Externally publishedYes
EventIEEE International Conference on Communications, ICC 2015 - London, United Kingdom
Duration: 8 Jun 201512 Jun 2015


ConferenceIEEE International Conference on Communications, ICC 2015
Country/TerritoryUnited Kingdom

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Relay placement for latency minimization in delay tolerant networks'. Together they form a unique fingerprint.

Cite this