When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-11149
Go to the corresponding Portal

Gao, Jie ; Lederer, Sol ; Wang, Yue

Discovery of Sensor Network Layout using Connectivity Information

07151.GaoJie.ExtAbstract.1114.pdf (0.6 MB)


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.

BibTeX - Entry

  author =	{Jie Gao and Sol Lederer and Yue Wang},
  title =	{Discovery of Sensor Network Layout using Connectivity Information},
  booktitle =	{Geometry in Sensor Networks},
  year =	{2007},
  editor =	{Subhash Suri and Roger Wattenhofer and Peter Widmayer },
  number =	{07151},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{},
  annote =	{Keywords: Sensor Networks, Localization, Delaunay complex, Rigidity}

Keywords: Sensor Networks, Localization, Delaunay complex, Rigidity
Seminar: 07151 - Geometry in Sensor Networks
Issue Date: 2007
Date of publication: 11.07.2007

DROPS-Home | Fulltext Search | Imprint Published by LZI