{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:31:32Z","timestamp":1750307492191,"version":"3.41.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2010,9,1]],"date-time":"2010-09-01T00:00:00Z","timestamp":1283299200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["ACR-0222920"],"award-info":[{"award-number":["ACR-0222920"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004410","name":"T\u00fcrkiye Bilimsel ve Teknolojik Arastirma Kurumu","doi-asserted-by":"publisher","award":["106 EO 71"],"award-info":[{"award-number":["106 EO 71"]}],"id":[{"id":"10.13039\/501100004410","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Sen. Netw."],"published-print":{"date-parts":[[2010,9]]},"abstract":"<jats:p>As the number of applications of sensor networks increases, so does the interest in sensor network localization, that is, in recovering the correct position of each node in a network of sensors from partial connectivity information such as adjacency, range, or angle between neighboring nodes. In this article, we consider the anchor-free localization problem in sensor networks that report possibly noisy range information and angular information about the relative order of each sensor's neighbors. Previously proposed techniques seem to successfully reconstruct the original positions of the nodes for relatively small networks with nodes distributed in simple regions. However, these techniques do not scale well with network size and yield poor results with nonconvex or nonsimple underlying topology. Moreover, the distributed nature of the problem makes some of the centralized techniques inapplicable in distributed settings. To address these problems we describe a multiscale dead-reckoning (MSDR) algorithm that scales well for large networks, can reconstruct complex underlying topologies, and is resilient to noise. The MSDR algorithm takes its roots from classic force-directed graph layout computation techniques. These techniques are augmented with a multiscale extension to handle the scalability issue and with a dead-reckoning extension to overcome the problems arising with nonsimple topologies. Furthermore, we show that the distributed version of the MSDR algorithm performs as well as, if not better than, its centralized counterpart, as shown by the quality of the layout, measured in terms of the accuracy of the computed pairwise distances between sensors in the network.<\/jats:p>","DOI":"10.1145\/1807048.1807057","type":"journal-article","created":{"date-parts":[[2010,10,1]],"date-time":"2010-10-01T12:29:13Z","timestamp":1285936153000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["Force-directed approaches to sensor localization"],"prefix":"10.1145","volume":"7","author":[{"given":"Alon","family":"Efrat","sequence":"first","affiliation":[{"name":"University of Arizona, Thcson, AZ"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Forrester","sequence":"additional","affiliation":[{"name":"University of Arizona, Thcson, AZ"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anand","family":"Iyer","sequence":"additional","affiliation":[{"name":"University of Arizona, Thcson, AZ"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stephen G.","family":"Kobourov","sequence":"additional","affiliation":[{"name":"University of Arizona, Thcson, AZ"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cesim","family":"Erten","sequence":"additional","affiliation":[{"name":"Kadir Has University, Cibali, Istanbul, Turkey"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ozan","family":"Kilic","sequence":"additional","affiliation":[{"name":"Isik University, Sile, Istanbul, Turkey"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,10,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCOM.2002.1024422"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132905.1132934"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.121791"},{"volume-title":"Proceedings of the 5th Sensor Array and Multichannel Signal Processing Workshop (SAM'08)","author":"Cevher V.","key":"e_1_2_1_4_1","unstructured":"}} Cevher , V. and Baraniuk , R . 2008. Compressive sensing for sensor calibration . In Proceedings of the 5th Sensor Array and Multichannel Signal Processing Workshop (SAM'08) . IEEE, 175--178. }}Cevher, V. and Baraniuk, R. 2008. Compressive sensing for sensor calibration. In Proceedings of the 5th Sensor Array and Multichannel Signal Processing Workshop (SAM'08). IEEE, 175--178."},{"volume-title":"Proceedings of the 20th IEEE Computer and Communications Societies (INFOCOM'01)","author":"Doherty L.","key":"e_1_2_1_5_1","unstructured":"}} Doherty , L. , Pister , K. , and Ghaoui , L. E . 2001. Convex optimization methods for sensor node position estimation . In Proceedings of the 20th IEEE Computer and Communications Societies (INFOCOM'01) . 1655--1663. }}Doherty, L., Pister, K., and Ghaoui, L. E. 2001. Convex optimization methods for sensor node position estimation. In Proceedings of the 20th IEEE Computer and Communications Societies (INFOCOM'01). 1655--1663."},{"key":"e_1_2_1_6_1","unstructured":"}}Efrat A. Erten C. Forrester D. Iyer A. Kilic Y. and Kobourov S. Force-directed approaches to sensor localization. http:\/\/hacivat.khas.edu.tr\/~cesim\/sensorloc.html.  }}Efrat A. Erten C. Forrester D. Iyer A. Kilic Y. and Kobourov S. Force-directed approaches to sensor localization. http:\/\/hacivat.khas.edu.tr\/~cesim\/sensorloc.html."},{"volume-title":"Proceedings of the 45th IEEE Conference on Decision and Control (CDC'06)","author":"Eren T.","key":"e_1_2_1_7_1","unstructured":"}} Eren , T. , Whiteley , W. , and Belhumeur , P. N . 2006. Using angle of arrival (bearing) information in network localization . In Proceedings of the 45th IEEE Conference on Decision and Control (CDC'06) . 4676--4681. }}Eren, T., Whiteley, W., and Belhumeur, P. N. 2006. Using angle of arrival (bearing) information in network localization. In Proceedings of the 45th IEEE Conference on Decision and Control (CDC'06). 4676--4681."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the International Workshop on Algorithmic Aspects of Wireless Sensor Networks. Lecture Notes in Computer Science","volume":"3121","author":"Fekete S. P.","unstructured":"}} Fekete , S. P. , Kr\u00f6ller , A. , Pfisterer , D. , Fischer , S. , and Buschmann , C . 2004. Neighborhood-based topology recognition in sensor networks . In Proceedings of the International Workshop on Algorithmic Aspects of Wireless Sensor Networks. Lecture Notes in Computer Science , vol. 3121 . Springer, 123--136. }}Fekete, S. P., Kr\u00f6ller, A., Pfisterer, D., Fischer, S., and Buschmann, C. 2004. Neighborhood-based topology recognition in sensor networks. In Proceedings of the International Workshop on Algorithmic Aspects of Wireless Sensor Networks. Lecture Notes in Computer Science, vol. 3121. Springer, 123--136."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31843-9_47"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380211102"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.03.014"},{"volume-title":"Matrix Computations","author":"Golub G. H.","key":"e_1_2_1_12_1","unstructured":"}} Golub , G. H. and Van Loan , C. F. 1996. Matrix Computations . Johns Hopkins Press , Baltimore, MD . }}Golub, G. H. and Van Loan, C. F. 1996. Matrix Computations. Johns Hopkins Press, Baltimore, MD."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31843-9_28"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00051"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1023720.1023726"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90102-6"},{"key":"e_1_2_1_17_1","series-title":"Lecture Notes in Electrical Engineering","volume-title":"Multiscale anchor-free distribution positioning in sensor networks","author":"Katz B.","unstructured":"}} Katz , B. and Wagner , D . Multiscale anchor-free distribution positioning in sensor networks . In Lecture Notes in Electrical Engineering , vol. 7 . Springer . }}Katz, B. and Wagner, D. Multiscale anchor-free distribution positioning in sensor networks. In Lecture Notes in Electrical Engineering, vol. 7. Springer."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00710797"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPSN.2008.55"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/65.967595"},{"volume-title":"Proceedings of the 22nd Conference of the IEEE Computer and Communications Societies (INFOCOM'03)","author":"Niculescu D.","key":"e_1_2_1_21_1","unstructured":"}} Niculescu , D. and Nath , B . 2003. Ad hoc positioning system (APS) using AOA . In Proceedings of the 22nd Conference of the IEEE Computer and Communications Societies (INFOCOM'03) . 1734--1743. }}Niculescu, D. and Nath, B. 2003. Ad hoc positioning system (APS) using AOA. In Proceedings of the 22nd Conference of the IEEE Computer and Communications Societies (INFOCOM'03). 1734--1743."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/958491.958550"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236360.1236368"},{"volume-title":"Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing. 2037--2040","author":"Savarese C.","key":"e_1_2_1_24_1","unstructured":"}} Savarese , C. , Beutel , J. , and Rabaey , J . 2001. Locationing in distributed ad-hoc wireless sensor networks . In Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing. 2037--2040 . }}Savarese, C., Beutel, J., and Rabaey, J. 2001. Locationing in distributed ad-hoc wireless sensor networks. In Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing. 2037--2040."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/381677.381693"}],"container-title":["ACM Transactions on Sensor Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1807048.1807057","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1807048.1807057","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:17:34Z","timestamp":1750249054000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1807048.1807057"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,9]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,9]]}},"alternative-id":["10.1145\/1807048.1807057"],"URL":"https:\/\/doi.org\/10.1145\/1807048.1807057","relation":{},"ISSN":["1550-4859","1550-4867"],"issn-type":[{"type":"print","value":"1550-4859"},{"type":"electronic","value":"1550-4867"}],"subject":[],"published":{"date-parts":[[2010,9]]},"assertion":[{"value":"2008-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-10-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}