Skip to main content
SpringerLink
Log in

(Robust) Edge-based semidefinite programming relaxation of sensor network localization

  • Full Length Paper
  • Series A
  • Published:
Mathematical Programming Submit manuscript

Abstract

Recently Wang, Zheng, Boyd, and Ye (SIAM J Optim 19:655–673, 2008) proposed a further relaxation of the semidefinite programming (SDP) relaxation of the sensor network localization problem, named edge-based SDP (ESDP). In simulation, the ESDP is solved much faster by interior-point method than SDP relaxation, and the solutions found are comparable or better in approximation accuracy. We study some key properties of the ESDP relaxation, showing that, when distances are exact, zero individual trace is not only sufficient, but also necessary for a sensor to be correctly positioned by an interior solution. We also show via an example that, when distances are inexact, zero individual trace is insufficient for a sensor to be accurately positioned by an interior solution. We then propose a noise-aware robust version of ESDP relaxation for which small individual trace is necessary and sufficient for a sensor to be accurately positioned by a certain analytic center solution, assuming the noise level is sufficiently small. For this analytic center solution, the position error for each sensor is shown to be in the order of the square root of its trace. Lastly, we propose a log-barrier penalty coordinate gradient descent method to find such an analytic center solution. In simulation, this method is much faster than interior-point method for solving ESDP, and the solutions found are comparable in approximation accuracy. Moreover, the method can distribute its computation over the sensors via local communication, making it practical for positioning and tracking in real time.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. Alfakih A.Y.: Graph rigidity via Euclidean distance matrices. Linear Algebra Appl. 310, 149–165 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  2. Aspnes, J., Goldenberg, D., Yang, Y.R.: On the computational complexity of sensor network localization, in ALGOSENSORS 2004, Turku, Finland, Lecture Notes in Computer Science, vol. 3121, pp. 32–44. Springer, New York (2004)

  3. Biswas, P., Semidefinite programming approaches to distance geometry problems, Ph. D. Thesis, Department of Electrical Engineering, Stanford University, Stanford. http://pratik.biswas.googlepages.com (2007)

  4. Biswas, P., Aghajan, H., Ye, Y.: Semidefinite programming algorithms for sensor network localization using angle of arrival information. In: Proceedings of the 39th Annual Asilomar Conference on Signals, Systems, and Computers, Pacific Grove, CA (2005)

  5. Biswas P., Liang T.-C., Toh K.-C., Wang T.-C., Ye Y.: Semidefinite programming approaches for sensor network localization with noisy distance measurements. IEEE Trans. Auto. Sci. Eng. 3, 360–371 (2006)

    Article  Google Scholar 

  6. Biswas P., Liang T.-C., Wang T.-C., Ye Y.: Semidefinite programming based algorithms for sensor network localization. ACM Trans. Sensor Networks 2, 188–220 (2006)

    Article  Google Scholar 

  7. Biswas P., Toh K.-C., Ye Y.: A distributed SDP approach for large-scale noisy anchor-free graph realization with applications to molecular conformation. SIAM J. Sci. Comput. 30, 1251–1277 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  8. Biswas, P., Ye, Y.: Semidefinite programming for ad hoc wireless sensor network localization. In: Proceedings of the 3rd IPSN, Berkeley, CA, pp. 46–54 (2004)

  9. Biswas, P., Ye, Y.: A distributed method for solving semidefinite programs arising from ad hoc wireless sensor network localization. In: Mutiscale Optimization Methods and Applications, Nonconvex Optimization and Applications, vol. 82, pp. 69–84. Springer, New York (2006)

  10. Carter W., Jin H.H., Saunders M.A., Ye Y.: SpaseLoc: an adaptive subproblem algorithm for scalable wireless sensor network localization. SIAM J. Optim. 17, 1102–1128 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  11. Ding, Y., Krislock, N., Qian, J., Wolkowicz, H.: Sensor network localization, Euclidean distance matrix completions, and graph realization. Report, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, February 2008

  12. Doherty, L., Pister, K.S.J., El Ghaoui, L.: Convex position estimation in wireless sensor networks. In: Proceedings of the 20th INFOCOM, vol. 3, pp. 1655–1663. Los Alamitos, CA (2001)

  13. Eren, T., Goldenberg, D.K., Whiteley, W., Yang, Y.R., Morse, A.S., Anderson, B.D.O., Belhumeur, P.N.: Rigidity: computation, and randomization in network localization. In: Proceedings of the 23rd INFOCOM, vol. 4, pp. 2673– 2684. Los Alamitos, CA (2004)

  14. Fariña, N., Miguez, J., Bugallo, M.F.: Novel decision-fusion algorithms for target tracking using ad hoc networks. In: Proceedings of the 61st Vehicular Technology Conference, vol. 4, pp. 2556–2559 (2005)

  15. Gustafsson F., Gunnarsson F., Bergman N., Forssell U., Jansson J., Karlsson R., Nordlund P.: Particle filters for positioning, navigation, and tracking. IEEE Trans. Signal Proc. 50, 425–437 (2002)

    Article  Google Scholar 

  16. Hightower J., Borriello G.: Location systems for ubiquitous computing. Computer 34, 57–66 (2001)

    Article  Google Scholar 

  17. Horn R.A., Johnson C.R.: Matrix Analysis. 2nd edn. Cambridge University Press, New York (2005)

    Google Scholar 

  18. Kim S., Kojima M., Waki H.: Exploiting sparsity in SDP relaxation for sensor network localization. SIAM J. Optim. 1, 192–215 (2009)

    Article  MathSciNet  Google Scholar 

  19. Krislock, N., Piccialli, V., Wolkowicz, H.: Robust semidefinite programming approaches for sensor network localization with anchors. Report, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, May 2006

  20. Liang, T.-C., Wang, T.-C., Ye, Y.: A gradient search method to round the semidefinite programming relaxation solution for ad hoc wireless sensor network localization. Report, Electrical Engineering, Stanford University, Stanford. http://serv1.ist.psu.edu:8080/viewdoc/summary?doi=10.1.1.81.7689 (2004)

  21. Liu, J., Zhang, Y., Zhao, F.: Robust distributed node localization with error management. In: Proceedings of the 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing, Florence, Italy, pp. 250–261 (2006)

  22. Moré J.J., Wu Z.: Global continuation for distance geometry problems. SIAM J. Optim. 7, 814–836 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  23. Nasipuri, A., Li, K.: A directionality based location discovery scheme for wireless sensor networks. In: Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications, Atlanta, GA, pp. 105–111 (2002)

  24. Neto J.X., Ferreira O.P., Monteiro R.D.C.: Asymptotic behavior of the central path for a special class of degenerate SDP problems. Math. Program. 103, 487–514 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  25. Niculescu D., Nath B.: Ad hoc positioning system (APS) using AOA. IEEE INFOCOM 3, 1734–1743 (2003)

    Google Scholar 

  26. Nie J.: Sum of squares method for sensor network localization. Comput. Optim. Appl. 43, 151–179 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  27. Rao, A., Ratnasamy, S., Papadimitriou, C., Shenker, S., Stoica, I.: Geographic routing without location information. In: Proceedings of the 9th Annual International Conference on Mobile Computing and Networking (MobiCom ’03), San Diego, CA, pp. 96–108 (2003)

  28. Savarese, C., Rabaey, J. M., Langendoen, K.: Robust positioning algorithms for distributed ad-hoc wireless sensor networks. In: Proceedings USENIX Annual Technical Conference, Monterey, CA, pp. 317–327 (2002)

  29. Saxe, J.B.: Embeddability of weighted graphs in k-space is strongly NP-hard. In: Proceedings of the 17th Allerton Conference in Communications, Control, and Computing, Monticello, IL, pp. 480–489 (1979)

  30. Shang Y., Ruml W., Zhang Y., Fromherz M.: Localization from connectivity in sensor networks. IEEE Trans. Parallel Distrib. Syst. 15, 961–974 (2004)

    Article  Google Scholar 

  31. Simić, S.N., Sastry, S.: Distributed localization in wireless ad hoc networks. Report, Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, 2002; First ACM International Workshop on Wireless Sensor Networks and Applications, Atlanta, GA (2002) submitted

  32. So A.M.-C., Ye Y.: Theory of semidefinite programming for sensor network localization. Math. Program. 109, 367–384 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  33. Sturm, J.F.: Using SeDuMi 1.02, A Matlab* toolbox for optimization over symmetric cones (updated for Version 1.05), Report, Department of Econometrics, Tilburg University, Tilburg, Aug–Oct (1998–2001)

  34. Tseng P.: Second-order cone programming relaxation of sensor network localizations. SIAM J. Optim. 18, 156–185 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  35. Tseng P., Yun S.: A coordinate gradient descent method for nonsmooth separable minimization. Math. Program. 117, 387–423 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  36. Wang Z., Zheng S., Ye Y., Boyd S.: Further relaxations of the semidefinite programming approach to sensor network localization. SIAM J. Optim. 19, 655–673 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  37. Wei, Z.: Large scale sensor network localization, Report, Department of Statistics, Stanford University, Stanford, November 2006

  38. Zhang, Y.: Private commuication, January 2009

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, University of Washington, Seattle, WA, 98195, USA

    Ting Kei Pong & Paul Tseng

Authors
  1. Ting Kei Pong
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Paul Tseng
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ting Kei Pong.

Additional information

This work is supported by National Science Foundation grant DMS-0511283.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Pong, T.K., Tseng, P. (Robust) Edge-based semidefinite programming relaxation of sensor network localization. Math. Program. 130, 321–358 (2011). https://doi.org/10.1007/s10107-009-0338-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-009-0338-x

Keywords

Mathematics Subject Classification (2000)

Search

Navigation