Jukka Suomela

Computational complexity of relay placement in sensor networks

SOFSEM 2006 · 32nd Conference on Current Trends in Theory and Practice of Computer Science, Měřín, Czech Republic, January 2006 · doi:10.1007/11611257_50

author’s version publisher’s version

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.

Publication

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, volume 3831 of Lecture Notes in Computer Science, pages 521–529, Springer, Berlin, 2006

ISBN 978-3-540-31198-0

Links

© Springer 2006

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.