# Find the position of a beacon using lat/lng/signal strength data

Let's assume, hidden in a forest, there's a beacon. I walk in the forest and, at random intervals, ping the beacon. For each ping I get a lat/lng pair and the signal strength of the ping at that point (but no direction). At the end of the day I have n readings where n is a random number.

1. How would I compute the location (lat/lng) of the beacon?

2. If, at a later time, I would get another reading, how would I add this to my current estimate of the beacon's location?

Note: we do not know how the forest is affecting the signal strength, but we can assume the effect is uniform - the beacon could be in a clearing, or buried beneath a stone.

I am assuming that all my n readings can be drawn on a map as circles where the lat/lng is the center of the circle and the signal strength is the radius. If the readings are accurate then the beacon should be in that area where all the circles overlap. I have however no clue how to find the center of the overlapping areas of n circles. Can somebody help?

Edit: clarifications
1. Each reading indicates the position I am currently standing in (random location)
2. The signal strength is inversely proportional to the distance between the reading and the beacon although I do not know what is the coefficient. I do however know that this coefficient is the same for all the readings
3. While from a theoretical point of view only two readings are necessary I would like to be able to incorporate as many of the readings as possible in the calculation as all these readings might not be 100% accurate

-
So lat/lng will always be the same number unless the beacon is moving, right? – Raskolnikov Dec 28 '11 at 11:25
@Raskolnikov: no, I think he gets lat/long of his current position and signal strength. – user20266 Dec 28 '11 at 11:35
@Thomas: Yes, that would definitely make more sense. But it's not very clear from the question. – Raskolnikov Dec 28 '11 at 11:41
Is signal strength proportional to a negative power (or is it at least a decreasing function) of distance? – bgins Dec 28 '11 at 11:41
note: if my interpretation of your description is correct, and if signal strength is an exact indicator of your distance to the beacon (i.e. if you can derive your distance to the beacon from signal strength -- you did not say this) then you need only two measurements from different locations to deduce two points one of which will be the location of the beacon, since two circles in the plane will intersect in at most two points (there will be at least one since the beacon is somewhere). A third measurement might leave only one solution. – user20266 Dec 28 '11 at 11:45

How much computing power do you have available for the exercise? Some scattered ideas:

For each point on the map you can assume that this is the location of the transmitter, then compute the true distances top each of your sample point and do a least-squares estimation of the unknown proportionality constant. Given that estimate, you can predict what the signal strength at each of your points should have been in an ideal world, and then aggregate the deviations from that, e.g., as the sum of the squared differences.

You then want to find the point on the map that minimizes the error aggregate. Doing this symbolically would probably be complex and restrict your freedom to experiment with different error aggregate functions, so if you have ample computing power, I'd suggest doing it numerically. A brute-force strategy would be to compute the error aggregate for a coarse grid first, and then progress to finer grids in the area around the minimum of the coarse grid points until you reach your desired precision.

A cheaper method would be gradient descent, or start by guessing a point and then iteratively move it in the direction of those sample points where you measured more signal than predicted and away from those where you measured less signal than predicted. This latter idea probably works only when you have the true location well surrounded by samples.

Some thought will need to be given to making sure that the error aggregate is comparable between different guesses even if they have different estimates for the proportionality constant. One way to do this would be to aggregate logarithmic errors instead of absolute ones. Ideally, the choice of error aggregate function should be done based on actual experimental data, as it is difficult to predict by pure reasoning which kind of noise you will face in the real application (and hence which technique for overcoming it will be most effective).

It is probably a good idea to use weighted averages in the calculations such that samples with large signal strength have greater weight than samples with low signal, because these are the ones you need to narrow in on the precise location, and are likely less affected by topographical obstacles.

-
Computational power is something scarce, so I need as "cheap" a solution as possible. Further, the readings are truly random so there is no saying that the becon is even roughly at the center of the readings or that I don't have 100 readings very close to each other and the beacon very far away. – Adrien Hingert Dec 28 '11 at 13:28