U. A. Khan, "Localization in sensor networks using message passing algorithms," *MS Project Report*, ECE Department, UW-Madison, Aug. 2004.

## Abstract

We describe a powerful and different approach to solve the localization problem of sensor networks with a very few anchor nodes (we deotne anchor nodes as those sensors that are equipped with GPS receivers so that
they are fully aware of their location). The triangulation procedure (employed usually to solve this problem)
fails when we don't have the anchor nodes lying close to each other, since it requires for any sensor node, at
least three anchor nodes in its neighborhood to find its exact position estimate. Our algorithm finds out the
position estimates of these sensor nodes. The sensor nodes then act as anchor nodes (for the sensor nodes
whose positions are still unknown) increasing the number of anchor nodes in the network, making it possible
to carry out the triangulation procedure. The algorithm is based upon the two dimensional distance matrix
computed for all the nodes present in the network and a simple message passing scheme. The network is
converted into a graph (a dense graph if the number of nodes is large) and subsequently random spanning
trees are generated from it. Working on the spanning trees is benficial since we avoid getting caught in the
cyclic nature of the graph. The algorithm takes into account the random nature of the different spanning
trees selected. The message is then passed on these spanning trees one by one, their order selected at random.
The message propagates from the root of the tree to the succeeding levels/generations. The algorithm then
updates the position of the current node by minimizing a two dimensional equation based on distance matrix
and the information contained in the message1. We further use a cross validation procedure to verify our
estimates.