The problem of placing relay nodes in a wireless sensor network is studied in the context of balanced data gathering. Previous work is extended by showing that even the simplest classes of the relay placement problem are hard to approximate. This work also presents a heuristic method for both lower-bounding and upper-bounding the maximum performance of a sensor network over all possible relay locations.
Lichun Bao and Isabelle Guerin Lassous (Eds.): PE-WASUN 2006, Proceedings of the Third ACM International Workshop on Performance Evaluation of Wireless Ad Hoc, Sensor and Ubiquitous Networks, October 6, 2006, Torremolinos, Malaga, Spain, pages 145–148, ACM Press, New York, 2006