On bounding node-to-sink latency in wireless sensor networks with multiple sinks

Donghyun Kim, Wei Wang, Weili Wu, Deying Li, Changcun Ma, Nassim Sohaee, Wonjun Lee, Yuexuan Wang, Ding Zhu Du

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)


Bounding node-to-sink latency is an important issue of wireless sensor networks (WSNs) with a quality of service requirement. This paper proposes to deploy multiple sinks to control the worst case node-to-sink data latency in WSNs. The end-to-end latency in multihop wireless networks is known to be proportional to the hop length of the routing path that the message moves over. Therefore, we formulate the question of what is the minimum number of sinks and their locations to bound the latency as the minimum d-hop sink placement problem. We also consider its capacitated version. We show problems are NP-hard in unit disk graph (UDG) and unit ball graph, and propose constant factor approximations of the problems in both graph models. We further extend our algorithms so that they can work well in more realistic quasi UDG model. A simulation study is also conducted to see the average performance of our algorithms.

Original languageEnglish
Pages (from-to)13-29
Number of pages17
JournalInternational Journal of Sensor Networks
Issue number1
Publication statusPublished - 2013


  • Approximation algorithm
  • Graph theory
  • Mobile computing
  • Multiple sink placement
  • Quasi unit disk graph
  • Relay node placement
  • UBG
  • UDG
  • Unit ball graph
  • Unit disk graph
  • WSNs
  • Wireless sensor networks

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Computer Science Applications
  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'On bounding node-to-sink latency in wireless sensor networks with multiple sinks'. Together they form a unique fingerprint.

Cite this