Sol Lederer
Jie Gao
Skip Abstract Section
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.
- Amenta, N., Bern, M., and Eppstein, D. 1998. The crust and the β-skeleton: Combinatorial curve reconstruction. Graph. Mod. Image Process. 60, 125--135. Google Scholar
Digital Library
- 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. Google ScholarDigital Library
- 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.Google Scholar
- 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. Google ScholarDigital Library
- Bateni, M., Demaine, E. D., Hajiaghayi, M., and Moharrami, M. 2007. Plane embeddings of planar graph metrics. Discrete Comput. Geom. 38, 3, 615--637. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Bott, R. and Tu, L. 1982. Differential Forms in Algebraic Topology. Springer-Verlag.Google Scholar
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- Carlsson, G. and de Silva, V. 2004. Topological approximation by small simplicial complexes. In Proceedings of the Symposium on Point-Based Graphics.Google Scholar
- de Silva, V. 2003. A weak definition of Delaunay triangulation. Tech. Rep., Stanford University.Google Scholar
- Edelsbrunner, H. 2001. Geometry and Topology for Mesh Generation. Cambridge University Press. Google ScholarDigital Library
- Elson, J. 2003. Time synchronization in wireless sensor networks. Ph.D. thesis, University of California, Los Angeles. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google ScholarCross Ref
- Fruchterman, T. M. J. and Reingold, E. M. 1991. Graph drawing by force-directed placement. Softw. Pract. Exper. 21, 11, 1129--1164. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Funke, S. and Klein, C. 2006. Hole detection or: “how much geometry hides in connectivity?”. In Proceedings of the 22nd Annual Symposium on Computational Geometry (SCG'06). 377--385. Google ScholarDigital Library
- 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.Google Scholar
- Funke, S. and Milosavljević, N. 2007b. Network sketching or: “how much geometry hides in connectivity? - part II”. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'07). 958--967. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google Scholar
- Graver, J. E., Servatius, B., and Servatius, H. 1993. Combinatorial Rigidity. Graduate Studies in Math., AMS.Google Scholar
- Hendrickson, B. 1992. Conditions for unique graph realizations. SIAM J. Comput. 21, 1, 65--84. Google ScholarDigital Library
- 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.Google Scholar
- Jacobs, D. J. and Hendrickson, B. 1997. An algorithm for two-dimensional rigidity percolation: the pebble game. J. Comput. Phys. 137, 2, 346--365. Google ScholarDigital Library
- Kamada, T. and Kawai, S. 1989. An algorithm for drawing general undirected graphs. Inform. Process. Lett. 31, 1, 7--15. Google ScholarDigital Library
- 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).Google Scholar
- 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. Google ScholarDigital Library
- Laman, G. 1970. On graphs and rigidity of plane skeletal structures. J. Engin. Math. 4, 331--340.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- Priyantha, N. B., Balakrishnan, H., Demaine, E., and Teller, S. 2003. Anchor-free distributed localization in sensor networks. Tech. Rep. TR-892, MIT LCS.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Tenenbaum, J., de Silva, V., and Langford, J. 2000. A global geometric framework for nonlinear dimensionality reduction. Science 290, 22, 2319--323.Google ScholarCross Ref
- Tutte, W. T. 1963. How to draw a graph. Proc. London Math. Soc. 13, 52, 743--768.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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.Google Scholar
Index Terms
- Connectivity-based localization of large-scale sensor networks with complex shape
Recommendations
Range-free localization schemes for large scale sensor networks
MobiCom '03: Proceedings of the 9th annual international conference on Mobile computing and networkingWireless 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 networksA 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 8255A 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