AN IMPROVED TWO-PHASED APPROXIMATION OF MINIMUM CONNECTED DOMINATING SETS IN UNIT DISK GRAPHS USING TWO-HOP DEGREE CENTRALITY

Minimum connected dominating set (MCDS) offers an optimized route in wireless networks. However, constructing an MCDS is an NP-complete problem. Many heuristics based approximation algorithms for MCDS problems have been previously reported. Nevertheless, results of these algorithms are not close enough to MCDS. In this paper, a new two-phased algorithm (THDCBTPS) is proposed for approximating an MCDS in unit disk graphs (UDGs) by using two-hop degree (D-2) centrality of the nodes. The main contributions of this paper are as follows. Firstly, a better approximation for MIS in the first phase is achieved by considering D-2. Secondly, an improved Steiner tree construction is proposed to obtain fewer connectors in the second phase, which leads to a smaller CDS. Thirdly, the upper bound of proposed approach is proved to be 6.075\opt\ + 5.425 which is better than most of existing methods. Simulation results show that THDCBTPS constructs better CDSs for networks with random distribution of nodes in UDG.