Improved algorithms for construction of connected dominating set in MANETs

The paper proposes two distributed algorithms for the construction of a connected dominating set (CDS) in a mobile ad hoc network. The CDS can be used as a virtual backbone for efficient communication in the ad hoc networks and consequently allow scalability of distributed algorithms implemented for these networks. The proposed algorithms organize the entire network topology into clusters and the CDS is formed out of the nodes acting as the cluster heads (CHs). The paper proposes improvements in some existing algorithms to yield a smaller sized CDS or cause a low message overhead during CDS construction. The simulation results verify the effectiveness of the proposed algorithms as compared to the existing algorithms.