Minimum Data-Latency-Bound k-Sink Placement Problem in Wireless Sensor Networks
- Authors
- Kim, Donghyun; Wang, Wei; Sohaee, Nassim; Ma, Changcun; Wu, Weili; Lee, Wonjun; Du, Ding-Zhu
- Issue Date
- 10월-2011
- Publisher
- IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
- Keywords
- Graph theory; greedy approximation algorithms; network center placement problem; wireless sensor networks (WSNs)
- Citation
- IEEE-ACM TRANSACTIONS ON NETWORKING, v.19, no.5, pp.1344 - 1353
- Indexed
- SCIE
SCOPUS
- Journal Title
- IEEE-ACM TRANSACTIONS ON NETWORKING
- Volume
- 19
- Number
- 5
- Start Page
- 1344
- End Page
- 1353
- URI
- https://scholar.korea.ac.kr/handle/2021.sw.korea/111411
- DOI
- 10.1109/TNET.2011.2109394
- ISSN
- 1063-6692
- Abstract
- In this paper, we propose a new multiple-sink positioning problem in wireless sensor networks to best support realtime applications. We formally define this problem as the k-Sink Placement Problem (k-SPP) and prove that it is APX-complete. We show that an existing approximation algorithm for the well-known k-center problem is a constant factor approximation of k-SPP. Furthermore, we introduce a new greedy algorithm for k-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.
- Files in This Item
- There are no files associated with this item.
- Appears in
Collections - School of Cyber Security > Department of Information Security > 1. Journal Articles
Items in ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.