Mobile Computing

Today we witness that three recent tech success stories (cellular phones, the Internet, and ultra light computing devices such as personal digital assistants) are being unified into what is dubbed "mobile computing".

The goal of this course is to discuss the principles of mobile computing and wireless communication. We start with radio transmission and work our way up the networking stack by discussing the usual suspects: media access and logical link control, network and transport layer with mobile IP and TCP alternatives. We discuss and analyze algorithmic concepts along with real-world standards such as GSM, wireless LAN, Bluetooth, or satellites. We also study the foundations of multi-hop ad-hoc networks. After knowing the basics we home in on applications and ask how mobile computing will change the programmer's world: How do we program in disconnected operation (for example calendar synchronization); how do we deal with hardware limitations (WAP)?

We are excited about our practical exercises! They are an integral part of the course and tied in with the lecture. In the exercises we build an ad-hoc network on wireless LAN base. We start by programming the "hello world!" equivalent for ad-hoc networks, and step by step build more advanced mobile computing applications, such as instant messaging, chat, multi-hop discovery, and an awesome distributed game.

Course pre-requisites: Basic networking knowledge; it would be great if each student had a programmable "mobile" (old school schlepptop is OK) device available, and if possible a wireless LAN card (IEEE 802.11b by Cisco/Aironet or Apple/AirPort).

Course language: English written, German spoken.

Lecture by Roger Wattenhofer, Monday 10-12 @ IFW A32.

Exercises by Aaron Zollinger, Thursday 4-6 @ HRS F5. First exercise lesson: April 10.

Useful references

Lecture material

Exercise material

References

Chapter 1: Introduction

• Jochen Schiller, Mobile Communications, Chapter 1, Addison-Wesley
• Computer magazines: c't, ...
• General magazines: Der Spiegel, ...
• World Wide Web
• And many others...

Chapter 2: Physical and Link Layer

• Hermann Rohling, Einführung in die Informations- und Codierungstheorie, Teubner Studienbücher
• Andrew Tanenbaum, Computer Networks, Prentice Hall
• Jochen Schiller, Mobile Communications, Chapter 2, Addison-Wesley
• And many others...

Chapter 3: Media Access Control

• Dimitri Bertsekas, Robert Gallager, Data Networks, Prentice Hall
• Andrew Tanenbaum, Computer Networks, Prentice Hall
• Jochen Schiller, Mobile Communications, Chapter 3, Addison-Wesley
• R. Rivest, Network Control by Bayessian Broadcast, MIT Tech Report, 1985
• V. Mikhailov, Methods of Random Multiple Access, Candidate Engineering Thesis, 1979
• Van Jacobson, Michael Karels, Congestions Avoidance and Control, 1988
• D. Aldous, Ultimate instability of exponential back-off protocol for acknowledgement based transmission control of random access communication channels, IEEE Transactions on Information Theory, 1987
• J. Hastad, T. Leighton, B. Rogoff, Analysis of backoff protocols for multiple access channels, ACM Symposium on Theory of Computing, 1987
• R. Metcalfe, D. Boggs, Ethernet: Distributed packet switching for local computer networks, Communications of the ACM, 1976

Chapter 4: Wireless LAN

• Jochen Schiller, Mobile Communications, Chapter 7, Addison-Wesley
• Hermann Rohling, Einführung in die Informations- und Codierungstheorie, Teubner Studienbücher
• Own back-of-envelope calculation on fragmentation
• Scott Fluhrer, Itsik Mantin, Adi Shamir, Weaknesses in the Key Scheduling Algorithm of RC4, 2001
• Ian Goldberg, An analysis of the Wired Equivalent Privacy Protocol, 2001
• Jesse Walker, Overview of 802.11 Security, 2001

Chapter 5: Ad Hoc Networks

• Elizabeth Royer, C.-K. Toh, A review of current routing protocols for ad-hoc mobile wireless networks, 1999
• Josh Broch, David Maltz, David Johnson, Yih-Chun Hu, Jorjeta Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, MobiCom, 1998
• David B. Johnson, David A. Maltz, Dynamic Source Routing in Ad Hoc Wireless Networks, 1996

Chapter 6: Dominating Sets

• Sudipto Guha, Samir Khuller, Approximation Algorithms for Connected Dominating Sets, Algorithmica, 1998
• B. Das, E. Sivakumar, V. Bhargavan, Routing in ad Hoc Networks using a virtual backbone, 1997
• Jie Wu, Chapter 20: Dominating-Set-Based Routing in Ad Hoc Wireless Networks, in Ivan Stojmenovic: Handbook of Wireless Networks and Mobile Computing, 2002
• Fabian Kuhn, Roger Wattenhofer, Constant-Time Distributed Dominating Set Approximation, PODC, 2003

Chapter 7: Geometric Routing

• Jorge Urrutia, Chapter 18: Routing with Guaranteed Delivery in Geometric and Wireless Networks, in Ivan Stojmenovic: Handbook of Wireless Networks and Mobile Computing, 2002
• David Matula, Robert Sokal: Properties of Gabriel Graphs Relevant to Geographic Variation Research and the Clustering of Points in the Plane
• J. E. Goodman and J. O'Rourke, Handbook of Discrete and Computational Geometry, CRC Press LLC, 1997
• Evangelos Kranakis, Harvinder Singh, Jorge Urrutia, Compass Routing on Geometric Networks
• Fabian Kuhn, Roger Wattenhofer, Aaron Zollinger, Asymptotically Optimal Geometric Mobile Ad-Hoc Routing, 2002
• Fabian Kuhn, Roger Wattenhofer, Aaron Zollinger, Worst-Case Optimal and Average-Case Efficient Geometric Ad-Hoc Routing, 2003
• Fabian Kuhn, Roger Wattenhofer, Yan Zhang, Aaron Zollinger, Geometric Ad-Hoc Routing: Of Theory and Practice, 2003
• Prosenjit Bose, Pat Morin, Online Routing in triangulations
• Prosenjit Bose, Pat Morin, Ivan Stojmenovic, Jorge Urrutia, Routing with guaranteed delivery in ad hoc wireless networks
• Jinyang Li, John Jannotti, Douglas De Couto, David Karger, Robert Morris, A scalable location service for geographic ad hoc routing, MobiCom, 2000
• Martin Mauve, Joerg Widmer, Hannes Hartenstein, A survey on position-based routing in mobile ad-hoc networks, 2001

Chapter 8: Mobile IP and TCP

• James D. Solomon, Mobile IP, the Internet unplugged
• Charles E. Perkins, Mobile IP Design Principles and Practices
• Jochen Schiller, Mobile Communications, Chapter 9, Addison-Wesley
• Hari Balakrishnan, Venkata POadmanabhan, Srinivasan Seshan, Randy Katz, A Comparison of Mechanisms for Improving TCP Performance over Wireless Links, Sigcomm, 1996
• T. Lakshman, U. Madhow, The performance of TCP/IP for networks with high bandwidth-delay products and random loss, 1997
• Hung-Yuh Hsieh, Raghupathy Sivakumar, Chapter 13: Transport over Wireless Networks, in Ivan Stojmenovic: Handbook of Wireless Networks and Mobile Computing, 2002
• Jochen Schiller, Mobile Communications, Chapter 10, Addison-Wesley

Chapter 9: GSM

• Jochen Schiller, Mobile Communications, Chapter 4, Addison-Wesley
• Lata Narayanan, Chapter 4: Channel Assignment and Graph Multicoloring, in Ivan Stojmenovic: Handbook of Wireless Networks and Mobile Computing, 2002
• Jeannette Janssen, Chapter 5: Channel Assignment and Graph Labeling, in Ivan Stojmenovic: Handbook of Wireless Networks and Mobile Computing, 2002
• Ioannis Caragiannis, Christos Kaklamanis, Evi Papaioannou, Efficient On-line Communication in Cellular Networks, SPAA, 2000
• Ioannis Caragiannis, Christos Kaklamanis, Evi Papaioannou, Efficient On-line Frequency Allocation and Call Control in Cellular Networks, TOCS, 2001