Connectivity-Based Sensor Network Localization with Incremental Delaunay Refinement Method

Abstract

We study the anchor-free localization problem for a large-scale sensor network with a complex shape, knowing network connectivity information only. The main idea follows from our previous work in which a subset of the nodes are selected as landmarks and the sensor field is partitioned into Voronoi cells with all the nodes closest to the same landmark grouped into the same cell. We extract the combinatorial Delaunay complex as the dual complex of the landmark Voronoi diagram and embed the combinatorial Delaunay complex as a structural skeleton. In this paper we develop a new landmark selection algorithm with incremental Delaunay refinement method. This algorithm does not assume any knowledge of the network boundary and runs in a distributed manner to select landmarks incrementally until both the global rigidity property (the Delaunay complex is globally rigid and thus can be embedded uniquely) and the coverage property (every node is not far from the embedded Delaunay complex) are met. The new algorithm substantially improves the robustness and applicability of the original localization algorithm, especially in networks with very low average degree (even non- rigid networks) and complex shapes.