Localization from mere connectivity

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.

REFERENCES

• 1: I. Borg and P. Groenen. Modern Multidimensional Scaling, Theory and Applications. Springer-Verlag, New York, 1997.
• 2: 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.
• 3: 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.
• 4: L. Doherty, L. E. Ghaoui, and K. Pister. Convex position estimation in wireless sensor networks. In Proc. Infocom 2001, Anchorage, AK, April 2001.
• 5: 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.
• 6: Jeffrey Hightower , Gaetano Borriello, Location Systems for Ubiquitous Computing, Computer, v.34 n.8, p.57-66, August 2001 [doi>10.1109/2.940014]
• 7: 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.
• 8: Asis Nasipuri , Kai Li, A directionality based location discovery scheme for wireless sensor networks, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570754]
• 9: D. Niculescu and B. Nath. Ad-hoc positioning system. In IEEE GlobeCom, Nov. 2001.
• 10: 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.
• 11: Chris Savarese , Jan M. Rabaey , Koen Langendoen, Robust Positioning Algorithms for Distributed Ad-Hoc Wireless Sensor Networks, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.317-327, June 10-15, 2002
• 12: Andreas Savvides , Chih-Chieh Han , Mani B. Strivastava, Dynamic fine-grained localization in Ad-Hoc networks of sensors, Proceedings of the 7th annual international conference on Mobile computing and networking, p.166-179, July 2001, Rome, Italy [doi>10.1145/381677.381693]
• 13: Andreas Savvides , Heemin Park , Mani B. Srivastava, The bits and flops of the n-hop multilateration primitive for node localization problems, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570755]
• 14: R. N. Shepard. Analysis of proximities: Multidimensional scaling with an unknown distance function I & II. Psychometrika, 27:125--140, 219--246, 1962.
• 15: W. S. Torgeson. Multidimensional scaling of similarity. Psychometrika, 30:379--393, 1965.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations

General Terms:
Algorithms, Performance

Keywords:
ad-hoc networks, multidimensional scaling, multilateration, node localization, position estimation, sensor networks