@article{2eab0e2be4cd4c4da344d2b1851a0472,
title = "Minimum data-latency-bound κ-sink placement problem in wireless sensor networks",
abstract = "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.",
keywords = "Graph theory, greedy approximation algorithms, network center placement problem, wireless sensor networks (WSNs)",
author = "Donghyun Kim and Wei Wang and Nassim Sohaee and Changcun Ma and Weili Wu and Wonjun Lee and Du, {Ding Zhu}",
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).",
year = "2011",
month = oct,
doi = "10.1109/TNET.2011.2109394",
language = "English",
volume = "19",
pages = "1344--1353",
journal = "IEEE/ACM Transactions on Networking",
issn = "1063-6692",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "5",
}