×

(Robust) edge-based semidefinite programming relaxation of sensor network localization. (English) Zbl 1231.90308

The paper deals with certain semidefinite programming (SDP) relaxations of the, in general NP-hard, ad hoc wireless sensor network localization problem. In particular, the authors study key properties of a SDP relaxiation and of the recently proposed edge-based SDP relaxation (ESDP). An outcome of this study is that these relaxations are more sensitive to noise than a second order cone-programming (SOCP) relaxation. To dampen this sensitivity the authors introduce a noise-aware robust version of the ESDP relaxation for which a small individual trace is necessary and sufficient for a sensor to be accurately positioned by a certain analytic center solution if the noise level is sufficiently small. For finding such a solution they suggest a log-barrier penalty coordinate gradient descent method. In simulations this method turns out to be much faster than a primal-dual interior-point method for the solution of the ESDP problem and to produce solutions of a comparable accuracy. The method is suitable for positioning and tracking in real time.

MSC:

90C22 Semidefinite programming
90C35 Programming involving graphs or networks
49M20 Numerical methods of relaxation type
68W15 Distributed algorithms
90C06 Large-scale problems in mathematical programming
90C31 Sensitivity, stability, parametric optimization
90C90 Applications of mathematical programming

Software:

SeDuMi; SFSDP; SNLSDP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alfakih A.Y.: Graph rigidity via Euclidean distance matrices. Linear Algebra Appl. 310, 149–165 (2000) · Zbl 0965.05069 · doi:10.1016/S0024-3795(00)00066-5
[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) · Zbl 1104.68305
[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) · doi:10.1109/TASE.2006.877401
[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) · doi:10.1145/1149283.1149286
[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) · Zbl 1161.49028 · doi:10.1137/05062754X
[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) · Zbl 1100.90029
[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) · Zbl 1136.90321 · doi:10.1137/040621600
[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 · Zbl 1273.74387
[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) · doi:10.1109/78.978396
[16] Hightower J., Borriello G.: Location systems for ubiquitous computing. Computer 34, 57–66 (2001) · Zbl 05089798 · doi:10.1109/2.940014
[17] Horn R.A., Johnson C.R.: Matrix Analysis. 2nd edn. Cambridge University Press, New York (2005)
[18] Kim S., Kojima M., Waki H.: Exploiting sparsity in SDP relaxation for sensor network localization. SIAM J. Optim. 1, 192–215 (2009) · Zbl 1190.65096 · doi:10.1137/080713380
[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) · Zbl 0891.90168 · doi:10.1137/S1052623495283024
[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) · Zbl 1099.90042 · doi:10.1007/s10107-004-0555-2
[25] Niculescu D., Nath B.: Ad hoc positioning system (APS) using AOA. IEEE INFOCOM 3, 1734–1743 (2003)
[26] Nie J.: Sum of squares method for sensor network localization. Comput. Optim. Appl. 43, 151–179 (2009) · Zbl 1170.90510 · doi:10.1007/s10589-007-9131-z
[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) · Zbl 05107860 · doi:10.1109/TPDS.2004.67
[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) · Zbl 1278.90482 · doi:10.1007/s10107-006-0040-1
[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) · Zbl 1176.90454 · doi:10.1137/050640308
[35] Tseng P., Yun S.: A coordinate gradient descent method for nonsmooth separable minimization. Math. Program. 117, 387–423 (2009) · Zbl 1166.90016 · doi:10.1007/s10107-007-0170-0
[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) · Zbl 1173.90498 · doi:10.1137/060669395
[37] Wei, Z.: Large scale sensor network localization, Report, Department of Statistics, Stanford University, Stanford, November 2006
[38] Zhang, Y.: Private commuication, January 2009
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.