[Solved]: How to obtain a trilateration ordering in a graph?

Problem Detail: 

In a sensor network graph $G = (V,E)$
$V = \{1,2,...,n\}$ is the set of sensors and the edge $(i,j)$ denotes that sensor $i$ and sensor $j$ are inside each other's sensing range. The weight of that edge denotes the Euclidean distance between the corresponding sensors.
The problem is in 2D.

Our goal is to fix the positions of three sensors and find the positions of the remaining.
Starting from 3 nodes (seed nodes), we first start the localization by finding a common adjacent of those 3 nodes.
Determining the position of a fourth node using three already localized node is called trilateration.

We expand the localization using trilateration. We have a localized node set, and each time we search for three nodes from that set that has a common unlocalized adjacent.

When we find such node, it does not mean it is localizable.

A trilateration ordering is: starting from three nodes, the list of vertices denoted by $a \rightarrow i, j, k$ so that when followed, the localization process is completed unless there can be no improvement.

For instance:
$1 \rightarrow 5, 6, 7$
$2 \rightarrow 5, 6, 7$
$4 \rightarrow 5, 6, 7$
$8 \rightarrow 1, 2, 4$

Is a trilateration ordering.

My question is:

How to obtain such ordering, starting from three seeds, without checking the same node triplet twice and without skipping any node triplet.

Asked By : cagirici

Answered By : D.W.

Focus on the right problem

I suspect you will find that the most important challenge is not finding a trilateration ordering, but rather choosing a strategy that minimizes the localization error.

It is easy to find a trilateration ordering, as I will describe below. In contrast, minimizing the error is more challenging. Trilateration might actually not be the best way to minimize the error. For instance, when trying to localize a node, it is possible that you might get better accuracy by using four neighbors (e.g., doing multiple trilaterations) and averaging. Also, the order in which you do the localization might matter. If you choose a bad order, errors might accumulate.

So, I suspect you might not be focusing on the right problem.

Answering your question as posed

I'm going to answer your problem as posed, even though I'm not sure it is the right problem.

There is a trivial, straightforward algorithm to solve your problem. You simply enumerate all possibilities. That can be done as follows:

• Let $S$ denote the set of nodes that are currently localized. Initially, $S$ includes just the three seed nodes.

• Repeat the following, until $S$ includes all nodes (i.e., until $S=V$):

  • For each node $v \in V\setminus S$, for all triples $s,t,u \in S$ of three nodes in $S$:

    • If $s,t,u$ are all adjacent to $v$, then append $v \to s,t,u$ to your trilateration order. Assuming localization of $v$ doesn't fail, add $v$ to $S$, and continue to the next iteration of the outermost loop.

The running time is $O(n^5)$, i.e., polynomial in the size of the graph.

With standard optimizations, the running time can be reduced significantly. For instance, you can use a worklist $W$ of nodes that are adjacent to some element of $S$ but not in $S$ themselves (i.e., $W= \{w \in V \setminus S : \exists s \in S . w \in N(s)\}$). You can update this worklist efficiently. You can also use a priority queue to sort the elements of $W$ by their "degree" (i.e., the number of nodes in $S$ they are adjacent to), and you can update this ordering efficiently.

But since you didn't list any specific running time requirements, this should be sufficient.

A better approach

I suspect that a better approach is to try to use statistical methods to estimate a global best-fit for the location of all sensors, simultaneously. For instance, you might use least-squares methods.

Let me illustrate what I mean. Suppose that you perform a bunch of measurements of the distances between pairs of sensors; create a graph $G=(V,E)$, where there is an edge $(v,w)$ if you have measured the distance between sensor $v$ and sensor $w$. Let $m(v,w)$ be the measured distance between $v$ and $w$.

Now our goal is locations of all the sensors that best fit these measurements. In particular, we are looking for a map $L : V \to \mathbb{R}^2$, where $L(v)$ represents the location of sensor $v$. We are given the locations of three seed nodes, say $v_1,v_2,v_3$. Also, we are given approximate distance measures between pairs of nodes that are connected by an edge in $G$. We want to find a location map $L$ that minimizes the total error of the measurements. Thus, the cost of a location map $L$ might be given by the total squared error:

$$\text{cost}(L) = \sum_{(v,w) \in E} (d(L(v),L(w)) - m(v,w))^2.$$

Here $d(p,q)$ represents the Euclidean distance between the two points $p,q \in \mathbb{R}^2$.

Now we want to find the location map $L$ that minimizes $\text{cost}(L)$, subject to the requirement that $L(v_1),L(v_2),L(v_3)$ have their given values (the locations of the three seed nodes).

This is an optimization problem that can be readily solved using standard methods, e.g., least-squares fitting.

Your problem then decomposes into two parts:

1. Select a set of measurements to perform.
2. Solve the optimization problem, e.g., using least-squares best fit, to find the location of all sensors.

A simple approach to decide on a set of measurements might be: each sensor looks at the set of other sensors that are within in its range, and selects 5 of them at random (and ensures that each sensor has its distance measured against at least 3 other sensors, to ensure its location can be uniquely determined; hopefully most will be measured against more than 3 other sensors). Of course, you could adjust the parameter 5 based upon empirical accuracy/performance tradeoffs.

You could also imagine more sophisticated methods, e.g., where you perform a series of measurements, solve the optimization, look at the average error for each sensor (as a crude measure of how accurate its location might be), then perform a few additional measurements (e.g., only for sensors who average error in its location is too high), and solve the optimization problem again with the additional data.

I think you might find that this is a more effective and robust way to solve your localization problem.

I also encourage you to look at the literature on localization in sensor networks. There is lots of prior work on this problem. You know the saying: a month in the field can save you a week in the library. So, spend the week in the library, and first inform yourself about what has already been tried in the literature.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/27913