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 nth 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.
[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
