Fast connected dominating set construction in mobile ad hoc networks

The connected dominating set (CDS) has been commonly used for routing and broadcast in mobile ad hoc networks (MANETs). Considering the applications of MANETs, it is generally preferred that the CDS protocol not only creates CDS of small size, incurs less communication and computational overheads, adapts to the nodal mobility, but also generates CDS as quickly as possible. Unfortunately, none of the existing CDS protocols possesses all of these desirable properties. In this paper, we propose an algorithm to rapidly grow a CDS tree from an initiator. By incorporating this algorithm with the Multi-Initiator CDS protocol, we have created the CDS protocol for MANETs which enjoys all the aforementioned desirable properties. The simulation results validate that our proposed protocol achieves its design goals. In addition, an analytical model is provided that can accurately estimate the convergence time required by our proposed CDS protocol.