Discovery of Sensor Network Layout using Connectivity Information

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.