Minimum data-latency-bound κ-sink placement problem in wireless sensor networks

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

Research output: Contribution to journalArticlepeer-review

36 Citations (Scopus)


In this paper, we propose a new multiple-sink positioning problem in wireless sensor networks to best support real-time applications. We formally define this problem as the κ-Sink Placement Problem (κ-SPP) and prove that it is APX-complete. We show that an existing approximation algorithm for the well-known κ-center problem is a constant factor approximation of κ-SPP. Furthermore, we introduce a new greedy algorithm for κ-SPP and prove its approximation ratio is very near to the best achievable, 2. Via simulations, we show our algorithm outperforms its competitor on average.

Original languageEnglish
Article number5720275
Pages (from-to)1344-1353
Number of pages10
JournalIEEE/ACM Transactions on Networking
Issue number5
Publication statusPublished - 2011 Oct


  • Graph theory
  • greedy approximation algorithms
  • network center placement problem
  • wireless sensor networks (WSNs)

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Minimum data-latency-bound κ-sink placement problem in wireless sensor networks'. Together they form a unique fingerprint.

Cite this