Complexity of Localization in Wireless Networks

Question

Let distinct points $1 ... n$ sit in $\mathbb{R}^2$. We say points $i$ and $j$ are neighbors if $|i-j| < 3 \pmod{n-2}$, meaning each point is neighbors with points with indexes within $2$, wrapping around.

The problem is:

For each pair of neighbors we are given their pairwise distances (and we know which distance corresponds to which points), and we want to reconstruct the pairwise distances of all points. My questions is, what is the complexity of this localization problem?

I don't know of a polynomial time algorithm.

This is motivated by problems in localization in sensor networks, where agents, placed ad-hoc, can wirelessly communicate with their lexicographic neighbors, and we want to reconstruct their positions.

I don't know much about geometry / localization problems, so this might be easy or known. The closest problem I know about is the Turnpike problem, recently pointed out on this forum by @Suresh Venkat.

Answer 1

(I don't have a real answer, but this was too long for a comment, so posting it here anyway...)

I suspect that the problem is NP-hard, by reduction from the subset sum problem. A proof idea:

Reduction: if the $i$th element in the subset sum instance is $x_i$, then the distance between nodes $2i-1$ and $2i$ is $s$, distance between $2i-1$ and $2i+1$ is $x_i$, distance between $2i$ and $2i+2$ is also $x_i$, and distance between $2i$ and $2i+1$ is $\sqrt{s^2 + x_i^2}$.

Assume that the edges between $2i-1$ and $2i$ for all $i$ are vertical. Then the whole graph consists of a chain of rectangles with diagonals. However, you can "flip" each rectangle so that $2i+2$ is either on the left side of $2i$ or the right side of $2i$. And you need to find the right subset of flips so that the distance between the last node $n = 2k$ and the node $2$ is "correct" (and the distance between $2k-1$ and $1$ is correct and the distance between $2k-1$ and $2$ is correct).

So far so good, but our rectangles aren't really rigid; we could also flip along the diagonal. However, I think if we choose a nasty value $s$, then perhaps we could show that everything goes horribly wrong if we ever flip along a diagonal (e.g., the coordinates of $2k$ won't be rational)? This may require some tweaks in the values $x_i$, though.

Answer 2

It is actually NP-hard. See the following paper for references.

Sriram V. Pemmaraju, Imran A. Pirwani: Good Quality Virtual Realization of Unit Ball Graphs. ESA 2007: 311-322

Answer 3

Drineas et al. wrote the paper Distance Matrix Reconstruction from Incomplete Distance Information for Sensor Network Localization. But what they achieve is probably not exactly what you ask for : they compute the whole distance map from an incomplete one, even in the presence of noise and node failures.