Local Algorithms for Topology Control in Ad-Hoc Networks

Local Algorithms for Topology Control in Ad-Hoc Networks

Evangelos Kranakis (Carleton University, Canada) and Jorge Urrutia (Universidad Nacional Autonoma de Mexico, Mexico)
Copyright: © 2011 |Pages: 8
DOI: 10.4018/978-1-60566-250-3.ch006
OnDemand PDF Download:
No Current Special Offers


In this chapter, we present a survey of recent techniques for local topology control in location aware Unit Disk Graphs including local algorithms for Routing, Traversal, Planar Spanners, Dominating and Connected Dominating Sets, and Vertex and Edge Coloring. In addition to investigating trade-offs for these problems, we discuss open problems that will play an important role in the future development of the subject.
Chapter Preview

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.

Complete Chapter List

Search this Book: