Week 5 – Location-based computing
Mobile and Ubiquitous Computing 2020/21
Sandy Gould, School of Computer Science University of Birmingham
Overview
We’re going to learn about location-based computing this week. Location-based computing is a clear and successful exampling of efforts to inject context awareness into ubicomp systems. We will cover the following topics:
– What methods are there for understanding the location of devices?
– How do these methods work?
– How is location information used?
– What should we be worrying about with the collection of location data?
Important concepts
There are a variety of technical and non-technical concepts to get your head around this week, varying from the way that location can be sensed through to thinking about how such information can be represented in ways that are useful or interesting for people.
Global Navigation Satellite Systems
This is perhaps the kind of location-sensing technology you will be most familiar with. Colloquially known as ‘GPS’ after the American system, there are actually several similar systems run by different authorities: GPS, controlled by the USA; GLONASS, controlled by Russia; Galileo, controlled by the EU; and BeiDou, controlled by China. These systems vary in their spatial resolution from several metres (e.g., public GPS, GLONASS) down to centimetre resolution (paid-for Galileo). They all operate on the same principle, however.
As the name Global Navigation Satellite System (GNSS) implies, these systems all use satellites to sense location. Satellites operate in ‘constellations’. GPS has 31, Galileo 22, GLONASS 24, BeiDou 33. These satellites have orbits which mean that some part of the constellation is in the sky over any place on earth. Any missing satellites reduces the proportion of the constellation that can be seen and so the accuracy (or total functioning) of the system.
As the satellites orbit Earth, they transmit their current time and location. They keep time using exceptionally accurate atomic clocks (which are synchronized with other satellites in the constellation and with ground stations) and their location is precisely known and carefully controlled by operators. This information is transmitted at a frequency of ~1600MHz, which is one of the reasons why indoor signal is so poor for GPS.
A receiver gets these signals from the satellites and examines the encoded location and time information from each signal. It uses the tiny time differences in arrival time (waves from satellites further away take longer to arrive). It puts this information into some simultaneous equations… and out pops the longitude, latitude and elevation of the device. Communication is strictly one directional – the GPS system has no sense of how many devices are using it.
One of the challenges of maintaining GNSS systems is that their clocks tick more slowly than clocks on earth. This is due to relativistic effects of the kind described in Einstein’s theories. Time passes more slowly as things move faster. The satellites move very quickly as they orbit the earth, which means the clocks on them run more slowly too. GNSS have to correct for these relativistic effects or they would quickly become desynchronized! This is a fantastic example of the complexity of a sensing device being ‘abstracted away’ from developers in the way that Anind Dey has promoted in ‘Context Widgets’. As Android developers, we don’t need to worry about satellites or relativistic effects. Everything is taken care of, and we get direct access to longitude and latitude.
There are supplementary methods that devices use in addition to GNSS, including A-GPS, which uses data from cell-towers and WiFi-Assist which uses a database of the locations of WiFi hotspots.
Getting location with Android
We have previously discussed the need for context-aware systems to hide the complexity of sensors from the developers using them. As we have seen, the functioning of GNSS is an exceptionally complex feat of engineering. Thankfully, as a developer of, say, mobile applications, we do not need to understand any of these steps to work with location. This is because Android hides the complexity of getting location which make obtaining and using location very much easier.
The process of getting location in Android is mediated by Providers. Android comes with three:
– NETWORK_PROVIDER – Uses cell-towers and WiFi, no GPS involved
– PASSIVE_PROVIDER – Piggybacks on the location requests of other apps.
– GPS_PROVIDER – ‘Full Fat’ location provider that uses GPS.
Google offer a ‘Fused Location Provider’ through their Play Services tools, but these are not strictly part of Android.
To collect information from providers we need to make use of managers and listeners for the first time. Listeners allow your app to receive events from the Android operating system and execute code in response to changes. Managers provide access to those location services and allow your Listeners to subscribe to the underlying operating system events.
We will cover the exact mechanism for getting these set-up in a future labsheet. The important thing for you to understand from this lecture is that all that complexity underlying location is exposed in Android through half a dozen lines of code. That’s it: satellites whizzing around the earth, atomic clocks, the theory of relativity, all made accessible to you in a couple of lines of code. This is a really excellent demonstration of hiding complexity from programmers.
Developing useful abstractions of location
For places on planet earth, longitude and latitude and elevation (to some number of specificity) are sufficient to locate anything on the planet. But it’s not a representation that is always terribly useful. If on Canvas I listed the rooms for our classes as longitude and latitude, how would that work for you? Would it be a useful thing to tell you? Probably not. You’d want to know the name of the room and building.
There are three ways of representing location. Absolute, symbolic and relative. An absolute reference gives a precise location in a coordinate system (e.g., “You’re at 52 ̊27’03.7”N, 01 ̊55’43.1W” or “You’re at OS/GB HU396753”). A symbolic reference is some kind of abstraction of that location (e.g., 10 Downing Street, Room 110, your house). Relative positions might combine elements of both (e.g., you’re 3m from the front door of the Computer Science building). Absolute references are good for high precision but they are not very accessible to people – we do not think about location in this way. Symbolic references are very accessible to people but they lack precision (e.g., ‘please place the chair in the room Muirhead G15’ – but where in the room?). Relative references provide a degree of comprehensibility and precision (e.g., ‘please place the chair 2m from the door of Muirhead G15’). It may be necessary for systems to convert between these representations depending on context (e.g., whether they are communicating with another machine or another person). Selecting the appropriate representation (and working out how to obtain it) is critical for any location-aware service or application. Geocoders are services that help to facilitate the translation between different forms of representation; Google offers access to one as part of its Play Services.
Examples of location aware services and how they abstract location
An early example of a location-aware service was developed at Olivetti Research Cambridge: ActiveBadge. This was a system developed to help people to know where their colleagues were. The system was so called because people wore a physical badge while they were at work. This badge containted infrared transmitters (remember from Week 1 that infrared was an important inter-device communcation technology at this time), which would transmit a unique code associated with the wearer to receivers mounted on the ceilings of rooms.
This data would be relayed to a central server, so as people
moved around the buildings the central record would be
updated. This record was displayed to everyone coming into the
building at reception, where it was also used by receptionists for routing calls to the correct phone. This system collected symbolic
representations of location and stored them centrally.
One of the challenges of using GPS and GPS-like systems is that they do not always have great accuracy (although see EU Galileo) and don’t work well indoors. In this contexts, other location-sensing technologies are required. Two related technologies are ActiveBat and Cricket.
ActiveBat (Implementing a sentient
computing system—IEEE Journals &
Magazine, n.d.) makes use of tags. You have
to put one on anything your want to track. When the system wants to know the location of a tag, it sends a signal asking the tag to emit an ultrasound signal. Detectors in known locations listen out for this ultrasound emission and use the time of arrival at each of the sensors to compute the location. (If the sound reaches sensor B first, sensor A second and sensor C third, we can estimate where that is given we know the speed of sound.) The advantages of ActiveBat are that it is very precise (~3cm resolution) and that it uses minimal power because it only reports its location when it is ‘pinged’ by the radio base station. The disadvantages of ActiveBat are that: you need a tag on everything you wish to track; the system is centralised – a central server computes the location of all devices, devices cannot compute their own location. The centralisation also means that each device puts additional load on the central system responsible for computing location; so unlike GPS there is not unlimited scalability.
Cricket (Priyantha et al., 2000) attempts to solves some of the problems with ActiveBat. The Cricket, just like ActiveBat, makes use of tags. Rather than emitting ultrasound though, the Cricket receives ultrasound from emitters in known locations. The Cricket can use the arrival time of the sound from each emitter to compute its own location. This makes it a decentralized location awareness system, like GPS. Additional devices only add load to the system in as much that in sufficient quantities they may occlude the ultrasound from the emitters.
ActiveFloor (Addlesee et al., 1997) is a completly different kind of location-sensing technology. It makes use of a false floor, supported by pressure sensors. As people walk over the floor, the pattern of their toes and heels hitting the floor and the transition between them can be recorded. Maching learning techniques can be used to build individual profiles which could then be used to track people as they move around different floors. Such a system has the advantage that nothing needs to be tagged as you move through the system. However, it requires you to install new floors, it takes time to learn who individuals are, and once it has learnt this information it has the potential to be used unethically (e.g., telling workers they are too slow). It also presumes that everyone is going to be walking, which it shouldn’t do.
RADAR (Ahamed et al., 2008) is a method of allowing devices to work out their location through WiFi networks. Think about the UoB campus. The location of every unique wireless access point is known and this can be used to build a precise map. This map can be loaded onto a WiFi-capable device like a smartphone, and the relative strengths of different access points can be used by the device to work out roughly where it is. (Note, this is a decentralised system where location is computed by the device – it is not about a central system tracking the location of devices by monitoring which access points a given device associated with as it moves through an area.) The advantage of this method of location calculation is that it requires no special devices or hardware. Almost everyone carries a phone. However, the resolution of this system isn’t great (3-6m) and the map of a given area has to be rebuilt whenever there are any changes to the arrangement of the WiFi access points.
There are other ways of monitoring location, from looking at changes in inductance of powerlines, to sensing pressure in ventilation (HVAC) systems as doors open and close, to using cameras like Microsoft’s Kinect to identify things as they move through a space. We’ve already seen some novel ways of sensing location and others that repurpose existing hardware. The most important thing is to think about the context: what kind of hardware is going to be available and what kind of accuracy is required for a given application?
Location measurement error
There is no completely reliable way to measure location. There is noise in all ways to measure location. For GPS, signals can be slowed down in the ionosphere or reflected by big buildings (multipath errors). We’ve seen how other technologies can be noisy in their output, too. How can we deal with this noise when the question of which side of the road you’re on can be critical for navigation?
Let’s think again about seamfulness. How can we apply those four ways (pessimistic, optimistic, cautious, opportunistic) of dealing with seams in location services? We already this in the way things like Google Maps works. When signal is weak, it will make an estimate of your location, showing you a coloured boundary around the point to indicate that it thinks you could be anywhere in the shaded area. I would describe this as a cautious approach to noise in the measurement of location. Rather than just claim it knows where you are (optimistic) or just telling you location is unavailable (pessimistic) it shows what it thinks to be the truth, but qualifies this with the margin for noise.
What could we do that might fit in with the ‘opportunistic’ approach to dealing with seams? Benford et al. (2003) developed an early location-aware game called CYSMN (Can You See Me Now?) It had groups of people trying to chase down someone in an urban area. All players carried devices that recorded their location. When a device from a ‘chaser’ got close enough to a ‘runner’, then the ‘runner’ would be deemed to have been caught. There were technical glitches, though: this was in the early days of mobile devices with GPS and the system would frequently get confused about where a given device was. Sometimes a ‘chaser’ couldn’t catch a ‘runner’ even if they were standing next to each other. Benford et al. found that people would adapt to this unreliability, seeking out areas where signal was reliable in order to ambush
runners. Benford et al.’s conclusion was in the spirit of seamfulness and they recommended either completely hiding uncertainty about location from players (i.e., pretend everything is perfect) or fully embrace the uncertainty to provide new gameplay modes (i.e., do something opportunistic).
Using location in services
What kind of things can we actually do with this location data? There are lots – you will have used many of them yourselves. Let’s look at a couple of specific examples here. First, we have Picalilly, which a location-based photo sharing application (Vyas et al., 2013). In this application, an event area would be defined. Only people from within this area would be able to contribute photos. Anyone in a group could view photos posted to the group whether they were at the event or not. In this way, the stream of photos from the group stay focused on a particular event in a particular area.
PlaceMail (Ludford et al., 2006) was another effort to use location services to improve an application. The app supported location-aware reminders, for example “don’t forget carrots when you’re at the shop.” Ludford et al. found that it wasn’t sufficient just to have geo-fences – defined areas within which a reminder would be sent. It is also necessary to look at where someone is now, and the speed and direction they are travelling in. There’s no point a reminder to pick something up on the way back from the shop firing as you drive over a particular section of road on the way too the shop. By the time you return you might forget. We need to think about location as part of a bigger context-aware system.
Finally, we see a lot of location-based tools being used for marketing, both in physical-world advertising, but also in advertising online or mixed-reality contexts which have aspects of the physical and digital worlds. The goal of these adverts is to provide you with more contextually aware adverts (e.g., advertising shops you’re close to), but, as we know, there is more to context awareness than this – there’s also the time of day, the weather etc. This form of advertising does raise privacy concerns, though, and that’s the topic we’ll finish on.
Privacy concerns for location services
As we have already considered, there are two ways that location can be measured: client- based measures and centralised measures. Client-based measures are privacy preserving because location is calculated on the device using the information, rather than location being computed (and therefore potentially recorded) on a central server. GPS is an example of a client-based was of measuring location even if on many new smartphones, this data is returned to a central authority (e.g., for advertising). Where a central authority computes location (e.g., ActiveBat, ActiveBadge), then privacy is necessarily compromised. Having to compute location in a central location means this information could be stored or potentially compromised.
We also have to recognise that location data can leak critical information. This might be the locations of endangered species (Bowser et al., 2017) or it could be the location of secret military bases being exposed my military personal using fitness apps to log their training runs. We will talk more about the issues here in our lecture on privacy and security in mobile and ubiquitous computing. The important thing to remember from this lecture is that different technologies allow location to be computed more or less privacy preserving ways. We should be mindful of this when we’re developing systems which make use of location.
References
Addlesee, M. D., Jones, A., Livesey, F., & Samaria, F. (1997). The ORL active floor [sensor system]. IEEE Personal Communications, 4(5), 35–41. https://doi.org/10.1109/98.626980
Ahamed, S. I., Talukder, N., & Monjur, M. (2008). WiFi Radar: Design and Implementation of an Infrastructure-less Location Tracking System for Pervasive Environment. 2008 32nd Annual IEEE International Computer Software and Applications Conference, 335–338. https://doi.org/10.1109/COMPSAC.2008.127
Benford, S., Anastasi, R., Flintham, M., Greenhalgh, C., Tandavanitj, N., Adams, M., & Row-Farr, J. (2003). Coping with uncertainty in a location-based game. IEEE Pervasive Computing, 2(3), 34–41. https://doi.org/10.1109/MPRV.2003.1228525
Bowser, A., Shilton, K., Preece, J., & Warrick, E. (2017). Accounting for Privacy in Citizen Science: Ethical Research in a Context of Openness. Proceedings of the 2017 ACM Conference on Computer Supported Cooperative Work and Social Computing, 2124– 2136. https://doi.org/10.1145/2998181.2998305
Implementing a sentient computing system—IEEE Journals & Magazine. (n.d.). Retrieved 3 February 2020, from https://ieeexplore.ieee.org/document/940013
Ludford, P. J., Frankowski, D., Reily, K., Wilms, K., & Terveen, L. (2006). Because I Carry My Cell Phone Anyway: Functional Location-based Reminder Applications. Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, 889–898. https://doi.org/10.1145/1124772.1124903
Priyantha, N. B., Chakraborty, A., & Balakrishnan, H. (2000). The Cricket location-support system. Proceedings of the 6th Annual International Conference on Mobile Computing and Networking, 32–43. https://doi.org/10.1145/345910.345917
Vyas, D., Keijl, E., Akker, R. op den, Nijholt, A., & van der Veer, G. C. (2013). Geo-locked Photo Sharing on Mobile Devices. CHI ’13 Extended Abstracts on Human Factors in Computing Systems, 1407–1412. https://doi.org/10.1145/2468356.2468607