Yi Shang
Wheeler Ruml
Ying Zhang
ABSTRACT
It is often useful to know the geographic positions of nodes in a communications network, but adding GPS receivers or other sophisticated sensors to every node can be expensive. We present an algorithm that uses connectivity information who is within communications range of whom to derive the locations of the nodes in the network. The method can take advantage of additional information, such as estimated distances between neighbors or known positions for certain anchor nodes, if it is available. The algorithm is based on multidimensional scaling, a data analysis technique that takes O(n3) time for a network of n nodes. Through simulation studies, we demonstrate that the algorithm is more robust to measurement error than previous proposals, especially when nodes are positioned relatively uniformly throughout the plane. Furthermore, it can achieve comparable results using many fewer anchor nodes than previous methods, and even yields relative coordinates when no anchor nodes are available.
- I. Borg and P. Groenen. Modern Multidimensional Scaling, Theory and Applications. Springer-Verlag, New York, 1997.Google Scholar
Cross Ref
- A. Buja, D. F. Swayne, M. Littman, N. Dean, and H. Hofmann. XGvis: Interactive data visualization with multidimensional scaling. Journal of Computational and Graphical Statistics, page (to appear), 2001.Google Scholar
- N. Bulusu, J. Heidemann, and D. Estrin. GPS-less low-cost outdoor localization for very small devices. IEEE Personal Communications, 7(5):28--34, Oct. 2000.Google ScholarCross Ref
- L. Doherty, L. E. Ghaoui, and K. Pister. Convex position estimation in wireless sensor networks. In Proc. Infocom 2001, Anchorage, AK, April 2001.Google ScholarCross Ref
- D. Ganesan, B. Krishnamachari, A. Woo, D. Culler, D. Estrin, and S. Wicker. An empirical study of epidemic algorithms in large scale multihop wireless networks. Technical report UCLA/CSD-TR-02-0013, UCLA Computer Science Department, 2002.Google Scholar
- J. Hightower and G. Boriello. Location systems for ubiquitous computing. IEEE Computer, 34(8):57--66, Aug. 2001. Google ScholarDigital Library
- A. Howard, M. J. Mataric, and G. S. Sukhatme. Relaxation on a mesh: a formalism for generalized localization. In Proc. IEEE/RSJ Int'l Conf. on Intelligent Robots and Systems (IROS01), pages 1055--1060, 2001.Google ScholarCross Ref
- A. Nasipuri and K. Li. A directionality based location discovery scheme for wireless sensor networks. In 1st ACM Int'l Workshop on Wireless Sensor Networks and Applications (WSNA'02), pages 105--111, Atlanta, GA, Sept. 2002. Google ScholarDigital Library
- D. Niculescu and B. Nath. Ad-hoc positioning system. In IEEE GlobeCom, Nov. 2001.Google ScholarCross Ref
- S. I. Roumeliotis and G. A. Bekey. Synergetic localization for groups of mobile robots. In Proc. 39th IEEE Conf. on Decision and Control, Sydney, Australia, Dec. 2000.Google ScholarCross Ref
- C. Savarese, J. Rabaey, and K. Langendoen. Robust positioning algorithm for distributed ad-hoc wireless sensor networks. In USENIX Technical Annual Conf., Monterey, CA, June 2002. Google ScholarDigital Library
- A. Savvides, C. C. Han, and M. Srivastava. Dynamic fine-grained localization in ad hoc networks of sensors. In ACM/IEEE Int'l Conf. on Mobile Computing and Networking (MOBICON), July 2001. Google ScholarDigital Library
- A. Savvides, H. Park, and M. Srivastava. The bits and ops of the n-hop multilateration primitive for node localization problems. In 1st ACM Int'l Workshop on Wireless Sensor Networks and Applications(WSNA'02), pages 112--121, Atlanta, GA, Sept. 2002. Google ScholarDigital Library
- R. N. Shepard. Analysis of proximities: Multidimensional scaling with an unknown distance function I & II. Psychometrika, 27:125--140, 219--246, 1962.Google ScholarCross Ref
- W. S. Torgeson. Multidimensional scaling of similarity. Psychometrika, 30:379--393, 1965.Google ScholarCross Ref
Index Terms
- Localization from mere connectivity
Recommendations
Distributed weighted-multidimensional scaling for node localization in sensor networks
Accurate, distributed localization algorithms are needed for a wide variety of wireless sensor network applications. This article introduces a scalable, distributed weighted-multidimensional scaling (dwMDS) algorithm that adaptively emphasizes the most ...
Resilient localization for sensor networks in outdoor environments
The process of determining the physical locations of nodes in a wireless sensor network is known as localization. Self-localization is critical for large-scale sensor networks, because manual or assisted localization is often impractical due to time ...
A Weighted DV-Hop Localization Scheme for Wireless Sensor Networks
SCALCOM-EMBEDDEDCOM '09: Proceedings of the 2009 International Conference on Scalable Computing and Communications; Eighth International Conference on Embedded ComputingLocalization is an important problem in wireless sensor networks (WSNs), since location information is widely requested in various location-dependent applications. As one of the range-free localization algorithm DV-Hop, a well known localization ...
Comments