android - Wi-Fi position triangulation

Question

Consider this map:

I need to understand how Wi-Fi triangulation basically works. The scene is portrayed in the above diagram. In order to implement Wi-Fi triangulation, I need a minimum of three Wi-Fi hotspots and their positions. The setup:

1. For simplicity, let's assume I have a 1 sq-Km by 1 sq-Km area, and I have three Wi-Fi hotspots in this area. The coordinate system is as follows: One corner of the square area is (0,0,0), and the diagonally furthest corner will have coordinates (1,1,1). All position determination is to be done relative to this coordinate system alone (for simplicity, I don't want global xyz coordinates). Within this, I have three Wi-Fi hotspots at (x1,y1,z1) , (x2,y2,z2), (x3,y3,z3).

2. We have a person with a device capable of receiving Wi-Fi signals and calculating the strength of the signal at position (x,y,z). The device could be a phone, a tablet, etc.

The problem: Calculate position (x,y,z) of the person dynamically, as they move around when you now have the following inputs:

1. The signal strength of signals received from each of the Wi-Fi hotspots

2. Coordinates of the Wi-Fi hotspots previously-stored in variables or a database.

First Question: How do I calculate position from the above inputs? I assume signal strength is directly proportional to the distance from the router, but what's the exact relation? How does Skyhook do this so accurately?

Second Question: I believe the above inputs are sufficient. Is there anything else required?

Answer 1

This is pretty easy. It's just some basic maths. Break it down into two parts:

1. Finding your horizontal location (no height).

To find your location, you need three points, but just focus on two points for a second. By using two points, you can create a triangle with yourself, and find your location based on your signal strength between two points. This will find out where you are in between two routers. For instance, if you're in between routers 3 and 4, and your signal strength in comparison to 3 is -89 and your signal strength to 4 is -54, you know that you're closer to 3 than you are to 4. If you do an approximation of distance vs signal strength, you can come up with a pretty accurate read of where you are in between routers 3 and 4. The problem left over then, is determining which side you're on in between 3 and 4, since you could have the same signal strength values (-89, -54) either above or below the routers (look at diagram)

           6

   You could be here

3--------------------------4

  You could also be here

            5

Then just find another router, and notice your signal strength. You should be able to determine which side you're on pretty easily just by taking a look at signal strength relationships between 5 and 6 routers (in the diagram).

2. You can do the same thing with height.

To do all of the above, you really only need an approximation of distance vs signal strength, and the distances between the routers. From my testing (I wrote my own Wi-Fi triangulation code), the signal strength is pretty uniform across mobile devices, so one device should have the same results as the device next to it.

Skyhook does this I think either through GPS positioning (it might be hard coded in), or basically the same principle as this. Skyhook is the only service that is Apple approved for this, so Apple basically did this same thing and then made sure other apps couldn't use it (any iPhone app that uses the restricted 802.11 library that contains the functions in order to do this will be denied from the App?Store).

How to find distance:

You need to do some simple approximations. These approximations will not be all the same depending on your environment, so -89 feet (27?m) might mean you're 15 feet (4.5?m) away from Router 3, but -89 feet (27?m) from router 4 might mean you're 13 feet (4?m) away. No matter what you do, this isn't going to be 100 percent accurate, but that's okay, because you can get within 5 feet (1.5?m) for sure.

So what you do is you find a bunch of points where you get a reading from -89 from router 3, and you jot down what your distance was. Then, you take an average, and you use this average to put down in your database (which says when you're -89 from router 3, you're 15 feet (4.5?m)). You then do this for other values, like -50 or whatever, and you jot down your values and find an average. Now, if -89 means you're 15 feet (4.5?m) away, and -50 means you're 25 feet (4.5?m) away (just an example), you have to approximate your distance when you're -75 from router 3 unless you want to go get an approximation by hand for -75. This would be cumbersome for tons of values, but you'll have to experiment to see how accurate you can be with as few data points as you can get.

You can approximate between two signal strength averages by realizing that signal strength is logarithmic, so you can estimate that since -89 is 15 feet (4.5?m), then -75 would be logarithmically (base 10 or base 2, I can't remember, but I'm leaning towards base 10) further away than -89 by a factor of 14/100.

Asking for code

I have the code somewhere, but it was a couple years ago so I'd have to dig through a lot of stuff to find it. I think conceptually, it should be easy to replicate without code. It took me about 50 lines of Java code for the android devices I was testing.

Essentially I took an android phone and created an application that allows me to at any moment display the current ID of the connected Wi-Fi device, its signal strength, other nearby Wi-Fi ID's and their signal strength, and then GPS location. This is all accessible through Android's API. I think you need an Android device on API 4 or higher or something. This was like three or four years ago, so I'm just throwing this out from what I remember.

The GPS location part was to make the mapping between physical and Wi-Fi strength easier, rather than having to create a blueprint map of my facility in some other way, I could just have google maps do it for me at the same time since I can overlay their map and the GPS coordinates essentially, while creating the distance map. You'd still need a depth map to map floor levels though, which we can do by hand pretty easily by finding if you're in the middle of two routers.

We know that signal strength is strongest to Wi-Fi hubs on the same floor, and then can double check by making sure you have weaker signals to Wi-Fi hubs on different floors. This depth map is essentially a list of Wi-Fi hubs, and their respective floors.

We do not need their positions, since we can best fit the signal strength to the GPS locations we grabbed when walking around the facility and grabbing the signal strength to certain hubs. This is some simple math. So for 2D plane position, looking down from the top, we have a bunch objects like such:

BestFitObject{
   Tuple<long, long> GPSLocation;
   List<Tuple<WifiDevice, signedInt>> WifiReadings; //WifiDeviceName(through UUID or some other way), tupled with the signalStrength when that bestFit reading was taken
}

WifiDevice{
   UUID ID; // Think a string should work fine, might be an internal type that encompasses UUID which would be better.
   int floorNumber;
   Tuple<long, long> GPSLocation; // Not entirely necessary, could provide better accuracy though
}

And then when we ping the client device and want to best fit it, it returns an object like this:

ClientPosition{
   List<Tuple<UUID, signedIt> NearbySignals; // Tuple of the UUID of the Wi-Fi device and the signal strength taken during the time of the ping.
}

Then we can easily best fit our ClientPosition to the 2D map that we created with the above two objects.

The above is pretty simple, and the depth map is even simpler in my opinion.

Ideally, you'd want to try and hit a couple different devices that encompass a couple different wireless techs (some a devices, some b devices, n, g etc) just to get more accurate results. What I found though, was that accuracy isn't that big of a deal, and you'll be within 5 feet (1.5?m) or so. That was accurate enough for my needs. Ideally, all the Wi-Fi hubs are the same model, and they usually are in large facilities/companies, but even then, it's not that big of a deal. The variability is so small, and if you don't need crazy accuracy, it won't matter.