License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.07151.2
URN: urn:nbn:de:0030-drops-11149
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2007/1114/
Go to the corresponding Portal

Gao, Jie ; Lederer, Sol ; Wang, Yue

Discovery of Sensor Network Layout using Connectivity Information

pdf-format:
07151.GaoJie.ExtAbstract.1114.pdf (0.6 MB)

Abstract

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

@InProceedings{gao_et_al:DagSemProc.07151.2,
  author =	{Gao, Jie and Lederer, Sol and Wang, Yue},
  title =	{{Discovery of Sensor Network Layout using Connectivity Information}},
  booktitle =	{Geometry in Sensor Networks},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7151},
  editor =	{Subhash Suri and Roger Wattenhofer and Peter Widmayer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2007/1114},
  URN =		{urn:nbn:de:0030-drops-11149},
  doi =		{10.4230/DagSemProc.07151.2},
  annote =	{Keywords: Sensor Networks, Localization, Delaunay complex, Rigidity}
}

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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI