We consider the problem of estimating vector-valued variables from noisy “relative” measurements. The measurement model can be expressed in terms of a graph, whose nodes correspond to the variables being estimated and the edges to noisy measurements of the difference between the two variables. This type of measurement model appears in several sensor network problems, such as sensor localization and time synchronization. We consider the optimal estimate for the unknown variables obtained by applying the classical Best Linear Unbiased Estimator, which achieves the minimum variance among all linear unbiased estimators.

We propose a new algorithm to compute the optimal estimate in an iterative manner, the Overlapping Subgraph Estimator algorithm. The algorithm is distributed, asynchronous, robust to temporary communication failures, and is guaranteed to converges to the optimal estimate even with temporary communication failures. Simulations for a realistic example show that the algorithm can reduce energy consumption by a factor of two compared to previous algorithms, while achieving the same accuracy.