Localization From Connectivity: A 1-bit Maximum Likelihood Approach

Abstract

We consider the problem of determining the location of sensor nodes in a wireless sensor ad hoc network when only connectivity information is available, i.e., one only knows if a pair of nodes is within a fixed radio range distance of each other but does not have access to exact or even approximate distance information. We propose a maximum likelihood based reconstruction algorithm to reconstruct the node positions in a d-dimensional Euclidean space. For an n-node network, the constrained maximum likelihood estimation problem is non-convex in both the d × n node position matrix X and in the Gram matrix Q <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">X</sub> =X <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">T</sup> X. We derive an upperbound on the average Frobenius norm of the estimation error in Q, which is of the order of the reciprocal of square root of n for a fixed radio range. We present a set of algorithms for finding the maximum likelihood estimate of X by first embedding d ×n X into m × n Y, factorizing Q <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Y</sub> = Y <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">T</sup> Y, d ≤ m ≤ n, and then optimizing in Y. We relate local minima in Y to the global minimum of a relaxed convex formulation in Q <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Y</sub> to provide global convergence guarantees, despite the nonconvexity of the negative log-likelihood function in Y. We demonstrate that our algorithm is empirically successful for both uniform and irregular networks, using only a few anchor nodes. Finally, numerical experiments demonstrate improved performance of the proposed algorithm relative to the MDS algorithm and a variant.