Consider an expanse of randomly-placed computing nodes. Each node
has a processor, wireless communications hardware, and
sensors. Perhaps the nodes are dropped from a plane to make
measurements across an area of land. There is some communication
radius *R*, and only nodes that are less than a distance
*R* apart can communicate. The set of nodes within range
*R* of a node *n* are called *n*'s neighborhood,
and neighborhood sizes are on the order of a dozen.

The goal is for each node to determine its own location. Some small fraction of the nodes are called "anchor" nodes and already know their location.

In one variant of this problem, each node has a way of estimating the physical distance to each of its neighbors.

Since a good set of locations for the nodes would have internode distances that agree with the measured distances, I thought of attaching virtual springs to the nodes. Each node keeps track of its own believed position, and applies spring forces as if there is a spring to each neighbor with a relaxed length equal to the measured distance to that neighbor. The springs are increasingly damped with time.

The results were mixed; it mostly worked, but there was a lot of oscillation, and it didn't always find the right answer; parts of the mesh could be "folded over".

In my simulation display, the actual locations of nodes are drawn as yellow boxes. Anchor nodes are red. Each node's belief about its location is drawn as a white cross. These are connected by gray lines. Blue lines connect nodes that are within the communication radius of each other. Click on the window once to hide the blue lines, and again to start the simulation over with another random set of node locations.

I then tried writing down a cost function to minimize and using
gradient descent. Here is the cost function, where *x* is node
position and *d* is the measured internode distance:

I made the step size a fixed length that gets exponentially smaller with time. This approach came to a solution more directly than the springs, but the cost function is not convex, so there are still problems.

The cost function can be made convex by not penalizing nodes for being too close together:

This is a convex function of the positions of the nodes, as can be seen by plotting cost as a function of distance between two nodes. The center has been flattened out:

For simplicity, I again used gradient descent with a decreasing step size. This was very successful. As long as there are anchor nodes at the edges to "pull" the other nodes into place, the nodes reach the correct positions. The only exception is at the corners, because the anchor nodes are not at the very edge.

(I did not find the relevant literature right away, but [2] also talks about solving this localization problem by posing it as an optimization and dropping nonconvex constraints. They do it a little differently.)

What if the nodes do not have a way of estimating the distance to their neighbors?

One approach is to use the minimum "hop count" between two nodes as
an approximate measure of distance. I noticed that the hop count
between two nodes *i* and *j* can be written as:

Powers of the adjacency matrix *A* are easy to compute in a
distributed way, so I looked for a relationship between entries of the
adjacency matrix and distance. The *n*th power of *A*
essentially tells you the number of walks of length *n* between
any two nodes. A long walk between the nodes is a lot like a random
walk in two dimensions.

Here is the equation for the evolution of the probability distribution in time for a random walk in two dimensions:

We use *n* as "time", set

and solve the equation to get:

To get the expected number of walks between two nodes, we multiply by
the expected number of total walks originating at any given node, and
divide by node density. Let *b* be the average neighborhood
size, and let *N* be the number of nodes per units area:

Finally, let *B* be a matrix formed from the adjacency
matrix *A* by normalizing each row to sum to 1. We can relate
elements of *B* to distances between nodes:

How well does this work? Here's a plot for *n*=5 for a node
arrangement much like the one at the top of the page. All pairs of
nodes are plotted as points. The white line is our equation, which is
a parabola on the log plot. By choosing a value of *n* to use
based on hopcount, the distance between two nodes can be found using
this equation within *R*.

This allows each node to estimate its distance to each anchor node
more accurately than just using hopcount. What does the node do with
these distance estimates? I came up with a simple convex cost function
for the nodes to minimize. Let *a* and *b* be the
indices of two anchors, and *i* be a non-anchor node. (Note
that *x_a* and *x_b* are constants reported by the
anchors, not variables in the minimization.)

This essentially creates a "trough" passing through the best locations given each pair of anchors:

So, to sum it up, each node *i* keeps track of values of
(*B*^*n*)_*ia* for each anchor *a* and for
a range of *n*. The elements of B^n for each power of
*n* are continually recalculated from the neighbors' values for
*n*-1. This allows the node to estimate the distance to each
anchor. (Currently, a value of *n* equal to twice the hopcount
is used to make the estimate.) It then minimizes the above cost
function using gradient descent to reach its location.

This algorithm seems to work fairly well, given that no range data is used. I have not compared it to existing range-free methods.

(See [3] for a review of range-free localization algorithms. Using hopcounts is common, but the rest of my algorithm seems original.)I am very interested in range-free localization because of my work with Paintable displays, and would like to explore this more.

- How good quantitatively is my proposed algorithm in realistic situations? What if membership in a neighborhood is probabilistic?
- When there are discrepancies in the final result, where do they come from? Inaccuracies in calculating distance to anchors? Bad use of distance estimates?
- How does performance depend on parameters such as neighborhood size, network shape, and anchor placement?

[1] K. Langendoen and N. Reijers, "Distributed localization in wireless sensor networks: a quantitative comparison," Computer Networks: The International Journal of Computer and Telecommunications Networking, v.43 n.4, p.499-518, 15 November 2003. (PDF)

[2] L. Doherty, K. Pister, and L. El Ghaoui, "Convex position estimation in wireless sensor networks," in Proceedings of IEEE Infocom, April 2001. (PDF)

[3] T. He, C. Huang, B. Blum, et. al., "Range-Free Localization Schemes in Large Scale Sensor Networks," MobiCom 2003. (PDF)

by David Greenspan