Distributed Structures for Multihop Networks

A fundamental challenge in multihop networks is to organize the network so as to enable efficient and reliable communication and cooperation among the nodes. A natural approach to this problem is to create and maintain distributed structures that store relevant control information about the network. Such structures, which include spanning trees, dominating sets, independent sets, clusterings and other network decompositions, play an important role in a variety of schemes for frequency and bandwidth allocation, routing, location management, and resource discovery. In this tutorial, we survey a number of techniques for designing and maintaining these structures that have been proposed in the distributed computing and wireless networking literature. We also study the impact of varying degrees of node and object mobility on the effectiveness of these techniques.

  • Latest version, given at Cornell University, September 2002 (Powerpoint slides)
  • An earlier version given, joint with Torsten Suel, in August 2000 at
        DIMACS Summer School on Foundations of Wireless Networks and Applications