Range-free localization using grid graph extraction

This paper proposes a new type of range-free localization method based on affine transformation. Nodes extract subgraphs with a grid topology from a sensor network and assign x-y coordinates to themselves in a decentralized manner. The nodes estimate their positions using an affine transformation based on the mapping of the physical positions and the x-y coordinates of three anchors in an extracted graph. In contrast with multilateration-based localization methods, the proposed method works well even in a non-convex hull deployment, such as a terrain with big regions without sensors. We provide a theoretical analysis and simulation results. We also present a strategy for minimizing the position estimation error and maximizing the coverage of the proposed method. In the simulation results, the position estimation error is 0.18 (normalized by the radio communication range) and the coverage is almost 100% in a non-convex hull deployment.