Close

How Does It Work?

A project log for SubPos Positioning System

A "dataless" Wi-Fi positioning system that can be used anywhere GPS can't.

bleckyBlecky 03/24/2015 at 11:380 Comments

So you might be wondering, how is this any different from any of the aforementioned technologies? Well SPS fully utilises the capabilities of beacon frames in Wi-Fi, much like traditional Wi-Fi positioning techniques, except we add in additional information that was previously inferred or guessed (through area modelling/profiling; war-driving) and which we had to contact a database to obtain. Additionally, Wi-Fi positioning only works when you have another positioning system to profile against (GPS) while logging the access points.

SPS as such maintains a passive client implementation (like GPS) and has minimal acquisition times. And since it uses the beacon frame only, a simple beacon only access point can be created without the need for a network or complex hardware/infrastructure (you only require power). One of the goals of this project is to produce a manufacturable device that does just this and is easy to configure as well as set and forget.

So how do we "exploit" the beacon frame?

SSID Encoding

An SSID contains a total of 256bits. This provides quite a large amount of data to exploit within a beacon frame of an access point. To this effect, we can actually store the physical location of the access point directly in the SSID.

Using a 32bit signed integer for the latitude and longitude gives us a worst case position of ±1.1 cm (7 digits of precision after decimal point; towards the equator, 1 degree is roughly equivalent to about 110 km).

Since we only alter the SSID of a beacon frame, we are also able to easily modify existing equipment or infrastructure (for example, if the access point supports multiple SSIDs) as we aren't altering the Wi-Fi standard itself.

Note: this has been updated here. We now only have 31 octets.


Be Careful of 0x0 String Termination Characters

"A common, albeit incorrect assumption, is that an SSID is a string of human-readable characters (such as ASCII), terminated by a NUL character (as in a C-string). SSIDs must be treated and handled as what they are a series of 0 to 32 octets, some of which may not be human-readable."[1]

While this is a problem when writing software, it can be easily accounted for; for example we need to use memcpy instead of string functions (in c).

Obviously this becomes an issue when configuring the SSID manually. So it needs to be handled correctly if augmenting existing systems. In most instances we can just use the hex character representation, but some existing access points might not support this.

Alternate Mapping

This project has a wide variety of applications and is designed to be portable. The above protocol schema is presented as a bare minimum specification to enable accurate location services. The feature flags allow us to enable alternate mapping which presents an application ID and reserved bits for custom services (such as integration into shopping mall navigation apps, indoor tour guide apps). When this alternate mapping is enabled, the latitude and longitude bits are read as centimetres instead of degrees around a point 0,0. This can be treated as the centre-point of a map or the 0,0 X/Y coordinate; it's up to the developer.

Getting Location

While Wi-Fi triangulation is quite a well-known concept nowadays (Received Signal Strength Indication etc.) it presents a problem as it's a fuzzy approach to a solution. SPS tries to remove the unknown by creating a series of fixed and known location transmission nodes (there is a once off manual planning effort to program the position of the node). With this knowledge, we are able to very accurately determine our position.

Additionally since the position of the AP is known (as it's sent in the beacon) you get almost instantaneous position calculations; this method is sort of like AGPS, but quicker and no need for data connectivity.

With regard to calculating the right altitude, it is assumed that devices on a plane remain relatively horizontal to some extent. In this sense, if a client device can see multiple access points on different floors, it can ignore these points to create a better altitude calculation (to be determined with further testing). Hopefully we can get very accurate 3D positioning accuracy with multiple nodes placed on the floor and ceiling of a room (hence the large precision for altitude).

Ideally the nodes themselves will be designed to all have the same or replicable wireless parameters for accurate distance calculations. While, this might not always be true, extra encoded information can help us normalise the output power to bring it in line with the standard nodes worked on within this project.

Obviously, the more sources the SPS client can see, the more accurate the positioning will be.

Why Encode and Not Just Store Strings?

Well you could use each character to store fixed digit string representations:

SPS:-11999999+111999999-1199999
But you are limited in the amount of information you can actually send. In this instance you can have a tag, latitude, longitude and altitude. The lat/long can be decoded with 6 decimal points of resolution (resolution of meters) only and the altitude gives you a pretty broad range in meters, you could use the BSSID to determine uniqueness of the access point (providing two are never the same). That's where it ends though, you cannot send any more information. The usefulness of encoding starts when you can add even more information that allows us to create more accurate position estimations. In this instance we have packed so much in there that there is even space for future features, alternate mapping functionality and even the ability to mask incorrect characters from the SSID (as it turns out the "+" character doesn't work in the ESP8266).

Plus, where is the fun in doing it the lazy way? This is hackaday, not potatoaday.

[1] - http://en.wikipedia.org/wiki/Service_set_%28802.11_network%29

Discussions