Positioning mobile devices

There is a lot of discussion about using mobile technology to partially automate tracing COVID-19 patients’ close contacts. I thought I’d provide a quick overview of the various ways you can locate mobile phones.

Cell-site location

This is the one everyone thinks of first. In order to route incoming voice calls and Internet packets back to your phone, the network obviously needs to know where to send them, and in the 2G/3G/4G family this is accomplished by registering the devices a given network is currently providing service to in a database called the visitor-location register (VLR). A Vodafone UK VLR covers, say, the large fraction of Vodafone UK customers who are currently in their service area, plus other carriers’ customers who are roaming with them. This all happens automatically and at enormous scale, and location data from the VLR is routinely used in criminal investigations, and by Saudi Arabia to follow its citizens around abroad for whatever nefarious purposes connected with pizza ovens and bone saws they may have.

This information only tells you which cell a device was located in. For some purposes this is useful – placing somebody on Waterloo Station or in Acacia Avenue could be very important in a criminal investigation, knowing which bits of an airport get the most footfall could be really useful to its management – but as we will see it’s not much help. For a start, the cells themselves are the product of a complicated optimization based on the pure physics of radio propagation in free space, empirical classifications of different kinds of landscape down to the species of trees, estimates of demand, and the constraints of rent, access, power supply, fixed connectivity, and planning complaints. They are not designed to help locate people and tend to be anything but nice regular hexagons.

You might also be able to find out which antenna sector on the base station and a rough idea of range. But this isn’t necessarily all that useful, for the following reasons.

The network needs to know roughly how far the device is from the base station, because it needs to measure the time it takes for a message to get to your device and back in order that transmissions intended for different users (or for the uplink and downlink directions in some networks) don’t interfere with each other. The maximum and minimum values of the time adjustment, the timing advance interval, define the maximum and minimum size of the cells. In LTE, the bounds are…a maximum cell radius of 100.15km and a minimum of 78.12m. I reckon the precision of the measurement is about 7.8m, one-tenth of the minimum cell size. (Walk through the maths here.) These numbers are not defined by the laws of radio theory but by international standardization, and some specialized systems change them, but we can leave Australian mining railway control systems out of this, much as the self-denial tortures me.

As for the antenna sector, typical sectors might be between 60 and 120 degrees wide. It should be obvious from this that trying to identify people who have been within 2 metres of each other for 15 minutes consecutively this way is hopeless. According to the Financial Times, Chinese public health authorities did try to identify contacts with network data but gave up because the numbers of false positives exhausted the force of contact tracers.

GPS

GPS, GPS, everyone loves GPS. In principle the satellite navigation system (and its relations, GLONASS, Galileo, and Beidou, which most modern mobile systems-on-chips also support) should give you positioning in three dimensions and movement in four down to sub-metre levels all over the world. It’s magic Reaganite communism. The problem with using it here is that obviously it doesn’t work so well under a roof and indoor positioning is very much part of the problem. There are ways around this, and we’ll come to them.

There is also a way to get GPS locations from mobile devices from the network side. Under the E-911 program, imposed by the US FCC and also in a European Commission directive, the network can light up the GPS on your phone and get a precision location fix, if GPS works. The point of this is that when you make an emergency call, the control centre should see you pop up on a big map like in the fillums, so things like pressing 5 on a silent 999 call so your violent spouse doesn’t notice work. Obviously it’s also hella creepy and you’d be naive to think spooks weren’t abusing it.

The problem with this is that, as anyone with a smartphone has noticed, keeping the GPS on all the time burns the battery down, and using E-911 faces some scaling problems. We’re trying to detect contacts defined as 15 consecutive minutes, so the interval between checks has to be less than 15 minutes; I think half the interval would be necessary but I’m not sure if the Shannon-Nyquist law is the right intuition here. Anyway that means pinging all the phones every 7 minutes, say 5 to take account of retries, for the 3.5bn phones on the planet…as well as the whole “massive creepy database of everyone’s location with submetre spatial and 5-minute temporal precision” thing.

Location inference

If you’re Google and you mapped all the public WiFi networks and everyone who signed up for your ads or just appearing in the gazeteer, while you’re waiting for GPS to do its thing you can have a damn good guess at location, so long as there are some of those things nearby and you don’t really mind not having defined bounds on precision at all. This is the stuff that happens if you enable “location services” as well as GPS on your phone. But we’re trying to measure intersections between 1m radius (or was it 2?) spheres around individual people, so that’s…not good enough.

Also there’s a general issue here, which is that all the systems we’ve discussed do well in answering the question “Is so-and-so near this place?” with varying degrees of precision and universality. GPS does best of all in answering the question “Where is so-and-so in a reference frame defined by the WGS-84 geoid?” and you can get where we’re going from there. But the location inference systems are really more about “What’s a good enough guess to orientate the user on the map while waiting for GPS?” and “Has the user interacted with this brand?” and this isn’t the problem we’re trying to solve.

Bluetooth Low Energy

Ironically this was invented pretty much to find out who was near which shop, but it actually serves the purpose quite a lot better than some of the others. Some devices broadcast their ID on very low-power but wide-band radio and others hear it. If you hear it you must be very close by. This tells you not much – if anything at all about absolute location, but it does tell you about proximity with high confidence and decent precision and isn’t as creepy as RRLPing the planet. That sounds like what we’re after and there’s a good reason the Singaporean health ministry, NHSX, the Apple/Google joint project, and a bunch of others have converged on solutions that use BLE plus public-key cryptography. It does have some problems – notably, as Ross Anderson points out, it’s still radio and it doesn’t care if you were on opposite sides of double glazing, and there are complicated platform restrictions in Apple iOS to stop you being creepy and weird with it. But so far it’s the best solution.

Our 5G Future

As well as activating the chemtrail nanotechnology robots in your pituitary gland, 5G has some interesting positioning features coming in this year’s Release 16 of the standards. This stuff isn’t available at scale right now so there’s not much point going into it, but 5G devices can attach to multiple cells at the same time and the timing units (subframes) used in it are much smaller (down to 1ms long, hence 10x better time-domain resolution, or much better as the subframes can be shorter in wider channels), so they can use various methods to get very precise location relative to base stations. Industrial users are really keen on this, but it’s unlikely to be relevant for this pandemic.

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.