mN/2 Algorithm to Resolve Uncertainty of Sensors Localization

Abstract

This paper introduces a novel graph-theoretic self localization algorithm that resolves ambiguities in the position candidates. The algorithm is especially effective in very sparse networks where other algorithms usually fail. Even when the algorithm cannot locate a given node, it produces a polygonal estimate of the region in which the node is located. Monte Carlo simulations show that this algorithm performs better than other well known algorithms.