David Moore
ABSTRACT
This paper describes a distributed, linear-time algorithm for localizing sensor network nodes in the presence of range measurement noise and demonstrates the algorithm on a physical network. We introduce the probabilistic notion of robust quadrilaterals as a way to avoid flip ambiguities that otherwise corrupt localization computations. We formulate the localization problem as a two-dimensional graph realization problem: given a planar graph with approximately known edge lengths, recover the Euclidean position of each vertex up to a global rotation and translation. This formulation is applicable to the localization of sensor networks in which each node can estimate the distance to each of its neighbors, but no absolute position reference such as GPS or fixed anchor nodes is available.
We implemented the algorithm on a physical sensor network and empirically assessed its accuracy and performance. Also, in simulation, we demonstrate that the algorithm scales to large networks and handles real-world deployment geometries. Finally, we show how the algorithm supports localization of mobile nodes.
- Bulusu, N., Heidemann, J., and Estrin, D. GPS-less low cost outdoor localization for very small devices. IEEE Personal Communications Magazine 7, 5 (October 2000), 28-34.Google Scholar
Cross Ref
- Capkun, S., Hamdi, M., and Hubaux, J.-P. GPS-free positioning in mobile ad-hoc networks. In Proceedings of the 34th Hawaii International Conference on System Sciences (2001). Google ScholarDigital Library
- Doherty, L., Pister, K. S. J., and Ghaoui, L. E. Convex position estimation in wireless sensor networks. In Proc. IEEE INFOCOM (Anchorage, AK, April 2001).Google ScholarCross Ref
- Eren, T., Goldenberg, D., Whiteley, W., Yang, Y. R., Morse, A. S., Anderson, B. D. O., and Belhumeur, P. N. Rigidity, computation, and randomization in network localization. In Proc. IEEE INFOCOM (March 2004).Google ScholarCross Ref
- Estrin, D., Govindan, R., and Heidemann, J. Embedding the internet: introduction. Commun. ACM 43, 5 (2000), 38--41. Google ScholarDigital Library
- Grabowski, R., and Khosla, P. Localization techniques for a team of small robots. In Proc. IEEE IROS (Maui, Hawaii, October 2001).Google ScholarCross Ref
- Hendrickson, B. Conditions for unique graph realizations. SIAM J. Comput. 21, 1 (1992), 65--84. Google ScholarDigital Library
- Horn, B. K. P. Closed form solution of absolute orientation using unit quaternions. Journal of the Optical Society A 4, 4 (April 1987), 629--642.Google ScholarCross Ref
- Ji, X., and Zha, H. Sensor positioning in wireless ad-hoc sensor networks using multidimensional scaling. In Proc. IEEE INFOCOM (March 2004).Google Scholar
- Laman, G. On graphs and rigidity of plane skeletal structures. J. Engineering Math 4 (1970), 331--340.Google ScholarCross Ref
- Nagpal, R., Shrobe, H., and Bachrach, J. Organizing a global coordinate system from local information on an ad hoc sensor network. In Proc. IPSN (Palo Alto, CA, April 2003), pp. 333--348. Google ScholarDigital Library
- Niculescu, D., and Nath, B. DV based positioning in ad hoc networks. Kluwer journal of Telecommunication Systems (2003), 267--280.Google Scholar
- Niculescu, D., and Nath, B. Error characteristics of ad hoc positioning systems (APS). In Proc. 5th ACM MobiHoc (Tokyo, May 2004). Google ScholarDigital Library
- Patwari, N., III, A. O. H., Perkins, M., Correal, N. S., and O'Dea, R. J. Relative location estimation in wireless sensor networks. IEEE Trans. Signal Process. 51, 8 (August 2003), 2137--2148. Google ScholarDigital Library
- Priyantha, N. B., Balakrishnan, H., Demaine, E., and Teller, S. Anchor-free distributed localization in sensor networks. Tech. Rep. 892, MIT Lab. for Comp. Sci., April 2003.Google Scholar
- Priyantha, N. B., Chakraborty, A., and Balakrishnan, H. The Cricket location-support system. In Proc. 6th ACM MobiCom (Boston, MA, August 2000). Google ScholarDigital Library
- Savarese, C., Rabaey, J., and Langendoen, K. Robust positioning algorithms for distributed ad-hoc wireless sensor networks. In USENIX Annual Tech. Conf. (Monterey, CA, June 2002), pp. 317--327. Google ScholarDigital Library
- Savvides, A., Garber, W., Adlakha, S., Moses, R., and Srivastava, M. B. On the error characteristics of multihop node localization in ad-hoc sensor networks. In Proc. IPSN (Palo Alto, CA, April 2003), pp. 317--332. Google ScholarDigital Library
- Savvides, A., Han, C.-C., and Srivastava, M. B. Dynamic fine-grained localization in ad-hoc networks of sensors. In Proc. 7th ACM MobiCom (Rome, Italy, 2001), pp. 166--179. Google ScholarDigital Library
- Saxe, J. B. Embeddability of weighted graphs in k-space is strongly NP-hard. In Proc. 17th Allerton Conf. Commun. Control Comput. (1979), pp. 480--489.Google Scholar
- Simic, S. N., and Sastry, S. Distributed localization in wireless ad hoc networks. Tech. Rep. UCB/ERL M02/26, UC Berkeley, December 2001.Google Scholar
- Smith, A., Balakrishnan, H., Goraczko, M., and Priyantha, N. Tracking moving devices with the cricket location system. In Proc. 2nd ACM MobiSys (Boston, MA, June 2004), pp. 190--202. Google ScholarDigital Library
- Teller, S., Chen, J., and Balakrishnan, H. Pervasive pose-aware applications and infrastructure. IEEE Computer Graphics and Applications (July/August 2003), 14--18. Google ScholarDigital Library
Index Terms
- Robust distributed network localization with noisy range measurements
Recommendations
Range-free localization schemes for large scale sensor networks
MobiCom '03: Proceedings of the 9th annual international conference on Mobile computing and networkingWireless Sensor Networks have been proposed for a multitude of location-dependent applications. For such systems, the cost and limitations of the hardware on sensing nodes prevent the use of range-based localization schemes that depend on absolute point-...
GPS-Free node localization in mobile wireless sensor networks
MobiDE '06: Proceedings of the 5th ACM international workshop on Data engineering for wireless and mobile accessAn important problem in mobile ad-hoc wireless sensor networks is the localization of individual nodes, i.e., each node's awareness of its position relative to the network. In this paper, we introduce a variant of this problem (directional localization) ...
Low-cost two-hop anchor node-based distributed range-free localization in wireless sensor networks
ICCSA'10: Proceedings of the 2010 international conference on Computational Science and Its Applications - Volume Part IIIDue to the fact that most of the sensor network applications are based on the location information of sensor nodes, localization is an essential research area. Some localization schemes in the literature require sensor nodes to have additional devices ...
Comments