0

I want to have an estimation of the location of a user using the surrounding cell towers. For each tower, I have a location and a signal strength. Now I use a simple means of the coordinates but it is not very accurate (the user is not necessarily between the two towers).

I guess the solution is to draw a circle around each tower (the less the signal strength is, the larger it will be) and them compute the intersection between the circles. I usually don't have more than 3 cell towers.

Any idea how ? I found the Delaunay triangulation method but I don't think it applies here.

Thank you

Martin Trigaux
  • 5,311
  • 9
  • 45
  • 58

1 Answers1

3

You need to convert each signal strength to an estimate of distance and then use each distance (as the radius of a circle) in order to triangulate. You'll need at least three transmitters to resolve ambiguity, and accuracy will not be great, since signal strength is only very approximately related to distance and is affected by numerous external factors in the real world. Note that in ideal conditions, signal strength follows an inverse square law with distance.

Paul R
  • 208,748
  • 37
  • 389
  • 560
  • That was the idea I had (saying something like if signal is 0-10 1000m, 11-20 500m,...). But how can I compute the intersection between circles after ? I know that the more cell I have, the better it will be but I just want to improve that just using the coordinates of the closest tower. – Martin Trigaux Mar 13 '12 at 11:35
  • It's pretty easy to calculate the intersection points of two circles - do this for the strongest pair and then maybe use the third radius to resolve the ambiguity. Ideally you should add some "slack" to each radius so that you get an *area* of intersection rather than just a point. – Paul R Mar 13 '12 at 11:45
  • Interesting answer. Will the signal become weak or none when it is confined in a room or say elevator though the signal tower is beside? Then what will the accuracy of the position of the user then? – Jasonw Mar 13 '12 at 13:00
  • 1
    @Jasonw: that's the kind of thing I meant by "numerous external factors" in the answer above - the inverse square law for signal strength only applies with any real accuracy in a *free field*. – Paul R Mar 13 '12 at 13:19
  • I think I found a good equation for circle intersection. Not as easy as I thought... http://2000clicks.com/mathhelp/GeometryConicSectionCircleIntersection.aspx – Martin Trigaux Mar 13 '12 at 15:45
  • Just to be sure, using that equation, I should be in E or F cf the graph right ? – Martin Trigaux Mar 13 '12 at 15:56
  • 1
    Yes, E and F would be the two intersections - you can then use a third distance and center to resolve the ambiguity. – Paul R Mar 13 '12 at 16:09
  • I still have one problem : how can I convert the signal strength to coordinates. I estimate a strength of 1 is ~2000m, 30 is ~300m (+/-, asm scale from android, inverse square function). But I'm working with coordinates like 50N-4E, not 500 meters (for circle radius). Any idea how to convert easily ? – Martin Trigaux Mar 13 '12 at 17:14
  • You're not converting signal strength to coordinates - you're converting it to *distance*. You obviously need to know the locations (coordinates) of your transmitters and then you use the estimated distances to triangulate based on the transmitter locations. – Paul R Mar 13 '12 at 17:18
  • Yes I understand that, I have the transmitters coordinates but if I want to use the formula given above, I need to use the radius of the circle around the transmitter. The radius is in meter, I can not use like this. For example with the formula `xD = (1/2)(xB+xA) + (1/2)(xB-xA)(rA²-rB²)/d²` (where x are coordinates and r radius) or maybe I don't get something... – Martin Trigaux Mar 13 '12 at 17:29
  • The radius is the distance that you estimate based on the signal strength of the transmitter. – Paul R Mar 13 '12 at 17:33
  • Yes and ? Sorry but I don't understand how I should handle this value. If I use m or km or dBm, the result of the computation won't be the same. – Martin Trigaux Mar 13 '12 at 17:40
  • You need to use the same units for all distances, so convert your transmitter locations to say metres relative to some arbitrary reference point, then convert your signal strengths to radii, also in metres. Once you have the triangulated location in metres relative to the arbitrary reference point then you can convert this back to map coordinates or whatever else you like. – Paul R Mar 13 '12 at 19:23
  • Ok I have found this [IBM conversion](https://www.ibm.com/developerworks/java/library/j-coordconvert/index.html) script to convert to UTM – Martin Trigaux Mar 14 '12 at 12:58