As location-based products and applications are becoming a staple of people’s everyday activities, the expectation to have a favourite map or search app constantly on hand regardless of the strength or availability of a GPS signal has also become a given. Everyone wants to have access to relevant and useful information at any point in time even if their mobile device cannot receive satellite signal.
To make sure the users of our location-based services and apps can have the information they need when and where they need it, we have created Yandex.Locator, our own GPS-independent method for pinpointing users’ locations. Instead of relying on GPS to provide location-based information on mobile devices, it uses Wi-Fi points and cellular networks.
Implemented in our turn-by-turn navigation app Yandex.Navigator, this technology removes the need to enter the starting point of a journey and allows building a driving route even in an enclosed parking lot where satellite signal is weak or unavailable. The Yandex.Locator technology is also helpful when choosing a film on the Yandex.Afisha movie guide or a product on the Yandex.Market comparison shopping system. The technology’s location-sniffing prowess allows to show the user films running in cinemas or products available in shops in their immediate neighbourhood on top of other search results. Yandex.Locator can also help to find the nearest ATMs and cafes – even when you’re on the metro tens of metres below the ground surface.
The precision of a user’s location determined by pinpointing the nearest GSM towers, Wi-Fi networks and even IP addresses is inferior to GPS, but in combination these methods give acceptable results.
A network database for a GPS-independent location service can either be purchased from a specialist company or created from scratch by logging networks in specific areas and then continually updating this information (costly and time-consuming).
Alternatively, such database can be built using the data generated by users of a popular mobile platform, such as iOS or Andriod, (luxury available to few).
However, there is another, probably the best and the most cost-effective way – utilise the data collected as a by-product from users of a popular mobile app. And this is exactly what we have done.
Network database
By the time the idea of Yandex.Locator started taking shape, hundreds of thousands of people on the streets with the Yandex.Maps app on their mobile phones were already sending us their GPS coordinates to help us build the picture of current traffic conditions – a traffic layer on Yandex.Maps. We figured that together with this information, the app could also send us the information about which GSM station is serving a phone at particular coordinates, and which Wi-Fi networks are in its range (without actually connecting to them, of course).
Taking part in such crowdsourcing requires no special effort on a user’s part – all they need to do is simply use the app the way they have always had. As with location coordinates, data about nearby Wi-Fi networks and GSM stations are anonymised. The volume of the network data is not large, so the phone’s battery life doesn’t suffer.
The Yandex.Maps mobile users help us and help each other. Those with GPS receivers on their phones register their exact location and transmit this information to Yandex. Others, who don’t have GPS modules, transmit a list of Wi-Fi networks that they are picking up at a given moment, and in response they receive their approximate location on a map.
Migrating networks
Practice shows that GSM station identifiers can migrate (while the stations themselves remain physically stationary, of course), and Wi-Fi routers also have a tendency to move about together with their owners. Overcoming the problems created by all this movement took no small amount of ingenuity.
When a user sends us a request for location information, we also receive the data about which GSM stations or Wi-Fi points their device registers. If the list of networks includes one that was previously recorded as being in a different part of the city, Yandex.Locator calculates how many signals have been picked up from this network in each place and how recently. Every dense concentration of such signals is called a “cloud”. Clouds with a greater number of fresh signals are naturally the ones whose information we trust most.
Improving precision
… by GSM networks
In the past, location services only received information about one base station, although mobile devices usually see several. That changed with the arrival of Android, which has enabled the apps to see all base stations in range (except when the device is on 3G, which only allows one base station to be recognised). This means locations can now be determined with more precision – not just by one cloud, but by the combined power of several. And, as it turns out, the approach used with one cloud also works for a whole bunch of them. The radius is calculated by the standard deviation of the combined cloud signals, and the centre is taken as the arithmetic average of their coordinates.
... by Wi-Fi networks
When a smartphone is in range of several Wi-Fi networks, it can relay not just a list of networks but also the strength of each one’s signal. We use this signal strength as one of the tools for pinpointing the centre of the zone where the user is located. We started attaching metaphorical “springs” to the centre of each observed cloud – the tighter the spring, the stronger the signal – then joined the free ends. The point where the springs equilibrate is the corrected centre of the cloud.
As Wi-Fi networks continue to expand, and the amount of data produced by the growing number of the users of our location-based apps continues to increase, so does the precision with which locations are determined.
However, the location precision is not unlimited. If a telephone detects just one GSM tower, the minimal radius for the user’s location is several hundred metres in a city, or several kilometres outside the city. If a telephone detects several cell towers, the centre point of their location can be determined with more precision, but the radius is unlikely to be reduced. And, even if a user’s location is confidently determined by a Wi-Fi network signal, the minimal radius is currently 10 metres.
Yandex.Locator has been implemented in Yandex.Maps, Yandex.Market, Yandex.Afisha and Yandex.Navigator available to users in Russia, Ukraine, Belarus and Kazakhstan, with Yandex.Maps and Yandex.Afisha also offered to mobile users in Turkey. The Yandex.Locator also helps to offer location-based search suggestions, weather forecasts and traffic reports in Yandex.Browser.
The technology is also available for public use via a free API (in Russian).