We consider a generalization of the location from range measurements problem in lecture 11.
The goal is to determine the location of M points in a plane, given the location of K points
with known positions, and inexact measurements of the distances between certain pairs of
the points. As an application, the points may represent nodes in a wireless sensor network.
Some sensors have been carefully placed or are equipped with GPS receivers, so their location
is known. The location of the other sensor nodes has to be determined from the distances
to nearby nodes (for example, estimated from the strength of signals received from those
Nonlinear least squares formulation. The distance measurements can be represented
by an undirected graph. We use similar notation as in exercise T12.12.
• The number of vertices in the graph is N. The rst M = N K vertices represent the
points with unknown position. We refer to these as the free nodes. The last K vertices
are the points with known position and are the anchor nodes.
• The node positions are denoted by 2-vectors
p1 = (u1; v1); p2 = (u2; v2); : : : ; pN = (uN; vN):
The vectors p1, . . . , pN K are the unknowns in the problem. The vectors pN K+1, . . . ,
pN give the positions of the anchor nodes and are given.
• The edges in the graph indicate the pairs of nodes for which a distance measurement
is available. There are L edges, denoted by (i1; j1), . . . , (iL; jL). The L distance
k = kpik pjkk + “k; k = 1; : : : ; L;
where “k is measurement error.
Figure 1 shows an example with N = 30 nodes and L = 98 edges. There are K = 9 anchor
nodes, shown as squares, and M = 21 free points, shown as circles.
To estimate the location of the free nodes we minimize the function
(kpik pjkk k)
(uik ujk)2 + (vik vjk)2 k
This is a nonlinear least squares problem with variables u1; : : : ; uN K and v1; : : : ; vN K.
Figure 1: Example with 9 anchor nodes (shown as red squares), 21 free nodes (shown as blue
circles), and 98 edges.
Test problems. The MATLAB le network_loc_data.m on the class website generates
random networks. The calling sequence is
[E, pos, K] = network_loc_data(N, R)
The rst input argument N is the number of nodes in the network. This includes K = 9
anchor nodes, positioned as in Figure 1. The N 9 free nodes are placed randomly in the
square [0; 1] [0; 1]. Two nodes are connected by an edge if their distance is less than or
equal to R. Figure 1 is an example with N = 30 and R = 0:4.
The rst output argument E is an L2 array, specifying the L edges. The two entries of
row k are ik and jk, the nodes connected by edge k. The output argument pos is an N 2
array with the coordinates of the N nodes. K = 9 is the number of anchor nodes.
From the exact positions in pos we can compute the exact distances and add random
L = size(E,1);
d = sqrt(sum((pos(E(:,1),:) – pos(E(:,2),:)).^2, 2)); % exact distances
rho = (1 + .1*randn(L,1)) .* d; % add about 10 percent error
Solving the nonlinear least squares problem with the inexact distance measurements then
gives estimates as in Figure 2.
Julia users can use the function dened in network_loc_data.jl:
E, pos, K = network_loc_data(N, R);
L = size(E,1);
d = sqrt.( sum( (pos[E[:,1],:] – pos[E[:,2],:]).^2, dims = 2) );
rho = (1 .+ .1*randn(L,1)) .* d;