ID:14366
Type of Publication: Conference Proceedings
Authors: Zvi Lotker, M.M.de Albeniz, S.Perennes
Title: Range-free ranking in sensors networks and its applications to localization
ConferenceName: Ad-Hoc, Mobile and Wireless Networks. Third International Conference, ADHOC-NOW 2004. Proceedings (Lecture Notes in Comput. Sci. Vol.3158)
Year: 2004
Pages: 158 - 71
Abstract: We address the question of finding the sensors' coordinates, or at least an approximation of them, when the sensors' abilities are very weak. In a d dimensional space, we define an extremely relaxed notion of coordinates along dimension i. The ranki of a sensor s is the number of sensors with ith-coordinate less than the i-coordinate of s. In this paper, we provide a theoretical foundation for sensor ranking, when one assumes that a few anchor sensors know their locations and that the others determine their rank only by exchanging information. We show that the rank problem can be solved in linear time in ℝ and that it is NP-hard in ℝ2. We also study the usual localization problem and show that in general one cannot solve it; unless one knows a priori information on the sensors distribution
Keywords: computational complexity;wireless sensor networks; ,
Last Updated: 9/4/2007 12:00:00 AM
Powered by Rami Palombo © 2005
Search in: Google Scholar  |  Scitation