WiFi Positioning Triangulate

[Anton]

Hey guy's so recently I was working on an APP that used GPS to locate the positions Latitude & Longitude of a device. Now that all fine and dandy when you're outdoors but as soon as you go indoors its a whole different ball game, because the device does not have clear line of sight to the satellites it cannot accurately (within a reasonable margin of error 1-2 meters) get the correct position of the device. So GPS was out the windows and I started looking at other solutions and figured where better to ask these questions than hak5.

So far what i have learned is that in doors the position of a device can be accurately calculated using WiFi. Now I know to some of you boffins out there this will be nothing knew but this is new mind blowing territory for me and I am having a hard time wrapping my head around just how it works and was wondering if you guys could shed some noob friendly light on the whole subject of WiFi positioning and how it works.

From what I have read and understood so far you take a number of WiFi routers position them throughout a building and by doing this you can accurately locate the position of the device in the building based on WiFi signal strength of the routers? < thats the bit i don't get / am getting mixed of with.

Basically I need a cheap solution for wifi positioning. There are guys out there that all ready have bespoke products avalable but i am sure they are crazy expensive like these guys over at Navizon http://www.youtube.com/watch?v=Sw7gc8ic5vM

Also I found this video intresting, istead of wifi these guys mention using bluetooth as a means of positioning instead of wifi http://www.youtube.com/watch?v=n0UbrkJpypc


I hope we can all discuss this subject further as I really need to implement a solution like this and i just find it pretty dam interesting in general.


Also as a side note I think i may have accidently have stumbled accross why google street view cars collected all that wifi info they were not suppose to be collecting. WIFI POSITIONING!!! http://en.wikipedia.org/wiki/Wi-Fi_positioning_system just a hunch but you never know! and if that wasn't enough take a listen to this guy and play close attention when he talks about drivers! http://www.youtube.com/watch?v=Skifba2SMpE

Edited September 6, 2013 by Anton

[Drei_Drachen]

You're pretty much spot on. You need to be able to access the device and get the signal strength from preferably 3 or more wifi access points. Since the locations of the access points are known, you can look at the signal strength of each of them and come up with a relative location. You can do the same thing with Cell Towers. Their location is known. If the phone company (or law enforcement) need to track your phone, you query the phone for cell tower data and triangulate from there.

If you are looking for a cheap solution (and have a little programming ability), you can use Google's API. You get 100 queries a day for free. Depending on how many access points you have in your building, their location service can be pretty accurate. Just as an example, the school I work for has ipads (among other devices). Apple also uses wifi geolocation. If I open the map program on any ipad and allow it to 'use my location', it will give me to the room, where that ipad is located. This is because we have so many AP's, it's pretty easy to triangulate. So this leads to the next question...how do Google and Apple know the locations of our AP's? Lets pick up on what you mentioned about google. They had gotten in trouble for essentially war driving their street view cars. Well...that's one way to get this info. What's another? You know how your smartphone tells you that it is sending 'anonymous' info back to the manufacturer? Guess what else it's sending...Wifi access points, Cell towers, and their signal strength at a given location. Apple and Google both admit they do it. Since smartphones have wifi, cell, AND gps...they are the perfect device. Of course, you have the option to disable this 'feature', but how many people really will? So, instead of sending cars out to war drive, they just get their users to do it for them...Pretty ingenious if you ask me.

[Anton]

Hi, and thanks for the reply, man had no idea google and apple collected that type of information from our devices.... i should have known though after that war driving fiasco. The google API does sound like a good idea but the app, if it does take of as intended will be used by thousands of people and the requests would used in a matter of a few minutes. Right now this is the plan for the app i have in my head.

The App: Uses WiFi(or bluetooth) triangulation by calculating signal strengths of nearby routers that i would setup.

Web Service: This is what the app will communicate with over the internet to retrieve information of a location (longitude and latitude coords).

The App: Once the mobile device has this information it no longer needs the web service, the device/app will calculate its position (using wifi triangulation, i.e. scanning for a list of specific networks and comparing their signal strengths). Once the device/app calculates its position (knows its longitude and latitude coords) it can then calculate the distance between the position retrieved from the web service and its current position. One question i did ask my self was ok, how am i going to work out the longitude and latitude of the device (because i know the longitude and latitude of the routers - although I don't know how i am accurately going to do this as i am going to need many routers and they to will be indoors, so getting there lats and longs is going to be hard enough).

But yea, thats the general idea i have in my head of what i want to do. I have been looking into using bluetooth as well (which potentially could be more accurate but would cost more because i would need a shit load of transmitters.)

Also I am having a hard time trying to wrap my head around triangulation, i understand that if there was say 1 router i can measure how far i am away from that but i could be that distance away from that router in any direction.

Example:


So then i i read a little more and understood what would happen if i used two routers

Example:

So I understand things up to here, now when you bring a third router into the equation it looks like this.

Example:

I even understand that now I know where i am (roughly) but i could be at any point inside that triangle, how do i know where i am, or would the size of that triangle be dependant on how strong the routers broadcasting are? so the weaker the wifi signal the better accuracy i would have? (maybe thats why nokia is working on indoor navigation using bluetooth because its weaker than wifi) when i mean weaker i mean in terms of how far it can travel not the actual users position from it. Hope I am not just talking gibberish here just trying to understand things before i start programing any thing, and as for as programing a system that will work this out lol its going to take ne some time, especially in android....

Edited September 6, 2013 by Anton

[Drei_Drachen]

how do i know where i am, or would the size of that triangle be dependant on how strong the routers broadcasting are?

Exactly...the size of the overlapping areas are going to depend on the strength of the AP's broadcasting. The stronger the signal, the closer you are that AP. So using your last graphic, if the signal to router 1 is stronger than 2 and 3...you know that within that overlapping area, you are going to be closer to 1...Upper left. If you are the same strength on 1 and 2...but weaker on 3...it's going to be top middle.

Shortening the broadcast distance helps in that it shortens the radius around the AP. Meaning, if your device can see the AP, it's within (just using an arbitrary number) 25 ft instead of 50-100 ft...Which is fine...you just need more devices to cover more area. I assume it also helps because being closer to the AP means a lesser chance of interference artificially weakening the signal and throwing your math off. Your graphics are correct. Your understanding of the general concept is spot on. The actual process of finding that point within the three circles is called trilateration. http://en.wikipedia.org/wiki/Trilateration

The equations are pretty straight forward. Mathematically, the challenge is going to be finding the numbers to plug into the equations. As for the coding part...best of luck to ya. B)

Edit: Here is a more in-depth explanation of how you would accomplish your task. http://sdiwc.net/digital-library/download.php?id=00000223.pdf

Edited September 8, 2013 by Drei_Drachen

[barry99705]

Don't forget, what you're posting above assumes it's done in free space. Signal is going to vary quite a bit once you put this in a building.

[Anton]

Thanks for the replays guys, after reading them I have to the conclusion that a weaker router might be better for accuracy or better yet a using Bluetooth. As you say in a building there will be obstructions, the idea is to mount them 9-10ft in the air and have lots of them so i can always calculate the signal using 3 or more routers. The fact that I will end up using a fingerprinting technique using rssi will also help, i mean it will involve more work i.e. surveying the site and taking readings and then mapping but i see the effort being worth it. The finger prints would be taken at 5ft distances apart.

en

This is another reason i think bluetooth would be better. Its a pitty GPS III wasn't out already apparently its going to impove indoor navigation, to what extent thought i dont know, and also if it need a special type of reviver.

[barry99705]

Now you're getting into too expensive to setup and lots of noise area. You don't want to flood the area with too much 2.4Ghz signals, you'll start to impede normal wireless communications.

[Drei_Drachen]

Now you're getting into too expensive to setup and lots of noise area. You don't want to flood the area with too much 2.4Ghz signals, you'll start to impede normal wireless communications.

agreed...that's a little excessive.

[Anton]

even if i am using bluetooth?

[Drei_Drachen]

Bluetooth, just like wifi, runs on 2.4 GHz. So yes, your proposed setup will make things noisy. On top of that...Expensive has hell!

See "Myth #1" on the link below.

http://www.cisco.com/en/US/prod/collateral/wireless/ps9391/ps9393/ps9394/prod_white_paper0900aecd807395a9_ns736_Networking_Solutions_White_Paper.html

Edited September 10, 2013 by Drei_Drachen

[dracolytch]

Your best bet, before you go too crazy, it to just try it with a couple of routers.

Also, calculating your distance to the router gets tricky: The building, what it's made of (and how much of that is between you and any one router), the time of day, the model of access point, all play into how strong the signal is, and how much noise there is.

So, with all of those factors, it will be imperfect. And that's OK. Start small, learn, and then grow.

[Anton]

Yea that sounds like the best idea, in the words of steve baulldmer, experiment, experiment, experiment lol.