Mobile Intelligence

2.2 RELATED WORK

In this section, we discuss related work with respect to topology control in two categories: transmission range control and hierarchical topology organization (in the context of connected dominating set formation).

2.2.1 Transmission Range Control

Most of the existing topology control algorithms select a less-than-normal transmission range (also called the actual transmission range) while maintaining network connectivity. Centralized algorithms [26] construct optimized solutions based on global information and, therefore, are not suitable in wireless ad hoc networks. Some probabilistic algorithms [8] adjust transmission range to maintain an optimal number of neighbors. However, probabilistic algorithms do not provide hard guarantees on network connectivity. Most of the localized topology control algorithms use nonuniform actual transmission ranges computed from one-hop information (under the normal transmission range) and take advantage of some original research topics in computational geometry, such as the minimum spanning tree [20], the Delaunay triangulation [19], or the relative neighborhood graph [21]. Most of these contributions mainly considered energy efficiency of paths in the resulting topology. The CBTC algorithm [18] was the first construction to focus on several desired properties. A nice literature review of transmission range control can be found in Ref. [4].

2.2.2 Connected Dominating Set

Das et al. proposed a MCDS-based routing algorithm for wireless ...