Wi-Fi position triangulation
This is pretty easy. It's just some basic maths. Break it down into two parts:
- 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).
- 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.
Well, it's a signal, so its intensity will fall off by the square of the distance. See Inverse-square law.
Android is going to give you signal strength in dBm. I'm unfamiliar with that unit, but if it is anything like audio decibels, it isn't a linear scale. You'll want to factor that in.
In a perfect world, the fields will be uniform enough for pure measurements to give you distance, but if you're doing this through any metal whatsoever things might get ugly. Additionally, the internal configuration of your device's Wi-Fi radio may make it more sensitive in certain directions. I'm not an engineer or anything, so I don't know to what degree these things will affect the final result. It may be inconsequential.
Finally, for getting a three-dimensional location, I believe you need four reference points. If all the Wi-Fi hotspots are at the same height, you can still find your horizontal position. If they are not, you will be finding your position on the plane they are on, which may not be exact enough for you depending on how steep that plane is.