# GSM triangulation

Could you describe an algorithm of triangulation based on the GSM data. If you know the coordinates of three towers in latitude/longitude, the signal strengh of each tower, how to find the intersection of the three cercles ?
Due to damping and reflection I am aware that you can never calculate the exact position.

-

Note that this doesn't work very reliably in practice. The measured signal strength depends not only on the distance to the base station, but also on whether you have a clear line of sight to it (and which obstacles the signal will have to punch through otherwise), and potentially on the orientation of the mobile antenna. And nobody says the different base stations transmit with the same power either -- or even with the same power in all directions; around here the antennas usually seem to be mounted on towers in a triangular arrangement, so one would expect the transmission levels to show a similar pattern.

You also need to know whether the power measurement you have is on a linear scale or something else. Whatever it is, there's a scale-dependent transformation to do in order to get something that is roughly proportional to the distance to the base station.

Why not just use GPS?

For the sake of discussion, though, let's suppose that you somehow have a good idea of the ratios of the distance between yourself and each of three power stations. Then:

• First convert the lat/long values to a square coordinate system. Latitude lines are orthogonal to longitude lines, but a degree of longitude is shorter than a degree of latitude by a factor of $\cos \varphi$ (where $\varphi$ is the latitude). Convert to kilometers instead.

• Let your unknown position be $(x,y)$ and the known base stations be at $(x_1,y_1)$, $(x_2,y_2)$ and $(x_3,y_3)$. If you know the distance to base station 2 is $f_{12}$ times the distance to base station 1, you get the equation $$(x-x_1)^2 + (y-y_1)^2 = \frac{(x-x_2)^2 + (y-y_2)^2}{f_{12}^2}$$ Since the coordinates of the base stations are known, this reduces to a quadratic equation in $x$ and $y$: $$(f_{12}^2-1)(x^2+y^2) + bx + cy = d$$ for some coefficients $b, c, d$ which you calculate.

• Do the same thing for the ratio between the distances to base stations 1 and 3. If you subtract an appropriate multiple of one equation from the other, the quadratic terms will cancel out and you're left with a linear equation in $x$ and $y$.

• Do the same thing for the ratio between the distances to 2 and 3. Subtract one of the quadratic equations you've already got, as before, and you get a different linear equation in $x$ and $y$.

• Find the intersection between the two lines.

By doing this procedure in a different order you can actually get three lines to intersect. For numerical stability in case one of the distance ratios is close to $1:1$, you should compute all three lines and then take the intersection between the pair that are closest to orthogonal.

-
why not use GPS ? just because that doesn't work indoor ! –  user62025 Feb 12 '13 at 22:39
@user62025: Neither will a distance-from-signal-strength estimation, if one base station happens to be visible through a window and another is behind several thick walls. –  Henning Makholm Feb 12 '13 at 22:45
You are right but the number of neighbour cells is generally 6. That reduces the risk no ? Did you describe the Delaunay triangulation in your answer ? if no, do you know this algorithm ? –  user62025 Feb 12 '13 at 23:10