2026-07-20T05:47:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1114 2024-03-06T11:07:28Z ddc:004 open_access

Discovery of Sensor Network Layout using Connectivity Information Gao, Jie Lederer, Sol Wang, Yue Sensor Networks Localization Delaunay complex Rigidity We propose a distributed algorithm to discover and recover the layout of a large sensor network having a complex shape. As sensor network deployments grow large in size and become non-uniform, localization algorithms suffer from ``flip'' ambiguities---where a part of the network folds on top of another while keeping all edge length measurements preserved. We explore the high-order topological information in a sensor field to prevent incorrect flips and accurately recover the shape of the sensor network. We select landmarks on network boundaries with sufficient density, construct the landmark Voronoi diagram and its dual combinatorial Delaunay complex on these landmarks. The key insight is that when the landmarks are dense enough to capture the local geometric complexity, the combinatorial Delaunay complex is globally rigid and has a unique realization in the plane. An embedding by simply gluing the Delaunay triangles properly derives a faithful network layout, which consequently leads to a practical and sufficiently accurate localization algorithm. We prove the global rigidity of the combinatorial Delaunay complex in the case of a continuous geometric region. Simulation results on discrete networks show surprisingly good results, while multi-dimensional scaling and rubberband representation perform poorly or not at all in recovering the network layout. This is joint work with Sol Lederer and Yue Wang. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jie Gao and Sol Lederer and Yue Wang 2007 Is Part Of Dagstuhl Seminar Proceedings, Volume 7151, Geometry in Sensor Networks (2007) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.07151.2 urn:nbn:de:0030-drops-11149 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07151.2 eng https://creativecommons.org/licenses/by/4.0/legalcode