We propose the correctness proofs and the complexity analysis for the first self-stabilizing constructions of connected overlays
for wireless networks (eg. MANETs, WSN) based on the computation of
Connected Dominating Set (CDS). The basic idea is to construct an overlay that contains a small number of nodes, but still obtain full connectivity
of the network while only relying on local exchanges of information and knowledge. We adopt two methodologies of construction:
the first methodology consists of two parallel tasks, namely, computing a
maximal independent set (MIS) and then adding bridge nodes between the MIS nodes. The second methodology computes a connected dominating set using
the observation that a dominator is a bridge between nodes that do not share the same neighborhood.
The proposed algorithms are fully decentralized and are designed in a self-stabilizing manner in order to cope with transient
faults, mobility and nodes join/leave. In particular, they do not need to be (re)initialized after a fault or a physical topology
change. That is, whatever the initial configuration is, the algorithms satisfy their specification after a stabilization period.
The convergence time of our algorithms is linear in the size of the network and they use only one extra bit of memory. We
also present an optimization of our algorithms that reduces the number of nodes in the cover. However, the optimization increases
the convergence time with a constant factor.