James Aspnes, David Goldenberg, and Yang Richard Yang. On the computational complexity of sensor network localization. Algorithmic Aspects of Wireless Sensor Networks: First International Workshop, ALGOSENSORS 2004, Turku, Finland, July 16, 2004. Proceedings. Lecture Notes in Computer Science 3121, Springer-Verlag, 2004, pp. 32–44. Available as YALEU/DCS/TR-1282, April 2004.
Determining the positions of the sensor nodes in a network is essential to many network functionalities such as routing, coverage and tracking, and event detection. The localization problem for sensor networks is to reconstruct the positions of all of the sensors in a network, given the distances between all pairs of sensors that are within some radius r of each other. In the past few years, many algorithms for solving the localization problem were proposed, without knowing the computational complexity of the problem. In this paper, we show that no polynomial-time algorithm can solve this problem in the worst case, even for sets of distance pairs for which a unique solution exists, unless RP=NP. We also discuss the consequences of our result and present open problems.
@inproceedings(AspnesGY2004,
title="On the computational complexity of sensor network localization",
author="James Aspnes and David Goldenberg and Yang Richard Yang",
booktitle="Algorithmic Aspects of Wireless Sensor Networks: First International Workshop, ALGOSENSORS 2004, Turku, Finland, July 16, 2004. Proceedings.",
series={Lecture Notes in Computer Science},
volume=3121,
publisher="Springer-Verlag",
year=2004,
pages={32--44}
)