{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,15]],"date-time":"2026-08-15T17:37:26Z","timestamp":1786815446182,"version":"3.56.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2006,5,1]],"date-time":"2006-05-01T00:00:00Z","timestamp":1146441600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Sen. Netw."],"published-print":{"date-parts":[[2006,5]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/1149283.1149286","type":"journal-article","created":{"date-parts":[[2006,10,18]],"date-time":"2006-10-18T18:11:32Z","timestamp":1161195092000},"page":"188-220","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":453,"title":["Semidefinite programming based algorithms for sensor network localization"],"prefix":"10.1145","volume":"2","author":[{"given":"Pratik","family":"Biswas","sequence":"first","affiliation":[{"name":"Stanford University, Stanford, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tzu-Chen","family":"Lian","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ta-Chung","family":"Wang","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yinyu","family":"Ye","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2006,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008655427845"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623497328008"},{"key":"e_1_2_1_3_1","unstructured":"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. 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."},{"key":"e_1_2_1_4_1","unstructured":"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. 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."},{"key":"e_1_2_1_5_1","unstructured":"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. 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."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the Third International Symposium on Information Processing in Sensor Networks. ACM Press, 46--54","author":"Biswas P.","unstructured":"Biswas , P. and Ye , Y . 2004. Semidefinite programming for ad hoc wireless sensor network localization . In Proceedings of the Third International Symposium on Information Processing in Sensor Networks. ACM Press, 46--54 . 10.1145\/984622.984630 Biswas, P. and Ye, Y. 2004. Semidefinite programming for ad hoc wireless sensor network localization. In Proceedings of the Third International Symposium on Information Processing in Sensor Networks. ACM Press, 46--54. 10.1145\/984622.984630"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Boyd S. Ghaoui L. E. Feron E. and Balakrishnan V. 1994. Linear Matrix Inequalities in System and Control Theory. SIAM. Boyd S. Ghaoui L. E. Feron E. and Balakrishnan V. 1994. Linear Matrix Inequalities in System and Control Theory. SIAM.","DOI":"10.1137\/1.9781611970777"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"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. 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.","DOI":"10.1109\/98.878533"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/040621600"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1138127.1138129"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Cox T. and Cox M. A. A. 2001. Multidimensional Scaling. Chapman Hall\/CRC London. Cox T. and Cox M. A. A. 2001. Multidimensional Scaling. Chapman Hall\/CRC London.","DOI":"10.1201\/9780367801700"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of IEEE Infocom","author":"Doherty L.","unstructured":"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. 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."},{"key":"e_1_2_1_13_1","unstructured":"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. 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."},{"key":"e_1_2_1_14_1","volume-title":"The Majorization Approach to Multidimensional Scaling: Some Problems and Extensions","author":"Groenen P.","unstructured":"Groenen , P. 1993. The Majorization Approach to Multidimensional Scaling: Some Problems and Extensions . DSWO Press, Leiden University . Groenen, P. 1993. The Majorization Approach to Multidimensional Scaling: Some Problems and Extensions. DSWO Press, Leiden University."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.940014"},{"key":"e_1_2_1_16_1","volume-title":"IEEE\/RSJ International Conference on Intelligent Robots and Systems","author":"Howard A.","unstructured":"Howard , A. , Matari\u0107 , 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. Howard, A., Matari\u0107, 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."},{"key":"e_1_2_1_18_1","first-page":"221","article-title":"Matrix completion problems","volume":"3","author":"Laurent M.","year":"2001","unstructured":"Laurent , M. 2001 . Matrix completion problems . The Encyclopedia of Optimization 3 , 221 -- 229 . Laurent, M. 2001. Matrix completion problems. The Encyclopedia of Optimization 3, 221--229.","journal-title":"The Encyclopedia of Optimization"},{"key":"e_1_2_1_19_1","unstructured":"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. 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."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623495283024"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Niculescu D. and Nath B. 2001. Ad hoc positioning system (APS). In GLOBECOM (1). 2926--2931. Niculescu D. and Nath B. 2001. Ad hoc positioning system (APS). In GLOBECOM (1). 2926--2931.","DOI":"10.1109\/GLOCOM.2001.965964"},{"key":"e_1_2_1_22_1","unstructured":"Niculescu D. and Nath B. 2003. Ad hoc positioning system (APS) using AoA. In INFOCOM. San Francisco CA. Niculescu D. and Nath B. 2003. Ad hoc positioning system (APS) using AoA. In INFOCOM. San Francisco CA."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of Asilomar Conference on Signals and Systems","author":"Patwari N.","unstructured":"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. 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."},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Priyantha N. B. Miu A. K. L. Balakrishnan H. and Teller S. 2001. The cricket compass for context-aware mobile applications. In Mobile Computing and Networking. 1--14. 10.1145\/381677.381679 Priyantha N. B. Miu A. K. L. Balakrishnan H. and Teller S. 2001. The cricket compass for context-aware mobile applications. In Mobile Computing and Networking. 1--14. 10.1145\/381677.381679","DOI":"10.1145\/381677.381679"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the General Track: 2002 USENIX Annual Technical Conference. USENIX Association, 317--327","author":"Savarese C.","unstructured":"Savarese , C. , Rabaey , J. M. , and Langendoen , K . 2002. Robust positioning algorithms for distributed ad hoc wireless sensor networks . In Proceedings of the General Track: 2002 USENIX Annual Technical Conference. USENIX Association, 317--327 . Savarese, C., Rabaey, J. M., and Langendoen, K. 2002. Robust positioning algorithms for distributed ad hoc wireless sensor networks. In Proceedings of the General Track: 2002 USENIX Annual Technical Conference. USENIX Association, 317--327."},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Savvides A. Han C.-C. and Strivastava M. B. 2001. Dynamic fine-grained localization in ad hoc networks of sensors. In Mobile Computing and Networking. 166--179. 10.1145\/381677.381693 Savvides A. Han C.-C. and Strivastava M. B. 2001. Dynamic fine-grained localization in ad hoc networks of sensors. In Mobile Computing and Networking. 166--179. 10.1145\/381677.381693","DOI":"10.1145\/381677.381693"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications. ACM Press, 112--121","author":"Savvides A.","unstructured":"Savvides , A. , Park , H. , and Srivastava , M. B . 2002. The bits and flops of the n-hop multilateration primitive for node localization problems . In Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications. ACM Press, 112--121 . 10.1145\/570738.570755 Savvides, A., Park, H., and Srivastava, M. B. 2002. The bits and flops of the n-hop multilateration primitive for node localization problems. In Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications. ACM Press, 112--121. 10.1145\/570738.570755"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 23rd Conference of the IEEE Communicatons Society (Infocom","author":"Shang Y.","year":"2004","unstructured":"Shang , Y. and Ruml , W . 2004. Improved MDS-based localization . In Proceedings of the 23rd Conference of the IEEE Communicatons Society (Infocom 2004 ). Shang, Y. and Ruml, W. 2004. Improved MDS-based localization. In Proceedings of the 23rd Conference of the IEEE Communicatons Society (Infocom 2004)."},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the fourth ACM International Symposium on Mobile Ad Hoc Networking and Computing. ACM Press, 201--212","author":"Shang Y.","unstructured":"Shang , Y. , Ruml , W. , Zhang , Y. , and Fromherz , M. P . 2003. Localization from mere connectivity . In Proceedings of the fourth ACM International Symposium on Mobile Ad Hoc Networking and Computing. ACM Press, 201--212 . 10.1145\/778415.778439 Shang, Y., Ruml, W., Zhang, Y., and Fromherz, M. P. 2003. Localization from mere connectivity. In Proceedings of the fourth ACM International Symposium on Mobile Ad Hoc Networking and Computing. ACM Press, 201--212. 10.1145\/778415.778439"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2004.67"},{"key":"e_1_2_1_31_1","unstructured":"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. 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."},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Sturm J. F. 1999. Using SeDuMi 1.02 a MATLAB toolbox for optimization over symmetric cones. Optimization Methods and Software 11 & 12 625--633. Sturm J. F. 1999. Using SeDuMi 1.02 a MATLAB toolbox for optimization over symmetric cones. Optimization Methods and Software 11 & 12 625--633.","DOI":"10.1080\/10556789908805766"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623495288362"}],"container-title":["ACM Transactions on Sensor Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1149283.1149286","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1149283.1149286","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:31:13Z","timestamp":1750264273000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1149283.1149286"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,5]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2006,5]]}},"alternative-id":["10.1145\/1149283.1149286"],"URL":"https:\/\/doi.org\/10.1145\/1149283.1149286","relation":{},"ISSN":["1550-4859","1550-4867"],"issn-type":[{"value":"1550-4859","type":"print"},{"value":"1550-4867","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,5]]},"assertion":[{"value":"2006-05-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}