Computational complexity of relay placement in sensor networks

Conference paper

Author: Jukka Suomela
Title: Computational complexity of relay placement in sensor networks
Conference: 32nd Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), Měřín, Czech Republic, January 2006
Proceedings: Jiří Wiedermann, Gerard Tel, Jaroslav Pokorný, Mária Bieliková, and Július Štuller (Eds.): SOFSEM 2006: Theory and Practice of Computer Science. 32nd Conference on Current Trends in Theory and Practice of Computer Science. Měřín, Czech Republic, January 21-27, 2006. Proceedings
Lecture Notes in Computer Science, volume 3831
Springer, Berlin, Germany, 2006
ISBN: 978-3-540-31198-0
pages 521–529
doi:10.1007/11611257_50
Links: publisher’s version · local copy
© Springer 2006
presentation, 24 January 2006
presentation at HIIT seminar, 14 October 2005
conference · proceedings · series · DBLP · Google
Abstract:
We study the computational complexity of relay placement in energy-constrained wireless sensor networks. The goal is to optimise balanced data gathering, where the utility function is a weighted sum of the minimum and average amounts of data collected from each sensor node. We define a number of classes of simplified relay placement problems, including a planar problem with a simple cost model for radio communication. We prove that all of these problem classes are NP-hard, and that in some cases even finding approximate solutions is NP-hard.
This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.