Approximating relay placement in sensor networks

ABSTRACT

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.

REFERENCES

• 1: E. Falck, P. Floréen, P. Kaski, J. Kohonen, and P. Orponen. Balanced data gathering in energy-constrained sensor networks. In Proc. 1st International Workshop on Algorithmic Aspects of Wireless Sensor Networks (ALGOSENSORS, Turku, Finland, July 2004), volume 3121 of Lecture Notes in Computer Science, pages 59--70, Berlin, Germany, 2004. Springer-Verlag.
• 2: Tomás Feder , Daniel Greene, Optimal algorithms for approximate clustering, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.434-444, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62255]
• 3: Patrik Floréen , Petteri Kaski , Jukka Kohonen , Pekka Orponen, Exact and approximate balanced data gathering in energy-constrained sensor networks, Theoretical Computer Science, v.344 n.1, p.30-46, 11 November 2005 [doi>10.1016/j.tcs.2005.06.024]
• 4: M. R. Garey and D. S. Johnson. The rectilinear Steiner tree problem is NP-complete. SIAM Journal on Applied Mathematics, 32(4):826--834, 1977.
• 5: Bhaskar Krishnamachari, Networking Wireless Sensors, Cambridge University Press, New York, NY, 2005
• 6: V. Raghunathan, C. Schurgers, S. Park, and M. B. Srivastava. Energy-aware wireless microsensor networks. IEEE Signal Processing Magazine, 19(2):40--50, 2002.
• 7: J. Suomela. Computational complexity of relay placement in sensor networks. In Proc. 32nd Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM, Měřín, Czech Republic, January 2006), volume 3831 of Lecture Notes in Computer Science, pages 521--529, Berlin, Germany, 2006. Springer-Verlag.
• 8: R. Tamassia and I. G. Tollis. Planar grid embedding in linear time. IEEE Transactions on Circuits and Systems, 36(9):1230--1234, 1989.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Performance, Theory

Keywords:
balanced data gathering, energy constraints, relay placement, wireless sensor networks