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:
Acknowledgment: This work was partially supported by NSF IIS-0330201 "SENSORS: Data driven sensor networks".