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