Constructing minimum extended weakly-connected dominating sets for clustering in ad hoc networks

Motivated by cooperative communication in ad hoc networks , Wu et al. proposed extended dominating set (EDS) where each node in an ad hoc network is covered by either a dominating neighbor or several 2-hop dominating neighbors, and defined two types of dominating sets: extended strongly connected dominating set (ECDS) and extended weakly connected dominating set (EWCDS), according to the success of a broadcast process. An EWCDS is an effective method for clustering. In this paper, we extend the dominative capabilities of nodes such that each forward node dominates not only itself and its regular neighbors fully, but also its quasi-neighbors partly. Based on this extension, three novel algorithms to find EWCDSs in ad hoc networks are proposed. The correctness and performance of our algorithms are confirmed through theoretical analysis and comprehensive simulations. ► We extend the dominative capability of nodes to find small EWCDSs in graphs. ► We design an extended area-based algorithm (EAA) for EWCDSs. ► We propose an extended pruning algorithm (EPA) for EWCDSs. ► We give a piece-based algorithm (PA) for EWCDSs.