Computer Laboratory > Teaching > Course material 2008–09 > Additional Topics


Additional Topics

Principal lecturer: Prof Andy Hopper
Taken by: Part II
Past exam questions

Course Details

The lectures this year are 12:00-13:00 in Lecture Theatre 2 of the CL. Note that time of 10:00-11:00 as advertised in the reporter is incorrect (it had to be moved due to a clash of lecturers!). The schedule is as follows:

Friday 24/04 Ubiquitous Computing (Robert Harle)
Monday 27/04 RFID (Robert Harle)
Wednesday 29/04 GPS (Alan Jones)
Friday 01/05 Location Determination Part I (Robert Harle)
Monday 04/05 Location Determination Part II (Robert Harle)
Wednesday 06/05Cryptography (Frank Stajano)
Friday 08/05 Security for UbiComp (Frank Stajano)
Monday 11/05 Security for RFID (Frank Stajano)
Wednesday 13/05 Thin Client Computing Part I (Andy Harter)
Friday 15/05 Computing for the Future of the Planet (Andy Hopper)
Monday 18/05 Sustainable Energy (David Mackay)
Wednesday 20/05 Thin Client Computing Part II (Andy Harter)

Electronic copies of notes, links and other material will appear here as the lectures are completed.

Lecture 1: Ubiquitous Computing

What you need to know: The ubicomp vision in 1988; Context-aware computing; Example projects and lessons learnt (active badge, PARC, Intel Personal Server, Wearable Computing, Sentient Computing); Ubicomp today.

Lecture Notes: PDF


Yesterday’s tomorrows: notes on ubiquitous computing’s dominant vision. Bell and Dourish. PDF

The Computer for the 21st Century. Weiser. PDF

A distributed Location System for the Active Office. Harter and Hopper. PDF

The Anatomy of a Context-Aware Application. Harter, Hopper, Steggles, Ward and Webster. PDF

The Royal Society Clifford Paterson Lecture, 1999 - Sentient Computing. Andy Hopper. PDF

The PARCTAB Ubiquitous Computing Experiment. Want, Schilit, Adams, Gold, Petersen, Goldberg, Ellis and Weiser. Link.


1A. Contrast mobile computing with ubiquitous computing. [5]

1B. It has been suggested that the Apple iPhone was the first major ubicomp device. What are the properties of the iPhone that resulted in this description? Discuss how well the iPhone fits the original vision for Ubicomp. [10]

1C. Describe the "programming with space" metaphor that enabled location-aware computing in the Sentient Computing platform. [5]

1D. The Intel Personal Server project proposed a wireless device that would connect to public infrastructure to provide input and output. Discuss the technical, commercial and social issues associated with such a device. [10]

1E. Weiser's original vision for ubicomp has not been met within the timescale he suggested (20 years). Suggest why not. [8]

Lecture 2: RFID

What you need to know: Types of RFID; Active vs Passive; Properties and applications for close-coupled, remote-coupled and long range RFID; Principles of back-scattering; Basics of EPC; Anti-collision protocols for LR tags; Technical, real-world issues with LR tags

Lecture Notes: PDF


RFID Handbook. Klaus Finkenzeller Available in libraries. Some chapters online


2A. Give two example applications for long range RFID tags. One application should be suitable for active LR tags, the other for passive. [4]

2B. The media regularly attack the security and privacy associated with RFID tags. And yet the banks are all turning to RFID-based contactless payment cards. Why do they not share the same security issues?

2C. Why are longer range passive RFID tags associated with higher frequencies of operation?

2D. Why have we yet to see automatic checkouts where we push our trolley through the doors and have everything charged correctly? (It is not because products don't have RFID tags at the moment - these could be added very quickly to products, if desired).

2E. How do probabilistic anti-collision schemes work? Suggest applications where they might be more suitable than deterministic schemes.

2F. Write out the rounds required to identify the following tags using a binary search: {11010, 01010, 00101, 11000}

2G. An RFID system contains N tags and uses a simple ALOHA anti-collision protocol. Tags are constrained only to transmit a packet with a probability of p within each time period T.

(a) Write down the expected number of transmissions in time T and hence an expression for P(k), the probability that there will be k transmissions in time T

(b) Give an expression in terms of T for the vulnerable period (this is the length of time during which a transmitting packet will collide with a specific packet). What would this period be for slotted ALOHA?

(c) From these answers, compute the probability that a given tag transmission will not collide and hence the expected throughput (number of tags per time T).

Lecture 3: GPS

What you need to know: GPS components; Basic operating principles; Error sources; DGPS; Selective availability; The notion of Gold codes and how they are used.


Recommended Site: Here

More detailed information (including offical docs): Here


3A. Why do GPS satellites require atomic clocks? Why doesn't it matter that GPS handsets don't have an accurate absolute time estimate? [6]

3B. Explain the principles of D-GPS. [5]

3C. What are the important properties of Gold codes that make them useful for GPS? How is it that a GPS signal so weak it is below the noise threshold at the receiver is still useful?

3D. Although intended for positioning, GPS is commonly used to accurately synchronise clocks to a global reference time. Explain how a handset on the surface of the Earth can compute an accurate absolute time from a GPS satellite. Estimate the timing error that might be expected at the handset immediately after synchronization to a satellite.

Lectures 4 and 5: Location, Location, Location

What you need to know: The principles of AoA, ToA and TDOA location; Examples systems of each; Basics of Inertial navigation; Fingerprinting.

Lecture Notes: PDF


4A. Briefly explain why the Bluetooth inquiry (a.k.a. discovery) process takes so long (10.24s) and why this limits its use as a proximity-based tracking system.

4B. Compare and contrast location systems that position a mobile transmitter (e.g. the Bat system, U-TDOA) with those that position a mobile receiver (e.g. GPS, Cricket). [6]

4C. Explain why UWB systems can achieve better positioning accuracy than more traditional radio location systems. [5]

4D. A transmitter located at (15,20) is surrounded by synchronised receivers: A at (0,50), B at (5,0), C at (30,30). For this setup, give the equations of the vectors, circles or hyperbolae associated with the i) AoA ii) TOA and iii) TDOA location techniques. Assume all measurements have no noise (and are therefore perfect) and receivers are perfectly synchronized. [8]

4E. Imagine that your GPS signal is being jammed by an enemy transmitter. In order to unjam it, you need to first locate the source. Describe how you would do this. [Remember that you can't use GPS to position your receivers!]

4F. Explain why the Ubisense system makes use of UWB radio rather than, say, the usual 2.4GHz ISM radio band. Why do we not need to use UWB signals when positioning outdoors?

4G. What factors might you need to take into account if you were creating a WiFi radio map?

4H. Discuss the advantages and disadvantages of using radio fingerprints for positioning.

4I. The Nintendo Wiimote was apparently intended to be based purely on inertial sensors. Explain why inertial sensors alone were insufficient and describe briefly the solution implemented by Nintendo.

4J. What do you need to specify in order to create a useful tracking system from an inertial measurement unit?

4K. Imagine that you are tasked with designing an iPhone-like device that must be able to position itself at all times. Discuss the solutions you would use and the accuracies you might expect indoors and out.

Lecture 6: Cryptography

What you need to know: basics of visual cryptography; Cocaine auction; Romantic cryptography

Lecture Notes: Here


Exercises can be found in the notes

Lecture 7: Security for Ubiquitous Computing

What you need to know: basics of visual cryptography; Cocaine auction; Romantic cryptography

Lecture Notes: Here


Exercises can be found in the notes

Lecture 8: Security for RFID

What you need to know: Limitations of RFID as a secure ID mechanism; Schemes to improve RFID security and privacy

Lecture Notes: Here

Lecture 9: Thin Client Systems Part I

What you need to know: Definition of thin client

Lecture Notes: Here


9A. Give three advantages and three disadvantags of thin client systems.

9B. How did advances in memory technology lead to better graphics on computer screens in the 1980s?

9C. Describe the different roaches used to remote bitmap graphics by VNC, X and RDP.

Lecture 10: Computing for the Future of the Planet

What you need to know: Ways in which technology might create a sustainable future.

Lecture Notes: Coming soon


10A. The lectures identified four ways in which computing might be applied to sustainability issues. Describe them.

10B. Discuss three technical and three political/social challenges to "googling space-time".

10C. Is the vision for ubicomp (many devices, always on, interacting) fundamentally incompatible with a sustainable future? Illustrate your answer with examples.

Lecture 11: Sustainable Energy

What you need to know: The scale of the energy crisis; Sustainable sources of energy

Lecture Notes: You can find Professor Mackay's entire book online: The talks section also contains the slides used in the lecture.


11A. Discuss the extent to which modern computing technology is responsible for the current power demands of the UK.

Lecture 12: Thin Client Systems Part II

What you need to know:

Lecture Notes: Here


12A. In the lecture about Ubiquitous computing, a scenario involving a user walking up to a public display and 'comandeeringing' it as an output device was presented. Discuss how remote bitmap graphics software (such as RDP and VNC) might act as an enabler for this application.

12B. Compare and contrast the RDP and VNC protocols. [6]

12C. A student implements a simple remote graphics protocol by regularly snapshotting the screen image and transmitting it over the network. Identify four optimisations that would significantly boost the performance of this protocol.

12D. Compare RDP, VNC and X for remote graphics over i) a LAN ii) a typical ADSL connection iii) a 3G connection.

12E. What is meant by 'cloud computing'? [4]