| Wireless ad hoc networks are infrastructure-less multi-hop networks consisting of mobile (such as in mobile ad hoc networks) or stationary (such as in wireless sensor networks) wireless devices. These networks involve several challenges, including limited bandwidth and energy resources, frequent topology changes, and a lack of central control. Local acting, self-organizing, and self-healing algorithms (also called localized algorithms) are essential to the design of wireless ad hoc networks. A connected dominating set (CDS) is frequently used in wireless ad hoc networks as a virtual backbone to support efficient routing, service discovery, and area monitoring. In addition, efficient broadcasting (i.e., finding a small set of forward nodes to ensure full delivery) can be viewed as forming a CDS on-the-fly. The periodically maintained virtual backbone is called a static CDS, and the temporarily formed forward node set is called a dynamic CDS. For efficiency and robustness, the ideal CDS construction algorithm is lightweight, has fast convergence, and minimizes the CDS size. This dissertation focuses on providing a generic framework to unify localized CDS construction schemes, including both static and dynamic CDS constructions, for wireless ad hoc networks. The goal is to provide insights on how to form a small CDS (forward node set) in dynamic networks with affordable overhead and high robustness. A classification of CDS construction algorithms for wireless ad hoc networks has been provided at the beginning. An efficient scheme, called Rule K, has been proposed for static CDS construction. Rule K achieves a probabilistic constant upper bound on the expected CDS size, which is currently the best known performance guarantee for localized CDS algorithms. Rule K has been extended to a unified framework, called the coverage condition, which contains most existing localized virtual backbone construction and efficient broadcast algorithms as its special cases. The coverage condition has been further extended to construct a k-connected k-dominating set for higher robustness, and integrated in an iterative process that further reduces the CDS size while maintaining the same level of robustness. |
