Welcome to another installment of Skyhook Under the Hood: Geopositioning more than 1 Billion Wi-Fi access points! Our previous posts have outlined how to determine the location of a Wi-Fi access point and how to gather on-device signals and information. Today, we’ll be walking through how to get signals to server, or get beacon locations to a device.
Step 1: Determine the location of a Wi-Fi access point
Step 2: Gather on-device signals and information
Step 3: Get signals to server or get beacon locations to device
Okay, so we have the location of a bunch of Wi-Fi access points, and we’ve gathered signal information from the device. We're now ready to compute the location of the device, right?
Well, not quite. You have the signals from the device, you have the beacon locations on the server (see Step 1 and Step 2), but, you need both coming together to compute a location. Skyhook uses two methods in our hybrid positioning system. Both of these are active (but tunable) when taking advantage of our SDKs.
The first method is to simply package up all of the signal data and toss it at our server. Now, this is nice and simple(ish) and provides a very versatile mechanism for determining device locations. This service is a simple RESTful service that takes the signals and computes the location of the device (see Step 4 to follow).
The second method is to provide enough information to the device for the device to compute its own location. We handle this method by providing another interface that allows the client to request ‘tiles’ of beacon locations. This allows the device to cache beacon locations that are near it, providing temporary and locally relevant information such that local resolution is possible without requiring a network connection or round trip. As the device moves around it refreshes its cache as needed, but can use the same methods described below (as well as some additional, on-device only capabilities) to compute the location of the device.
Step 4: Compute location of device
Phew, finally…we are now ready to compute the location of a device! We have signals, we have beacon locations…now just put them together and voila!
Note that we’ve built our system to try to obtain the optimum user experience while minimizing resource consumption and maintaining underlying privacy and security of the system. This is a non-trivial balance of conflicting requirements which we have balanced but which can be adjusted based on the customer use case.
To compute a single location, the process is very similar to what was explained in step #1 only in reverse. To compute the location of a device via Wi-Fi signals, we first take a look at all of the Wi-Fi signals that were captured. For each access point that is in the signal capture, we will use the MAC address to look up the location of that Wi-Fi access point in our database or the local cache. Once we have the set of MAC addresses, their locations, and their confidence factors (as briefly describe in #1 above), we plug this information into our algorithm using a weighted nonlinear least squares fitting method. You may have seen this process described as triangulation, trilateration, or multilateration. In essence we use our confidence factors to compute a weighted centroid which indicates the most probable location based on the signal information.
In the end, what is returned is an accurate location with an error estimate providing the app developers and the end users to make better use of the location for their particular use case.
This is a multi-step process which will also take into account additional information that may be available. Next week, we’ll walk through the final step - how to combine all this newly gathered signal information together.
