6

I've been scouring the Internet for enlightenment but so far I've found very little that has helped. To be fair, I'm not a math major and might just not be using the right search queries.

I'm working on a system for outdoor WiFi localization. My experimental data suggests that using the RSSI (received signal strength) gives enough accuracy for the resolution we need, which is where the math - and you good folks - come in. I'd like to use trilateration to find a device's location, possibly using more than 3 beacons with known locations.

With the variability of the RSSI at a given distance it is highly unlikely that trilateration will produce circles with a single common intersection. As such, I need to be able to calculate the point in 2D space that is closest to the edges of all 3+ circles.

At the moment I am coding in python, if that makes a difference to anyone.

What are my options?

Thanks!

Kyle G.
  • 175
  • 1
    Can you write explicitly, which function of a point you wish to minimize?
    Let $C_1,C_2,\dots C_n$ be given circles of the plane and $A$ be a point. Let $d_i$ be the distance from the point $A$ to $C_i$ for each $i$. Which value you wish to minimize? $\max_i d_i$? $(\sum_i d^2_i)^{1/2}$? $\sum_i d_i$? Or another?     – Alex Ravsky Apr 19 '13 at 23:23
  • 1
    That's an excellent question, @Alex, and I'm not sure I have the answer. Maybe this will help though: I'd like each of the circles to have the same amount of influence on the position of point A. In other words, if a circle is added then point A should be pulled slightly towards the closest edge of the new circle. I'm thinking that that means I'd like to minimize $\sum_i d_i$. – Kyle G. Apr 20 '13 at 18:02

1 Answers1

3

Let $(x,y)$ be the mystery point and $(w_i,f_i)$ be the sources of the signals; let $m_i$ be the imperfect measurement of the distance between the mystery point and the $i$th signal. Probably the easiest expression to minimize is the sum of the squares of the errors, $$ E(x,y) = \sum_i \big( (x-w_i)^2 + (y-f_i)^2 - m_i^2 \big)^2 $$ (this expression is easier to handle than the sum of the absolute values of the errors, or the maximum absolute error). You could try to minimize this function like any other function: solve the system of equations $$ \frac{\partial E}{\partial x}(x,y) = 0, \quad \frac{\partial E}{\partial y}(x,y) = 0 $$ for $x$ and $y$ and verify that it is indeed a minimum. In this case, the partial derivatives would be polynomials of degree 3, which is within the realm of symbolic calculators to solve numerically.

Alternatively, here's a more lowbrow approach. The three measured circles have a total of six points of intersection. Ideally three of those points of intersection would coincide; in practice, though, three of them will be quite close together and the other three will be rather more distant. So compute all six points of intersection; then select the three that are close together; and then take the average of those three (the centroid of the triangle formed from them) as your estimate of the mystery point.

Greg Martin
  • 78,820
  • Wow, thanks for the info, Greg! That lowbrow approach is pretty much the concept I had in my head. The issue with that, however, is that there's no guarantee that any of the circles will actually overlap. Right now I'm assuming the worst, i.e. the possibility that none of the circles will even touch.

    Forgive my ignorance, but would you mind briefly explaining how $E(x,y)$ provides the points $x$ and $y$? The sum looks fairly straightforward, but it looks like it will only provide a single number, not a pair of coordinates. What am I missing?

     – Kyle G. Apr 20 '13 at 18:05
  • Wait a minute, I think I just found what I was missing. I'm looking for the $x$ and $y$ values that minimize $E$, correct? And you're saying that if I make the partial derivative with respect to $x$ equal to zero, then solve for $x$, it will give me the $x$ coordinate of my point? – Kyle G. Apr 20 '13 at 18:13
  • Response to your first comment: yeah, there are situations that in theory make the lowbrow approach really bad (like the circles not intersecting, or all three sources being in almost the same direction). In practice it probably works pretty well, but it is easy to break. – Greg Martin Apr 21 '13 at 19:30
  • Response to your second comment: both partial derivatives are functions of two variables $x$ and $y$. You'll need to set them both equal to $0$ simultaneously; then you can numerically solve the resulting system of equations for $x$ and $y$ together. – Greg Martin Apr 21 '13 at 19:30
  • Awesome, thanks Greg! I think I have what I need. Now to figure out how to translate that into Python, lol. – Kyle G. Apr 21 '13 at 22:03
  • Is the definition of the sum of squared errors correct? The absolute error is: $$ \sum{\sqrt{(x-w_i)^2 + (y-f_i)^2} - m_i} $$ and squaring that gives a different formula? Or am I mistaken about the absolute error? – adamw Jan 31 '14 at 20:13