Find Position based on signal strength (intersection area between circles)

Question

I'm trying to estimate a position based on signal strength received from 4 Wi-Fi Access Points. I measure the signal strength from 4 access points located in each corner of a square room with 100 square meters (10x10). I recorded the signal strengths in a known position (x, y) = (9.5, 1.5) using an Android phone. Now I want to check how accurate can a multilateration method be under the circumstances. Using MATLAB, I applied a formula to calculate distance using the signal strength. The following MATLAB function shows the application of the formula:

    function [ d_vect ] = distance( RSS )
    % Calculate distance from signal strength
    result = (27.55 - (20 * log10(2400)) + abs(RSS)) / 20;

    d_vect = power(10, result);

    end

The input RSS is a vector with the four signal strengths measured in the test point (x,y) = (9.5, 1.5). The RSS vector looks like this:

    RSS =

    -57.6000
    -60.4000
    -44.7000
    -54.4000

and the resultant vector with all the estimated distances to each access points looks like this:

   d_vect =

   7.5386
   10.4061
   1.7072
   5.2154

Now I want to estimate my position based on these distances and the access points position in order to find the error between the estimated position and the known position (9.5, 1.5). I want to find the intersection area (In order to estimate a position) between four circles where each access point is the center of one of the circles and the distance is the radius of the circle.

I want to find the grey area as shown in this image : http://www.biologycorner.com/resources/venn4.gif

Answer 1

If you want an alternative way of estimating the location without estimating the intersection of circles you can use trilateration. It is a common technique in navigation (e.g. GPS) to estimate a position given a set of distance measurements.

Also, if you wanted the area because you also need an estimate of the uncertainty of the position I would recommend solving the trilateration problem using least squares which will easily give you an estimate of the parameters involved and an error propagation to yield an uncertainty of the location.

Answer 2

If you have three sets of measurements with (x,y) coordinates of location and corresponding signal strength. such as:

m1 = (x1,y1,s1)
m2 = (x2,y2,s2)
m3 = (x3,y3,s3)

Then you can calculate distances between each of the point locations:

d12 = Sqrt((x1 - x2)^2 + (y1 - y2)^2)
d13 = Sqrt((x1 - x3)^2 + (y1 - y3)^2)
d23 = Sqrt((x2 - x3)^2 + (y2 - y3)^2)

Now consider that each signal strength measurement signifies an emitter for that signal, that comes from a location somewhere at a distance. That distance would be a radius from the location where the signal strength was measured, because one would not know at this point the direction from where the signal came from. Also, the weaker the signal... the larger the radius. In other words, the signal strength measurement would be inversely proportional to the radius. The smaller the signal strength the larger the radius, and vice versa. So, calculate the proportional, although not yet accurate, radius's of our three points:

r1 = 1/s1
r2 = 1/s2
r3 = 1/s3

So now, at each point pair, set apart by their distance we can calculate a constant (C) where the radius's from each location will just touch one another. For example, for the point pair 1 & 2:

Ca * r1 + Ca * r2 = d12

... solving for the constant Ca:

Ca = d12 / (r1 + r2)

... and we can do this for the other two pairs, as well.

Cb = d13 / (r1 + r3)

Cc = d23 / (r2 + r3)

All right... select the largest C constant, either Ca, Cb, or Cc. Then, use the parametric equation for a circle to find where the coordinates meet. I will explain.

The parametric equation for a circle is:

x = radius * Cos(theta)
y = radius * Sin(theta)

If Ca was the largest constant found, then you would compare points 1 & 2, such as:

Ca * r1 * Cos(theta1) == Ca * r2 * Cos(theta2) && 
Ca * r1 * Sin(theta1) == Ca * r2 * Sin(theta2)

... iterating theta1 and theta2 from 0 to 360 degrees, for both circles. You might write code like:

for theta1 in 0 ..< 360 {
    for theta2 in 0 ..< 360 {

        if( abs(Ca*r1*cos(theta1) - Ca*r2*cos(theta2)) < 0.01 && abs(Ca*r1*sin(theta1) - Ca*r2*sin(theta2)) < 0.01 ) {
            print("point is: (", Ca*r1*cos(theta1), Ca*r1*sin(theta1),")")
        }
    }
}

Depending on what your tolerance was for a match, you wouldn't have to do too many iterations around the circumferences of each signal radius to determine an estimate for the location of the signal source.