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

Bibliographical note

Funding Information:
Manuscript received October 30, 2009; revised August 28, 2010 and January 02, 2011; accepted January 15, 2011; approved by IEEE/ACM TRANSACTIONS ON NETWORKING Editor K. Kar. Date of publication February 24, 2011; date of current version October 14, 2011. This work was supported in part by the National Natural Science Foundation of China under Grants 11071191, 61073174, and 61033001; the National Scientific Foundation under Grants CNS-0524429, CCF-0627233, and CCF-0514796; the National Basic Research Program of China under Grants 2007CB807900 and 2007CB807901; the Ministry of Education, Science and Technology (MEST), Korea, under WCU (R33-2008-000-10044-0); the National Research Foundation (NRF), Korea, under Grant KRF-2008-314-D00354; and the Ministry of Knowledge Economy (MKE), Korea, under ITRC NIPA-2010-(C1090-1021-0008).


  • 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