Semidefinite programming for ad hoc wireless sensor network localization

ABSTRACT

We describe an SDP relaxation based method for the position estimation problem in wireless sensor networks. The optimization problem is set up so as to minimize the error in sensor positions to fit distance measures. Observable gauges are developed to check the quality of the point estimation of sensors or to detect erroneous sensors. The performance of this technique is highly satisfactory compared to other techniques. Very few anchor nodes are required to accurately estimate the position of all the unknown nodes in a network. Also the estimation errors are minimal even when the anchor nodes are not suitably placed within the network or the distance measurements are noisy.

REFERENCES

• 1: Abdo Y. Alfakih , Amir Khandani , Henry Wolkowicz, Solving Euclidean Distance Matrix Completion Problems Via Semidefinite Programming, Computational Optimization and Applications, v.12 n.1-3, p.13-30, Jan. 1999 [doi>10.1023/A:1008655427845]
• 2: S. J. Benson, Y. Ye, and X. Zhang. Solving large-scale sparse semidefinite programs for combinatorial optimization.
• 3: D. Bertsimas and Y. Ye. Semidefinite relaxations, multivariate normal distributions, and order statistics. Handbook of Combinatorial Optimization, 3:1--19, 1998.
• 4: P. Biswas and Y. Ye. A distributed method for solving semidefinite programs arising from ad hoc wireless sensor network localization. Technical report, Dept of Management Science and Engineering, Stanford University, October 2003.
• 5: S. Boyd, L. E. Ghaoui, E. Feron, and V. Balakrishnan. Linear Matrix Inequalities in System and Control Theory. SIAM., 1994.
• 6: N. Bulusu, J. Heidemann, and D. Estrin. Gps-less low cost outdoor localization for very small devices. Technical report, Computer science department, University of Southern California, April 2000.
• 7: L. Doherty, L. E. Ghaoui, and S. J. Pister. Convex position estimation in wireless sensor networks. In IEEE Infocom, volume 3, pages 1655--1663, April 2001.
• 8: 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, University of California, Los Angeles, 2002.
• 9: Jeffrey Hightower , Gaetano Borriello, Location Systems for Ubiquitous Computing, Computer, v.34 n.8, p.57-66, August 2001 [doi>10.1109/2.940014]
• 10: A. Howard, M. Mataric, and G. Sukhatme. Relaxation on a mesh: a formalism for generalized localization. In IEEE/RSJ Int'l Conf. on Intelligent Robots and Systems, volume 3, pages 1055--1060, October 2001.
• 11: M. Laurent. Matrix completion problems. The Encyclopedia of Optimization., 3:221--229, 2001.
• 12: Jorge J. Moré , Zhijun Wu, Global Continuation for Distance Geometry Problems, SIAM Journal on Optimization, v.7 n.3, p.814-836, 1997 [doi>10.1137/S1052623495283024]
• 13: D. Niculescu and B. Nath. Ad hoc positioning system (APS). In IEEE GLOBECOM (1), pages 2926--2931, 2001.
• 14: C. Savarese, J. Rabay, and K. Langendoen. Robust positioning algorithms for distributed ad-hoc wireless sensor networks.
• 15: 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]
• 16: 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]
• 17: Yi Shang , Wheeler Ruml , Ying Zhang , Markus P. J. Fromherz, Localization from mere connectivity, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778439]
• 18: J. F. Sturm. Let sedumi seduce you, October 2001.
• 19: Guoliang Xue , Yinyu Ye, An Efficient Algorithm for Minimizing a Sum of Euclidean Norms with Applications, SIAM Journal on Optimization, v.7 n.4, p.1017-1036, 1997 [doi>10.1137/S1052623495288362]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Convex programming

Additional Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms

Keywords:
semidefinite programming, sensor network localization