Semidefinite programming based algorithms for sensor network localization

ABSTRACT

An SDP relaxation based method is developed to solve the localization problem in sensor networks using incomplete and inaccurate distance information. The problem is set up to find a set of sensor positions such that given distance constraints are satisfied. The nonconvex constraints in the formulation are then relaxed in order to yield a semidefinite program that can be solved efficiently.The basic model is extended in order to account for noisy distance information. In particular, a maximum likelihood based formulation and an interval based formulation are discussed. The SDP solution can then also be used as a starting point for steepest descent based local optimization techniques that can further refine the SDP solution.We also describe the extension of the basic method to develop an iterative distributed SDP method for solving very large scale semidefinite programs that arise out of localization problems for large dense networks and are intractable using centralized methods.The performance evaluation of the technique with regard to estimation accuracy and computation time is also presented by the means of extensive simulations.Our SDP scheme also seems to be applicable to solving other Euclidean geometry problems where points are locally connected.

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: Steven J. Benson , Yinyu Ye , Xiong Zhang, Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization, SIAM Journal on Optimization, v.10 n.2, p.443-461, 1999 [doi>10.1137/S1052623497328008]
• 3: Biswas, P., Aghajan, H., and Ye, Y. 2005a. Integration of angle of arrival information for multimodal sensor network localization using semidefinite programming. Tech. rep., Wireless Sensor Networks Lab, Stanford University, May.
• 4: Biswas, P., Liang, T.-C., Toh, K.-C., and Ye, Y. 2005b. An SDP based approach for anchor-free 3d graph realization. Tech. rep., Dept of Management Science and Engineering, Stanford University. Submitted to SIAM Journal on Scientific Computing. March.
• 5: Biswas, P. and Ye, Y. 2003. A distributed method for solving semidefinite programs arising from ad hoc wireless sensor network localization. Tech. rep., Dept of Management Science and Engineering, Stanford University, October.
• 6: Pratik Biswas , Yinyu Ye, Semidefinite programming for ad hoc wireless sensor network localization, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984630]
• 7: Boyd, S., Ghaoui, L. E., Feron, E., and Balakrishnan, V. 1994. Linear Matrix Inequalities in System and Control Theory. SIAM.
• 8: Bulusu, N., Heidemann, J., and Estrin, D. 2000. Gps-less low cost outdoor localization for very small devices. Tech. rep., Computer science department, University of Southern California, April.
• 9: Carter, M., Jin, H., Saunders, M., and Ye, Y. 2005. Spaseloc: An adaptable subproblem algorithm for scalable wireless network localization. Submitted to the SIAM J. on Optimization.
• 10: Jose A. Costa , Neal Patwari , Alfred O. Hero, III, Distributed weighted-multidimensional scaling for node localization in sensor networks, ACM Transactions on Sensor Networks (TOSN), v.2 n.1, p.39-64, February 2006 [doi>10.1145/1138127.1138129]
• 11: Cox, T. and Cox, M. A. A. 2001. Multidimensional Scaling. Chapman Hall/CRC, London.
• 12: Doherty, L., Ghaoui, L. E., and Pister, K. S. J. 2001. Convex position estimation in wireless sensor networks. In Proceedings of IEEE Infocom. Anchorage, Alaska, 1655--1663.
• 13: Ganesan, D., Krishnamachari, B., Woo, A., Culler, D., Estrin, D., and Wicker, S. 2002. An empirical study of epidemic algorithms in large scale multihop wireless networks.
• 14: Groenen, P. 1993. The Majorization Approach to Multidimensional Scaling: Some Problems and Extensions. DSWO Press, Leiden University.
• 15: Jeffrey Hightower , Gaetano Borriello, Location Systems for Ubiquitous Computing, Computer, v.34 n.8, p.57-66, August 2001 [doi>10.1109/2.940014]
• 16: Howard, A., Matarić, M., and Sukhatme, G. 2001. Relaxation on a mesh: a formalism for generalized localization. In IEEE/RSJ International Conference on Intelligent Robots and Systems. Wailea, Hawaii, 1055--1060.
• 17: Holly Hui Jin, Scalable sensor localization algorithms for wireless sensor networks, University of Toronto, Toronto, Ont., Canada, 2005
• 18: Laurent, M. 2001. Matrix completion problems. The Encyclopedia of Optimization 3, 221--229.
• 19: Liang, T.-C., Wang, T.-C., and Ye, Y. 2004. A gradient search method to round the semidefinite programming relaxation solution for ad hoc wireless sensor network localization. Tech. rep., Dept of Management Science and Engineering, Stanford University, August.
• 20: 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]
• 21: Niculescu, D. and Nath, B. 2001. Ad hoc positioning system (APS). In GLOBECOM (1). 2926--2931.
• 22: Niculescu, D. and Nath, B. 2003. Ad hoc positioning system (APS) using AoA. In INFOCOM. San Francisco, CA.
• 23: Patwari, N. and Hero III, A. O. 2002. Location estimation accuracy in wireless sensor networks. In Proceedings of Asilomar Conference on Signals and Systems. Pacific Grove, CA.
• 24: Nissanka B. Priyantha , Allen K.L. Miu , Hari Balakrishnan , Seth Teller, The cricket compass for context-aware mobile applications, Proceedings of the 7th annual international conference on Mobile computing and networking, p.1-14, July 2001, Rome, Italy [doi>10.1145/381677.381679]
• 25: 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
• 26: 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]
• 27: 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]
• 28: Shang, Y. and Ruml, W. 2004. Improved MDS-based localization. In Proceedings of the 23rd Conference of the IEEE Communicatons Society (Infocom 2004).
• 29: 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]
• 30: Yi Shang , Wheeler Ruml , Ying Zhang , Markus Fromherz, Localization from Connectivity in Sensor Networks, IEEE Transactions on Parallel and Distributed Systems, v.15 n.11, p.961-974, November 2004 [doi>10.1109/TPDS.2004.67]
• 31: So, A. M.-C. and Ye, Y. 2004. Theory of semidefinite programming relaxation for sensor network localization. Tech. rep., Dept of Management Science and Engineering, Stanford University, April.
• 32: Sturm, J. F. 1999. Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optimization Methods and Software 11 & 12, 625--633.
• 33: 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, distributed methods, sensor network localization