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 nodes).
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 measurements are
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)2=L X
(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 measurement error.
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;