Connected Dominating Set in Wireless Ad Hoc Networks: Variations with Applications

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, selforganizing,
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 dynamk 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.