Local Algorithms for Topology Control in Ad-Hoc Networks

2 Background

Algorithms devised for traditional wire-line systems are not always adequate in ad hoc networking. In dynamically changing ad hoc networks, participating hosts cannot be assumed to have knowledge of the entire system. In addition, it is often impractical or even impossible to explore the whole network prior to executing an algorithm since by the time the entire system has been examined a new change may have occurred that was not taken into account.

In this setting, locality emerges as an important concept. In local algorithms it is required that the status of a node depends only on the nodes at most a constant number (independent of the size of the network) of edges (hops) away from it. Introduced by (Linial [1992]), this model has the advantage that each node in the network need only be aware of the existence of other parts of the network that are only a constant (usually small) number of hops away from it. Algorithmic design based on locality guarantees stability (changes in the network outside a constant neighborhood do not influence the computation), consistency of solutions regardless of the order of execution, and constant termination time of the proposed algorithm. This approach was further investigated in the work of (Naor and Stockmeyer [1995]) which investigated constant-time solutions for labeling problems and the book of (Peleg [2000]) which proposes a locality-sensitive approach to distributed computing.