CS GZ06/M038: Mobile and Adaptive Systems


Steve Hailes s dot hailes at cs dot ucl dot ac dot uk 7.19 MPEB
Brad Karp 7.05 MPEB
Kyle Jamieson 7.02 MPEB

Meeting Times

UCL Term 2: 12th January, 2009 - 13th February, 2009

  • Monday 9 AM - 11 AM, MPEB 1.20
  • Monday 3 PM - 4 PM, Darwin Biochemistry LT
  • Tuesday 1 PM - 2 PM, MPEB 1.20
  • Wednesday 9 AM - 10 AM, MPEB 1.20
  • Friday noon - 1 PM, MPEB 1.02

  • Course Description and Detailed Course Calendar

    GZ06/M038 is a graduate class in which students read and discuss 15-20 recent research papers in the area of wireless, mobile, and peer-to-peer systems. The mix of these topic areas may change from year to year. There are three chief aims in reading and discussing these papers:

  • To gain experience in thinking critically about research papers: learning to question authors' assumptions, the importance of a research problem, and the degree to which an evaluation convinces the reader of a research idea's worth.
  • To expose students to some of the most recent trends in thinking in hot areas of networked systems research.
  • To give students important background on the state of the art in wireless systems that will serve as a foundation for students' own research.
  • Each paper appears in the calendar below on the day when it will be covered in lecture. Students must read papers before they are covered.

    To motivate students to read papers before lecture, and to help students ensure they are digesting the material in the papers, most papers in the latter two-thirds of the class will be accompanied by a short question on the paper's content, posted on the class calendar below. Students are required to write and hand in a one-pager for each such question: a short, 200-500 word answer to the question. One-pagers are due at the start of the lecture when the corresponding paper is discussed. These short answers will be assessed as described further below (see "One-Pagers").

    N.B. that all assigned readings (including those presented by students at the end of the course) are examinable.

    Monday Tuesday Wednesday Friday

    12th Jan

    9 AM: Hailes


    3 PM: Hailes


    13th Jan


    Introduction to Sensor Nets

    Reading: SensorNet survey


    14th Jan


    Security for sensor nodes

    Reading: SPINS

    Reading: Key distribution

    16th Jan


    Security: DoS, Trust

    Reading: DoS


    19th Jan

    9 AM: Hailes

    Reading: Simulation1

    Reading: Simulation2

    3 PM: Karp
    Geographic Routing

    Lecture Notes:
    Reading Critically, GPSR

    Reading: GPSR

    20th Jan

    Geographic Routing (cont'd)

    Supplemental Reading (non-examinable): CLDP

    21st Jan

    Geographic Routing (cont'd)

    23rd Jan

    Wireless LAN MACs

    Lecture Notes: MACAW and Wireless MACs

    Reading: MACAW


    26th Jan

    9 AM: Karp
    Mesh Networks

    Lecture Notes: Roofnet

    Reading: Roofnet


    3 PM: Karp
    Interference Avoidance and Control

    Lecture Notes: VWID

    Reading: I/F Avoidance and Control

    27th Jan

    Distributed Hash Tables (DHTs)

    Lecture Notes: DHTs and Chord

    Reading: Chord


    28th Jan

    Bitrate Adaptation

    Lecture Notes: Intro to the PHY and SampleRate

    Reading: SampleRate (see erratum)


    30th Jan

    Radio Link Diversity

    Lecture Notes: SampleRate wrap-up and Radio Link Diversity

    Reading: MRD


    2nd Feb

    (cancelled due to inclement weather)

    3rd Feb

    Opportunistic Routing

    Lecture Notes: MRD wrap-up and ExOR

    Reading: ExOR (see erratum)


    4th Feb

    Channel Width Adaptation

    Lecture Notes: ExOR wrap-up and SampleWidth

    Reading: SampleWidth


    6th Feb

    SampleWidth (cont'd)

    Reading: Taking the Sting out of Carrier Sense

    Lecture Notes: SampleWidth wrap-up and SIC lead-in


    9th Feb

    9 AM:

    Group C (Bahuguna, Deresse, Kyomo, Nopphakhun)
    MAC for Long-Distance 802.11 Links

    Presentation slides

    Reading: JazzyMAC

    10 AM:

    Group B (Bao, Olutoni, Ugochukwu-Paul, Zhushi)
    Indoor Localization using 802.11

    Presentation slides

    Reading: RADAR

    3 PM:

    Group F (Nasralla, Noulas, Theocharides, Wiland)
    Congestion Control for Sensor Networks

    Presentation slides

    Reading: IFRC

    10th Feb

    Group E (Ahmad, Bhatt, Kheirkhah, Kral, Sundo)
    Effects of Interference on 802.11

    Presentation slides

    Reading: 802.11 Interference

    11th Feb

    Group A (Dong, Meng, Mishra, Sun)
    Indoor Localization using Ultrasound and RF

    Presentation slides

    Reading: Cricket

    12th Feb
    9 AM: Jamieson

    Interference cancellation

    Lecture Notes: Interference cancellation

    13th Feb

    9 AM: Jamieson
    The Viterbi Algorithm

    Lecture notes: The Viterbi algorithm

    Reading: The Viterbi Algorithm
    (see notes, requires UCL login)

    12 Noon:

    Group D (Michaelides, Raja, Suraweera, Wijayapala)
    802.11 Connectivity for Vehicles

    Presentation slides

    Reading: ViFi

    Assigned Readings (to be covered in lectures and discussions)

    Steve Hailes:

  • General introduction to sensornets:
    Akyildiz, I., Su, W., Sankarasubramaniam, Y., and Cayirci, E., A survey on sensor networks, in IEEE Commun. Mag., 40 (8), (2002), 102--114. html
  • Security in mote-based sensornets:
    Perrig, A., Szewczyk, R., Wen, V., Culler, D., and Tygar, J. D., SPINS: Security protocols for sensor networks, in Proceedings of MobiCom 2001. html
  • More security for sensornets:
    Chan, H., Perrig, A., and Song, D., Random Key Predistribution Schemes for Sensor Networks, in Proc. of the IEEE Symposium on Security and Privacy (Oakland 2003). html
  • DoS in sensornet context:
    Wood, A.D. and Stankovic, J.A., Denial of Service in Sensor Networks, in IEEE Computer, Oct 2002. html
  • Simulation and its problems:
    Cavin, D., Sasson, Y., and Schiper, A., On the accuracy of MANET simulators, in Proceedings of the ACM Workshop on Principles of Mobile Computing (POMC '02), Oct. 2002, pp. 38--43. html
  • D. Kotz, C. Newport, R. Gray, J. Liu, Y. Yuan, and C. Elliott, "Experimental evaluation of wireless simulation assumptions," in Int'l Workshop Modeling Analysis and Simulation of Wireless and Mobile Systems (MSWiM 04). ACM Press, New York, Oct. 2004. html
  • Brad Karp:

  • Geographic routing (scalable routing in multi-hop wireless networks):
    Karp, B. and Kung, H.T., GPSR: Greedy Perimeter Stateless Routing for Wireless Networks, in Proceedings of the Sixth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom 2000), Boston, MA, August, 2000, pp. 243-254. .ps.gz
  • Geographic routing, revisited (on arbitrary topologies):
    Kim, Y.-J., Govindan, R., Karp, B., and Shenker, S., Geographic Routing Made Practical, in the Proceedings of the Second USENIX/ACM Symposium on Networked System Design and Implementation (NSDI 2005), Boston, MA, May, 2005. pdf
  • The "classic" wireless MAC layer:
    Bharghavan, V., Demers, A., Shenker, S., and Zhang, L., MACAW: A Media Access Protocol for Wireless LANs, in ACM SIGCOMM 1994. pdf
  • A 40-node, fixed, outdoor 802.11b mesh network:
    Bicket, J., Aguayo, D., Biswas, S., and Morris, R., Architecture and Evaluation of an Unplanned 802.11b Mesh Network, in MobiCom 2005, August 2005. pdf
  • Assigning custom-width channels to transmitters on long-distance, outdoor 802.11 links to mitigate interference:
    Gummadi, R., Patra, R., Balakrishnan, H., and Brewer, E., Interference Avoidance and Control, in ACM HotNets 2008. pdf
  • One of the original Distributed Hash Table (DHT) overlay proposals:
    Stoica, I., Morris, R., Karger, D., Kaashoek, M.F., and Balakrishnan, H., Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications, in ACM SIGCOMM 2001, San Diego, CA, USA, August 2001, pp. 149-160. pdf
  • Kyle Jamieson:

  • A widely-used wireless 802.11 bitrate adaptation scheme:
    Bicket, J. Bitrate Selection in Wireless Networks. MIT MS Thesis, 2005. pdf
  • Exploiting the diversity of 802.11 wireless links in a setting with multiple APs:
    Miu, A., Balakrishnan, H., and Koksal, C. E. Improving Loss Resilience wih Multi-Radio Diversity in Wireless Networks. In ACM MobiCom, Cologne, Germany, 2005. pdf
  • Taking advantage of opportunistic receptions to improve traffic routing in a wireless mesh:
    Biswas, S., Morris, R. Opportunistic Routing in Multi-Hop Wireless Networks. In ACM SIGCOMM, Philadelphia, PA, 2005. pdf
  • Adapting channel width increases throughput, saves power:
    Chandra, R., Mahajan, R., Moscibroda, T., Raghavendra, R, and Bahl, V. A Case for Adapting Channel Width in Wireless Networks. In ACM SIGCOMM, Seattle, WA, 2007. pdf
  • Canceling interfering Zigbee/802.11 transmissions using software radio:
    Halperin, D., Anderson, T., and Wetherall, D. Taking the Sting out of Carrier Sense: Interference Cancellation for Wireless LANs. In ACM MobiCom, San Francisco, CA, 2008. pdf
  • A tutorial paper treating a ubiquitous algorithm for decoding error correcting codes. The Viterbi algorithm finds numerous applications in cellular, wireless LAN, dial-up modems, satellite and deep-space communications, and other areas:
    Forney, D. The Viterbi Algorithm. Proceedings of the IEEE, vol. 61, no. 3, pp. 268-278, March 1973. IEEE Xplore (requires UCL login)

  • Assessment

    There are three components in the marking scheme for GZ06/M038, each of which contributes the below percentage to your final mark:

  • One-pager answers (5%): All one-pagers you turn in are of equal weight; your average mark on them will contribute 5% of the overall total marks for GZ06/M038.
  • Paper presentation (10%): As described below, students form groups, each group will together present one paper from the below list of papers offered by the course instructors, and each student in each group will write a short evaluation of the work in the paper his or her group presents. A detailed breakdown of the marking of presentations is offered further below. The mark for your presentation and writeup will contribute 10% of the overall total marks for GZ06/M038.
  • Final exam (85%): There is a written final exam during the Easter exam period that constitutes 85% of your overall mark for GZ06/M038.

  • One-Pagers

    To encourage students to keep up with the reading for the class, and thus ensure fruitful in-lecture discussions, we will assign one-pagers for the papers in the last two-thirds of the class. 48 hours before each lecture, we will post on the above calendar a question about the reading assigned for that lecture. Your answer should be in the form of a short essay of between 200-400 words.

    You must turn in your one-pager at the start of the lecture for which a paper has been assigned.

    One-pagers will be assessed on a simple scale between 0 and 2 marks:

  • 0 marks: no one-pager turned in at the start of lecture, or answer turned in cannot be seen to respond meaningfully to question asked
  • 1 mark: one-pager turned in at the start of lecture, and answer addresses the question asked
  • 2 marks: one-pager turned in at the start of lecture, and answer precisely, correctly, and thoroughly addresses the question asked

  • Presentation Papers (to be presented by student groups)

    N.B. that papers will be marked in red as groups claim them.

    Steve Hailes:

  • Performance evaluation of ad hoc routing
    J. Broch, D. A. Maltz, D. B. Johnson, Y. C. Hu, and J. Jetcheva. A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols. In Proc. of the ACM/IEEE MobiCom, October 1998. html
  • Security in mobile networks:
    Kong, J., Zerfos, P., Luo, H., and Lu, S., Providing Robust and Ubiquitous Security Support for Wireless Mobile Networks, in ICNP 2001. html
  • Emulation for mobile systems:
    Noble, B., Satyanarayanan, M., Nguyen, G., and Katz, R., Trace-Based Mobile Network Emulation, in ACM SIGCOMM 1997. html
  • Secure routing for ad hoc networks
    Y.-C. Hu, A. Perrig, and D. B. Johnson, Ariadne: A secure on-demand routing protocol for ad hoc networks, in The 8th ACM International Conference on Mobile Computing and Networking, September 2002. html
  • Trust management
    Boukerche, A. and Li, X., An agent-based trust and reputation management scheme for wireless sensor networks, in Global Telecommunications Conference, 2005 (GLOBECOM '05). pdf
  • Brad Karp:

  • The nature of congestion in sensornets, and how to control it:
    Rangwala, S., Gummadi, R., Govindan, R., and Psounis, K., Interference-Aware Fair Rate Control in Wireless Sensor Networks, in SenSys 2006.
  • Synopsis Diffusion: how to forward sensor readings over multiple paths to a base station for robustness, without duplicating sensed values (!):
    Nath, S., Synopsis Diffusion for Robust Aggregation in Sensor Networks, in SenSys 2004. pdf
  • JazzyMAC: a MAC approach for building long-distance 802.11 links for Internet connectivity in rural areas:
    Nedevschi, S., Patra, R., Surana, S., Ratnasamy, S., Subramanian, L., and Brewer, E., An Adaptive, High Performance MAC for Long-Distance Multihop Wireless Networks, in ACM/IEEE MobiCom 2008.
  • Engineering 802.11 networks that offer improved TCP throughput and VoIP connectivity for clients in moving vehicles:
    Balasubramanian, A., Mahajan, R., Venkataramani, A., Levine, B., and Zahorjan, J., Interactive WiFi Connectivity for Moving Vehicles, in ACM SIGCOMM 2008.
  • Measurement study of how interference from Zigbee (mote-like radio) and 2.4 GHz cordless phone interference affect 802.11 performance:
    Gummadi, R., Wetherall, D., Greenstein, B., and Seshan, S., Understanding and Mitigating the Impact of RF Interference on 802.11 Networks, in ACM SIGCOMM 2007.
  • Kyle Jamieson:

  • A follow-on to SampleRate rate adaptation and related work:
    Wong, S. H. Y., Yang, H., Lu, S., Bharghavan, V., Robust Rate Adaptation in 802.11 Wireless Networks, in ACM MobiCom 2006. pdf
  • A clever variation on interference cancellation that solves the hidden terminal problem:
    Gollakota, S., and Katabi, D. ZigZag Decoding: Combating Hidden Terminals in Wireless Networks, in ACM SIGCOMM 2008. pdf
  • Allowing wideband networks to coexist with narrowband (802.11, Zigbee) devices:
    Rahul, H., Kushman, N., Katabi, D., Sodini, C., and Edalat, F., Learning to Share: Narrowband-Friendly Wideband Networks, in ACM SIGCOMM 2008. pdf
  • An indoor location system that uses a combination of ultrasound and RF:
    Priyantha, N. B., Chakraborty, A., and Balakrishnan, H. The Cricket Location-Support System, in ACM MobiCom 2000.
  • A wireless LAN-based location system, using RF fingerprinting, with a novel application of the Viterbi algorithm:
    Bahl, P., Padmanabhan, V. N., and Balachandran, A., Enhancements to the RADAR User Location and Tracking System. Microsoft Research Technical Report MSR-TR-2000-12, February 2000.

  • GZ06/M038 Presentation Guidelines


    The final component of assessment for GZ06/M038 is a student-given presentation on a research paper. You and your fellow group members select a paper, prepare a presentation on it, and deliver the presentation.

    Students choose their own groups. Once you have formed a group, please email the instructors to notify them of your group's membership and the paper you have selected. Only one group can present a paper, and they will be given to groups on a first-come, first-served basis. So it is very much in your interest to form a group and select a paper early! Once formed, all groups will be listed here.

    Presentation Schedule

    Each presentation will take place during a one-hour lecture slot for GZ06/M038 during the last week of the half-term (9th February, 2008 - 13th February, 2009, inclusive). Your group will have 30 minutes in which to present and 20 minutes to answer questions from students and staff. Please arrive for lecture promptly!

    The presentation schedule will appear in the course calendar once groups have formed and selected papers to present.

    Submission of Presentation Materials

    Send a single electronic version of your slides (PDF or gzip'ed PostScript) as an email attachment no later than:

         9 AM Monday, 9th February, 2009

    to all course staff:

    S dot Hailes at cs dot ucl dot ac dot uk

    In your presentation to the class, you must use the same slides that you submitted by email for this 9th February deadline.

    Presentation Format

    Most groups in recent years have used a laptop to project slides; you may also use overhead projector slides, if you so desire, and any other appropriate materials or aids.

    Each group member should take a turn to speak, and all group members should speak for the same approximate duration.

    Each group's presentation should include:

    1. a summary of the work/experiments in the paper
    2. the main conclusions drawn and why the work is important
    3. a critical appraisal of the work
    4. a summary and appraisal of relevant/similar work in the area


    At least two members of staff will be present for presentations. You will be assesed on [% of marks]:

    1. presentation structure and delivery [10%]
    2. a summary of the work in the paper and the main conclusions (a and b) [10%]
    3. a critical appraisal of work in the paper (c) [15%]
    4. a summary and appriasal of some relevant/similar work (d) [15%]
    5. responses to questions [10%]
    6. a short individual report (3 pages of A4 maximum, plus references) discussing the main issues with respect to future development and application of the particular technology/system you have presented. This should be a personal viewpoint backed-up by references to literature in support of the statements in your discussion. [40%]

    The marksheet that the assessors will use for the presentations can be found here.

    Note that:

    Each student must submit his individual report by:

         Friday, 20th February, 2009

    You will be required to submit the individual report both electronically and on paper; you will be sent further instructions by email concerning how and when you should do so.

    Paper notes and errata