Algorithmic Foundations of Ad Hoc Networks

Summer School at ETH Zurich, June 30 - July 3, 2004

Andrea Richa (Arizona State)
Rajmohan Rajaraman (Northeastern)

An ad hoc network consists of a collection of geographically distributed nodes that communicate with one other over a wireless medium. An ad hoc network differs from both wired and cellular networks in that there is no wired infrastructure and the communication and computation capabilities of the network are limited by the battery power of the network nodes. In recent years, the rapid advent of mobile telephony, personal digital assistants, and the increasing deployment of diverse monitoring tools involving inexpensive wireless sensors and RFID tags have brought to the fore a number of commercial applications of ad hoc networks. Examples are disaster relief, conferencing, home networking, habitat monitoring, warehouse inventory monitoring, and personal area networks.

The lack of a fixed infrastructure in ad hoc networks implies that any computation on the network needs to be carried out in a decentralized manner. Thus, many of the important problems in ad hoc networking can be formulated as problems in distributed computing. However, there are several intrinsic characteristics of ad hoc networks -- e.g., energy limitations, the need for medium access control, limited computational power, mobility -- that makes this study different than traditional work in distributed computing.

In this tutorial, we will cover the algorithmic foundations of ad hoc networks. Our presentation will focus on the following topics, which are by no means exhaustive:

  1. Introduction: General overview, models, and routing paradigms
  2. Clustering: dominating sets, connected dominating sets, and clustering under mobility
  3. Medium access protocols (MAC) and their analyses
  4. Power control
  5. Topology control: connectivity, energy-efficiency, and interference
  6. Fundamental limits of ad hoc network capacity
  7. Algorithms for sensor networks: MAC protocols, synchronization protocols, and query and stream processing

Part II of the tutorial (topics 3 through 7) is avaliable here as Powerpoint slides (pdf file). The references listing the citations in the tutorial are here.

Acknowledgment: This work was partially supported by NSF IIS-0330201 "SENSORS: Data driven sensor networks".