A Clusterized WLS Localization Algorithm for Large Scale WSNs

We present a low-complexity, accurate and robust localization algorithm suitable for large scale wireless sensor networks (WSNs). The algorithm is a clusterized version of the weighted least-squares (WLS) localization technique which we recently introduced in (Destino, 2006). The WLS algorithm is a low-complexity localization technique that owes its high-accuracy to the ability to complete and approximate the Euclidean distance matrix (EDM) samples constructed from incomplete and error-disturbed ranging information collected from the sensors. The performance of this algorithm is, however, known to decrease sharply (Destino, 2006) when the completeness is not sufficient to ensure the uniqueness of the network (graph) realization (Hendrickson, 1992). The clusterization procedure is based on recent graph-theoretical results (Krishnadev, 2005) showing that the elements of the second smallest eigenvector of the Laplacian matrix of a graph are strongly correlated with the proximity of its vertices. This graph-spectrum analytical tool is utilized here to separate the network into sub-groups that satisfy the completeness constraints of the WLS technique. The resulting clusterization procedure, which relies solely on connectivity information, allows the WLS to be applied into smaller parts of the network, each exhibiting a prescribed completeness level, leading simultaneously to a significant improvement in accuracy and to a reduction in the computational demand of the WLS optimization.