| Wireless ad hoc networks (or simply ad hoc networks) are infrastructureless multihop networks consisting of mobile or stationary wireless devices, which include mobile ad hoc networks (MANETs) and wireless sensor networks (WSNs). These networks are characterized by limited bandwidth and energy resources, frequent topology changes, and a lack of central control. These characteristics lead to the research challenges of ad hoc networks. The algorithms designed for ad hoc networks should be localized, self-organizing, and energy efficient. A connected dominating set (CDS) is frequently used in 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. Recently, due to some specific applications and new techniques, the concept of a connected dominating set can be modified or further extended for more efficient usage.; This dissertation focuses on the variations with applications of the connected dominating set, designing new concepts, and developing new algorithms for them. A review of CDS construction algorithms for 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. Several CDS algorithms are extended to generate the extended CDS, which exploits the cooperative communication technique to further reduce the size of CDS. A k-coverage set is developed for higher robustness. With the equipment of directional antennas, the transmission can be restricted to some certain directions to reduce interference and energy consumption. The corresponding directional CDS is discussed. Finally, a wireless sensor and actor network (WSAN) is introduced and localized algorithms are designed for it. |
