More Web Proxy on the site http://driver.im/

research-article

Connectivity-based localization of large-scale sensor networks with complex shape

Authors:

Jie GaoAuthors Info & Claims

ACM Transactions on Sensor Networks (TOSN), Volume 5, Issue 4

Article No.: 31, Pages 1 - 32

https://doi.org/10.1145/1614379.1614383

Published: 27 November 2009 Publication History

Abstract

We study the problem of localizing a large sensor network having a complex shape, possibly with holes. A major challenge with respect to such networks is to figure out the correct network layout, that is, avoid global flips where a part of the network folds on top of another. Our algorithm first selects landmarks on network boundaries with sufficient density, then constructs the landmark Voronoi diagram and its dual combinatorial Delaunay complex on these landmarks. The key insight is that the combinatorial Delaunay complex is provably globally rigid and has a unique realization in the plane. Thus an embedding of the landmarks by simply gluing the Delaunay triangles properly recovers the faithful network layout. With the landmarks nicely localized, the rest of the nodes can easily localize themselves by trilateration to nearby landmark nodes. This leads to a practical and accurate localization algorithm for large networks using only network connectivity. Simulations on various network topologies show surprisingly good results. In comparison, previous connectivity-based localization algorithms such as multidimensional scaling and rubberband representation generate globally flipped or distorted localization results.

References

[1]

Amenta, N., Bern, M., and Eppstein, D. 1998. The crust and the β-skeleton: Combinatorial curve reconstruction. Graph. Mod. Image Process. 60, 125--135.

Digital Library

[2]

Anderson, B. D. O., Belhumeur, P. N., Eren, T., Goldenberg, D. K., Morse, A. S., Whiteley, W., and Yang, Y. R. 2007. Graphical properties of easily localizable sensor networks. Wire. Netw. 15, 2, 177--191.

Digital Library

[3]

Aspnes, J., Goldenberg, D., and Yang, Y. R. 2004. On the computational complexity of sensor network localization. In Proceedings of the 1st International Workshop on Algorithmic Aspects of Wireless Sensor Networks (ALGOSENSORS). 32--44.

[4]

Badoiu, M., Demaine, E. D., Hajiaghayi, M. T., and Indyk, P. 2004. Low-dimensional embedding with extra information. In Proceedings of the 20th Annual Symposium on Computational Geometry (SCG'04). 320--329.

Digital Library

[5]

Bateni, M., Demaine, E. D., Hajiaghayi, M., and Moharrami, M. 2007. Plane embeddings of planar graph metrics. Discrete Comput. Geom. 38, 3, 615--637.

Digital Library

[6]

Berg, A. R. and Jordán, T. 2003. A proof of connelly's conjecture on 3-connected generic cycles. J. Comb. Theory B 88, 1, 17--37.

Digital Library

[7]

Biswas, P. and Ye, Y. 2004. Semidefinite programming for ad hoc wireless sensor network localization. In Proceedings of the 3rd International Symposium on Information Processing in Sensor Networks. 46--54.

Digital Library

[8]

Bott, R. and Tu, L. 1982. Differential Forms in Algebraic Topology. Springer-Verlag.

[9]

Bruck, J., Gao, J., and Jiang, A. 2005. MAP: Medial axis based geometric routing in sensor networks. In Proceedings of the ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom). 88--102.

Digital Library

[10]

Cabello, S., Demaine, E. D., and Rote, G. 2007. Planar embeddings of graphs with specified edge lengths. J. Graph Algor. Appl. 11, 1, 259--276.

[11]

Carlsson, G. and de Silva, V. 2004. Topological approximation by small simplicial complexes. In Proceedings of the Symposium on Point-Based Graphics.

[12]

de Silva, V. 2003. A weak definition of Delaunay triangulation. Tech. Rep., Stanford University.

[13]

Edelsbrunner, H. 2001. Geometry and Topology for Mesh Generation. Cambridge University Press.

Digital Library

[14]

Elson, J. 2003. Time synchronization in wireless sensor networks. Ph.D. thesis, University of California, Los Angeles.

Digital Library

[15]

Eren, T., Goldenberg, D., Whitley, W., Yang, Y., Morse, S., Anderson, B., and Belhumeur, P. 2004. Rigidity, computation, and randomization of network localization. In Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'04). Vol. 4. 2673--2684.

[16]

Fang, Q., Gao, J., Guibas, L., de Silva, V., and Zhang, L. 2005. GLIDER: Gradient landmark-based distributed routing for sensor networks. In Proceedings of the 24th Conference of the IEEE Communication Society (INFOCOM). Vol. 1. 339--350.

[17]

Fang, Q., Gao, J., and Guibas, L. J. 2006. Landmark-based information storage and retrieval in sensor networks. In Proceedings of the 25th Conference of the IEEE Communication Society (INFOCOM'06). Vol. 1. 339--350.

[18]

Fekete, S. P., Kaufmann, M., Kröller, A., and Lehmann, N. 2005. A new approach for boundary recognition in geometric sensor networks. In Proceedings of the 17th Canadian Conference on Computational Geometry. 82--85.

[19]

Fekete, S. P., Kröller, A., Pfisterer, D., Fischer, S., and Buschmann, C. 2004. Neighborhood-based topology recognition in sensor networks. Lecture Notes in Computer Science, vol. 3121. 123--136.

[20]

Fruchterman, T. M. J. and Reingold, E. M. 1991. Graph drawing by force-directed placement. Softw. Pract. Exper. 21, 11, 1129--1164.

Digital Library

[21]

Funke, S. 2005. Topological hole detection in wireless sensor networks and its applications. In Proceedings of the Joint Workshop on Foundations of Mobile Computing (DIALM-POMC'05). 44--53.

Digital Library

[22]

Funke, S. and Klein, C. 2006. Hole detection or: “how much geometry hides in connectivity&quest;”. In Proceedings of the 22nd Annual Symposium on Computational Geometry (SCG'06). 377--385.

Digital Library

[23]

Funke, S. and Milosavljević, N. 2007a. Guaranteed-delivery geographic routing under uncertain node locations. In Proceedings of the 26th Conference of the IEEE Communications Society (INFOCOM'07). 1244--1252.

[24]

Funke, S. and Milosavljević, N. 2007b. Network sketching or: “how much geometry hides in connectivity&quest; - part II”. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'07). 958--967.

Digital Library

[25]

Ganeriwal, S., Kumar, R., and Srivastava, M. B. 2003. Timing-sync protocol for sensor networks. In Proceedings of the 1st International Conference on Embedded Networked Sensor Systems (SenSys'03). 138--149.

Digital Library

[26]

Gao, J., Guibas, L., Oudot, S., and Wang, Y. 2008. Geodesic delaunay triangulation and witness complex in the plane. In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms. 571--580.

Digital Library

[27]

Goldenberg, D., Bihler, P., Cao, M., Fang, J., Anderson, B. D., Morse, A. S., and Yang, Y. R. 2006. Localization in sparse networks using sweeps. In Proceedings of the ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom). 110--121.

Digital Library

[28]

Goldenberg, D., Krishnamurthy, A., Maness, W., Yang, Y. R., Young, A., Morse, A. S., Savvides, A., and Anderson, B. 2005. Network localization in partially localizable networks. In Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'05). Vol. 1. 313--326.

[29]

Graver, J. E., Servatius, B., and Servatius, H. 1993. Combinatorial Rigidity. Graduate Studies in Math., AMS.

[30]

Hendrickson, B. 1992. Conditions for unique graph realizations. SIAM J. Comput. 21, 1, 65--84.

Digital Library

[31]

Howard, A., Mataric, M., and Sukhatme, G. 2001. Relaxation on a mesh: a formalism for generalized localization. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). 1055--1060.

[32]

Jacobs, D. J. and Hendrickson, B. 1997. An algorithm for two-dimensional rigidity percolation: the pebble game. J. Comput. Phys. 137, 2, 346--365.

Digital Library

[33]

Kamada, T. and Kawai, S. 1989. An algorithm for drawing general undirected graphs. Inform. Process. Lett. 31, 1, 7--15.

Digital Library

[34]

Kobourov, S. G., Efrat, A., Forrester, D., and Iyer, A. 2006. Force-directed approaches to sensor network localization. In Proceedings of the 8th Workshop on Algorithm Engineering and Experiments (ALENEX).

[35]

Kröller, A., Fekete, S. P., Pfisterer, D., and Fischer, S. 2006. Deterministic boundary recognition and topology extraction for large sensor networks. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms. 1000--1009.

Digital Library

[36]

Laman, G. 1970. On graphs and rigidity of plane skeletal structures. J. Engin. Math. 4, 331--340.

[37]

Moore, D., Leonard, J., Rus, D., and Teller, S. 2004. Robust distributed network localization with noisy range measurements. In Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems (SenSys'04). 50--61.

Digital Library

[38]

Priyantha, N. B., Balakrishnan, H., Demaine, E., and Teller, S. 2003. Anchor-free distributed localization in sensor networks. Tech. Rep. TR-892, MIT LCS.

[39]

Rao, A., Papadimitriou, C., Shenker, S., and Stoica, I. 2003. Geographic routing without location information. In Proceedings of the 9th Annual International Conference on Mobile Computing and Networking. 96--108.

Digital Library

[40]

Savvides, A., Han, C.-C., and Strivastava, M. B. 2001. Dynamic fine-grained localization in ad-hoc networks of sensors. In Proceedings of the 7th ACM Annual International Conference on Mobile Computing and Networking (MobiCom'01). 166--179.

Digital Library

[41]

Saxe, J. B. 1979. Embeddability of weighted graphs in k-space is strongly NP-hard. In Proceedings of the 17th Allerton Conference in Communications, Control and Computing. 480--489.

[42]

Shang, Y., Ruml, W., Zhang, Y., and Fromherz, M. P. J. 2003. Localization from mere connectivity. In Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc'03). 201--212.

Digital Library

[43]

So, A. M.-C. and Ye, Y. 2005. Theory of semidefinite programming for sensor network localization. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'05). 405--414.

Digital Library

[44]

Tenenbaum, J., de Silva, V., and Langford, J. 2000. A global geometric framework for nonlinear dimensionality reduction. Science 290, 22, 2319--323.

[45]

Tutte, W. T. 1963. How to draw a graph. Proc. London Math. Soc. 13, 52, 743--768.

[46]

Wang, Y., Gao, J., and Mitchell, J. S. B. 2006. Boundary recognition in sensor networks by topological methods. In Proceedings of the ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom). 122--133.

Digital Library

[47]

Zhu, X., Sarkar, R., and Gao, J. 2007. Shape segmentation and applications in sensor networks. In Proceedings of the 26th Conference of the IEEE Communications Society (INFOCOM'07). 1838--1846.

Cited By

Shiraki SShioda SMatsuda T(2024)Sensor Response-Based Localization Using Spatial Correlation of Nongeotagged DataIEEE Sensors Journal10.1109/JSEN.2023.333972324:3(3788-3796)Online publication date: 1-Feb-2024
https://doi.org/10.1109/JSEN.2023.3339723
Kumari JKumar P(2023)Location error analysis of WSN in 3D complex terrainJournal of Control and Decision10.1080/23307706.2023.217192111:3(428-437)Online publication date: 19-Feb-2023
https://doi.org/10.1080/23307706.2023.2171921
Shiraki SSuzuki AUehara TOhashi YShioda S(2022)Indoor Pedestrian Localization Methods Using Contact Information from Bluetooth Low Energy Beacons Between Smartphones2022 IEEE 95th Vehicular Technology Conference: (VTC2022-Spring)10.1109/VTC2022-Spring54318.2022.9860994(1-7)Online publication date: Jun-2022
https://doi.org/10.1109/VTC2022-Spring54318.2022.9860994
Show More Cited By

Index Terms

Connectivity-based localization of large-scale sensor networks with complex shape
1. Networks
  1. Network protocols
  2. Network types
    1. Mobile networks
    2. Wireless access networks
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Range-free localization schemes for large scale sensor networks
MobiCom '03: Proceedings of the 9th annual international conference on Mobile computing and networking

Wireless Sensor Networks have been proposed for a multitude of location-dependent applications. For such systems, the cost and limitations of the hardware on sensing nodes prevent the use of range-based localization schemes that depend on absolute point-...
Localization in wireless sensor networks
IPSN '07: Proceedings of the 6th international conference on Information processing in sensor networks

A fundamental problem in wireless sensor networks is localization -- the determination of the geographical locations of sensors. Most existing localization algorithms were designed to work well either in networks of static sensors or networks in which ...
Localizability of Wireless Sensor Networks: Beyond Wheel Extension
SSS 2013: 15th International Symposium on Stabilization, Safety, and Security of Distributed Systems - Volume 8255

A network is called localizable if the positions of all the nodes of the network can be computed uniquely. If a network is localizable and embedded in plane with generic configuration, the positions of the nodes may be computed uniquely in finite time. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Sensor Networks

ACM Transactions on Sensor Networks Volume 5, Issue 4

November 2009

264 pages

ISSN:1550-4859

EISSN:1550-4867

DOI:10.1145/1614379

Issue’s Table of Contents

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 27 November 2009

Accepted: 01 August 2008

Revised: 01 August 2008

Received: 01 March 2008

Published in TOSN Volume 5, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Division of Computer and Network Systems

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

69
Total Citations
View Citations
754
Total Downloads

Downloads (Last 12 months)15
Downloads (Last 6 weeks)6

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Shiraki SShioda SMatsuda T(2024)Sensor Response-Based Localization Using Spatial Correlation of Nongeotagged DataIEEE Sensors Journal10.1109/JSEN.2023.333972324:3(3788-3796)Online publication date: 1-Feb-2024
https://doi.org/10.1109/JSEN.2023.3339723
Kumari JKumar P(2023)Location error analysis of WSN in 3D complex terrainJournal of Control and Decision10.1080/23307706.2023.217192111:3(428-437)Online publication date: 19-Feb-2023
https://doi.org/10.1080/23307706.2023.2171921
Shiraki SSuzuki AUehara TOhashi YShioda S(2022)Indoor Pedestrian Localization Methods Using Contact Information from Bluetooth Low Energy Beacons Between Smartphones2022 IEEE 95th Vehicular Technology Conference: (VTC2022-Spring)10.1109/VTC2022-Spring54318.2022.9860994(1-7)Online publication date: Jun-2022
https://doi.org/10.1109/VTC2022-Spring54318.2022.9860994
Shiraki SShioda S(2022)Contact Information-Based Indoor Pedestrian Localization Using Bluetooth Low Energy BeaconsIEEE Access10.1109/ACCESS.2022.322230110(119863-119874)Online publication date: 2022
https://doi.org/10.1109/ACCESS.2022.3222301
Bose KKundu MAdhikary RSau B(2022)Distributed localization of wireless sensor network using communication wheelInformation and Computation10.1016/j.ic.2022.104962289:PAOnline publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1016/j.ic.2022.104962
Shiraki SOhashi YUehara TShioda S(2021)Verification of Error-Increasing Factors by Sensor Response-Based Localization Technology Through Real Device ExperimentsIEEE Access10.1109/ACCESS.2021.30953069(101729-101740)Online publication date: 2021
https://doi.org/10.1109/ACCESS.2021.3095306
Shiraki SOhashi YShioda S(2020)Data-Correlation-Based Sensor Localization for Environment Sensing with Non-Geotagged Data2020 IEEE 92nd Vehicular Technology Conference (VTC2020-Fall)10.1109/VTC2020-Fall49728.2020.9348657(1-6)Online publication date: Nov-2020
https://doi.org/10.1109/VTC2020-Fall49728.2020.9348657
Shioda SOhashi Y(2020)Environment Sensing Based on Non-Geotagged Sensor Data2020 International Conference on Computing, Networking and Communications (ICNC)10.1109/ICNC47757.2020.9049710(90-95)Online publication date: Feb-2020
https://doi.org/10.1109/ICNC47757.2020.9049710
Shi X(2020)Cooperative Localization in Wireless Sensor NetworksEncyclopedia of Wireless Networks10.1007/978-3-319-78262-1_266(235-239)Online publication date: 30-Aug-2020
https://doi.org/10.1007/978-3-319-78262-1_266
Bose KKundu MAdhikary RSau B(2020)Distributed Localization of Wireless Sensor Network Using Communication WheelAlgorithms for Sensor Systems10.1007/978-3-030-62401-9_2(17-31)Online publication date: 9-Sep-2020
https://dl.acm.org/doi/10.1007/978-3-030-62401-9_2
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents